Submission #132177

#	Time	Username	Problem	Language	Result	Execution time	Memory
132177		amiratou	Meetings (IOI18_meetings)	C++14	19 / 100	873 ms	626044 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF LLONG_MAX
ll pre[5001][5001],suf[5001][5001];
ll cum[5001][5001],cum2[5001][5001];
int st[400002];
vector<int> A,tab;
void build(int node,int l,int r){
	if(l==r){
		st[node]=tab[l];
		return ;
	}
	int med=(l+r)/2;
	build(node*2,l,med),build(node*2+1,med+1,r);
	st[node]=max(st[node*2],st[node*2+1]);
}
int query(int node,int l,int r,int i,int j){
	if(l>j||r<i)
		return 0;
	if(l>=i&&r<=j)
		return st[node];
	int med=(l+r)/2;
	return max(query(node*2,l,med,i,j),query(node*2+1,med+1,r,i,j));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
	int n=H.size();
	if(n<=5000){
		for (int i = 0; i < n; ++i)
			for (int j = i; j < n;++j)
			{
				pre[i][j]=H[j];
				if(j)pre[i][j]=max(pre[i][j],pre[i][j-1]);
			}
		for (int i = n-1; i >= 0; i--)
			for (int j = i; j >= 0;j--)
			{
				suf[i][j]=H[j];
				if(j!=(n-1))suf[i][j]=max(suf[i][j],suf[i][j+1]);
			}
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
			{
				cum2[i][j]+=suf[i][j];
				if(i)cum2[i][j]+=cum2[i-1][j];
				cum[i][j]+=pre[i][j];
				if(i)cum[i][j]+=cum[i-1][j];
			}
		int Q = L.size();
		vector<ll> C(Q);
		for (int q = 0; q < Q; ++q) {
			ll ans=INF;
			for (int i = L[q]; i <=R[q] ; ++i)
				ans=min(ans,cum2[R[q]][i]+cum[n-1][i]-(L[q]?cum[L[q]-1][i]:0)-H[i]);
			C[q]=ans;
		}
		return C;
	}
	A=H;
	tab.resize(n);
	for (int i = 0; i < n; ++i)
	{
		tab[i]=0;
		if(tab[i]==1){
			if(i)tab[i]+=tab[i-1];
			tab[i]++;
		}
	}
	build(1,0,n-1);
	int Q = L.size();
	vector<ll> C(Q);
	for (int q = 0; q < Q; ++q) {
		ll nb=query(1,0,n-1,L[q],R[q]);
		C[q]=nb+2*(R[q]-L[q]+1-nb);
	}
	return C;
}

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