Submission #543076

#	Time	Username	Problem	Language	Result	Execution time	Memory
543076		DJ035	Watching (JOI13_watching)	C++17	100 / 100	214 ms	35124 KiB

watching

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#define MEM 2222
#define sanic ios_base::sync_with_stdio(0)
#define x first
#define y second
#define pf push_front
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz size()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
const ll INF = 2e18;
const ll MOD = 998244353;
ll t,n,m,p,q;
ll a[MEM];
ll dp[MEM][MEM];
ll f(ll w){
    //cout << 'P';
    for(int i=0; i<=p; i++) dp[0][i] = 0;
    for(int i=1; i<=n; i++){
        ll k=-1, l=-1;
        //cout << 'q';
        for(int j=1; j<=i; j++){
            if(k==-1 && a[i]-a[j]+1<=w) k = j;
            if(l==-1 && a[i]-a[j]+1<=2*w) l = j;
        }
        //cout << 'r';
        l--, k--;
        //cout << k << ' ' << l << '\n';
        dp[i][0] = dp[l][0]+1;
        for(int j=1; j<=p; j++)
            dp[i][j] = min(dp[k][j-1], dp[l][j]+1);
        //cout << 's';
    }
    return (dp[n][p]<=q);
}

signed main(){
    //sanic; cin.tie(0);
    cin >> n >> p >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    if(p+q>=n){
        cout << 1;
        return 0;
    }
    //cout << '/';
    sort(a+1, a+n+1);
    ll l=1, r=1e9;
    //cout << '.';
    while(l<=r){
        ll mid=l+r>>1;
        //cout << 'u';
        if(f(mid)) r = mid-1;
        else l = mid+1;
    }
    cout << l;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:56:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         ll mid=l+r>>1;
      |                ~^~

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