Submission #588404

#TimeUsernameProblemLanguageResultExecution timeMemory
588404BlagojceDistributing Candies (IOI21_candies)C++17
0 / 100
111 ms12344 KiB
#include "candies.h" #include <bits/stdc++.h> #define fr(i, n, m) for(int i = (n); i < (m); i ++) #define pb push_back #define st first #define nd second #define all(x) begin(x), end(x) #define pq priority_queue using namespace std; typedef long long ll; int n; int q; std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { n = c.size(); q = v.size(); ll sum[q+1]; sum[0] = 0; fr(i, 1, q+1){ sum[i] = sum[i-1] + v[i-1]; } ll Min[q+2]; ll Max[q+2]; Min[q+1] = 1e18; Max[q+1] =-1e18; for(int i = q; i >= 0; i--){ Min[i] = min(Min[i+1], sum[i]); Max[i] = max(Max[i+1], sum[i]); } vector<int> sol; fr(i, 0, n){ int k1 = q+1; for(int b = (q+3)/2; b >= 1; b /= 2){ while(k1-b >= 0 && Max[k1-b] - Min[k1-b] <= c[i]) k1 -= b; } ll h = sum[q]; if(k1 == 0){ sol.pb(max(0LL, h)); continue; } if(sum[k1] > sum[k1-1]){ sol.pb(max(0LL, h-Max[k1]+c[i])); } else{ sol.pb(max(0LL, h-Min[k1])); } } return sol; } /* int main(){ vector<int> ans = distribute_candies({10, 15, 13}, {0, 0}, {2, 2}, {-2, -3}); for(auto u : ans) cout<< u<<' '; cout<<endl; }*/
#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...