Submission #230021

#	Time	Username	Problem	Language	Result	Execution time	Memory
230021		CaroLinda	Raisins (IOI09_raisins)	C++14	100 / 100	830 ms	21624 KiB

raisins

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define mkt make_tuple
#define debug printf
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair

const int MAX = 52 ;
const int inf = 1e9+10 ;

using namespace std ;

int N , M ;
int grid[MAX][MAX] ;
int dp[MAX][MAX][MAX][MAX] ;

int get(int a1, int b1, int a2, int b2) { return grid[a2][b2] - grid[a1-1][b2] - grid[a2][b1-1] + grid[a1-1][b1-1] ; }

int solve(int a1, int b1, int a2, int b2 )
{
    int &ptr = dp[a1][b1][a2][b2] ;

    if( ptr != 0 || (a1 == a2  && b1 == b2) ) return ptr ;

    ptr = inf ;

    for(int i = b1 ; i < b2 ; i++ )
        ptr = min( ptr , solve( a1, b1 , a2 , i ) + solve(a1, i+1, a2, b2) ) ;
    for(int i = a1 ; i <a2 ; i++ )
        ptr = min( ptr , solve(a1, b1, i , b2) + solve(i+1, b1, a2, b2) ) ;

   // debug("%d %d %d %d -> %d\n" , a1, b1, a2, b2 , ptr + get(a1,b1,a2,b2))     ;

    return ptr += get(a1,b1,a2,b2) ;

}

int main()
{
    scanf("%d%d", &N , &M ) ;
    lp(i,1,N+1)
        lp(j,1,M+1)
        {
            scanf("%d",&grid[i][j] ) ;
            grid[i][j] += -grid[i-1][j-1] + grid[i-1][j] + grid[i][j-1] ;
        }

    printf("%d\n", solve(1,1,N,M) ) ;


}

Compilation message (stderr)

raisins.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
raisins.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
raisins.cpp: In function 'int main()':
raisins.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N , &M ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~
raisins.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&grid[i][j] ) ;
             ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100