제출 #431354

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

meetings

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

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define all(x) begin(x),end(x)
#define sz(v) (int)v.size()

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)
//------------------------------------------

const ll INF=1e18;

void ckmin(ll &x, ll y){x=min(x,y);}
void ckmax(int &x, int y){x=max(x,y);}

int N,Q; 
vector<ll> minimum_costs(vi H, vi L, vi R){
    N=sz(H),Q=sz(L);
        
    //compress
    ll val[N][N];
    FOR(i,0,N){
        int cur=0;
        ROF(j,0,i+1){
            ckmax(cur,H[j]);
            val[i][j]=cur; 
            if(i!=j) val[i][j]+=val[i][j+1];
        }

        cur=0;
        FOR(j,i,N){
            ckmax(cur,H[j]);
            val[i][j]=cur; 
            if(i!=j) val[i][j]+=val[i][j-1];
        }
    }

    vector<ll> res(Q);
    FOR(idx,0,Q){
        ll ans=INF;

        FOR(i,L[idx],R[idx]+1){
            ckmin(ans,val[i][L[idx]]+val[i][R[idx]]-H[i]);
        }

        res[idx]=ans; 
    }
    return res; 
}


/*

4 2
2 4 3 5
0 2
1 3

*/

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