Submission #1187415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187415		vito	Nestabilnost (COI23_nestabilnost)	C++17	32 / 100	59 ms	12176 KiB

code1

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define F first
#define S second
#define sz(x) int(x.size())
const ll INF=1e18+5;
int n;
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	vector<int> a(n+1);
	for(int i=1; i<=n; i++) {
		cin >> a[i];
	}
	vector<ll> f(n+1);
	for(int k=1; k<=n; k++) {
		cin >> f[k];
	}
	for(int i=0; i<n-1; i++) {
		int x, y;
		cin >> x >> y;
	}
	vector<ll> suff(n+1);
	suff[n]=f[n];
	for(int i=n-1; i>=1; i--) {
		suff[i]=min(suff[i+1], f[i]);
	}
	vector<ll> dp(n+1, INF);
	dp[0]=0;
	dp[1]=suff[a[1]+1];
	vector<int> poc(n+1);
	poc[1]=1;
	for(int i=2; i<=n; i++) {
		if(a[i-1]+1==a[i]) {
			poc[i]=poc[i-1];
		}
		else {
			poc[i]=i;
		}
	}
	// for(int i=1; i<=n; i++) {
	// 	cout << poc[i] << ' ';
	// 	dp[i]=dp[poc[i]-1]+suff[a[i]+1];
	// }
	// cout << '\n';
	int mora=-1;
	vector<pair<int, int>> koji(n+1, make_pair(-1, -1));
	for(int i=2; i<=n; i++) {
		if(a[i]==0) {
			if(mora==a[i-1]+1) {
				koji[i]=koji[i-1];
			}
			else {
				mora=a[i-1]+1;
				koji[i]=make_pair(poc[i-1], mora);
			}
		}
		else {
			if(a[i-1]+1!=a[i]) {
				mora=-1;
			}
			else if(mora!=-1) {
				if(mora>a[i]) {
					koji[i]=koji[i-1];
				}
			}
		}
	}
	// cout << dp[1] << ' ' << dp[2] << ' ' << dp[3] << '\n';
	// cout << koji[2].F << ' ' << koji[2].S << '\n';
	// cout << koji[3].F << ' ' << koji[3].S << '\n';
	for(int i=1; i<=n; i++) {
		dp[i]=dp[poc[i]-1]+suff[a[i]+1];
		if(koji[i].S!=-1) {
			dp[i]=min(dp[i], dp[koji[i].F-1]+f[koji[i].S]);
		}
	}
	cout << dp[n] << '\n';
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 20 / 20
• Subtask 3: 0 / 7
• Subtask 4: 0 / 22
• Subtask 5: 0 / 39