제출 #585944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585944		jasmin	모임들 (IOI18_meetings)	C++14	19 / 100	5603 ms	8132 KiB

meetings

#include<bits/stdc++.h>
using namespace std;
#include<meetings.h>
#define int long long

const int inf=1e18;

vector<int> minimum_costs(vector<int32_t> h, vector<int32_t> l, vector<int32_t> r){
    int n=h.size(); int q=l.size();

    vector<int> cost(q, inf);
    vector<int> left(n);
    vector<int> right(n);
    vector<pair<int,int> > stack;
    int value=0;
    for(int i=0; i<q; i++){

        left.assign(n, 0);
        right.assign(n, 0);
        
        stack.clear(); int last=-1;
        value=0;
        for(int j=l[i]; j<=r[i]; j++){

            int cnt=0;
            while(!stack.empty() && stack[last].first<h[j]){
                value-=stack[last].first*stack[last].second;
                cnt+=stack[last].second;
                stack.pop_back();
                last--;
            }

            
            left[j]=value;
            left[j]+=cnt*h[j];
            stack.push_back({h[j], cnt+1});
            value+=h[j]*(cnt+1);
            last++;
        }
        stack.clear(); last=-1; value=0;
        for(int j=r[i]; j>=l[i]; j--){

            int cnt=0;
            while(!stack.empty() && stack[last].first<h[j]){
                value-=stack[last].first*stack[last].second;
                cnt+=stack[last].second;
                stack.pop_back();
                last--;
            }

            right[j]=value;
            right[j]+=cnt*h[j];
            stack.push_back({h[j], cnt+1});
            value+=h[j]*(cnt+1);
            last++;
        }

        int best=inf;
        for(int j=l[i]; j<=r[i]; j++){
            best=min(best, left[j]+right[j]+h[j]);
        }
        cost[i]=best;
    }

    return cost;
}

/*signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n>> q;
    vector<int32_t> h(n);
    for(int i=0; i<n; i++){
        cin >> h[i];
    }
    vector<int32_t> l(q);
    vector<int32_t> r(q);
    for(int i=0; i<q; i++){
        cin >> l[i] >> r[i];
    }

    vector<int> ans=minimum_costs(h, l, r);
    for(auto e: ans){
        cout << e << "\n";
    }
}*/

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40