제출 #1111925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111925		SalihSahin	모임들 (IOI18_meetings)	C++14	19 / 100	637 ms	786432 KiB

meetings

#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "meetings.h"

const long long inf = 1e17;

//#include "meetings.h"

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int n = H.size();

  vector<vector<int> > mx(n, vector<int>(n));
  for(int i = 0; i < n; i++){
    mx[i][i] = H[i];
  }

  for(int i = 0; i < n; i++){
    for(int j = i+1; j < n; j++){
      mx[i][j] = max(mx[i][j-1], H[j]);
    }
  }

  vector<vector<long long> > pre(n, vector<long long>(n)), suf(n, vector<long long>(n));
  for(int i = 0; i < n; i++){
    pre[i][i] = H[i];
    suf[i][i] = H[i];
  }
  for(int i = 0; i < n; i++){
    for(int j = i+1; j < n; j++){
      pre[i][j] = pre[i][j-1] + mx[i][j];
    }
  }
  for(int i = n-1; i >= 0; i--){
    for(int j = i+1; j < n; j++){
      suf[i][j] = suf[i+1][j] + mx[i][j];
    }
  }

  int Q = L.size();
  vector<long long> C(Q);
  for (int j = 0; j < Q; ++j) {
    long long ans = inf;
    for(int i = L[j]; i <= R[j]; i++){
      ans = min(ans, suf[L[j]][i] + pre[i][R[j]] - H[i]);
    }
    C[j] = ans;
  }

  return C;
}

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