oj.uz

Submission #209204

# Submission time Handle Problem Language Result Execution time Memory
209204 2020-03-13T11:48:33 Z ffao Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
75 / 100
 500 ms 148020 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 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 = 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()
{
    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:66: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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 5 ms 636 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 636 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 5 ms 632 KB Output is correct
15 Correct 5 ms 500 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 5 ms 376 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 5 ms 636 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 636 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 5 ms 632 KB Output is correct
15 Correct 5 ms 500 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 8 ms 4216 KB Output is correct
19 Correct 8 ms 3448 KB Output is correct
20 Correct 8 ms 4088 KB Output is correct
21 Correct 9 ms 4476 KB Output is correct
22 Correct 7 ms 2936 KB Output is correct
23 Correct 9 ms 3832 KB Output is correct
24 Correct 7 ms 2808 KB Output is correct
25 Correct 5 ms 1400 KB Output is correct
26 Correct 5 ms 1656 KB Output is correct
27 Correct 8 ms 4344 KB Output is correct
28 Correct 8 ms 4344 KB Output is correct
29 Correct 8 ms 4088 KB Output is correct
30 Correct 8 ms 4092 KB Output is correct
31 Correct 8 ms 3576 KB Output is correct
32 Correct 8 ms 4216 KB Output is correct
33 Correct 6 ms 1912 KB Output is correct
34 Correct 6 ms 2424 KB Output is correct
35 Correct 8 ms 4344 KB Output is correct
36 Correct 7 ms 3448 KB Output is correct
37 Correct 7 ms 3064 KB Output is correct
38 Correct 7 ms 3576 KB Output is correct
39 Correct 9 ms 4216 KB Output is correct
40 Correct 5 ms 504 KB Output is correct
41 Correct 5 ms 1404 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 9 ms 6648 KB Output is correct
3 Correct 9 ms 6648 KB Output is correct
4 Correct 9 ms 6776 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6776 KB Output is correct
7 Correct 8 ms 6648 KB Output is correct
8 Correct 8 ms 6776 KB Output is correct
9 Correct 8 ms 6644 KB Output is correct
10 Correct 8 ms 6652 KB Output is correct
11 Correct 8 ms 6648 KB Output is correct
12 Correct 6 ms 3576 KB Output is correct
13 Correct 7 ms 4728 KB Output is correct
14 Correct 8 ms 5624 KB Output is correct
15 Correct 8 ms 6648 KB Output is correct
16 Correct 9 ms 6648 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 5 ms 636 KB Output is correct
8 Correct 5 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 636 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 504 KB Output is correct
14 Correct 5 ms 632 KB Output is correct
15 Correct 5 ms 500 KB Output is correct
16 Correct 5 ms 380 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 8 ms 4216 KB Output is correct
19 Correct 8 ms 3448 KB Output is correct
20 Correct 8 ms 4088 KB Output is correct
21 Correct 9 ms 4476 KB Output is correct
22 Correct 7 ms 2936 KB Output is correct
23 Correct 9 ms 3832 KB Output is correct
24 Correct 7 ms 2808 KB Output is correct
25 Correct 5 ms 1400 KB Output is correct
26 Correct 5 ms 1656 KB Output is correct
27 Correct 8 ms 4344 KB Output is correct
28 Correct 8 ms 4344 KB Output is correct
29 Correct 8 ms 4088 KB Output is correct
30 Correct 8 ms 4092 KB Output is correct
31 Correct 8 ms 3576 KB Output is correct
32 Correct 8 ms 4216 KB Output is correct
33 Correct 6 ms 1912 KB Output is correct
34 Correct 6 ms 2424 KB Output is correct
35 Correct 8 ms 4344 KB Output is correct
36 Correct 7 ms 3448 KB Output is correct
37 Correct 7 ms 3064 KB Output is correct
38 Correct 7 ms 3576 KB Output is correct
39 Correct 9 ms 4216 KB Output is correct
40 Correct 5 ms 504 KB Output is correct
41 Correct 5 ms 1404 KB Output is correct
42 Correct 4 ms 376 KB Output is correct
43 Correct 9 ms 6648 KB Output is correct
44 Correct 9 ms 6648 KB Output is correct
45 Correct 9 ms 6776 KB Output is correct
46 Correct 8 ms 6648 KB Output is correct
47 Correct 8 ms 6776 KB Output is correct
48 Correct 8 ms 6648 KB Output is correct
49 Correct 8 ms 6776 KB Output is correct
50 Correct 8 ms 6644 KB Output is correct
51 Correct 8 ms 6652 KB Output is correct
52 Correct 8 ms 6648 KB Output is correct
53 Correct 6 ms 3576 KB Output is correct
54 Correct 7 ms 4728 KB Output is correct
55 Correct 8 ms 5624 KB Output is correct
56 Correct 8 ms 6648 KB Output is correct
57 Correct 9 ms 6648 KB Output is correct
58 Execution timed out 823 ms 148020 KB Time limit exceeded
59 Halted 0 ms 0 KB -