Submission #1038859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038859		huutuan	Meetings (IOI18_meetings)	C++14	19 / 100	235 ms	198404 KiB

meetings

#include "meetings.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N=1e6+10;
int pf[5010][5010], n, a[N], q;

vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L,
                                vector<int32_t> R) {
   n=H.size(), q=L.size();
   for (auto &i:L) ++i;
   for (auto &i:R) ++i;
   for (int i=1; i<=n; ++i) a[i]=H[i-1];
   vector<int> res;
   if (n<=5000 && q<=5000){
      for (int i=1; i<=n; ++i){
         for (int j=i, mx=0; j<=n; ++j){
            mx=max(mx, a[j]);
            pf[i][j]=mx;
         }
         for (int j=i, mx=0; j>=1; --j){
            mx=max(mx, a[j]);
            pf[i][j]=mx;
         }
         partial_sum(pf[i], pf[i]+n+1, pf[i]);
      }
      for (int i=0; i<q; ++i){
         int ans=1e18;
         for (int j=L[i]; j<=R[i]; ++j) ans=min(ans, pf[j][R[i]]-pf[j][L[i]-1]);
         res.push_back(ans);
      }
      return res;
   }
   return {};
}

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