Submission #300753

#	Time	Username	Problem	Language	Result	Execution time	Memory
300753		TMJN	Meetings (IOI18_meetings)	C++17	19 / 100	5114 ms	2432 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

int N,Q;
long long A[5001],B[5001];
vector<long long> minimum_costs(vector<int>H,vector<int>L,vector<int>R){
	N=H.size();
	Q=L.size();
	assert(N<=5000&&Q<=5000);
	vector<long long>res(Q);
	for(int i=0;i<Q;i++){
		map<int,int>mp;
		long long t=0;
		for(int j=0;j<N;j++){
			A[j]=B[j]=0;
		}
		for(int j=L[i];j<=R[i];j++){
			t+=H[j];
			mp[H[j]]++;
			while(mp.begin()->first<H[j]){
				t+=(H[j]-mp.begin()->first)*(long long)mp.begin()->second;
				mp[H[j]]+=mp.begin()->second;
				mp.erase(mp.begin());
			}
			A[j]=t;
		}
		t=0;
		mp.clear();
		for(int j=R[i];j>=L[i];j--){
			t+=H[j];
			mp[H[j]]++;
			while(mp.begin()->first<H[j]){
				t+=(H[j]-mp.begin()->first)*(long long)mp.begin()->second;
				mp[H[j]]+=mp.begin()->second;
				mp.erase(mp.begin());
			}
			B[j]=t;
		}
		long long a=0xE869120E869120;
		for(int j=L[i]-1;j<=R[i];j++){
			if(j==-1){
				a=min(a,B[j+1]);
			}
			else if(j==N-1){
				a=min(a,A[j]);
			}
			else{
				a=min(a,A[j]+B[j+1]);
			}
		}
		res[i]=a;
	}
	return res;
}

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