Submission #1679899
Source Code Expand
#include<iostream> #include<string> #include<cmath> #include<queue> #include<map> #include<set> #include<list> #include<iomanip> #include<vector> #include<functional> #include<algorithm> #include<cstdio> #include<unordered_map> using namespace std; //--------------------------------------------------- //ライブラリゾーン!!!! #define int long long #define str string #define rep(i,j) for(int i=0;i<(int)(j);i++) typedef long long ll; typedef long double ld; const ll inf = 4523372036854775807; short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } }; struct P { ll pos, cost; }; bool operator<(P a, P b) { return a.cost < b.cost; } bool operator>(P a, P b) { return a.cost > b.cost; } struct B {//隣接リスト表現 ll to, cost; }; struct S {//辺の情報を入れる変数 int from, to, cost; }; struct H { int x, y; }; bool operator<(H a, H b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; } ll gcm(ll i, ll j) {//最大公約数 if (i > j) swap(i, j); if (i == 0) return j; return gcm(j%i, i); } ld rad(ld a, ld b, ld c, ld d) { return sqrt(pow(a - c, 2) + pow(b - d, 2)); }//rad=座標上の2点間の距離 int ari(int a, int b, int c) { return (a + b)*c / 2; }//等差数列の和 bool suf(ld a, ld b, ld c, ld d) { if (b <= c || d <= a) return 0; return 1; }//[a,b),[c,d) //--------------------------------------------------- //+++++++++++++++++++++++++++++++++++++++++++++++++++ int n, x, y; int t[300], h[300], dp[301][301][601]; signed main() { cin >> x >> y >> n; for (int i = 0; i < n; i++) cin >> t[i] >> h[i]; for (int i = 0; i < n; i++) for (int j = 0; j <= x; j++) for (int z = 0; z <= x + y; z++) dp[i][j][z] = -1; dp[0][0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < x; j++) { for (int z = 0; z <= x + y; z++) { if (dp[i][j][z] == -1) continue; dp[i + 1][j][z] = max(dp[i + 1][j][z], dp[i][j][z]); if (z + t[i] > x + y) continue; dp[i + 1][j + 1][z + t[i]] = max(dp[i + 1][j + 1][z + t[i]], dp[i][j][z] + h[i]); } } } int sum = 0; for (int i = 0; i <= n; i++) for (int j = 0; j <= x; j++) for (int z = 0; z <= x + y; z++) sum = max(sum, dp[i][j][z]); cout << sum << endl; getchar(); getchar(); }
Submission Info
Submission Time | |
---|---|
Task | C - 最高のトッピングにしような |
User | Thistle |
Language | C++14 (GCC 5.4.1) |
Score | 30 |
Code Size | 2303 Byte |
Status | MLE |
Exec Time | 213 ms |
Memory | 424576 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 0 / 70 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask0-sample04.txt |
Subtask1 | subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask0-sample04.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt |
Subtask2 | subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask0-sample04.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0-sample01.txt | AC | 2 ms | 4352 KB |
subtask0-sample02.txt | AC | 2 ms | 4352 KB |
subtask0-sample03.txt | AC | 2 ms | 4352 KB |
subtask0-sample04.txt | AC | 2 ms | 4352 KB |
subtask1-01.txt | AC | 5 ms | 20736 KB |
subtask1-02.txt | AC | 6 ms | 26880 KB |
subtask1-03.txt | AC | 6 ms | 26880 KB |
subtask1-04.txt | AC | 6 ms | 26880 KB |
subtask1-05.txt | AC | 6 ms | 26880 KB |
subtask1-06.txt | AC | 9 ms | 41472 KB |
subtask1-07.txt | AC | 9 ms | 41344 KB |
subtask1-08.txt | AC | 9 ms | 41216 KB |
subtask1-09.txt | AC | 12 ms | 55680 KB |
subtask1-10.txt | AC | 12 ms | 55680 KB |
subtask1-11.txt | AC | 15 ms | 70016 KB |
subtask1-12.txt | AC | 15 ms | 70016 KB |
subtask1-13.txt | AC | 15 ms | 70144 KB |
subtask1-14.txt | AC | 1 ms | 256 KB |
subtask1-15.txt | AC | 15 ms | 69888 KB |
subtask1-16.txt | AC | 15 ms | 69888 KB |
subtask1-17.txt | AC | 15 ms | 70272 KB |
subtask1-18.txt | AC | 15 ms | 70272 KB |
subtask1-19.txt | AC | 15 ms | 70272 KB |
subtask1-20.txt | AC | 16 ms | 70400 KB |
subtask1-21.txt | AC | 16 ms | 70400 KB |
subtask1-22.txt | AC | 16 ms | 70400 KB |
subtask1-23.txt | AC | 16 ms | 70400 KB |
subtask1-24.txt | AC | 16 ms | 70400 KB |
subtask1-25.txt | AC | 16 ms | 70400 KB |
subtask2-01.txt | AC | 18 ms | 84480 KB |
subtask2-02.txt | AC | 24 ms | 113152 KB |
subtask2-03.txt | AC | 29 ms | 141568 KB |
subtask2-04.txt | MLE | 80 ms | 353024 KB |
subtask2-05.txt | MLE | 89 ms | 422656 KB |
subtask2-06.txt | AC | 53 ms | 211840 KB |
subtask2-07.txt | MLE | 61 ms | 283392 KB |
subtask2-08.txt | MLE | 92 ms | 353280 KB |
subtask2-09.txt | MLE | 80 ms | 353408 KB |
subtask2-10.txt | MLE | 101 ms | 423424 KB |
subtask2-11.txt | MLE | 90 ms | 422400 KB |
subtask2-12.txt | MLE | 97 ms | 422784 KB |
subtask2-13.txt | MLE | 156 ms | 424064 KB |
subtask2-14.txt | MLE | 205 ms | 424320 KB |
subtask2-15.txt | MLE | 164 ms | 424320 KB |
subtask2-16.txt | MLE | 166 ms | 424448 KB |
subtask2-17.txt | MLE | 163 ms | 424320 KB |
subtask2-18.txt | MLE | 82 ms | 422144 KB |
subtask2-19.txt | MLE | 82 ms | 422144 KB |
subtask2-20.txt | MLE | 198 ms | 424320 KB |
subtask2-21.txt | MLE | 213 ms | 424576 KB |
subtask2-22.txt | MLE | 167 ms | 424448 KB |
subtask2-23.txt | MLE | 178 ms | 424448 KB |
subtask2-24.txt | MLE | 205 ms | 424320 KB |
subtask2-25.txt | MLE | 205 ms | 424320 KB |