oj.uz

Submission #567632

# Submission time Handle Problem Language Result Execution time Memory
567632 2022-05-23T21:21:26 Z losmi247 Raisins (IOI09_raisins) C++14
100 / 100
 259 ms 35408 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 52;

ll n,m,a[N][N];
ll pf[N][N];
ll dp[N][N][N][N];

ll suma(int i,int j,int h,int g){
    return (pf[h][g]-pf[i-1][g]-pf[h][j-1]+pf[i-1][j-1]);
}

int daj(int a,int b,int c,int d){
    if(dp[a][b][c][d] != -1) return dp[a][b][c][d];

    ll uksum = suma(a,b,c,d);
    ll minv = 7e18;
    for(int i = b; i < d; i++){
        minv = min(minv,daj(a,b,c,i)+daj(a,i+1,c,d)+uksum);
    }

    ll minh = 7e18;
    for(int i = a; i < c; i++){
        minh = min(minh,daj(a,b,i,d)+daj(i+1,b,c,d)+uksum);
    }

    return dp[a][b][c][d] = min(minv,minh);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }

    for(int j = 1; j <= m; j++) pf[1][j] = pf[1][j-1]+a[1][j];
    for(int i = 1; i <= n; i++) pf[i][1] = pf[i-1][1]+a[i][1];
    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            pf[i][j] = pf[i][j-1]+pf[i-1][j]-pf[i-1][j-1]+a[i][j];
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int h = i; h <= n; h++){
                for(int g = j; g <= m; g++){
                    if(i == h && j == g) dp[i][j][h][g] = 0;
                    else dp[i][j][h][g] = -1;
                }
            }
        }
    }

    cout << daj(1,1,n,m) << endl;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 5 ms 3412 KB Output is correct
9 Correct 6 ms 4948 KB Output is correct
10 Correct 9 ms 5960 KB Output is correct
11 Correct 6 ms 4948 KB Output is correct
12 Correct 22 ms 10780 KB Output is correct
13 Correct 35 ms 13908 KB Output is correct
14 Correct 11 ms 6100 KB Output is correct
15 Correct 55 ms 15696 KB Output is correct
16 Correct 5 ms 5460 KB Output is correct
17 Correct 17 ms 11348 KB Output is correct
18 Correct 157 ms 26108 KB Output is correct
19 Correct 235 ms 32428 KB Output is correct
20 Correct 259 ms 35408 KB Output is correct