Submission #1272935

#TimeUsernameProblemLanguageResultExecution timeMemory
1272935ken7236Zemljište (COCI22_zemljiste)C++20
70 / 70
196 ms4548 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int r, s, pp, qq;
    cin>>r>>s>>pp>>qq;
    int p = min(pp,qq);
    int q = max(pp,qq);
    int ans = INT_MAX;
    vector<vector<int> > arr(r+1, vector<int>(s+1));
    for(int a=1; a<=r; a++)
    {
        for(int b=1; b<=s; b++)
        {
            cin>>arr[a][b];
            ans = min(ans, abs(p - arr[a][b]) + abs(q - arr[a][b]));
        }
    }
    vector<vector<int> > pref(r+1, vector<int>(s+1, 0));
    for(int a=1; a<=s; a++)
    {
        for(int b=1; b<=r; b++)
        {
            pref[b][a] = pref[b-1][a] + arr[b][a];
        }
    }
    bool done = false;
    for(int a=1; a<=r; a++)
    {
        for(int b=a; b<=r; b++)
        {
            //cout<<a<<" "<<b<<endl;
            vector<int> temp(s+2, 0);
            for(int c=1; c<=s; c++)
            {
                temp[c] = pref[b][c] - pref[a-1][c];
                //cout<<temp[c]<<" ";
            }
            int left = 1;
            long long cur = 0;
            for (int right = 1; right <= s; ++right) {
                cur += temp[right];

                // any window with sum > q: evaluate it (above interval)
                while (cur > q && left <= right) {
                    int cand = cur;
                    ans = min(ans, (int)(llabs(cand - p) + llabs(cand - q)));
                    if (ans == q - p) { done = true; break; }
                    cur -= temp[left++];
                }
                if (done) break;

                // current window sum <= q (if window non-empty)
                if (left <= right) {
                    int cand2 = cur; // <= q
                    ans = min(ans, (int)(llabs(cand2 - p) + llabs(cand2 - q)));
                    if (ans == q - p) { done = true; break; }
                }
            }
        }
    }
    cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...