Submission #156036

#	Time	Username	Problem	Language	Result	Execution time	Memory
156036		souhhcong	JOIOJI (JOI14_joioji)	C++14	100 / 100	73 ms	8584 KiB

joioji

#include <iostream>
#include <map>
#include <stdio.h>
#include <string.h>

using namespace std;

const int N = 2e5+5;
const long long mpI = 1000000007, mpO = 100000009, mpJ = -(mpI+mpO);
int n, ans = 0;
string s;
long long pref[N], a[N];
int cnt[30];
map<long long,int> check;

int main()
{
    cin >> n >> s;
    if (n <= 4000)
    {
        for (int i = 0; i < n; i++)
        {
            memset(cnt,0,sizeof cnt);
            for (int j = i; j < n; j++)
            {
                cnt[s[j]-'A']++;
                if (cnt['I'-'A'] == cnt['O'-'A'] && cnt['I'-'A'] == cnt['J'-'A'])
                    ans = max(ans,j-i+1);
            }
        }
        return cout << ans, 0;
    }
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'I') a[i+1] = mpI;
        else if (s[i] == 'O') a[i+1] = mpO;
        else a[i+1] = mpJ;
    }
    for (int i = 1; i <= n; i++)
    {
        pref[i] = pref[i-1] + a[i];
        if (check[pref[i]])
        {
            ans = max(ans,i-check[pref[i]]);
        }
        else
            check[pref[i]] = i;
    }
    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80