Submission #1870735
Source Code Expand
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;
#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,N) for(ll i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100
ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
if (n == 0)return 1;
if (n == 1)return x%MOD;
ll res = sq(mod_pow(x, n / 2));
res %= MOD;
if (n % 2 == 1) {
res *= x;
res %= MOD;
}
return res;
}
ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }
ll N, W;
ll w[110], v[110];
ll dp[110][1100][3];
int main() {
cin >> N >> W;
ll buf = 0;
rep(i, N) {
cin >> w[i] >> v[i];
if (i == 0)buf = w[i];
w[i] -= buf;
}
rep(i, N) {
rep(j, 1100) {
rep(k, 3) {
ll ww = buf*j + k;
ww += buf + w[i];
ll nj = ww / buf;
ll nk = ww%buf;
if (ww <= W) {
dp[i + 1][nj][nk]
= max(dp[i + 1][nj][nk],
dp[i][j][k] + v[i]);
}
dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
}
}
}
ll ans = 0;
rep(i, 1100) {
rep(j, 3) {
if (i*buf + j <= W) {
ans = max(ans, dp[N][i][j]);
}
}
}
//rep(k, N + 1) {
// rep(i, 10) {
// rep(j, 3) {
// cout << dp[k][i][j] << " ";
// }
// cout << endl;
// }
// cout << endl;
//}
cout << ans << endl;
}
Submission Info
Submission Time |
|
Task |
D - Simple Knapsack |
User |
jimmy |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2116 Byte |
Status |
WA |
Exec Time |
4 ms |
Memory |
2816 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
4 ms |
2816 KB |
antigreedy1 |
AC |
4 ms |
2816 KB |
antigreedy2 |
AC |
4 ms |
2816 KB |
example0 |
AC |
1 ms |
384 KB |
example1 |
AC |
1 ms |
384 KB |
example2 |
AC |
1 ms |
384 KB |
example3 |
AC |
1 ms |
384 KB |
quarter0 |
WA |
4 ms |
2816 KB |
quarter1 |
WA |
4 ms |
2816 KB |
quarter2 |
WA |
4 ms |
2816 KB |
rand0 |
AC |
1 ms |
384 KB |
rand1 |
AC |
2 ms |
1536 KB |
rand2 |
AC |
2 ms |
896 KB |
smallw0 |
AC |
3 ms |
2816 KB |
smallw1 |
AC |
4 ms |
2816 KB |
smallw2 |
WA |
4 ms |
2816 KB |