oj.uz

Submission #340546

# Submission time Handle Problem Language Result Execution time Memory
340546 2020-12-27T22:14:32 Z iliccmarko Watching (JOI13_watching) C++14
0 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
ll n, p, q;
const int N = 2005;
ll a[N];




int main()
{
    ios
    cin>>n>>p>>q;
    for(int i = 0;i<n;i++) cin>>a[i];
    sort(a, a+n);

    ll ans = 1e9;
    ll l = 1;
    ll r = 1e9;
    while(l<=r)
    {
        ll mid = (r+l)/2;
        ll poc = a[0];
        ll pret = a[0];
        vector<pair<ll, ll> > v;
        ll cnt = 0;
        for(ll i = 0;i<n;i++)
        {
            if(a[i] - poc>=mid)
            {
                cnt = 1;
                v.pb({poc, pret});
                poc = a[i];
                pret = a[i];
            }
            else
            {
                pret = a[i];
            }
        }
        v.pb({poc, pret});
        ll c = 0;
        ll qq = q;
        ll pp = p;
        for(ll i = 1;i<len(v);i++)
        {
            if(!qq) break;
            ll raz = v[i].second - v[i-1].first;
            if(raz<=2*mid-1)
            {
                qq--;
                i--;
                i+=2;
            }
        }
        ll w = (ll)len(v) - (q-qq)*2;
        if(qq+p>=w)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }

    cout<<ans;





    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:38:12: warning: variable 'cnt' set but not used [-Wunused-but-set-variable]
   38 |         ll cnt = 0;
      |            ^~~
watching.cpp:54:12: warning: unused variable 'c' [-Wunused-variable]
   54 |         ll c = 0;
      |            ^
watching.cpp:56:12: warning: unused variable 'pp' [-Wunused-variable]
   56 |         ll pp = p;
      |            ^~

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 1 ms 364 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Incorrect 1 ms 492 KB Output isn't correct
8 Halted 0 ms 0 KB -