Submission #1275301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275301		nicolo_010	Meetings (IOI18_meetings)	C++20	19 / 100	3271 ms	851968 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct Node {
	int val, l, r;
};

Node vd;

struct SegTree {
	vector<Node> tree;
	SegTree(int n) {
		tree.assign(4*n, vd);
	}
};

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	vd.val = 0;
	vd.l = 0;
	vd.r = 0;
	int N = H.size();
	int Q = L.size();
	vector<vector<ll>> pref(N, vector<ll>(N, 0));
	for (int i=0; i<N; i++) {
		pref[i][i] = H[i];
		int mx=H[i];
		for (int j=i-1; j>=0; j--) {
			mx = max(mx, H[j]);
			pref[i][j] = mx;
		}
		mx = H[i];
		for (int j=i+1; j<N; j++) {
			mx = max(mx, H[j]);
			pref[i][j] = mx;
		}
		for (int j=1; j<N; j++) {
			pref[i][j] += pref[i][j-1];
		}
	}
	vector<ll> ans(Q);
	for (int i=0; i<Q; i++) {
		ll mn = 1e18; 
		for (int j=L[i]; j<=R[i]; j++) {
			ll left = (L[i]==0 ? 0 : pref[j][L[i]-1]);
			mn = min(pref[j][R[i]] - left, mn);
		}
		ans[i] = mn;
	}
	return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40