Submission #3768768
Source Code Expand
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define MAX_N (100)
using namespace std;
int dp[MAX_N + 1][MAX_N + 1][4 * MAX_N + 1] = {};
int main(int argc, char *argv[]) {
// read inputs
int N, W, ws[MAX_N], vs[MAX_N];
scanf("%d %d", &N, &W);
for (int i = 0; i < N; i++) {
scanf("%d %d", &ws[i], &vs[i]);
}
// subtract w1 from all wis
const int w0 = ws[0];
for (int i = 0; i < N; i++) {
ws[i] -= w0;
}
// solve dp
for (int n = 1; n <= N; n++) {
for (int i = 0; i < N; i++) {
const int w_i = ws[i], v_i = vs[i];
for (int j = 0; j < w_i; j++) {
dp[n][i + 1][j] = dp[n][i][j];
}
for (int j = w_i; j <= 3 * N; j++) {
dp[n][i + 1][j] = max(dp[n][i][j], dp[n - 1][i][j - w_i] + v_i);
}
}
}
// print answer
int ans = 0;
for (int n = 1; n <= N && W - n * w0 >= 0; n++) {
ans = max(ans, dp[n][N][min(W - n * w0, 3 * N)]);
}
printf("%d\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Simple Knapsack |
User |
khir |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
1018 Byte |
Status |
AC |
Exec Time |
10 ms |
Memory |
16000 KB |
Compile Error
./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:14:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &W);
^
./Main.cpp:16:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &ws[i], &vs[i]);
^
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 |
10 ms |
16000 KB |
antigreedy1 |
AC |
10 ms |
16000 KB |
antigreedy2 |
AC |
10 ms |
16000 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 |
10 ms |
16000 KB |
quarter1 |
AC |
10 ms |
16000 KB |
quarter2 |
AC |
10 ms |
16000 KB |
rand0 |
AC |
1 ms |
256 KB |
rand1 |
AC |
3 ms |
7296 KB |
rand2 |
AC |
2 ms |
4736 KB |
smallw0 |
AC |
10 ms |
16000 KB |
smallw1 |
AC |
10 ms |
16000 KB |
smallw2 |
AC |
10 ms |
16000 KB |