| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 261078 |
2020-08-11T11:18:17 Z |
srj |
Watching (JOI13_watching) |
C++14 |
|
87 ms |
16000 KB |
#include<bits/stdc++.h>
// #include<gondola.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;
//for debugging
/*
g++ -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -std=c++14
*/
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v){
os<<"[";
for(auto& x:v){os<<x<<", ";}
return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p){
return os<<"{"<<p.first<<", "<<p.second<<"}";
}
// debugging ends here
typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 1e9;
const int mxn = 2005;
int cache[mxn+1][mxn];
int p,q;
int a[mxn];
int n;
ll dp(int i, ll pres, ll w) {
//cerr << "i=" << i << "; pres=" << pres << endl;
// caso base
if (i >= n) return 0LL;
// caso dp
if (cache[i][p]!=-1) return cache[i][pres];
// caso recursivo
else {
ll res1 = INF, res2 = INF;
// tomo un p
int j=i;
while (j+1<n && a[j+1]-a[i]+1<=w) j++;
if (pres) res1 = dp(j+1, pres-1, w);
// tomo un q
while (j+1<n && a[j+1]-a[i]+1<=2*w) j++;
res2 = dp(j+1, pres, w) + 1LL;
return cache[i][pres] = min(res1, res2);
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("bbreeds.in","r",stdin);
freopen("bbreeds.out","w",stdout);
#endif
// int n;
cin >> n >> p >> q;
// int a[n];
// dbg(n);
for(int i =0;i<n;i++)
cin >> a[i];
sort(a,a+n);
int lo = 1,hi = 1e9;
while(lo<=hi){
int mid = lo + (hi-lo)/2;
// cout << mid << endl;
memset(cache,-1,sizeof(cache));
int check = dp(0,p,mid);
// cout << lo << endl;
// cout << mid << " " << cache[n-1][p] << endl;
if(check<=q)
hi = mid-1;
else lo = mid+1;
}
cout << lo << endl;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:75:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("bbreeds.in","r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("bbreeds.out","w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
16000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
16000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
