fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define endl '\n'
  4. #define se second
  5. #define int long long
  6. #define getName(x) #x
  7. #define vi std::vector<int>
  8. #define isz(v) (int) v.size()
  9. #define pii std::pair<int, int>
  10. #define all(v) v.begin(), v.end()
  11. #define loop cerr << "here" << endl;
  12. #define breakLoop if(TIME > 1) break;
  13. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  14. using namespace std;
  15. typedef long long ll;
  16.  
  17.  
  18. template <typename T> void maximize(T &a, T b){if(a < b) a = b;}
  19. template <typename T> void minimize(T &a, T b){if(a > b) a = b;}
  20. const int MAXN = 4e5 + 7;
  21. const int inf32 = 1e9;
  22.  
  23. int f[MAXN], a[MAXN], n, t, x, y, z;
  24. int cur1[3];
  25. int cur2[3];
  26.  
  27. bool valid(int a, int b, int c){
  28.     cur1[0]=a,cur1[1]=b,cur1[2]=c;
  29.     int p[3] = {cur2[0], cur2[1], cur2[2]};
  30.     do{
  31.         bool check = 1;
  32.         int curSum = 0, curIdx = 0;
  33.         for(int i = 0; i < 3; i++){
  34.             int val = cur1[i];
  35.             while(curSum < val and curIdx < 3){
  36.                 curSum += p[curIdx];
  37.                 curIdx++;
  38.             }
  39.             if(curSum >= val){
  40.                 curSum = 0;
  41.                 continue;
  42.             }
  43.             check = 0;
  44.             break;
  45.         }
  46.         if(check) return 1;
  47.     }while(next_permutation(p, p + 3));
  48.     return 0;
  49. }
  50.  
  51. signed main(){
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(nullptr);
  54.     #define task "fight"
  55.     if (fopen(task".inp", "r")){
  56.         freopen(task".inp", "r", stdin);
  57.         freopen(task".out", "w", stdout);
  58.     }
  59.  
  60.     cin >> t;
  61.     //t = min(t, 400005);
  62.     while(t--){
  63.         cin >> n;
  64.         cin >> x >> y >> z;
  65.         for(int i = 1; i <= n; i++) cin >> a[i];
  66. //        if(x > y) swap(x, y);
  67. //        if(y > z) swap(y, z);
  68. //        if(x > z) swap(x, z);
  69.         fill(f + 1, f + 1 + n, inf32);
  70.         cur2[0]=x,cur2[1]=y,cur2[2]=z;
  71.         sort(cur2, cur2 + 3);
  72.         for(int i = 1; i <= n; i++){
  73.             if(f[i - 1] != inf32 and valid(0, 0, a[i])) f[i] = f[i - 1] + 1;
  74.             if(i > 1 and f[i - 2] != inf32 and valid(0, a[i - 1], a[i])) minimize(f[i], f[i - 2] + 1);
  75.             if(i > 2 and f[i - 3] != inf32 and valid(a[i - 2], a[i - 1], a[i]))minimize(f[i], f[i - 3] + 1);
  76.         }
  77.         cout << (f[n] == inf32 ? -1 : f[n]) << ' ';
  78.     }
  79.  
  80.  
  81. }
  82.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FMzo9w
language:
C++14 (gcc 8.3)
created:
2 days 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!