Submission #542948

#	Time	Username	Problem	Language	Result	Execution time	Memory
542948		Sho10	Raisins (IOI09_raisins)	C++17	100 / 100	882 ms	61060 KiB

raisins

#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
using ll=long long;
using ld=long double;
int const INF=1000000005;
ll const LINF=1000000000000000005;
ll const mod=1000000007;
ld const PI=3.14159265359;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,m,dp[55][55][55][55],a[55][55],viz[55][55][55][55];
void solve(ll xl,ll xr,ll yl,ll yr){
    if(xl>xr){
        return;
    }
    if(yl>yr){
        return;
    }
if(xl==xr&&yl==yr){
    dp[xl][xr][yl][yr]=0;
    return;
}
if(viz[xl][xr][yl][yr]==1){
    return;
}
ll sum=0;
for(ll i=xl;i<=xr;i++)
{
    for(ll j=yl;j<=yr;j++)
    {
        sum+=a[i][j];
    }
}
for(ll i=xl+1;i<=xr;i++)
{
    solve(xl,i-1,yl,yr);
    solve(i,xr,yl,yr);
dp[xl][xr][yl][yr]=min(dp[xl][xr][yl][yr],dp[xl][i-1][yl][yr]+dp[i][xr][yl][yr]);
}
for(ll i=yl+1;i<=yr;i++)
{
    solve(xl,xr,yl,i-1);
    solve(xl,xr,i,yr);
    dp[xl][xr][yl][yr]=min(dp[xl][xr][yl][yr],dp[xl][xr][yl][i-1]+dp[xl][xr][i][yr]);
}
dp[xl][xr][yl][yr]+=sum;
viz[xl][xr][yl][yr]=1;
}
int32_t main(){
CODE_START;
#ifdef LOCAL
    ifstream cin("input.txt");
#endif
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
    for(ll j=1;j<=m;j++)
    {
        cin>>a[i][j];
    }
}
for(ll i=1;i<=n;i++)
{
    for(ll j=1;j<=m;j++)
    {
        for(ll i1=i;i1<=n;i1++)
            for(ll j1=j;j1<=m;j1++)
        {
            dp[i][i1][j][j1]=LINF;
        }
    }
}
solve(1,n,1,m);
cout<<dp[1][n][1][m]<<endl;
}

• Subtask 1: 100 / 100