oj.uz

답안 #872782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872782 2023-11-13T18:49:49 Z scrge Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 345 ms 757532 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")

#include <bits/stdc++.h>
using namespace std;

int dp[401][401][401][3];
signed main(){
    int n; cin >> n;
    string s; cin >> s;
    //RGY
    map<char, int> mp;
    mp['R']=0, mp['G']=1, mp['Y']=2;

    vector<int> a(n);
    for(int i = 0; i < n; i++) a[i] = mp[s[i]];

    array<vector<int>, 3> pos;
    for(int i = 0; i < n; i++)
        pos[a[i]].push_back(i);

    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++) for(int l = 0; l < 3; l++){
        dp[i][j][k][l] = 1e9;
    }

    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0; 
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= pos[0].size(); j++){
            for(int k = 0; k <= pos[1].size(); k++){
                //printf("%d %d %d\n", i, j, k);
                //for(int l: {0, 1, 2}){ printf("dp(%d %d %d %d) = %d\n", i, j, k, l, dp[i][j][k][l]); }
                for(int last: {0, 1, 2}) for(int next: {0, 1, 2}) {
                    if(last == next) continue;
                    int x = last, y = next;
                    //cout << last << " " << next << " ";
                    //cout << x << " " << y << endl;
                    //cout << dp[i][j][k][x] << endl;
                    if(j < pos[0].size() && next == 0) 
                        dp[i+1][j+1][k][y] = min(dp[i+1][j+1][k][y], dp[i][j][k][x] + abs(pos[next][j] - i));
                    if(k < pos[1].size() && next == 1)
                        dp[i+1][j][k+1][y] = min(dp[i+1][j][k+1][y], dp[i][j][k][x] + abs(pos[next][k] - i));
                    if(i-j-k < pos[2].size() && next == 2)
                        dp[i+1][j][k][y] = min(dp[i+1][j][k][y], dp[i][j][k][x] + abs(pos[next][i-j-k] - i));
                }
            }
        }
    }
    //cout << "here\n";

    auto last = dp[n][pos[0].size()][pos[1].size()];
    int ans = min({last[0], last[1], last[2]});
    cout << ((ans == 1e9) ? -1 : ans/2) << endl;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(int j = 0; j <= pos[0].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:31:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             for(int k = 0; k <= pos[1].size(); k++){
      |                            ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                     if(j < pos[0].size() && next == 0)
      |                        ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                     if(k < pos[1].size() && next == 1)
      |                        ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |                     if(i-j-k < pos[2].size() && next == 2)
      |                        ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 20828 KB Output is correct
5 Correct 3 ms 29020 KB Output is correct
6 Correct 3 ms 29020 KB Output is correct
7 Correct 3 ms 29020 KB Output is correct
8 Correct 3 ms 29200 KB Output is correct
9 Correct 3 ms 29020 KB Output is correct
10 Correct 3 ms 29212 KB Output is correct
11 Incorrect 3 ms 29020 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 20828 KB Output is correct
5 Correct 3 ms 29020 KB Output is correct
6 Correct 3 ms 29020 KB Output is correct
7 Correct 3 ms 29020 KB Output is correct
8 Correct 3 ms 29200 KB Output is correct
9 Correct 3 ms 29020 KB Output is correct
10 Correct 3 ms 29212 KB Output is correct
11 Incorrect 3 ms 29020 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 345 ms 757532 KB Output is correct
3 Correct 262 ms 755284 KB Output is correct
4 Correct 258 ms 757528 KB Output is correct
5 Correct 268 ms 757320 KB Output is correct
6 Correct 251 ms 757332 KB Output is correct
7 Correct 249 ms 755724 KB Output is correct
8 Correct 247 ms 755284 KB Output is correct
9 Correct 253 ms 752712 KB Output is correct
10 Correct 245 ms 757288 KB Output is correct
11 Correct 246 ms 757332 KB Output is correct
12 Correct 65 ms 390288 KB Output is correct
13 Correct 91 ms 506552 KB Output is correct
14 Correct 154 ms 599456 KB Output is correct
15 Correct 226 ms 757324 KB Output is correct
16 Correct 229 ms 757328 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 20828 KB Output is correct
5 Correct 3 ms 29020 KB Output is correct
6 Correct 3 ms 29020 KB Output is correct
7 Correct 3 ms 29020 KB Output is correct
8 Correct 3 ms 29200 KB Output is correct
9 Correct 3 ms 29020 KB Output is correct
10 Correct 3 ms 29212 KB Output is correct
11 Incorrect 3 ms 29020 KB Output isn't correct
12 Halted 0 ms 0 KB -