oj.uz

Submission #675928

# Submission time Handle Problem Language Result Execution time Memory
675928 2022-12-28T12:01:31 Z Cookie Raisins (IOI09_raisins) C++14
100 / 100
 148 ms 26544 KB 
#include<bits/stdc++.h>
 
#include<fstream>
 
using namespace std;
//ifstream fin("INTERNET.INP");
//ofstream fout("INTERNET.OUT");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define int long long
typedef unsigned long long ull;
const int mxn = 1e3;
int d[51][51][51][51];
int n, m;
int p[51][51], a[51][51];
int get(int a, int b, int c, int d){
    return(p[c][d] - p[a - 1][d] - p[c][b - 1] + p[a - 1][b - 1]);
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            for(int k = 1; k <= m; k++){
                for(int l = k; l <= m; l++){
                    d[i][j][k][l] = 1e9;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j]; 
            d[i][i][j][j] = 0;
        }
    }
    for(int i = n; i >= 1; i--){
        for(int j = i; j <= n; j++){
            for(int k = m; k >= 1; k--){
                for(int l = k; l <= m; l++){
                    
                    for(int h = i; h < j; h++){
                        d[i][j][k][l] = min(d[i][j][k][l], d[i][h][k][l] + d[h + 1][j][k][l]);
                    }
                    for(int h = k; h < l; h++){
                        d[i][j][k][l] = min(d[i][j][k][l], d[i][j][k][h] + d[i][j][h + 1][l]);
                    }
                    d[i][j][k][l] += get(i, k, j, l);
                }
            }
        }
    }
    cout << d[1][n][1][m] - get(1, 1, n, m);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 336 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 724 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 3 ms 2516 KB Output is correct
9 Correct 5 ms 4052 KB Output is correct
10 Correct 5 ms 4820 KB Output is correct
11 Correct 4 ms 3540 KB Output is correct
12 Correct 12 ms 8916 KB Output is correct
13 Correct 19 ms 11604 KB Output is correct
14 Correct 6 ms 4428 KB Output is correct
15 Correct 24 ms 13268 KB Output is correct
16 Correct 4 ms 6612 KB Output is correct
17 Correct 13 ms 11380 KB Output is correct
18 Correct 89 ms 23252 KB Output is correct
19 Correct 146 ms 24524 KB Output is correct
20 Correct 148 ms 26544 KB Output is correct