제출 #1244422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244422		nguyenhuythach	구경하기 (JOI13_watching)	C++20	0 / 100	5 ms	8260 KiB

watching

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
//#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define MASK(i) ((1)<<(i))
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_asince_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=2001;
int n,p,q;
vector<int> a;
int dp[nmax][nmax];

void input()
{
    cin >> n >> p >> q;
    a.push_back(0);
    FOR(i,1,n)
    {
        int x; cin >> x;
        a.push_back(x);
    }
}

bool check(int w)
{
    FOR(i,0,p) dp[1][i]=q;
    FOR(i,2,n+1) FOR(j,0,p) dp[i][j]=INT_MIN;
    FOR(i,1,n)
    {
        int small=upper_bound(a.begin(),a.end(),a[i]+w-1)-a.begin();
        int large=upper_bound(a.begin(),a.end(),a[i]+2*w-1)-a.begin();
        FOR(j,0,p)
        {
            dp[small][j-1]=max(dp[small][j-1],dp[i][j]);
            dp[large][j]=max(dp[large][j],dp[i][j]-1);
        }
    }
    int ans=INT_MIN;
    FOR(i,0,p) ans=max(ans,dp[n+1][i]);
//    if(w==4)
//    {
//        FOR(i,1,n+1) {FOR(j,0,p) cout << dp[i][j] << ' '; cout << '\n';}
//    }
    if(ans<0) return false;
    else return true;
}

void solve()
{
    p=min(p,n);
    q=min(q,n);
    int l=0,r=1e9;
    while(l+1<r)
    {
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout << r;
}

int main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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