제출 #587742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587742		alireza_kaviani	Meetings (IOI18_meetings)	C++17	19 / 100	607 ms	234700 KiB

meetings

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

typedef long long ll;

#define SZ(x)   int((x).size())
#define lc      id << 1
#define rc      lc | 1

const ll MAXN = 5010;
const ll LOG = 22;
const ll INF = 1e18;

ll n , q , A[MAXN] , dpl[MAXN][MAXN] , dpr[MAXN][MAXN];

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    n = SZ(H); q = SZ(L);
    if(n > MAXN){
        return {};
    }
    for(int i = 0 ; i < n ; i++){
        A[i] = H[i];
    }
    for(int i = 0 ; i < n ; i++){
        ll mx = A[i];
        for(int j = i + 1 ; j < n ; j++){
            mx = max(mx , A[j]);
            dpl[i][j] = dpl[i][j - 1] + mx;
        }
    }
    for(int i = 0 ; i < n ; i++){
        ll mx = A[i];
        for(int j = i ; j >= 0 ; j--){
            mx = max(mx , A[j]);
            dpr[i][j] = dpr[i][j + 1] + mx;
        }
    }
    vector<ll> ans(q , 0);
    for(int i = 0 ; i < q ; i++){
        ll res = INF;
        for(int j = L[i] ; j <= R[i] ; j++){
            res = min(res , dpr[j][L[i]] + dpl[j][R[i]]);
        }
        ans[i] = res;
    }
    return ans;
}

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