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
Task X - Tower
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1003 Byte
Status
Exec Time 128 ms
Memory 235520 KB

Judge Result

Set Name Score / Max Score Test Cases
All 100 / 100 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