Submission #218967

#	Time	Username	Problem	Language	Result	Execution time	Memory
218967		Rakhmand	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	165 ms	163064 KiB

joi2019_ho_t3

//  I feel still alive.
//  Created by existence on 18/04/2003.
//  Copyright © 2020 Rakhman. All rights reserved.
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define S second
#define F first
#define nl '\n'

const long long mxn = 510501;
const long long mod = 1e5 + 7;
const long long inf = 1e18;

typedef long long llong;

using namespace std;

void istxt(bool yes){
    if(yes == 1){
        freopen("sum2.in", "r", stdin);
        freopen("sum2.out", "w", stdout);
    }else{
        freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
    }
}

int n, cnt[3], dp[410][410][410][3], a[mxn], pr[mxn][3];
int nx[3][410];
string s;

int main(){
    ios;
    cin >> n;
    cin >> s;
    s = '#' + s;
    for(int i = 1; i <= n; i++){
        a[i] = (s[i] == 'R' ? 0 : (s[i] == 'G' ? 1 : 2));
        cnt[a[i]]++;
        nx[a[i]][cnt[a[i]]] = i;
    }
    for(int i = 1; i <= n; i++){
        for(int f = 0; f <= 2; f++){
            pr[i][f] = pr[i - 1][f];
        }
        pr[i][a[i]]++;
    }
    for(int i = 0; i <= cnt[0]; i++){
        for(int j = 0; j <= cnt[1]; j++){
            for(int k = 0; k <= cnt[2]; k++){
                for(int f = 0; f <= 2; f++){
                    dp[i][j][k][f] = mxn;
                }
            }
        }
    }
    for(int f = 0; f <= 2; f++) dp[0][0][0][f] = 0;
    for(int i = 0; i <= cnt[0]; i++){
        for(int j = 0; j <= cnt[1]; j++){
            for(int k = 0; k <= cnt[2]; k++){
                for(int last = 0; last < 3; last ++){
                    for(int cur = 0; cur < 3; cur++){
                        if(cur == last) continue;
                        if((cur == 0 && cnt[0] == i) || (cur == 1 && cnt[1] == j) || (cur == 2 && cnt[2] == k)) continue;
                        
                        int ans = 0;
                        int pos1, pos2, pos3;
                        int other = 3 - last - cur;
                        if(last == 0){
                            pos1 = nx[0][i];
                            if(cur == 1){
                                pos2 = nx[1][j + 1], pos3 = nx[2][k];
                            }else{
                                pos2 = nx[2][k + 1], pos3 = nx[1][j];
                            }
                        }else if(last == 1){
                            pos1 = nx[1][j];
                            if(cur == 0){
                                pos2 = nx[0][i + 1], pos3 = nx[2][k];
                            }else{
                                pos2 = nx[2][k + 1], pos3 = nx[0][i];
                            }
                        }else{
                            pos1 = nx[2][k];
                            if(cur == 0){
                                pos2 = nx[0][i + 1], pos3 = nx[1][j];
                            }else{
                                pos2 = nx[1][j + 1], pos3 = nx[0][i];
                            }
                        }
                        ans += max(0, pr[pos2][last] - pr[pos1][last]);
                        ans += max(0, pr[pos2][other] - pr[pos3][other]);
                        ans += dp[i][j][k][last];
                        if(cur == 0){
                            dp[i + 1][j][k][cur] = min(dp[i + 1][j][k][cur], ans);
                        }else if(cur == 1){
                            dp[i][j + 1][k][cur] = min(dp[i][j + 1][k][cur], ans);
                        }else{
                            dp[i][j][k + 1][cur] = min(dp[i][j][k + 1][cur], ans);
                        }
                    }
                }
            }
        }
    }
    int ans = mxn;
    for(int i = 0; i < 3; i++){
        ans = min(ans, dp[cnt[0]][cnt[1]][cnt[2]][i]);
    }
    if(ans == mxn) cout << -1;
    else cout << ans;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void istxt(bool)':
joi2019_ho_t3.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("sum2.in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("sum2.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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