Submission #959296
Source Code Expand
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.IntStream;
public class Main {
int n, W;
int[] v;
int[] w;
void run() {
n = ni();
W = ni();
v = new int[n];
w = new int[n];
int maxv = 0;
int maxw = 0;
for (int i = 0; i < n; ++i) {
v[i] = ni();
w[i] = ni();
maxv = Math.max(maxv, v[i]);
maxw = Math.max(maxw, w[i]);
}
if (n <= 30) {
solve1();
} else if (maxv <= 1000) {
solve2();
} else if (maxw <= 1000) {
solve3();
} else {
int d = 0 / 0;
}
}
long dfs(int i, long sumv, long sumw) {
if (sumw > W) {
return 0;
}
if (i == n) {
return sumv;
}
return Math.max(
dfs(i + 1, sumv + v[i], sumw + w[i]),
dfs(i + 1, sumv, sumw)
);
}
void solve1() {
long sumv = IntStream.of(v).mapToLong(Long::valueOf).sum();
long sumw = IntStream.of(w).mapToLong(Long::valueOf).sum();
if (sumw <= W) {
System.out.println(sumv);
return;
}
System.out.println(dfs(0, 0, 0));
}
void solve2() {
int sumv = IntStream.of(v).sum();
long[] dp = new long[sumv + 1];
Arrays.fill(dp, Long.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = sumv; 0 <= j; --j) {
if (dp[j] == Long.MAX_VALUE) {
continue;
}
dp[j + v[i]] = Math.min(dp[j + v[i]], dp[j] + w[i]);
}
}
for (int i = sumv; 0 <= i; --i) {
if (dp[i] <= W) {
System.out.println(i);
return;
}
}
}
void solve3() {
int sumw = IntStream.of(w).sum();
long[] dp = new long[sumw + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = sumw; 0 <= j; --j) {
if (dp[j] == -1) {
continue;
}
dp[j + w[i]] = Math.max(dp[j + w[i]], dp[j] + v[i]);
}
}
long max = 0;
for (int i = sumw; 0 <= i; --i) {
if (i > W) {
continue;
}
max = Math.max(max, dp[i]);
}
System.out.println(max);
}
Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
new Main().run();
}
int ni() {
return Integer.parseInt(sc.next());
}
void debug(Object... os) {
System.err.println(Arrays.deepToString(os));
}
class BIT<T> {
int n;
ArrayList<T> bit;
BiFunction<T, T, T> bif;
/**
* 1-indexed なBinary Indexed Treeを構築する
*
* @param n 容量
* @param bif 適用させる関数
* @param sup 初期値
*/
BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {
this.n = n;
bit = new ArrayList<>(n + 1);
for (int i = 0; i < n + 1; ++i) {
bit.add(sup.get());
}
this.bif = bif;
}
/**
* iの位置の値をvで更新する
*
* @param i index
* @param v 新しい値
*/
void update(int i, T v) {
for (int x = i; x <= n; x += x & -x) {
bit.set(x, bif.apply(bit.get(x), v));
}
}
/**
* クエリー
*
* @param defaultValue 初期値
* @param i index
* @return [1, i]までfを適用した結果
*/
T reduce(T defaultValue, int i) {
T ret = defaultValue;
for (int x = i; x > 0; x -= x & -x) {
ret = bif.apply(ret, bit.get(x));
}
return ret;
}
}
long MOD = 1_000_000_007;
/**
* 繰り返し2乗法を用いたべき乗の実装
*
* @return a^r (mod 1,000,000,007)
*/
long pow(long a, long r) {
long sum = 1;
while (r > 0) {
if ((r & 1) == 1) {
sum *= a;
sum %= MOD;
}
a *= a;
a %= MOD;
r >>= 1;
}
return sum;
}
/**
* 組み合わせ
* O(n)
*
* @return {}_nC_r
*/
long C(int n, int r) {
long sum = 1;
for (int i = n; 0 < i; --i) {
sum *= i;
sum %= MOD;
}
long s = 1;
for (int i = r; 0 < i; --i) {
s *= i;
s %= MOD;
}
sum *= pow(s, MOD - 2);
sum %= MOD;
long t = 1;
for (int i = n - r; 0 < i; --i) {
t *= i;
t %= MOD;
}
sum *= pow(t, MOD - 2);
sum %= MOD;
return sum;
}
double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;
/**
* 黄金分割探索
*
* @param left 下限
* @param right 上限
* @param f 探索する関数
* @param comp 上に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue)
* 下に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue).reversed()
* @return 極値の座標x
*/
double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {
double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
double d1 = f.apply(c1);
double d2 = f.apply(c2);
while (right - left > 1e-9) {
if (comp.compare(d1, d2) > 0) {
right = c2;
c2 = c1;
d2 = d1;
c1 = divideInternally(left, right, 1, GOLDEN_RATIO);
d1 = f.apply(c1);
} else {
left = c1;
c1 = c2;
d1 = d2;
c2 = divideInternally(left, right, GOLDEN_RATIO, 1);
d2 = f.apply(c2);
}
}
return right;
}
/**
* [a,b]をm:nに内分する点を返す
*/
double divideInternally(double a, double b, double m, double n) {
return (n * a + m * b) / (m + n);
}
long gcd(long a, long b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
long lcd(long a, long b) {
return (a / gcd(a, b)) * b;
}
int lcd(int a, int b) {
return (a / gcd(a, b)) * b;
}
/**
* http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b
*/
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
public FastScanner(InputStream in) {
this.in = in;
}
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte()) return buffer[ptr++];
else return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
}
}
Submission Info
Submission Time |
|
Task |
D - ナップサック問題 |
User |
arukuka |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
100 |
Code Size |
8327 Byte |
Status |
AC |
Exec Time |
490 ms |
Memory |
30448 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
34 / 34 |
33 / 33 |
33 / 33 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt |
Subtask1 |
subtask01_0.txt, subtask01_1.txt, subtask01_10.txt, subtask01_11.txt, subtask01_12.txt, subtask01_13.txt, subtask01_14.txt, subtask01_2.txt, subtask01_3.txt, subtask01_4.txt, subtask01_5.txt, subtask01_6.txt, subtask01_7.txt, subtask01_8.txt, subtask01_9.txt, subtask00_sample_1.txt, subtask00_sample_2.txt, subtask00_sample_3.txt, subtask00_sample_4.txt |
Subtask2 |
subtask02_0.txt, subtask02_1.txt, subtask02_10.txt, subtask02_11.txt, subtask02_12.txt, subtask02_13.txt, subtask02_14.txt, subtask02_2.txt, subtask02_3.txt, subtask02_4.txt, subtask02_5.txt, subtask02_6.txt, subtask02_7.txt, subtask02_8.txt, subtask02_9.txt, subtask00_sample_1.txt, subtask00_sample_3.txt |
Subtask3 |
subtask03_0.txt, subtask03_1.txt, subtask03_10.txt, subtask03_11.txt, subtask03_2.txt, subtask03_3.txt, subtask03_4.txt, subtask03_5.txt, subtask03_6.txt, subtask03_7.txt, subtask03_8.txt, subtask03_9.txt, subtask00_sample_1.txt, subtask00_sample_4.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask00_sample_1.txt |
AC |
471 ms |
29316 KB |
subtask00_sample_2.txt |
AC |
378 ms |
29464 KB |
subtask00_sample_3.txt |
AC |
359 ms |
29336 KB |
subtask00_sample_4.txt |
AC |
358 ms |
29244 KB |
subtask01_0.txt |
AC |
363 ms |
29500 KB |
subtask01_1.txt |
AC |
375 ms |
29520 KB |
subtask01_10.txt |
AC |
357 ms |
29328 KB |
subtask01_11.txt |
AC |
364 ms |
29312 KB |
subtask01_12.txt |
AC |
363 ms |
29476 KB |
subtask01_13.txt |
AC |
373 ms |
29468 KB |
subtask01_14.txt |
AC |
376 ms |
29408 KB |
subtask01_2.txt |
AC |
358 ms |
29272 KB |
subtask01_3.txt |
AC |
360 ms |
29328 KB |
subtask01_4.txt |
AC |
360 ms |
29416 KB |
subtask01_5.txt |
AC |
368 ms |
29396 KB |
subtask01_6.txt |
AC |
360 ms |
29356 KB |
subtask01_7.txt |
AC |
361 ms |
29428 KB |
subtask01_8.txt |
AC |
364 ms |
29488 KB |
subtask01_9.txt |
AC |
362 ms |
29380 KB |
subtask02_0.txt |
AC |
455 ms |
30236 KB |
subtask02_1.txt |
AC |
460 ms |
30340 KB |
subtask02_10.txt |
AC |
458 ms |
30348 KB |
subtask02_11.txt |
AC |
447 ms |
30232 KB |
subtask02_12.txt |
AC |
450 ms |
30184 KB |
subtask02_13.txt |
AC |
363 ms |
29152 KB |
subtask02_14.txt |
AC |
448 ms |
30156 KB |
subtask02_2.txt |
AC |
457 ms |
30416 KB |
subtask02_3.txt |
AC |
457 ms |
30260 KB |
subtask02_4.txt |
AC |
447 ms |
30252 KB |
subtask02_5.txt |
AC |
484 ms |
30308 KB |
subtask02_6.txt |
AC |
490 ms |
30040 KB |
subtask02_7.txt |
AC |
467 ms |
30252 KB |
subtask02_8.txt |
AC |
467 ms |
30448 KB |
subtask02_9.txt |
AC |
480 ms |
30308 KB |
subtask03_0.txt |
AC |
471 ms |
30316 KB |
subtask03_1.txt |
AC |
468 ms |
30228 KB |
subtask03_10.txt |
AC |
457 ms |
30296 KB |
subtask03_11.txt |
AC |
370 ms |
29276 KB |
subtask03_2.txt |
AC |
465 ms |
30284 KB |
subtask03_3.txt |
AC |
455 ms |
30324 KB |
subtask03_4.txt |
AC |
467 ms |
30188 KB |
subtask03_5.txt |
AC |
451 ms |
30356 KB |
subtask03_6.txt |
AC |
449 ms |
30348 KB |
subtask03_7.txt |
AC |
454 ms |
30288 KB |
subtask03_8.txt |
AC |
460 ms |
30304 KB |
subtask03_9.txt |
AC |
454 ms |
30316 KB |