Submission #222920

#	Time	Username	Problem	Language	Result	Execution time	Memory
222920		miello	Raisins (IOI09_raisins)	C++11	100 / 100	307 ms	35192 KiB

raisins

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9 + 7;

int dp[55][55][55][55];
int c[55][55];
int n , m;

void recur(int f , int s , int l , int r){
    if(f == l && s == r){
        dp[f][s][f][s] = 0;
        return;
    }
    for(int i = f ; i < l ; i++){
        if(dp[f][s][i][r] == INF){
            recur(f , s , i , r);
        }
        if(dp[i + 1][s][l][r] == INF){
            recur(i + 1 , s , l , r);
        }
        dp[f][s][l][r] = min(dp[f][s][l][r],dp[f][s][i][r] + dp[i + 1][s][l][r] + c[l][r] - c[f - 1][r] - c[l][s - 1] + c[f - 1][s - 1]); 
    }
    for(int i = s ; i < r ; i++){
        if(dp[f][s][l][i] == INF){
            recur(f , s , l , i);
        }
        if(dp[f][i + 1][l][r] == INF){
            recur(f , i + 1 , l , r);
        }
        dp[f][s][l][r] = min(dp[f][s][l][r],dp[f][s][l][i] + dp[f][i + 1][l][r] + c[l][r] - c[f - 1][r] - c[l][s - 1] + c[f - 1][s - 1]);         
    }
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            scanf("%d",&c[i][j]);
        }
    }
    for(int i = 1 ; i < 55 ; i++){
        for(int j = 1 ; j < 55 ; j++){
            for(int k = 1 ; k < 55 ; k++){
                for(int l = 1 ; l < 55 ; l++){
                    dp[i][j][k][l] = INF;
                }
            }
        }
    }
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= m ; j++){
            c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];
        }
    }
    recur(1 , 1 , n , m);
    printf("%d",dp[1][1][n][m]);
}

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:36: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:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&c[i][j]);
             ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100