Submission #1160959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160959		nguyn	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	147 ms	137716 KiB

joi2019_ho_t3

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

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 405;

int n; 
string s;
vector<int> pos[3];
int p[3][N];
vector<vector<vector<vector<int>>>> f; 

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> s; 
    for (int i = 1; i <= n; i++) {
        char c = s[i - 1]; 
        int x = 0;
        if (c == 'G') x = 1;
        if (c == 'Y') x = 2;    
        for (int j = 0; j < 3; j++) {
            p[j][i] = p[j][i - 1];
        }
        p[x][i]++;
        pos[x].pb(i);
    }
    f.resize(p[0][n] + 2, vector<vector<vector<int>>>(p[1][n] + 2, vector<vector<int>>(p[2][n] + 2, vector<int>(3)))); 
    for (int i = 0; i <= p[0][n]; i++) {
        for (int j = 0; j <= p[1][n]; j++) {
            for (int k = 0; k <= p[2][n]; k++) {
                for (int l = 0; l < 3; l++) {
                    f[i][j][k][l] = 2e9;
                }
            }
        }
    }
    for (int i = 0; i < 3; i++) {
        f[0][0][0][i] = 0; 
    }
    for(int j = 0; j <= p[0][n]; j++) {
        for(int k = 0; k <= p[1][n]; k++) {
            for (int l = 0; l <= p[2][n]; l++) {
                if(j < p[0][n]) {
                    int cur = min(f[j][k][l][1], f[j][k][l][2]);
                    cur += max(0, p[1][pos[0][j]] - k) + max(0, p[2][pos[0][j]] - l);

                    f[j + 1][k][l][0] = min(f[j + 1][k][l][0], cur);
                }
                if(k < p[1][n]) {
                    int cur = min(f[j][k][l][0], f[j][k][l][2]);
                    cur += max(0, p[0][pos[1][k]] - j) + max(0, p[2][pos[1][k]] - l);
                      
                    f[j][k + 1][l][1] = min(f[j][k + 1][l][1], cur);
                }
                if(l < p[2][n]) {
                    int cur = min(f[j][k][l][1], f[j][k][l][0]);
                    cur += max(0, p[1][pos[2][l]] - k) + max(0, p[0][pos[2][l]] - j);
                  
                    f[j][k][l + 1][2] = min(f[j][k][l + 1][2], cur);
                }
            }
        }
    }
    int res = 2e9;
    for (int i = 0; i < 3; i++) {
        res = min(res, f[p[0][n]][p[1][n]][p[2][n]][i]);
    }
    if (res == 2e9) {
        cout << -1;
    }
    else {
        cout << res;
    }
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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