Submission #704943

#	Time	Username	Problem	Language	Result	Execution time	Memory
704943		Cookie197	Zemljište (COCI22_zemljiste)	C++17	70 / 70	382 ms	4428 KiB

Main

#pragma GCC optimize("O4,unroll-loops")
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define endl "\n"
#define mp make_pair
#define out(x) cout << #x << " = " << x << endl

int n,m;
ll arr[505][505],pre[505][505],a,b;

signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m>>a>>b; if (a>b) swap(a,b);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) cin>>arr[i][j], pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + arr[i][j];
    }

    if (n*m <= 10000){
        ll ans = 1e18;
        for (int i=1;i<=n;i++) for (int j=i;j<=n;j++){
            for (int k=1;k<=m;k++) for (int l=k;l<=m;l++){
                ll x = pre[j][l] - pre[j][k-1] - pre[i-1][l] + pre[i-1][k-1];
                ans = min(ans, abs(a-x) + abs(b-x));
            }
        }
        cout<<ans<<endl;
        return 0;
    }

    ll ans = 1e18;
    for (int i=1;i<=n;i++) for (int j=i;j<=n;j++){
        ll tmp[505]; tmp[0] = 0;
        for (int k=1;k<=m;k++) tmp[k] = pre[j][k] - pre[j][k-1] - pre[i-1][k] + pre[i-1][k-1];
        
        int r = 0; ll sum = 0;
        for (int i=1;i<=m;i++){
            while(1){
                ans = min(ans, abs(sum-a) + abs(sum-b));
                if (r==m) break;
                if (sum >= a) break;
                r++; sum += tmp[r];
            }
            ans = min(ans, abs(sum-a) + abs(sum-b));
            sum -= tmp[i];
        }
    }
    cout<<ans<<endl;
}

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