Submission #412423

#	Time	Username	Problem	Language	Result	Execution time	Memory
412423		kimbj0709	Watching (JOI13_watching)	C++14	100 / 100	103 ms	7884 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define int long long
int small,big;
vector<int> vect1;

bool can(int k){
  int dp[small+2][big+2];
  int pos1[vect1.size()+2],pos2[vect1.size()+2];
  for(int i=0;i<vect1.size();i++){
    pos1[i] = i,pos2[i] = i;
    while(pos1[i]+1<vect1.size()&&vect1[pos1[i]+1]-vect1[i]+1<=k){
      pos1[i]++;
    }
    while(pos2[i]+1<vect1.size()&&vect1[pos2[i]+1]-vect1[i]+1<=k*2){
      pos2[i]++;
    }
  }
  memset(dp,0,sizeof(dp));
  for(int i=0;i<=small;i++){
    for(int j=0;j<=big;j++){
      if(dp[i][j]==vect1.size()){
        return 1;
      }
      dp[i+1][j] = max(dp[i+1][j],pos1[dp[i][j]]+1);
      dp[i][j+1] = max(dp[i][j+1],pos2[dp[i][j]]+1);
    }
  }
  return 0;
}

int32_t main() {
  int no_of_input,input;
  cin >> no_of_input >> small >> big;
  for(int i=0;i<no_of_input;i++){
    cin >> input;
    vect1.push_back(input);
  }
  sort(vect1.begin(),vect1.end());
  if(small+big>=vect1.size()){
    cout << 1;
    return 0;
  }
  int low = 0,high = INT_MAX;
  while(low+1!=high){
    //cout << low << " " << high << endl;
    int mid = (low+high)/2;
    if(can(mid)==1){
      high = mid;
    }
    else{
      low = mid;
    }
  }
  cout <<high;
}

Compilation message (stderr)

watching.cpp: In function 'bool can(long long int)':
watching.cpp:10:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |   for(int i=0;i<vect1.size();i++){
      |               ~^~~~~~~~~~~~~
watching.cpp:12:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     while(pos1[i]+1<vect1.size()&&vect1[pos1[i]+1]-vect1[i]+1<=k){
      |           ~~~~~~~~~^~~~~~~~~~~~~
watching.cpp:15:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     while(pos2[i]+1<vect1.size()&&vect1[pos2[i]+1]-vect1[i]+1<=k*2){
      |           ~~~~~~~~~^~~~~~~~~~~~~
watching.cpp:22:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |       if(dp[i][j]==vect1.size()){
      |          ~~~~~~~~^~~~~~~~~~~~~~
watching.cpp: In function 'int32_t main()':
watching.cpp:40:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   if(small+big>=vect1.size()){
      |      ~~~~~~~~~^~~~~~~~~~~~~~

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