Submission #431687

#	Time	Username	Problem	Language	Result	Execution time	Memory
431687		tqbfjotld	Long Distance Coach (JOI17_coach)	C++14	71 / 100	293 ms	112792 KiB

coach

#include <bits/stdc++.h>
using namespace std;
#define int long long

int X,N,M,W,T;
int refill_points[200005];
int init_t[200005];
int cost[200005];
int cost_pref[200005];
int cost_2[200005];
vector<pair<int,int> > points;
vector<pair<int,pair<int,int> > > passenger_mod;
vector<int> tvals;

int memo[2005][2005];
int val[200005];

int func(int pos, int vv){
    if (pos==-1) return 0;
    if (memo[pos][vv]!=-1) return memo[pos][vv];
    int curans = func(pos-1,tvals.size())+cost_2[pos];
    if (vv!=tvals.size()){
        curans = min(curans,W*tvals[vv]+func(pos-1,vv)+cost[pos]);
    }
    if (val[pos]!=-1){
        int v2 = min(vv,(int)(lower_bound(tvals.begin(),tvals.end(),val[pos])-tvals.begin()));
        curans = min(curans,W*tvals[v2]+func(pos-1,v2)+cost[pos]);
    }
    //printf("func %lld %lld, %lld = %lld\n",pos,vv,tvals[vv],curans);
    return memo[pos][vv] = curans;
}

main(){
    scanf("%lld%lld%lld%lld%lld",&X,&N,&M,&W,&T);
    refill_points[0] = 0;
    for (int x = 1; x<=N; x++){
        scanf("%lld",&refill_points[x]);
    }
    N++;
    refill_points[N] = X;
    sort(refill_points,refill_points+N+1);
    for (int x = 0; x<M; x++){
        int a,b;
        scanf("%lld%lld",&a,&b);
        passenger_mod.push_back({a%T,{a,b}});
    }
    sort(passenger_mod.begin(),passenger_mod.end());
    for (int x = 0; x<M; x++){
        init_t[x] = passenger_mod[x].second.first;
        cost[x] = passenger_mod[x].second.second;
        if (x==0) cost_pref[x] = cost[x];
        else cost_pref[x] = cost_pref[x-1]+cost[x];
    }
    for (int x = 0; x<=N; x++){
        int num = lower_bound(passenger_mod.begin(),passenger_mod.end(),make_pair(refill_points[x]%T+1,make_pair(-1LL,-1LL)))-passenger_mod.begin();
        points.push_back({num,refill_points[x]/T});
    }
    /*
    set<pair<int,int> > prev_stuff;
    prev_stuff.insert({0,0});
    for (int x = 1; x<=N; x++){
        auto it = prev_stuff.upper_bound({points[x].first,points[x].second});
        it--;
        int ind = (*it).second;
        memo[x] = memo[ind]+(points[x].first-points[ind].first)*(points[x].second);
        prev_stuff.insert({points[x].first,x});
        printf("memo %lld = %lld * %lld = %lld\n",x,points[x].first-points[ind].first,points[x].second,memo[x]);
    }
    */
    for (int x = M-1; x>=0; x--){
        cost_2[x] = X/T+(X%T>init_t[x]%T?1:0);
        cost_2[x] *= W;
      //  printf("cost_2 %lld = %lld\n",x,cost_2[x]);
    }
    /*
    int finans = 999999999999999999LL;
    for (int x = 0; x<=N; x++){
        finans = min(finans,W*memo[x]+(points[x].first==0?0:cost_pref[points[x].first-1])+W*cost_2[points[x].first]+W*(X/T+1));
        printf("now finans = %lld\n",finans);
    }
    printf("%lld\n",finans);
    */
    memset(val,-1,sizeof(val));
    for (auto x : points){
        if (x.first!=0LL)
        {

        if (val[x.first-1]==-1){
            val[x.first-1] = x.second;
        }
        else val[x.first-1] = min(val[x.first-1],x.second);
        }
        tvals.push_back(x.second);
       // printf("set val %lld to %lld,%lld\n",x.first-1,val[x.first-1],x.second);
    }
    sort(tvals.begin(),tvals.end());
    memset(memo,-1,sizeof(memo));
    printf("%lld\n",func(M-1,tvals.size())+W*(X/T+1));
}

Compilation message (stderr)

coach.cpp: In function 'long long int func(long long int, long long int)':
coach.cpp:22:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if (vv!=tvals.size()){
      |         ~~^~~~~~~~~~~~~~
coach.cpp: At global scope:
coach.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main(){
      | ^~~~
coach.cpp: In function 'int main()':
coach.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%lld%lld%lld%lld%lld",&X,&N,&M,&W,&T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%lld",&refill_points[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%lld%lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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