# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
784283 |
2023-07-16T00:33:31 Z |
bane |
Watching (JOI13_watching) |
C++17 |
|
89 ms |
15984 KB |
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
const int MOD = (int)1e9 + 7;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
const int maxN = (int)2e5+1;
int n, p, q;
int a[2001];
bool check(int w){
int dp[n+1][q + 1];
for (int i = 0; i <= n; i++){
for (int j = 0; j <= q; j++){
dp[i][j] = (int)1e9;
}
}
dp[0][0] = 0;
for (int R = 1; R <= n; R++){
int pos2 = R, pos1 = R;
for (int L = R; L>=1; L--){
if (a[R] - a[L] <= w - 1)pos1 = L;
if (a[R] - a[L] <= 2 * w - 1)pos2 = L;
if (a[R] - a[L] >= 2 * w)break;
}
for (int j = 0; j <= q; j++){
if (j)
dp[R][j] = min(dp[pos2-1][j - 1], dp[R][j]);
dp[R][j] = min(dp[R][j], dp[pos1-1][j]+1);
}
}
int MIN = (int)1e9;
for (int i = 0; i <= q; i++)MIN = min(MIN, dp[n][i]);
return MIN <= p;
}
void Ormnis(){
cin >> n >> p >> q;
q = min(n,q);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a + 1, a + 1 + n);
int l = 1, r = (int)a[n] - a[1];
while(l<=r){
int mid = (l+r) >> 1;
if (check(mid)) r = mid - 1;
else l = mid + 1;
}
cout << r + 1 << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
//cin >> tt;
while(tt--){
Ormnis();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
60 ms |
12056 KB |
Output is correct |
4 |
Correct |
8 ms |
928 KB |
Output is correct |
5 |
Correct |
86 ms |
15984 KB |
Output is correct |
6 |
Correct |
89 ms |
15956 KB |
Output is correct |
7 |
Correct |
11 ms |
340 KB |
Output is correct |
8 |
Correct |
31 ms |
6228 KB |
Output is correct |
9 |
Correct |
9 ms |
1300 KB |
Output is correct |
10 |
Correct |
7 ms |
980 KB |
Output is correct |
11 |
Correct |
85 ms |
15192 KB |
Output is correct |
12 |
Correct |
40 ms |
7892 KB |
Output is correct |
13 |
Correct |
6 ms |
468 KB |
Output is correct |
14 |
Correct |
7 ms |
340 KB |
Output is correct |
15 |
Correct |
7 ms |
456 KB |
Output is correct |