oj.uz

Submission #963450

# Submission time Handle Problem Language Result Execution time Memory
963450 2024-04-15T03:30:07 Z 8pete8 Packing Biscuits (IOI20_biscuits) C++17
21 / 100
 55 ms 34136 KB 
//#include "biscuits.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include <cstdint>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
#define int long long
#define double long double
int lg=60;
long long count_tastiness(long long x, vector<ll>v) {
	int sum;
	if(x==1){
		int k=v.size();
		vector<int>nv(k+65);
		k=nv.size();
		for(int i=0;i<k-1;i++){
			if(i<v.size())nv[i]+=v[i];
			if(nv[i]==0)continue;
			if(nv[i]%2)nv[i+1]+=(nv[i]/2),nv[i]=1;
			else nv[i+1]+=((nv[i]-2)/2),nv[i]=2;//spread
		}
		int idk=2*k;
		vector<vector<int>>dp(k+5,vector<int>(idk+5,0));
		dp[0][0]=1;
		for(int i=0;i<k;i++){
			for(int j=idk;j>=nv[i];j--)dp[i][j]=dp[i][j-nv[i]];//shifting
			for(int j=nv[i]-1;j>=0;j--)dp[i][j]=0;
			for(int j=idk;j>=0;j--){
				if(j-x>=0)dp[i+1][(j-1)/2]+=dp[i][j];
				dp[i+1][(j/2)]+=dp[i][j];
			}
		}
		sum=0;//not using anything
		for(int i=0;i<=idk;i++)sum+=dp[k][i];
		return sum;
	}
	else{
		int k=v.size();
		sum=0;
		for(auto i:v)sum+=i;
		if(sum>100000)assert(0);
		vector<vector<int>>dp(k+63,vector<int>(sum+5,0));
		dp[0][0]=1;
		for(int i=0;i<=k+61;i++){
			if(i<v.size()){
				for(int j=sum;j>=v[i];j--)dp[i][j]=dp[i][j-v[i]];//shifting
				for(int j=v[i]-1;j>=0;j--)dp[i][j]=0;
			}
			for(int j=sum;j>=0;j--){
				if(j-x>=0)dp[i+1][(j-x)/2]+=dp[i][j];//use x
				dp[i+1][(j/2)]+=dp[i][j];//
			}
		}
		int ans=0;//not using anything
		for(int i=0;i<=sum;i++)ans+=dp[k+62][i];
		return ans;
	}
}
/*
int32_t main(){
	int x,k;cin>>x>>k;
	vector<int>in(k);
	for(int i=0;i<k;i++)cin>>in[i];
	cout<<count_tastiness(x,in)<<'\n';
}*/

Compilation message

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:46:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    if(i<v.size())nv[i]+=v[i];
      |       ~^~~~~~~~~
biscuits.cpp:74:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    if(i<v.size()){
      |       ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 55 ms 34136 KB Output is correct
4 Correct 22 ms 9084 KB Output is correct
5 Correct 10 ms 8140 KB Output is correct
6 Correct 21 ms 11172 KB Output is correct
7 Correct 6 ms 3944 KB Output is correct
8 Correct 22 ms 11040 KB Output is correct
9 Correct 10 ms 7496 KB Output is correct
10 Correct 30 ms 11308 KB Output is correct
11 Correct 18 ms 7180 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 3 ms 1248 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 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 692 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 1 ms 632 KB Output is correct
9 Correct 1 ms 600 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 608 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 55 ms 34136 KB Output is correct
4 Correct 22 ms 9084 KB Output is correct
5 Correct 10 ms 8140 KB Output is correct
6 Correct 21 ms 11172 KB Output is correct
7 Correct 6 ms 3944 KB Output is correct
8 Correct 22 ms 11040 KB Output is correct
9 Correct 10 ms 7496 KB Output is correct
10 Correct 30 ms 11308 KB Output is correct
11 Correct 18 ms 7180 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 3 ms 1248 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 692 KB Output is correct
21 Correct 1 ms 352 KB Output is correct
22 Correct 1 ms 632 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Runtime error 1 ms 608 KB Execution killed with signal 6
25 Halted 0 ms 0 KB -