Submission #1125935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125935		AverageAmogusEnjoyer	Raisins (IOI09_raisins)	C++20	100 / 100	152 ms	26940 KiB

raisins

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}

const int N=51;
int dp[N][N][N][N];
int n,m;
int grid[N][N];
const int inf=1e9;

int get_sum(int x1,int y1,int x2,int y2) {
    return grid[x2][y2]-(x1>0?grid[x1-1][y2]:0)-(y1>0?grid[x2][y1-1]:0)+(x1>0&&y1>0?grid[x1-1][y1-1]:0);
}

int solve(int x1,int y1,int x2,int y2) {
    int &now = dp[x1][y1][x2][y2];
    if (now < inf)
        return now;
    for (int x=x1;x<x2;x++) {
        cmin(now,solve(x1,y1,x,y2)+solve(x+1,y1,x2,y2));
    }    
    for (int y=y1;y<y2;y++) {
        cmin(now,solve(x1,y1,x2,y)+solve(x1,y+1,x2,y2));
    }
    now+=get_sum(x1,y1,x2,y2);
    return now;
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    cin >> n >> m;
    memset(dp,0x3f,sizeof(dp));
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++) {
            cin >> grid[i][j];
            dp[i][j][i][j]=0;
        }
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++)
            grid[i][j]+=(i > 0?grid[i-1][j]:0)+(j>0?grid[i][j-1]:0)-(i>0&&j>0?grid[i-1][j-1]:0);
    cout << solve(0,0,n-1,m-1) << "\n";
}

• Subtask 1: 100 / 100