oj.uz

Submission #630582

# Submission time Handle Problem Language Result Execution time Memory
630582 2022-08-16T15:39:52 Z Karliver Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 68 ms 162920 KB 
	
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
#define ff first
#define se second
#define mp make_pair
using ll = long long;
int mod = (ll)1e9 + 7;
const int INF = 1e9 + 1;
const int N = 405;
const double eps = 1e-7;
const  long  long inf = 1e18;
template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}



void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)


int n;
string s;
int dp[N][N][N][4];
void solve() {	

	cin >> n >> s;
	vector<int> a(n);
	vector<int> pos[4];
	for(int j = 0;j < n;++j) {
		a[j] = (s[j] == 'R' ? 0 : (s[j] == 'G' ? 1 : 2));
		pos[a[j]].push_back(j);
	}
	
	
	int A = sz(pos[0]), B = sz(pos[1]), C = sz(pos[2]);
	if(max({A, B, C}) > (n + 1) / 2) {
		cout << -1 << '\n';
		return;
	}
	forn(i, A+1) forn(j, B+1) forn(k, C+1) forn(l, 3) dp[i][j][k][l] = INF;
	forn(i, 3) dp[0][0][0][i] = 0;
	forn(i, A+1) forn(j, B + 1) forn(k, C+1) forn(l, 3) {
		int x = i+j+k;
		if(i<A &&  l!= 0)ckmi(dp[i+1][j][k][0], dp[i][j][k][l]+max(0, pos[0][i]-x));
		if(j<B && l != 1)ckmi(dp[i][j+1][k][1], dp[i][j][k][l]+max(0, pos[1][j]-x));
		if(k<C && l != 2)ckmi(dp[i][j][k+1][2], dp[i][j][k][l]+max(0, pos[2][k]-x));
	}	
	
	int res = INF;
	forn(i, 3) {
		//debug(dp[A][B][C][i]);
		ckmi(res, dp[A][B][C][i]);
	}
	assert(res != INF);
	
	cout << res << '\n';
}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Incorrect 0 ms 468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Incorrect 0 ms 468 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 0 ms 340 KB Output is correct
2 Correct 62 ms 162912 KB Output is correct
3 Correct 62 ms 162064 KB Output is correct
4 Correct 55 ms 162920 KB Output is correct
5 Correct 65 ms 162892 KB Output is correct
6 Correct 68 ms 162916 KB Output is correct
7 Correct 64 ms 162072 KB Output is correct
8 Correct 57 ms 161996 KB Output is correct
9 Correct 56 ms 161280 KB Output is correct
10 Correct 56 ms 162816 KB Output is correct
11 Correct 62 ms 162840 KB Output is correct
12 Correct 17 ms 44068 KB Output is correct
13 Correct 28 ms 77132 KB Output is correct
14 Correct 38 ms 111344 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Incorrect 0 ms 468 KB Output isn't correct
12 Halted 0 ms 0 KB -