Contest Duration: ~ (local time) (300 minutes)

Submission #11972119

Source Code Expand

Copy
```#include <bits/stdc++.h>
#define chmax(x, y) do { x = max(x, y);} while(0)
typedef long long int ll;

using namespace std;

ll N;
struct T{
ll w, s, v;
};

vector<T> a;
ll dp[2000][30000]; // dp[i][j]: i番目のブロックまでみて、合計の重さがjのときの最大価値

int main() {
cin >> N;
for (int i=0; i<N; i++) {
ll w, s, v;
cin >> w >> s >> v;
a.push_back({w,s,v});
}
sort(begin(a), end(a), [](const T &l, const T &r) {
return min(l.s, r.s - l.w) > min(r.s, l.s - r.w);
});
dp[0][a[0].w] = a[0].v;
dp[0][0] = 0;
for (int i=0; i<N-1; i++) for (int j=0; j<30000; j++) {
int ni = i+1;
// niを置かない
chmax(dp[ni][j], dp[i][j]);
// niを置く
int nj = j + a[ni].w;
if (nj < 30000 && j <= a[ni].s) {
chmax(dp[ni][nj], dp[i][j] + a[ni].v);
}
}
ll ans = -1;
for (int j=0; j<30000; j++) {
chmax(ans, dp[N-1][j]);
}
cout << ans << endl;
return 0;
}

```

#### Submission Info

Submission Time 2020-04-16 14:25:05+0900 X - Tower bobuhiro11 C++14 (GCC 5.4.1) 100 1003 Byte AC 128 ms 235520 KB

#### Judge Result

Set Name All
Score / Max Score 100 / 100
Status
 AC × 25
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20
Case Name Status Exec Time Memory
0_00 2 ms 768 KB
0_01 2 ms 896 KB
0_02 2 ms 1152 KB
0_03 2 ms 1920 KB
1_00 1 ms 256 KB
1_01 128 ms 235520 KB
1_02 107 ms 235520 KB
1_03 91 ms 235520 KB
1_04 92 ms 235520 KB
1_05 94 ms 235520 KB
1_06 94 ms 235520 KB
1_07 94 ms 235520 KB
1_08 96 ms 235520 KB
1_09 94 ms 235520 KB
1_10 96 ms 235520 KB
1_11 99 ms 235520 KB
1_12 102 ms 235520 KB
1_13 100 ms 235520 KB
1_14 99 ms 235520 KB
1_15 99 ms 235520 KB
1_16 100 ms 235520 KB
1_17 100 ms 235520 KB
1_18 99 ms 235520 KB
1_19 100 ms 235520 KB
1_20 99 ms 235520 KB