제출 #1181829

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181829		HappyCapybara	Meetings (IOI18_meetings)	C++17	19 / 100	5593 ms	6324 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int N;

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
  N = H.size();
  int Q = L.size();
  vector<ll> C(Q, 1ll<<50);
  for (int i=0; i<Q; i++){
    vector<ll> lc(N, 0), rc(N, 0);
    stack<pair<ll,pair<ll,ll>>> s;
    for (int j=L[i]; j<=R[i]; j++){
      lc[j] = H[j];
      if (j != L[i]) lc[j] += lc[j-1];
      while (!s.empty() && H[j] > s.top().first){
        lc[j] += ((ll) H[j]-s.top().first)*s.top().second.first;
        s.pop();
      }
      if (s.empty()) s.push({H[j], {j-L[i]+1, j}});
      else s.push({H[j], {j-s.top().second.second, j}});
    }
    while (!s.empty()) s.pop();
    for (int j=R[i]; j>=L[i]; j--){
      rc[j] = H[j];
      if (j != R[i]) rc[j] += rc[j+1];
      while (!s.empty() && H[j] > s.top().first){
        rc[j] += ((ll) H[j]-s.top().first)*s.top().second.first;
        s.pop();
      }
      if (s.empty()) s.push({H[j], {R[i]-j+1, j}});
      else s.push({H[j], {s.top().second.second-j, j}});
    }
    for (int j=L[i]; j<=R[i]; j++) C[i] = min(C[i], lc[j]+rc[j]-H[j]);
  }
  return C;
}

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