Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.67 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement