Submission #567632

#	Time	Username	Problem	Language	Result	Execution time	Memory
567632		losmi247	Raisins (IOI09_raisins)	C++14	100 / 100	259 ms	35408 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 52;

ll n,m,a[N][N];
ll pf[N][N];
ll dp[N][N][N][N];

ll suma(int i,int j,int h,int g){
    return (pf[h][g]-pf[i-1][g]-pf[h][j-1]+pf[i-1][j-1]);
}

int daj(int a,int b,int c,int d){
    if(dp[a][b][c][d] != -1) return dp[a][b][c][d];

    ll uksum = suma(a,b,c,d);
    ll minv = 7e18;
    for(int i = b; i < d; i++){
        minv = min(minv,daj(a,b,c,i)+daj(a,i+1,c,d)+uksum);
    }

    ll minh = 7e18;
    for(int i = a; i < c; i++){
        minh = min(minh,daj(a,b,i,d)+daj(i+1,b,c,d)+uksum);
    }

    return dp[a][b][c][d] = min(minv,minh);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    for(int j = 1; j <= m; j++) pf[1][j] = pf[1][j-1]+a[1][j];
    for(int i = 1; i <= n; i++) pf[i][1] = pf[i-1][1]+a[i][1];
    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            pf[i][j] = pf[i][j-1]+pf[i-1][j]-pf[i-1][j-1]+a[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int h = i; h <= n; h++){
                for(int g = j; g <= m; g++){
                    if(i == h && j == g) dp[i][j][h][g] = 0;
                    else dp[i][j][h][g] = -1;
                }
            }
        }
    }

    cout << daj(1,1,n,m) << endl;
}

• Subtask 1: 100 / 100