Submission #835121

#	Time	Username	Problem	Language	Result	Execution time	Memory
835121		tolbi	Meetings (IOI18_meetings)	C++17	0 / 100	5526 ms	7628 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define tol(bi) (1LL<<((int)(bi)))
#include "meetings.h"
vector<long long> minimum_costs(vector<int> arr, vector<int> L, vector<int> R) {
	int q = L.size();
	int n = arr.size();
	vector<ll> ansarr(q,0);
	for (int qu = 0; qu < q; ++qu) {
		int l = L[qu];
		int r = R[qu];
		vector<ll> leftdp(r-l+1);
		vector<ll> rightdp(r-l+1);
		vector<ll> stak;
		for (int i = l; i <= r; i++){
			while (stak.size() && arr[stak.back()]<=arr[i]){
				stak.pop_back();
			};
			if (stak.size()==0){
				leftdp[i-l]=(i-l+1)*arr[i];
			}
			else {
				leftdp[i-l]=leftdp[stak.back()-l]+arr[i]*(i-stak.back());
			}
			stak.push_back(i);
		}
		stak.clear();
		for (int i = r; i >= l; i--){
			while (stak.size() && arr[stak.back()]<=arr[i]){
				stak.pop_back();
			}
			if (stak.size()==0){
				rightdp[i-l]=(r-i+1)*arr[i];
			}
			else {
				rightdp[i-l]=rightdp[stak.back()-l]+arr[i]*(stak.back()-i);
			}
			stak.push_back(i);
		}
		ll ans = 2323232323232323;
		for (int i = l; i <= r; i++){
			ans=min(ans,leftdp[i-l]+rightdp[i-l]-arr[i]);
		}
		ansarr[qu]=ans;
	}
	return ansarr;
}

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:8:6: warning: unused variable 'n' [-Wunused-variable]
    8 |  int n = arr.size();
      |      ^

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