Submission #1137826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137826		jackofall718	Zemljište (COCI22_zemljiste)	C++20	70 / 70	244 ms	4400 KiB

Main

//COCI 2021-22 ROUND 6 PROBLEM 2
#include <bits/stdc++.h>
#define ll long long int
#define endl '\n'
using namespace std;

const ll INF = 0x3f3f3f3f3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll r, s, a, b;
    cin >> r >> s >> a >> b;
    if (a > b) swap(a, b);

    vector<vector<ll>> grid(r + 1, vector<ll>(s + 1));
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= s; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<ll>> pref(r + 1, vector<ll>(s + 1, 0));
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= s; j++) {
            pref[i][j] = pref[i - 1][j] + grid[i][j];
        }
    }

    ll ans = INF;

    
    for (int top = 1; top <= r; top++) {
        for (int bot = top; bot <= r; bot++) {
            vector<ll> colSum(s + 1);
            for (int j = 1; j <= s; j++) {
                colSum[j] = pref[bot][j] - pref[top-1][j];
            }

            
            ll tempSum = 0;
            int left = 1;
            for (int right = 1; right <= s; right++) {
                tempSum += colSum[right];

               
                while (left <= right && tempSum - colSum[left] >= a) {
                    tempSum -= colSum[left];
                    left++;
                }

                
                ll currentDist = abs(tempSum - a) + abs(tempSum - b);
                ans = min(ans, currentDist);
                // The error in my original code was in the 2 pointer impl. I did not contract the window every time like is done below to try and find better ans
                // also I didnt do tempSum - colSum[left] >= a
                if (left < right) {
                    ll adjustedSum = tempSum - colSum[left];
                    ll adjustedDist = abs(adjustedSum - a) + abs(adjustedSum - b);
                    ans = min(ans, adjustedDist);
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}

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