답안 #512586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
512586	2022-01-16T13:27:56 Z	Jarif_Rahman	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	500 ms	1048580 KB

joi2019_ho_t3

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int inf = 1e9+5;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; str ss; cin >> n >> ss;
    vector<int> s;
    for(int i = 0; i < n; i++){
        if(ss[i] == 'R') s.pb(0);
        if(ss[i] == 'G') s.pb(1);
        if(ss[i] == 'Y') s.pb(2);
    }

    vector<vector<int>> cnt(n, vector<int>(3, 0));
    vector<vector<int>> pos(3);
    vector<vector<vector<vector<int>>>> dp(n+1, vector<vector<vector<int>>>(n+1,
        vector<vector<int>>(n+1, vector<int>(3, inf))));

    for(int i = n-1; i >= 0; i--){
        pos[s[i]].pb(i);
        if(i != n-1) cnt[i][0] = cnt[i+1][0], cnt[i][1] = cnt[i+1][1], cnt[i][2] = cnt[i+1][2];
        cnt[i][s[i]]++;
    }

    for(int i = n-1; i >= 0; i--){
        int c[3];
        for(c[0] = 0; c[0] <= n-i; c[0]++) for(c[1] = 0; c[1]+c[0] <= n-i; c[1]++){
            c[2] = n-i-c[0]-c[1];
            for(int cl = 0; cl < 3; cl++){
                if(c[cl] == 0) continue;
                if(c[cl] > pos[cl].size()) continue;
                vector<int> o;
                for(int j = 0; j < 3; j++) if(j != cl) o.pb(j);
                for(int j = 0; j < 2; j++){
                    int cur = 0;
                    c[cl]--;
                    if(i != n-1) cur+=dp[i+1][c[0]][c[1]][o[j]];
                    c[cl]++;
                    if(i == n-1) cur+=abs(pos[cl][c[cl]-1]-i);
                    else cur+=abs(pos[cl][c[cl]-1]-max(0, c[o[0]]-cnt[pos[cl][c[cl]-1]][o[0]])
                        -max(0, c[o[1]]-cnt[pos[cl][c[cl]-1]][o[1]])-i);

                    dp[i][c[0]][c[1]][cl] = min(dp[i][c[0]][c[1]][cl], cur);
                }
            }
        }
    }
    int ans = inf;
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int c = 0; c < 3; c++)
        ans = min(ans, dp[0][i][j][c]);
    if(ans >= inf) ans = -1;
    cout << ans << "\n";
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |                 if(c[cl] > pos[cl].size()) continue;
      |                    ~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	440 KB	Output is correct
6	Correct	1 ms	436 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	1 ms	564 KB	Output is correct
9	Correct	1 ms	464 KB	Output is correct
10	Correct	1 ms	564 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	1 ms	568 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	444 KB	Output is correct
16	Correct	1 ms	460 KB	Output is correct
17	Correct	1 ms	436 KB	Output is correct

Subtask #2
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	440 KB	Output is correct
6	Correct	1 ms	436 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	1 ms	564 KB	Output is correct
9	Correct	1 ms	464 KB	Output is correct
10	Correct	1 ms	564 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	1 ms	568 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	444 KB	Output is correct
16	Correct	1 ms	460 KB	Output is correct
17	Correct	1 ms	436 KB	Output is correct
18	Correct	24 ms	13004 KB	Output is correct
19	Correct	20 ms	13008 KB	Output is correct
20	Correct	21 ms	13080 KB	Output is correct
21	Correct	21 ms	13008 KB	Output is correct
22	Correct	21 ms	13004 KB	Output is correct
23	Correct	21 ms	13004 KB	Output is correct
24	Correct	21 ms	13088 KB	Output is correct
25	Correct	19 ms	13084 KB	Output is correct
26	Correct	19 ms	13004 KB	Output is correct
27	Correct	21 ms	13012 KB	Output is correct
28	Correct	20 ms	13004 KB	Output is correct
29	Correct	24 ms	13004 KB	Output is correct
30	Correct	20 ms	13004 KB	Output is correct
31	Correct	20 ms	13004 KB	Output is correct
32	Correct	21 ms	13084 KB	Output is correct
33	Correct	20 ms	12492 KB	Output is correct
34	Correct	20 ms	12492 KB	Output is correct
35	Correct	19 ms	11872 KB	Output is correct
36	Correct	20 ms	12492 KB	Output is correct
37	Correct	17 ms	11296 KB	Output is correct
38	Correct	20 ms	13004 KB	Output is correct
39	Correct	20 ms	13084 KB	Output is correct
40	Correct	18 ms	12364 KB	Output is correct
41	Correct	19 ms	12956 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Execution timed out	842 ms	1048580 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	440 KB	Output is correct
6	Correct	1 ms	436 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	1 ms	564 KB	Output is correct
9	Correct	1 ms	464 KB	Output is correct
10	Correct	1 ms	564 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	1 ms	568 KB	Output is correct
14	Correct	1 ms	460 KB	Output is correct
15	Correct	1 ms	444 KB	Output is correct
16	Correct	1 ms	460 KB	Output is correct
17	Correct	1 ms	436 KB	Output is correct
18	Correct	24 ms	13004 KB	Output is correct
19	Correct	20 ms	13008 KB	Output is correct
20	Correct	21 ms	13080 KB	Output is correct
21	Correct	21 ms	13008 KB	Output is correct
22	Correct	21 ms	13004 KB	Output is correct
23	Correct	21 ms	13004 KB	Output is correct
24	Correct	21 ms	13088 KB	Output is correct
25	Correct	19 ms	13084 KB	Output is correct
26	Correct	19 ms	13004 KB	Output is correct
27	Correct	21 ms	13012 KB	Output is correct
28	Correct	20 ms	13004 KB	Output is correct
29	Correct	24 ms	13004 KB	Output is correct
30	Correct	20 ms	13004 KB	Output is correct
31	Correct	20 ms	13004 KB	Output is correct
32	Correct	21 ms	13084 KB	Output is correct
33	Correct	20 ms	12492 KB	Output is correct
34	Correct	20 ms	12492 KB	Output is correct
35	Correct	19 ms	11872 KB	Output is correct
36	Correct	20 ms	12492 KB	Output is correct
37	Correct	17 ms	11296 KB	Output is correct
38	Correct	20 ms	13004 KB	Output is correct
39	Correct	20 ms	13084 KB	Output is correct
40	Correct	18 ms	12364 KB	Output is correct
41	Correct	19 ms	12956 KB	Output is correct
42	Correct	0 ms	204 KB	Output is correct
43	Execution timed out	842 ms	1048580 KB	Time limit exceeded
44	Halted	0 ms	0 KB	-

답안 #512586

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 55.0 / 55.0

Subtask #3 0 / 15.0

Subtask #4 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
55.0 / 55.0

Subtask #3
0 / 15.0

Subtask #4
0 / 25.0