Submission #1266594

#TimeUsernameProblemLanguageResultExecution timeMemory
1266594canhnam357Zemljište (COCI22_zemljiste)C++20
70 / 70
421 ms2420 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; long long L, R; cin >> n >> m >> L >> R; if (L > R) swap(L, R); // min such >= l and <= r // max <= l // min >= r vector<vector<long long>> a(n, vector<long long>(m)); for (auto &x : a) for (long long &i : x) cin >> i; for (int i = 1; i < n; i++) { for (int j = 0; j < m; j++) { a[i][j] += a[i - 1][j]; } } auto get = [&](int i, int l, int r) { return a[r][i] - (l ? a[l - 1][i] : 0LL); }; const long long inf = 1e18; long long y = -inf, z = inf; { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { long long sum = 0; for (int l = 0, r = 0; r < m; r++) { sum += get(r, i, j); while (sum - get(l, i, j) >= L) { sum -= get(l, i, j); l++; } if (sum >= L && sum <= R) { cout << R - L << '\n'; return 0; } } } } } { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { long long sum = 0; for (int l = 0, r = 0; r < m; r++) { sum += get(r, i, j); while (sum > L) { sum -= get(l, i, j); l++; } y = max(y, sum); } } } } { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { long long sum = 0; for (int l = 0, r = 0; r < m; r++) { sum += get(r, i, j); while (sum - get(l, i, j) >= R) { sum -= get(l, i, j); l++; } if (sum >= R) z = min(z, sum); } } } } if (y == 0) y = -inf; cout << min(2 * z - L - R, L + R - 2 * y); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...