結果
問題 | No.783 門松計画 |
ユーザー |
![]() |
提出日時 | 2019-01-11 22:13:18 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 24 ms / 2,000 ms |
コード長 | 1,211 bytes |
コンパイル時間 | 502 ms |
コンパイル使用メモリ | 56,592 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-23 12:17:15 |
合計ジャッジ時間 | 1,348 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
ソースコード
#include <iostream>using namespace std;int n, c;int l[55], w[55];int memo[55][55][55];int calc(int x, int pp, int p){if(memo[x][pp][p] != -1) return memo[x][pp][p];int ret = 0;for(int i = 1; i <= n; i++){if(pp < p && l[i] > p) continue;if(pp > p && l[i] < p) continue;if(l[i] == p || l[i] == pp) continue;if(x+w[i] > c) continue;ret = max(ret, calc(x+w[i], p, l[i]) + l[i]);}return memo[x][pp][p] = ret;}bool check(int p, int q){int x = l[p], y = l[q];for(int i = 1; i <= n; i++){if(x == l[i] || y == l[i]) continue;if(w[p]+w[q]+w[i] > c) continue;if(x < y && y > l[i]) return true;if(x > y && y < l[i]) return true;}return false;}int main(void){cin >> n >> c;for(int i = 1; i <= n; i++) cin >> l[i];for(int i = 1; i <= n; i++) cin >> w[i];for(int i = 0; i < 55; i++){for(int j = 0; j < 55; j++){for(int k = 0; k < 55; k++){memo[i][j][k] = -1;}}}int ans = 0;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(l[i] == l[j]) continue;if(w[i]+w[j] > c) continue;if(!check(i, j)) continue;ans = max(ans, calc(w[i]+w[j], l[i], l[j]) + l[i]+l[j]);}}cout << ans << endl;return 0;}