oj.uz

Submission #418990

# Submission time Handle Problem Language Result Execution time Memory
418990 2021-06-06T09:49:05 Z Blagojce Packing Biscuits (IOI20_biscuits) C++17
42 / 100
 1000 ms 48128 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define rfr(i, n, m) for(int i = (n); i >= (m); i --)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
#include <string>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
const int mxn = 2e5+5;
mt19937 _rand(time(NULL));
clock_t z;

#include "biscuits.h"

vector<ll> A;

int m;

vector<int> v;



ll dp[61][100000];


ll X;
ll gen(int pos, ll carry){
	
	if(pos == m-1){
		return (A[pos] + carry)/X + 1;
	}
	
	if(dp[pos][carry] != -1) return dp[pos][carry];
	
	ll tot = A[pos] + carry;

	if(tot < X){
		return gen(pos+1, tot/2);
	}	
	ll ret = 0;
	
	//if we put : 
	ret = gen(pos+1, (tot-X) / 2);
	
	//if we don't : 
	ret += gen(pos+1, tot/2);
	
	dp[pos][carry] = ret;
	return ret;
}


long long count_tastiness(long long x, std::vector<long long> a) {
	memset(dp, -1, sizeof(dp));
	X = x;
	
	
	m = (int)a.size();
		
	fr(i, 0, (int)a.size()-1){
		while(a[i] >= x+2){
			a[i] -= 2;
			a[i+1] ++;
		}
		if(a[i] >= x + 2){
			ll take = (a[i] - (x + 2) + 1) / 2;
			
			ll rem = a[i] - take*2;
			//if(rem == 0) rem += x+1;
			ll mov = (a[i]-rem);
			a[i+1] += mov/2;
			a[i] -= mov;
		}
	}
	

	
	A = a;
	
	/*for(auto u : A) cout<<u<<' ';
	cout<<endl;*/
	return gen(0, 0);
}/*
int main(){
	//cout<<count_tastiness(2, {5, 0})<<endl;
	cout<<count_tastiness(1, {10, 9, 8, 7, 6})<<endl;


}*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 48076 KB Output is correct
2 Correct 75 ms 48032 KB Output is correct
3 Correct 75 ms 48128 KB Output is correct
4 Correct 75 ms 48024 KB Output is correct
5 Correct 76 ms 48068 KB Output is correct
6 Correct 78 ms 47948 KB Output is correct
7 Correct 75 ms 48032 KB Output is correct
8 Correct 73 ms 47948 KB Output is correct
9 Correct 75 ms 48000 KB Output is correct
10 Correct 75 ms 48024 KB Output is correct
11 Correct 75 ms 48000 KB Output is correct
12 Correct 79 ms 48032 KB Output is correct
13 Correct 74 ms 48028 KB Output is correct
14 Correct 78 ms 48028 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 47948 KB Output is correct
2 Correct 51 ms 47948 KB Output is correct
3 Correct 75 ms 47940 KB Output is correct
4 Correct 74 ms 47928 KB Output is correct
5 Correct 73 ms 47976 KB Output is correct
6 Correct 75 ms 48032 KB Output is correct
7 Correct 73 ms 47948 KB Output is correct
8 Correct 73 ms 48000 KB Output is correct
9 Correct 72 ms 48028 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 48024 KB Output is correct
2 Correct 74 ms 48028 KB Output is correct
3 Correct 76 ms 47940 KB Output is correct
4 Correct 74 ms 47948 KB Output is correct
5 Correct 75 ms 48032 KB Output is correct
6 Correct 74 ms 47952 KB Output is correct
7 Correct 76 ms 47944 KB Output is correct
8 Correct 141 ms 48040 KB Output is correct
9 Correct 72 ms 47940 KB Output is correct
10 Correct 73 ms 48028 KB Output is correct
11 Correct 74 ms 47996 KB Output is correct
12 Correct 84 ms 48028 KB Output is correct
13 Correct 144 ms 48040 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 48036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 48076 KB Output is correct
2 Correct 75 ms 48032 KB Output is correct
3 Correct 75 ms 48128 KB Output is correct
4 Correct 75 ms 48024 KB Output is correct
5 Correct 76 ms 48068 KB Output is correct
6 Correct 78 ms 47948 KB Output is correct
7 Correct 75 ms 48032 KB Output is correct
8 Correct 73 ms 47948 KB Output is correct
9 Correct 75 ms 48000 KB Output is correct
10 Correct 75 ms 48024 KB Output is correct
11 Correct 75 ms 48000 KB Output is correct
12 Correct 79 ms 48032 KB Output is correct
13 Correct 74 ms 48028 KB Output is correct
14 Correct 78 ms 48028 KB Output is correct
15 Correct 74 ms 47948 KB Output is correct
16 Correct 51 ms 47948 KB Output is correct
17 Correct 75 ms 47940 KB Output is correct
18 Correct 74 ms 47928 KB Output is correct
19 Correct 73 ms 47976 KB Output is correct
20 Correct 75 ms 48032 KB Output is correct
21 Correct 73 ms 47948 KB Output is correct
22 Correct 73 ms 48000 KB Output is correct
23 Correct 72 ms 48028 KB Output is correct
24 Correct 67 ms 48024 KB Output is correct
25 Correct 74 ms 48028 KB Output is correct
26 Correct 76 ms 47940 KB Output is correct
27 Correct 74 ms 47948 KB Output is correct
28 Correct 75 ms 48032 KB Output is correct
29 Correct 74 ms 47952 KB Output is correct
30 Correct 76 ms 47944 KB Output is correct
31 Correct 141 ms 48040 KB Output is correct
32 Correct 72 ms 47940 KB Output is correct
33 Correct 73 ms 48028 KB Output is correct
34 Correct 74 ms 47996 KB Output is correct
35 Correct 84 ms 48028 KB Output is correct
36 Correct 144 ms 48040 KB Output is correct
37 Execution timed out 1100 ms 48036 KB Time limit exceeded
38 Halted 0 ms 0 KB -