oj.uz

답안 #865918

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865918 2023-10-25T03:26:03 Z phoenix0423 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 42 ms 390308 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
// #pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int maxn = 400 + 5;
const int INF = 1e9;
int dp[3][maxn][maxn][maxn];

int main(void){
	fastio;
	int n;
	cin>>n;
	string s;
	cin>>s;
	vector<vector<int>> pos(3);
	for(int i = 0; i < n; i++){
		if(s[i] == 'R') pos[0].pb(i);
		else if(s[i] == 'Y') pos[1].pb(i);
		else pos[2].pb(i);
	}
	for(int i = 0; i < 3; i++){
		if(pos[i].size() > (n + 1) / 2){
			cout<<-1<<"\n";
			return 0;
		}
	}
	// for(int i = 0; i < 3; i++) for(int j = 0; j < maxn; j++) for(int k = 0; k < maxn; k++) for(int l = 0; l < maxn; l++) if(j + k + l) dp[i][j][k][l] = INF;
	for(int i = 1; i <= n; i++){
		for(int a = 0; a <= pos[0].size(); a++){
			for(int b = 0; b <= pos[1].size(); b++){
				int c = i - a - b;
				for(int lst = 0; lst < 3; lst++) dp[lst][a][b][c] = INF;
				if(a) ckmin(dp[0][a][b][c], min(dp[1][a - 1][b][c] + abs(pos[0][a - 1] - (i - 1)), dp[2][a - 1][b][c] + abs(pos[0][a - 1] - (i - 1))));
				if(b) ckmin(dp[1][a][b][c], min(dp[0][a][b - 1][c] + abs(pos[1][b - 1] - (i - 1)), dp[2][a][b - 1][c] + abs(pos[1][b - 1] - (i - 1))));
				if(c) ckmin(dp[2][a][b][c], min(dp[0][a][b][c - 1] + abs(pos[2][c - 1] - (i - 1)), dp[1][a][b][c - 1] + abs(pos[2][c - 1] - (i - 1))));
			}
		}
	}
	int ans = INF;
	for(int i = 0; i < 3; i++) ans = min(ans, dp[i][pos[0].size()][pos[1].size()][pos[2].size()]);
	cout<<ans / 2<<"\n";
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:31:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |   if(pos[i].size() > (n + 1) / 2){
      |      ~~~~~~~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int a = 0; a <= pos[0].size(); a++){
      |                  ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for(int b = 0; b <= pos[1].size(); b++){
      |                   ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 6492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 6492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 42 ms 390308 KB Output is correct
3 Correct 36 ms 390212 KB Output is correct
4 Correct 37 ms 390156 KB Output is correct
5 Correct 38 ms 390280 KB Output is correct
6 Correct 37 ms 390104 KB Output is correct
7 Correct 37 ms 388176 KB Output is correct
8 Correct 37 ms 388168 KB Output is correct
9 Correct 41 ms 388180 KB Output is correct
10 Correct 37 ms 390208 KB Output is correct
11 Correct 39 ms 390224 KB Output is correct
12 Correct 22 ms 203436 KB Output is correct
13 Correct 28 ms 269140 KB Output is correct
14 Correct 31 ms 322388 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 356 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 6492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -