Submission #198569

#	Time	Username	Problem	Language	Result	Execution time	Memory
198569		arnold518	Long Distance Coach (JOI17_coach)	C++14	0 / 100	6 ms	504 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 = 2000;

struct Data
{
	ll D, C;
	bool operator < (const Data &p) { return D<p.D; }
};

int N, M;
ll X, W, T, S[MAXN+10], dp[MAXN+10];
Data A[MAXN+10];
vector<pll> V[MAXN+10];

int main()
{
	int i, j;

	scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);
	for(i=1; i<=N; i++) scanf("%lld", &S[i]); S[N+1]=X;
	for(i=1; i<=M; i++) scanf("%lld%lld", &A[i].D, &A[i].C);
	sort(A+1, A+M+1);
	
	for(i=1; i<=N+1; i++)
	{
		ll l, r;
		if(S[i-1]/T==S[i]/T)
		{
			l=S[i-1]%T, r=S[i]%T;
			l=lower_bound(A+1, A+M+1, (Data){l, 0})-A;
			r=lower_bound(A+1, A+M+1, (Data){r, 0})-A-1;
		}
		else
		{
			l=0, r=S[i]%T;
			l=lower_bound(A+1, A+M+1, (Data){l, 0})-A;
			r=lower_bound(A+1, A+M+1, (Data){r, 0})-A-1;
		}
		if(l<=r) V[r].push_back({l, S[i]/T});
	}

	dp[0]=(X/T+1)*W;
	for(i=1; i<=M; i++)
	{
		if(A[i].D<=X%T) dp[i]=dp[i-1]+(X/T+1)*W;
		else dp[i]=dp[i-1]+X/T*W;

		for(auto it : V[i])
		{
			ll s=0;
			for(j=i; j>=it.first; j--)
			{
				s+=A[j].C+W*it.second;
				dp[i]=min(dp[i], dp[j-1]+s);
			}
		}
	}
	printf("%lld", dp[M]);
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:26:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(i=1; i<=N; i++) scanf("%lld", &S[i]); S[N+1]=X;
  ^~~
coach.cpp:26:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(i=1; i<=N; i++) scanf("%lld", &S[i]); S[N+1]=X;
                                            ^
coach.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%d%d%lld%lld", &X, &N, &M, &W, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:26:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld", &S[i]); S[N+1]=X;
                      ~~~~~^~~~~~~~~~~~~~~
coach.cpp:27:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%lld%lld", &A[i].D, &A[i].C);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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