Submission #319479

#	Time	Username	Problem	Language	Result	Execution time	Memory
319479		arnold518	Long Distance Coach (JOI17_coach)	C++14	71 / 100	2062 ms	39252 KiB

coach

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 4e5;

ll X, W, T;
int N, M, K;

vector<pll> V;
ll S[MAXN+10];
pll C[MAXN+10];
ll A[MAXN+10];

ll dp[MAXN+10];
map<ll, ll> MM;

int main()
{
	scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);

	for(int i=1; i<=N; i++) scanf("%lld", &S[i]);
	sort(S+1, S+N+1, greater<ll>());

	{
		ll x, y;
		x=X%T; y=X/T;
		MM[x]=-y;
	}
	for(int i=1; i<=N; i++)
	{
		ll x, y;
		x=S[i]%T; y=S[i]/T;
		MM[x]=-y;
	}

	for(int i=1; i<=M; i++)
	{
		scanf("%lld%lld", &C[i].first, &C[i].second);
		dp[0]+=C[i].second;
		MM[C[i].first]=C[i].second;

		dp[0]+=W*(X/T);
		if(C[i].first<=X%T) dp[0]+=W;
	}
	dp[0]+=W*(X/T+1);

	K=MM.size();
	int t=1, P;
	for(auto it : MM)
	{
		if(it.first==X%T) P=t;
		A[t++]=it.second;
	}

	for(int i=1; i<=K; i++)
	{
		if(A[i]>0)
		{
			dp[i]=dp[i-1]-A[i];
		}
		else
		{
			dp[i]=1e18;
			ll t=0;
			for(int j=i; j>=1; j--)
			{
				if(A[j]>0)
				{
					t+=X/T+A[i];
					if(j<=P) t++;
				}
				dp[i]=min(dp[i], dp[j-1]-t*W);
			}
		}
	}

	printf("%lld\n", dp[K]);
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |  scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:25:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  for(int i=1; i<=N; i++) scanf("%lld", &S[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
coach.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |   scanf("%lld%lld", &C[i].first, &C[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:74:6: warning: 'P' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |      if(j<=P) t++;
      |      ^~

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