Submission #1272932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272932		ken7236	Zemljište (COCI22_zemljiste)	C++20	30 / 70	2095 ms	4348 KiB

Main

#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];
        }
    }
    for(int a=1; a<=r; a++)
    {
        for(int b=1; b<=s; b++)
        {
            //cout<<pref[a][b]<<" ";
        }
        //cout<<endl;
    }
    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]<<" ";
            }
            vector<long long> pref1(s+1, 0);
            for (int c = 1; c <= s; c++) 
            {
                pref1[c] = pref1[c-1] + temp[c];
            }
            //cout<<endl;
            set<long long> seen;
            seen.insert(0);
            for (int c = 1; c <= s; c++) 
            {
                long long cur = pref1[c];
                long long low = cur - q;   // smaller
                long long high = cur - p;  // larger

                auto it = seen.lower_bound(low);

                // if any prefix in [low, high], cost is minimal = q - p
                if (it != seen.end() && *it <= high) {
                    ans = min(ans, (long long)(q - p));
                } else {
                    if (it != seen.end()) {
                        long long cand = cur - *it;
                        ans = min(ans, llabs(cand - p) + llabs(cand - q));
                    }
                    if (it != seen.begin()) {
                        auto it2 = prev(it);
                        long long cand = cur - *it2;
                        ans = min(ans, llabs(cand - p) + llabs(cand - q));
                    }
                }
                seen.insert(cur);
            }
        }
    }
    cout<<ans<<endl;
}

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