| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 59921 |
2018-07-23T10:13:11 Z |
ainta(#1720) |
Cultivation (JOI17_cultivation) |
C++11 |
|
3 ms |
492 KB |
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
long long W, H, n, S[610][610], M[610][610], U[610][610];
set<long long>SX, SY;
long long YY[1000000];
struct point {
long long x, y;
}w[330];
struct Rect {
long long x1, y1, x2, y2;
}R[330];
long long X[610], Y[610];
bool Pos(long long dx, long long dy) {
long long i, j;
long long CX = 0, CY = 0;
for (i = 1; i <= n; i++) {
X[CX++] = w[i].x;
X[CX++] = w[i].x + dx + 1;
Y[CY++] = w[i].y;
Y[CY++] = w[i].y + dy + 1;
}
sort(X, X + CX);
sort(Y, Y + CY);
CX = unique(X, X + CX) - X;
CY = unique(Y, Y + CY) - Y;
for (i = 0; i <= CX; i++)for (j = 0; j <= CY; j++)S[i][j] = 0;
for (i = 1; i <= n; i++) {
R[i].x1 = lower_bound(X, X + CX, w[i].x) - X;
R[i].x2 = lower_bound(X, X + CX, w[i].x + dx + 1) - X;
R[i].y1 = lower_bound(Y, Y + CY, w[i].y) - Y;
R[i].y2 = lower_bound(Y, Y + CY, w[i].y + dy + 1) - Y;
S[R[i].x1][R[i].y1]++;
S[R[i].x1][R[i].y2]--;
S[R[i].x2][R[i].y1]--;
S[R[i].x2][R[i].y2]++;
}
for (i = 0; i < CX; i++)for (j = 1; j < CY; j++)S[i][j] += S[i][j - 1];
for (i = 1; i < CX; i++)for (j = 0; j < CY; j++)S[i][j] += S[i -1][j];
for (i = 0; i < CX - 1; i++) {
for (j = 0; j < CY - 1; j++) {
if (!S[i][j])M[i][j] = 0;
else if (j == 0)M[i][j] = Y[j + 1] - Y[j];
else M[i][j] = Y[j + 1] - Y[j] + M[i][j - 1];
if (M[i][j] >= H) {
if (i == 0)U[i][j] = X[i + 1] - X[i];
else U[i][j] = U[i - 1][j] + X[i + 1] - X[i];
if (U[i][j] >= W)return true;
}
else {
U[i][j] = 0;
}
}
}
return false;
}
int main() {
freopen("input.txt", "r", stdin);
long long i, j, CY = 0;
scanf("%lld%lld%lld", &W, &H, &n);
for (i = 1; i <= n; i++) {
scanf("%lld%lld", &w[i].x, &w[i].y);
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (w[i].x <= w[j].x) {
if(w[j].x>w[i].x)SX.insert(w[j].x - w[i].x - 1);
SX.insert(w[i].x - 1 + W - w[j].x);
}
SX.insert(w[j].x - w[i].x + W);
if (w[i].y <= w[j].y) {
if (w[j].y>w[i].y)SY.insert(w[j].y - w[i].y - 1);
SY.insert(w[i].y - 1 + H - w[j].y);
}
SY.insert(w[j].y - w[i].y + H);
}
}
long long res = 3e9;
for (auto &y : SY) {
YY[CY++] = y;
}
for (auto &x : SX) {
long long b = 0, e = CY - 1, r = CY;
while (b <= e) {
long long mid = (b + e) >> 1;
if (Pos(x, YY[mid])) {
r = mid;
e = mid - 1;
}
else b = mid + 1;
}
if (r != CY) {
res = min(res, x + YY[r]);
}
}
printf("%lld\n", res);
return 0;
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:59:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &W, &H, &n);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &w[i].x, &w[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
