Submission #1186586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186586		vito	Nestabilnost (COI23_nestabilnost)	C++17	0 / 100	1593 ms	8516 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];
	for(int i=2; i<=n; i++) {
		dp[i]=dp[i-1]+suff[a[i]+1];
		int mx=a[i];
		int mora=n+5;
		for(int j=i-1; j>=1; j--) {
			if(a[j+1]<=a[j] && a[j+1]!=0) {
				break;
			}
			if(a[j]+1==a[j+1]) {
				if(a[j+1]>=mora) {
					break;
				}
			}
			else if(a[j+1]==0) {
				if(mora==n+5) {
					mora=a[j]+1;
					if(mora<=mx) {
						break;
					}
				}
				else {
					if(mora!=a[j]+1) {
						break;
					}
				}
			}
			else {
				break;
			}
			mx=max(mx, a[j]);
			if(mora==n+5) {
				dp[i]=dp[j-1]+suff[a[i]+1];
			}
			else {
				dp[i]=dp[j-1]+f[mora];
			}
		}
	}
	cout << dp[n] << '\n';
	// for(int i=1; i<=n; i++) {
	// 	cout << dp[i] << '\n';
	// }
	return 0;
}

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