oj.uz

답안 #122656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122656 2019-06-29T04:50:36 Z DifferentHeaven 구경하기 (JOI13_watching) C++17
100 / 100
 85 ms 8700 KB 
#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
 
using namespace std;
 
inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}
 
const int N = 2007;
 
int n, p, q;
int a[N];
int f[N][N];
ii nxt[N];
 
inline int BS(int i, long long d){
	int l = i;
	int r = n;
	while (l <= r){
		int mid = (l + r) / 2;
		if (a[mid] - a[i] + 1 <= d)
			l = mid + 1;
		else
			r = mid - 1;
	}
	return r;
}
 
bool check(int x){
	for (int i = 1; i <= n; i++){
		nxt[i].x = BS(i, x);
		nxt[i].y = BS(i, 2 * x);
	}
	for (int i = 0; i <= p; i++)
		for (int j = 0; j <= q; j++){
			f[i][j] = 0;
			if (j) f[i][j] = max(f[i][j], nxt[f[i][j - 1] + 1].y);
			if (i) f[i][j] = max(f[i][j], nxt[f[i - 1][j] + 1].x);
			if (f[i][j] >= n) return true;
		}
	return false;
}	
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	read(n); read(p); read(q);
	p = min(p, n); q = min(q, n);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	sort(a + 1, a + n + 1);
	int l = 1;
	int r = 1000000000;
	while (l <= r){
		int mid = (l + r) / 2;
		if (check(mid)) 
			r = mid - 1;
		else
			l = mid + 1;
	}
	writeln(l);
}

Compilation message

watching.cpp: In function 'void read(int&)':
watching.cpp:9:39: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
 inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
                                       ^
watching.cpp: In function 'void read(long long int&)':
watching.cpp:10:45: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
 inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
                                             ^
watching.cpp: In function 'void writeln(long long int)':
watching.cpp:11:63: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
 inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
                                                               ^
watching.cpp: In function 'void write(long long int)':
watching.cpp:12:61: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
 inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}
                                                             ^

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 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 760 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 248 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 3 ms 632 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

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 41 ms 4088 KB Output is correct
4 Correct 26 ms 8516 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 10 ms 504 KB Output is correct
8 Correct 18 ms 1272 KB Output is correct
9 Correct 22 ms 3832 KB Output is correct
10 Correct 30 ms 8700 KB Output is correct
11 Correct 14 ms 1144 KB Output is correct
12 Correct 85 ms 8092 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 504 KB Output is correct