Submission #49599

#TimeUsernameProblemLanguageResultExecution timeMemory
49599mra2322001Watching (JOI13_watching)C++14
100 / 100
367 ms16560 KiB
#include <bits/stdc++.h> #define f0(i, n) for(int i(0); i<(n); i++) #define f1(i, n) for(int i(1); i<=(n); i++) using namespace std; typedef long long ll; const int N = 2002; typedef pair <int, int> pii; int n, p, q, a[N]; ostream& operator << (ostream &os, pii yu){ cout << yu.first << " " << yu.second; } istream& operator >> (istream &is, pii &yu){ cin >> yu.first >> yu.second; } int f[N][N], d1[N], d2[N]; bool check(int mid){ memset(f, -1, sizeof(f)); memset(d1, 0, sizeof(d1)); memset(d2, 0, sizeof(d2)); f1(i, n){ int k = lower_bound(a + 1, a + n + 1, a[i] - mid + 1) - a; --k; d1[i] = k; k = lower_bound(a + 1, a + n + 1, a[i] - 2*mid + 1) - a; --k; d2[i] = k; } f0(j, q + 1) f[0][j] = p; f1(i, n){ f0(j, q + 1){ if(j == 0){ int k = d1[i]; /// k + 1 -> i if(f[k][j] > 0){ f[i][j] = f[k][j] - 1; } } else{ int k = d1[i]; /// k + 1 -> i if(f[k][j] > 0){ f[i][j] = f[k][j] - 1; } k = d2[i]; f[i][j] = max(f[i][j], f[k][j - 1]); } } } return (f[n][q] >= 0); } int main(){ ios_base::sync_with_stdio(0); cin >> n >> p >> q; f1(i, n) cin >> a[i]; sort(a + 1, a + n + 1); if(p + q >= n){ cout << 1; return 0; } int l = 1, r = 1e9 + 2, ans = -1; while(l <= r){ int mid = (l + r)/2; if(check(mid)) ans = mid, r = mid - 1; else l = mid + 1; } cout << ans; }

Compilation message (stderr)

watching.cpp: In function 'std::ostream& operator<<(std::ostream&, pii)':
watching.cpp:14:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
watching.cpp: In function 'std::istream& operator>>(std::istream&, pii&)':
watching.cpp:18:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...