oj.uz

Submission #874823

# Submission time Handle Problem Language Result Execution time Memory
874823 2023-11-17T21:16:14 Z _uros9 Raisins (IOI09_raisins) C++17
30 / 100
 321 ms 106344 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]=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+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 348 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 0 ms 604 KB Output isn't correct
8 Incorrect 3 ms 3676 KB Output isn't correct
9 Incorrect 5 ms 5468 KB Output isn't correct
10 Incorrect 9 ms 7504 KB Output isn't correct
11 Incorrect 6 ms 6492 KB Output isn't correct
12 Incorrect 29 ms 17756 KB Output isn't correct
13 Incorrect 46 ms 26716 KB Output isn't correct
14 Incorrect 10 ms 9564 KB Output isn't correct
15 Correct 57 ms 31272 KB Output is correct
16 Incorrect 5 ms 4184 KB Output isn't correct
17 Incorrect 22 ms 14428 KB Output isn't correct
18 Incorrect 152 ms 64056 KB Output isn't correct
19 Correct 263 ms 94396 KB Output is correct
20 Incorrect 321 ms 106344 KB Output isn't correct