Submission #529897

#	Time	Username	Problem	Language	Result	Execution time	Memory
529897		Deepesson	Holiday (IOI14_holiday)	C++17	24 / 100	5068 ms	3628 KiB

holiday

#include <bits/stdc++.h>
#include"holiday.h"
#define MAXS 2100000
#define MAX 110000
using ll = long long;
struct node {
    int left;
    int right;
    ll sum;
    int total;
};
node memoria[MAXS];
int cur=1;
int alocar(void){
    return cur++;
}
node nodes[MAX];
ll vals[MAX];
void inserir(node* x,ll val,int p,int la=0,int ra=MAX-1){
    if(la==ra){
        assert(p==la);
        x->total++;
        x->sum+=val;
        return;
    }
    int m = (la+ra)/2;
    if(m>=p){
        if(!x->left)x->left=alocar();
        inserir(&memoria[x->left],val,p,la,m);
    }else {
        if(!x->right)x->right=alocar();
        inserir(&memoria[x->right],val,p,m+1,ra);
    }
    ll tot = 0,ss=0;
    if(x->left)tot+=memoria[x->left].sum;
    if(x->right)tot+=memoria[x->right].sum;
    if(x->left)ss+=memoria[x->left].total;
    if(x->right)ss+=memoria[x->right].total;
    x->sum=tot;
    x->total=ss;
}
long long ans=0,limites;
/*void walk(node* k,int pode,int la=0,int ra=MAX-1){
    if(k->total<=pode){
        ans+=k->sum;
        limites=std::min(limites,la);
        return;
    }
    int m=(la+ra)/2;
    int tem = 0;
    if(k->right){
        tem=memoria[k->right].total;
    }
    int sobra = pode-tem;
    if(sobra>=0&&k->left){
        walk(&memoria[k->left],sobra,la,m);
        if(k->right)
        ans+=memoria[k->right].sum;
    }else {
        assert(&memoria[k->right]);
        walk(&memoria[k->right,sobra,m+1,ra);
    }
}*/
long long consulta(int l,int r,int p){///Naive
    std::priority_queue<int> queue;
    for(int i=l;i!=r+1;++i){
        queue.push(vals[i]);
    }
    ll ans=0;
    while(queue.size()&&p){
        --p;
        ans+=queue.top();
        queue.pop();
    }
    return ans;
}
long long pode=0;
long long resp=0;
long long inicio=0;
void dp(int l,int r,int la,int ra){
    if(r<l)return;
    int m = (l+r)/2;
    ll ans = 0,split=inicio;
    for(int i=la;i<=ra;++i){
        ll dist1=(inicio-i),dist2=(m-inicio);
        ll custo = (std::min(dist1,dist2)*2)+std::max(dist1,dist2);
        ll tem = pode-custo;
        if(tem<=0)continue;
        ll bonus = consulta(i,m,tem);
     ///   std::cout<<i<<" "<<m<<" "<<tem<< " "<<bonus<< "\n";
        if(bonus>ans){
            ans=bonus;
            split=i;
        }
    }
    resp=std::max(resp,ans);
  ///  std::cout<<ans<<" "<<m<<"<-\n";
    dp(l,m-1,la,split);
    dp(m+1,r,split,ra);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    for(int i=0;i!=n;++i){
        vals[i]=attraction[i];
    }
    inicio=start;
    pode=d;
    dp(inicio,n-1,0,inicio);
    return resp;
}

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