Submission #384887

#	Time	Username	Problem	Language	Result	Execution time	Memory
384887		cpp219	Watching (JOI13_watching)	C++14	50 / 100	690 ms	262148 KiB

watching

#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,jump[N][2]; /// 0 if short jump    1 long jump

ll Find(ll x){
    if (x > a[n]) return n + 1;
	ll p = lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
	return p;
}

ll f(ll pos,ll p){
	if (pos > n) return 0;
	if (dp[pos][p] != -1) return dp[pos][p];
	ll ans = inf;
	if (p) ans = f(jump[pos][0],p - 1);
	ans = min(ans,1 + f(jump[pos][1],p));
	return dp[pos][p] = ans;
}

bool chk(ll m){
	memset(dp,-1,sizeof(dp)); val = m;
	for (ll i = 1;i <= n;i++){
        jump[i][0] = Find(a[i] + m); jump[i][1] = Find(a[i] + 2*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]);
    if (P + Q >= n){
        cout<<1; return 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 (stderr)

watching.cpp: In function 'int main()':
watching.cpp:46:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   46 |     for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
      |     ^~~
watching.cpp:46:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   46 |     for (ll i = 1;i <= n;i++) cin>>a[i]; sort(a + 1,a + n + 1);
      |                                          ^~~~
watching.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         freopen(task".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50