Ieri quando ho finito l iterativa di marcel mi aspettavo un 85 ,dovuto alla matrice da 120 120 120 120 di int che dovrebbe sforare di memoria .
Non so ieri cosa sia successo al server prendo 55.
1 sub corretto
2 sub corretto
3 sub corretto
4 tle ( ?)
5 un output sbagliato (?)
6 corretto
Essendo che sono nuovo e non so cosa sia successo alla mia matrice, perché per mie conoscenze non so come calcolare precisamente la memoria ed il tempo ,ma so dare solo una stima ;non so minimamente cosa fare o cosa sia successo a questo problema.
Cosa divertente nel subtask 4
La memoria 250 mib
Nel 6 1.9mib
Ciao!
Non posso risponderti con certezza, non avendo risolto il problema, dico solo che l’accepted sul subtask 6 mi sembra molto strano 
(meglio così si intende) e che il TLE sul subtask 4 penso sia dato dal fatto che per ogni rettangolo tutte e 5 le mosse sono consentite, quindi il tuo programma finisce ad analizzare tutti gli stati della dp (mentre negli altri testcase alcuni venivano scartati perchè irraggiungibili), posso sapere esattamente come calcoli la somma dei valori sui lati dei rettangoli?
Ah e nel subtask 5 forse è un errore di overflow? But again, posso solo ipotizzare, inoltre continua a sembrarmi strano che sul 6 non ci siano controesempi.
2 Mi Piace
Utilizzo una matrice quadradimensionale per ogni lato ed una prefix sum 2d per avere in costante la somma del lato interessato e se quest’ultima ≥X carico sulla cella successiva al taglio compiuto il numero di partite che posso fare aggiornando una variabile accumulatrice ,ovviamente effettuando il modulo ad entrambi, se peró il lato corrisponde con il rettangolo ottenuto fermo la dp ed aggiungo le partite che arrivano a quella cella tutto questo considerando l’opzione di poter finire il gioco
2 Mi Piace
Quello che fai tu è giustissimo, a questo punto ricontrolla solo se effettivamente fai il modulo ad ogni singola addizione (e non scrivi magari a+=b%mod invece di a=(a+b)%mod).
Per il subtask 4 dovrebbe esistere una soluzione in O(N^2) se non sbaglio.
1 Mi Piace
sono riuscito a fare 75 prendendo 1 2 3 4 6 testcase adesso però non so che fare ho ricontrollato i moduli e vanno tutti bene (ho un solo testcase che va in rosso )
Ho usato anch’io una matrice a 4 dimensioni e mi aspettavo di sforare la memoria e invece NO!
Meglio così e non è la prima volta che fila tutto liscio però non mi è chiaro il perchè.
(120^4) * sizeof(int) se non ho erro fa più di 800MB e io l’ho dichiarata statica.
Mi viene da pensare che venga calcolata solo quella che usa e che in tutti i testcase N sia ben minore di 120.
Inoltre,a giudicare dai report i testcase del subtask 6 vengono risolti così rapidamente e con così poca memoria da essere comparabili a quelli del subtask 2. Il più pesante per l’occupazione di memoria è il subtask 4 (comunque 60MB max) , penso che i suoi testcase siano quelli con i maggiori valori di N.
Lo deduco anche dal fatto che per risolvere il subtask 4 l’algoritmo che mi andava bene per gli altri era troppo lento e ne ho dovuto usare uno ad hoc che taglia solo da due lati ortogonali fra loro.
3 Mi Piace
Ho poca esperienza sulla piattaforma ma ricordo che quando ho risolto dijkstra avendo dichiarato un vettore bool&long long int&vector di pair di long long int di 10000005 celle avevo ovviamente ~220MB fissi occupati, mi sembra strano che il calcolo di memoria occupata cambi da problema a problema
questo problema è magia nera secondo me domani starà a 1000 punti 
Non è molto un fatto di dimensione della griglia, quanto più di stati possibili, nel subtask 4 è possibile arrivare a tutti gli stati della dp, mentre a quanto pare nel 6 no (pur essendo n=120 per tutti i testcase) questo dovrebbe influire anche sulla memoria, infatti se delle regioni di memoria non vengono mai visitate può succedere che non vengano contate come memoria utilizzata.
Grazie per le informazioni, tra l’altro riguardando le cose ho riscritto la funzione per il subtask 4 utilizzando un array aggiuntivo a 2 dimensioni e l’uso della memoria in tutti i testcase del 4 è drasticamente calato sotto il MB il che conferma quello che mi dicevi:
Inoltre sono andati praticamente a 0 anche i tempi di esecuzione nel subtask4 dai 170ms di prima.
1 Mi Piace
ma il modulo lo devo mettere pure alla prefix sum?
perchè il subtask 5 rimane irrisolto :<
essendo che l ho messo sia quando vado a propagare le partite sia quando vado ad utilizzare l incremento non capisco perchè il 025 mi da output sbagliato
No non dovrebbe essere messo sulla prefix sum
#include<bits/stdc++.h>
using namespace std;
long long int mat[121][121];
int aux[120][120][121][121];
int main()
{
int cont=0;
long long int N,X,z=0;
cin>>N>>X;
for(int i=1;i<N+1;i++)
{
for(int j=1;j<N+1;j++)
{
cin>>mat[i][j];
mat[i][j]=mat[i][j]+mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1];
}
}
aux[0][0][1][1]=1;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
for(int k=1;k<N+1;k++)
{
for(int l=1;l<N+1;l++)
{
if(aux[i][j][k][l]!=0)
{
aux[i][j][k][l]%=1000000007;
long long int sopra=mat[l][N-i]-mat[l-1][N-i]-mat[l][k-1]+mat[l-1][k-1];
long long int sinistra=mat[N-j][k]-mat[N-j][k-1]-mat[l-1][k]+mat[l-1][k-1];
long long int sotto=mat[N-j][N-i]-mat[N-j-1][N-i]-mat[N-j][k-1]+mat[N-j-1][k-1];
long long int destra=mat[N-j][N-i]-mat[N-j][N-i-1]-mat[l-1][N-i]+mat[l-1][N-i-1];
long long int Y=mat[N-j][N-i]-mat[N-j][k-1]-mat[l-1][N-i]+mat[l-1][k-1];
if(sopra>=X)
{
if(sopra==Y)
{
cont=(cont+aux[i][j][k][l])%1000000007;
}
else
{
aux[i][j][k][l+1]=(aux[i][j][k][l]+aux[i][j][k][l+1])%1000000007;
}
}
if(sinistra>=X)
{
if(sinistra==Y)
{
cont=(cont+aux[i][j][k][l])%1000000007;
}
else
{
aux[i][j][k+1][l]=(aux[i][j][k][l]+aux[i][j][k+1][l])%1000000007;
}
}
if(sotto>=X)
{
if(sotto==Y)
{
cont=(cont+aux[i][j][k][l])%1000000007;
}
else
{
aux[i][j+1][k][l]=(aux[i][j][k][l]+aux[i][j+1][k][l])%1000000007;
}
}
if(destra>=X)
{
if(destra==Y)
{
cont=(cont+aux[i][j][k][l])%1000000007;
}
else
{
aux[i+1][j][k][l]=(aux[i][j][k][l]+aux[i+1][j][k][l])%1000000007;
}
}
cont=(cont+aux[i][j][k][l])%1000000007;
}
}
}
}
}
cout<<cont;
}
non so cosa fare il codice di suo da 55 essendo che devo mettere un code a parte per quel subtask
di suo però questo codice dovrebbe fare tutti i sub tranne il 4
ma il 025 non lo fa (subtask 5 N<=50 )
help me 
Eh ma non basta dire che sinistra (o qualunque degli altri 3) è uguale a y per dire che ricopre tutto il rettangolo, ad esempio
0 1 -1
0 1 -1
0 1 -1
1 Mi Piace
grazie mille non ci avevo pensato essendo che era la mia prima volta con una prefix sum bidimensionale non avevo pensato a quella condizione
1 Mi Piace