Submission #1199229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199229		repsak	모임들 (IOI18_meetings)	C++20	19 / 100	3594 ms	851968 KiB

meetings

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

vector<ll> solve(vector<int> H, vector<int> L, vector<int> R){
  int N = H.size();
  int Q = L.size();

  vector<vector<int>> precomp(N, vector<int>(N));
  vector<vector<ll>> prefix(N, vector<ll>(N + 1, 0));

  // Compute minimums O(N^2)
  for(int i = 0; i < N; i++){
    precomp[i][i] = H[i];

    int aCop = i + 1;
    while(aCop < N){
      precomp[i][aCop] = max(H[aCop], precomp[i][aCop - 1]);
      aCop++;
    }

    int bCop = i - 1;
    while(bCop >= 0){
      precomp[i][bCop] = max(H[bCop], precomp[i][bCop + 1]);
      bCop--;
    }
  }

  // Calc prefixes O(N^2)
  for(int i = 0; i < N; i++){
    for(int j = 1; j <= N; j++){
      prefix[i][j] = prefix[i][j - 1] + precomp[i][j - 1];
    }
  }

  // Make queries O(N*Q)
  vector<ll> C(Q);

  for(int i = 0; i < Q; i++){
    int l = L[i]; int r = R[i];
    ll best = 1e18;

    for(int j = l; j <= r; j++){
      best = min(best, prefix[j][r + 1] - prefix[j][l]);
    }
    
    C[i] = best;
  }

  return C;
}


std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  return solve(H, L, R);
}

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