結果
問題 | No.393 2本の竹 |
ユーザー |
![]() |
提出日時 | 2020-10-18 11:35:41 |
言語 | Go (1.23.4) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,284 bytes |
コンパイル時間 | 11,362 ms |
コンパイル使用メモリ | 240,060 KB |
実行使用メモリ | 119,192 KB |
最終ジャッジ日時 | 2024-07-21 03:23:35 |
合計ジャッジ時間 | 15,519 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 TLE * 1 -- * 25 |
ソースコード
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}const inf = 99var a []intvar m, n intvar dp [][]intvar r []intvar result intfunc calc(r []int, N1 int) {total := 0for _, v := range r {total += v}// fmt.Fprint(wr, r, total, " ")idx := 0cnt := 0tot := 0b := make([]int, 0)for _, e := range a {if idx < len(r) && e == r[idx] {idx++continue}if tot+e <= N1 {tot += ecnt++b = append(b, e)}}// out(b, tot)result = max(result, len(r)+cnt)}func rec(m, n, N1 int) {if m == 0 {calc(r, N1)return}x := dp[m][n]if n-a[m-1] >= 0 {y := dp[m-1][n-a[m-1]]if y+1 == x {r = append([]int{a[m-1]}, r...)rec(m-1, n-a[m-1], N1)r = r[1:]}}if dp[m-1][n] != -1 {rec(m-1, n, N1)}}func g(N, N1 int) int {n = m + 1dp = make([][]int, n)for i := 0; i < n; i++ {dp[i] = make([]int, 110000)}for i := 0; i <= N; i++ {dp[0][i] = -1}dp[0][0] = 0for i := 1; i < n; i++ {for j := 0; j <= N; j++ {dp[i][j] = dp[i-1][j]if j-a[i-1] < 0 {continue}if dp[i-1][j-a[i-1]] == -1 {continue}dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i-1]]+1)}// out(dp[i][:N+1], dp[i][N])}NN := Nfor ; NN >= 0; NN-- {if dp[m][NN] != -1 {break}}// out(dp[m][:N+1])r = make([]int, 0, m)result = 0rec(m, NN, N1)ret := result// ret := 0// for _, r := range route {// total := 0// for _, v := range r {// total += v// }// // fmt.Fprint(wr, r, total, " ")// idx := 0// cnt := 0// tot := 0// b := make([]int, 0)// for _, e := range a {// if idx < len(r) && e == r[idx] {// idx++// continue// }// if tot+e <= N1 {// tot += e// cnt++// b = append(b, e)// }// }// // out(b, tot)// ret = max(ret, len(r)+cnt)// }return ret}func f() {n1, n2 := getI(), getI()m = getI()a = getInts(m)sort.Ints(a)ret := g(n1, n2)// ret = max(g(n2, n1), ret)out(ret)}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()}}