Submission #1143444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143444		simplemind_31	Holiday (IOI14_holiday)	C++20	30 / 100	57 ms	131072 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> llset;
vector<ll> ATRA;
vector<vector<ll>> dp;
ll N;
ll solveiz(ll dia, ll posicion){
    if(dia<=0 || posicion<0 || posicion>=N){
        return 0;
    }
    if(dp[dia][posicion]!=0){
        return dp[dia][posicion];
    }
    ll op1=ATRA[posicion]+solveiz(dia-2,posicion-1);
    ll op2=solveiz(dia-1,posicion-1);
    return dp[dia][posicion]=max(op1,op2);
}
ll solvede(ll dia, ll posicion){
    if(dia<=0 || posicion<0 || posicion>=N){
        return 0;
    }
    if(dp[dia][posicion]!=0){
        return dp[dia][posicion];
    }
    ll op1=ATRA[posicion]+solvede(dia-2,posicion+1);
    ll op2=solvede(dia-1,posicion+1);
    return dp[dia][posicion]=max(op1,op2);
}
ll findMaxAttraction(int n,int start,int d,int attraction[]) {
    if(start==0){
        llset res;
        ll sum=0;
        ll maxi=0;
        for(ll i=0;i<(ll)((d+1)/2) && i<n;i++){
            res.insert(attraction[i]);
            sum+=attraction[i];
        }
        maxi=sum;
        for(ll i=(d+1)/2;i<n;i++){
            sum+=attraction[i];
            res.insert(attraction[i]);
            while(res.size()>0 && res.size()>d-i){
                sum-=*res.begin();
                res.erase(res.begin());
            }
            maxi=max(maxi,sum);
        }
        return maxi;
    }else{
        N=n;
        ll maxi=0;
        ATRA.resize(n);
        for(ll i=0;i<n;i++){
            ATRA[i]=attraction[i];
        }
        for(ll i=0;i<n;i++){
            dp.clear();
            dp.assign(d+5,vector<ll>(n+5,0));
            maxi=max(maxi,solveiz(d-abs(start-i),i));
            dp.clear();
            dp.assign(d+5,vector<ll>(n+5,0));
            maxi=max(maxi,solvede(d-abs(start-i),i));
        }
        return maxi;
    }
}

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