Dhiraj-01

make one's

Jun 14th, 2021 (edited)
298
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. Problem link:
  2. https://www.hackerearth.com/challenges/college/csi-2019/algorithm/c22462cde5b64cf7a353ea0305e89f13/
  3.  
  4. is this greedy solution correct ?
  5. if x < y then always swap and collect zero together (total swap * x + y)
  6. else just flip all consequitive zero to one (total consequitive zero * y)
  7.  
  8. void solve(ll &tc)
  9. {
  10.     ll n, x, y;
  11.     cin >> n >> x >> y;
  12.  
  13.     string s;
  14.     cin >> s;
  15.  
  16.     vector<pair<char, ll>> a;
  17.     for(ll i = 0; i < n; i++) {
  18.         if(a.empty() or a.back().first != s[i]) {
  19.             a.push_back({s[i], 1});
  20.         }
  21.         else {
  22.             a.back().second++;
  23.         }
  24.     }
  25.     ll ans = 0;
  26.     if(x < y) {
  27.         for(ll i = 1; i + 1 < a.size(); i++) {
  28.             if(a[i].first == '1') {
  29.                 ans += x;
  30.             }
  31.         }
  32.         ans += y;
  33.     }
  34.     else {
  35.         for(ll i = 0; i < a.size(); i++) {
  36.             if(a[i].first == '0') {
  37.                 ans += y;
  38.             }
  39.         }
  40.     }
  41.     cout << ans << endl;
  42. }
Advertisement
Add Comment
Please, Sign In to add comment