Submission #742887

#	Time	Username	Problem	Language	Result	Execution time	Memory
742887		flappybird	Toilets (JOI16_toilets)	C++17	100 / 100	111 ms	9316 KiB

toilets

#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(ll 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();
	if (!n1.sum) return n1;
	node res;
	res.sum = n1.sum * x;
	if (n1.sum < 0) res.lmx = n1.lmx;
	else res.lmx = (x - 1) * n1.sum + n1.lmx;
	return res;
}
node gets(int s, int n = -1) {
	if (!~n) n = str[s].size();
	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 (str[i][j] == 'F') sfs++;
						else rem--;
						if (!rem) break;
					}
					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;
		assert((allf - N) * 2 == res.sum);
		if (res.lmx > lim) l = m;
		else r = m;
	}
	cout << r << ln;
}

Compilation message (stderr)

toilets.cpp: In function 'int main()':
toilets.cpp:72:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |   ll m = l + r >> 1;
      |          ~~^~~

• Subtask 1: 14 / 14
• Subtask 2: 22 / 22
• Subtask 3: 64 / 64