oj.uz

Submission #369282

# Submission time Handle Problem Language Result Execution time Memory
369282 2021-02-21T06:32:31 Z Return_0 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
75 / 100
 500 ms 769132 KB 
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1); cout.flush();
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< x << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

cl inf = sizeof(ll) == 4 ? (1e9 + 10) : (3e18), mod = 1e9 + 7, MOD = 998244353;

template <class A,class B> ostream& operator << (ostream& out,const pair<A,B>&a){return out<<'('<<a.first<<", "<<a.second<<')';}
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
	out<< '['; for (int i = -1; ++i < int(a.size());) out<< a[i] << (i + 1 < int(a.size()) ? ", " : ""); return out<<']'; }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 4e2 + 3;

ll dp [N][N][N][3], cnt [3][N], pos [3][N], n;
char c;

inline ll conv () {
	if (c == 'R')	return 0;
	if (c == 'G')	return 1;
	return 2;
}

int main ()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin>> n;
	for (ll i = 1, x; i <= n; i++) {
		cin>> c, x = conv();
		cnt[0][i] = cnt[0][i - 1]; cnt[1][i] = cnt[1][i - 1]; cnt[2][i] = cnt[2][i - 1];
		cnt[x][i]++;
		pos[x][cnt[x][i]] = i;
	}

	memset(dp, 61, sizeof dp);
	memset(dp[0][0][0], 0, sizeof dp[0][0][0]);

	ll t [3], p1, p2, p3, ow;
	for (t[0] = 0; t[0] <= cnt[0][n]; t[0]++) for (t[1] = 0; t[1] <= cnt[1][n]; t[1]++) for (t[2] = 0; t[2] <= cnt[2][n]; t[2]++)
	for (ll lst = 0; lst < 3; lst++) for (ll cur = 0; cur < 3; cur++) if (lst != cur && t[cur] < cnt[cur][n]) {
		ow = 3 ^ lst ^ cur;
		p1 = pos[cur][t[cur] + 1]; p2 = pos[lst][t[lst]]; p3 = pos[ow][t[ow]];
		ll tmp = dp[t[0]][t[1]][t[2]][lst];
		tmp += max(0, cnt[lst][p1] - cnt[lst][p2]);
		tmp += max(0, cnt[ow][p1] - cnt[ow][p3]);
		t[cur]++;
		dp[t[0]][t[1]][t[2]][cur] = min(dp[t[0]][t[1]][t[2]][cur], tmp);
		t[cur]--;
	}

	ow = inf;
	for (ll i = 0; i < 3; i++) ow = min(dp[cnt[0][n]][cnt[1][n]][cnt[2][n]][i], ow);
	if (ow >= inf)	ow = -1;
	kill(ow);

	return 0;
}
/*
5
RRGYY

6
RRRRRG

20
YYGYYYGGGGRGYYGRGRYG

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 768900 KB Output is correct
2 Correct 452 ms 768876 KB Output is correct
3 Correct 414 ms 768876 KB Output is correct
4 Correct 415 ms 768876 KB Output is correct
5 Correct 416 ms 769004 KB Output is correct
6 Correct 418 ms 769004 KB Output is correct
7 Correct 426 ms 769016 KB Output is correct
8 Correct 413 ms 769132 KB Output is correct
9 Correct 410 ms 768876 KB Output is correct
10 Correct 425 ms 768876 KB Output is correct
11 Correct 418 ms 768876 KB Output is correct
12 Correct 415 ms 768876 KB Output is correct
13 Correct 414 ms 768920 KB Output is correct
14 Correct 418 ms 768896 KB Output is correct
15 Correct 420 ms 768860 KB Output is correct
16 Correct 425 ms 768876 KB Output is correct
17 Correct 411 ms 768876 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 768900 KB Output is correct
2 Correct 452 ms 768876 KB Output is correct
3 Correct 414 ms 768876 KB Output is correct
4 Correct 415 ms 768876 KB Output is correct
5 Correct 416 ms 769004 KB Output is correct
6 Correct 418 ms 769004 KB Output is correct
7 Correct 426 ms 769016 KB Output is correct
8 Correct 413 ms 769132 KB Output is correct
9 Correct 410 ms 768876 KB Output is correct
10 Correct 425 ms 768876 KB Output is correct
11 Correct 418 ms 768876 KB Output is correct
12 Correct 415 ms 768876 KB Output is correct
13 Correct 414 ms 768920 KB Output is correct
14 Correct 418 ms 768896 KB Output is correct
15 Correct 420 ms 768860 KB Output is correct
16 Correct 425 ms 768876 KB Output is correct
17 Correct 411 ms 768876 KB Output is correct
18 Correct 421 ms 768876 KB Output is correct
19 Correct 415 ms 768956 KB Output is correct
20 Correct 420 ms 768876 KB Output is correct
21 Correct 425 ms 768876 KB Output is correct
22 Correct 415 ms 769004 KB Output is correct
23 Correct 422 ms 768876 KB Output is correct
24 Correct 419 ms 768876 KB Output is correct
25 Correct 421 ms 768876 KB Output is correct
26 Correct 416 ms 768876 KB Output is correct
27 Correct 425 ms 768876 KB Output is correct
28 Correct 416 ms 768876 KB Output is correct
29 Correct 428 ms 768876 KB Output is correct
30 Correct 420 ms 768876 KB Output is correct
31 Correct 422 ms 768876 KB Output is correct
32 Correct 417 ms 768876 KB Output is correct
33 Correct 417 ms 768876 KB Output is correct
34 Correct 411 ms 768876 KB Output is correct
35 Correct 416 ms 768876 KB Output is correct
36 Correct 419 ms 769132 KB Output is correct
37 Correct 421 ms 768876 KB Output is correct
38 Correct 422 ms 769004 KB Output is correct
39 Correct 414 ms 769004 KB Output is correct
40 Correct 419 ms 768876 KB Output is correct
41 Correct 419 ms 768876 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 769004 KB Output is correct
2 Correct 413 ms 769052 KB Output is correct
3 Correct 422 ms 768876 KB Output is correct
4 Correct 420 ms 768888 KB Output is correct
5 Correct 441 ms 768784 KB Output is correct
6 Correct 418 ms 768876 KB Output is correct
7 Correct 432 ms 768876 KB Output is correct
8 Correct 423 ms 769064 KB Output is correct
9 Correct 418 ms 768876 KB Output is correct
10 Correct 427 ms 768876 KB Output is correct
11 Correct 416 ms 768876 KB Output is correct
12 Correct 426 ms 768876 KB Output is correct
13 Correct 412 ms 768876 KB Output is correct
14 Correct 459 ms 768876 KB Output is correct
15 Correct 429 ms 768876 KB Output is correct
16 Correct 416 ms 768876 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 768900 KB Output is correct
2 Correct 452 ms 768876 KB Output is correct
3 Correct 414 ms 768876 KB Output is correct
4 Correct 415 ms 768876 KB Output is correct
5 Correct 416 ms 769004 KB Output is correct
6 Correct 418 ms 769004 KB Output is correct
7 Correct 426 ms 769016 KB Output is correct
8 Correct 413 ms 769132 KB Output is correct
9 Correct 410 ms 768876 KB Output is correct
10 Correct 425 ms 768876 KB Output is correct
11 Correct 418 ms 768876 KB Output is correct
12 Correct 415 ms 768876 KB Output is correct
13 Correct 414 ms 768920 KB Output is correct
14 Correct 418 ms 768896 KB Output is correct
15 Correct 420 ms 768860 KB Output is correct
16 Correct 425 ms 768876 KB Output is correct
17 Correct 411 ms 768876 KB Output is correct
18 Correct 421 ms 768876 KB Output is correct
19 Correct 415 ms 768956 KB Output is correct
20 Correct 420 ms 768876 KB Output is correct
21 Correct 425 ms 768876 KB Output is correct
22 Correct 415 ms 769004 KB Output is correct
23 Correct 422 ms 768876 KB Output is correct
24 Correct 419 ms 768876 KB Output is correct
25 Correct 421 ms 768876 KB Output is correct
26 Correct 416 ms 768876 KB Output is correct
27 Correct 425 ms 768876 KB Output is correct
28 Correct 416 ms 768876 KB Output is correct
29 Correct 428 ms 768876 KB Output is correct
30 Correct 420 ms 768876 KB Output is correct
31 Correct 422 ms 768876 KB Output is correct
32 Correct 417 ms 768876 KB Output is correct
33 Correct 417 ms 768876 KB Output is correct
34 Correct 411 ms 768876 KB Output is correct
35 Correct 416 ms 768876 KB Output is correct
36 Correct 419 ms 769132 KB Output is correct
37 Correct 421 ms 768876 KB Output is correct
38 Correct 422 ms 769004 KB Output is correct
39 Correct 414 ms 769004 KB Output is correct
40 Correct 419 ms 768876 KB Output is correct
41 Correct 419 ms 768876 KB Output is correct
42 Correct 433 ms 769004 KB Output is correct
43 Correct 413 ms 769052 KB Output is correct
44 Correct 422 ms 768876 KB Output is correct
45 Correct 420 ms 768888 KB Output is correct
46 Correct 441 ms 768784 KB Output is correct
47 Correct 418 ms 768876 KB Output is correct
48 Correct 432 ms 768876 KB Output is correct
49 Correct 423 ms 769064 KB Output is correct
50 Correct 418 ms 768876 KB Output is correct
51 Correct 427 ms 768876 KB Output is correct
52 Correct 416 ms 768876 KB Output is correct
53 Correct 426 ms 768876 KB Output is correct
54 Correct 412 ms 768876 KB Output is correct
55 Correct 459 ms 768876 KB Output is correct
56 Correct 429 ms 768876 KB Output is correct
57 Correct 416 ms 768876 KB Output is correct
58 Correct 488 ms 768876 KB Output is correct
59 Correct 481 ms 768908 KB Output is correct
60 Execution timed out 510 ms 768904 KB Time limit exceeded
61 Halted 0 ms 0 KB -