Submission #872760

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

joi2019_ho_t3

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

signed main(){
    int n; cin >> n;
    string s; cin >> s;
    //RGY
    map<int, vector<int>> pos;
    for(int i = 0; i < n; i++)
        pos[s[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;
    map<char, int> mp;
    mp['R']=0, mp['G']=1, mp['Y']=2;
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= pos['R'].size(); j++){
            for(int k = 0; k <= pos['G'].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(char last: {'R', 'G', 'Y'}) for(char next: {'R', 'G', 'Y'}) {
                    if(last == next) continue;
                    int x = mp[last], y = mp[next];
                    //cout << dp[i][j][k][x] << endl;
                    if(j < pos['R'].size() && next == 'R') 
                        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['G'].size() && next == 'G')
                        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['Y'].size() && next == 'Y')
                        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['R'].size()][pos['G'].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:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int j = 0; j <= pos['R'].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:23:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             for(int k = 0; k <= pos['G'].size(); k++){
      |                            ~~^~~~~~~~~~~~~~~~~~
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 |                     if(j < pos['R'].size() && next == 'R')
      |                        ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                     if(k < pos['G'].size() && next == 'G')
      |                        ~~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:34:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |                     if(i-j-k < pos['Y'].size() && next == 'Y')
      |                        ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25