fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int64_t slv(int64_t x) {
  5.     if(x < 5) return 0;
  6.     x -= 5;
  7.     static int c[] = {0, -1, 0};
  8.     return x / 3 + 1 + c[x % 3];
  9. }
  10.  
  11. const int N = 1e7 + 1, EN = 664579;
  12. int pc, prm[EN];
  13. int spf[N];
  14.  
  15. auto pre_Sieve = []() {
  16.     for (int i = 2; i < N; i++) {
  17.         if (!spf[i]) spf[i] = prm[pc++] = i;
  18.         for (int j = 0; i * prm[j] < N; j++) {
  19.             spf[i * prm[j]] = prm[j];
  20.             if (spf[i] == prm[j]) break;
  21.         }
  22.     }
  23.     return 0;
  24. }();
  25.  
  26. void TC() {
  27.     int n;
  28.     int64_t x;
  29.     cin >> n >> x;
  30.     int ans = 0;
  31.     for(int i = 0, y; i < n; i++) {
  32.         cin >> y;
  33.         if(x < 4) {
  34.             ans += y <= x;
  35.             if (x < y) x -= y;
  36.             continue;
  37.         }
  38.         int64_t limit = x / 2;
  39.         if(y <= x) {
  40.             ans++;
  41.             int best = y / 2 + 1;
  42.             if(y < limit) {
  43.                 x += y;
  44.             }
  45.             else if(best <= limit)
  46.                 x += y % best;
  47.             else
  48.                 x += slv(y);
  49.         }
  50.         else {
  51.             x -= spf[y] > limit;
  52.         }
  53.     }
  54.     cout << ans << '\n';
  55. }
  56.  
  57. int32_t main() {
  58.     ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  59.     int tc = 1;
  60.     cin >> tc;
  61.     for (int test = 1; test <= tc; ++test) {
  62.         TC();
  63.     }
  64.     //    cerr << clock() / 1000.0 << " Secs";
  65.     return 0;
  66. }
Success #stdin #stdout 0.06s 45264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/eEl56A
language:
C++14 (gcc 8.3)
created:
1 day 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!