Submission #612358

#	Time	Username	Problem	Language	Result	Execution time	Memory
612358		balbit	Giraffes (JOI22_giraffes)	C++14	59 / 100	54 ms	28460 KiB

giraffes

#include <bits/stdc++.h>
using namespace std;

#define int ll
#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for(int i = 1; i<=n; ++i)
#define FOR(i,a,b) for(int i = a; i<b; ++i)
#define MX(a,b) a = max(a,b)
#define YO(a,b) a = max(a,(short)(b))
#define MN(a,b) a = min(a,b)
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif 

const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5+5;

short dp[305][305][305];

int p[maxn];

signed main(){
	ios::sync_with_stdio(0), cin.tie(0);
	
	int n; cin>>n;
	REP1(i,n) {
		cin>>p[i]; --p[i];
	}
	REP1(len, n) {
		REP1(i, n-len+1) {
			int j = i+len-1;
			REP(col, n-len+1) {
				int c2 = col+len-1;
				YO(dp[i][j][col], dp[i+1][j][col] + (c2==p[i]));
				YO(dp[i][j][col], dp[i+1][j][col+1] + (col==p[i]));
				YO(dp[i][j][col], dp[i][j-1][col] + (c2==p[j]));
				YO(dp[i][j][col], dp[i][j-1][col+1] + (col==p[j]));

				// bug(i,j,col,dp[i][j][col]);
			}
		}
	}


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

}

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