Submission #1158562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158562		erering	Meetings (IOI18_meetings)	C++20	19 / 100	5591 ms	4416 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
#include "meetings.h"
#define pb push_back
#define ll long long
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
  vector<long long> sol;
  for(int i=0;i<L.size();i++){
      deque<pair<ll,ll>> dq;
      ll sz=R[i]-L[i]+1;
      ll pref[sz],ans=H[L[i]];
      dq.pb({H[L[i]],1});
      pref[0]=ans;
      for(int j=L[i]+1;j<=R[i];j++){
          ll cnt=1;
          while(!dq.empty() && dq.back().first<=H[j]){
              ans-=dq.back().second*dq.back().first;
              cnt+=dq.back().second;
              dq.pop_back();
          }
          dq.pb({H[j],cnt});
          ans+=dq.back().first*dq.back().second;
          pref[j-L[i]]=ans;
      }
      ans=H[R[i]];
      dq.clear();
      dq.pb({H[R[i]],1});
      ll suff[sz],idx=sz-2;
      suff[sz-1]=H[R[i]];
      for(int j=R[i]-1;j>=L[i];j--){
          ll cnt=1;
          while(!dq.empty() && dq.front().first<=H[j]){
              ans-=dq.front().second*dq.front().first;
              cnt+=dq.front().second;
              dq.pop_front();
          }
          dq.push_front({H[j],cnt});
          ans+=dq.front().first*dq.front().second;
          suff[idx]=ans;
          idx--;
      }
      ll best=1e18,cnt=0;
      for(int j=L[i];j<=R[i];j++){
        //  if(i==0 && j==L[i])cout<<pref[cnt]<<" "<<suff[cnt]<<endl;
          best=min(best,pref[cnt]+suff[cnt]-H[j]);
          cnt++;
      }
      sol.pb(best);
  }
  return sol;
}

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