fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<ll,ll> pll;
  5.  
  6. pll mergeSeg(pll a, pll b) {
  7.     return { max(a.first, a.second + b.first), a.second + b.second };
  8. }
  9.  
  10. int main(){
  11.     ios::sync_with_stdio(false);
  12.     cin.tie(nullptr);
  13.  
  14.     ll N; int M;
  15.     cin >> N >> M;
  16.  
  17.     pll cur = {0,0}; // (max_prefix, sum)
  18.     for(int i=0;i<M;i++){
  19.         string s; ll k;
  20.         cin >> s >> k;
  21.         ll sum = 0, mx = 0;
  22.         for(char c : s){
  23.             sum += (c=='F' ? 1 : -1);
  24.             mx = max(mx, sum);
  25.         }
  26.         pll block = {mx, sum};
  27.  
  28.         // binary lifting 방식으로 block^k 병합
  29.         pll pw = block;
  30.         for(int bit=0; (1LL<<bit) <= k; bit++){
  31.             if(k & (1LL<<bit)) cur = mergeSeg(cur, pw);
  32.             pw = mergeSeg(pw, pw);
  33.         }
  34.     }
  35.  
  36.     if(cur.second < 0) { // sum < 0 → 불가능
  37.         cout << -1 << "\n";
  38.         return 0;
  39.     }
  40.     ll ans = max(0LL, cur.first - cur.second - 1);
  41.     cout << ans << "\n";
  42.     return 0;
  43. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
6
1
6
4
M 1
F 2
FM 2
MFFFM 1 1
stdout 
-1
https://ideone.com/G88KiL
language:
C++ (gcc 8.3)
created:
22 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!