oj.uz

Submission #1081951

# Submission time Handle Problem Language Result Execution time Memory
1081951 2024-08-30T13:13:01 Z Dennis_Jason Raisins (IOI09_raisins) C++14
100 / 100
 559 ms 32344 KB 
#include <bits/stdc++.h>
#define NMAX 2005
#define pb push_back
#define eb emplace_back
#define MOD 100003
#define nl '\n'
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int>
//#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
 *
 *
    ================DEMONSTRATION===================


    =====================END========================
 */
int INF =2147483647;
int n,m;
int mat[55][55];
int sp[55][55];
int dp[55][55][55][55];
int suma(int x1, int y1, int x2, int y2) {
    return sp[x2][y2] - (x1 > 1 ? sp[x1-1][y2] : 0) - (y1 > 1 ? sp[x2][y1-1] : 0) + (x1 > 1 && y1 > 1 ? sp[x1-1][y1-1] : 0);
}
int solve(int x,int y,int N,int M)
{

    if(x==N && y==M)
    {
        return 0;
    }
    if(dp[x][y][N][M]!=INF)
        return dp[x][y][N][M];
    int mini=INF;

    //cut on horizontal
    for(int i=y;i<M;++i)
    {
        mini=min(mini,solve(x,i+1,N,M)+solve(x,y,N,i)+suma(x,y,N,M));
    }

    //cut on vertical
    for(int i=x;i<N;++i)
    {
        mini=min(mini,solve(x,y,i,M)+solve(i+1,y,N,M)+suma(x,y,N,M));
    }
    return dp[x][y][N][M]=mini;
}
signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cin>>mat[i][j];
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            for(int k=1;k<=n;++k)
            {
                for(int l=1;l<=m;++l)
                {
                    dp[i][j][k][l]=INF;
                }
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            sp[i][j]=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1]+mat[i][j];
        }
    }

    cout<<solve(1,1,n,m);



    return 0;
}

Compilation message

raisins.cpp:7: warning: "LLONG_MAX" redefined
    7 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from raisins.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      |

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 9 ms 12636 KB Output is correct
9 Correct 14 ms 15300 KB Output is correct
10 Correct 22 ms 16732 KB Output is correct
11 Correct 16 ms 14684 KB Output is correct
12 Correct 57 ms 20308 KB Output is correct
13 Correct 95 ms 20828 KB Output is correct
14 Correct 26 ms 14684 KB Output is correct
15 Correct 142 ms 23388 KB Output is correct
16 Correct 11 ms 20312 KB Output is correct
17 Correct 45 ms 24924 KB Output is correct
18 Correct 294 ms 28208 KB Output is correct
19 Correct 492 ms 31232 KB Output is correct
20 Correct 559 ms 32344 KB Output is correct