Submission #1222392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222392		12345678	Toilets (JOI16_toilets)	C++20	100 / 100	13 ms	4168 KiB

toilets

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=1e5+5;

ll n, m, cnt[nx], sm, mnpref;
string s[nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=m; i++) cin>>s[i]>>cnt[i];
    for (int i=m; i>=1; i--)
    {
        ll sz=s[i].size(), cursm=0, curmn=0;
        for (int j=sz-1; j>=0; j--)
        {
            if (s[i][j]=='F') cursm++;
            else cursm--;
            curmn=min(curmn, cursm);
        }
        mnpref=min({mnpref, sm+curmn, sm+(cnt[i]-1)*cursm+curmn});
        sm+=cursm*cnt[i];
        //cout<<"debug "<<sm<<' '<<mnpref<<'\n';
    }
    if (sm<0) cout<<-1;
    else cout<<max(0ll, -1-mnpref);
}

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