Submission #356846

#	Time	Username	Problem	Language	Result	Execution time	Memory
356846		Kerim	Packing Biscuits (IOI20_biscuits)	C++17	100 / 100	859 ms	1132 KiB

biscuits

#include "biscuits.h"
#include "bits/stdc++.h"
#define ff first
#define ss second
using namespace std;
 
typedef long long ll;
ll X,tmp;vector<ll>a;
map<ll,ll>dp[61];
ll rec(int pos,ll cur){
	if(pos==61)return 1;
  	__typeof((dp[pos]).begin())it=dp[pos].lower_bound(cur),itt;
	if(it!=dp[pos].end()){
		if(it->ff==cur)return it->ss;itt=it;
		if(itt!=dp[pos].begin()){itt--;if(itt->ss==it->ss)return it->ss;}
	}	
	ll &ret=dp[pos][cur];
	ret=rec(pos+1,(cur+a[pos])/2);
	if(a[pos]+cur>=X)ret+=rec(pos+1,(a[pos]+cur-X)/2);
	it=dp[pos].upper_bound(cur);
	if(it!=dp[pos].end() and it->ss==ret){
		itt=it;itt++;
		if(itt!=dp[pos].end() and itt->ss==ret)
			dp[pos].erase(it);
	}it--;
	if(it!=dp[pos].begin()){it--;
		if(it->ss==ret){itt=it;
			if(itt!=dp[pos].begin()){itt--;
				if(itt->ss==ret)dp[pos].erase(it);
			}
		}
	}
	return ret;
}
long long count_tastiness(long long x, vector<long long> A) {X=x;a=A;
	for(int i=0;i<61;i++)dp[i].clear();
	while(int(a.size())<61)a.push_back(0);
	for(int i=0;i<60;i++)if(a[i]>x)tmp=(a[i]-x)/2,a[i+1]+=tmp,a[i]-=tmp<<1;	
	return rec(0,0);
}

Compilation message (stderr)

biscuits.cpp: In function 'll rec(int, ll)':
biscuits.cpp:14:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   14 |   if(it->ff==cur)return it->ss;itt=it;
      |   ^~
biscuits.cpp:14:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   14 |   if(it->ff==cur)return it->ss;itt=it;
      |                                ^~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 23 / 23