oj.uz

Submission #874821

# Submission time Handle Problem Language Result Execution time Memory
874821 2023-11-17T21:13:51 Z _uros9 Raisins (IOI09_raisins) C++17
30 / 100
 337 ms 106124 KB 
#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+1][m+1][n+1][m+1];
    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+1][m+1][n+1][m+1];
    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]=1e9;
            }
        }
    }
    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+d1==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
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Correct 0 ms 604 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Incorrect 3 ms 3676 KB Output isn't correct
9 Incorrect 5 ms 5616 KB Output isn't correct
10 Incorrect 8 ms 7516 KB Output isn't correct
11 Incorrect 7 ms 6492 KB Output isn't correct
12 Incorrect 28 ms 17756 KB Output isn't correct
13 Incorrect 45 ms 26712 KB Output isn't correct
14 Incorrect 10 ms 9564 KB Output isn't correct
15 Correct 62 ms 31304 KB Output is correct
16 Incorrect 4 ms 3928 KB Output isn't correct
17 Incorrect 21 ms 14424 KB Output isn't correct
18 Incorrect 153 ms 64056 KB Output isn't correct
19 Correct 273 ms 94288 KB Output is correct
20 Incorrect 337 ms 106124 KB Output isn't correct