Submission #209205

#	Time	Username	Problem	Language	Result	Execution time	Memory
209205		ffao	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	306 ms	181368 KiB

joi2019_ho_t3

#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <memory.h>
#include <cmath>
#include <array>

using namespace std;

void re(int& x);

void re(char* c);

void pr(int x);

void pr(const char *x);

void ps();
template<class T, class... Ts> void ps(const T& t, const Ts&... ts);

#ifdef FFDBG

#else
#define dbg(x...) dsfdsfsdfasd
#endif

void re(int& x) { scanf("%d", &x); }

void re(char* c) { scanf("%s", c); }

void pr(int x) { printf("%d", x); }

void pr(const char *x) { printf("%s", x); }

void ps() { pr("\n"); }
template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
    pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
}

#define rep(i, a, b) for(int i = a; i < (b); ++i)

int n;
char s[500];

vector<int> locs[3];
int ct[3][410];
int dp[410][410][410][3];
int sn[410][410][410][3];

int rec(int l1, int l2, int l3, int p) {
    //dbg(l1,l2,l3,p);
    if (l1+l2+l3==n) return 0;
    int l[3] = {l1,l2,l3};
    int &ret = dp[l1][l2][l3][p];

    if (!sn[l1][l2][l3][p]) {
        sn[l1][l2][l3][p]=1;
        ret = 1000000000;

        for (int nxt = 0; nxt < 3; nxt++) if ((l1+l2+l3 ==0||nxt != p) && l[nxt] != locs[nxt].size()) {
            int this_pos = locs[nxt][l[nxt]];

            int hm = -1;
            for (int ot = 0; ot < 3; ot++) {
                hm += max(0, ct[ot][this_pos] - l[ot]);
            }

            l[nxt]++;
            //dbg(l1,l2,l3,p,nxt,hm);
            ret = min(ret, hm + rec(l[0],l[1],l[2],nxt));
            l[nxt]--;
        }
    }
    return ret;
}

void solve()
{
    re(n);
    re(s);
    rep(i,0,n) {
        if (i!=0) rep(j,0,3) ct[j][i] = ct[j][i-1];
        if (s[i]=='R') {
            locs[0].push_back(i);
            ct[0][i]++;
        }
        else if (s[i]=='G') {
            ct[1][i]++;
            locs[1].push_back(i);
        }
        else {
            ct[2][i]++;
            locs[2].push_back(i);
        }
    }

    int ans = rec(0,0,0,0);
    ps(ans == 1000000000 ? -1 : ans);
}

int main() {

    solve();
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int rec(int, int, int, int)':
joi2019_ho_t3.cpp:65:82: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int nxt = 0; nxt < 3; nxt++) if ((l1+l2+l3 ==0||nxt != p) && l[nxt] != locs[nxt].size()) {
                                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void re(int&)':
joi2019_ho_t3.cpp:32:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void re(int& x) { scanf("%d", &x); }
                   ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp: In function 'void re(char*)':
joi2019_ho_t3.cpp:34:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void re(char* c) { scanf("%s", c); }
                    ~~~~~^~~~~~~~~

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