oj.uz

Submission #542940

# Submission time Handle Problem Language Result Execution time Memory
542940 2022-03-28T13:34:22 Z Sho10 Raisins (IOI09_raisins) C++17
5 / 100
 1 ms 304 KB 
#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];
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(dp[xl][xr][yl][yr]!=LINF){
    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(xr,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;
}
int32_t main(){
CODE_START;
#ifndef LOCAL_ENGINE
    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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Incorrect 0 ms 304 KB Output isn't correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Incorrect 0 ms 212 KB Output isn't correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Incorrect 0 ms 212 KB Output isn't correct
15 Incorrect 0 ms 212 KB Output isn't correct
16 Incorrect 0 ms 212 KB Output isn't correct
17 Incorrect 0 ms 212 KB Output isn't correct
18 Incorrect 1 ms 212 KB Output isn't correct
19 Incorrect 0 ms 212 KB Output isn't correct
20 Incorrect 0 ms 212 KB Output isn't correct