Submission #590089

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
590089	2022-07-05T14:08:09 Z	Lucpp	Packing Biscuits (IOI20_biscuits)	C++17	33 / 100	973 ms	2097152 KB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int k = 60;
ll x;
vector<ll> a;

vector<vector<ll>> dp;

ll calc(int i, ll cnt){
	if(i == k) return 1;
	if(dp[i][cnt] != -1) return dp[i][cnt];
	ll ans = 0;
	if(cnt+a[i] >= x){
		ans += calc(i+1, (cnt+a[i]-x)/2);
	}
	ans += calc(i+1, (cnt+a[i])/2);
	return dp[i][cnt] = ans;
}

ll count_tastiness(ll x_, vector<ll> a_) {
	x = x_; a = a_;
	a.resize(k);
	for(int i = 0; i < k; i++){
		if(a[i] <= x+1) continue;
		ll cnt = (a[i]-x)/2;
		a[i] -= 2*cnt;
		a[i+1] += cnt;
	}
	dp.assign(k, vector<ll>(2*x, -1));
	return calc(0, 0);
}

Subtask #1

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	2 ms	468 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-

Subtask #2

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	300 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct

Subtask #3

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	10084 KB	Output is correct
2	Correct	19 ms	8984 KB	Output is correct
3	Correct	22 ms	9604 KB	Output is correct
4	Correct	1 ms	296 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	53 ms	10072 KB	Output is correct
9	Correct	42 ms	10068 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	428 KB	Output is correct
12	Correct	8 ms	1600 KB	Output is correct
13	Correct	62 ms	9768 KB	Output is correct

Subtask #4

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	973 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Runtime error	2 ms	468 KB	Execution killed with signal 6
3	Halted	0 ms	0 KB	-