제출 #886116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886116		vjudge1	Airplane (NOI23_airplane)	C++17	0 / 100	124 ms	13652 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX;
int main(){
	int n,m;cin>>n>>m;
	vector<int> val(n);
	for (int i = 0; i < n; ++i)
	{
		cin>>val[i];
	}
	vector<vector<int>> arr(n);
	for (int i = 0; i < m; i++){
		int u,v;cin>>u>>v;
		arr[u-1].push_back(v-1);
		arr[v-1].push_back(u-1);
	}
	vector<int> dp1(n);
	vector<int> dp2(n);
	int crmax = 0;
	int crans = 0;
	int ans = INF;
	for (int i = 1; i < n; ++i)
	{
		if (crmax>=val[i]) crans++;
		else crans+=val[i]-crmax;
		dp1[i]=crans;
		crmax=max(crmax,val[i]);
	}
	ans=crans+crmax;
	crmax=0;
	crans=0;
	for (int i = n-2; i >= 0; --i){
		if (crmax>=val[i]) crans++;
		else crans+=val[i]-crmax;
		dp2[i]=crans;
		crmax=max(crmax,val[i]);
	}
	ans=min(ans,crans+crmax);
	for (int i = 1; i < n-1; ++i)
	{
		ans=min(ans,dp1[i]+dp2[i]);
	}
	cout<<ans<<endl;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 10
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37