Submission #3003410
Source Code Expand
#include <iostream> #include <string> #include <queue> #include <vector> #include <set> #include <map> #include <algorithm> #include <utility> #include <iomanip> #define ll long long int #define pb push_back #define mk make_pair #define pq priority_queue using namespace std; typedef pair<int, int> P; typedef pair<ll, int> Pl; typedef pair<ll, ll> Pll; const int inf = 1e9; const ll linf = 1LL << 50; int n; ll W; int v[201], w[201]; ll dp[201][200001]; ll vsum = 0; bool comp(const Pll &a, const Pll &b){ if(a.first != b.first)return a.first > b.first; else return a.second > b.second; } ll calc1(){ vector<Pll> vec; for(int i = 0; i < (1 << (n / 2)); i++){ ll wtmp = 0; ll vtmp = 0; for(int j = 0; j < n / 2; j++){ if((i >> j) % 2 == 1){ wtmp += w[j]; vtmp += v[j]; } } if(wtmp <= W)vec.pb(mk(wtmp, vtmp)); } sort(vec.begin(), vec.end(), comp); ll res = 0; for(int i = 0; i < (1 << (n - n / 2)); i++){ ll wtmp = 0; ll vtmp = 0; for(int j = 0; j < n - n / 2; j++){ if((i >> j) % 2 == 1){ wtmp += w[n / 2 + j]; vtmp += v[n / 2 + j]; } } if(wtmp <= W){ int index = lower_bound(vec.begin(), vec.end(), mk(W-wtmp, linf), comp) - vec.begin(); for(int j = index; j < vec.size(); j++){ res = max(res, vtmp + vec[j].second); } } } return res; } ll calc2(){ for(int i = 0; i < n; i++){ dp[i+1][0] = 0; for(int j = 1; j <= W; j++){ dp[i+1][j] = dp[i][j]; if(j - w[i] >= 0)dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i]); } } ll res = 0; for(int j = 1; j <= W; j++){ res = max(res, dp[n][j]); } return res; } ll calc3(){ for(int i = 0; i <= n; i++){ for(int j = 0; j <= vsum; j++){ dp[i][j] = linf; } } dp[0][0] = 0; for(int i = 0; i < n; i++){ dp[i+1][0] = 0; for(int j = 1; j <= vsum; j++){ dp[i+1][j] = dp[i][j]; if(j - v[i] >= 0)dp[i+1][j] = min(dp[i+1][j], dp[i][j-v[i]] + w[i]); } } ll res = 0; for(int i = 0; i <= vsum; i++){ if(dp[n][i] <= W)res = i; } return res; } int main(int argc, char const* argv[]) { cin >> n >> W; ll wsum = 0; for(int i = 0; i < n; i++)cin >> v[i] >> w[i]; for(int i = 0; i < n; i++)wsum += w[i]; for(int i = 0; i < n; i++)vsum += v[i]; if(n <= 30)cout << calc1() << endl; else if(wsum <= 200000)cout << calc2() << endl; else cout << calc3() << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - ナップサック問題 |
User | fumiphys |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 2567 Byte |
Status | AC |
Exec Time | 1058 ms |
Memory | 312832 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 34 / 34 | 33 / 33 | 33 / 33 | ||||||||
Status |
|
|
|
|
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 | 256 KB |
subtask00_sample_2.txt | AC | 6 ms | 256 KB |
subtask00_sample_3.txt | AC | 1 ms | 256 KB |
subtask00_sample_4.txt | AC | 1 ms | 256 KB |
subtask01_0.txt | AC | 6 ms | 256 KB |
subtask01_1.txt | AC | 6 ms | 256 KB |
subtask01_10.txt | AC | 6 ms | 256 KB |
subtask01_11.txt | AC | 6 ms | 256 KB |
subtask01_12.txt | AC | 6 ms | 256 KB |
subtask01_13.txt | AC | 6 ms | 256 KB |
subtask01_14.txt | AC | 6 ms | 256 KB |
subtask01_2.txt | AC | 6 ms | 256 KB |
subtask01_3.txt | AC | 6 ms | 256 KB |
subtask01_4.txt | AC | 6 ms | 256 KB |
subtask01_5.txt | AC | 1058 ms | 892 KB |
subtask01_6.txt | AC | 6 ms | 256 KB |
subtask01_7.txt | AC | 6 ms | 256 KB |
subtask01_8.txt | AC | 6 ms | 256 KB |
subtask01_9.txt | AC | 6 ms | 256 KB |
subtask02_0.txt | AC | 91 ms | 312064 KB |
subtask02_1.txt | AC | 66 ms | 311680 KB |
subtask02_10.txt | AC | 66 ms | 311680 KB |
subtask02_11.txt | AC | 71 ms | 311808 KB |
subtask02_12.txt | AC | 74 ms | 311808 KB |
subtask02_13.txt | AC | 61 ms | 311552 KB |
subtask02_14.txt | AC | 63 ms | 311552 KB |
subtask02_2.txt | AC | 85 ms | 312064 KB |
subtask02_3.txt | AC | 66 ms | 311680 KB |
subtask02_4.txt | AC | 85 ms | 312064 KB |
subtask02_5.txt | AC | 63 ms | 311552 KB |
subtask02_6.txt | AC | 81 ms | 312064 KB |
subtask02_7.txt | AC | 74 ms | 311808 KB |
subtask02_8.txt | AC | 66 ms | 311680 KB |
subtask02_9.txt | AC | 81 ms | 312064 KB |
subtask03_0.txt | AC | 106 ms | 312832 KB |
subtask03_1.txt | AC | 104 ms | 312832 KB |
subtask03_10.txt | AC | 103 ms | 312832 KB |
subtask03_11.txt | AC | 61 ms | 311552 KB |
subtask03_2.txt | AC | 102 ms | 312832 KB |
subtask03_3.txt | AC | 103 ms | 312832 KB |
subtask03_4.txt | AC | 103 ms | 312832 KB |
subtask03_5.txt | AC | 103 ms | 312832 KB |
subtask03_6.txt | AC | 103 ms | 312832 KB |
subtask03_7.txt | AC | 102 ms | 312832 KB |
subtask03_8.txt | AC | 100 ms | 312704 KB |
subtask03_9.txt | AC | 104 ms | 312832 KB |