Submission #644391

#	Time	Username	Problem	Language	Result	Execution time	Memory
644391		Iwanttobreakfree	Zemljište (COCI22_zemljiste)	C++17	70 / 70	237 ms	4780 KiB

Main

#include <iostream>
#include <vector>

using namespace std;

#define int long long

signed main() {
    int r, s, a, b;
    cin >> r >> s >> a >> b;
    if (b > a) swap (a, b);
    vector<vector<int>> grid (r+1,vector<int> (s+1));
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < s; ++j) {
            int x;
            cin >> x;
            grid[i+1][j+1]=grid[i+1][j]+grid[i][j+1]-grid[i][j]+x;
        }
    }
    int sol = 1e18;
    for (int i = 1; i <= r; ++i) {
        for (int j = 0; j < i; ++j) {
            int l = 0, r = 1;
            while (r <= s) {
                while (l < r and grid[i][r]-grid[j][r]-grid[i][l]+grid[j][l] > b) {
                    int val = grid[i][r]-grid[j][r]-grid[i][l]+grid[j][l];
                    sol = min (sol, abs (a-val)+abs (b-val));
                    ++l;
                }
                if (l < r) {
                    int val = grid[i][r]-grid[j][r]-grid[i][l]+grid[j][l];
                    //cout << grid[j][l+1] << ' ';
                    sol = min (sol, abs (a-val)+abs (b-val));
                }
                ++r;
            }
        }
    }
    cout << sol << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40