oj.uz

Submission #631031

# Submission time Handle Problem Language Result Execution time Memory
631031 2022-08-17T15:14:02 Z Karliver Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 74 ms 162924 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];
int ca[N], cb[N], cc[N];
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);
	}
	
	for(int j = 0;j < n;++j) {
		if(j)ca[j] = ca[j-1], cb[j] = cb[j-1], cc[j] = cc[j-1];
		if(a[j] == 0)ca[j]++;
		else if(a[j] == 1) cb[j]++;
		else cc[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;
	
	dp[0][0][0][0] = 0;
	forn(i, A+1) forn(j, B + 1) forn(k, C+1) forn(l, 3) {
		if(dp[i][j][k][l] == INF)continue;
		int x = i+j+k;
		if(i<A &&  (l != 0 || x==0))ckmi(dp[i+1][j][k][0], dp[i][j][k][l]+max(0, cb[pos[0][i]]-j)+max(0,cc[pos[0][i]]-k));
		if(j<B && (l != 1 || x == 0))ckmi(dp[i][j+1][k][1], dp[i][j][k][l]+max(0, ca[pos[1][j]]-i)+max(0, cc[pos[1][j]]-k));
		if(k<C && (l != 2 || x == 0))ckmi(dp[i][j][k+1][2], dp[i][j][k][l]+max(0, ca[pos[2][k]]-i)+max(0, cb[pos[2][k]]-j));
	}	
	
	int res = INF;
	forn(i, 3) {
		//debug(dp[A][B][C][i]);
		ckmi(res, dp[A][B][C][i]);
	}
	
	
	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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 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 Incorrect 1 ms 596 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 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 Incorrect 1 ms 596 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 59 ms 162924 KB Output is correct
3 Correct 58 ms 162100 KB Output is correct
4 Correct 58 ms 162820 KB Output is correct
5 Correct 58 ms 162904 KB Output is correct
6 Correct 71 ms 162852 KB Output is correct
7 Correct 74 ms 162056 KB Output is correct
8 Correct 64 ms 162124 KB Output is correct
9 Correct 62 ms 161228 KB Output is correct
10 Correct 61 ms 162832 KB Output is correct
11 Correct 58 ms 162828 KB Output is correct
12 Correct 18 ms 44116 KB Output is correct
13 Correct 33 ms 77140 KB Output is correct
14 Correct 43 ms 111272 KB Output is correct
15 Incorrect 60 ms 162904 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 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 Incorrect 1 ms 596 KB Output isn't correct
11 Halted 0 ms 0 KB -