# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
292667 | BThero | Cultivation (JOI17_cultivation) | C++17 | 59 ms | 1920 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
pii arr[305];
int pref[305][305];
int cnt[305][305];
int R, C, n;
void solve() {
scanf("%d %d", &R, &C);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x, y;
scanf("%d %d", &x, &y);
arr[i] = mp(x, y);
}
int ans = R + C;
for (int dx = 0; dx <= R - 1; ++dx) {
for (int dy = 0; dy <= C - 1; ++dy) {
for (int i = 1; i <= 2 * R; ++i) {
for (int j = 1; j <= 2 * C; ++j) {
cnt[i][j] = 0;
}
}
for (int i = 1; i <= n; ++i) {
int x1 = arr[i].fi;
int x2 = x1 + dx;
int y1 = arr[i].se;
int y2 = y1 + dy;
++cnt[x1][y1];
--cnt[x2 + 1][y1];
--cnt[x1][y2 + 1];
++cnt[x2 + 1][y2 + 1];
}
for (int i = 1; i <= 2 * R; ++i) {
for (int j = 1; j <= 2 * C; ++j) {
cnt[i][j] += cnt[i - 1][j];
cnt[i][j] += cnt[i][j - 1];
cnt[i][j] -= cnt[i - 1][j - 1];
}
}
for (int i = 1; i <= 2 * R; ++i) {
for (int j = 1; j <= 2 * C; ++j) {
pref[i][j] = !!cnt[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
}
for (int x1 = 1; x1 <= dx + 1; ++x1) {
for (int y1 = 1; y1 <= dy + 1; ++y1) {
int x2 = x1 + R - 1;
int y2 = y1 + C - 1;
int tot = pref[x2][y2];
tot -= pref[x1 - 1][y2];
tot -= pref[x2][y1 - 1];
tot += pref[x1 - 1][y1 - 1];
if (tot == R * C) {
ans = min(ans, dx + dy);
}
}
}
}
}
printf("%d\n", ans);
}
int main() {
int tt = 1;
while (tt--) {
solve();
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |