oj.uz

Submission #600682

# Submission time Handle Problem Language Result Execution time Memory
600682 2022-07-21T06:59:04 Z 조영욱(#8469) Long Distance Coach (JOI17_coach) C++17
0 / 100
 1 ms 340 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);
    for(int i=0;i<m;i++) {
        int d;
        long long c;
        scanf("%d %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%t<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:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     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:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%d %lld",&d,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 0 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 0 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 0 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 0 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -