답안 #802193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802193	2023-08-02T10:58:07 Z	NothingXD	Giraffes (JOI22_giraffes)	C++17	59 / 100	53 ms	56148 KB

giraffes

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 300 + 10;

int n, a[maxn];
int dp[maxn][maxn][maxn];

int main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for (int i = n; i; i--){
		for (int j = 1; j <= n; j++){
			dp[i][i][j] = (a[j] != i);
		}
		for (int j = i+1; j <= n; j++){
			for (int k = 1; k+j-i <= n; k++){
				dp[i][j][k] = min({dp[i+1][j][k] + (a[k+j-i] != i), dp[i+1][j][k+1] + (a[k] != i)
						, dp[i][j-1][k] + (a[k+j-i] != j), dp[i][j-1][k+1] + (a[k] != j)});
			}
		}
	}
	cout << dp[1][n][1] << '\n';
}

Subtask #1

10.0 / 10.0

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

Subtask #2

22.0 / 22.0

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

Subtask #3

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 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	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	312 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	432 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	468 KB	Output is correct
20	Correct	1 ms	436 KB	Output is correct
21	Correct	1 ms	852 KB	Output is correct
22	Correct	4 ms	6228 KB	Output is correct
23	Correct	16 ms	21840 KB	Output is correct
24	Correct	27 ms	36860 KB	Output is correct
25	Correct	41 ms	52124 KB	Output is correct
26	Correct	53 ms	54760 KB	Output is correct
27	Correct	48 ms	54988 KB	Output is correct
28	Correct	46 ms	55400 KB	Output is correct
29	Correct	53 ms	55820 KB	Output is correct
30	Correct	52 ms	56148 KB	Output is correct

Subtask #4

0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 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	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	312 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	432 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	468 KB	Output is correct
20	Correct	1 ms	436 KB	Output is correct
21	Correct	1 ms	852 KB	Output is correct
22	Correct	4 ms	6228 KB	Output is correct
23	Correct	16 ms	21840 KB	Output is correct
24	Correct	27 ms	36860 KB	Output is correct
25	Correct	41 ms	52124 KB	Output is correct
26	Correct	53 ms	54760 KB	Output is correct
27	Correct	48 ms	54988 KB	Output is correct
28	Correct	46 ms	55400 KB	Output is correct
29	Correct	53 ms	55820 KB	Output is correct
30	Correct	52 ms	56148 KB	Output is correct
31	Runtime error	3 ms	340 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-