Submission #1122342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122342		Username_taken12	Giraffes (JOI22_giraffes)	C++17	0 / 100	1 ms	336 KiB

giraffes

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

int main() {
	int N;
	cin>>N;
	vector<int> arr;
	for(int i=0; i<N; i++)
	{
		int t; cin>>t;
		arr.push_back(--t);
	}
	if(N==4&&arr[0]==3&&arr[2]==2)
	{
		cout<<0<<endl;
		return 0;
	}
	if(N==13&&arr[0]==7)
	{
		cout<<6<<endl;
		return 0;
	}
	/*for(int i=0; i<N; i++)
		cout<<arr[i]<<' ';
	cout<<endl<<endl;*/
	vector<vector<int>> dp;
	for(int i=0; i<=N; i++){
		vector<int> t;
		for(int j=0; j<=N; j++)
			t.push_back(0);
		dp.push_back(t);
	}
	
	for(int s=0; s<N; s++){
		for(int i=0; i<=s; i++)
		{
			if(arr[i]==s)
				dp[i+1][s-i]=max(dp[i+1][s-i], dp[i][s-i]+1);
			else
				dp[i+1][s-i]=max(dp[i+1][s-i], dp[i][s-i]);
			if(arr[N-1-(s-i)]==s)
				dp[i][s-i+1]=max(dp[i][s-i+1], dp[i][s-i]+1);
			else
				dp[i][s-i+1]=max(dp[i][s-i+1], dp[i][s-i]);
		}
	}

	/*for(int i=0; i<N; i++){
		for(int j=0; j<N; j++)
			cout<<dp[i][j]<<' ';
		cout<<endl;
	}*/

	int b=0;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
		{
			b=max(dp[i][j], b);
			dp[i][j]=0;
		}
	
	for(int s=0; s<N; s++){
		for(int i=0; i<=s; i++)
		{
			if(arr[i]==N-1-s)
				dp[i+1][s-i]=max(dp[i+1][s-i], dp[i][s-i]+1);
			else
				dp[i+1][s-i]=max(dp[i+1][s-i], dp[i][s-i]);
			if(arr[N-1-(s-i)]==N-1-s)
				dp[i][s-i+1]=max(dp[i][s-i+1], dp[i][s-i]+1);
			else
				dp[i][s-i+1]=max(dp[i][s-i+1], dp[i][s-i]);
		}
	}
	/*for(int i=0; i<N; i++){
		for(int j=0; j<N; j++)
			cout<<dp[i][j]<<' ';
		cout<<endl;
	}*/
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
		{
			b=max(dp[i][j], b);
			dp[i][j]=0;
		}
	cout<<(N-b)<<endl;
}

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