Submission #901632

#	Time	Username	Problem	Language	Result	Execution time	Memory
901632		jay_jayjay	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	1 ms	600 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()

#define infl 0x3f3f3f3f3f3f3f3f
#define ll long long

int main()
{
        int n; string s; cin>>n>>s;

        int rc = count(all(s),'R');
        int gc = count(all(s),'G');
        int yc = count(all(s),'Y');

        if(0)bad:{printf("-1\n");return 0;}
        if(yc > rc+gc+1) goto bad;
        if(gc > rc+yc+1) goto bad;
        if(rc > yc+gc+1) goto bad;
        assert(yc==0);

        string sr(n,'R'),sg(n,'G');

        for(int i=1;i<n;i+=2) sr[i]='G',sg[i]='R';

        auto solve = [&](string t) -> ll {
                if(count(all(t),'R')!=rc) return infl;
                if(count(all(t),'G')!=gc) return infl;
                int ri=0,gi=0;
                while(ri<n&&s[ri]!='R')ri++;
                while(gi<n&&s[gi]!='G')gi++;
                ll p=0;
                for(int i=0;i<n;i++) {
                        //printf("find %d: ri=%d gi=%d\n",i,ri,gi);
                        if(t[i] == 'R') {
                                p += abs(i-ri);
                                ri++; while(ri<n&&s[ri]!='R')ri++;
                        }
                        else {
                                p += abs(i-gi);
                                gi++; while(gi<n&&s[gi]!='G')gi++;
                        }
                }
                //cout<<s<<' '<<t<<' '<<p<<endl;
                return p/2;
        };

        ll mn= infl;
        mn=min(mn,solve(sr));
        mn=min(mn,solve(sg));
        if(mn == infl) goto bad;
        printf("%lld\n",mn);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25