oj.uz

Submission #881857

# Submission time Handle Problem Language Result Execution time Memory
881857 2023-12-02T05:19:44 Z Matjaz Raisins (IOI09_raisins) C++14
0 / 100
 155 ms 24940 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(){
    cout << INF << endl;
    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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 24664 KB Output isn't correct
2 Incorrect 3 ms 24664 KB Output isn't correct
3 Incorrect 3 ms 24668 KB Output isn't correct
4 Incorrect 3 ms 24668 KB Output isn't correct
5 Incorrect 3 ms 24920 KB Output isn't correct
6 Incorrect 4 ms 24668 KB Output isn't correct
7 Incorrect 4 ms 24912 KB Output isn't correct
8 Incorrect 6 ms 24668 KB Output isn't correct
9 Incorrect 7 ms 24924 KB Output isn't correct
10 Incorrect 9 ms 24924 KB Output isn't correct
11 Incorrect 13 ms 24924 KB Output isn't correct
12 Incorrect 19 ms 24924 KB Output isn't correct
13 Incorrect 42 ms 24696 KB Output isn't correct
14 Incorrect 10 ms 24664 KB Output isn't correct
15 Incorrect 32 ms 24940 KB Output isn't correct
16 Incorrect 7 ms 24924 KB Output isn't correct
17 Incorrect 15 ms 24920 KB Output isn't correct
18 Incorrect 79 ms 24924 KB Output isn't correct
19 Incorrect 135 ms 24924 KB Output isn't correct
20 Incorrect 155 ms 24924 KB Output isn't correct