Submission #1157237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157237		MPG	Watching (JOI13_watching)	C++20	100 / 100	58 ms	16200 KiB

watching

//#pragma GCC optomize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse4.1,sse4.2") 



#include <bits/stdc++.h>
using namespace std;
typedef long long                           ll;
#define                                     max_heap priority_queue<pair <ll, pair <ll, ll>>>
#define                                     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>>
//#define                                     min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define                                     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define                                     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout); 
#define                                     endl '\n'
#define                                     md(a) (a % mod + mod) % mod
#define pb push_back
//cout << vectorprecision(5) << fixed << f;
//hash prime = 769
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


ll const maxn = 1e5 + 123;
ll const inf = 2e18;
ll const loG = 23;
ll const mod = 1e9 + 7;
//ll const mod = 998244353;
ll const sq = 400;
ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}


int n, A, B, dp[2025][2025];
vector <int> arr, mos;

void Solve(){


cin >> n >> A >> B;
int mn = mod;
for (int i = 1; i < n + 1; i++){
    int x; cin >> x;
    mos.pb(x);
    arr.pb(-x);
    mn = min(mn, x);
}
if (A + B >= n){
    cout << 1 << endl;
    return;
}

sort(arr.begin(), arr.end()); arr.resize(unique(arr.begin(), arr.end()) - arr.begin());
sort(mos.begin(), mos.end()); mos.resize(unique(mos.begin(), mos.end()) - mos.begin());
n = arr.size();

int l = 0, r = mod / A + 1;
while (r - l > 1){
    int mid = (l + r) / 2;
    for (int i = 1; i < n + 1; i++){
        dp[i][0] = mod;
        int x = mos[i - 1];
        int y1 = upper_bound(arr.begin(), arr.end(), -(x - 2 * mid + 1)) - arr.begin();
        y1 = n - y1;
        dp[i][0] = dp[y1][0] + 1;
 
        int y2 = upper_bound(arr.begin(), arr.end(), -(x - mid + 1)) - arr.begin();
        y2 = n - y2;

        for (int j = 1; j < A + 1; j++){
            dp[i][j] = mod;
            dp[i][j] = dp[y1][j] + 1;
            dp[i][j] = min(dp[i][j], dp[y2][j - 1]);
            //cout << i << ' ' << j << ' ' << dp[i][j] << endl;
        }
    }
    if (dp[n][A] <= B)
        r = mid;
    else
        l = mid;
}
cout << r << endl;




}





int main(){
sariE;// filE;



int test = 1;
//cin >> test;
while (test--) Solve();
return 0;
}

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