Submission #1308798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308798		nvc2k8	Watching (JOI13_watching)	C++20	100 / 100	27 ms	16524 KiB

watching

#include <bits/stdc++.h>
#define TASK "watch"
#define endl mmm
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) (C).begin(), (C).end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///
int n, p, q;
ll a[2048];

void inp()
{
    cin >> n >> p >> q;
    minimize(p, n);
    minimize(q, n);
    FOR(i, 1, n) cin >> a[i];
    sort(a+1, a+1+n);
}

int b[2048], c[2048];
int f[2048][2048];

bool check(ll r)
{
    deque<int> dq;
    FORD(i, n, 1)
    {
        dq.pb(i);
        while (a[dq.front()]>=a[i]+r) dq.pop_front();
        b[i] = dq.front();
    }
    while (!dq.empty()) dq.pop_front();
    FORD(i, n, 1)
    {
        dq.pb(i);
        while (a[dq.front()]>=a[i]+r*2) dq.pop_front();
        c[i] = dq.front();
    }
    FOR(i, 0, p) FOR(j, 0, q) f[i][j] = 0;
    f[0][0] = 1;
    FOR(i, 0, p) FOR(j, 0, q) if (f[i][j])
    {
//        cout << i << ' ' << j << ' ' << f[i][j] << '\n';
        if (f[i][j]==n+1) return true;
        if (i<p) maximize(f[i+1][j], b[f[i][j]]+1);
        if (j<q) maximize(f[i][j+1], c[f[i][j]]+1);
    }
    return false;
}

void solve()
{
    ll l = 1, r = 1e9, ret = 0;
//    FOR(i, 1, 5) cout << check(i) << '\n';
    while (l<=r)
    {
        int mid = (l+r)>>1;
        if (check(mid))
        {
            ret = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    cout << ret;
}

signed main()
{
    ///--------------------------///
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen(TASK".INP","r")!=NULL)
    {
        freopen(TASK".INP","r",stdin);
        freopen(TASK".OUT","w",stdout);
    }
    ///--------------------------///

    int NTEST = 1;
    bool multitest = 0;
    if (multitest) cin >> NTEST;

    while (NTEST--)
    {
        inp();
        solve();
    }

    return 0;
}

///------------------------------------------///

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(TASK".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(TASK".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50