Submission #675928

#	Time	Username	Problem	Language	Result	Execution time	Memory
675928		Cookie	Raisins (IOI09_raisins)	C++14	100 / 100	148 ms	26544 KiB

raisins

#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 / 100