| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 384837 |
2021-04-02T11:55:33 Z |
cpp219 |
Watching (JOI13_watching) |
C++14 |
|
388 ms |
262148 KB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e3 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
vector<ll> v;
ll n,P,Q,a[N],dp[N][N],val;
unordered_map<ll,ll> mp;
ll Find(ll x){
if (!mp[x]) return mp[x];
return mp[x] = lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}
ll f(ll pos,ll p){
if (pos > n) return 0;
if (dp[pos][p] != -1) return dp[pos][p];
ll ans = inf,nxt1 = Find(a[pos] + val),nxt2 = Find(a[pos] + val*2);
if (p) ans = f(nxt1,p - 1);
ans = min(ans,1 + f(nxt2,p));
return dp[pos][p] = ans;
}
bool chk(ll m){
memset(dp,-1,sizeof(dp)); val = m;
return f(1,P) <= Q;
}
int main(){
//ios_base::sync_with_stdio(0);
//cin.tie(0), cout.tie(0);
#define task "tst"
if (fopen(task".in", "r")){
freopen(task".in", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>n>>P>>Q;
for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
for (ll i = 1;i <= n;i++) v.push_back(a[i]); v.push_back(inf);
if (P + Q >= n) return cout<<1,0;
ll l,m,h; l = 0; h = inf;
while(l <= h){
m = (l + h)/2;
if (chk(m)) h = m - 1;
else l = m + 1;
}
cout<<l;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:43:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
43 | for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
| ^~~
watching.cpp:43:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
43 | for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
| ^~~~
watching.cpp:44:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
44 | for (ll i = 1;i <= n;i++) v.push_back(a[i]); v.push_back(inf);
| ^~~
watching.cpp:44:50: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
44 | for (ll i = 1;i <= n;i++) v.push_back(a[i]); v.push_back(inf);
| ^
watching.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
39 | freopen(task".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
388 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
387 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
