Submission #1188712

#TimeUsernameProblemLanguageResultExecution timeMemory
1188712hyakupPacking Biscuits (IOI20_biscuits)C++20
35 / 100
6 ms948 KiB
#include "biscuits.h" #include <bits/stdc++.h> using namespace std; #define ll long long ll count_tastiness( ll x, vector<ll> a ){ for( int i = 0; i < (int)a.size(); i++ ) if( a[i] > x ){ if( i == (int)a.size() - 1 ) a.push_back(0); ll aux = (a[i] - x)/2; a[i + 1] += aux; a[i] -= 2*aux; } int n = a.size(); vector<ll> sum( n, a[0] ); for( int i = 1; i < n; i++ ) sum[i] = sum[i - 1] + (a[i]<<i); vector<ll> resp(n + 1, 1); auto solve = [&]( int id, ll val ){ ll ans = 1LL; for(; id >= 0; id-- ){ val = min( val, sum[id] ); if( (val>>id) >= x ) ans += resp[id], val -= (x<<id); } return ans; }; // resp[i + 1] corresponde ao bit i for( int i = 0; i < n; i++ ){ resp[i + 1] = resp[i]; if( (sum[i]>>i) < x ) continue; resp[i + 1] += solve( i - 1, sum[i] - (x<<i) ); } return resp.back(); }
#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...