Submission #298508

#	Time	Username	Problem	Language	Result	Execution time	Memory
298508		mohammedehab2002	Long Distance Coach (JOI17_coach)	C++11	71 / 100	2065 ms	11864 KiB

coach

#include <bits/stdc++.h>
using namespace std;
pair<long long,int> d[200005];
long long x,t,s[200005],dp[200005],fs[200005];
int f[200005];
int main()
{
	int n,m,w;
	scanf("%lld%d%d%d%lld",&x,&n,&m,&w,&t);
	for (int i=0;i<n;i++)
	scanf("%lld",&s[i]);
	s[n]=x;
	sort(s,s+n+1);
	for (int i=1;i<=m;i++)
	scanf("%lld%d",&d[i].first,&d[i].second);
	sort(d,d+m+1);
	memset(f,-1,sizeof(f));
	for (int i=n;i>=0;i--)
	{
		int p=upper_bound(d,d+m+1,make_pair(s[i]%t,0))-d-1;
		f[p]=i;
	}
	dp[m+1]=(x/t+1)*w;
	fs[m+1]=dp[m+1];
	for (int i=m;i>0;i--)
	{
		fs[i]=min(((x-d[i].first)/t+1)*w+dp[i+1],(long long)2e18);
		dp[i]=fs[i];
		long long mn=2e18;
		for (int j=i+1;j<=m+1;j++)
		{
			if (f[j-1]!=-1)
			mn=min(mn,((s[f[j-1]]-d[i].first)/t)*w);
			fs[j]=min((long long)2e18,fs[j]+mn+d[i].second);
			dp[i]=min(dp[i],fs[j]);
		}
	}
	printf("%lld",dp[1]);
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |  scanf("%lld%d%d%d%lld",&x,&n,&m,&w,&t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |  scanf("%lld",&s[i]);
      |  ~~~~~^~~~~~~~~~~~~~
coach.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |  scanf("%lld%d",&d[i].first,&d[i].second);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 0 / 29