oj.uz

Submission #821729

# Submission time Handle Problem Language Result Execution time Memory
821729 2023-08-11T14:06:57 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 1024752 KB 
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
//#define int long long
//#define ld long double
using namespace std;
using ll=long long;
const int inf = 1e9;
const int MN =400+5;
const int mod=1e9+7;
int n;
string s;
int cnt[MN][MN][4][4];
int dp[MN][MN][MN][4];
int a[MN],b[MN],c[MN];
void solve() {
	cin>>n>>s;
//	s="#"+s;
	int n1=0,n2=0,n3=0;
	for (int i=0; i<n; i++) {
		if(s[i]=='R') a[++n1]=i;
		else if(s[i]=='Y') b[++n2]=i;
		else c[++n3]=i;
	}
	int k;
	k=0;
	for (int i=1; i<=n1; i++) {
		k=0;
		for (int j=1; j<=n2; j++) {
			if(b[j]>a[i]) k++;
			cnt[i][j][1][2]=k;
//			cout<<cnt[i][j][1][2]<<" ";
		}
	}
	k=0;
	for (int i=1; i<=n1; i++) {
		k=0;
		for (int j=1; j<=n3; j++) {
			if(c[j]>a[i]) k++;
			cnt[i][j][1][3]=k;
		}
	}
	k=0;
	for (int i=1; i<=n2; i++) {
		k=0;
		for (int j=1; j<=n1; j++) {
			if(a[j]>b[i]) k++;
			cnt[i][j][2][1]=k;
		}
	}
	k=0;
	for (int i=1; i<=n2; i++) {
		k=0;
		for (int j=1; j<=n3; j++) {
			if(c[j]>b[i]) k++;
			cnt[i][j][2][3]=k;
		}
	}
	k=0;
	for (int i=1; i<=n3; i++) {
		k=0;
		for (int j=1; j<=n1; j++) {
			if(a[j]>c[i]) k++;
			cnt[i][j][3][1]=k;
		}
	}
	k=0;
	for (int i=1; i<=n3; i++) {
		k=0;
		for (int j=1; j<=n2; j++) {
			if(b[j]>c[i]) k++;
			cnt[i][j][3][2]=k;
		}
	}
	for (int i=0; i<=n; i++) {
		for (int j=0; j<=n; j++) {
			for (int l=0; l<=n; l++) {
				dp[i][j][l][1]=dp[i][j][l][2]=dp[i][j][l][3]=inf;
			}
		}
	}
	dp[0][0][0][1]=dp[0][0][0][2]=dp[0][0][0][3]=0;
	for (int i=0; i<=n1; i++) {
		for (int j=0; j<=n2; j++) {
			for (int l=0; l<=n3; l++) {
				if(i>0) dp[i][j][l][1] = min(dp[i-1][j][l][2],dp[i-1][j][l][3]) + cnt[i][j][1][2] + cnt[i][l][1][3];
				if(j>0) dp[i][j][l][2] = min(dp[i][j-1][l][1],dp[i][j-1][l][3]) + cnt[j][i][2][1] + cnt[j][l][2][3];
				if(l>0) dp[i][j][l][3] = min(dp[i][j][l-1][2],dp[i][j][l-1][1]) + cnt[l][i][3][1] + cnt[l][j][3][2];
			}
		}
	}
	int ans=min({dp[n1][n2][n3][1], dp[n1][n2][n3][2], dp[n1][n2][n3][3]});
	if(ans==inf) cout<<-1;
	else cout<<ans;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen(".inp", "r", stdin);
//	freopen(".out", "w", stdout);
	int t=1;
//	cin>>t;
	while(t--) {
		solve();
	}
		
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 1488 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Incorrect 1 ms 1492 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 1488 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Incorrect 1 ms 1492 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 526 ms 1024752 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 1488 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 2 ms 1492 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 1 ms 1492 KB Output is correct
13 Incorrect 1 ms 1492 KB Output isn't correct
14 Halted 0 ms 0 KB -