Submission #1089533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089533		salmon	Raisins (IOI09_raisins)	C++14	100 / 100	398 ms	30832 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

int N;
int M;
long long int lst[55][55];
long long int pre[55][55];
long long int memo[55][55][55][55];
long long int inf = 2e18;

long long int dp(int l, int r, int l1, int r1){
    if(memo[l][r][l1][r1] != -1) return memo[l][r][l1][r1];
    if(l == r && l1 == r1) return memo[l][r][l1][r1] = 0;

    long long int V = pre[r][r1] - pre[l - 1][r1] - pre[r][l1 - 1] + pre[l - 1][l1 - 1];
    long long int V1 = inf;

    if(l != r){
        for(int i = l; i < r; i++){
            V1 = min(V1, dp(l,i,l1,r1) + dp(i + 1, r, l1, r1) );
        }
    }
    if(l1 != r1){
        for(int i = l1; i < r1; i++){
            V1 = min(V1, dp(l,r,l1,i) + dp(l,r,i + 1, r1));
        }
    }

    return memo[l][r][l1][r1] = V + V1;
}

int main(){

    scanf(" %d",&N);
    scanf(" %d",&M);

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            scanf(" %d",&lst[i][j]);
        }
    }

    for(int i = 0; i <= N; i++){
        pre[i][0] = 0;
    }

    for(int j = 0; j <= M; j++){
        pre[0][j] = 0;
    }

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            pre[i][j] = lst[i][j] + pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1];
        }
    }

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            for(int i1 = i; i1 <= N; i1++){
                for(int j1 = j; j1 <= M; j1++){
                    memo[i][i1][j][j1] = -1;
                }
            }
        }
    }

    printf("%lld",dp(1,N,1,M));

}

Compilation message (stderr)

raisins.cpp: In function 'int main()':
raisins.cpp:39:22: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   39 |             scanf(" %d",&lst[i][j]);
      |                     ~^  ~~~~~~~~~~
      |                      |  |
      |                      |  long long int*
      |                      int*
      |                     %lld
raisins.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
raisins.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
raisins.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |             scanf(" %d",&lst[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100