Submission #81928

#	Time	Username	Problem	Language	Result	Execution time	Memory
81928		wleung_bvg	Meetings (IOI18_meetings)	C++14	19 / 100	562 ms	398992 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define all(a) (a).begin(),(a).end()
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define FOR(i,b) For(i,0,b)
#define Rev(i,a,b) for(auto i=(a);i>(b);i--)
#define REV(i,a) Rev(i,a,-1)
#define FORE(i,a) for(auto&&i:a)
#define sz(a) (int((a).size()))
#define MIN(a,b) ((a)=min((a),(b)))
#define MAX(a,b) ((a)=max((a),(b)))
using ll=long long;using ld=long double;using uint=unsigned int;using ull=unsigned long long;
using pii=pair<int,int>;using pll=pair<ll,ll>;using pill=pair<int,ll>;using plli=pair<ll,int>;using pdd=pair<double,double>;using pld=pair<ld,ld>;
constexpr const char nl='\n',sp=' ';constexpr const int INT_INF=0x3f3f3f3f;constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f;
constexpr const double D_INF=numeric_limits<double>::infinity();constexpr const ld LD_INF=numeric_limits<ld>::infinity();constexpr const double EPS=1e-9;

const int MAXN = 5005;

ll cost[MAXN][MAXN], dp[MAXN][MAXN];
int mid[MAXN][MAXN];

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    FOR(j, sz(H)) cost[0][j] = 0;
    FOR(i, sz(H)) {
        for (int j = i, mx = H[i]; j < sz(H); j++) cost[i + 1][j] = mx = max(mx, H[j]);
        for (int j = i, mx = H[i]; j >= 0; j--) cost[i + 1][j] = mx = max(mx, H[j]);
    }
    FOR(i, sz(H)) FOR(j, sz(H)) cost[i + 1][j] += cost[i][j];
    FOR(i, sz(H)) { dp[i][i] = H[i]; mid[i][i] = i; };
    REV(l, sz(H) - 2) For(r, l + 1, sz(H)) {
        int mnInd = -1; ll mn = 0x3f3f3f3f3f3f3f3f;
        for (int m = max(l, mid[l][r - 1]), mr = min(r, mid[l + 1][r]); m <= mr; m++) {
            ll temp = cost[r + 1][m] - cost[l][m];
            if (mn > temp) { mn = temp, mnInd = m; }
        }
        dp[l][r] = mn; mid[l][r] = mnInd;
    }
    vector<ll> ret(sz(L));
    FOR(i, sz(L)) ret[i] = dp[L[i]][R[i]];
    return ret;
}

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