oj.uz

Submission #944167

# Submission time Handle Problem Language Result Execution time Memory
944167 2024-03-12T09:24:52 Z yhkhoo Meetings (IOI18_meetings) C++17
19 / 100
 3963 ms 786432 KB 
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

/*struct node{
	int s, e, m;
	int val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val = 0;
		if(s!=e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void update(int X, int V){
		if(s == X && e == X){
			val = V;
		}
		else{
			if(X <= m) l->update(X, V);
			else r->update(X, V);
			val = l->val + r->val;
		}
	}
	
	int query(int S, int E){*/
		
const ll INF=1e18;

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int N = H.size();
	vector<vector<int>> cost(N);
	for(int i=0; i<N; i++){
		cost[i].reserve(N);
		for(int j=0; j<i; j++){
			cost[i].push_back(cost[j][i]);
		}
		cost[i].push_back(H[i]);
		for(int j=i+1; j<N; j++){
			cost[i].push_back(max(cost[i][j-1], H[j]));
		}
	}
	vector<vector<ll>> pre(N);
	for(int i=0; i<N; i++){
		pre[i].push_back(cost[i][0]);
		for(int j=1; j<N; j++){
			pre[i].push_back(pre[i][j-1] + cost[i][j]);
		}
	}
	int Q = L.size();
	vector<ll> ans(Q, INF);
	for(int i=0; i<Q; i++){
		for(int j=L[i]; j<=R[i]; j++){
			ll cur = pre[j][R[i]];
			if(L[i] != 0){
				cur -= pre[j][L[i]-1];
			}
			ans[i] = min(ans[i], cur);
		}
	}
	return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 112 ms 118152 KB Output is correct
3 Correct 106 ms 118368 KB Output is correct
4 Correct 103 ms 118136 KB Output is correct
5 Correct 104 ms 118356 KB Output is correct
6 Correct 104 ms 118352 KB Output is correct
7 Correct 110 ms 118376 KB Output is correct
8 Correct 107 ms 118184 KB Output is correct
9 Correct 105 ms 118352 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 112 ms 118152 KB Output is correct
3 Correct 106 ms 118368 KB Output is correct
4 Correct 103 ms 118136 KB Output is correct
5 Correct 104 ms 118356 KB Output is correct
6 Correct 104 ms 118352 KB Output is correct
7 Correct 110 ms 118376 KB Output is correct
8 Correct 107 ms 118184 KB Output is correct
9 Correct 105 ms 118352 KB Output is correct
10 Correct 498 ms 314704 KB Output is correct
11 Correct 793 ms 314704 KB Output is correct
12 Correct 489 ms 314732 KB Output is correct
13 Correct 772 ms 314696 KB Output is correct
14 Correct 482 ms 314560 KB Output is correct
15 Correct 513 ms 314960 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3963 ms 767516 KB Output is correct
3 Runtime error 1185 ms 786432 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3963 ms 767516 KB Output is correct
3 Runtime error 1185 ms 786432 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 112 ms 118152 KB Output is correct
3 Correct 106 ms 118368 KB Output is correct
4 Correct 103 ms 118136 KB Output is correct
5 Correct 104 ms 118356 KB Output is correct
6 Correct 104 ms 118352 KB Output is correct
7 Correct 110 ms 118376 KB Output is correct
8 Correct 107 ms 118184 KB Output is correct
9 Correct 105 ms 118352 KB Output is correct
10 Correct 498 ms 314704 KB Output is correct
11 Correct 793 ms 314704 KB Output is correct
12 Correct 489 ms 314732 KB Output is correct
13 Correct 772 ms 314696 KB Output is correct
14 Correct 482 ms 314560 KB Output is correct
15 Correct 513 ms 314960 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 3963 ms 767516 KB Output is correct
18 Runtime error 1185 ms 786432 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -