oj.uz

Submission #27668

# Submission time Handle Problem Language Result Execution time Memory
27668 2017-07-13T11:43:06 Z suhgyuho_william Long Distance Coach (JOI17_coach) C++14
71 / 100
 2000 ms 11396 KB 
#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007

using namespace std;

int N,M;
lld X,W,T;
lld a[200002],d[200002],memo[200002],sum[200002];
struct data{
	lld d,c;
	data(){}
	data(lld d,lld c):d(d),c(c){}
	bool operator < (const data &cmp) const{
		return d < cmp.d;
	}
}b[200002];

lld get(lld x){
	return ((X-x)/T+1)*W;
}

int main(){
	long long iX,iW,iT;
	scanf("%lld %d %d %lld %lld",&iX,&N,&M,&iW,&iT);
	X = iX; W = iW; T = iT;
	for(int i=1; i<=N; i++){
		long long ia;
		scanf("%lld",&ia);
		a[i] = ia;
	}
	sort(a+1,a+N+1);
	for(int i=1; i<=M; i++){
		long long id,ic;
		scanf("%lld %lld",&id,&ic);
		b[i].d = id; b[i].c = ic;
	}
	sort(b+1,b+M+1);
	a[N+1] = X;
	for(int i=1; i<=M; i++){
		memo[i] = Linf;
		sum[i] = sum[i-1]+b[i].c;
	}
	for(int i=1; i<=N+1; i++){
		int it;
		it = lower_bound(b+1,b+M+1,data(a[i]%T,0))-b-1;
		memo[it] = min(memo[it],a[i]/T);
	}
	d[0] = get(0);
	for(int i=1; i<=M; i++){
		d[i] = d[i-1]+get(b[i].d);
		if(memo[i] == Linf) continue;
		for(int j=0; j<i; j++){
			d[i] = min(d[i],d[j]+sum[i]-sum[j]+W*(i-j)*memo[i]);
		}
	}
	long long print = d[M];
	printf("%lld\n",print);

	return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:32:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %d %d %lld %lld",&iX,&N,&M,&iW,&iT);
                                                 ^
coach.cpp:36:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&ia);
                    ^
coach.cpp:42:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&id,&ic);
                             ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11396 KB Output is correct
2 Correct 0 ms 11396 KB Output is correct
3 Correct 0 ms 11396 KB Output is correct
4 Correct 0 ms 11396 KB Output is correct
5 Correct 0 ms 11396 KB Output is correct
6 Correct 0 ms 11396 KB Output is correct
7 Correct 0 ms 11396 KB Output is correct
8 Correct 0 ms 11396 KB Output is correct
9 Correct 0 ms 11396 KB Output is correct
10 Correct 0 ms 11396 KB Output is correct
11 Correct 0 ms 11396 KB Output is correct
12 Correct 0 ms 11396 KB Output is correct
13 Correct 0 ms 11396 KB Output is correct
14 Correct 0 ms 11396 KB Output is correct
15 Correct 0 ms 11396 KB Output is correct
16 Correct 0 ms 11396 KB Output is correct
17 Correct 0 ms 11396 KB Output is correct
18 Correct 0 ms 11396 KB Output is correct
19 Correct 0 ms 11396 KB Output is correct
20 Correct 0 ms 11396 KB Output is correct
21 Correct 0 ms 11396 KB Output is correct
22 Correct 0 ms 11396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11396 KB Output is correct
2 Correct 0 ms 11396 KB Output is correct
3 Correct 0 ms 11396 KB Output is correct
4 Correct 0 ms 11396 KB Output is correct
5 Correct 0 ms 11396 KB Output is correct
6 Correct 0 ms 11396 KB Output is correct
7 Correct 0 ms 11396 KB Output is correct
8 Correct 0 ms 11396 KB Output is correct
9 Correct 0 ms 11396 KB Output is correct
10 Correct 0 ms 11396 KB Output is correct
11 Correct 0 ms 11396 KB Output is correct
12 Correct 0 ms 11396 KB Output is correct
13 Correct 0 ms 11396 KB Output is correct
14 Correct 0 ms 11396 KB Output is correct
15 Correct 0 ms 11396 KB Output is correct
16 Correct 0 ms 11396 KB Output is correct
17 Correct 0 ms 11396 KB Output is correct
18 Correct 0 ms 11396 KB Output is correct
19 Correct 0 ms 11396 KB Output is correct
20 Correct 0 ms 11396 KB Output is correct
21 Correct 0 ms 11396 KB Output is correct
22 Correct 0 ms 11396 KB Output is correct
23 Correct 0 ms 11396 KB Output is correct
24 Correct 0 ms 11396 KB Output is correct
25 Correct 0 ms 11396 KB Output is correct
26 Correct 0 ms 11396 KB Output is correct
27 Correct 0 ms 11396 KB Output is correct
28 Correct 0 ms 11396 KB Output is correct
29 Correct 0 ms 11396 KB Output is correct
30 Correct 0 ms 11396 KB Output is correct
31 Correct 0 ms 11396 KB Output is correct
32 Correct 0 ms 11396 KB Output is correct
33 Correct 0 ms 11396 KB Output is correct
34 Correct 0 ms 11396 KB Output is correct
35 Correct 0 ms 11396 KB Output is correct
36 Correct 0 ms 11396 KB Output is correct
37 Correct 0 ms 11396 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11396 KB Output is correct
2 Correct 0 ms 11396 KB Output is correct
3 Correct 0 ms 11396 KB Output is correct
4 Correct 0 ms 11396 KB Output is correct
5 Correct 0 ms 11396 KB Output is correct
6 Correct 0 ms 11396 KB Output is correct
7 Correct 0 ms 11396 KB Output is correct
8 Correct 0 ms 11396 KB Output is correct
9 Correct 0 ms 11396 KB Output is correct
10 Correct 0 ms 11396 KB Output is correct
11 Correct 0 ms 11396 KB Output is correct
12 Correct 0 ms 11396 KB Output is correct
13 Correct 0 ms 11396 KB Output is correct
14 Correct 0 ms 11396 KB Output is correct
15 Correct 0 ms 11396 KB Output is correct
16 Correct 0 ms 11396 KB Output is correct
17 Correct 0 ms 11396 KB Output is correct
18 Correct 0 ms 11396 KB Output is correct
19 Correct 0 ms 11396 KB Output is correct
20 Correct 0 ms 11396 KB Output is correct
21 Correct 0 ms 11396 KB Output is correct
22 Correct 0 ms 11396 KB Output is correct
23 Correct 0 ms 11396 KB Output is correct
24 Correct 0 ms 11396 KB Output is correct
25 Correct 0 ms 11396 KB Output is correct
26 Correct 0 ms 11396 KB Output is correct
27 Correct 0 ms 11396 KB Output is correct
28 Correct 0 ms 11396 KB Output is correct
29 Correct 0 ms 11396 KB Output is correct
30 Correct 0 ms 11396 KB Output is correct
31 Correct 0 ms 11396 KB Output is correct
32 Correct 0 ms 11396 KB Output is correct
33 Correct 0 ms 11396 KB Output is correct
34 Correct 0 ms 11396 KB Output is correct
35 Correct 0 ms 11396 KB Output is correct
36 Correct 0 ms 11396 KB Output is correct
37 Correct 0 ms 11396 KB Output is correct
38 Correct 3 ms 11396 KB Output is correct
39 Correct 3 ms 11396 KB Output is correct
40 Correct 3 ms 11396 KB Output is correct
41 Correct 3 ms 11396 KB Output is correct
42 Correct 3 ms 11396 KB Output is correct
43 Correct 0 ms 11396 KB Output is correct
44 Correct 3 ms 11396 KB Output is correct
45 Correct 3 ms 11396 KB Output is correct
46 Correct 3 ms 11396 KB Output is correct
47 Correct 3 ms 11396 KB Output is correct
48 Correct 3 ms 11396 KB Output is correct
49 Correct 3 ms 11396 KB Output is correct
50 Correct 3 ms 11396 KB Output is correct
51 Correct 3 ms 11396 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11396 KB Output is correct
2 Correct 0 ms 11396 KB Output is correct
3 Correct 0 ms 11396 KB Output is correct
4 Correct 0 ms 11396 KB Output is correct
5 Correct 0 ms 11396 KB Output is correct
6 Correct 0 ms 11396 KB Output is correct
7 Correct 0 ms 11396 KB Output is correct
8 Correct 0 ms 11396 KB Output is correct
9 Correct 0 ms 11396 KB Output is correct
10 Correct 0 ms 11396 KB Output is correct
11 Correct 0 ms 11396 KB Output is correct
12 Correct 0 ms 11396 KB Output is correct
13 Correct 0 ms 11396 KB Output is correct
14 Correct 0 ms 11396 KB Output is correct
15 Correct 0 ms 11396 KB Output is correct
16 Correct 0 ms 11396 KB Output is correct
17 Correct 0 ms 11396 KB Output is correct
18 Correct 0 ms 11396 KB Output is correct
19 Correct 0 ms 11396 KB Output is correct
20 Correct 0 ms 11396 KB Output is correct
21 Correct 0 ms 11396 KB Output is correct
22 Correct 0 ms 11396 KB Output is correct
23 Correct 0 ms 11396 KB Output is correct
24 Correct 0 ms 11396 KB Output is correct
25 Correct 0 ms 11396 KB Output is correct
26 Correct 0 ms 11396 KB Output is correct
27 Correct 0 ms 11396 KB Output is correct
28 Correct 0 ms 11396 KB Output is correct
29 Correct 0 ms 11396 KB Output is correct
30 Correct 0 ms 11396 KB Output is correct
31 Correct 0 ms 11396 KB Output is correct
32 Correct 0 ms 11396 KB Output is correct
33 Correct 0 ms 11396 KB Output is correct
34 Correct 0 ms 11396 KB Output is correct
35 Correct 0 ms 11396 KB Output is correct
36 Correct 0 ms 11396 KB Output is correct
37 Correct 0 ms 11396 KB Output is correct
38 Correct 3 ms 11396 KB Output is correct
39 Correct 3 ms 11396 KB Output is correct
40 Correct 3 ms 11396 KB Output is correct
41 Correct 3 ms 11396 KB Output is correct
42 Correct 3 ms 11396 KB Output is correct
43 Correct 0 ms 11396 KB Output is correct
44 Correct 3 ms 11396 KB Output is correct
45 Correct 3 ms 11396 KB Output is correct
46 Correct 3 ms 11396 KB Output is correct
47 Correct 3 ms 11396 KB Output is correct
48 Correct 3 ms 11396 KB Output is correct
49 Correct 3 ms 11396 KB Output is correct
50 Correct 3 ms 11396 KB Output is correct
51 Correct 3 ms 11396 KB Output is correct
52 Execution timed out 2000 ms 11396 KB Execution timed out
53 Halted 0 ms 0 KB -