Submission #1305455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305455		mikasa	구경하기 (JOI13_watching)	C++20	0 / 100	8 ms	580 KiB

watching

#include<bits/stdc++.h>
using namespace std;
using intt=int32_t;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x) x.begin(),x.end()
#define pb push_back 

const int N=10001;
const int mod=1e9;
const int inf=2e9;
int n,p,q;
int a[N];

bool check(int x){
  const int m=p+q;
  vector<vector<bool>> dp(n+1,vector<bool>(m+1,0));
  vector<int> mem(n+1,0);
  for (int i=0;i<=m;++i) {
    dp[0][i]=1;
  }
  for (int i=1;i<=n;++i) {
    for (int j=1;j<=m;++j) {
      int w=x;
      if (j>p) w*=2;
      int dist=a[i]-a[mem[j-1]+1]+1;
      if (dist<=w) {
        dp[i][j]=dp[mem[j-1]][j-1];
      }
      if (dp[i][j]) mem[j]=i;
    }
  }
  return dp[n][m]==1;
}

void levi() {
  cin>>n>>p>>q;
  a[0]=1;
  for (int i=1;i<=n;++i) cin>>a[i];
  sort(a+1,a+n+1);
  if (p+q>=n) {
    cout<<1<<'\n';
    return;
  }
  int lo=1,hi=1e9;
  int res=1e9;
  while(lo<=hi) {
    int mid=lo+(hi-lo)/2;
    if (check(mid)) {
      res=mid;
      hi=mid-1;
    }
    else lo=mid+1;
  }
  cout<<res<<'\n';
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);int tt=1;//cin>>tt;
  while(tt--)levi();
}

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