oj.uz

Submission #1104496

# Submission time Handle Problem Language Result Execution time Memory
1104496 2024-10-24T00:55:27 Z hickwhither Zemljište (COCI22_zemljiste) C++17
0 / 70
 1 ms 336 KB 
#include <iostream>
#include <algorithm>

using namespace std;

#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] = s[i-1]+ps[i][r] - ps[i][l-1];

        // a <= s[i]-s[j] <= b
        // s[i]-a <= s[j] <= s[i]-b
        // cout << l << ' ' << r << '\n';
        for(int i=1; i<=n; ++i){
            int c = lower_bound(s+1,s+i,s[i]-a) - s,
                d = upper_bound(s+1,s+i,s[i]-b) - s;
            // cout << c << ' ' << d << ' ' <<  i << " ~ " << s[i] << ' ' << s[i]-a << ' ' << s[i]-b << '\n';
            // cout << s[i] << "~~\n";
            // if(c!=d){
            //     cout << b-a;
            //     return 0;
            // }
            minimize(ans, toQ(s[i]-s[c]));
            minimize(ans, toQ(s[i]-s[d]));
            
            minimize(ans, toQ(s[i]-s[c-1]));
            minimize(ans, toQ(s[i]-s[d-1]));
            if(c<i)minimize(ans, toQ(s[i]-s[c+1]));
            if(d<i)minimize(ans, toQ(s[i]-s[d+1]));
        }
    }
    cout << ans;
    

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -