Submission #4409918
Source Code Expand
#include<iostream> #include<algorithm> #include<vector> #include<functional> using namespace std; typedef long long ll; typedef pair<ll, ll> P; ll N, W; vector<vector<P>> value(4);//value[i][j] : 重さi+w1 のj番目に価値が高いもの ll sum_value[4][101], sum_weight[4][101]; ll ans = 0; void depth_first(int n, int b[4]) { if (n == 4) { ll value_total = 0, weight_total = 0; for (int i = 0; i < 4; i++) { value_total += (sum_value[i][b[i]] - sum_value[i][0]); weight_total += (sum_weight[i][b[i]] - sum_weight[i][0]); } if (weight_total <= W)ans = max(ans, value_total); return; } int next_b[4]; next_b[0] = b[0], next_b[1] = b[1], next_b[2] = b[2], next_b[3] = b[3]; for (int i = 0; i <= value[n].size(); i++) { next_b[n] = i; depth_first(n + 1 ,next_b); } } int main() { ll base_weight; cin >> N >> W; for (int i = 0; i < N; i++) { ll a, b; cin >> a >> b; if (i == 0) { base_weight = a, value[0].push_back(P(b, a)); } else { value[a - base_weight].push_back(P(b, a)); } } for (int i = 0; i < 4; i++) { sort(value[i].begin(), value[i].end(), greater<P>()); sum_value[i][0] = 0; sum_weight[i][0] = 0; for (int j = 1; j <= value[i].size(); j++) { sum_value[i][j] = sum_value[i][j - 1] + value[i][j - 1].first; sum_weight[i][j] = sum_weight[i][j - 1] + value[i][j - 1].second; } } int tmp[4] = { 0,0,0,0 }; depth_first(0, tmp); cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Simple Knapsack |
User | Sen |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1506 Byte |
Status | AC |
Exec Time | 5 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3 |
All | antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
antigreedy0 | AC | 1 ms | 256 KB |
antigreedy1 | AC | 1 ms | 256 KB |
antigreedy2 | AC | 1 ms | 256 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
example3 | AC | 1 ms | 256 KB |
quarter0 | AC | 5 ms | 256 KB |
quarter1 | AC | 5 ms | 256 KB |
quarter2 | AC | 5 ms | 256 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 2 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |
smallw0 | AC | 5 ms | 256 KB |
smallw1 | AC | 5 ms | 256 KB |
smallw2 | AC | 5 ms | 256 KB |