Submission #588363

#	Time	Username	Problem	Language	Result	Execution time	Memory
588363		Blagojce	Distributing Candies (IOI21_candies)	C++17	0 / 100	128 ms	18712 KiB

candies

#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] = v[0];
	fr(i, 1, q){
		sum[i] = sum[i-1] + v[i];
	}
	
	
	
	
	
	
	
    ll suf[q+1];
    suf[q] = 0;
    for(int i = q-1; i >= 0; i --){
		suf[i] = suf[i+1] + v[i];
	}
	ll Min[q+1];
	ll Max[q+1];

	Min[q] = 1e18;
	Max[q] =-1e18;
	for(int i = q-1; 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;
		for(int b = (q+1)/2; b >= 1; b /= 2){
			while(k1-b >= 0 && Max[k1-b] - Min[k1-b] <= c[i]) k1 -= b;
		}
		
		ll h = sum[q-1];
		if(k1 == 0){
			sol.pb(h);
		}
		else{
			if(sum[k1] > sum[k1-1]){
				sol.pb(h-sum[k1]+c[i]);
			}
			else{
				sol.pb(h-sum[k1]);
			}
		}
	}
	
	
	
	
	
    
    
    
    return sol;
 
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33