Submission #1237263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237263		mychecksedad	모임들 (IOI18_meetings)	C++20	19 / 100	376 ms	215200 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define ll long long int
#define pii pair<int,int>
const int N = 1e5+100, M = 5010, K = 22;
 
int rmq[N][K], dp[N][K];
ll pref[M][M];
int get(int l, int r){
  int k = __lg(r-l+1);
  return max(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
  int n = H.size();
  int q = L.size();
  for(int i = 0; i < n; ++i) rmq[i][0] = H[i];
  for(int j = 1; j < K; ++j){
    for(int i = 0; i + (1<<j) <= n; ++i){
      rmq[i][j] = max(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
    }
  }
  for(int i = 0; i < n; ++i){
    pref[i][0] = get(0, i);
    for(int j = 1; j < n; ++j) pref[i][j] = pref[i][j - 1] + (i <= j ? get(i, j) : get(j, i));
  }
  vector<ll> C;
  if(n <= 5000 && q <= 5000){
    for(int _ = 0; _ < q; ++_){
      ll ans = 1e18;
      for(int i = L[_]; i <= R[_]; ++i){
        ll cur = pref[i][R[_]] - (L[_] == 0 ? 0ll : pref[i][L[_] - 1]);
        // for(int j = L[_]; j <= R[_]; ++j){
        //   if(i<=j) cur += get(i, j);
        //   else cur += get(j,i);
        // } 
        ans=min(ans,cur);
      }
      C.pb(ans);
    }
    return C;
  }

}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

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