- for (int l=0 ; l<=2 ; l++)
- {
- sumy[poprz][l][0]=0;
- sumy[poprz][l][1]=max(skarby[0][(l+2)%3], skarby[0][(l+4)%3]);
- sumy[poprz][l][2]=skarby[0][(l+2)%3]+skarby[0][(l+4)%3];
- for (int i=1 ; i<n ; i++)
- {
- // W kazdym sektorze bierzemy co najwyzej 2 robotnikow,
- // wiec po i-tym mozemy wybrac max 2*i+2 (i>=0)
- sumy[akt][0][0]=0;
- sumy[akt][0][1]=max(max(max(max(sumy[poprz][0][1], sumy[poprz][1][1]), sumy[poprz][2][1]),
- sumy[poprz][0][0]+max(skarby[0][1],skarby[0][2])), sumy[poprz][1][0]+skarby[0][2]);
- sumy[akt][0][2]=max(max(max(max(max(sumy[poprz][0][2], sumy[poprz][1][2]), sumy[poprz][2][2]),
- sumy[poprz][0][1]+max(skarby[0][1],skarby[0][2])), sumy[poprz][1][1]+skarby[0][2]),
- sumy[poprz][0][0]+skarby[0][1]+skarby[0][2]);
- sumy[akt][1][0]=0;
- sumy[akt][1][1]=max(max(max(max(max(sumy[poprz][0][1], sumy[poprz][1][1]), sumy[poprz][2][1]),
- sumy[poprz][0][0]+skarby[0][2]), sumy[poprz][2][0]+skarby[0][0]),
- sumy[poprz][0][0]+max(skarby[0][0],skarby[0][2]));
- sumy[akt][1][2]=max(max(max(max(max(max(sumy[poprz][0][2], sumy[poprz][1][2]), sumy[poprz][2][2]),
- sumy[poprz][0][1]+skarby[0][2]), sumy[poprz][2][1]+skarby[0][0]),
- sumy[poprz][0][1]+max(skarby[0][0],skarby[0][2])), sumy[poprz][1][0]+skarby[i][0]+
- skarby[0][2]);
- sumy[akt][2][0]=0;
- sumy[akt][2][1]=max(max(max(max(sumy[poprz][0][1], sumy[poprz][1][1]), sumy[poprz][2][1]), sumy[poprz][2][0]+
- max(skarby[0][0],skarby[0][1])), sumy[poprz][1][0]+skarby[0][0]);
- sumy[akt][2][2]=max(max(max(max(max(sumy[poprz][0][2], sumy[poprz][1][2]), sumy[poprz][2][2]), sumy[poprz][2][1]+
- max(skarby[0][0],skarby[0][1])), sumy[poprz][1][1]+skarby[0][0]), sumy[poprz][2][0]+skarby[0][0]+
- skarby[0][1]);
- for (int j=1 ; j<=min(2, k) ; j++)
- {
- maks=max(maks, sumy[akt][0][j]);
- maks=max(maks, sumy[akt][1][j]);
- maks=max(maks, sumy[akt][2][j]);
- }
- for (int j=3 ; j<=min(2*i+2, k) ; j++)
- {
- sumy[akt][0][j]=max(max(max(max(max(sumy[poprz][0][j], sumy[poprz][1][j]), sumy[poprz][2][j]),
- sumy[poprz][0][j-1]+max(skarby[i][1],skarby[i][2])), sumy[poprz][1][j-1]+skarby[i][2]),
- sumy[poprz][0][j-2]+skarby[i][1]+skarby[i][2]);
- sumy[akt][1][j]=max(max(max(max(max(max(sumy[poprz][0][j], sumy[poprz][1][j]), sumy[poprz][2][j]),
- sumy[poprz][0][j-1]+skarby[i][2]), sumy[poprz][2][j-1]+skarby[i][0]),
- sumy[poprz][0][j-1]+max(skarby[i][0],skarby[i][2])), sumy[poprz][1][j-2]+skarby[i][0]+
- skarby[i][2]);
- sumy[akt][2][j]=max(max(max(max(max(sumy[poprz][0][j], sumy[poprz][1][j]), sumy[poprz][2][j]), sumy[poprz][2][j-1]+
- max(skarby[i][0],skarby[i][1])), sumy[poprz][1][j-1]+skarby[i][0]), sumy[poprz][2][j-2]+skarby[i][0]+
- skarby[i][1]);
- // ostatni sektor
- if (i==n-1)
- {
- maks=max(maks, sumy[akt][l][j]);
- }
- else
- {
- maks=max(maks, sumy[akt][0][j]);
- maks=max(maks, sumy[akt][1][j]);
- maks=max(maks, sumy[akt][2][j]);
- }
- }
- poprz=1-poprz;
- akt=1-akt;
- }
- }