제출 #1234304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234304		lalig777	Nile (IOI24_nile)	C++20	0 / 100	26 ms	9032 KiB

nile

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
//#define int long long
using namespace std;
typedef long long ll;

struct dades{
	ll ini;
	ll fin;
	ll mini;
	ll par;
};

vector<pair<ll, ll> >artifact;
vector<dades>blocs;

vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
	int N=W.size();
	int Q=E.size();
	artifact.resize(N);
	blocs.resize(N);
	ll sum=0;
	for (int i=0; i<N; i++) sum+=A[i];
	for (int i=0; i<N; i++) artifact[i]=make_pair(W[i], A[i]-B[i]);
	sort(artifact.begin(), artifact.end());
	for (int i=0; i<N; i++){
		blocs[i].ini=i;
		blocs[i].fin=i;
		blocs[i].mini=artifact[i].second;
		blocs[i].par=1;
	}

	vector<pair<ll,ll> >consec(N-1);
	for (int i=0; i<N-1; i++) consec[i]=make_pair(artifact[i+1].first-artifact[i].first, i);
	sort(consec.begin(), consec.end());
	
	vector<pair<ll,ll> >queries(Q);
	vector<ll>resposta(Q);
	for (int i=0; i<Q; i++) queries[i]=make_pair(E[i], i);
	sort(queries.begin(), queries.end());
	
	int j=0; ll ans=0;
	for (int k=0; k<Q; k++){
		ll D=queries[k].first;
		while (j<N-1){

			if (consec[j].first>D) break;
			ll ind=consec[j].second;
			ll inici=blocs[ind].ini, final=blocs[ind+1].fin;
			ll minim=min(blocs[ind].mini, blocs[ind+1].mini), paritat=blocs[ind].par+blocs[ind+1].par;
			//cout<<ind<<' '<<inici<<' '<<final<<' '<<minim<<' '<<paritat<<endl;

			if (paritat==1 and blocs[ind].par==0) ans=ans-blocs[ind].mini+max(blocs[ind].mini, blocs[ind+1].mini);
			else if (paritat==1 and blocs[ind].par==1) ans=ans-blocs[ind+1].mini+max(blocs[ind].mini, blocs[ind+1].mini);
			else if (paritat==2) ans=ans+blocs[ind].mini+blocs[ind+1].mini;
			//cout<<ans<<endl;
			blocs[inici].ini=inici; blocs[inici].fin=final; blocs[inici].mini=minim; blocs[inici].par=paritat%2;
			blocs[final].ini=inici; blocs[final].fin=final; blocs[final].mini=minim; blocs[final].par=paritat%2;
			j++;
		}
		resposta[queries[k].second]=sum-ans;
	}
	for (int i=0; i<Q; i++) cout<<E[i]<<' ';
	return resposta;
	
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18