제출 #288213

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

meetings

#include <bits/stdc++.h>
using namespace std ;
#define pb push_back 
typedef long long ll ;
typedef vector < int > vi ;
typedef vector < ll > vll ;
const ll inf = 1e18 ;
#include "meetings.h"
ll n , q ;
ll h  [5009] ;
ll cost [5009][5009] , sum [5009][5009] ;
ll calc ( ll id , ll l , ll r ) {
        return ( l <= r ? sum [id][r] - ( l ? sum [id][l-1] : 0 ) : 0 ) ;
}
vll minimum_costs ( vi H , vi L , vi R) {
        n = H .size () , q = L .size () ;
        for ( ll i = 0 ; i < n ; i ++ ) {
                h [i] = H [i] ;
        }
        for ( ll i = 0 ; i < n ; i ++ ) {
                ll mx = 0 ;
                for ( ll j = i ; j < n ; j ++ ) {
                        mx = max ( mx , h [j] ) ;
                        cost [i][j] = mx ;
                }
                mx = 0 ;
                for ( ll j = i ; j >= 0 ; j -- ) {
                        mx = max ( mx , h [j] ) ;
                        cost [i][j] = mx ; 
                }
                ll crnt = 0 ;
                for ( ll j = 0 ; j < n ; j ++ ) {
                        crnt += cost [i][j] ;
                        sum [i][j] = crnt ;
                }
        }
        vll ans ;
        for ( int i = 0 ; i < q ; i ++ ) {
                ll l = L [i] , r = R [i] , mn = inf ;
                for ( ll j = l ; j <= r ; j ++ ) {
                        mn = min ( mn , calc ( j , l , r ) ) ;
                }
                ans .pb ( mn ) ;
        }
        return ans ;
}

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