oj.uz

답안 #865917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865917 2023-10-25T03:23:41 Z phoenix0423 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 500 ms 1048580 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;
				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 Execution timed out 2940 ms 1048580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2940 ms 1048580 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 780368 KB Output is correct
2 Correct 289 ms 780200 KB Output is correct
3 Correct 301 ms 780400 KB Output is correct
4 Correct 289 ms 780224 KB Output is correct
5 Correct 291 ms 780388 KB Output is correct
6 Correct 293 ms 780368 KB Output is correct
7 Correct 286 ms 780628 KB Output is correct
8 Correct 285 ms 780208 KB Output is correct
9 Correct 277 ms 780428 KB Output is correct
10 Correct 286 ms 780300 KB Output is correct
11 Correct 277 ms 780260 KB Output is correct
12 Correct 286 ms 780632 KB Output is correct
13 Correct 274 ms 780312 KB Output is correct
14 Correct 277 ms 780368 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2940 ms 1048580 KB Time limit exceeded
2 Halted 0 ms 0 KB -