Submission #1052780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052780		Itamar	Meetings (IOI18_meetings)	C++14	19 / 100	144 ms	201508 KiB

meetings

using namespace std;
#include <vector>
#define ll long long
#define vll vector<ll>

vll h;
const int siz = 5002;
int maxi[siz][siz];
ll q(int a,int b){
  if(a>b)return 0;
  int in = maxi[a][b];
  return min((b-in+1)*h[in]+q(a,in-1), (in-a+1)*h[in]+q(in+1,b));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  for(int hi :H)h.push_back(hi);
  int Q = L.size();
  std::vector<ll> ans(Q);
  int N= H.size();
  for(int i = 0; i < N; i++){
    int m = i;
    for(int j = i; j < N; j++){
      if(H[j]>H[m])m=j;
      maxi[i][j]=m;
    }
  }
  for (int j = 0; j < Q; ++j) {
    ans[j] = q(L[j],R[j]);
  }

  return ans;
}

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