oj.uz

Submission #306373

# Submission time Handle Problem Language Result Execution time Memory
306373 2020-09-25T10:17:11 Z llaki Packing Biscuits (IOI20_biscuits) Java 11
33 / 100
 228 ms 15732 KB 
class biscuits {

	final int x_max = (int) 1e5+1;
	long[][] dp = new long[2][2*x_max];

	long[] merge_biscuits(long x, long[] a) {
		long[] b = new long[61];
		for(int i=0; i<=60; i++) {
			b[i] = (i < a.length ? a[i] : 0);
		}
		for(int i=0; i<b.length; i++) {
			if(b[i]>x+1) {
				b[i+1] += (b[i]-x)/2;
				b[i] -= (b[i]-x)&(-2);
			}
		}
		return b;
	}

	long count_tastiness(long x, long[] a) {
		a = merge_biscuits(x, a);
		for(int j=0; j<=2*x; j++) {
			dp[0][j] = 1;
			dp[1][j] = 1;
		}
	
		for(int i=60; i>=0; i--) {
			int parity = i%2;
			for(int j=0; j<x-a[i]; j++) {
				dp[parity][j] = dp[parity^1][(int)(j+a[i])/2];
			}
			for(int j=Math.max(0,(int)(x-a[i])); j<=2*x; j++) {
				dp[parity][j] = dp[parity^1][(int)(j+a[i])/2] 
				     + dp[parity^1][(int)(j+a[i]-x)/2];
			}
		}
		return dp[0][0];
	}
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13428 KB Output is correct
2 Runtime error 92 ms 13380 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13496 KB Output is correct
2 Correct 85 ms 13424 KB Output is correct
3 Correct 90 ms 13300 KB Output is correct
4 Correct 82 ms 13288 KB Output is correct
5 Correct 91 ms 13544 KB Output is correct
6 Correct 92 ms 13436 KB Output is correct
7 Correct 85 ms 13396 KB Output is correct
8 Correct 87 ms 13412 KB Output is correct
9 Correct 84 ms 13420 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 14988 KB Output is correct
2 Correct 171 ms 15140 KB Output is correct
3 Correct 174 ms 15032 KB Output is correct
4 Correct 84 ms 13540 KB Output is correct
5 Correct 83 ms 13428 KB Output is correct
6 Correct 85 ms 13552 KB Output is correct
7 Correct 86 ms 13552 KB Output is correct
8 Correct 228 ms 15732 KB Output is correct
9 Correct 195 ms 15112 KB Output is correct
10 Correct 86 ms 13544 KB Output is correct
11 Correct 101 ms 13792 KB Output is correct
12 Correct 140 ms 14524 KB Output is correct
13 Correct 228 ms 15724 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 15116 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13428 KB Output is correct
2 Runtime error 92 ms 13380 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -