| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 163415 | 2019-11-13T08:52:56 Z | iefnah06 | The Kingdom of JOIOI (JOI17_joioi) | C++11 | 260 ms | 93840 KB |
#include <bits/stdc++.h>
using namespace std;
namespace from_kczno1 {
const int ch_top=4e6*11+1e6;
char ch[ch_top],*now_r=ch-1;
#define c (*now_r)
#define gc (*++now_r)
int read()
{
while(gc<'-');
int x=c-'0';
while(gc>='0')x=x*10+c-'0';
return x;
}
#undef gc
#undef c
}
using namespace from_kczno1;
const int INF = 1.1e9;
const int MAXX = 2010;
const int MAXY = 2010;
short X, Y;
int A[MAXX][MAXY];
int gmi, gma;
int mi, ma;
bool is_good(int v) {
int lhi = gmi + v;
int rlo = gma - v;
short prv = Y;
for (short x = 0; x < X; x++) {
short cur = 0;
while (cur < prv && A[x][cur] <= lhi) {
cur++;
}
for (short i = cur; i < Y; i++) {
if (A[x][i] < rlo) return false;
}
prv = cur;
}
return true;
}
// keep the upper bound
void go() {
mi = -1;
while (ma - mi > 1) {
int md = (mi + ma) / 2;
if (is_good(md)) {
ma = md;
} else {
mi = md;
}
}
}
int main() {
fread(ch,1,ch_top,stdin);
X = read(), Y = read();
gmi = INF, gma = -INF;
for (short x = 0; x < X; x++) {
for (short y = 0; y < Y; y++) {
A[x][y] = read();
gmi = min(gmi, A[x][y]);
gma = max(gma, A[x][y]);
}
}
ma = gma - gmi;
go();
for (short x = 0; x < X; x++) {
reverse(A[x], A[x] + Y);
}
go();
for (short y = 0; y < Y; y++) {
for (short x = 0; x < X / 2; x++) {
swap(A[x][y], A[X - 1 - x][y]);
}
}
go();
for (short x = 0; x < X; x++) {
reverse(A[x], A[x] + Y);
}
go();
cout << ma << '\n';
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 504 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Correct | 2 ms | 376 KB | Output is correct |
| 4 | Correct | 2 ms | 376 KB | Output is correct |
| 5 | Correct | 2 ms | 376 KB | Output is correct |
| 6 | Correct | 2 ms | 376 KB | Output is correct |
| 7 | Correct | 2 ms | 376 KB | Output is correct |
| 8 | Correct | 2 ms | 376 KB | Output is correct |
| 9 | Correct | 2 ms | 376 KB | Output is correct |
| 10 | Correct | 2 ms | 376 KB | Output is correct |
| 11 | Correct | 2 ms | 376 KB | Output is correct |
| 12 | Correct | 2 ms | 376 KB | Output is correct |
| 13 | Correct | 2 ms | 376 KB | Output is correct |
| 14 | Correct | 2 ms | 376 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 504 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Correct | 2 ms | 376 KB | Output is correct |
| 4 | Correct | 2 ms | 376 KB | Output is correct |
| 5 | Correct | 2 ms | 376 KB | Output is correct |
| 6 | Correct | 2 ms | 376 KB | Output is correct |
| 7 | Correct | 2 ms | 376 KB | Output is correct |
| 8 | Correct | 2 ms | 376 KB | Output is correct |
| 9 | Correct | 2 ms | 376 KB | Output is correct |
| 10 | Correct | 2 ms | 376 KB | Output is correct |
| 11 | Correct | 2 ms | 376 KB | Output is correct |
| 12 | Correct | 2 ms | 376 KB | Output is correct |
| 13 | Correct | 2 ms | 376 KB | Output is correct |
| 14 | Correct | 2 ms | 376 KB | Output is correct |
| 15 | Correct | 2 ms | 376 KB | Output is correct |
| 16 | Correct | 3 ms | 1400 KB | Output is correct |
| 17 | Correct | 4 ms | 1784 KB | Output is correct |
| 18 | Correct | 4 ms | 1784 KB | Output is correct |
| 19 | Correct | 4 ms | 1784 KB | Output is correct |
| 20 | Correct | 4 ms | 1656 KB | Output is correct |
| 21 | Correct | 5 ms | 2040 KB | Output is correct |
| 22 | Correct | 5 ms | 2040 KB | Output is correct |
| 23 | Correct | 5 ms | 2040 KB | Output is correct |
| 24 | Correct | 4 ms | 1912 KB | Output is correct |
| 25 | Correct | 5 ms | 2040 KB | Output is correct |
| 26 | Correct | 6 ms | 2040 KB | Output is correct |
| 27 | Correct | 6 ms | 2040 KB | Output is correct |
| 28 | Correct | 6 ms | 2040 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 504 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Correct | 2 ms | 376 KB | Output is correct |
| 4 | Correct | 2 ms | 376 KB | Output is correct |
| 5 | Correct | 2 ms | 376 KB | Output is correct |
| 6 | Correct | 2 ms | 376 KB | Output is correct |
| 7 | Correct | 2 ms | 376 KB | Output is correct |
| 8 | Correct | 2 ms | 376 KB | Output is correct |
| 9 | Correct | 2 ms | 376 KB | Output is correct |
| 10 | Correct | 2 ms | 376 KB | Output is correct |
| 11 | Correct | 2 ms | 376 KB | Output is correct |
| 12 | Correct | 2 ms | 376 KB | Output is correct |
| 13 | Correct | 2 ms | 376 KB | Output is correct |
| 14 | Correct | 2 ms | 376 KB | Output is correct |
| 15 | Correct | 2 ms | 376 KB | Output is correct |
| 16 | Correct | 3 ms | 1400 KB | Output is correct |
| 17 | Correct | 4 ms | 1784 KB | Output is correct |
| 18 | Correct | 4 ms | 1784 KB | Output is correct |
| 19 | Correct | 4 ms | 1784 KB | Output is correct |
| 20 | Correct | 4 ms | 1656 KB | Output is correct |
| 21 | Correct | 5 ms | 2040 KB | Output is correct |
| 22 | Correct | 5 ms | 2040 KB | Output is correct |
| 23 | Correct | 5 ms | 2040 KB | Output is correct |
| 24 | Correct | 4 ms | 1912 KB | Output is correct |
| 25 | Correct | 5 ms | 2040 KB | Output is correct |
| 26 | Correct | 6 ms | 2040 KB | Output is correct |
| 27 | Correct | 6 ms | 2040 KB | Output is correct |
| 28 | Correct | 6 ms | 2040 KB | Output is correct |
| 29 | Correct | 112 ms | 59484 KB | Output is correct |
| 30 | Correct | 137 ms | 59100 KB | Output is correct |
| 31 | Correct | 161 ms | 62356 KB | Output is correct |
| 32 | Correct | 125 ms | 62360 KB | Output is correct |
| 33 | Correct | 103 ms | 54288 KB | Output is correct |
| 34 | Correct | 127 ms | 62456 KB | Output is correct |
| 35 | Correct | 260 ms | 93560 KB | Output is correct |
| 36 | Correct | 188 ms | 83388 KB | Output is correct |
| 37 | Correct | 259 ms | 93840 KB | Output is correct |