Submission #881859

#	Time	Username	Problem	Language	Result	Execution time	Memory
881859		Matjaz	Raisins (IOI09_raisins)	C++14	100 / 100	145 ms	24924 KiB

raisins

//
//  IOI2009Salesman.cpp
//
//
//  Created by Matjaz Leonardis on 11/11/2023.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>

using namespace std;


int N,M;
int R[55][55];
int INF = (1<<31) - 1;
int dp[50][50][50][50];
int S[55][55];


int sum(int x0, int y0, int x1, int y1){
    
    if (x0 == 0 && y0 == 0) return S[x1][y1];
    
    if (x0 == 0) return S[x1][y1] - S[x1][y0 -1];
    if (y0 == 0) return S[x1][y1] - S[x0 - 1][y1];
    
    
    return S[x1][y1] - S[x0-1][y1] - S[x1][y0 -1] + S[x0-1][y0-1];
}

int solve(int x0, int y0, int x1, int y1){
    if (x0 == x1 && y0 == y1) return 0;
    if (dp[x0][y0][x1][y1] != -1) return dp[x0][y0][x1][y1];
    
    int best = INF;
    for (int xn=x0;xn<x1;xn++){
        int tmp = solve(x0, y0, xn, y1) + solve(xn+1, y0, x1, y1);
        best = min(best, tmp);
    }
    
    for (int yn=y0;yn<y1;yn++){
        int tmp = solve(x0, y0, x1, yn) + solve(x0, yn + 1, x1, y1);
        best = min(best, tmp);
    }
    
    return dp[x0][y0][x1][y1] = best + sum(x0, y0, x1, y1);
    
}

int main(){
    memset(dp, -1, sizeof(dp));
    
    cin >> N >> M;
    for (int i=0;i<N;i++){
        for (int j=0;j<M;j++) cin >> R[i][j];
    }
    
    S[0][0] = R[0][0];
    for (int i=1;i<M;i++) S[0][i] = S[0][i-1] + R[0][i];
    for (int i=1;i<N;i++) S[i][0] = S[i-1][0] + R[i][0];
    for (int i=1;i<N;i++){
        for (int j=1;j<M;j++) S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + R[i][j];
    }
    
    cout << solve(0,0,N-1,M-1) << endl;
    return 0;
}

Compilation message (stderr)

raisins.cpp:19:19: warning: integer overflow in expression of type 'int' results in '2147483647' [-Woverflow]
   19 | int INF = (1<<31) - 1;
      |           ~~~~~~~~^~~

• Subtask 1: 100 / 100