oj.uz

Submission #784777

# Submission time Handle Problem Language Result Execution time Memory
784777 2023-07-16T14:01:54 Z aZvezda Meetings (IOI18_meetings) C++14
4 / 100
 5500 ms 2172 KB 
#include "meetings.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef local
#define cerr if(false)cerr
#endif

const int MAX_N = 1e6 + 10;
int n, q, arr[MAX_N];

ll solve(ll l, ll r) {
	if(r < l) { return 0; }
	if(l == r) { return arr[l]; }
	int mx = max_element(arr + l, arr + r + 1) - arr;
	ll ret = arr[mx] * (r - l + 1);
	ll lft = solve(l, mx - 1) + (r - mx + 1) * arr[mx];
	ll rght = solve(mx + 1, r) + (mx - l + 1) * arr[mx];
	return min({ret, lft, rght});
}

vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
	vector<ll> ret = {};
	int q = l.size();
	int n = h.size();
	for(int i = 0; i < n; i ++) {
		arr[i] = h[i];
	}
	for(int i = 0; i < q; i ++) {
		ret.push_back(solve(l[i], r[i]));
	}
	return ret;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 6 ms 448 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 22 ms 436 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 6 ms 448 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 22 ms 436 KB Output is correct
10 Correct 232 ms 672 KB Output is correct
11 Correct 824 ms 592 KB Output is correct
12 Correct 234 ms 692 KB Output is correct
13 Correct 773 ms 632 KB Output is correct
14 Execution timed out 5526 ms 844 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 5598 ms 2172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 5598 ms 2172 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 6 ms 448 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 22 ms 436 KB Output is correct
10 Correct 232 ms 672 KB Output is correct
11 Correct 824 ms 592 KB Output is correct
12 Correct 234 ms 692 KB Output is correct
13 Correct 773 ms 632 KB Output is correct
14 Execution timed out 5526 ms 844 KB Time limit exceeded
15 Halted 0 ms 0 KB -