fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef unsigned long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=500000+10;
  27.  
  28. LL m,d;
  29. int n;
  30. LL x[MAX];
  31.  
  32. int main()
  33. {
  34. //    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  35.     int i;
  36.     cin>>m>>d;
  37.     cin>>n;
  38.     REP(i,1,n)
  39.         cin>>x[i];
  40.     sort(x+1,x+n+1,greater<LL>());
  41.     if(x[1]<m-d)
  42.     {
  43.         printf("0\n");
  44.         return 0;
  45.     }
  46.     LL now=0;
  47.     for(i=1;i<=n;++i)
  48.         if(x[i]<m-d)
  49.             break;
  50.     int t=i-1;//the last one
  51.     for(i=1;i<=n;++i)
  52.     {
  53.         if(x[i]<(d-now))
  54.         {
  55.             printf("0\n");
  56.             return 0;
  57.         }
  58.         else
  59.         {
  60.             LL nd=now+x[i]-(d-now);
  61.             if(nd>=m)
  62.             {
  63.                 printf("%d\n",i);
  64.                 return 0;
  65.             }
  66.             if(i==t)
  67.                 continue;
  68.             if(nd<d)
  69.                 now=nd;
  70.             else
  71.             {
  72.                 printf("%d\n",i>t?i:i+1);
  73.                 return 0;
  74.             }
  75.         }
  76.         if(now+x[t]-(d-now)>=m && x[t]>=(d-now))
  77.         {
  78.             printf("%d\n",i>=t?i:i+1);
  79.             return 0;
  80.         }
  81.     }
  82.     printf("0\n");
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0s 7208KB
comments (?)
stdin
copy 
42 23 6
20 25 14 27 30 7
stdout
copy 
4
https://ideone.com/zDLNJw
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!