Submission #11377240


Source Code Expand

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */


// どこまで使ったか,重さ,種類数,最後に使った色
int dp[2][10001][51][51] = {};

int main() {
  
  memset(dp, -1, sizeof(dp));
  int n, W, C; cin >> n >> W >> C;
  vector<int> w(n);
  vector<int> v(n);
  vector<int> c(n);
  vector<pair<pair<int, int>, int>> data(n);
  for (int i = 0; i < n; i++) {
    cin >> w[i] >> v[i] >> c[i];
    data[i] = {{c[i], w[i]}, v[i]};
  }

  sort(ALL(data));
  for (int i = 0; i < n; i++) {
    c[i] = data[i].first.first;
    w[i] = data[i].first.second;
    v[i] = data[i].second;
  }
  
  int cur = 0;
  int nxt = 1;
  dp[cur][0][0][0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= W; j++) {
      for (int k = 0; k <= C; k++) {
        for (int l = 0; l <= 50; l++) {
          if (dp[cur][j][k][l] == -1) continue;
          
          // if (dp[cur][j][k][l] >= 0) cerr << "i = " << i << ", j = " << j << ", k = " << k << ", l = " << l << " := " << dp[cur][j][k][l] << endl;

          // 取らない
          dp[nxt][j][k][l] = max(dp[nxt][j][k][l], dp[cur][j][k][l]);

          // 取る
          int ni = i + 1;
          int nj = j + w[i];
          int nk = (l == c[i] ? k : k + 1);
          int nl = c[i];
          if (nj <= W and nk <= C) {
            dp[nxt][nj][nk][nl] = max(dp[nxt][nj][nk][nl], dp[cur][j][k][l] + v[i]);
          }
        }
      }
    } 

    swap(cur, nxt);
  }
  
  int ans = 0;
  for (int j = 0; j <= W; j++) {
    for (int k = 0; k <= C; k++) {
      for (int l = 0; l <= 50; l++) {
        // if (dp[cur][j][k][l] >= 0) cerr << "i = " << cur << ", j = " << j << ", k = " << k << ", l = " << l << " := " << dp[cur][j][k][l] << endl;
        ans = max(ans, dp[cur][j][k][l]);
      }
    }
  }
  
  cout << ans << endl;

  return 0;
}

Submission Info

Submission Time
Task H - ナップザック
User monkukui
Language C++14 (GCC 5.4.1)
Score 5
Code Size 2697 Byte
Status AC
Exec Time 1614 ms
Memory 203520 KB

Judge Result

Set Name All
Score / Max Score 5 / 5
Status
AC × 11
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 08, 09, 10, 90, 91
Case Name Status Exec Time Memory
00 AC 176 ms 203520 KB
01 AC 223 ms 203520 KB
02 AC 308 ms 203520 KB
03 AC 307 ms 203520 KB
04 AC 157 ms 203520 KB
05 AC 1614 ms 203520 KB
08 AC 163 ms 203520 KB
09 AC 471 ms 203520 KB
10 AC 1574 ms 203520 KB
90 AC 51 ms 203520 KB
91 AC 51 ms 203520 KB