Submission #704852

#	Time	Username	Problem	Language	Result	Execution time	Memory
704852		browntoad	Zemljište (COCI22_zemljiste)	C++14	70 / 70	544 ms	6728 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i=(n)-1; i>=0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

const ll maxn = 505;
const ll inf = (1ll<<60);

int r, c, a, b;
int arr[maxn][maxn];
int spf[maxn][maxn];
void inp(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>r>>c>>a>>b;
    if (a>b) swap(a, b);
    REP1(i, r){
        REP1(j, c){
            cin>>arr[i][j];
            spf[i][j] = spf[i-1][j] + arr[i][j];
        }
    }
}
int ans = inf;
vector<int> tmp;
int cval = 0;
void check(){
    ans = min(ans, abs(a-cval)+abs(b-cval));
}
void run(){
    int R=0;
    cval = 0;
    check();
    REP(i, c){
        while(R<c && cval < a){
            check();
            cval+=tmp[R];
            R++;
        }
        check();
        cval-=tmp[i];
        check();
    }
}
void solve(){
    REP1(i, r){
        FOR(j, i, r+1){
            tmp.clear();
            REP1(k, c){
                tmp.pb(spf[j][k] - spf[i-1][k]);
            }
            run();
        }
    }
}
signed main(){
    inp();
    solve();
    cout<<ans<<endl;
}

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