oj.uz

Submission #630579

# Submission time Handle Problem Language Result Execution time Memory
630579 2022-08-16T15:36:39 Z Karliver Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 53 ms 133304 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 = 210;
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]);
	
	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]);
	}
	cout << (res == INF ? -1 : 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 260 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Incorrect 1 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 324 KB Output is correct
4 Correct 1 ms 260 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 456 KB Output is correct
11 Incorrect 1 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 1 ms 340 KB Output is correct
2 Correct 48 ms 133196 KB Output is correct
3 Correct 47 ms 132544 KB Output is correct
4 Correct 47 ms 133304 KB Output is correct
5 Correct 53 ms 133232 KB Output is correct
6 Correct 48 ms 133264 KB Output is correct
7 Correct 48 ms 132552 KB Output is correct
8 Correct 48 ms 132556 KB Output is correct
9 Correct 46 ms 131848 KB Output is correct
10 Correct 48 ms 133240 KB Output is correct
11 Correct 49 ms 133268 KB Output is correct
12 Correct 16 ms 35924 KB Output is correct
13 Correct 24 ms 63020 KB Output is correct
14 Correct 33 ms 91016 KB Output is correct
15 Correct 51 ms 133196 KB Output is correct
16 Correct 48 ms 133196 KB Output is correct

Subtask #4
0 / 25.0

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