Submission #1035229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035229		NeroZein	Meetings (IOI18_meetings)	C++17	19 / 100	5565 ms	5468 KiB

meetings

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

vector<int> h, ql, qr;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
  h = H; ql = L, qr = R;
  int n = (int) H.size();
  int q = (int) L.size();
  vector<long long> ret(q);
  for (int qind = 0; qind < q; ++qind) {
    vector<long long> change(n); 
    int l = ql[qind], r = qr[qind];
    for (int i = l; i < r; ++i) {
      if (h[i] < h[i + 1]) {//there's a suffix that will get affected (increase)
        int mx = 0;
        for (int j = i; j >= l; --j) {
          if (h[j] >= h[i + 1]) {
            break; 
          }
          mx = max(mx, h[j]); 
          change[i] += (h[i + 1] - mx);
        }
      } else if (h[i] > h[i + 1]) {
        int mx = 0;
        for (int j = i + 1; j <= r; ++j) {
          if (h[j] >= h[i]) {
            break; 
          }
          mx = max(mx, h[j]);
          change[i] -= (h[i] - mx); //there's a prefix of him that will decrease
        }
      }
    }
    long long init_cost = 0; 
    for (int i = l, mx = 0; i <= r; ++i) {
      mx = max(mx, h[i]);
      init_cost += mx; 
    }
    long long mn = init_cost;
    for (int i = l; i < r; ++i) {
      init_cost += change[i];
      mn = min(mn, init_cost); 
    }
    ret[qind] = mn; 
  }
  return ret; 
}

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