oj.uz

Submission #862539

# Submission time Handle Problem Language Result Execution time Memory
862539 2023-10-18T13:10:13 Z sunwukong123 Packing Biscuits (IOI20_biscuits) C++14
12 / 100
 17 ms 1116 KB 
#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long 
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
int ans;

long long count_tastiness(long long X, std::vector<long long> vec) {
	ans=1;//0
	unordered_map<int,int> pref;
	pref[-1]=1;
	while((int)vec.size()<140)vec.push_back(0);
	for(int i=0;i<140;i++){ // let's count the numbers st the biggest bit is 2^i
		int smallest=i;
		int debt=0;
		for(int j=i-1;j>=0;j--){ // let's find smallest j such that i can fill everything from [j,i-1]
			debt*=2;
			debt+=X;
			debt-=vec[j];
			if(debt<=0)smallest=min(smallest,j);
			if(debt>oo)break; // no way to repay
			debt=max(0ll,debt); 
		}
		pref[i]=pref[i-1];
		if(smallest == i){
			if(vec[i]>=X){
				ans+=pref[i-1];
				pref[i]+=pref[i-1];
				
			}
			continue;
		}
		__int128 sum = 0;
		for(int j=i;j>=smallest;j--){
			__int128 t=1ll<<(j-smallest);
			sum+=vec[j]*t;
		}
		__int128 res=sum/X;
		res=min(res,(__int128)((1ll<<(i-smallest+1))-1));

		res-=(__int128)(1ll<<(i-smallest));
		
		if(res+1<=0)continue;
		res++;
		res*=pref[smallest-1];
		ans+=(int)res;
		pref[i]+=res;
	}
	return ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 348 KB Output is correct
2 Incorrect 17 ms 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -