oj.uz

Submission #443857

# Submission time Handle Problem Language Result Execution time Memory
443857 2021-07-12T09:13:52 Z BT21tata Watching (JOI13_watching) C++17
100 / 100
 536 ms 31752 KB 
#include<bits/stdc++.h>
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef long double ld;
#define SPEED ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define rall(v) (v).rbegin(),(v).rend()
#define all(v) (v).begin(),(v).end()
#define OK cerr<<"OK"<<endl<<flush
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define F first
#define S second
#define y0 jahdakdh
#define y1 jahsadakdakdh
#define endl '\n'
using namespace std;
const ll MOD=1e9+7;
// mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

ll n, s, b, a[2005], dp[2005][2005];

bool check(int w)
{
    dp[0][0]=0;
    ll pos, x=0;
    for(int i=0; i<=min(n, s); i++)
    {
        for(int j=0; j<=min(n, b); j++)
        {
            if(!i and !j) continue;
            if(i)
            {
                x=pos=dp[i-1][j];
                while(x<n and a[pos]+w-1>=a[x]) x++;
            }
            dp[i][j]=x;
            if(j)
            {
                x=pos=dp[i][j-1];
                while(x<n and a[pos]+2*w-1>=a[x]) x++;
            }
            dp[i][j]=max(x, dp[i][j]);
        }
    }
    /*cout<<w<<endl;
    for(int i=0; i<=min(n, s); i++, cout<<endl)
    {
        for(int j=0; j<=min(n, b); j++)
        {
            cout<<dp[i][j]<<' ';
        }
    }*/
    return dp[min(n, s)][min(n, b)]>=n;
}

int main()
{
    SPEED;
    cin>>n>>s>>b;
    for(int i=0; i<n; i++)
        cin>>a[i];
    sort(a, a+n);
    ll l=1, r=1e9, mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 327 ms 23896 KB Output is correct
4 Correct 33 ms 9548 KB Output is correct
5 Correct 27 ms 1484 KB Output is correct
6 Correct 536 ms 31752 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 28 ms 1564 KB Output is correct
9 Correct 30 ms 4044 KB Output is correct
10 Correct 37 ms 9312 KB Output is correct
11 Correct 31 ms 1756 KB Output is correct
12 Correct 163 ms 11780 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct