oj.uz

Submission #1044708

# Submission time Handle Problem Language Result Execution time Memory
1044708 2024-08-05T12:38:55 Z ByeWorld Raisins (IOI09_raisins) C++14
100 / 100
 71 ms 30652 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
typedef pair<ld,ld> pll;
const int MAXN = 3e5+15;
const int INF = 3e18+10;
const int MX = 2e18;
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m;
int a[55][55], pr[55][55];
int dp[55][55][55][55];

int get(int a, int b, int c, int d){ // a-b * c-d
    return pr[b][d]+pr[a-1][c-1]-pr[a-1][d]-pr[b][c-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=1; j<=m; j++){
            cin >> a[i][j];
            pr[i][j] = pr[i-1][j]+pr[i][j-1]-pr[i-1][j-1]+a[i][j];
        }
    }
    for(int lx=1; lx<=n; lx++){
        for(int x=1; x+lx-1<=n; x++){
            int y=x+lx-1;
            for(int ly=1; ly<=m; ly++){ // ver
                for(int a=1; a+ly-1<=m; a++){
                    int b = a+ly-1;
                    if(lx==1 && ly==1) continue;
                    int mn = INF;
                    // ver || |||
                    for(int c=a; c<=b-1; c++){
                        chmn(mn, dp[x][y][a][c]+dp[x][y][c+1][b]);
                    }
                    for(int z=x; z<=y-1; z++){
                        chmn(mn, dp[x][z][a][b]+dp[z+1][y][a][b]);
                    }
                    dp[x][y][a][b] = mn+get(x,y,a,b); 
                }
            }
        }
    }
    cout << dp[1][n][1][m] << '\n';
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 0 ms 1116 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 4444 KB Output is correct
10 Correct 4 ms 5212 KB Output is correct
11 Correct 3 ms 3932 KB Output is correct
12 Correct 10 ms 9564 KB Output is correct
13 Correct 15 ms 12380 KB Output is correct
14 Correct 5 ms 4700 KB Output is correct
15 Correct 22 ms 14024 KB Output is correct
16 Correct 4 ms 7004 KB Output is correct
17 Correct 11 ms 12076 KB Output is correct
18 Correct 46 ms 24920 KB Output is correct
19 Correct 61 ms 28244 KB Output is correct
20 Correct 71 ms 30652 KB Output is correct