Submission #1162543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162543		alexander707070	Train (APIO24_train)	C++20	5 / 100	1096 ms	34604 KiB

train

#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

const long long inf=1e18;
const int endt=1e9;

struct flight{
	int from,to;
	int l,r,cost;

	inline friend bool operator < (flight fr,flight sc){
		return fr.l<sc.l;
	}
}s[MAXN];

struct meal{
	int l,r;
}w[MAXN];

int n,m,k;
long long cost[MAXN];

long long dp[MAXN];
vector< pair<long long,int> > v[MAXN];

long long meals(int l,int r){
	int res=0;
	for(int i=1;i<=k;i++){
		if(w[i].l>=l and w[i].r<=r)res++;
	}

	return res;
}

long long solve(int N, int M, int W, vector<int> T,vector<int> X, vector<int> Y,vector<int> A, vector<int> B, vector<int> C,vector<int> L,vector<int> R){
	n=N; m=M; k=W;

	for(int i=1;i<=n;i++)cost[i]=T[i-1];

	for(int i=1;i<=m;i++){
		s[i]={X[i-1]+1,Y[i-1]+1,A[i-1],B[i-1],C[i-1]};
	}
	sort(s+1,s+m+1);

	for(int i=1;i<=k;i++)w[i]={L[i-1],R[i-1]};

	v[1].push_back({0,0});

	for(int i=1;i<=m;i++){
		dp[i]=inf;

		for(auto curr:v[s[i].from]){
			if(curr.second>s[i].l)continue;

			dp[i]=min(dp[i] , curr.first + meals(curr.second+1,s[i].l-1) * cost[s[i].from]);
		}

		dp[i]+=s[i].cost;
		v[s[i].to].push_back({dp[i],s[i].r});
	}

	long long ans=inf;
	for(int i=1;i<=m;i++){
		if(s[i].to!=n)continue;

		ans=min(ans , dp[i] + meals(s[i].r+1,endt) * cost[n]);
	}

	if(ans>=inf)return -1;
	return ans;
}   

/*int main(){

	cout<<solve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2},
		{12, 48, 26, 6, 49}, {16, 50, 28, 7, 54}, {38, 6, 23, 94, 50},
		{32, 14, 42, 37, 2, 4}, {36, 14, 45, 40, 5, 5})<<"\n";

	return 0;
}*/

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