Submission #1142358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142358		Gabriel	Holiday (IOI14_holiday)	C++20	0 / 100	5097 ms	13980 KiB

holiday

#include "holiday.h"
#include "bits/stdc++.h"
using namespace std;
long long n, Inicio, Tiempo;
vector< vector< vector<long long> > > Memorizaci_n;
vector<long long> Atracciones;
long long Resolver(long long i, long long Restante, long long Giro){
    if(Restante < 0) return -2222222222222222;
    if(i < 0 or i >= n) return -2222222222222222;
    if(Restante == 0) return 0;
    if(Restante == 1) return Memorizaci_n[i][Restante][Giro] = Atracciones[i];
    if(Memorizaci_n[i][Restante][Giro] != -2) return Memorizaci_n[i][Restante][Giro];
    long long m = 0;
    if(i == Inicio and Restante == Tiempo and Giro == 0){
        if(i + 1 < n) m = max(m, Resolver(i + 1, Restante - 1, 0));
        if(i + 1 < n) m = max(m, Resolver(i + 1, Restante - 2, 0) + Atracciones[i]);
        if(i > 0) m = max(m, Resolver(i - 1, Restante - 1, 0));
        if(i > 0) m = max(m, Resolver(i - 1, Restante - 2, 0) + Atracciones[i]);
    } else {
        if(i < Inicio){
            if(i > 0) m = max(m, Resolver(i - 1, Restante - 1, Giro));
            if(i > 0) m = max(m, Resolver(i - 1, Restante - 2, Giro) + Atracciones[i]);
            if(Giro == 0){
                if(Inicio + 1 < n) m = max(m, Resolver(Inicio + 1, Restante - (Inicio - i) - 1, 1));
                if(Inicio + 1 < n) m = max(m, Resolver(Inicio + 1, Restante - (Inicio - i) - 2, 1) + Atracciones[i]);
            }
        } else {
            if(i + 1 < n) m = max(m, Resolver(i + 1, Restante - 1, Giro));
            if(i + 1 < n) m = max(m, Resolver(i + 1, Restante - 2, Giro) + Atracciones[i]);
            if(Giro == 0){
                if(Inicio > 0) m = max(m, Resolver(Inicio - 1, Restante - (i - Inicio) - 1, 1));
                if(Inicio > 0) m = max(m, Resolver(Inicio - 1, Restante - (i - Inicio) - 2, 1) + Atracciones[i]);
            }
        }
    }
    m = max(m, Atracciones[i]);
    return Memorizaci_n[i][Restante][Giro] = m;
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]){
    n = N;
    Inicio = start;
    Tiempo = d;
    for(long long i = 0; i < n; i++) Atracciones.push_back(attraction[i]);
    if(Tiempo == 0) return 0;
    if(n == 1) return Atracciones[0];
    //Memorizaci_n.assign(n, vector< vector<long long> >(Tiempo + 1, vector<long long>(2, -2)));
    deque< vector<long long> > Inicio_m_s_1(2, vector<long long>(Tiempo + 1, 0)), Inicio_menos_1 = Inicio_m_s_1, Izquierda = Inicio_m_s_1, Derecha = Inicio_m_s_1;
    for(long long i = 1; i <= Tiempo; i++){
        Inicio_m_s_1[0][i] = Atracciones.back();
    }
    for(long long i = n - 2; i > Inicio; i--){
        swap(Inicio_m_s_1[0], Inicio_m_s_1[1]);
        Inicio_m_s_1[0][0] = 0;
        for(long long j = 1; j <= Tiempo; j++){
            long long m = Atracciones[i];
            m = max(m, Inicio_m_s_1[1][j - 1]);
            if(j > 1) m = max(m, Inicio_m_s_1[1][j - 2] + Atracciones[i]);
            Inicio_m_s_1[0][j] = m;
        }
    }
    for(long long i = 1; i <= Tiempo; i++){
        Inicio_menos_1[0][i] = Atracciones[0];
    }
    for(long long i = 1; i < Inicio; i++){
        swap(Inicio_menos_1[0], Inicio_menos_1[1]);
        Inicio_menos_1[0][0] = 0;
        for(long long j = 1; j <= Tiempo; j++){
            long long m = Atracciones[i];
            m = max(m, Inicio_menos_1[1][j - 1]);
            if(j > 1) m = max(m, Inicio_menos_1[1][j - 2] + Atracciones[i]);
            Inicio_menos_1[0][j] = m;
        }
    }
    for(long long i = 1; i <= Tiempo; i++){
        Izquierda[0][i] = Atracciones[0];
    }
    for(long long i = 1; i < Inicio; i++){
        swap(Izquierda[0], Izquierda[1]);
        Izquierda[0][0] = 0;
        for(long long j = 1; j <= Tiempo; j++){
            long long m = Atracciones[i];
            m = max(m, Izquierda[1][j - 1]);
            if(j > 1) m = max(m, Izquierda[1][j - 2] + Atracciones[i]);
            if(Inicio + 1 < n and j - (Inicio - i) - 1 > 0) m = max(m, Inicio_m_s_1[0][j - (Inicio - i) - 1]);
            if(Inicio + 1 < n and j - (Inicio - i) - 2 > 0) m = max(m, Inicio_m_s_1[0][j - (Inicio - i) - 2] + Atracciones[i]);
            Izquierda[0][j] = m;
        }
    }
    for(long long i = 1; i <= Tiempo; i++){
        Derecha[0][i] = Atracciones.back();
    }
    for(long long i = n - 2; i > Inicio; i--){
        swap(Derecha[0], Derecha[1]);
        Derecha[0][0] = 0;
        for(long long j = 1; j <= Tiempo; j++){
            long long m = Atracciones[i];
            m = max(m, Derecha[1][j - 1]);
            if(j > 1) m = max(m, Derecha[1][j - 2] + Atracciones[i]);
            if(Inicio > 0 and j - (i - Inicio) - 1 > 0) m = max(m, Inicio_menos_1[0][j - (i - Inicio) - 1]);
            if(Inicio > 0 and j - (i - Inicio) - 2 > 0) m = max(m, Inicio_menos_1[0][j - (i - Inicio) - 2] + Atracciones[i]);
            Derecha[0][j] = m;
        }
    }
    long long m = Atracciones[Inicio];
    if(Inicio + 1 < n) m = max(m, Derecha[0][Tiempo - 1]);
    if(Inicio + 1 < n and Tiempo > 1) m = max(m, Derecha[0][Tiempo - 2] + Atracciones[Inicio]);
    if(Inicio > 0) m = max(m, Izquierda[0][Tiempo - 1]);
    if(Inicio > 0 and Tiempo > 1) m = max(m, Izquierda[0][Tiempo - 2] + Atracciones[Inicio]);
    return m;
}

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