Submission #1272182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272182		ttoopp	Zemljište (COCI22_zemljiste)	C++20	0 / 70	48 ms	110492 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll r, s, a, b, maxi;
ll arr[103][103], ans=1e18;
ll horizontal[103][103], vertikal[103][103];
bool vis[103][103][103][103];

ll count(ll x){
    return abs(a-x)+abs(b-x);
}

void search(int x, int y, int i, int j, ll sum){
    //cout  <<x<<" "<<y<<" "<< i <<" "<<j<<endl;
    //cnt++;
    ans=min(ans,  abs(a-sum)+abs(b-sum));
    if(sum>maxi){
        ll one=sum-(horizontal[x][j]-horizontal[x][y-1]);
        if(x+1<=i && !vis[x+1][y][i][j])search(x+1, y, i, j, one);
        ll two=sum-(vertikal[i][y]-vertikal[x-1][y]);
        if(y+1<=j && ! vis[x][y+1][i][j])search(x, y+1, i, j, two);
        return;
    }
    if(i+1<=r){
        ll rep= sum+horizontal[i+1][j]-horizontal[i+1][y-1];
        if(!vis[x][y][i+1][j]){
            vis[x][y][i+1][j]=true;
            search(x, y, i+1, j, rep);
        }
    }
    if(j+1<=s){
        ll rep= sum+vertikal[i][j+1]-vertikal[x-1][j+1];
        if(!vis[x][y][i][j+1]){
            vis[x][y][i][j+1]=true;
            search(x, y, i, j+1, rep);
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(vis, 0, sizeof(vis));
    cin >> r >> s >> a >> b;
    maxi=max(a, b);
    for(int i=1; i<=r; i++){
        for(int j=1; j<=s; j++){
            cin >> arr[i][j];
        }
    }

    for(int i=1; i<=r; i++){
        horizontal[i][0]=0;
        for(int j=1; j<=s; j++){
            horizontal[i][j]=horizontal[i][j-1]+arr[i][j];
        }
    }
    for(int j=1; j<=s; j++){
        vertikal[0][j]=0;
        for(int i=1; i<=r; i++){
            vertikal[i][j]=vertikal[i-1][j]+arr[i][j];
        }
    }
    search(1,1,1,1, arr[1][1]);
    cout <<ans<<endl;
}

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