제출 #1272162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272162		ttoopp	Zemljište (COCI22_zemljiste)	C++20	0 / 70	2093 ms	568 KiB

Main

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

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

void search(int x, int y, int i, int j, ll sum){
    ans=min(ans, count(sum));
    if(sum>maxi){
        ll one=sum-(horizontal[x][j]-horizontal[x][y-1]);
        search(x+1, y, i, j, one);
        ll two=sum-(vertikal[i][y]-vertikal[x-1][y]);
        search(x, y+1, i, j, two);
        return;
    }
    if(i+1<=r){
        ll rep= sum+horizontal[i+1][j]-horizontal[i+1][y-1];
        search(x, y, i+1, j, rep);
    }
    if(j+1<=s){
        ll rep= sum+vertikal[i][j+1]-vertikal[x-1][j+1];
        search(x, y, i, j+1, rep);
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    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