Submission #1264725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264725		4o2a	Watching (JOI13_watching)	C++20	0 / 100	5 ms	8260 KiB

watching

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define _F "what"
using namespace std;
typedef long long ll;

constexpr int N = 2e3 + 1;
int n, P, Q, dp[N][N];
vector<int> A(N);

bool DP(int w)
{
    for (int i = 1; i <= n; ++i)
    {
        int lp = lower_bound(A.begin()+1, A.begin()+n+1, A[i] - w) - A.begin(), lq = lower_bound(A.begin()+1, A.begin()+n+1, A[i] - 2*w) - A.begin();
        dp[i][0] = dp[lq-1][0] + 1;
        for (int p = 1; p <= min(P, n); ++p)
            dp[i][p] = min(dp[lp-1][p-1], dp[lq-1][p] + 1);
    }
    return (dp[n][min(P, n)] <= Q);
}

void solve()
{
    cin>>n>>P>>Q;
    for (int i = 1; i <= n; ++i)
        cin>>A[i];
    sort(A.begin()+1, A.begin()+n+1);
    int l = 0, r = 1e9;
    while (r-l > 1)
    {
        int mid = (l+r)/2;
        if (DP(mid))
            r = mid;
        else
            l = mid;
    }
    cout<<r;
}

int main()
{
    if (fopen(_F".INP", "r"))
    {
        freopen(_F".INP", "r", stdin);
        freopen(_F".OUT", "w", stdout);
    }
    else if (fopen("test.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        //freopen("test.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int Test = 1; //cin>>Test;
    while (Test--) solve();
}

Compilation message (stderr)

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

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