Cod sursa(job #542528)

Utilizator S7012MYPetru Trimbitas S7012MY Data 26 februarie 2011 14:31:29
Problema Pixels Scor 0
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.65 kb
#include <iostream>
#include <fstream>
#define DN 105
#define MAX(a,b) (((a)>(b)) ? (a) : (b))
using namespace std;

int n,dp[DN][DN][2],a[DN][DN],b[DN][DN],c[DN][DN][6];

int main()
{
    ifstream f("pixels.in");
    ofstream g("pixels.out");
    f>>n;
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) f>>a[i][j];
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) f>>b[i][j];
    for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) f>>c[i][j][0]>>c[i][j][1]>>c[i][j][2]>>c[i][j][3];
    dp[1][1][0]=a[1][1];
    dp[1][1][1]=b[1][1];
    for(int i=2; i<=n; ++i) {
        dp[1][i][0]=MAX(dp[1][i-1][0],dp[1][i-1][1]-c[1][i][3])+a[1][i];
        dp[1][i][1]=MAX(dp[1][i-1][1],dp[1][i-1][0]-c[1][i][3])+b[1][i];
        dp[i][1][0]=MAX(dp[i-1][1][0],dp[i-1][1][1]-c[i][1][0])+a[i][1];
        dp[i][1][1]=MAX(dp[i-1][1][1],dp[i-1][1][0]-c[i][1][0])+b[i][1];
    }
    for(int i=2; i<=n; ++i) for(int j=2; j<=n; ++j) {
        dp[i][j][0]=MAX(
                        MAX(dp[i-1][j][0]+dp[i][j-1][0],dp[i-1][j][1]+dp[i][j-1][1]-c[i][j][0]-c[i][j][3]),
                        MAX(dp[i-1][j][1]+dp[i][j-1][0]-c[i][j][0],dp[i-1][j][0]+dp[i][j-1][1]-c[i][j][3])
                        )
                    +a[i][j];
        dp[i][j][1]=MAX(
                        MAX(dp[i-1][j][1]+dp[i][j-1][1],dp[i-1][j][0]+dp[i][j-1][0]-c[i][j][0]-c[i][j][3]),
                        MAX(dp[i-1][j][0]+dp[i][j-1][1]-c[i][j][0],dp[i-1][j][1]+dp[i][j-1][0]-c[i][j][3])
                        )
                    +b[i][j];
        dp[i][j][0]-=dp[i-1][j-1][0];
        dp[i][j][1]-=dp[i-1][j-1][1];
    }
    g<<MAX(dp[n][n][0],dp[n][n][1]);
    cout<<MAX(dp[n][n][0],dp[n][n][1]);
    return 0;
}