Submission #295284

#	Time	Username	Problem	Language	Result	Execution time	Memory
295284		Saboon	Meetings (IOI18_meetings)	C++17	19 / 100	1090 ms	3200 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
const int maxn = 5e3 + 10;
ll dp[maxn];

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int n = H.size(), Q = L.size();
	vector<ll> C(Q);
	for (int j = 0; j < Q; j++){
		C[j] = inf;
		stack<pair<int,int>> S;
		ll Sum = 0;
		for (int i = L[j]; i <= R[j]; i++){
			int cnt = 1;
			while (!S.empty() and S.top().first <= H[i]){
				Sum -= 1LL*S.top().first*S.top().second;
				cnt += S.top().second;
				S.pop();
			}
			Sum += 1LL*H[i]*cnt;
			dp[i] = Sum;
			S.push({H[i],cnt});
		}
		while (!S.empty())
			S.pop();
		Sum = 0;
		for (int i = R[j]; i >= L[j]; i--){
			int cnt = 1;
			while (!S.empty() and S.top().first <= H[i]){
				Sum -= 1LL*S.top().first*S.top().second;
				cnt += S.top().second;
				S.pop();
			}
			Sum += 1LL*H[i]*cnt;
			C[j] = min(C[j], Sum+dp[i]-H[i]);
			S.push({H[i],cnt});
		}
	}
	return C;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:10:6: warning: unused variable 'n' [-Wunused-variable]
   10 |  int n = H.size(), Q = L.size();
      |      ^

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