Submission #1261658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261658		shidou26	Zemljište (COCI22_zemljiste)	C++20	70 / 70	410 ms	4396 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << x << "]"

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> bool maximize(T &a, T b) {
    if(a < b) return a = b, true;
    else return false;
}

template<typename T> bool minimize(T &a, T b) {
    if(a > b) return a = b, true;
    else return false;
}

template<typename T1, typename T2> T2 rnd(T1 l, T2 r) {
    return uniform_int_distribution<T2>(l, r)(rng);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;

const int N = 5e2 + 3;

int n, m;
ll a, b;
ll board[N][N];

ll p[N];
ll pre[N][N];

ll get(int l, int r, int u, int v) {
    return pre[u][v] - pre[u][r - 1] - pre[l - 1][v] + pre[l - 1][r - 1];
}

ll get(int l, int r) {
    return p[r] - p[l - 1];
}

void process() {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + board[i][j];
        }
    }

    // one: min num >= a
    // two: min num >= b
    // three: max num <= a

    ll Q = LLONG_MAX, one = LLONG_MAX, two = LLONG_MAX, three = LLONG_MIN;
    for(int l = 1; l <= n; l++) {
        for(int r = l; r <= n; r++) {
            for(int i = 1; i <= m; i++) p[i] = p[i - 1] + get(l, i, r, i);

            for(int i = 1, j1 = 1, j2 = 1, j3 = 1; i <= m; i++) {
                while(j1 < m && get(i, j1) < a) j1++;
                if(get(i, j1) >= a) minimize(one, get(i, j1));

                while(j2 < m && get(i, j2) < b) j2++;
                if(get(i, j2) >= b) minimize(two, get(i, j2));

                while(j3 + 1 <= m && get(i, j3 + 1) <= a) j3++;
                if(get(i, j3) <= a) maximize(three, get(i, j3));
            }

        }
    }

//    cout << dbg(one) << dbg(two) << dbg(three) << endl;
    if(two != LLONG_MAX) minimize(Q, 2LL * two - (a + b));
    if(one != LLONG_MAX && one <= b) minimize(Q, b - a);
    if(three != LLONG_MIN) minimize(Q, (a + b) - 2LL * three);

    cout << Q << endl;
}

void input() {
    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 >> board[i][j];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    #define task "DAUTU"
    if(fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int testcase = 1; // cin >> testcase;
    for(int i = 1; i <= testcase; i++) {
        input();
        process();
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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