oj.uz

Submission #944954

# Submission time Handle Problem Language Result Execution time Memory
944954 2024-03-13T08:48:46 Z siewjh Meetings (IOI18_meetings) C++17
19 / 100
 687 ms 596984 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
const ll inf = 1e18;
ll lc[MAXN][MAXN], rc[MAXN][MAXN], ls[MAXN][MAXN], rs[MAXN][MAXN];

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	int nums = H.size();
	vector<pair<int, ll>> vec;
	vec.push_back({-1, inf});
	for (int i = 0; i < nums; i++){
		while (vec.back().second <= H[i]) vec.pop_back();
		vec.push_back({i, H[i]});
		int curr = 1;
		for (int j = 0; j < i; j++){
			while (vec[curr].first < j) curr++;
			lc[i][j] = max(lc[i - 1][j], vec[curr].second);
		}
		lc[i][i] = ls[i][i] = H[i];
		for (int j = i - 1; j >= 0; j--) ls[i][j] = ls[i][j + 1] + lc[i][j];
	}
	vec.clear();
	vec.push_back({nums, inf});
	for (int i = nums - 1; i >= 0; i--){
		while (vec.back().second <= H[i]) vec.pop_back();
		vec.push_back({i, H[i]});
		int curr = 1;
		for (int j = nums - 1; j > i; j--){
			while (vec[curr].first > j) curr++;
			rc[i][j] = max(rc[i + 1][j], vec[curr].second);
		}
		rc[i][i] = rs[i][i] = H[i];
		for (int j = i + 1; j < nums; j++) rs[i][j] = rs[i][j - 1] + rc[i][j];
	}
	int queries = L.size();
	vector<ll> ans(queries);
	for (int q = 0; q < queries; q++){
		int l = L[q], r = R[q];
		ll res = inf;
		for (int m = l; m <= r; m++) res = min(res, ls[m][l] + rs[m][r] - H[m]);
		ans[q] = res;
	}
	return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 125 ms 317404 KB Output is correct
3 Correct 95 ms 318184 KB Output is correct
4 Correct 90 ms 317520 KB Output is correct
5 Correct 105 ms 318288 KB Output is correct
6 Correct 91 ms 318164 KB Output is correct
7 Correct 92 ms 318284 KB Output is correct
8 Correct 90 ms 318292 KB Output is correct
9 Correct 92 ms 318520 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 125 ms 317404 KB Output is correct
3 Correct 95 ms 318184 KB Output is correct
4 Correct 90 ms 317520 KB Output is correct
5 Correct 105 ms 318288 KB Output is correct
6 Correct 91 ms 318164 KB Output is correct
7 Correct 92 ms 318284 KB Output is correct
8 Correct 90 ms 318292 KB Output is correct
9 Correct 92 ms 318520 KB Output is correct
10 Correct 420 ms 596048 KB Output is correct
11 Correct 687 ms 596160 KB Output is correct
12 Correct 385 ms 596972 KB Output is correct
13 Correct 659 ms 596884 KB Output is correct
14 Correct 409 ms 596984 KB Output is correct
15 Correct 399 ms 596976 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Runtime error 283 ms 551072 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Runtime error 283 ms 551072 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 125 ms 317404 KB Output is correct
3 Correct 95 ms 318184 KB Output is correct
4 Correct 90 ms 317520 KB Output is correct
5 Correct 105 ms 318288 KB Output is correct
6 Correct 91 ms 318164 KB Output is correct
7 Correct 92 ms 318284 KB Output is correct
8 Correct 90 ms 318292 KB Output is correct
9 Correct 92 ms 318520 KB Output is correct
10 Correct 420 ms 596048 KB Output is correct
11 Correct 687 ms 596160 KB Output is correct
12 Correct 385 ms 596972 KB Output is correct
13 Correct 659 ms 596884 KB Output is correct
14 Correct 409 ms 596984 KB Output is correct
15 Correct 399 ms 596976 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Runtime error 283 ms 551072 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -