oj.uz

Submission #572569

# Submission time Handle Problem Language Result Execution time Memory
572569 2022-06-04T17:18:13 Z Jesus Holiday (IOI14_holiday) C++14
30 / 100
 5000 ms 6488 KB 
#include"holiday.h"
#include<bits/stdc++.h>

using namespace std;

priority_queue<long long int> caso2;

long long int tabla_izq[250001],tabla_der[250001];

int valores[100000];

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

long long int avanzar_der(int dia,int i,long long int acum=0){
    if(dia>lim||i>=lim_c) return 0;
    long long int aux=acum+valores[i];
    aux+=tabla_izq[lim-dia-(i-ini)];
    aux=max(aux,avanzar_der(dia+1,i+1,acum));
    aux=max(aux,avanzar_der(dia+2,i+1,acum+valores[i]));
    return aux;
}

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

long long int avanzar_izq(int dia,int i,long long int acum=0){
    if(dia>lim||i<0) return 0;
    long long int aux=acum+valores[i];
    aux+=tabla_der[lim-dia-(ini-i)];
    aux=max(aux,avanzar_izq(dia+1,i-1,acum));
    aux=max(aux,avanzar_izq(dia+2,i-1,acum+valores[i]));
    return aux;
}

void t_d(int dia,int i,long long int acum=0){
    if(dia>lim||i>=lim_c) return;
    tabla_der[dia]=max(acum+valores[i],tabla_der[dia]);
    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);
        res=avanzar_der(1,start);
        t_d(2,start+1);
        res=max(res,avanzar_izq(1,start));
    }
    return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 8 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1852 KB Output is correct
2 Correct 7 ms 1740 KB Output is correct
3 Correct 7 ms 1748 KB Output is correct
4 Correct 9 ms 1748 KB Output is correct
5 Correct 13 ms 1240 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 8 ms 1240 KB Output is correct
8 Correct 12 ms 1332 KB Output is correct
9 Correct 3 ms 988 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5027 ms 860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5064 ms 6488 KB Time limit exceeded
2 Halted 0 ms 0 KB -