제출 #1012156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012156		NintsiChkhaidze	휴가 (IOI14_holiday)	C++17	7 / 100	5090 ms	4696 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
const int N = 2e5 + 3;
ll ans = 0,arr[N];
int id,D;

void go(int l1,int r1,int l2,int r2){
	if (l1 > id) return;
	if (l1 > r1) return;
	
	int mid = (l1 + r1)/2,opt = 0;
	ll mx = -1;
	
//	cout<<"! "<<l1<<" "<<r1<<" -> "<<l2<<" "<<r2<<endl;
		
	for (int i = l2; i <= r2; i++){
		ll cur = 0;
		int l = mid,r = i;
		l = min(l,id);
		r = max(r,id);
		
		int len = r - l + min(r - id,id - l);
		int cnt = D - len;
		
//		cout<<"i = "<<i<<" -> "<<cnt<<endl;
		multiset <int> st;
		for (int j = l; j <= r; j++)
			st.insert(arr[j]);
		while (cnt > 0 && st.size() > 0){
			--cnt;
			cur += *(--st.end());
			st.erase(--st.end());
		}
//		cout<<"cur = "<<cur<<endl;
		if (cur > mx){
			mx = cur;
			opt = i;
		}
	}
	

//	cout<<"optimal "<<mid<<" "<<opt<<" "<<mx<<endl;
	ans=max(ans,mx);
	if (l1 == r1) return;
	go(l1,mid,l2,opt);
	go(mid+1,r1,opt + 1,r2);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    
    D = d;
    for (int i=0;i<n;i++)
    	arr[i]=attraction[i];
    id = start;
    go(0,n - 1,0,n - 1);
    return ans;
}

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