제출 #1355611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1355611		opeleklanos	사탕 분배 (IOI21_candies)	C++20	0 / 100	57 ms	15648 KiB

candies

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#include "candies.h"

#define ll long long



vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v){
    int n = v.size();
    vector<ll> pref(n, v[0]);
    vector<pair<ll, ll>> b(n, pair<ll, ll>()), s(n, pair<ll, ll>());

    
    for(int i = 1; i<n; i++) pref[i] = pref[i-1] + v[i];

    b[n-1] = {pref[n-1], n-1};
    s[n-1] = {pref[n-1], n-1};
    
    for(int i = n-2; i>=0; i--){
        b[i] = max(b[i+1], {pref[i], i});
        s[i] = min(s[i+1], {pref[i], i});
    }


    vector<int> ans;
    for(auto c : C){
        int l = 0, r = n-1;
        if(b[0].first - s[0].first < c){
            ans.push_back(pref[n-1]);
            continue;
        }
        while(l<r){
            int mid = (l+r+1)/2;
            if(b[mid].first - s[mid].first >= c) l = mid;
            else r = mid-1;
        }
        if(b[l].second > s[l].second) ans.push_back(c + (pref[n-1] - pref[b[l].second]));
        else ans.push_back(pref[n-1] - pref[s[l].second]);
    }

    return ans;
}

• 서브태스크 1: 0 / 3
• 서브태스크 2: 0 / 8
• 서브태스크 3: 0 / 27
• 서브태스크 4: 0 / 29
• 서브태스크 5: 0 / 33