제출 #1015214

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015214		amirhoseinfar1385	휴가 (IOI14_holiday)	C++17	24 / 100	5074 ms	4348 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
long long all[maxn],n,st,k;
long long mainres=0;

void solve(long long l,long long r,long long tl,long long tr){
    if(l>r){
        return ;
    }
    long long mid=(l+r)>>1,opt=tl,mx=-1;
    for(long long i=tl;i<=tr;i++){
        priority_queue<long long>pq;
        for(long long j=i;j<=mid;j++){
            pq.push(all[j]);
        }
        long long ted=k-(mid-i+min(mid-st,st-i));
        if(ted>=0){
            long long fake=0;
            for(long long j=0;(long long)pq.size()>0&&j<ted;j++){
                fake+=(pq.top());
                pq.pop();
            }
//        cout<<i<<" "<<mid<<" "<<ted<<" "<<fake<<endl;
            if(fake>mx){
                opt=i;
                mx=fake;
            }
        }
    }
  //  cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<opt<<" "<<mx<<" "<<mid<<endl;
    mainres=max(mainres,mx);
    solve(l,mid-1,tl,opt);
    solve(mid+1,r,opt,tr);
}

long long findMaxAttraction(int N, int start, int d, int attraction[]) {
    n=N;
    st=start;
    k=d;
    st++;
    for(long long i=1;i<=n;i++){
        all[i]=attraction[i-1];
    }
    solve(st,n,1,st);
    return mainres;
}

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