oj.uz

Submission #303273

# Submission time Handle Problem Language Result Execution time Memory
303273 2020-09-20T06:52:01 Z model_code Packing Biscuits (IOI20_biscuits) Java 11
33 / 100
 217 ms 15820 KB 
// biscuits-yanhao-smallX-bottom_up
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 81 ms 13416 KB Output is correct
2 Runtime error 90 ms 13692 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 99 ms 13544 KB Output is correct
2 Correct 81 ms 13312 KB Output is correct
3 Correct 81 ms 13416 KB Output is correct
4 Correct 87 ms 13432 KB Output is correct
5 Correct 85 ms 13404 KB Output is correct
6 Correct 86 ms 13436 KB Output is correct
7 Correct 83 ms 13428 KB Output is correct
8 Correct 86 ms 13416 KB Output is correct
9 Correct 85 ms 13432 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 14876 KB Output is correct
2 Correct 176 ms 15192 KB Output is correct
3 Correct 170 ms 15144 KB Output is correct
4 Correct 87 ms 13356 KB Output is correct
5 Correct 82 ms 13296 KB Output is correct
6 Correct 83 ms 13556 KB Output is correct
7 Correct 81 ms 13160 KB Output is correct
8 Correct 215 ms 15820 KB Output is correct
9 Correct 217 ms 15568 KB Output is correct
10 Correct 85 ms 13680 KB Output is correct
11 Correct 97 ms 13688 KB Output is correct
12 Correct 136 ms 14700 KB Output is correct
13 Correct 205 ms 15156 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 206 ms 15528 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 81 ms 13416 KB Output is correct
2 Runtime error 90 ms 13692 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -