Submission #874832

#	Time	Username	Problem	Language	Result	Execution time	Memory
874832		_uros9	Raisins (IOI09_raisins)	C++17	95 / 100	345 ms	131072 KiB

raisins

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;



signed main()
{
    int n,m;
    cin >> n >> m;
    vector<vector<int>> matr(n+1,vector<int>(m+1));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++)
            cin >> matr[i][j];
    }
    int zb[n+5][m+5][n+5][m+5];
    for(int i=0; i<=n; i++){//pravljenje
        for(int j=0; j<=m; j++){
            for(int ii=0; ii<=n; ii++){
                for(int jj=0; jj<=m; jj++)
                    zb[i][j][ii][jj]=0;
            }
        }
    }
    for(int y1=1; y1<=n; y1++){
        for(int x1=1; x1<=m; x1++){
            for(int y2=y1; y2<=n; y2++){
                for(int x2=x1; x2<=m; x2++){
                    zb[y1][x1][y2][x2]=(y2-1<y1?0:zb[y1][x1][y2-1][x2])+(x2-1<x1?0:zb[y1][x1][y2][x2-1])-(((y2-1<y1)||(x2-1<x1))?0:zb[y1][x1][y2-1][x2-1])+matr[y2][x2];
                }
            }
        }
    }
    int dp[n+5][m+5][n+5][m+5];
    for(int i=0; i<=n; i++){//pravljenje
        for(int j=0; j<=m; j++){
            for(int ii=0; ii<=n; ii++){
                for(int jj=0; jj<=m; jj++)
                    dp[i][j][ii][jj]=1000000000000000000;
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++)
            dp[i][j][i][j]=0;//matr[i][j];
    }
    for(int d1=0; d1<=n; d1++){
        for(int d2=0; d2<=m; d2++){
            for(int y1=1; y1+d1<=n; y1++){
                for(int x1=1; x1+d2<=m; x1++){
                    if(d1+d2==0) continue;
                    int sum=zb[y1][x1][y1+d1][x1+d2];
                    for(int k=0; k<d2; k++){
                        dp[y1][x1][y1+d1][x1+d2]=min(dp[y1][x1][y1+d1][x1+d2],sum+dp[y1][x1][y1+d1][x1+k]+dp[y1][x1+k+1][y1+d1][x1+d2]);
                    }
                    for(int k=0; k<d1; k++){
                        dp[y1][x1][y1+d1][x1+d2]=min(dp[y1][x1][y1+d1][x1+d2],sum+dp[y1][x1][y1+k][x1+d2]+dp[y1+k+1][x1][y1+d1][x1+d2]);
                    }
                }
            }
        }
    }
    cout << dp[1][1][n][m];


    return 0;
}

• Subtask 1: 95 / 100