結果

問題 No.973 余興
ユーザー shibh308
提出日時 2019-12-06 01:39:18
言語 Go
(1.23.4)
結果
AC  
実行時間 651 ms / 4,000 ms
コード長 1,602 bytes
コンパイル時間 15,349 ms
コンパイル使用メモリ 239,976 KB
実行使用メモリ 347,220 KB
最終ジャッジ日時 2024-12-17 21:07:10
合計ジャッジ時間 33,935 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func readLine() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	n_x := strings.Split(readLine(), " ")
	n, _ := strconv.ParseInt(n_x[0], 10, 0)
	x, _ := strconv.ParseInt(n_x[1], 10, 0)

	arr := strings.Split(readLine(), " ")
	a := [5000]int64{}
	for i, elm := range arr {
		val, _ := strconv.ParseInt(elm, 10, 0)
		a[i] = val
	}
	left := [5000]int64{}
	right := [5000]int64{}
	l := int64(0)
	r := int64(0)
	sum := int64(0)

	for l != n {
		for r != n && sum+a[r] <= x {
			sum += a[r]
			r++
		}
		left[l] = r - l
		sum -= a[l]
		l++
	}
	l = n - 1
	r = n - 1
	sum = 0
	for r >= 0 {
		for l != -1 && sum+a[l] <= x {
			sum += a[l]
			l--
		}
		right[r] = r - l
		sum -= a[r]
		r--
	}
	dp_l := [5000][5001]int64{}
	dp_r := [5000][5001]int64{}

	for i := int64(0); i <= n; i++ {
		for j := int64(0); j < n; j++ {
			if i == 0 {
				dp_l[j][i] = 0
				dp_r[j][i] = 0
				continue
			}
			l = j
			r = j + i - 1
			if r >= n {
				break
			}
			cnt := left[l]
			if cnt > i-1 {
				cnt = i - 1
			}
			x := dp_r[r][i-1] - dp_r[r][i-cnt-1]
			if x != cnt {
				dp_l[l][i] = dp_l[l][i-1] + 1
				dp_r[r][i] = dp_r[r][i-1] + 1
				continue
			}

			cnt = right[r]
			if cnt > i-1 {
				cnt = i - 1
			}
			x = dp_l[l][i-1] - dp_l[l][i-cnt-1]
			if x != cnt {
				dp_l[l][i] = dp_l[l][i-1] + 1
				dp_r[r][i] = dp_r[r][i-1] + 1
				continue
			}
			dp_l[l][i] = dp_l[l][i-1]
			dp_r[r][i] = dp_r[r][i-1]
		}
	}
	if dp_l[0][n] == dp_l[0][n-1] {
		fmt.Println("B")
	} else {
		fmt.Println("A")
	}
}
0