fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define endl '\n'
  4. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  5. #define infi INT_MAX
  6. #define rinfi INT_MIN
  7. #define inf LLONG_MAX
  8. #define rinf LLONG_MIN
  9. #define ff first
  10. #define ss second
  11. #ifndef ONLINE_JUDGE
  12. #define line cout<<"here - "<<__LINE__<<"\n";
  13. #define dbg(a) cout<<#a<<" --> "<<(a)<<"\n";
  14. #define db(a,b) cout<<#a<<" --> "<<(a)<<"\n";cin>>b;
  15. #else
  16. #define line
  17. #define dbg(a)
  18. #define db(a,b)
  19. #endif
  20. char _;
  21. using namespace std;
  22. const int mx=1e6+10;
  23. int dp[mx][5];
  24. main()
  25. {
  26.     fast
  27.     int tc=1;
  28.     while(tc--)
  29.     {
  30.         int a, b;
  31.         cin>>a>>b;
  32.         string s, t;
  33.         cin>>s>>t;
  34.  
  35.         int ma = 0;
  36.         for(int i = 0; i < a; i++) if(s[i]=='0') ma++;
  37.         for(int i = 0; i < a; i++) if(t[i]=='0') ma++;
  38.  
  39.         if(s[0]=='0' && t[0]=='0') dp[0][2]=1;
  40.         for(int i = 1; i < a; i++)
  41.         {
  42.             for(int j = 0; j < 3; j++) dp[i][j] = dp[i-1][j];
  43.  
  44.             if(s[i]=='0' &&  s[i-1]=='0')
  45.             {
  46.                 dp[i][0] = max(dp[i][0], 1 + dp[i-1][1]);
  47.                 if(i-2 >= 0) dp[i][0] = max(dp[i][0], 1 + dp[i-2][2]);
  48.             }
  49.             if(t[i]=='0' &&  t[i-1]=='0')
  50.             {
  51.                 dp[i][1] = max(dp[i][1], 1 + dp[i-1][0]);
  52.                 if(i-2 >= 0) dp[i][1] = max(dp[i][1], 1 + dp[i-2][2]);
  53.             }
  54.             if(s[i]=='0' && t[i]=='0') dp[i][2] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]}) + 1;
  55.         }
  56.  
  57.         int ans = 0;
  58.         for(int j = 0; j < 3; j++) ans=max(ans,dp[a-1][j]);
  59.         while(b--)
  60.         {
  61.             int x, y;
  62.             cin>>x>>y;
  63.             int ok = 1;
  64.             if(((x*2)+y) > ma || x > ans) ok=0;
  65.             if(ok) cout<<"YES"<<endl;
  66.             else cout<<"NO"<<endl;
  67.         }
  68.  
  69.     }
  70. }
Success #stdin #stdout 0s 5520KB
comments (?)
stdin
copy 
6 3
000000
010010
3 4
4 3
4 2
stdout
copy 
YES
NO
YES
https://ideone.com/yLPpmN
language:
C++14 (gcc 8.3)
created:
2 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!