結果
問題 | No.393 2本の竹 |
ユーザー |
![]() |
提出日時 | 2020-10-18 11:55:29 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 328 ms / 1,000 ms |
コード長 | 2,031 bytes |
コンパイル時間 | 14,109 ms |
コンパイル使用メモリ | 226,160 KB |
実行使用メモリ | 145,024 KB |
最終ジャッジ日時 | 2024-07-21 03:24:25 |
合計ジャッジ時間 | 22,419 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
package mainimport ("bufio""fmt""os""sort""strconv")var sc = bufio.NewScanner(os.Stdin)var wr = bufio.NewWriter(os.Stdout)func out(x ...interface{}) {fmt.Fprintln(wr, x...)}func getI() int {sc.Scan()i, e := strconv.Atoi(sc.Text())if e != nil {panic(e)}return i}func getF() float64 {sc.Scan()i, e := strconv.ParseFloat(sc.Text(), 64)if e != nil {panic(e)}return i}func getInts(N int) []int {ret := make([]int, N)for i := 0; i < N; i++ {ret[i] = getI()}return ret}func getS() string {sc.Scan()return sc.Text()}// min, max, asub, absなど基本関数func max(a, b int) int {if a > b {return a}return b}func min(a, b int) int {if a < b {return a}return b}func asub(a, b int) int {if a > b {return a - b}return b - a}func abs(a int) int {if a >= 0 {return a}return -a}func lowerBound(a []int, x int) int {idx := sort.Search(len(a), func(i int) bool {return a[i] >= x})return idx}func upperBound(a []int, x int) int {idx := sort.Search(len(a), func(i int) bool {return a[i] > x})return idx}func f() {n1, n2 := getI(), getI()m := getI()a := getInts(m)sort.Ints(a)a = append([]int{0}, a...)sum := n1 + n2s := make([]int, m+1)s[0] = 0for i := 0; i < m; i++ {s[i+1] += s[i] + a[i+1]}var dp [61][100100]intfor i := 0; i < 61; i++ {for j := 0; j < 100100; j++ {dp[i][j] = -1}}dp[0][n1] = 0for i := 0; i < m; i++ {for j := 0; j <= n1; j++ {if j-a[i+1] >= 0 && dp[i][j] != -1 {dp[i+1][j-a[i+1]] = dp[i][j] + 1}if sum-j-s[i] >= a[i+1] && dp[i][j] != -1 {dp[i+1][j] = dp[i][j] + 1}}}ans := -100for i := 0; i < 61; i++ {for j := 0; j < 100100; j++ {ans = max(ans, dp[i][j])}}out(ans)}func main() {defer wr.Flush()sc.Split(bufio.ScanWords)sc.Buffer([]byte{}, 1000000)// this template is new version.// use getI(), getS(), getInts(), getF()d := getI()for i := 0; i < d; i++ {f()}}