Submission #384837

#	Time	Username	Problem	Language	Result	Execution time	Memory
384837		cpp219	Watching (JOI13_watching)	C++14	0 / 100	388 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;
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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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