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
AC × 4
AC × 12
WA × 4
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