제출 #614086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
614086		chirathnirodha	모임들 (IOI18_meetings)	C++17	19 / 100	5560 ms	5688 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair 
#define F first 
#define S second 
#define P push 
typedef long long ll;


vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
  int n,q;
  n=H.size();q=L.size();
  vector<ll> hei;
  for(int i=0;i<n;i++)hei.PB((ll)H[i]);
  vector<ll> C;
  for(int h=0;h<q;h++){
    ll ans=INT64_MAX;
    ll vall[n],valr[n];

    vector<int> v;
    ll cur=hei[L[h]];vall[L[h]]=cur;
    v.PB(L[h]);
    for(int i=L[h]+1;i<=R[h];i++){
      while(!v.empty()){
        int last=v.back();
        if(hei[last]>=hei[i])break;
        v.pop_back();
        if(v.empty())cur+=(hei[i]-hei[last])*(last-L[h]+1);
        else cur+=(hei[i]-hei[last])*(last-v.back());
      }
      v.PB(i);cur+=hei[i];
      vall[i]=cur;
    }

    v.clear();
    cur=hei[R[h]];valr[R[h]]=cur;
    v.PB(R[h]);
    for(int i=R[h]-1;i>=L[h];i--){
      while(!v.empty()){
        int last=v.back();
        if(hei[last]>=hei[i])break;
        v.pop_back();
        if(v.empty())cur+=(hei[i]-hei[last])*(R[h]-last+1);
        else cur+=(hei[i]-hei[last])*(v.back()-last);
      }
      v.PB(i);cur+=hei[i];
      valr[i]=cur;
    }
    for(int i=L[h];i<=R[h];i++){
      ans=min(ans,vall[i]+valr[i]-hei[i]);
    }
    C.PB(ans);
  }
  return C;
}

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