답안 #802085

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802085	2023-08-02T09:36:49 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	59 / 100	2389 ms	236016 KB

giraffes

// Wounds should become scars but I'm cracked instead U+1FAE0
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 300 + 10;

int dp[MAXN][MAXN][MAXN], n, A[MAXN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> A[i];

	for (int len = 1; len <= n; len++) {
		for (int l = 1; l <= n - len + 1; l++) {
			for (int tl = 1; tl <= n - len + 1; tl++) {
				int r = l + len - 1;
				int tr = tl + len - 1;

				if (A[l] == tl) dp[len][l][tl] = dp[len - 1][l + 1][tl + 1] + 1;
				else if (A[r] == tl) dp[len][l][tl] = dp[len - 1][l][tl + 1] + 1;
				else if (A[l] == tr) dp[len][l][tl] = dp[len - 1][l + 1][tl] + 1;
				else if (A[r] == tr) dp[len][l][tl] = dp[len - 1][l][tl] + 1;
				else dp[len][l][tl] = max({
					dp[len - 1][l][tl], 
					dp[len - 1][l + 1][tl], 
					dp[len - 1][l][tl + 1], 
					dp[len - 1][l + 1][tl + 1]
				});
			}
		}
	}

	cout << n - dp[n][1][1] << endl;
	return 0;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	224 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	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct

Subtask #2

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	224 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	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	1 ms	420 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	224 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	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	1 ms	420 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	852 KB	Output is correct
22	Correct	4 ms	6228 KB	Output is correct
23	Correct	14 ms	21844 KB	Output is correct
24	Correct	24 ms	36804 KB	Output is correct
25	Correct	36 ms	52208 KB	Output is correct
26	Correct	40 ms	54724 KB	Output is correct
27	Correct	51 ms	55084 KB	Output is correct
28	Correct	43 ms	55476 KB	Output is correct
29	Correct	39 ms	55740 KB	Output is correct
30	Correct	39 ms	56100 KB	Output is correct

Subtask #4

0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	224 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	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	1 ms	420 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	852 KB	Output is correct
22	Correct	4 ms	6228 KB	Output is correct
23	Correct	14 ms	21844 KB	Output is correct
24	Correct	24 ms	36804 KB	Output is correct
25	Correct	36 ms	52208 KB	Output is correct
26	Correct	40 ms	54724 KB	Output is correct
27	Correct	51 ms	55084 KB	Output is correct
28	Correct	43 ms	55476 KB	Output is correct
29	Correct	39 ms	55740 KB	Output is correct
30	Correct	39 ms	56100 KB	Output is correct
31	Runtime error	2389 ms	236016 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-