Submission #2241110
Source Code Expand
#include <iostream> #include <fstream> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #include <vector> #include <algorithm> #include <numeric> #include <map> #include <set> #include <stack> #include <queue> #include <deque> #include <functional> #include <cctype> #define BIT(a) (1 << (a)) using namespace std; vector<long long> w[4]; int main(void){ int N, W; cin >> N >> W; long long wbase; for (int i = 0; i < N; i++){ int wtmp, vtmp; cin >> wtmp >> vtmp; if (i == 0) wbase = wtmp; w[wtmp - wbase].push_back(vtmp); } for (int i = 0; i < 4; i++){ sort(w[i].begin(), w[i].end(), greater<long long>()); } for (int i = 0; i < 4; i++){ w[i].insert(w[i].begin(), 0); } for (int i = 0; i < 4; i++){ for (unsigned int j = 1; j < w[i].size(); j++){ w[i][j] += w[i][j-1]; } } /* for (int i = 0; i < 4; i++){ for (unsigned int j = 0; j < w[i].size(); j++){ printf("%lld ", w[i][j]); } printf("\n"); }*/ long long max = -1; for (unsigned int i = 0; i < w[0].size(); i++){ for (unsigned int j = 0; j < w[1].size(); j++){ for (unsigned int k = 0; k < w[2].size(); k++){ for (unsigned int l = 0; l < w[3].size(); l++){ if ((wbase)*(i)+(wbase+1)*(j)+(wbase+2)*(k)+(wbase+3)*(l) <= W){ max = max<w[0][i]+w[1][j]+w[2][k]+w[3][l]?w[0][i]+w[1][j]+w[2][k]+w[3][l]:max; } } } } } printf("%lld\n", max); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Simple Knapsack |
User | Morifo |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1500 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 |