oj.uz

Submission #874832

# Submission time Handle Problem Language Result Execution time Memory
874832 2023-11-17T21:45:22 Z _uros9 Raisins (IOI09_raisins) C++17
95 / 100
 345 ms 131072 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+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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 5 ms 6924 KB Output is correct
9 Correct 8 ms 9820 KB Output is correct
10 Correct 12 ms 12888 KB Output is correct
11 Correct 9 ms 11612 KB Output is correct
12 Correct 33 ms 27968 KB Output is correct
13 Correct 62 ms 40300 KB Output is correct
14 Correct 19 ms 16472 KB Output is correct
15 Correct 68 ms 46676 KB Output is correct
16 Correct 9 ms 8024 KB Output is correct
17 Correct 34 ms 23820 KB Output is correct
18 Correct 208 ms 89996 KB Output is correct
19 Correct 345 ms 128664 KB Output is correct
20 Runtime error 77 ms 131072 KB Execution killed with signal 9