Submission #1142341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142341		Gabriel	Holiday (IOI14_holiday)	C++20	0 / 100	91 ms	131072 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 or 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){
        m = max(m, Resolver(i + 1, Restante - 1, 0));
        m = max(m, Resolver(i + 1, Restante - 2, 0) + Atracciones[i]);
        m = max(m, Resolver(i - 1, Restante - 1, 0));
        m = max(m, Resolver(i - 1, Restante - 2, 0) + Atracciones[i]);
    } else {
        if(i < Inicio){
            m = max(m, Resolver(i - 1, Restante - 1, Giro));
            m = max(m, Resolver(i - 1, Restante - 2, Giro) + Atracciones[i]);
            if(Giro == 0){
                m = max(m, Resolver(Inicio + 1, Restante - (Inicio - i) - 1, 1));
                m = max(m, Resolver(Inicio + 1, Restante - (Inicio - i) - 2, 1) + Atracciones[i]);
            }
        } else {
            m = max(m, Resolver(i + 1, Restante - 1, Giro));
            m = max(m, Resolver(i + 1, Restante - 2, Giro) + Atracciones[i]);
            if(Giro == 0){
                m = max(m, Resolver(Inicio - 1, Restante - (i - Inicio) - 1, 1));
                m = max(m, Resolver(Inicio - 1, Restante - (i - Inicio) - 2, 1) + 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(n == 1){
        if(Tiempo > 0) return Atracciones[0];
        else return 0;
    }
    Memorizaci_n.assign(n, vector< vector<long long> >(Tiempo + 1, vector<long long>(2, -2)));
    return Resolver(Inicio, Tiempo, 0);
}

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