oj.uz

Submission #306036

# Submission time Handle Problem Language Result Execution time Memory
306036 2020-09-24T10:34:10 Z Yousef_Salama Packing Biscuits (IOI20_biscuits) C++17
0 / 100
 2 ms 384 KB 
#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

long long count_tastiness(long long x, vector <long long> a){
	int k = a.size();
	
	vector <long long> p2(k);
	
	p2[0] = 1;
	for(int i = 1; i < k; i++)
		p2[i] = p2[i - 1] * 2;
	
	vector < vector <long long> > b(k, vector <long long>(k));
	for(int i = 0; i < k; i++){
		long long total = 0;
		for(int j = 0; j <= i; j++)
			total += p2[j] * a[j];
			
		for(int j = i; j >= 0; j--){
			if(total / p2[j] >= x){
				b[k - i - 1][k - j - 1] = 1;
				total -= p2[j] * x;
			}else{
				b[k - i - 1][k - j - 1] = 0;
			}
		}
	}
	/*
	for(int i = 0; i < k; i++){
		for(int j = 0; j < k; j++)
			cout << b[i][j] << ' ';
		cout << endl;
	}
	*/
	
	auto cmp = [&](int i, int j){
					for(int l = max(i, j); l < k; l++){
						if(b[i][l] < b[j][l]){
							return true;
						}else if(b[i][l] > b[j][l]){
							return false;
						}
					}
					return false;
				};
	
	vector < vector <long long> > dp(k, vector <long long>(k));
	
	for(int i = k - 1; i >= 0; i--)
	for(int j = 0; j <= i; j++){
		if(i == k - 1){
			if(b[j][i] == 1)dp[i][j] = 2;
			else dp[i][j] = 1;
		}else{
			if(cmp(j, i + 1))dp[i][j] = dp[i + 1][j];
			else dp[i][j] = dp[i + 1][i + 1];

			if(b[j][i] == 1)dp[i][j] += dp[i + 1][i + 1];
		}
	}
	
	return dp[0][0];
}

/*
int main(){
	cout << count_tastiness(3, {5, 2, 1}) << endl;
	cout << count_tastiness(2, {2, 1, 2}) << endl;
	
	return 0;
}
*/

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 21.0

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

Subtask #4
0 / 35.0

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

Subtask #5
0 / 23.0

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