fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. #define ar array
  7. #define ll long long
  8. #define ld long double
  9. #define sza(x) ((int)x.size())
  10. #define all(a) (a).begin(), (a).end()
  11. #define nl cout << '\n';
  12. #define str string
  13. #define YES cout << "YES\n";
  14. #define NO cout << "NO\n";
  15. #define fxd(n) fixed << setprecision(n) // cout
  16. #define pi 3.14159265359
  17. #define loopr(i, a, b) for(int i = a; i <= b; ++i)
  18. #define loop(i, n) for(int i = 0; i < n; ++i)
  19. #define sorts(X) sort(X.begin(), X.end())
  20. #define sortt(X, n) sort(X, X + n)
  21. #define rev(X, n) reverse(X, X + n)
  22. #define all(X) X.begin(), X.end()
  23. #define sz size()
  24. #define F first
  25. #define S second
  26.  
  27. const int MAX_N = 1e5 + 5;
  28. const ll MOD = 1e9 + 7;
  29. const ll INF = 1e9;
  30. const ld EPS = 1e-9;
  31.  
  32. // parts so that in the left part the number of ones is at least the total number of twos and threes
  33. // middle part the total number of ones and twos is at least the number of threes
  34. // right part can be anything, but it must be non-empty
  35.  
  36.  
  37.  
  38.  
  39. void solve() {
  40.  
  41.     int n ; cin>>n;
  42.  
  43.     vector<int>  st ;
  44.     vector<int> v(n+1) ;
  45.  
  46.     vector<int> pf1(n+1);
  47.     vector<int> pf2(n+1);
  48.  
  49.  
  50.  
  51.     for (int i = 1; i <= n ; i++)
  52.     {
  53.         cin>>v[i];
  54.  
  55.         if(v[i]==1){
  56.  
  57.             pf1[i]=1;
  58.         }else{
  59.             pf1[i]=-1;
  60.         }
  61.  
  62.         if(v[i]==3){
  63.  
  64.             pf2[i]=-1;
  65.         }else{
  66.             pf2[i]=1;
  67.         }
  68.  
  69.     }
  70.  
  71.     for (int i = 1; i < n ; i++){
  72.  
  73.         pf1[i]+=pf1[i-1];
  74.         pf2[i]+=pf2[i-1];
  75.  
  76.     }
  77.  
  78.     // for (int i = 1; i <= n ; i++)
  79.     // {
  80.     //     cout<<pf1[i]<<' ';
  81.     // }
  82.  
  83.     // cout<<'\n';
  84.  
  85.     // for (int i = 1; i <= n ; i++)
  86.     // {
  87.     //     cout<<pf2[i]<<' ';
  88.     // }
  89.  
  90.  
  91.     for (int i = 1; i < n - 1; i++)
  92.     {
  93.  
  94.         if(pf1[i]>=0){
  95.  
  96.  
  97.             for (int j = i+1 ; j<n ; j++)
  98.             {
  99.  
  100.  
  101.                 if((pf2[j]-pf2[i])>=0){
  102.  
  103.                     YES
  104.                     return ;
  105.                 }
  106.  
  107.             }
  108.  
  109.  
  110.  
  111.         }
  112.     }
  113.  
  114.     NO
  115.  
  116. }
  117.  
  118. int main() {
  119.     ios_base::sync_with_stdio(0);
  120.     cin.tie(0); cout.tie(0);
  121.     int tc = 1;
  122.     cin >> tc;
  123.     for (int t = 1; t <= tc; t++) {
  124.         // cout << "Case #" << t << ": ";
  125.         solve();
  126.     }
  127. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/LbHQ98
language:
C++14 (gcc 8.3)
created:
6 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!