Pagini recente » Monitorul de evaluare | Cod sursa (job #353463) | Diferente pentru home intre reviziile 357 si 358 | Profil PetrescuRobert | Cod sursa (job #1770114)
#include <cstdio>
#include <iostream>
using namespace std;
int v[100001],d[100001][2];
int main()
{
FILE *fin=fopen ("oo.in","r");
FILE *fout=fopen ("oo.out","w");
int n,i,maxi,incmaxi,m;
fscanf (fin,"%d",&n);
for (i=1;i<=n;i++)
fscanf (fin,"%d",&v[i]);
// d[i][j]=suma maxima pe care o poate lua fermierul pana la poz i (inclusiv) cand prima poz de pe care a luat e j
d[1][0]=v[n]+v[1];
d[1][1]=1;
d[2][0]=v[1]+v[2];
d[2][1]=2;
d[3][0]=v[2]+v[3];
d[3][1]=3;
maxi=d[1][0];
incmaxi=d[1][1];
for (i=4;i<n-1;i++){
if (d[i-3][0]+v[i]+v[i-1]>maxi+v[i]+v[i-1]){
d[i][0]=d[i-3][0]+v[i]+v[i-1];
d[i][1]=d[i-3][1];
}
else {
d[i][0]=maxi+v[i]+v[i-1];
d[i][1]=incmaxi;
}
if (maxi<d[i-3][0]){
maxi=d[i-3][0];
//printf ("%d %d\n",maxi,i);
incmaxi=d[i-3][1];
}
}
maxi=max(maxi,d[n-2][0]);
maxi=max(maxi,d[n-3][0]);
// incerc sa bag undeva grupa n+(n-1)
m=0;
for (i=n-3;i>0;i--){
if (d[i][1]==3)
m=max(m,d[i][0]);
}
m=m+v[n]+v[n-1];
maxi=max(maxi,m);
// incerc sa bag undeva grupa (n-1)+(n-2)
m=0;
for (i=n-4;i>0;i--){
if (d[i][1]!=1)
m=max(m,d[i][0]);
}
m+=v[n-1]+v[n-2];
maxi=max(maxi,m);
fprintf (fout,"%d ",maxi);
return 0;
}