oj.uz

Submission #600694

# Submission time Handle Problem Language Result Execution time Memory
600694 2022-07-21T07:07:31 Z 조영욱(#8469) Long Distance Coach (JOI17_coach) C++17
71 / 100
 2000 ms 8320 KB 
#include <bits/stdc++.h>
using namespace std;

long long x;
int n,m;
long long w,t;
vector<long long> s;
long long c1[200000];
typedef pair<long long,long long> P;
vector<P> vec;
long long mn[200001];
long long psum[200001];
long long dp[200001];

int main() {
    scanf("%lld %d %d %lld %lld",&x,&n,&m,&w,&t);
    for(int i=0;i<n;i++) {
        long long val;
        scanf("%lld",&val);
        s.push_back(val);
    }
    s.push_back(x);
    sort(s.begin(),s.end());
    for(int i=0;i<m;i++) {
        long long d;
        long long c;
        scanf("%lld %lld",&d,&c);
        vec.push_back(P(d,c));
    }
    vec.push_back(P(0,0));
    sort(vec.begin(),vec.end());
    for(int i=0;i<=m;i++) {
        mn[i]=-1;
    }
    for(int i=0;i<s.size();i++) {
        int ind=lower_bound(vec.begin(),vec.end(),P(s[i]%t,-1))-vec.begin()-1;
        if (mn[ind]==-1) {
            mn[ind]=s[i]/t;
        }
    }
    dp[0]=((x/t)+1)*w;
    for(int i=1;i<=m;i++) {
        psum[i]=psum[i-1]+vec[i].second;
        long long cnt=x/t+(vec[i].first<x%t);
        dp[i]=9e18;
        dp[i]=min(dp[i],dp[i-1]+cnt*w);
        if (mn[i]!=-1) {
            for(int j=0;j<i;j++) {
                dp[i]=min(dp[i],dp[j]+mn[i]*w*(i-j)+psum[i]-psum[j]);
            }
        }
        //printf(".%lld\n",dp[i]);
    }
    printf("%lld",dp[m]);
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<s.size();i++) {
      |                 ~^~~~~~~~~
coach.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%lld %d %d %lld %lld",&x,&n,&m,&w,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf("%lld",&val);
      |         ~~~~~^~~~~~~~~~~~~
coach.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%lld %lld",&d,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
0 / 29.0

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