제출 #1267394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267394		elotelo966	Holiday (IOI14_holiday)	C++20	24 / 100	5091 ms	1980 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 100005

typedef long long lo;

int st,dist;

int dizi[lim];

lo cev;

inline int cal(int x,int y){
	int sol=abs(x-st);
	int sag=abs(y-st);
	return sol+sag+min(sol,sag);
}

inline void dnq(int l,int r,int optl,int optr){
	if(l>r)return ;
	int mi=(l+r)/2;
	int opt=optl;
	lo best=-1;
	for(int i=optl;i<=min(optr,mi);i++){
		int git=cal(i,mi);
		if(git>dist)continue;
		int kalan=dist-git;
		vector<lo> tut;
		for(int o=i;o<=mi;o++)tut.pb((lo)dizi[o]);
		sort(tut.rbegin(),tut.rend());
		lo cur_cev=0;
		for(int o=0;o<min(kalan,(int)tut.size());o++)cur_cev+=tut[o];
		if(cur_cev>best){
			best=cur_cev;
			opt=i;
		}
		cev=max(cev,cur_cev);
	}
	dnq(l,mi-1,optl,opt),dnq(mi+1,r,opt,optr);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	st=start+1;
	
	dist=d;
	
	cev=0;
	
	FOR{
		dizi[i]=attraction[i-1];
	}
		
	dnq(st,n,1,st);
	
	//~ for(int i=1;i<=st;i++){
		//~ for(int j=st;j<=n;j++){
			//~ int git=cal(i,j);
			//~ if(git>d)continue;
			//~ int kalan=d-git;
			//~ vector<lo> tut;
			//~ for(int o=i;o<=j;o++)tut.pb((lo)dizi[o]);
			//~ sort(tut.rbegin(),tut.rend());
			//~ lo cur_cev=0;
			//~ for(int o=0ll;o<min(kalan,tut.size());o++)cur_cev+=tut[o];
			//~ cev=max(cev,cur_cev);
		//~ }
	//~ }
	
	return cev;
}

//~ int main(){
	//~ faster
	//~ int n,start,d;
	//~ cin>>n>>start>>d;
	//~ int arr[n];
	//~ FOR{
		//~ cin>>arr[i-1];
	//~ }
	//~ lo cev=findMaxAttraction(n,start,d,arr);
	//~ cout<<cev<<'\n';
	//~ return 0;
//~ }

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53