oj.uz

Submission #209203

# Submission time Handle Problem Language Result Execution time Memory
209203 2020-03-13T11:45:35 Z ffao Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 500 ms 809848 KB 
#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 all(v) (v).begin(), (v).end()

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

int n;
char s[500];

vector<int> locs[3];
int dp[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 (ret == -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 = 0;
            for (int ot = 0; ot < 3; ot++) {
                hm += max(0, (int)(lower_bound(all(locs[ot]), this_pos) - locs[ot].begin()) - 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()
{
    memset(dp,-1,sizeof(dp));
    re(n);
    re(s);
    rep(i,0,n) {
        if (s[i]=='R') locs[0].push_back(i);
        else if (s[i]=='G') locs[1].push_back(i);
        else locs[2].push_back(i);
    }

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

int main() {

    solve();
}

Compilation message

joi2019_ho_t3.cpp: In function 'int rec(int, int, int, int)':
joi2019_ho_t3.cpp:64: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 538 ms 809548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 538 ms 809548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 809528 KB Output is correct
2 Correct 435 ms 809532 KB Output is correct
3 Correct 452 ms 809720 KB Output is correct
4 Correct 423 ms 809848 KB Output is correct
5 Correct 426 ms 809712 KB Output is correct
6 Correct 419 ms 809728 KB Output is correct
7 Correct 411 ms 809720 KB Output is correct
8 Correct 420 ms 809592 KB Output is correct
9 Correct 416 ms 809720 KB Output is correct
10 Correct 420 ms 809592 KB Output is correct
11 Correct 426 ms 809592 KB Output is correct
12 Correct 418 ms 809660 KB Output is correct
13 Correct 427 ms 809592 KB Output is correct
14 Correct 417 ms 809848 KB Output is correct
15 Correct 418 ms 809592 KB Output is correct
16 Correct 420 ms 809596 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 538 ms 809548 KB Time limit exceeded
2 Halted 0 ms 0 KB -