oj.uz

Submission #341010

# Submission time Handle Problem Language Result Execution time Memory
341010 2020-12-28T21:37:55 Z iliccmarko Watching (JOI13_watching) C++14
0 / 100
 30 ms 364 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;
        vector<ll> v;
        for(int i = 0;i<n;i++) v.pb(a[i]);
        ll qq = q;
        while(true)
        {
            if(!len(v)) break;
            if(!qq) break;
            ll ima = 0;
            ll cnt = 0;
            ll maks = 0;
        ll levi, desni;
        ll pret = v[0];
        ll poc = v[0];
        ll kraj = 0;
        ll duz = 1;
            for(int i = 0;i<(ll)len(v);i++)
            {
                cnt++;
                if(v[i] - poc >= mid&&v[i] - poc + 1 <= 2 * mid)
                {
                    ima = 1;
                    if(v[i] - poc + 1 >= maks)
                    {
                        maks = v[i] - poc;
                        kraj = i;
                        duz = cnt;
                    }
                }
                else if(v[i] - poc >= 2*mid)
                {
                    cnt = 1;
                    poc = v[i];
                    pret = v[i];
                }
                pret = v[i];
            }
        if(ima==0) break;
        else qq--;
        vector<ll> a;
        for(ll i = 0;i<(ll)len(v);i++)
        {
            ll k = kraj - duz  + 1;
            if(i<k||i>kraj) a.pb(v[i]);
        }
        v.clear();
        for(ll x : a) v.pb(x);
        }
        if(!len(v))
        {
            ans = mid;
            r = mid - 1;
            continue;
        }
        int poc = v[0];
        int pret = v[0];
        int cnt = 0;
        for(int x : v)
        {
            if(x - pret >= mid)
            {
                cnt++;
                pret = x;
                poc = x;
            }
        }
        cnt++;
        if(qq+p>=cnt)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }

    cout<<ans;





    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:45:12: warning: unused variable 'levi' [-Wunused-variable]
   45 |         ll levi, desni;
      |            ^~~~
watching.cpp:45:18: warning: unused variable 'desni' [-Wunused-variable]
   45 |         ll levi, desni;
      |                  ^~~~~
watching.cpp:46:12: warning: variable 'pret' set but not used [-Wunused-but-set-variable]
   46 |         ll pret = v[0];
      |            ^~~~
watching.cpp:88:13: warning: variable 'poc' set but not used [-Wunused-but-set-variable]
   88 |         int poc = v[0];
      |             ^~~

Subtask #1
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 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 Incorrect 1 ms 364 KB Output isn't correct
8 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 29 ms 364 KB Output is correct
4 Correct 21 ms 364 KB Output is correct
5 Correct 30 ms 364 KB Output is correct
6 Correct 30 ms 364 KB Output is correct
7 Incorrect 4 ms 364 KB Output isn't correct
8 Halted 0 ms 0 KB -