fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. #ifdef JASPER
  6. #include "debug.h"
  7. #else
  8. #define debug(...) 166
  9. #endif
  10.  
  11. const int N = 3e5 + 10;
  12. ll v[N], c[N];
  13.  
  14. string solve() {
  15.     ll a, b, n;
  16.  
  17.     string s;
  18.     cin >> n >> a >> b >> s;
  19.  
  20.     ll on = 0, off = 0;
  21.  
  22.     for (auto x : s) {
  23.         if (x == '0') off++; else 
  24.             on++;
  25.     }
  26.  
  27.     vector <bool> dp(101, 0);
  28.  
  29.     dp[off] = 1;
  30.  
  31.     queue <int> q;
  32.     q.push(off);
  33.  
  34.     while (q.size()) {
  35.         int t = q.front();
  36.         q.pop();
  37.         for (int i = a; i <= b; i++) {
  38.             for (int j = 0; j <= i; j++) {
  39.                 if (j <= t && i - j <= n - t) {
  40.                     int nx = t - j + (i - j);
  41.                     if (dp[nx])
  42.                         continue;
  43.  
  44.                     dp[nx] = 1;
  45.                     q.push(nx);
  46.                 }
  47.             }
  48.         }
  49.     }
  50.  
  51.     for (int i = a; i <= b; i++)
  52.         if (dp[i])
  53.             return "YES";
  54.  
  55.     return "NO";
  56. }
  57.  
  58. int main(){
  59.     ios_base::sync_with_stdio(false); 
  60.     cin.tie(NULL);
  61.     cout.tie(NULL);
  62.  
  63.     int t = 1;
  64.     cin >> t;
  65.  
  66.  
  67.     while (t--) {
  68.         //solve();
  69.         cout << solve() << "\n";
  70.     }
  71. }
  72.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO
https://ideone.com/jm8p5G
language:
C++14 (gcc 8.3)
created:
5 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!