Submission #363531

#	Time	Username	Problem	Language	Result	Execution time	Memory
363531		denkendoemeer	Long Distance Coach (JOI17_coach)	C++14	100 / 100	198 ms	20572 KiB

coach

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[200005],poz[200005],d[200005],c[200005],c2[200005];
pair<ll,ll>a[200005],b[200005];
struct cht
{
    struct line
    {
        ll x,y;
    };
    vector<line>aux;
    int u;
    long double crossp(line a,line b)
    {
        return (long double)(b.y-a.y)/(long double)(a.x-b.x);
    }
    void add(ll a,ll b)
    {
        line l={a,b};
        while(u>1 && crossp(aux[u-2],aux[u-1])>crossp(aux[u-2],l)){
            aux.pop_back();
            u--;
        }
        aux.push_back(l);
        u++;
    }
    ll query(ll x)
    {
        int st=0,dr=u-2,mij;
        while(st<=dr){
            mij=(st+dr)/2;
            if (crossp(aux[mij],aux[mij+1])<=x)
                st=mij+1;
            else
                dr=mij-1;
        }
        return aux[st].x*x+aux[st].y;
    }
}cht;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll x,w,t;
    int n,m,i;
    scanf("%lld%d%d%lld%lld",&x,&n,&m,&w,&t);
    b[0]={x%t,x/t};
    for(i=1;i<=n;i++){
        ll x;
        scanf("%lld",&x);
        b[i]={x%t,x/t};
    }
    for(i=1;i<=m;i++)
        scanf("%lld%lld",&a[i].first,&a[i].second);
    sort(a+1,a+m+1);
    c2[0]=(x+t-1)/t;
    for(i=1;i<=m;i++){
        c[i]=c[i-1]+a[i].second;
        if (a[i].first<x%t)
            c2[i]=c2[i-1]+x/t+1;
        else
            c2[i]=c2[i-1]+x/t;
    }
    for(i=1;i<=m;i++)
        poz[i]=(x+t-1)/t+1;
    for(i=0;i<=n;i++){
        int aux=upper_bound(a+1,a+m+1,b[i])-a-1;
        poz[aux]=min(poz[aux],b[i].second);
    }
    cht.add(0,-c2[0]*w);
    for(i=1;i<=m;i++){
        dp[i]=max(dp[i-1],cht.query(poz[i])+(c2[i]-i*poz[i])*w-c[i]);
        cht.add(w*i,dp[i]+c[i]-c2[i]*w);
    }
    printf("%lld\n",c2[m]*w-dp[m]);
return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |     scanf("%lld%d%d%lld%lld",&x,&n,&m,&w,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |         scanf("%lld",&x);
      |         ~~~~~^~~~~~~~~~~
coach.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |         scanf("%lld%lld",&a[i].first,&a[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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