oj.uz

답안 #588416

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588416 2022-07-03T09:13:53 Z Blagojce 사탕 분배 (IOI21_candies) C++17
29 / 100
 128 ms 17308 KB 
#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;
	
	ll H = 0;
	fr(i, 1, q+1){
		sum[i] = sum[i-1] + v[i-1];
		H += v[i-1];
		if(H < 0) H = 0;
	}
	
	
	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(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, 2});
	for(auto u : ans) cout<< u<<' ';
	cout<<endl;
	
}
*/

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 118 ms 12380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 55 ms 9804 KB Output is correct
4 Correct 53 ms 4248 KB Output is correct
5 Correct 126 ms 15820 KB Output is correct
6 Correct 107 ms 16592 KB Output is correct
7 Correct 107 ms 17188 KB Output is correct
8 Correct 128 ms 15812 KB Output is correct
9 Correct 105 ms 17308 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -