Submission #341553

#	Time	Username	Problem	Language	Result	Execution time	Memory
341553		Gajowy	Restore Array (RMI19_restore)	C++14	0 / 100	366 ms	1132 KiB

restore

#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define mp make_pair
#define e1 first
#define e2 second

const int MAXN=5e3+10;
const int inf=1e9+2137;

vector<pair<int,int>> g[MAXN];

int d[MAXN];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		d[i]=inf;
		g[i-1].eb(mp(i,1));
		g[i].eb(mp(i-1,0));
	}
	while(m--){
		int l,r,k,v;
		cin>>l>>r>>k>>v;
		l++,r++;
		if(v==0){
			g[l-1].eb(mp(r,r-l+1-k));
		}
		else{
			g[r].eb(mp(l-1,r-l+2-k));
		}
	}
	int lastRelax=0;
	for(int i=0;i<=n;i++){
		for(int u=0;u<=n;u++)
			for(auto v:g[u])
				if(d[u]+v.e2<d[v.e1])
					d[v.e1]=d[u]+v.e2,lastRelax=i;
	}
	if(lastRelax==n){
		cout<<"-1\n";
		return 0;
	}
	else{
		for(int i=1;i<=n;i++)
			cout<<(d[i]-d[i-1])<<' ';
		cout<<'\n';
	}
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55