제출 #1104531

#제출 시각아이디문제언어결과실행 시간메모리
1104531hickwhitherZemljište (COCI22_zemljiste)C++17
0 / 70
1 ms336 KiB
#include <iostream>
#include <algorithm>

using namespace std;

#define int int64_t

#define minimize(a,b) a=min(a,b)

int64_t ans = 1e18;
int n, m, a, b;
int x;
int64_t ps[503][503];
int64_t s[503];

int64_t toQ(int64_t x){
    // cout << x << '\n';
    return abs(x-a) + abs(x-b);
}

signed main()
{
    cin.tie(0) -> sync_with_stdio(0);
    // if(fopen("DAUTU.inp", "r")){
    //     freopen("DAUTU.inp", "r",stdin);
    //     freopen("DAUTU.out", "w",stdout);
    // }
    
    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 >> x;
        ps[i][j] = ps[i][j-1]+x;
    }
    // cout << ps[3][1] << '\n';

    for(int l=1; l<=n; ++l)
    for(int r=l; r<=m; ++r){
        for(int i=1; i<=n; ++i) s[i] = ps[i][r]-ps[i][l-1];

        int64_t sum=0;
        // cout << l << ' ' << r << "*\n";
        for(int i=1, j=1; i<=n; ++i){
            sum += s[i];
            // cout << sum << ' ';
            while(sum>b){
                if(a<=sum && sum<=b){
                    cout << b-a;
                    return 0;
                }
                minimize(ans, toQ(sum));
                sum-=s[j++];
            }
            minimize(ans, toQ(sum));
        }
        // cout << '\n';

    }
    cout << ans;
    

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...