Submission #572592

#	Time	Username	Problem	Language	Result	Execution time	Memory
572592		Jesus	Holiday (IOI14_holiday)	C++14	23 / 100	5053 ms	8140 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>

using namespace std;

priority_queue<long long int> caso2;

pair<long long int,int> tabla_izq[250001],tabla_der[250001];

long long int tabla[3000][3000];

int valores[100000];

int ini=0;
int lim=0;
int lim_c;

void t_i(int dia,int i,long long int acum=0){
    if(dia>lim||i<0) return;
    long long int aux=acum+valores[i];
    if(tabla_izq[dia].first<aux){
        tabla_izq[dia].first=aux;
        tabla_izq[dia].second=dia+ini-i;
    }
    t_i(dia+1,i-1,acum);
    t_i(dia+2,i-1,acum+valores[i]);
}

void t_d(int dia,int i,long long int acum=0){
    if(dia>lim||i>=lim_c) return;
    long long int aux=acum+valores[i];
    if(tabla_der[dia].first<aux){
        tabla_der[dia].first=aux;
        tabla_der[dia].second=dia+i-ini;
    }
    t_d(dia+1,i+1,acum);
    t_d(dia+2,i+1,acum+valores[i]);
}




long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    lim=d;
    lim_c=n;
    ini=start;
    long long int res=0;
   if(start==0){
        long long int aux=0;
        for(int i=0;i<n;i++){
            if(d==0){
                aux-=(caso2.top()*-1);
                caso2.pop();
                d++;
            }
            aux+=attraction[i];
            res=max(res,aux);
            caso2.push(attraction[i]*-1);
            d--;
            if(d==0){
                aux-=(caso2.top()*-1);
                caso2.pop();
            }
            else d--;
        }
    }

    else{
        for(int i=0;i<n;i++){
            valores[i]=attraction[i];
        }
        t_i(2,start-1);
        t_d(1,start);
        for(int i=0;i<=d;i++){
            res=max(res,tabla_der[i].first+tabla_izq[d-tabla_der[i].second].first);
        }
        for(int i=0;i<=d;i++){
            res=max(res,tabla_izq[i].first+tabla_der[d-tabla_izq[i].second].first);
        }
    }
    return res;
}

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