oj.uz

Submission #97338

# Submission time Handle Problem Language Result Execution time Memory
97338 2019-02-15T10:07:24 Z E869120 Meetings (IOI18_meetings) C++14
19 / 100
 1143 ms 117800 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

long long N, Q, H[5009], T[5009]; pair<int, int> dp[5009][5009];

void dfs(int cl, int cr) {
	if (cl > cr) return;
	int cm = dp[cl][cr].second; long long cost = dp[cl][cr].first;
	//cout << "cl = " << cl << ", cr = " << cr << ", cm = " << cm << ", cost = " << cost << endl;
	T[cl] += cost * (cr - cm + 1);
	T[cm] += cost * (cm - cl);
	T[cm + 1] -= cost * (cr - cm);
	T[cr + 1] -= cost * (cm - cl + 1);
	dfs(cl, cm - 1);
	dfs(cm + 1, cr);
}

vector<long long> minimum_costs(vector<int> HH, vector<int> L, vector<int> R) {
	N = HH.size(); Q = L.size();
	for (int i = 0; i < N; i++) H[i] = HH[i];
	
	for (int i = 0; i < N; i++) {
		pair<int, int> BASE = make_pair(-1, -1);
		for (int j = i; j < N; j++) {
			BASE = max(BASE, make_pair((int)H[j], j));
			dp[i][j] = BASE;
		}
	}
	
	vector<long long> ans;
	for (int i = 0; i < Q; i++) {
		for (int j = 0; j <= N; j++) T[j] = 0;
		dfs(L[i], R[i]);
		for (int j = 1; j <= N; j++) T[j] += T[j - 1];
		
		long long rem = (1LL << 60);
		for (int j = L[i]; j <= R[i]; j++) rem = min(rem, T[j]);
		ans.push_back(rem);
	}
	return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 53 ms 47736 KB Output is correct
3 Correct 52 ms 47772 KB Output is correct
4 Correct 52 ms 47748 KB Output is correct
5 Correct 53 ms 47688 KB Output is correct
6 Correct 47 ms 47740 KB Output is correct
7 Correct 51 ms 47708 KB Output is correct
8 Correct 49 ms 47760 KB Output is correct
9 Correct 51 ms 47848 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 53 ms 47736 KB Output is correct
3 Correct 52 ms 47772 KB Output is correct
4 Correct 52 ms 47748 KB Output is correct
5 Correct 53 ms 47688 KB Output is correct
6 Correct 47 ms 47740 KB Output is correct
7 Correct 51 ms 47708 KB Output is correct
8 Correct 49 ms 47760 KB Output is correct
9 Correct 51 ms 47848 KB Output is correct
10 Correct 452 ms 117672 KB Output is correct
11 Correct 1143 ms 117740 KB Output is correct
12 Correct 452 ms 117692 KB Output is correct
13 Correct 1143 ms 117640 KB Output is correct
14 Correct 430 ms 117800 KB Output is correct
15 Correct 457 ms 117636 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Runtime error 30 ms 2184 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 380 KB Output is correct
2 Runtime error 30 ms 2184 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 53 ms 47736 KB Output is correct
3 Correct 52 ms 47772 KB Output is correct
4 Correct 52 ms 47748 KB Output is correct
5 Correct 53 ms 47688 KB Output is correct
6 Correct 47 ms 47740 KB Output is correct
7 Correct 51 ms 47708 KB Output is correct
8 Correct 49 ms 47760 KB Output is correct
9 Correct 51 ms 47848 KB Output is correct
10 Correct 452 ms 117672 KB Output is correct
11 Correct 1143 ms 117740 KB Output is correct
12 Correct 452 ms 117692 KB Output is correct
13 Correct 1143 ms 117640 KB Output is correct
14 Correct 430 ms 117800 KB Output is correct
15 Correct 457 ms 117636 KB Output is correct
16 Correct 2 ms 380 KB Output is correct
17 Runtime error 30 ms 2184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -