oj.uz

Submission #74977

# Submission time Handle Problem Language Result Execution time Memory
74977 2018-09-07T19:28:23 Z rekt_n00b Meetings (IOI18_meetings) C++14
19 / 100
 685 ms 398824 KB 
#include "meetings.h"
using namespace std;

const int N = 5000;

long long costs[N][N];

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
    int n = H.size(), q = (int) L.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            costs[i][j] = 0;
        }
    }
    for (int i = 0; i < n; i++) {
        costs[i][i] = H[i];
        {
            int mx = H[i];
            for (int j = i - 1; j >= 0; j--) {
                mx = max(mx, H[j]);
                costs[i][j] = costs[i][j + 1] + mx;
            }
        }
        {
            int mx = H[i];
            for (int j = i + 1; j < n; j++) {
                mx = max(mx, H[j]);
                costs[i][j] = costs[i][j - 1] + mx;
            }
        }
    }
    vector<long long> ans(q);
    for (int i = 0; i < q; i++) {
        ans[i] = 1e18;
        for (int k = L[i]; k <= R[i]; k++) {
            ans[i] = min(ans[i], costs[k][L[i]] + costs[k][R[i]] - H[k]);
        }
    }
    return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 89 ms 82908 KB Output is correct
3 Correct 89 ms 82856 KB Output is correct
4 Correct 88 ms 82920 KB Output is correct
5 Correct 89 ms 82908 KB Output is correct
6 Correct 88 ms 82916 KB Output is correct
7 Correct 88 ms 82936 KB Output is correct
8 Correct 90 ms 82828 KB Output is correct
9 Correct 90 ms 82936 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct
2 Correct 89 ms 82908 KB Output is correct
3 Correct 89 ms 82856 KB Output is correct
4 Correct 88 ms 82920 KB Output is correct
5 Correct 89 ms 82908 KB Output is correct
6 Correct 88 ms 82916 KB Output is correct
7 Correct 88 ms 82936 KB Output is correct
8 Correct 90 ms 82828 KB Output is correct
9 Correct 90 ms 82936 KB Output is correct
10 Correct 505 ms 196340 KB Output is correct
11 Correct 675 ms 196292 KB Output is correct
12 Correct 492 ms 196356 KB Output is correct
13 Correct 685 ms 196344 KB Output is correct
14 Correct 507 ms 196320 KB Output is correct
15 Correct 511 ms 196308 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 459 ms 398824 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 459 ms 398824 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 400 KB Output is correct
2 Correct 89 ms 82908 KB Output is correct
3 Correct 89 ms 82856 KB Output is correct
4 Correct 88 ms 82920 KB Output is correct
5 Correct 89 ms 82908 KB Output is correct
6 Correct 88 ms 82916 KB Output is correct
7 Correct 88 ms 82936 KB Output is correct
8 Correct 90 ms 82828 KB Output is correct
9 Correct 90 ms 82936 KB Output is correct
10 Correct 505 ms 196340 KB Output is correct
11 Correct 675 ms 196292 KB Output is correct
12 Correct 492 ms 196356 KB Output is correct
13 Correct 685 ms 196344 KB Output is correct
14 Correct 507 ms 196320 KB Output is correct
15 Correct 511 ms 196308 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Runtime error 459 ms 398824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -