Submission #1275023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275023		recp	Zemljište (COCI22_zemljiste)	C++20	70 / 70	304 ms	5376 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long

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

    int r, s, a, b;
    cin >> r >> s >> a >> b;
    if (a > b) swap(a, b);
    int arr[r+1][s+1];
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= s; j++) cin >> arr[i][j];
    }
    vector<vector<ll>> preR(r+1, vector<ll>(s+1, 0)), preC(s+1, vector<ll>(r+1, 0));
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= s; j++) {
            preR[i][j] = preR[i][j-1]+arr[i][j];
        }
    }
    for (int i = 1; i <= s; i++) {
        for (int j = 1; j <= r; j++) {
            preC[i][j] = preC[i][j-1]+arr[j][i];
        }
    }
    ll bot = -1e18, top = 1e18;
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= s; j++) {
            ll lenX = 1, lenYB = r-i+1, lenYT = r-i+1, curB = 0, curT = 0;
            while (lenX+j-1 <= s) {
                curT += preC[j+lenX-1][i+lenYT-1]-preC[j+lenX-1][i-1];
                if (lenYB > 0) curB += preC[j+lenX-1][i+lenYB-1]-preC[j+lenX-1][i-1];
                while (lenYT > 1) {
                    if (curT-(preR[i+lenYT-1][j+lenX-1]-preR[i+lenYT-1][j-1]) >= a) {
                        curT -= preR[i+lenYT-1][j+lenX-1]-preR[i+lenYT-1][j-1];
                        lenYT--;
                    } else {
                        break;
                    }
                }
                while (lenYB > 0) {
                    if  (curB > b) {
                        curB -= preR[i+lenYB-1][j+lenX-1]-preR[i+lenYB-1][j-1];
                        lenYB--;
                    } else {
                        break;
                    }
                }
                lenX++;
                if (curT >= a) top = min(top, curT);
                if (curB <= b) bot = max(bot, curB);
            }
        }
    }
    cout << min(abs(top-a)+abs(top-b), abs(bot-a)+abs(bot-b)) << endl;
    return 0;
}

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