Submission #10956

#	Time	Username	Problem	Language	Result	Execution time	Memory
10956		dohyun0324	JOIOJI (JOI14_joioji)	C++98	100 / 100	48 ms	14764 KiB

joioji

#include<stdio.h>
#include<map>
using namespace std;
map<long long,long long>m;
char s[200010];
long long int p,len,dap,a[200010],b[200010],c[200010];
long long int arr1[200010],arr2[200010];
int main()
{
    int i;
    scanf("%lld",&len);
    scanf("%s",s);
    for(i=0;i<len;i++)
    {
        a[i]=a[i-1]; b[i]=b[i-1]; c[i]=c[i-1];
        if(s[i]=='J') a[i]=a[i-1]+1;
        if(s[i]=='O') b[i]=b[i-1]+1;
        if(s[i]=='I') c[i]=c[i-1]+1;
    }
    for(i=0;i<len;i++) arr1[i]=a[i]-b[i]+100000, arr2[i]=b[i]-c[i]+100000;
    for(i=0;i<len;i++)
    {
        if(arr1[i]==100000 && arr2[i]==100000 && dap<i+1) dap=i+1;
    }
    for(i=0;i<len;i++)
    {
        if(m[arr1[i]*1000000+arr2[i]])
        {
            p=m[arr1[i]*1000000+arr2[i]]-1;
            if(dap<i-p) dap=i-p;
        }
        else m[arr1[i]*1000000+arr2[i]]=i+1;
    }
    printf("%lld",dap);
    return 0;
}

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