Submission #1069059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069059		prvocislo	Giraffes (JOI22_giraffes)	C++17	59 / 100	2391 ms	225364 KiB

giraffes

// Is it a wonder I broke? Let's hear one more joke
// Then we could all just laugh until I cry
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <bitset>
typedef long long ll;
using namespace std;

const int maxn = 305;
int dp[maxn][maxn][maxn]; // interval co ostava, zaciatok hodnot, max pocet tych co si mozeme nechat

void upd(int& a, int b) { a = max(a, b); }

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> p(n);
	for (int i = 0; i < n; i++) cin >> p[i], p[i]--;
	int ans = 0;
	for (int l = 0; l < n; l++) for (int r = n - 1; r >= l; r--)
	{
		for (int vl = 0; vl + (r - l) < n; vl++)
		{
			int vr = vl + r - l;
			if (l == r)
			{
				if (p[l] == vr) upd(ans, dp[l][r][vl] + 1);
				upd(ans, dp[l][r][vl]);
				continue;
			}
			upd(dp[l + 1][r][vl + 1], dp[l][r][vl] + (p[l] == vl));
			upd(dp[l][r - 1][vl + 1], dp[l][r][vl] + (p[r] == vl));
			upd(dp[l + 1][r][vl], dp[l][r][vl] + (p[l] == vr));
			upd(dp[l][r - 1][vl], dp[l][r][vl] + (p[r] == vr));
		}
	}
	cout << n - ans << "\n";
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 41