SHARE
TWEET

Untitled

a guest Oct 23rd, 2019 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define fi first
  4. #define se second
  5. #define fin(s) freopen( s, "r", stdin );
  6. #define fout(s) freopen( s, "w", stdout );
  7.  
  8. const long long N = 200100;
  9. const long long Q = 10010;
  10. const long long mod = 1000000007;
  11. const long long block = 500;
  12.  
  13. using namespace std;
  14.  
  15. int n, k, m;
  16. int a[N];
  17. int d[N];
  18.  
  19. void solve()
  20. {
  21.         cin >> n >> k >> m;
  22.         for(int i = 1; i <= m; i++){
  23.                 cin >> a[i];
  24.         }
  25.         sort(a + 1, a + m + 1);
  26.         int ans = 0;
  27.         for(int i = 1; i <= m; i++){
  28.                 int l = 0, r = i - 1;
  29.                 while(l < r){
  30.                         int m = (l + r) / 2 + 1;
  31.                         if(a[i] - k + 1 <= a[m]){
  32.                                 r = m - 1;
  33.                         }
  34.                         else{
  35.                                 l = m;
  36.                         }
  37.                 }
  38.                 if(l == 0){
  39.                         d[i] = max(0, a[i] - k);
  40.                 }
  41.                 else{
  42.                         d[i] = d[l] + (a[i] - k + 1) - a[l] - 1;
  43.                 }
  44.                 if(a[i] + k - 1 >= a[m]){
  45.                         ans = max(ans, d[i - 1] + max(0, n - (a[i] + k - 1)) + a[i] - a[i - 1] - 1);
  46.                 }
  47.         }
  48.         ans = max(ans, d[m] + n - a[m]);
  49.         cout << ans << "\n";
  50. }
  51.  
  52. bool mtest = false; int main()
  53. {
  54.         //fin("input.txt");
  55.         //fout("output.txt");
  56.         //fin("mine.in");
  57.         //fout("mine.out");
  58.         ios_base::sync_with_stdio(0);
  59.         int TE = 1;
  60.         if(mtest)
  61.                 cin >> TE;
  62.         while(TE--)
  63.                 solve();
  64.         return 0;
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top