oj.uz

Submission #892115

# Submission time Handle Problem Language Result Execution time Memory
892115 2023-12-24T23:07:59 Z AMnu Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 95 ms 343476 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<pii> 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(pii(g,b));
		}
		else if(s[i] == 'G') {
			g++;
			pos[1].pb(pii(r,b));
		}
		else if(s[i] == 'Y') {
			b++;
			pos[2].pb(pii(r,g));
		}
	}
	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]) + max(0,pos[0][i-1].fi-j) + max(0,pos[0][i-1].se-k);
				if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0],dp[i][j-1][k][2]) + max(0,pos[1][j-1].fi-i) + max(0,pos[1][j-1].se-k);
				if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0],dp[i][j][k-1][1]) + max(0,pos[2][k-1].fi-i) + max(0,pos[2][k-1].se-j);
			}
		}
	}
	ll ans = min(dp[r][g][b][0],min(dp[r][g][b][1],dp[r][g][b][2]));
	if(ans == INF) cout << -1 << endl;
	else cout << ans << 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 2 ms 2392 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 10688 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 12636 KB Output is correct
10 Correct 3 ms 20828 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Incorrect 1 ms 6588 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 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 10688 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 12636 KB Output is correct
10 Correct 3 ms 20828 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Incorrect 1 ms 6588 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 95 ms 337552 KB Output is correct
3 Correct 43 ms 343460 KB Output is correct
4 Correct 41 ms 342356 KB Output is correct
5 Correct 41 ms 342244 KB Output is correct
6 Correct 40 ms 343476 KB Output is correct
7 Correct 40 ms 341444 KB Output is correct
8 Correct 40 ms 341588 KB Output is correct
9 Correct 43 ms 341344 KB Output is correct
10 Correct 40 ms 342452 KB Output is correct
11 Correct 43 ms 343460 KB Output is correct
12 Correct 20 ms 197468 KB Output is correct
13 Correct 26 ms 262992 KB Output is correct
14 Correct 32 ms 312248 KB Output is correct
15 Correct 42 ms 338376 KB Output is correct
16 Correct 41 ms 338000 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 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 10688 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 12636 KB Output is correct
10 Correct 3 ms 20828 KB Output is correct
11 Correct 1 ms 10588 KB Output is correct
12 Correct 2 ms 10588 KB Output is correct
13 Incorrect 1 ms 6588 KB Output isn't correct
14 Halted 0 ms 0 KB -