oj.uz

Submission #221799

# Submission time Handle Problem Language Result Execution time Memory
221799 2020-04-11T07:53:35 Z patrikpavic2 Raisins (IOI09_raisins) C++17
100 / 100
 657 ms 45512 KB 
/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  raisins
* score: 100.0
* date:  2019-05-11 08:03:57.940953
*/
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 53;
const int INF = 0x3f3f3f3f;

int dp[N][N][N][N], pref[N][N], cost[N][N][N][N], n, m, A[N][N];

int calc_cost(int x1,int x2,int y1,int y2){
    int ret = pref[x2][y2];
    if(x1) ret -= pref[x1 - 1][y2];
    if(y1) ret -= pref[x2][y1 - 1];
    if(x1 && y1) ret += pref[x1 - 1][y1 - 1];
    return ret;
}

int f(int x1,int x2,int y1,int y2){
    if(x1 == x2 && y1 == y2) return 0;
    if(dp[x1][x2][y1][y2] != -1) return dp[x1][x2][y1][y2];
    int ret = INF;
    for(int k = x1;k < x2;k++){
        ret = min(ret, f(x1, k, y1, y2) + f(k + 1, x2, y1, y2));
    }
    //printf("%d %d %d %d => %d + %d\n", x1, x2, y1, y2, ret, cost[x1][x2][y1][y2]);
    for(int k = y1;k < y2;k++){
        ret = min(ret, f(x1, x2, y1, k) + f(x1, x2, k + 1, y2));
    }
   // printf("%d %d %d %d => %d + %d\n", x1, x2, y1, y2, ret, cost[x1][x2][y1][y2]);
    return dp[x1][x2][y1][y2] = ret + cost[x1][x2][y1][y2];
}

int main(){
    memset(dp, -1, sizeof(dp));
    scanf("%d%d", &n, &m);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++)
            scanf("%d", &A[i][j]);
    }
    for(int i = 0;i < n;i++){
        int cur = 0;
        for(int j = 0;j < m;j++){
            cur += A[i][j];
            pref[i][j] = cur;
            if(i) pref[i][j] += pref[i - 1][j];
        }
    }
    for(int i1 = 0;i1 < n;i1++){
        for(int i2 = i1;i2 < n;i2++){
            for(int j1 = 0;j1 < m;j1++){
                for(int j2 = j1;j2 < m;j2++){
                    cost[i1][i2][j1][j2] = calc_cost(i1, i2, j1, j2);
                }
            }
        }
    }
    printf("%d\n", f(0, n - 1, 0, m - 1));
}

Compilation message

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 31232 KB Output is correct
2 Correct 19 ms 31232 KB Output is correct
3 Correct 19 ms 31232 KB Output is correct
4 Correct 19 ms 31232 KB Output is correct
5 Correct 19 ms 31352 KB Output is correct
6 Correct 20 ms 31488 KB Output is correct
7 Correct 20 ms 31872 KB Output is correct
8 Correct 27 ms 32640 KB Output is correct
9 Correct 33 ms 33792 KB Output is correct
10 Correct 41 ms 34176 KB Output is correct
11 Correct 37 ms 33280 KB Output is correct
12 Correct 89 ms 36728 KB Output is correct
13 Correct 126 ms 38144 KB Output is correct
14 Correct 49 ms 33792 KB Output is correct
15 Correct 154 ms 39032 KB Output is correct
16 Correct 33 ms 35968 KB Output is correct
17 Correct 70 ms 38656 KB Output is correct
18 Correct 346 ms 43648 KB Output is correct
19 Correct 577 ms 44376 KB Output is correct
20 Correct 657 ms 45512 KB Output is correct