oj.uz

Submission #895525

# Submission time Handle Problem Language Result Execution time Memory
895525 2023-12-30T07:34:03 Z nbphong Watching (JOI13_watching) C++14
50 / 100
 1000 ms 4188 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = (a), _b =(b); i <= _b; i++)
#define FORD(i, a, b) for(int i = (a), _b =(b); i >= _b; i--)
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x >> i) & 1)
#define popc(i) __builtin_popcountll(i)
#define fi first
#define se second
#define ALL(v) (v).begin(),(v).end()
#define pii pair<int, int>
using ll = long long;
using namespace std;
const int maxn = 2e3 + 10;
int n,p,q;
vector<vector<int>> dp;
long long a[maxn];
long long res(1);
bool check(long long w){
    FOR(i,0,p)
        FOR(j,0,q)
            dp[i][j] = 0;
    dp[0][0] = 1;
    FOR(i,0,p)
        FOR(j,0,q)
            if(dp[i][j] > 0){
                int pos = dp[i][j];
                if(i < p){
                    int tmp = upper_bound(&a[1],&a[n + 1],a[pos] + w - 1) - &a[0];
                    dp[i + 1][j] = max(dp[i + 1][j],tmp);
                }
                if(j < q){
                    int tmp = upper_bound(&a[1],&a[n + 1],a[pos] + 2LL*w - 1) - &a[0];
                    dp[i][j + 1] = max(dp[i][j + 1],tmp);
                }
            }
    FOR(i,0,p)
        FOR(j,0,q)
            if(dp[i][j] > n)
                return true;
    return false;
}
signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);
    #define task "events"
    //if(fopen(task".inp","r")){
    //    freopen(task".inp","r",stdin);
    //    freopen(task".out","w",stdout);
   // }
    cin >> n >> p >> q;
    FOR(i,1,n)
        cin >> a[i];
    if(n <= p + q)
        return cout << 1,0;
    dp.resize(p + 1,vector<int>(q + 1,0));
    sort(&a[1],&a[n + 1]);
    long long l = 1,r = a[n];
    while(l <= r){
        long long mid =(l + r) >> 1;
        if(check(mid)){
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << res;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 1 ms 600 KB Output is correct
8 Correct 199 ms 824 KB Output is correct
9 Correct 105 ms 860 KB Output is correct
10 Correct 180 ms 1116 KB Output is correct
11 Correct 353 ms 1136 KB Output is correct
12 Execution timed out 1048 ms 4188 KB Time limit exceeded
13 Halted 0 ms 0 KB -