Submission #614075

#	Time	Username	Problem	Language	Result	Execution time	Memory
614075		chirathnirodha	Meetings (IOI18_meetings)	C++17	0 / 100	5568 ms	6904 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> C;
  for(int h=0;h<q;h++){
    ll ans=INT64_MAX;
    ll vall[n],valr[n];

    vector<int> v;
    ll cur=H[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(H[last]>=H[i])break;
        v.pop_back();
        if(v.empty())cur+=(H[i]-H[last])*(last-L[h]+1);
        else cur+=(H[i]-H[last])*(last-v.back());
      }
      v.PB(i);cur+=H[i];
      vall[i]=cur;
    }

    v.clear();
    cur=H[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(H[last]>=H[i])break;
        v.pop_back();
        if(v.empty())cur+=(H[i]-H[last])*(R[h]-last+1);
        else cur+=(H[i]-H[last])*(v.back()-last);
      }
      v.PB(i);cur+=H[i];
      valr[i]=cur;
    }
    for(int i=L[h];i<=R[h];i++){
      ans=min(ans,vall[i]+valr[i]-(ll)H[i]);
    }
    C.PB(ans);
  }
  return C;
}

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