Submission #572688

#	Time	Username	Problem	Language	Result	Execution time	Memory
572688		tamthegod	Zemljište (COCI22_zemljiste)	C++17	30 / 70	2076 ms	4192 KiB

Main

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<string.h>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<cstdio>
#include<bitset>
#include<chrono>
#include<random>
#include<ext/rope>
/* ordered_set
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 500 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int r, s, a, b;
int c[maxN][maxN];
int sum[maxN][maxN];
void ReadInput()
{
    cin >> r >> s >> a >> b;
    for(int i=1; i<=r; i++)
        for(int j=1; j<=s; j++)
        {
            cin >> c[i][j];
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + c[i][j];
        }
}
int get(int x, int y, int u, int v)
{
    return sum[u][v] - sum[x - 1][v] - sum[u][y - 1] + sum[x - 1][y - 1];
}
void Solve()
{
    int res = oo;
    if(a > b) swap(a, b);
    for(int i=1; i<=r; i++)
        for(int j=i; j<=r; j++)
        {
            set<int> S;
            S.insert(0);
            for(int k=1; k<=s; k++)
            {
                int val = get(i, 1, j, k);
                auto it = S.upper_bound(val - a);
                auto it1 = it;
                if(it1 != S.begin()) it1--;
                if(it != S.end()) res = min(res, abs(val - *it - a) + abs(val - *it - b));
                if(it1 != S.end()) res = min(res, abs(val - *it1 - a) + abs(val - *it1 - b));
                S.insert(val);
            }
        }
    cout << res;
}
int32_t main()
{
 //   freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

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