Submission #147281

#TimeUsernameProblemLanguageResultExecution timeMemory
147281karmaWatching (JOI13_watching)C++11
100 / 100
635 ms30328 KiB
#include<bits/stdc++.h> #pragma GCC optimization ("O3") #define ll long long using namespace std; const int N = 2007; ll n, pos[N], p, q, f[N][N]; bool Check(ll w) { int k = 1, l; f[0][0] = 0; for(int j = 1; j <= n; ++j) { while(pos[j] - pos[k] >= 2 * w) ++k; f[0][j] = f[0][k - 1] + 1; } for(int i = 1; i <= p; ++i) { k = l = 1; f[i][0] = 0; for(int j = 1; j <= n; ++j) { while(pos[j] - pos[k] >= 2 * w) ++k; while(pos[j] - pos[l] >= w) ++l; f[i][j] = min({f[i][k - 1] + 1, f[i - 1][j], f[i - 1][l - 1]}); } } return f[p][n] <= q; } int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); if(fopen("test.inp", "r")) { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } cin >> n >> p >> q; for(int i = 1; i <= n; ++i) cin >> pos[i]; if(p + q >= n) return cout << 1, 0; sort(pos + 1, pos + n + 1); ll l = 1, h = (ll)1e9; while(l <= h) { ll mid = (l + h) >> 1; if(Check(mid)) h = mid - 1; else l = mid + 1; } cout << l; }

Compilation message (stderr)

watching.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
watching.cpp: In function 'int main()':
watching.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...