oj.uz

Submission #1089533

# Submission time Handle Problem Language Result Execution time Memory
1089533 2024-09-16T16:01:02 Z salmon Raisins (IOI09_raisins) C++14
100 / 100
 398 ms 30832 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 6 ms 2860 KB Output is correct
9 Correct 9 ms 4416 KB Output is correct
10 Correct 13 ms 5212 KB Output is correct
11 Correct 11 ms 3928 KB Output is correct
12 Correct 40 ms 9564 KB Output is correct
13 Correct 77 ms 12428 KB Output is correct
14 Correct 17 ms 4700 KB Output is correct
15 Correct 96 ms 14136 KB Output is correct
16 Correct 10 ms 7004 KB Output is correct
17 Correct 32 ms 11868 KB Output is correct
18 Correct 205 ms 24848 KB Output is correct
19 Correct 348 ms 28252 KB Output is correct
20 Correct 398 ms 30832 KB Output is correct