제출 #597180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
597180		Lucpp	모임들 (IOI18_meetings)	C++17	19 / 100	5532 ms	5544 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll solve(int n, vector<int> H){
	vector<ll> ans(n);
	ll v = 0;
	stack<pair<ll, int>> st;
	for(int i = 0; i < n; i++){
		int j = i;
		while(!st.empty() && st.top().first < H[i]){
			v -= st.top().first * st.top().second;
			j -= st.top().second;
			st.pop();
		}
		v += ll(H[i])*(i-j);
		ans[i] += v;
		v += H[i];
		if(!st.empty() && st.top().first == H[i]) st.top().second += i+1-j;
		else st.emplace(H[i], i+1-j);
	}
	v = 0;
	st = stack<pair<ll, int>>();
	for(int i = n-1; i >= 0; i--){
		ans[i] += v;
		int j = i;
		while(!st.empty() && st.top().first < H[i]){
			v -= st.top().first * st.top().second;
			j += st.top().second;
			st.pop();
		}
		v += ll(H[i])*(j+1-i);
		if(!st.empty() && st.top().first == H[i]) st.top().second += j+1-i;
		else st.emplace(H[i], j+1-i);
	}
	ll mi = INF;
	for(int i = 0; i < n; i++) mi = min(mi, ans[i]+H[i]);
	return mi;
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int Q = (int)L.size();
	vector<ll> C(Q);
	for(int j = 0; j < Q; ++j){
		vector<int> h;
		for(int k = L[j]; k <= R[j]; k++) h.push_back(H[k]);
		C[j] = solve((int)h.size(), h);
	}
	return C;
}

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