Submission #221799

#	Time	Username	Problem	Language	Result	Execution time	Memory
221799		patrikpavic2	Raisins (IOI09_raisins)	C++17	100 / 100	657 ms	45512 KiB

raisins

/**
* 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 (stderr)

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 / 100