Submission #1627542
Source Code Expand
#include <iostream> #include <algorithm> #include <vector> #define mp make_pair #define int long long using namespace std; typedef pair<int,int> P; typedef pair<int,P> PP; signed main(){ int n,w,c,a[100],b[100],dp[2][51][10001] = {}; vector<int> col[50]; cin >> n >> w >> c; for(int i = 0;i < n;i++){ int t; cin >> a[i] >> b[i] >> t; col[t - 1].push_back(i); } for(int i = 0;i < 50;i++){ int now = i % 2,next = (i + 1) % 2; for(int j = 0;j <= c;j++){ for(int m : col[i]){ int nxt[10001] = {}; for(int k = 0;k <= w;k++){ if(k + a[m] <= w) nxt[k + a[m]] = max(nxt[k + a[m]],max(dp[now][j][k],dp[next][j + 1][k]) + b[m]); } for(int k = 0;k <= w;k++) dp[next][j + 1][k] = nxt[k]; } for(int k = 0;k <= w;k++) dp[next][j][k] = max(dp[next][j][k],dp[now][j][k]); } for(int j = 0;j <= c;j++){ for(int k = 0;k <= w;k++){ dp[now][j][k] = 0; } } } int ma = 0; for(int i = 0;i <= c;i++){ for(int j = 0;j <= w;j++) ma = max(ma,dp[0][i][j]); } cout << ma << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - ナップザック |
User | hoget157 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1076 Byte |
Status | WA |
Exec Time | 80 ms |
Memory | 8320 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 5 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 08, 09, 10, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 10 ms | 8320 KB |
01 | WA | 14 ms | 8320 KB |
02 | AC | 17 ms | 8320 KB |
03 | AC | 17 ms | 8320 KB |
04 | AC | 10 ms | 8320 KB |
05 | AC | 80 ms | 8320 KB |
08 | WA | 9 ms | 8320 KB |
09 | WA | 21 ms | 8320 KB |
10 | WA | 77 ms | 8320 KB |
90 | AC | 4 ms | 8320 KB |
91 | AC | 4 ms | 8320 KB |