Submission #515789

#	Time	Username	Problem	Language	Result	Execution time	Memory
515789		Koosha_mv	Treatment Project (JOI20_treatment)	C++14	0 / 100	1 ms	464 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=6000,inf=1e18;

int n,m,ans=inf,a[N],l[N],t[N],r[N],cost[N],dist[N];
vector<int> g[N];

int eshterak(int l1,int r1,int l2,int r2){
	return min(r1,r2)-max(l1,l2);
}
void bfs(){
	set<pair<int,int> > s;
	f(i,0,m){
		s.insert({dist[i],i});
	}
	while(s.size()){
		int u=(*s.begin()).S;
		s.erase(s.begin());
		if(r[u]==n){
			minm(ans,dist[u]);
		}
		for(auto v : g[u]){
			if(dist[u]+cost[v]<dist[v]){
				s.erase({dist[v],v});
				dist[v]=dist[u]+cost[v];
				s.insert({dist[v],v});
			}
		}
	}
}
main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	if(m>N) exit(0);
	fill(dist,dist+N,inf);
	f(i,0,m){
		cin>>t[i]>>l[i]>>r[i]>>cost[i];
		l[i]--;
		if(l[i]==0){
			dist[i]=cost[i];
		}
	}
	f(i,0,m){
		f(j,0,i){
			int x=abs(t[i]-t[j]),esh=eshterak(l[i],r[i],l[j],r[j]);
			if(esh>=x){
				g[i].pb(j);
				g[j].pb(i);
			}
		}
	}
	bfs();
	cout<<(ans==inf ? -1 : ans);
}

Compilation message (stderr)

treatment.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main(){
      | ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61