oj.uz

Submission #785999

# Submission time Handle Problem Language Result Execution time Memory
785999 2023-07-17T21:47:00 Z Sputnik1234 Watching (JOI13_watching) C++14
100 / 100
 420 ms 31748 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 328 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 245 ms 23912 KB Output is correct
4 Correct 24 ms 9556 KB Output is correct
5 Correct 19 ms 1592 KB Output is correct
6 Correct 420 ms 31748 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 17 ms 1592 KB Output is correct
9 Correct 24 ms 4052 KB Output is correct
10 Correct 25 ms 9300 KB Output is correct
11 Correct 21 ms 1748 KB Output is correct
12 Correct 113 ms 11732 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct