Submission #3746338
Source Code Expand
#include <cstdio>
#include <iterator>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
vector<int> V[87];
LL presum[87][123];
int main() {
int N, W;
scanf("%d %d", &N, &W);
int w, v;
scanf("%d %d", &w, &v);
V[0].push_back(v);
for (int i = 0; i < N - 1; i++) {
int a, b;
scanf("%d %d", &a, &b);
V[a - w].push_back(b);
}
for (int i = 0; i < 4; i++) sort(V[i].begin(), V[i].end(), greater<int>());
for (int i = 0; i < 4; i++) {
for (int j = 0; j < (int)V[i].size(); j++) {
presum[i][j + 1] = presum[i][j] + V[i][j];
}
}
LL ans = 0;
for (int i = 0; i <= (int)V[0].size(); i++)
for (int j = 0; j <= (int)V[1].size(); j++)
for (int k = 0; k <= (int)V[2].size(); k++)
for (int m = 0; m <= (int)V[3].size(); m++) {
LL tmp = (LL)(i + j + k + m) * w + (j + 2 * k + 3 * m);
if (tmp > W) continue;
LL tmpv = presum[0][i] + presum[1][j] + presum[2][k] + presum[3][m];
ans = max(ans, tmpv);
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Simple Knapsack |
User |
BOT |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
1493 Byte |
Status |
AC |
Exec Time |
2 ms |
Memory |
256 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:25:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &W);
^
./Main.cpp:27:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &w, &v);
^
./Main.cpp:31:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
^
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 |