Submission #674595

#	Time	Username	Problem	Language	Result	Execution time	Memory
674595		esomer	Watching (JOI13_watching)	C++17	100 / 100	375 ms	15476 KiB

watching

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl "\n"
 
const int MOD = 998244353;

void solve(){
	int n, p, q; cin >> n >> p >> q;
	swap(p, q);
	vector<int> v(n);
	for(auto &i : v) cin >> i;
	sort(v.begin(), v.end());
	if(n <= p + q){
		cout << 1 << endl; return;
	}
	set<pair<int, int>> s;
	for(int i = 0; i < n; i++) s.insert({v[i], i});
	int ans;
	ll lo = 1;
	ll hi = 1e9;
	while(lo <= hi){
		ll w = (lo + hi) / 2;
		vector<vector<int>> dp(n, vector<int>(p + 1, 1e9));
		for(int i = 0; i < n; i++){
			auto it = s.upper_bound({v[i] - w, 1e9});
			if(it == s.begin()){
				dp[i] = vector<int>(p + 1, 1);
			}else{
				it--;
				int j = (*it).second;
				dp[i] = dp[j];
				for(int g = 0; g <= p; g++) dp[i][g]++;
			}
			it = s.upper_bound({v[i] - 2 * w, 1e9});
			if(it == s.begin()){
				for(int g = 1; g <= p; g++) dp[i][g] = 0;
			}else{
				it--;
				int j = (*it).second;
				for(int g = 1; g <= p; g++){
					dp[i][g] = min(dp[i][g], dp[j][g - 1]);
				}
			}
		}
		if(dp[n - 1][p] <= q){
			ans = w;
			hi = w - 1;
		}else lo = w + 1;
	}
	cout << ans << endl;
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    //int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

Compilation message (stderr)

watching.cpp: In function 'void solve()':
watching.cpp:6:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
    6 | #define endl "\n"
      |              ^~~~
watching.cpp:21:6: note: 'ans' was declared here
   21 |  int ans;
      |      ^~~

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