Submission #122656

#TimeUsernameProblemLanguageResultExecution timeMemory
122656DifferentHeavenWatching (JOI13_watching)C++17
100 / 100
85 ms8700 KiB
#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 (stderr)

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(' ');}
                                                             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...