oj.uz

Submission #81927

# Submission time Handle Problem Language Result Execution time Memory
81927 2018-10-27T20:23:00 Z wleung_bvg Meetings (IOI18_meetings) C++14
0 / 100
 491 ms 398884 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
using ll=long long;constexpr const char nl='\n',sp=' ';

const int MAXN = 5005;

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

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    for (int j = 0; j < sz(H); j++) cost[0][j] = 0;
    for (int i = 0; i < sz(H); i++) {
        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 (int i = 0; i < sz(H); i++) for (int j = 0; j < sz(H); j++) cost[i + 1][j] += cost[i][j];
    for (int l = 0; l < sz(H); l++) {
        ll mx = H[l]; int mxInd = l;
        for (int r = l; r < sz(H); r++) {
            if (mx < H[r]) { mx = H[r]; mxInd = r; }
            ind[l][r] = mxInd;
            dp[l][r] = 0x3f3f3f3f3f3f3f3f;
        }
    }
    for (int l = 0; l < sz(H); l++) for (int m = l, r = l; r < sz(H); r++) while (true) {
        dp[l][r] = min(dp[l][r], cost[r + 1][m] - cost[l][m]);
        if (m + 1 < ind[l][r]) m++;
        else break;
    }
    for (int r = sz(H) - 1; r >= 0; r--) {
        ll mx = H[r]; int mxInd = r;
        for (int l = r; l >= 0; l--) {
            if (mx < H[l]) { mx = H[l]; mxInd = l; }
            ind[r][l] = mxInd;
        }
    }
    for (int r = sz(H) - 1; r >= 0; r--) for (int m = r, l = r; l >= 0; l--) while (true) {
        dp[l][r] = min(dp[l][r], cost[r + 1][m] - cost[l][m]);
        if (m - 1 > ind[l][r]) m--;
        else break;
    }
    vector<ll> ret(sz(L));
    for (int i = 0; i < sz(L); i++) ret[i] = dp[L[i]][R[i]];
    return ret;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Incorrect 440 ms 177528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Incorrect 440 ms 177528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Runtime error 491 ms 398884 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 348 KB Output is correct
2 Runtime error 491 ms 398884 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 348 KB Output is correct
2 Incorrect 440 ms 177528 KB Output isn't correct
3 Halted 0 ms 0 KB -