oj.uz

Submission #881859

# Submission time Handle Problem Language Result Execution time Memory
881859 2023-12-02T05:20:52 Z Matjaz Raisins (IOI09_raisins) C++14
100 / 100
 145 ms 24924 KB 
//
//  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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24668 KB Output is correct
2 Correct 4 ms 24668 KB Output is correct
3 Correct 4 ms 24668 KB Output is correct
4 Correct 4 ms 24668 KB Output is correct
5 Correct 4 ms 24668 KB Output is correct
6 Correct 5 ms 24668 KB Output is correct
7 Correct 5 ms 24668 KB Output is correct
8 Correct 5 ms 24668 KB Output is correct
9 Correct 7 ms 24908 KB Output is correct
10 Correct 10 ms 24924 KB Output is correct
11 Correct 10 ms 24668 KB Output is correct
12 Correct 20 ms 24924 KB Output is correct
13 Correct 32 ms 24924 KB Output is correct
14 Correct 10 ms 24916 KB Output is correct
15 Correct 32 ms 24900 KB Output is correct
16 Correct 7 ms 24916 KB Output is correct
17 Correct 16 ms 24920 KB Output is correct
18 Correct 78 ms 24900 KB Output is correct
19 Correct 125 ms 24668 KB Output is correct
20 Correct 145 ms 24924 KB Output is correct