제출 #1199212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199212		repsak	모임들 (IOI18_meetings)	C++20	0 / 100	3678 ms	756864 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 + 1, vector<ll>(N + 1));

  // 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(precomp[i][aCop], precomp[i][aCop - 1]);
      aCop++;
    }

    int bCop = i - 1;
    while(bCop >= 0){
      precomp[i][bCop] = max(precomp[i][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) {
  // int Q = L.size();
  // std::vector<long long> C(Q);
  // for (int j = 0; j < Q; ++j) {
  //   C[j] = H[L[j]];
  // }

  return solve(H, L, R);
  // return C;
}

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