Submission #247266

#	Time	Username	Problem	Language	Result	Execution time	Memory
247266		Nightlight	Swimming competition (LMIO18_plaukimo_varzybos)	C++14	100 / 100	1048 ms	62308 KiB

plaukimo_varzybos

#include <bits/stdc++.h>
using namespace std;

int N, A, B;
int arr[1000005];
vector<int> pen[1000005];
bitset<1000001> can;
int p, cnt, pos;

bool check(int now) {
//  cout << now << "\n";
  p = 1;
  while(arr[p] - arr[1] <= now) p++;
  if(p <= A) return 0;

  can = 0;
  can[0] = 1;
  cnt = 0;
  
  pen[p].emplace_back(0);
  for(int i = A; i <= N; i++) {
    if(can[i - A]) cnt++;
    if(i > B && can[i - B - 1]) cnt--;
    while(!pen[i].empty()) {
      pos = pen[i].back();
      if(i - B <= pos && pos <= i - A) cnt--;
      can[pos] = 0; 
      pen[i].pop_back();
    }
//    cout << i << " " << cnt << "\n";
    if(cnt > 0) {
      can[i] = 1;
      if(i < N) while(arr[p] - arr[i + 1] <= now) p++;
      if(p != i) pen[p].emplace_back(i);
      else can[i] = 0;
    }
  }
//  cout << "\n";
  pen[N + 1].clear();
  return can[N];
}

int main() {
  scanf("%d %d %d", &N, &A, &B);
  for(int i = 1; i <= N; i++) {
    scanf("%d", &arr[i]);
  }
  sort(arr + 1, arr + N + 1);
//  for(int i = 1; i <= N; i++) {
//    cout << arr[i] << " ";
//  }
//  cout << "\n";
  arr[N + 1] = 1e9;
  int l = 0, r = 1000000, ans;
  while(l <= r) {
    int mid = (l + r) >> 1;
    if(check(mid)) {
      r = mid - 1;
      ans = mid;
    }else l = mid + 1;
  }
  printf("%d\n", ans);
  cin >> N;
}
/*
8 2 2
1
5
8
8
1
1
8
1000000
*/

Compilation message (stderr)

plaukimo_varzybos.cpp: In function 'int main()':
plaukimo_varzybos.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &N, &A, &B);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plaukimo_varzybos.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40