제출 #895524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895524		nbphong	구경하기 (JOI13_watching)	C++14	50 / 100	1052 ms	17076 KiB

watching

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define fi first
#define se second
#define pb emplace_back
#define pii pair<int, int>
#define ms(s, n) memset(s, n, sizeof(s))
#define all(a) a.begin(), a.end()
#define uni(a) (sort(all(a)), a.resize(unique(all(a))-a.begin()))
#define sz(s) (int)((s).size())
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x >> (i)) & 1)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)

using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return l + rd()% (r-l+1);}

const int MOD = 1000000007;
const int mod = 998244353;
const int oo = 1061109567;
const long long INF = 4557430888798830399;
const double PI = acos(-1);
const int N = 2e3 + 1;

/*
     /\_/\
    (= ._.)
    / >?  \>$
*/

int n, p, q;
int a[N];

namespace sub1{
    const int M = 1e2 + 1;
    bool dp[M][M][M];
    bool check(int w){
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        FOR(i, 1, n) FOR(j, 0, p) FOR(k, 0, q){
            int i1 = lower_bound(a+1,a+i,a[i]-w+1) - a;
            int i2 = lower_bound(a+1,a+i,a[i]-w-w+1) - a;
            if(j > 0) dp[i][j][k] |= dp[i1-1][j-1][k];
            if(k > 0) dp[i][j][k] |= dp[i2-1][j][k-1];
        }
        FOR(i, 0, p) FOR(j, 0, q) if(dp[n][i][j]) return 1;
        return 0;
    }
}

namespace sub2{
    int dp[N][N];
    bool check(int w){
        memset(dp, 0x3f, sizeof(dp));
        dp[0][0] = 0;
        FOR(i, 1, n) FOR(j, 0, p){
            int i1 = lower_bound(a+1,a+i,a[i]-w+1) - a;
            int i2 = lower_bound(a+1,a+i,a[i]-w-w+1) - a;
            if(j > 0) dp[i][j] = min(dp[i][j], dp[i1-1][j-1]);
            dp[i][j] = min(dp[i][j], dp[i2-1][j] + 1);
        }
        FOR(i, 0, p) if(dp[n][i] <= q) return 1;
        return 0;
    }
}

bool check(int w){
    if(n <= 1e2) return sub1::check(w);
    if(n <= 2e3) return sub2::check(w);
}

void sol(){
    cin >> n >> p >> q;
    FOR(i, 1, n) cin >> a[i];
    sort(a+1,a+n+1);
    if(p + q > n) return void(cout << 1 << '\n');
    int l = 1, r = a[n]-a[1]+1, ans = -1;
    while(l <= r){
        int m = (l + r) >> 1;
        if(check(m)) r = m-1, ans = m;
        else l = m+1;
    }
    cout << ans << '\n';
}

signed main(){
    #define TASK "EVENTS"
    //if(fopen(TASK".inp", "r")){
    //    freopen(TASK".inp", "r", stdin);
   //     freopen(TASK".out", "w", stdout);
  //  }
    fast; int t = 1;
//    cin >> t;
    while(t--) sol();
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}

컴파일 시 표준 에러 (stderr) 메시지

watching.cpp: In function 'bool check(int)':
watching.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
   89 | }
      | ^

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