La mia soluzione non supera l’ultimo subtask a causa della violazione dei limiti della memoria consentita. Temo si tratti del vettore di supporto che utilizzo per implementare l’algoritmo di programmazione dinamica, nonostante allochi solamente il numero di celle strettamente necessarie più una, cioè N*(N - 1)/2 celle più una che non sono riuscito ad evitare.
La logica sono sicuro sia giusta al 99,9%.
Qualcuno è riuscito a fare di meglio?
#include <vector>
#include <iostream>
using namespace std;
/*classe che mantiene il max, il min e la validità di ogni sequenza possibile*/
class MaxAndMin{
public:
int min = __INT_MAX__;
int max = 0;
bool validSequence;
};
long long conta(int N, vector<int> A){
MaxAndMin matrix[(N - 1) * N / 2 + 1];
int count = 0; //conta le seq miglioranti
// CASO BASE: SEQUENZE DI DUE ELEMENTI
for(int i = 0; i < N - 1; i++){
if(A[i] < A[i + 1]){
matrix[i + 1].min = A[i];
matrix[i + 1].max = A[i + 1];
matrix[i + 1].validSequence = true;
count++;
}
else{
matrix[i + 1].min = A[i + 1];
matrix[i + 1].max = A[i];
matrix[i + 1].validSequence = false;
}
}
int offset = 0; //indice da cui partire a ogni for esterno
/*delta rappresenta il distacco tra una cella e quella a cui si appoggia l'algoritmo dp*/
for(int delta = N - 1; delta >= 2; delta--){
int k = N - delta;
for(int i = 1; i < N - k; i++){//i-esimo elemento diagonale per diagonale
int j = i + k; // indice di A
if(A[j] < matrix[i + offset].min){
matrix[i + offset + delta].validSequence = false;
matrix[i + offset + delta].min = A[j];
matrix[i + offset + delta].max = matrix[i + offset].max;
}
else if(A[j] > matrix[i + offset].max){
matrix[i + offset + delta].max = A[j];
matrix[i + offset + delta].min = matrix[i + offset].min;
matrix[i + offset + delta].validSequence = true;
count++;
}
else{
if(matrix[i + offset].validSequence)
count++;
matrix[i + offset + delta].max = matrix[i + offset].max;
matrix[i + offset + delta].min = matrix[i + offset].min;
matrix[i + offset + delta].validSequence = matrix[i + offset].validSequence;
}
}
offset += delta;
}
return count;
}`Testo preformattato`