oj.uz

Submission #540437

# Submission time Handle Problem Language Result Execution time Memory
540437 2022-03-20T10:51:47 Z omohamadooo Watching (JOI13_watching) C++17
100 / 100
 237 ms 31712 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll>
#define F first
#define S second
#define double long double
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD = 1e9 + 7;
const int  N=1e6 + 7 ;
const ll INF= 1e18+10;

struct trp{ll F,S,T;};

ll po1(ll x,ll y)
{
    ll ans = 1;
    while(y){
        if( y & 1 ) ans *=x;
        y /= 2;
        x *=x;
        x %= MOD;
        ans %= MOD;
    }
    return ans;
}

ll n , p , q;
ll a[N];
ll dp[2005][2005];

bool ok(ll w)
{
    for(ll i= 0; i <= p ; i ++) dp[0][i] = 0;
    for(ll i= 1 ; i <= n ; i ++){
        ll ans1 = -1;
        ll ans2 = -1;
        for(ll j = 1 ; j <= i ; j ++){
            if(ans1 == -1 && a[i] - a[j] + 1<= w){
                ans1 = j;
            }
            if(ans2 == -1 && a[i] - a[j] + 1 <= 2 * w) ans2 = j;
        }

        dp[i][0] = dp[ans2 - 1][0] + 1;
        //if(w == 1 && i == 2) cout << ans2 << endl;
        for(ll j = 1 ; j <= p ; j ++){
            dp[i][j] = min(dp[ans1-1][j-1] , dp[ans2 - 1][j] + 1);
        }
    }
    return dp[n][p] <= q;
}

void solve()
{
    cin >> n >> p >> q;
    for(ll i=1 ;i <= n ; i++) cin >> a[i];
    sort(a + 1 , a + n + 1);
    if(p+q >= n){
        cout << 1 <<endl;
        return;
    }
    ll l = 1 , r = MOD , mid;
    while(l < r){
        mid = (l + r)/2;
        if(ok(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}

int main(){
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen(".in" , "r" , stdin);freopen(".out" , "w" , stdout);
	int t = 1;
    //cin >> t;
	while(t--) {solve() ; }
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8396 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 89 ms 8560 KB Output is correct
8 Correct 96 ms 10196 KB Output is correct
9 Correct 165 ms 20140 KB Output is correct
10 Correct 237 ms 31712 KB Output is correct
11 Correct 94 ms 9684 KB Output is correct
12 Correct 169 ms 23716 KB Output is correct
13 Correct 89 ms 8508 KB Output is correct
14 Correct 84 ms 8660 KB Output is correct
15 Correct 89 ms 8640 KB Output is correct