oj.uz

Submission #341008

# Submission time Handle Problem Language Result Execution time Memory
341008 2020-12-28T21:20:38 Z iliccmarko Watching (JOI13_watching) C++14
0 / 100
 1000 ms 492 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<int> v;
        for(int i = 0;i<n;i++) v.pb(a[i]);
        int qq = q;
        while(true)
        {
            if(!qq) break;
            int ima = 0;
            int cnt = 0;
            int maks = 0;
        int levi, desni;
        int pret = a[0];
        int poc = a[0];
        int kraj = 0;
        int duz = 1;
            for(int i = 0;i<len(v);i++)
            {
                cnt++;
                if(a[i] - poc >= mid&&a[i] - poc + 1 <= 2 * mid)
                {
                    ima = 1;
                    if(a[i] - poc + 1 >= maks)
                    {
                        maks = a[i] - poc;
                        kraj = i;
                        duz = cnt;
                    }
                }
                else if(a[i] - poc >= 2*mid)
                {
                    cnt = 1;
                    poc = a[i];
                    pret = a[i];
                }
                pret = a[i];
            }
        if(ima==0) break;
        else qq--;
        vector<int> a;
        for(int i = 0;i<n;i++)
        {
            int k = kraj - duz  + 1;
            if(i<k||i>kraj) a.pb(v[i]);
        }
        v.clear();
        for(int 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:44:13: warning: unused variable 'levi' [-Wunused-variable]
   44 |         int levi, desni;
      |             ^~~~
watching.cpp:44:19: warning: unused variable 'desni' [-Wunused-variable]
   44 |         int levi, desni;
      |                   ^~~~~
watching.cpp:45:13: warning: variable 'pret' set but not used [-Wunused-but-set-variable]
   45 |         int pret = a[0];
      |             ^~~~
watching.cpp:87:13: warning: variable 'poc' set but not used [-Wunused-but-set-variable]
   87 |         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 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Execution timed out 1071 ms 384 KB Time limit exceeded
6 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 380 KB Output is correct
3 Incorrect 618 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -