oj.uz

Submission #874835

# Submission time Handle Problem Language Result Execution time Memory
874835 2023-11-17T21:50:25 Z _uros9 Raisins (IOI09_raisins) C++17
100 / 100
 184 ms 113784 KB 
#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

int zb[52][52][52][52],dp[52][52][52][52];

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];
    }

    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];
                }
            }
        }
    }
    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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 4 ms 27184 KB Output is correct
7 Correct 7 ms 37468 KB Output is correct
8 Correct 6 ms 43608 KB Output is correct
9 Correct 10 ms 57948 KB Output is correct
10 Correct 12 ms 60032 KB Output is correct
11 Correct 9 ms 47704 KB Output is correct
12 Correct 24 ms 76488 KB Output is correct
13 Correct 32 ms 82524 KB Output is correct
14 Correct 12 ms 52060 KB Output is correct
15 Correct 42 ms 88668 KB Output is correct
16 Correct 11 ms 88664 KB Output is correct
17 Correct 24 ms 97064 KB Output is correct
18 Correct 86 ms 109144 KB Output is correct
19 Correct 150 ms 113476 KB Output is correct
20 Correct 184 ms 113784 KB Output is correct