Submission #872761

#	Time	Username	Problem	Language	Result	Execution time	Memory
872761		scrge	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	558 ms	757528 KiB

joi2019_ho_t3

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")

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

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);

    int dp[n+1][n+1][n+1][3];
    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 (stderr)

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
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25