Submission #546872

#TimeUsernameProblemLanguageResultExecution timeMemory
546872LucaDantasPacking Biscuits (IOI20_biscuits)C++17
12 / 100
1078 ms612 KiB
#include "biscuits.h" #include <bits/stdc++.h> using namespace std; long long brute(long long x, std::vector<long long> a) { long long ans = 0; while(a.size() < 20) a.push_back(0); for(int mask = 0; mask <= 100000; mask++) { long long tem = 0; bool ok = 1; for(int b = 0; b < 20; b++) { tem += a[b]; if(mask&(1<<b)) { if(tem >= x) tem -= x; else {ok = 0; break;} } tem >>= 1; } ans += ok; } return ans; } long long x_leq_10000(long long x, std::vector<long long> a) { while(a.size() < 128) a.push_back(0); int atv = 0; for(int i = 0; i+1 < a.size(); i++) { if(a[i]&1) a[i+1] += a[i]/2, a[i] = 1; else a[i+1] += max(0ll, a[i]/2-1), a[i] = min(a[i], 2ll); atv += a[i] > 0; } long long dp[20010]{}, new_dp[20010]{}; dp[0] = 1, dp[x] = 1; for(int i = (int)(a.size()) - 1; i >= 0; i--) { for(int qtd = 0; qtd <= x; qtd++) new_dp[qtd] = dp[(a[i] + qtd)/2] + (a[i]+qtd >= x ? dp[(a[i] + qtd - x) / 2] : 0); for(int qtd = 0; qtd <= x; qtd++) dp[qtd] = new_dp[qtd]; } return dp[0]; } long long count_tastiness(long long x, std::vector<long long> a) { if(x <= 10000) return x_leq_10000(x, a); return brute(x, a); }

Compilation message (stderr)

biscuits.cpp: In function 'long long int x_leq_10000(long long int, std::vector<long long int>)':
biscuits.cpp:29:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i+1 < a.size(); i++) {
      |                    ~~~~^~~~~~~~~~
#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...