제출 #432274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432274		kai824	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2076 ms	12840 KiB

coach

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

#define int long long
typedef pair<int,int> pii;
#define f first
#define s second
#define mp make_pair

int x,n,m,w,t;
int kp[200005],dp[200005];
int dea[200005];
pii ppl[200005];

inline int calc(int dj,int cur_time){
  return ((cur_time/t) + (dj<=(cur_time%t)?1:0))*w;
}

int32_t main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  cin>>x>>n>>m>>w>>t;

  for(int i=0;i<n;i++){//"break points"
    cin>>kp[i];
  }
  kp[n++]=x;
  for(int i=1;i<=m;i++){//the ppl...
    cin>>ppl[i].f>>ppl[i].s;//d_j, refund cost
  }
  ppl[0]=mp(0,0);//driver...
  sort(ppl,ppl+m+1);
  //prefix sum refund costs
  for(int i=1;i<=m;i++){
    ppl[i].s+=ppl[i-1].s;
  }

  for(int i=0;i<n;i++){
    int it=upper_bound(ppl,ppl+m+1,mp(kp[i]%t,LLONG_MAX))-ppl-1;
    if(dea[it]==0)dea[it]=kp[i];
    else dea[it]=min(dea[it],kp[i]);
  }
  dp[0]=calc(0,x);
  for(int i=1;i<=m;i++){
    //cout<<ppl[i].s<<'\n';
    int val=dp[i-1]+calc(ppl[i].f,x);//if we don't refund...
    if(dea[i]>0){
      for(int j=0;j<i;j++){
        val=min(val,dp[j]+ppl[i].s-ppl[j].s+((i-j)*(calc(ppl[i].f,dea[i]-t)) ));
      }
    }
    dp[i]=val;
    // cout<<i<<' '<<dp[i]<<'\n';
  }
  cout<<dp[m];
  return 0;
}

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