oj.uz

Submission #298502

# Submission time Handle Problem Language Result Execution time Memory
298502 2020-09-13T03:30:00 Z mohammedehab2002 Long Distance Coach (JOI17_coach) C++11
0 / 100
 1 ms 1184 KB 
#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;
	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]=((x-d[i].first)/t+1)*w+dp[i+1];
		dp[i]=fs[i];
		long long mn=1e18;
		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)1e18,fs[j]+mn+d[i].second);
			dp[i]=min(dp[i],fs[j]);
		}
	}
	printf("%lld",dp[1]);
}

Compilation message

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:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |  scanf("%lld%d",&d[i].first,&d[i].second);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Incorrect 1 ms 1184 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Incorrect 1 ms 1184 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Incorrect 1 ms 1184 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Incorrect 1 ms 1184 KB Output isn't correct
8 Halted 0 ms 0 KB -