Buongiorno. Sto cercando di risolvere ois_magnamagna, e in teoria il codice qui sotto, almeno per i casi di esempio, in locale funziona. Tuttavia il correttore mi segnala tutti i casi errati con una violazione di memoria con signal 9 (che se non sbaglio dovrebbe significare che uso troppa memoria, al contrario del signal 11).
Qualcuno riesce a suggerirmi un modo per diminuire le variabili in uso? Purtroppo non vedrei come poter togliere l’array con cui memoizzo le soluzioni ottime, che, credo, comporterebbe una perdita di tempo non sostenibile. Grazie.
#include <fstream>
#include <string.h>
#include <math.h>
using namespace std;
ifstream in ("input.txt");
ofstream out("output.txt");
int n;
int v[1001];
pair<int,string> memo[1001][1001][2];
double lf, rf;
int l,r;
string g;
string giorgio(int s, int d){
lf=0; rf=0;
for(int i=s;i<=d;i++){
lf+=pow(-1, i-s)*(v[i]/pow(2,i-s));
rf+=pow(-1, i-s)*(v[d+s-i]/pow(2,i-s));
}
if(lf>rf)return "L";
else if(rf>lf)return "R";
else return "-1";
}
int rec(int s,int d, int turno){
if(turno==0){
if(s==d){
memo[s][d][0].second="R";
return v[s];
}
if(memo[s][d][0].first!=-1){
//return memo[s][d][0];
return memo[s][d][0].first;
}
l=v[s]+rec(s+1,d,1);
r=v[d]+rec(s, d-1, 1);
if(l>r){
memo[s][d][0].second="L";
}
else{
memo[s][d][0].second="R";
}
memo[s][d][0].first=max(l,r);
return memo[s][d][0].first;
}
else{
if(s==d){
memo[s][d][1].second="R";
return 0;
}
if(memo[s][d][1].second!="-1"){
return memo[s][d][1].first;
}
g=giorgio(s,d);
if(g=="-1"){
l=v[s]+rec(s+1, d, 0);
r=v[d]+rec(s, d-1, 0);
if(l>r){
memo[s][d][1].first=l;
memo[s][d][1].second="L";
}
else {
memo[s][d][1].first=r;
memo[s][d][1].second="R";
}
return max(l,r);
}
else{
memo[s][d][1].second=g;
if(g=="L")memo[s][d][1].first=rec(s+1, d, 0);
else memo[s][d][1].first=rec(s, d-1, 0);
return memo[s][d][1].first;
}
}
}
int main(){
in>>n;
for(int i=0;i<n;i++){
in>>v[i];
}
for(int i=0;i<n;i++){
for(int y=0;y<n;y++){
memo[i][y][0].first=-1;
memo[i][y][0].second="-1";
memo[i][y][1].first=-1;
memo[i][y][1].second="-1";
}
}
rec(0, n-1, 0);
/*for(int i=0;i<n;i++){
cout<<sol[i]<<" "<<endl;
}*/
int o=0;
int p=n-1;
int cont=0;
while(o<=p){
out<<memo[o][p][cont%2].second<<" ";
if(memo[o][p][cont%2].second=="L")o+=1;
else p-=1;
cont++;
}
}
EDIT: Probabilmente i testcase non sono fatti benissimo, perché mettendo come grandezza agli array 900, pur essendo il limite n<=1000, il codice totalizza 70/100, senza mai andare fuori memoria. Il problema ora è il tempo per gli ultimi 5 casi, ma anche qui chiedo consigli perché non saprei dove migliorare il codice. Grazie.