Submission #8524381
Source Code Expand
#include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int n, W; cin >> n >> W; vector<vector<int>> vs(4, vector<int>(1, 0)); long long w0; for (int i = 0; i < n; i++) { if (i == 0) { int v; cin >> w0 >> v; vs[0].emplace_back(v); } else { int w, v; cin >> w >> v; vs[w - w0].push_back(v); } } for (auto &v: vs) { sort(v.begin(), v.end()); reverse(v.begin() + 1, v.end()); for (int i = 0; i + 1 < v.size(); i++) v[i + 1] += v[i]; } int ma = 0; #define vrep(i, v) for (int i = 0; i < v.size(); i++) vrep(i, vs[0]) vrep(j, vs[1]) vrep(k, vs[2]) vrep(l, vs[3]) { long long w = (w0 + 0) * i + (w0 + 1) * j + (w0 + 2) * k + (w0 + 3) * l; if (w > W) continue; int v = vs[0][i] + vs[1][j] + vs[2][k] + vs[3][l]; ma = max(ma, v); } cout << ma << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Simple Knapsack |
User | kyuna |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1006 Byte |
Status | AC |
Exec Time | 2 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 | 2 ms | 256 KB |
quarter1 | AC | 2 ms | 256 KB |
quarter2 | AC | 2 ms | 256 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 1 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |
smallw0 | AC | 2 ms | 256 KB |
smallw1 | AC | 2 ms | 256 KB |
smallw2 | AC | 2 ms | 256 KB |