Submission #4330827

---

Source Code Expand

package main

import (
	"fmt"
)

func Max(x, y int) int {
    if x < y {
        return y
    }
    return x
}

func main() {
	var A, B, tmp int
	fmt.Scan(&A)
	fmt.Scan(&B)
	var a, b []int

	dp := make([][][]int, A+1)
	for i:=0; i<A+1; i++{
		dp[i] = make([][]int, B+1)
		for j:=0; j<B+1; j++{
			dp[i][j] = make([]int, 2)
		}
	}

	for _a:=0; _a<A; _a++{
		fmt.Scan(&tmp)
		a = append(a, tmp)
	}

	for _a:=0; _a<A; _a++{
		dp[_a+1][0][0] = a[A-_a-1] + dp[_a][0][1]
		dp[_a+1][0][1] = dp[_a][0][0]
	}

	for _b:=0; _b<B; _b++{
		fmt.Scan(&tmp)
		b = append(b, tmp)
	}

	for _b:=0; _b<B; _b++{
		dp[0][_b+1][0] = b[B-_b-1] + dp[0][_b][1]
		dp[0][_b+1][1] = dp[0][_b][0]
	}

	for _a := range(a) {
		for _b := range(b) {
			dp[_a+1][_b+1][0] = Max(dp[_a][_b+1][1] + a[A-_a-1],
				dp[_a+1][_b][1] + b[B-_b-1])
			sum := 0
			for i:=A-_a-1; i<A; i++ {
				sum += a[i]
			}
			for i:=B-_b-1; i<B; i++ {
				sum += b[i]
			}
			dp[_a+1][_b+1][1] = sum - dp[_a+1][_b+1][0]
		}
	}

	fmt.Println(dp[A][B][0])
}

Submission Info

Judge Result