Submission #340061

#	Time	Username	Problem	Language	Result	Execution time	Memory
340061		couplefire	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	201 ms	4332 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#define reg register
#define maxn 405
using namespace std;
int n, sum[3][maxn], dp[2][maxn][maxn][3], R, G, Y, id[maxn], now, pos, ans, f[3][maxn];
char s[maxn];
int main() {
    cin >> n; scanf("%s", s + 1);
    for(int i = 1; i <= n; i++) {
        if(s[i] == 'R') sum[0][++R] = i; f[0][i] = f[0][i - 1] + (s[i] == 'R');
        if(s[i] == 'G') sum[1][++G] = i; f[1][i] = f[1][i - 1] + (s[i] == 'G');
        if(s[i] == 'Y') sum[2][++Y] = i; f[2][i] = f[2][i - 1] + (s[i] == 'Y');
        id[i] = id[i - 1] ^ 1;
    }
    memset(dp, 0x3f3f3f, sizeof dp);
    dp[1][1][0][0] = sum[0][1] - 1;
    dp[1][0][1][1] = sum[1][1] - 1;
    dp[1][0][0][2] = sum[2][1] - 1;
    for(int i = 2; i <= n; i++) {    
        for(int j = 0; j <= R; j++)
            for(int k = 0; k <= G; k++) {
                if(i - j - k > Y) continue;
                if(j) { 
                    pos = sum[0][j]; now = pos; now += max(0, k - f[1][pos]); now += max(0, i - j - k - f[2][pos]);  
                    dp[id[i]][j][k][0] = min(dp[id[i]][j][k][0], dp[id[i] ^ 1][j - 1][k][1] + now - i);
                    dp[id[i]][j][k][0] = min(dp[id[i]][j][k][0], dp[id[i] ^ 1][j - 1][k][2] + now - i);
                }
                if(k) {
                    pos = sum[1][k]; now = pos; now += max(0, j - f[0][pos]); now += max(0, i - j - k - f[2][pos]); 
                    dp[id[i]][j][k][1] = min(dp[id[i]][j][k][1], dp[id[i] ^ 1][j][k - 1][0] + now - i);
                    dp[id[i]][j][k][1] = min(dp[id[i]][j][k][1], dp[id[i] ^ 1][j][k - 1][2] + now - i);
                }
                    pos = sum[2][i - j - k]; now = pos; now += max(0, k - f[1][pos]); now += max(0, j - f[0][pos]);
                    dp[id[i]][j][k][2] = min(dp[id[i]][j][k][2], dp[id[i] ^ 1][j][k][0] + now - i);
                    dp[id[i]][j][k][2] = min(dp[id[i]][j][k][2], dp[id[i] ^ 1][j][k][1] + now - i);
            }
        memset(dp[id[i] ^ 1], 0x3f3f3f, sizeof dp[id[i] ^ 1]); 
    }
    ans = min(dp[id[n]][R][G][0], dp[id[n]][R][G][1]);
    ans = min(ans, dp[id[n]][R][G][2]); 
    if(ans >= 10000000) cout << -1 << endl;
    else cout << ans << endl;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:10:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   10 |         if(s[i] == 'R') sum[0][++R] = i; f[0][i] = f[0][i - 1] + (s[i] == 'R');
      |         ^~
joi2019_ho_t3.cpp:10:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   10 |         if(s[i] == 'R') sum[0][++R] = i; f[0][i] = f[0][i - 1] + (s[i] == 'R');
      |                                          ^
joi2019_ho_t3.cpp:11:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   11 |         if(s[i] == 'G') sum[1][++G] = i; f[1][i] = f[1][i - 1] + (s[i] == 'G');
      |         ^~
joi2019_ho_t3.cpp:11:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   11 |         if(s[i] == 'G') sum[1][++G] = i; f[1][i] = f[1][i - 1] + (s[i] == 'G');
      |                                          ^
joi2019_ho_t3.cpp:12:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   12 |         if(s[i] == 'Y') sum[2][++Y] = i; f[2][i] = f[2][i - 1] + (s[i] == 'Y');
      |         ^~
joi2019_ho_t3.cpp:12:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   12 |         if(s[i] == 'Y') sum[2][++Y] = i; f[2][i] = f[2][i - 1] + (s[i] == 'Y');
      |                                          ^
joi2019_ho_t3.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    8 |     cin >> n; scanf("%s", s + 1);
      |               ~~~~~^~~~~~~~~~~~~

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