Submission #286335

#	Time	Username	Problem	Language	Result	Execution time	Memory
286335		mohammad	Meetings (IOI18_meetings)	C++14	19 / 100	5509 ms	7032 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
 
#define endl "\n"
// #define int long long

typedef long long ll ;
const ll ooo = 1e18 ;
const ll oo = 2e9 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 7  ;
const int N = 10000010  ;

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int Q = L.size();
	vector<ll> C(Q);
	for (int j = 0; j < Q; ++j) {
		ll ans = ooo;
		int l = L[j] , r = R[j];
		stack<pair<ll,ll>> q;
		ll cost = 0;
		vector<ll> cl(H.size()) , cr(H.size());
		for(int i = l ; i <= r ;++i){
			ll w = 1 ;
			while(q.size() && q.top().first <= H[i]){
				cost += (ll)(H[i] - q.top().first) * q.top().second;
				w += q.top().second;
				q.pop();
			}
			q.push({H[i] , w});
			cl[i] = cost;
			cost += H[i];
		}
		q = stack<pair<ll,ll>>();
		cost = 0;
		for(int i = r ; i >= l ;--i){
			ll w = 1 ;
			while(q.size() && q.top().first <= H[i]){
				cost += (ll)(H[i] - q.top().first) * q.top().second;
				w += q.top().second;
				q.pop();
			}
			// cout << i << ' ' << cost 
			q.push({H[i] , w});
			cr[i] = cost;
			cost += H[i];
		}
		for(int i = l ; i <= r ; ++i) ans = min(ans , cl[i] + cr[i] + H[i]);
		C[j] = ans;
	}
	return C;
}

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