제출 #781362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
781362		vjudge1	모임들 (IOI18_meetings)	C++17	19 / 100	747 ms	196700 KiB

meetings

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

#define ll long long

// solving subtask 1 + 2 in O(N^2 + QN) time
const ll LLINF = 1ll<<60;
const int maxn = 5e3 + 10;
int n, q;
ll prefix[maxn][maxn] = {0};

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
    n = H.size();
    vector<ll> c;
    for (int i = 0; i < n; i++){
        // solving to right
        int mx = H[i];
        for (int j = i; j < n; j++){
            mx = max(mx, H[j]);
            prefix[j][i] = mx;
        }
        mx = H[i];
        for (int j = i; j >= 0; j--){
            mx = max(mx, H[j]);
            prefix[j][i] = mx;
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = 1; j < n; j++) prefix[i][j] += prefix[i][j - 1];
    }
    q = L.size();
    c.assign(q, 0);
    for (int i = 0; i < q; i++){
        ll best = LLINF;
        for (int j = L[i]; j <= R[i]; j++){
            ll val = prefix[j][R[i]] - (L[i] == 0 ? 0 : prefix[j][L[i] - 1]);
            best = min(best, val);
        }
        c[i] = best;
    }
    return c;
}

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