oj.uz

Submission #988344

# Submission time Handle Problem Language Result Execution time Memory
988344 2024-05-24T14:21:39 Z biximo Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 414 ms 519360 KB 
#include <bits/stdc++.h>
#define N 405
#define INF 2000000000
using namespace std;
int n, dp[N][N][N][4], p[N][3];
string s;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> s;
    for(char&i: s) {
    	if(i=='R')i=0;
    	else if(i == 'G')i=1;
    	else i=2;
    }
    for(int i = 1; i <= n; i ++) {
    	for(int j = 0; j < 3; j ++) {
    		p[i][j] = p[i-1][j]+(s[i-1]==j);
    	}
    }
    for(int i = 0; i <= n; i ++) {
    	for(int j = 0; j <= i; j ++) {
    		for(int k = 0; j+k <= i; k ++) {
    			for(int l = 0; l < 4; l ++) {
    				dp[i][j][k][l] = INF;
    			}
    		}
    	}
    }
    dp[0][0][0][3] = 0;
    for(int i = 0; i < n; i ++) {
    	for(int j = 0; j <= i; j ++) {
    		for(int k = 0; j+k <= i; k ++) {
    			for(int l = 0; l < 3+(i==0); l ++) {
    				if(INF == dp[i][j][k][l]) continue;
    				for(int nl = 0; nl < 3; nl ++) {
    					if(l == nl) continue;
    					int nj = j, nk = k;
    					if(nl == 0) nj++;
    					else if(nl == 1) nk++;
    					int nc = dp[i][j][k][l]+(abs(p[i+1][0]-nj)+abs(p[i+1][1]-nk)+abs(p[i+1][2]-(i+1-nj-nk)))/2;
    					dp[i+1][nj][nk][nl] = min(dp[i+1][nj][nk][nl],nc);
    					assert((abs(p[i+1][0]-nj)+abs(p[i+1][1]-nk)+abs(p[i+1][2]-(i+1-nj-nk)))%2==0);
    				}
    			}
    		}
    	}
    }
    int ans = INF;
    for(int i = 0; i < 3; i ++) {
    	ans = min(ans, dp[n][p[n][0]][p[n][1]][i]);
    }
    // assert(ans%2==0);
    if(ans == INF) cout << "-1";
    else cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 4508 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 8 ms 20824 KB Output is correct
5 Correct 12 ms 31068 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 5 ms 31064 KB Output is correct
9 Correct 5 ms 31064 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct
11 Incorrect 5 ms 31064 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 4508 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 8 ms 20824 KB Output is correct
5 Correct 12 ms 31068 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 5 ms 31064 KB Output is correct
9 Correct 5 ms 31064 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct
11 Incorrect 5 ms 31064 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 414 ms 519360 KB Output is correct
3 Correct 367 ms 516516 KB Output is correct
4 Correct 334 ms 518884 KB Output is correct
5 Correct 338 ms 518976 KB Output is correct
6 Correct 353 ms 518740 KB Output is correct
7 Correct 350 ms 516512 KB Output is correct
8 Correct 343 ms 516436 KB Output is correct
9 Correct 317 ms 513928 KB Output is correct
10 Correct 353 ms 519000 KB Output is correct
11 Correct 395 ms 518728 KB Output is correct
12 Correct 87 ms 177692 KB Output is correct
13 Correct 146 ms 270160 KB Output is correct
14 Correct 234 ms 368500 KB Output is correct
15 Correct 361 ms 518740 KB Output is correct
16 Correct 358 ms 518844 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 4508 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 8 ms 20824 KB Output is correct
5 Correct 12 ms 31068 KB Output is correct
6 Correct 6 ms 31320 KB Output is correct
7 Correct 5 ms 31068 KB Output is correct
8 Correct 5 ms 31064 KB Output is correct
9 Correct 5 ms 31064 KB Output is correct
10 Correct 5 ms 31068 KB Output is correct
11 Incorrect 5 ms 31064 KB Output isn't correct
12 Halted 0 ms 0 KB -