oj.uz

답안 #895524

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895524 2023-12-30T07:33:09 Z nbphong 구경하기 (JOI13_watching) C++14
50 / 100
 1000 ms 17076 KB 
//#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";
}

Compilation message

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.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 2396 KB Output is correct
8 Correct 6 ms 2396 KB Output is correct
9 Correct 6 ms 2396 KB Output is correct
10 Correct 44 ms 2516 KB Output is correct
11 Correct 46 ms 2396 KB Output is correct
12 Correct 104 ms 2396 KB Output is correct
13 Correct 3 ms 2396 KB Output is correct
14 Correct 2 ms 2396 KB Output is correct
15 Correct 4 ms 2396 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 17076 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 53 ms 16988 KB Output is correct
8 Correct 202 ms 17068 KB Output is correct
9 Execution timed out 1052 ms 17060 KB Time limit exceeded
10 Halted 0 ms 0 KB -