Submission #2593735


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using VL = vector<lint>;
using VVL = vector<VL>;
using P = pair<lint, lint>;
signed main() {
  cin.tie(0); ios::sync_with_stdio(false);
  lint n, c; cin >> n >> c;
  VL v(n), w(n); for (int i = 0; i < n; i++) cin >> v[i] >> w[i];
  if (*max_element(w.begin(), w.end()) <= 1000) {
    VVL dp(n + 1, VL(1000 * n + 1));
    for (int i = 0; i < n; i++) {
      dp[i + 1] = dp[i];
      for (int j = 1000 * n; j >= 0; j--) {
        if (j - w[i] < 0) break;
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
      }
    }
    cout << *max_element(dp[n].begin(), dp[n].begin() + c + 1) << '\n';
  } else if(*max_element(v.begin(), v.end()) <= 1000) {
    VVL dp(n + 1, VL(1000 * n + 1, 9e18));
    for (int i = 0; i <= n; i++) dp[i][0] = 0;
    for (int i = 0; i < n; i++) {
      dp[i + 1] = dp[i];
      for (int j = 1000 * n; j >= 0; j--) {
        if (j - v[i] < 0) break;
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i]);
      }
    }
    for (int i = 1000 * n; i >= 0; i--) {
      if (dp[n][i] <= c) {
        cout << i << '\n';
        break;
      }
    }
  } else {
    vector<P> vw1, vw2;
    for (int bit = 0; bit < 1 << n / 2; bit++) {
      P vw;
      for (int i = 0; i < n / 2; i++) {
        if (bit & 1 << i) {
          vw.first += v[i];
          vw.second += w[i];
        }
      }
      vw1.push_back(vw);
    }
    for (int bit = 0; bit < 1 << n - n / 2; bit++) {
      P vw;
      for (int i = n / 2; i < n; i++) {
        if (bit & 1 << i - n / 2) {
          vw.first += v[i];
          vw.second += w[i];
        }
      }
      vw2.push_back(vw);
    }
    auto comp = [](P a, P b) { 
      return a.second > b.second or a.second == b.second and a.first > b.first;
    };
    sort(vw2.begin(), vw2.end(), comp);
    for (int i = vw2.size() - 1; i > 0; i--) {
      vw2[i - 1].first = max(vw2[i - 1].first, vw2[i].first);
    }
    lint res = 0;
    for (auto&& vw : vw1) {
      auto itr = lower_bound(vw2.begin(), vw2.end(), P(9e18, c - vw.second), comp);
      if (itr == vw2.end()) continue;
      res = max(res, vw.first + (*itr).first);
    }
    cout << res << '\n';
  }
  return 0;
}

Submission Info

Submission Time
Task D - ナップサック問題
User risujiroh
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2290 Byte
Status AC
Exec Time 252 ms
Memory 316160 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 34 / 34 33 / 33 33 / 33
Status
AC × 4
AC × 19
AC × 17
AC × 14
Set Name Test Cases
Sample subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask1 subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt
Subtask2 subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt
Subtask3 subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt
Case Name Status Exec Time Memory
subtask00_sample_1.txt AC 1 ms 384 KB
subtask00_sample_2.txt AC 9 ms 1528 KB
subtask00_sample_3.txt AC 2 ms 1152 KB
subtask00_sample_4.txt AC 2 ms 1152 KB
subtask01_0.txt AC 9 ms 1528 KB
subtask01_1.txt AC 9 ms 1528 KB
subtask01_10.txt AC 9 ms 1528 KB
subtask01_11.txt AC 9 ms 1528 KB
subtask01_12.txt AC 9 ms 1528 KB
subtask01_13.txt AC 9 ms 1528 KB
subtask01_14.txt AC 9 ms 1528 KB
subtask01_2.txt AC 9 ms 1528 KB
subtask01_3.txt AC 9 ms 1528 KB
subtask01_4.txt AC 7 ms 1528 KB
subtask01_5.txt AC 7 ms 7808 KB
subtask01_6.txt AC 7 ms 7808 KB
subtask01_7.txt AC 9 ms 1528 KB
subtask01_8.txt AC 9 ms 1528 KB
subtask01_9.txt AC 9 ms 1528 KB
subtask02_0.txt AC 249 ms 316160 KB
subtask02_1.txt AC 246 ms 316160 KB
subtask02_10.txt AC 246 ms 316160 KB
subtask02_11.txt AC 246 ms 316160 KB
subtask02_12.txt AC 246 ms 316160 KB
subtask02_13.txt AC 247 ms 316160 KB
subtask02_14.txt AC 246 ms 316160 KB
subtask02_2.txt AC 246 ms 316160 KB
subtask02_3.txt AC 247 ms 316160 KB
subtask02_4.txt AC 246 ms 316160 KB
subtask02_5.txt AC 248 ms 316160 KB
subtask02_6.txt AC 246 ms 316160 KB
subtask02_7.txt AC 247 ms 316160 KB
subtask02_8.txt AC 247 ms 316160 KB
subtask02_9.txt AC 252 ms 316160 KB
subtask03_0.txt AC 247 ms 316160 KB
subtask03_1.txt AC 247 ms 316160 KB
subtask03_10.txt AC 247 ms 316160 KB
subtask03_11.txt AC 248 ms 316160 KB
subtask03_2.txt AC 246 ms 316160 KB
subtask03_3.txt AC 247 ms 316160 KB
subtask03_4.txt AC 246 ms 316160 KB
subtask03_5.txt AC 246 ms 316160 KB
subtask03_6.txt AC 247 ms 316160 KB
subtask03_7.txt AC 247 ms 316160 KB
subtask03_8.txt AC 247 ms 316160 KB
subtask03_9.txt AC 248 ms 316160 KB