Submission #316637

#	Time	Username	Problem	Language	Result	Execution time	Memory
316637		Dymo	Watching (JOI13_watching)	C++14	100 / 100	268 ms	38272 KiB

watching

#include<bits/stdc++.h>

using namespace std;


#define pb    push_back
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=5e3+50;
const ll mod =1e9+7;
const ll base=317;
ll p, q, n ;
ll a[maxn];
ll dp[maxn][maxn];

bool chk(ll len)
{
 // memset(dp,0 ,sizeof (dp));
  ll l=1, r=1;
  for (int i=1;i<=n;i++)
  {
      while (a[l]<a[i]-len+1) l++;
      while (a[r]<a[i]-2*len+1) r++;
      for (int j=0;j<=p;j++)
      {
          dp[i][j]=1e15;
         if (j)dp[i][j]=dp[l-1][j-1];
         dp[i][j]=min(dp[r-1][j]+1,dp[i][j]);
      }
  }
  if (dp[n][p]<=q) return true;
  return false;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.t", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout) ;
    }
    cin>>n>> p>> q;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    if (p+q>=n)
    {
        cout << 1;
        return 0;
    }
    ll l=1, h= 1e10;
    while (l<=h)
    {
        ll mid=(l+h)/2;
        if (chk(mid)) h=mid-1;
        else l=mid+1;
    }
    cout <<l;









}

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("test.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("test.out", "w", stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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