oj.uz

Submission #81928

# Submission time Handle Problem Language Result Execution time Memory
81928 2018-10-27T20:26:32 Z wleung_bvg Meetings (IOI18_meetings) C++14
19 / 100
 562 ms 398992 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 210 ms 159896 KB Output is correct
3 Correct 206 ms 159936 KB Output is correct
4 Correct 211 ms 159908 KB Output is correct
5 Correct 213 ms 159948 KB Output is correct
6 Correct 207 ms 159980 KB Output is correct
7 Correct 204 ms 159944 KB Output is correct
8 Correct 225 ms 159900 KB Output is correct
9 Correct 221 ms 159884 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 210 ms 159896 KB Output is correct
3 Correct 206 ms 159936 KB Output is correct
4 Correct 211 ms 159908 KB Output is correct
5 Correct 213 ms 159948 KB Output is correct
6 Correct 207 ms 159980 KB Output is correct
7 Correct 204 ms 159944 KB Output is correct
8 Correct 225 ms 159900 KB Output is correct
9 Correct 221 ms 159884 KB Output is correct
10 Correct 562 ms 380584 KB Output is correct
11 Correct 557 ms 380500 KB Output is correct
12 Correct 552 ms 380528 KB Output is correct
13 Correct 550 ms 380608 KB Output is correct
14 Correct 561 ms 380564 KB Output is correct
15 Correct 560 ms 380520 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 487 ms 398992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 487 ms 398992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 210 ms 159896 KB Output is correct
3 Correct 206 ms 159936 KB Output is correct
4 Correct 211 ms 159908 KB Output is correct
5 Correct 213 ms 159948 KB Output is correct
6 Correct 207 ms 159980 KB Output is correct
7 Correct 204 ms 159944 KB Output is correct
8 Correct 225 ms 159900 KB Output is correct
9 Correct 221 ms 159884 KB Output is correct
10 Correct 562 ms 380584 KB Output is correct
11 Correct 557 ms 380500 KB Output is correct
12 Correct 552 ms 380528 KB Output is correct
13 Correct 550 ms 380608 KB Output is correct
14 Correct 561 ms 380564 KB Output is correct
15 Correct 560 ms 380520 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Runtime error 487 ms 398992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -