Submission #1287785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287785		m.zeeshanrashid	Line Town (CCO23_day1problem3)	C++20	0 / 25	1 ms	572 KiB

Main

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

#define int long long
#define vec vector

const int mod=1e6+3;

void solve(){
	int n;
	cin>>n;
	vector<int>h(n);
	for(auto &i:h) cin>>i;
	vec<vec<int>>dpp(n+1,vec<int>(2,1e15));
	dpp[0][0]=0;
	if(h[0]<0) dpp[1][0]=0;
	else dpp[1][1]=0;
	for(int i=2;i<=n;i++){
		int x=h[i-1];
		if(x==1){
			dpp[i][0]=dpp[i-1][1]+1;
			dpp[i][1]=dpp[i-1][0];
		}
		else{
			dpp[i][0]=dpp[i-1][0];
			dpp[i][1]=1e15;
		}
	}
	vec<vec<int>>dps(n+2,vec<int>(2,1e15));
	dps[n+1][1]=0;
	if(h[n-1]==1) dps[n][1]=0;
	else dps[n][0]=0;
	for(int i=n-1;i>=1;i--){
		int x=h[i-1],y=h[i];
		if(x==1){
			dps[i][1]=dps[i+1][1];
			dps[i][0]=1e15;
		}
		else{
			dps[i][1]=dps[i+1][0]+1;
			dps[i][0]=dps[i+1][1];
		}
	}
	int ans=1e15;
	for(int i=0;i<=n;i++){
		// cout<<dpp[i][0]<<' '<<dps[i+1][1]<<endl;
		ans=min(ans,dpp[i][0]+dps[i+1][1]);
	}
	if(ans>n*n) cout<<"-1\n";
	else cout<<ans<<endl;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	solve();
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3