fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <set>
  4. #include <map>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <cstring>
  11. #include <ctime>
  12. #include <stack>
  13. #include <cassert>
  14. #include <list>
  15. //#include <unordered_set>
  16. using namespace std;
  17. typedef long long li;
  18. typedef long double ld;
  19. typedef vector<int> vi;
  20. typedef pair<int,int> pi;
  21.  
  22. #define mp make_pair
  23. #define pb push_back
  24. #define all(s) s.begin(), s.end()
  25. void solve();
  26.  
  27. int main() {
  28. #ifdef DEBUG
  29.     freopen("input", "r", stdin);
  30.     //freopen("output", "w", stdout);
  31.     clock_t start = clock();
  32. #else
  33.  
  34.     freopen("taxi.in", "r", stdin);
  35.     freopen("taxi.out", "w", stdout);
  36. #endif
  37.     ios_base::sync_with_stdio(false);
  38.     int t = 1;
  39.     //cin >> t;
  40.     while (t--)
  41.         solve();
  42.  
  43. #ifdef DEBUG
  44.     //cout << "\n\n\nTime:" << ((clock() - start) / 1.0 / CLOCKS_PER_SEC);
  45. #endif
  46.     return 0;
  47. }
  48. /**
  49.  * Built using CHelper plug-in
  50.  * Actual solution is at the top
  51.  * @author RiaD
  52.  */
  53.  
  54. li a[501010];
  55.  
  56.      void solve() {
  57. 		li m,d,n;
  58. 		cin >> m >> d >> n;
  59.         for(int i = 0; i < n; ++i)
  60. 			cin >> a[i];
  61.  
  62.         sort(a, a + n);
  63.  
  64.         if(a[n - 1] >= d + m) {
  65.             cout << 1;
  66.             return;
  67.         }
  68.  
  69.         int badIndex = 0;
  70.         long goodPos = d;
  71.  
  72.         for(int i = 0; i <= n; ++i) {
  73.             if(i == n) {
  74.                 cout << 0;
  75.                 return;
  76.             }
  77.             if(a[i] >= m - d) {
  78.               //  System.err.println("bad " + a[i]);
  79.                 goodPos = (a[i] - (m - d)) / 2;
  80.                 badIndex = i;
  81.                 break;
  82.             }
  83.  
  84.         }
  85.  
  86.  
  87.  
  88.         long last = m - d;
  89.  
  90.         int ans = 1;
  91.         for(int i = n - 1; i >= 0; --i) {
  92.             if(i == badIndex)
  93.                 continue;
  94.             //System.err.println("see " + a[i]);
  95.             if(a[i] < d) {
  96.                 cout << 0;
  97.                 return;
  98.             }
  99.             d -= a[i] - d;
  100.  
  101.  
  102.             if(d <= -last) {
  103.                 cout << ans;
  104.  
  105.                 return;
  106.             }
  107.             ++ans;
  108.             if(d <= goodPos) {
  109.                 cout << ans;
  110.                 return;
  111.             }
  112.  
  113.         }
  114.  
  115.         cout << 0;
  116.  
  117.     }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/T8eZZ6
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!