Submission #3767137
Source Code Expand
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e9;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }
signed main() {
int N, W;
cin >> N >> W;
vector<int> w1, w2, w3, w4;
int w, v;
rep(i, N) {
if (i == 0) {
cin >> w >> v;
w1.push_back(v);
} else {
int x;
cin >> x >> v;
if (x - w == 0)
w1.push_back(v);
else if (x - w == 1)
w2.push_back(v);
else if (x - w == 2)
w3.push_back(v);
else
w4.push_back(v);
}
}
sort(all(w1), greater<int>());
sort(all(w2), greater<int>());
sort(all(w3), greater<int>());
sort(all(w4), greater<int>());
int ans = 0;
rep(i, w1.size() + 1) {
rep(j, w2.size() + 1) {
rep(k, w3.size() + 1) {
rep(l, w4.size() + 1) {
if (W < i * w + j * (w + 1) + k * (w + 2) + l * (w + 3)) continue;
int tmp = 0;
rep(x, i) tmp += w1[x];
rep(x, j) tmp += w2[x];
rep(x, k) tmp += w3[x];
rep(x, l) tmp += w4[x];
cmax(ans, tmp);
}
}
}
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Simple Knapsack |
User |
fuu32 |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
1678 Byte |
Status |
AC |
Exec Time |
8 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 |
8 ms |
256 KB |
quarter1 |
AC |
5 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 |