oj.uz

Submission #663386

# Submission time Handle Problem Language Result Execution time Memory
663386 2022-11-26T21:12:34 Z esomer Raisins (IOI09_raisins) C++17
100 / 100
 2281 ms 29384 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

const int MOD = 1e9 + 7;

ll solve(vector<vector<int>>& table){
    int n = table.size();
    int m = table[0].size();
    ll ans = 0;
    function<void(int, int, int, int)> DFS = [&](int lx, int rx, int ly, int ry){
        cout << "Lx "<< lx << " rx "<< rx << " ly "<< ly << " ry "<< ry << " ans " << ans << endl;
        if(rx - lx == 0 && ry - ly == 0) return;
        int mn = 1e9;
        pair<int, int> cut;
        for(int i = ly; i <= ry; i++){
            for(int j = lx; j <= rx; j++) ans += table[i][j];
        }
        for(int i = ly; i < ry; i++){
            int up = 0;
            int down = 0;
            for(int j = ly; j <= i; j++){
                for(int q = lx; q <= rx; q++) up += table[j][q];
            }
            for(int j = i + 1; j <= ry; j++){
                for(int q = lx; q <= rx; q++) down += table[j][q];
            }
            if(abs(up - down) < mn){
                mn = abs(up - down);
                cut = {i, 0};
            }
        }
        for(int i = lx; i < rx; i++){
            int left = 0;
            int right = 0;
            for(int j = lx; j <= i; j++){
                for(int q = ly; q <= ry; q++) left += table[q][j];
            }
            for(int j = i + 1; j <= rx; j++){
                for(int q = ly; q <= ry; q++) right += table[q][j];
            }
            if(abs(left - right) < mn){
                mn = abs(left - right);
                cut = {i, 1};
            }
        }
        cout << "Cut "<< cut.first << " " << cut.second << " mn "<< mn << endl;
        if(cut.second == 0) {DFS(lx, rx, ly, cut.first); DFS(lx, rx, cut.first + 1, ry);}
        else {DFS(lx, cut.first, ly, ry); DFS(cut.first + 1, rx, ly, ry);}
    };
    DFS(0, m - 1, 0, n - 1);
    return ans;
}

mt19937 gen(time(0));

ll solve2(vector<vector<int>>& table){
    int n = table.size();
    int m = table[0].size();
    vector<vector<vector<vector<int>>>> dp(m, vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(n, -1))));
    function<ll(int, int, int, int)> DFS = [&](int lx, int rx, int ly, int ry){
        if(rx - lx == 0 && ry - ly == 0) return 0;
        if(dp[lx][rx][ly][ry] == -1){
            ll ans = 1e18;
            for(int i = ly; i < ry; i++){
                ans = min(ans, DFS(lx, rx, ly, i) + DFS(lx, rx, i + 1, ry));
            }
            for(int i = lx; i < rx; i++){
                ans = min(ans, DFS(lx, i, ly, ry) + DFS(i + 1, rx, ly, ry));
            }
            for(int i = ly; i <= ry; i++){
                for(int j = lx; j <= rx; j++) ans += table[i][j];
            }
            dp[lx][rx][ly][ry] = ans;
            return (int)ans;
        }else return dp[lx][rx][ly][ry];
    };
    return DFS(0, m - 1, 0, n - 1);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    //int tt; cin >> tt;
    string s = "RUN";
    if(s == "RUN"){
        int n, m; cin >> n >> m;
        vector<vector<int>> table(n, vector<int>(m));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++) cin >> table[i][j];
        }
        cout << solve2(table)<< endl;
        return 0;
    }
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        int n = gen() % 1 + 50;
        int m = gen() % 1 + 50;
        vector<vector<int>> table(n, vector<int>(m));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++) table[i][j] = gen() % 3 + 1;
        }
        //ll ans1 = solve(table);
        /*if(ans1 != ans2){
            cout << n << " "<< m << endl;
            for(auto v : table){
                for(int x: v) cout << x << " ";
                cout << endl;
            }
            cout << "Ans1 "<< ans1 << " ans2 "<< ans2 << endl;
            return 0;
        }*/
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 19 ms 1368 KB Output is correct
9 Correct 34 ms 1964 KB Output is correct
10 Correct 46 ms 2516 KB Output is correct
11 Correct 47 ms 2388 KB Output is correct
12 Correct 181 ms 5588 KB Output is correct
13 Correct 271 ms 8276 KB Output is correct
14 Correct 75 ms 3288 KB Output is correct
15 Correct 355 ms 9256 KB Output is correct
16 Correct 21 ms 1236 KB Output is correct
17 Correct 117 ms 4052 KB Output is correct
18 Correct 1020 ms 18772 KB Output is correct
19 Correct 1928 ms 27140 KB Output is correct
20 Correct 2281 ms 29384 KB Output is correct