# Violazione del limite di memoria https://training.olinfo.it/#/task/preoii\_allenamento/statement

**URL:** <https://forum.olinfo.it/t/violazione-del-limite-di-memoria-https-training-olinfo-it-task-preoii-allenamento-statement/7312>\
**Category:** Aiuto\
**Created:** [3 Maggio 2022, 2:32pm UTC](https://forum.olinfo.it/t/violazione-del-limite-di-memoria-https-training-olinfo-it-task-preoii-allenamento-statement/7312 "2022-05-03T14:32:01Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![peppe17](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/p/a8b319/32.png) [@peppe17](https://forum.olinfo.it/u/peppe17)\
**Post date:** [3 Maggio 2022, 2:32pm UTC](https://forum.olinfo.it/t/violazione-del-limite-di-memoria-https-training-olinfo-it-task-preoii-allenamento-statement/7312/1 "2022-05-03T14:32:02Z")

</div>

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?

```auto
#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`

```

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [4 Maggio 2022, 9:31pm UTC](https://forum.olinfo.it/t/violazione-del-limite-di-memoria-https-training-olinfo-it-task-preoii-allenamento-statement/7312/2 "2022-05-04T21:31:39Z")

</div>

Ciao, per prendere il punteggio completo devi trovare una soluzione con complessità \mathcal{O}(N) di tempo e spazio. Se non riesci a trovare la soluzione puoi consultare la spiegazione sulla [wiki](https://wiki.olinfo.it/it/2021/pre-oii/allenamento).