oj.uz

Submission #704887

# Submission time Handle Problem Language Result Execution time Memory
704887 2023-03-03T06:24:59 Z Cookie197 Zemljište (COCI22_zemljiste) C++17
10 / 70
 58 ms 1120 KB 
#pragma GCC optimize("O4,unroll-loops")
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define endl "\n"
#define mp make_pair
#define out(x) cout << #x << " = " << x << endl

int n,m;
ll arr[505][505],pre[505][505],a,b;

signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>m>>a>>b;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) cin>>arr[i][j], pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + arr[i][j];
    }

    ll ans = 1e18;
    for (int i=1;i<=n;i++) for (int j=i;j<=n;j++){
        multiset<ll> ms; ms.insert(2e18); ms.insert(-2e18); ms.insert(0);
        ll sum = 0;
        for (int k=1;k<=m;k++) sum += pre[j][k] - pre[j][k-1] - pre[i-1][k] + pre[i-1][k-1], ms.insert(sum);
        cout<<endl;
        for (ll u:ms){
            ll x = *ms.lower_bound(u+a);
            ans = min(ans, abs((x-u) - a) + abs((x-u) - b));
            x = *(--ms.lower_bound(u+b+1));
            ans = min(ans, abs((x-u) - a) + abs((x-u) - b));
        }
    }
    cout<<ans<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 17 ms 852 KB Output is correct
11 Correct 51 ms 1120 KB Output is correct
12 Incorrect 58 ms 1108 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 17 ms 852 KB Output is correct
11 Correct 51 ms 1120 KB Output is correct
12 Incorrect 58 ms 1108 KB Output isn't correct
13 Halted 0 ms 0 KB -