oj.uz

Submission #659352

# Submission time Handle Problem Language Result Execution time Memory
659352 2022-11-17T14:23:05 Z Trisanu_Das Raisins (IOI09_raisins) C++17
0 / 100
 5000 ms 10324 KB 
#include <bits/stdc++.h>
using namespace std;
 
int dp[51][51][51][51], a[51][51], pref[51][51];
 
int main() {
    int n, m; cin >> n >> m;
    for(int i = 1; i < n + 1; i++) for(int j = 1; j < m + 1; j++) {
        cin >> a[i][j];
        pref[i][j] = pref[i - 1][j] + pref[i][j - 1] + a[i][j] - pref[i - 1][j - 1];
    }
 
    for(int i = 1; i < n + 1;) for(int j = 1; j < m + 1; j++) for(int k = 1; k < n - i + 2; k++) for(int l = 1; l < m - j + 2; l++) {
        if (i == 1 && j == 1) continue;
        int mn = INT_MAX;
        for(int x = 1; x < i; x++) mn = min(mn, dp[k][l][x][j] + dp[k + x][l][i - x][j]);
        for(int x = 1; x < j; x++) mn = min(mn, dp[k][l][i][x] + dp[k][l + x][i][j - x]);
        dp[k][l][i][j] = mn + pref[k + i - 1][l + j - 1] + pref[k - 1][l - 1] - pref[k + i - 1][l - 1] - pref[k - 1][l + j - 1];
    }
 
    cout << dp[1][1][n][m];
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5092 ms 212 KB Time limit exceeded
2 Execution timed out 5041 ms 212 KB Time limit exceeded
3 Execution timed out 5057 ms 340 KB Time limit exceeded
4 Execution timed out 5060 ms 340 KB Time limit exceeded
5 Execution timed out 5046 ms 340 KB Time limit exceeded
6 Execution timed out 5054 ms 688 KB Time limit exceeded
7 Execution timed out 5077 ms 724 KB Time limit exceeded
8 Execution timed out 5090 ms 1876 KB Time limit exceeded
9 Execution timed out 5052 ms 2260 KB Time limit exceeded
10 Execution timed out 5083 ms 2772 KB Time limit exceeded
11 Execution timed out 5088 ms 2516 KB Time limit exceeded
12 Execution timed out 5074 ms 4180 KB Time limit exceeded
13 Execution timed out 5094 ms 5076 KB Time limit exceeded
14 Execution timed out 5081 ms 3028 KB Time limit exceeded
15 Execution timed out 5094 ms 5588 KB Time limit exceeded
16 Execution timed out 5063 ms 1876 KB Time limit exceeded
17 Execution timed out 5022 ms 3668 KB Time limit exceeded
18 Execution timed out 5067 ms 8020 KB Time limit exceeded
19 Execution timed out 5052 ms 9788 KB Time limit exceeded
20 Execution timed out 5092 ms 10324 KB Time limit exceeded