oj.uz

Submission #198570

# Submission time Handle Problem Language Result Execution time Memory
198570 2020-01-26T16:38:18 Z arnold518 Long Distance Coach (JOI17_coach) C++14
0 / 100
 184 ms 5112 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 2e5;

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

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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 184 ms 4984 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 4984 KB Output is correct
6 Correct 8 ms 4984 KB Output is correct
7 Correct 8 ms 4984 KB Output is correct
8 Correct 8 ms 4984 KB Output is correct
9 Correct 9 ms 4984 KB Output is correct
10 Correct 8 ms 4984 KB Output is correct
11 Correct 8 ms 4984 KB Output is correct
12 Correct 8 ms 4984 KB Output is correct
13 Correct 8 ms 5112 KB Output is correct
14 Correct 9 ms 5112 KB Output is correct
15 Correct 8 ms 4984 KB Output is correct
16 Correct 8 ms 4984 KB Output is correct
17 Correct 8 ms 5112 KB Output is correct
18 Incorrect 8 ms 5112 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 184 ms 4984 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 4984 KB Output is correct
6 Correct 8 ms 4984 KB Output is correct
7 Correct 8 ms 4984 KB Output is correct
8 Correct 8 ms 4984 KB Output is correct
9 Correct 9 ms 4984 KB Output is correct
10 Correct 8 ms 4984 KB Output is correct
11 Correct 8 ms 4984 KB Output is correct
12 Correct 8 ms 4984 KB Output is correct
13 Correct 8 ms 5112 KB Output is correct
14 Correct 9 ms 5112 KB Output is correct
15 Correct 8 ms 4984 KB Output is correct
16 Correct 8 ms 4984 KB Output is correct
17 Correct 8 ms 5112 KB Output is correct
18 Incorrect 8 ms 5112 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 184 ms 4984 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 4984 KB Output is correct
6 Correct 8 ms 4984 KB Output is correct
7 Correct 8 ms 4984 KB Output is correct
8 Correct 8 ms 4984 KB Output is correct
9 Correct 9 ms 4984 KB Output is correct
10 Correct 8 ms 4984 KB Output is correct
11 Correct 8 ms 4984 KB Output is correct
12 Correct 8 ms 4984 KB Output is correct
13 Correct 8 ms 5112 KB Output is correct
14 Correct 9 ms 5112 KB Output is correct
15 Correct 8 ms 4984 KB Output is correct
16 Correct 8 ms 4984 KB Output is correct
17 Correct 8 ms 5112 KB Output is correct
18 Incorrect 8 ms 5112 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 184 ms 4984 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 4984 KB Output is correct
6 Correct 8 ms 4984 KB Output is correct
7 Correct 8 ms 4984 KB Output is correct
8 Correct 8 ms 4984 KB Output is correct
9 Correct 9 ms 4984 KB Output is correct
10 Correct 8 ms 4984 KB Output is correct
11 Correct 8 ms 4984 KB Output is correct
12 Correct 8 ms 4984 KB Output is correct
13 Correct 8 ms 5112 KB Output is correct
14 Correct 9 ms 5112 KB Output is correct
15 Correct 8 ms 4984 KB Output is correct
16 Correct 8 ms 4984 KB Output is correct
17 Correct 8 ms 5112 KB Output is correct
18 Incorrect 8 ms 5112 KB Output isn't correct
19 Halted 0 ms 0 KB -