Submission #1226314

#TimeUsernameProblemLanguageResultExecution timeMemory
1226314Theo830Packing Biscuits (IOI20_biscuits)C++17
100 / 100
9 ms840 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ll,ii> #define id pair<ll,vector<ll> > #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training #include "biscuits.h" ll sum[65] = {0}; ll dp[65][65]; ll solve(ll i,ll j){ if(i == -1){ return 1; } if(dp[i][j] != -1){ return dp[i][j]; } ll ans; if(sum[j] & (1LL<<i)){ ans = solve(i-1,62); if(sum[i] >= (1LL<<i)){ if((sum[j] % (1LL<<(i+1))) < sum[i]){ ans += solve(i-1,j); } else{ ans += solve(i-1,i); } } } else{ ans = solve(i-1,j); } return dp[i][j] = ans; } long long count_tastiness(long long x, std::vector<long long> a){ while(a.size() < 62){ a.pb(0); } sum[0] = 0; memset(dp,-1,sizeof dp); f(i,0,61){ sum[i] = a[i] * (1LL<<i); if(i){ sum[i] += sum[i-1]; } } f(i,0,61){ sum[i] /= x; sum[i] = min(sum[i],(1LL<<(i+1)) - 1); } sum[62] = (1LL<<60) - 1; ll ans = 1; f(j,0,61){ if(sum[j] >= (1LL<<j)){ ans += solve(j-1,j); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...