#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
string str[MAX];
ll K[MAX];
int fs[MAX];
int ms[MAX];
struct node {
ll sum = 0;
ll lmx = 0;
node(int x = 0) { sum = lmx = x; }
};
node operator+(node n1, node n2) {
node ret;
ret.sum = n1.sum + n2.sum;
ret.lmx = max(n1.lmx, n1.sum + n2.lmx);
return ret;
}
node operator*(node n1, ll x) {
if (!x) return node();
node res = n1 * (x / 2);
res = res + res;
if (x & 1) res = n1 + res;
return res;
}
node gets(int s, int n = -1) {
if (!~n) n = str[s].size() + 1;
int i;
node ret;
for (i = 0; i <= n; i++) {
if (str[s][i] == 'M') ret = ret + node(-1);
else ret = ret + node(1);
}
return ret;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
ll N;
int M;
cin >> N >> M;
int i, j;
ll allf = 0;
for (i = 1; i <= M; i++) {
cin >> str[i] >> K[i];
for (auto v : str[i]) if (v == 'F') fs[i]++;
ms[i] = str[i].size() - fs[i];
allf += 1ll * fs[i] * K[i];
}
if (allf < N) {
cout << -1 << ln;
return 0;
}
ll lim = (allf - N) * 2 + 1;
ll l, r;
l = -1;
r = N * 2 - allf;
while (r - l > 1) {
ll m = l + r >> 1;
ll rem = m;
node res = node();
int isend = 0;
for (i = M; i >= 1; i--) {
if (isend) {
res = (gets(i) * K[i]) + res;
continue;
}
if (rem >= 1ll * ms[i] * K[i]) {
rem -= 1ll * ms[i] * K[i];
res = res + node(fs[i] * K[i]);
}
else {
ll n = rem / ms[i];
rem -= 1ll * ms[i] * n;
res = res + node(fs[i] * n);
if (rem) {
int sfs = 0;
for (j = str[i].size() - 1; j >= 0; j--) {
if (!rem) break;
if (str[i][j] == 'F') sfs++;
else rem--;
}
res = gets(i, j) + node(sfs) + res;
res = gets(i) * (K[i] - n - 1) + res;
}
else res = gets(i) * (K[i] - n) + res;
isend = 1;
}
}
res = node(-m) + res;
if (res.lmx > lim) l = m;
else r = m;
}
cout << r << ln;
}
Compilation message
toilets.cpp: In function 'int main()':
toilets.cpp:70:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | ll m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
6612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
6612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 2 |
Correct |
3 ms |
6612 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
6612 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
