oj.uz

Submission #432268

# Submission time Handle Problem Language Result Execution time Memory
432268 2021-06-18T06:52:05 Z kai824 Long Distance Coach (JOI17_coach) C++17
0 / 100
 1 ms 332 KB 
#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(dp[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])-w) ));
      }
    }
    dp[i]=val;
  }
  cout<<dp[m];
  return 0;
}

Subtask #1
0 / 16.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 29.0

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