oj.uz

Submission #891828

# Submission time Handle Problem Language Result Execution time Memory
891828 2023-12-24T07:18:00 Z Vvnx Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 79 ms 257236 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second

const ll N = 403;
const ll INF = 1e9;

ll n,r,g,b;
string s;
vector<ll> pos[5];
ll dp[N][N][N][3];

int main() {
	cin >> n >> s;
	s = '!' + s;
	for(int i=1; i<=n; i++) {
		if(s[i] == 'R') {
			r++;
			pos[0].pb(i);
		}
		else if(s[i] == 'G') {
			g++;
			pos[1].pb(i);
		}
		else if(s[i] == 'Y') {
			b++;
			pos[2].pb(i);
		}
	}
	for(int i=0; i<=r; i++) {
		for(int j=0; j<=g; j++) {
			for(int k=0; k<=b; k++) {
				for(int l=0; l<=3; l++) dp[i][j][k][l] = INF;
			}
		}
	}
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	dp[0][0][0][2] = 0;
	for(int i=0; i<=r; i++) {
		for(int j=0; j<=g; j++) {
			for(int k=0; k<=b; k++) {
				if(i) dp[i][j][k][0] = min(dp[i-1][j][k][1],dp[i-1][j][k][2]) + abs(i+j+k-pos[0][i-1]);
				if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0],dp[i][j-1][k][2]) + abs(i+j+k-pos[1][j-1]);
				if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0],dp[i][j][k-1][1]) + abs(i+j+k-pos[2][k-1]);
			}
		}
	}
	ll ans = min({dp[r][g][b][0],dp[r][g][b][1],dp[r][g][b][2]});
	if(ans == INF) cout << -1 << endl;
	else cout << ans/2 << endl;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:37:44: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
   37 |     for(int l=0; l<=3; l++) dp[i][j][k][l] = INF;
      |                             ~~~~~~~~~~~~~~~^~~~~
joi2019_ho_t3.cpp:37:19: note: within this loop
   37 |     for(int l=0; l<=3; l++) dp[i][j][k][l] = INF;
      |                  ~^~~
joi2019_ho_t3.cpp:37:42: warning: array subscript 3 is above array bounds of 'int [3]' [-Warray-bounds]
   37 |     for(int l=0; l<=3; l++) dp[i][j][k][l] = INF;
      |                             ~~~~~~~~~~~~~^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 20828 KB Output is correct
11 Incorrect 2 ms 10588 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 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 20828 KB Output is correct
11 Incorrect 2 ms 10588 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 1 ms 4444 KB Output is correct
2 Correct 79 ms 231600 KB Output is correct
3 Correct 59 ms 235700 KB Output is correct
4 Correct 56 ms 236112 KB Output is correct
5 Correct 53 ms 236112 KB Output is correct
6 Correct 60 ms 238760 KB Output is correct
7 Correct 54 ms 242560 KB Output is correct
8 Correct 51 ms 242396 KB Output is correct
9 Correct 55 ms 246660 KB Output is correct
10 Correct 51 ms 252904 KB Output is correct
11 Correct 51 ms 252760 KB Output is correct
12 Correct 19 ms 165724 KB Output is correct
13 Correct 29 ms 190548 KB Output is correct
14 Correct 39 ms 215396 KB Output is correct
15 Correct 50 ms 257236 KB Output is correct
16 Correct 51 ms 257048 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 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 2 ms 12636 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 2 ms 12632 KB Output is correct
10 Correct 2 ms 20828 KB Output is correct
11 Incorrect 2 ms 10588 KB Output isn't correct
12 Halted 0 ms 0 KB -