oj.uz

Submission #432274

# Submission time Handle Problem Language Result Execution time Memory
432274 2021-06-18T07:01:48 Z kai824 Long Distance Coach (JOI17_coach) C++17
71 / 100
 2000 ms 12840 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(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.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 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct

Subtask #2
30.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 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 312 KB Output is correct
28 Correct 1 ms 320 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 324 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct

Subtask #3
25.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 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 312 KB Output is correct
28 Correct 1 ms 320 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 324 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 4 ms 460 KB Output is correct
39 Correct 4 ms 460 KB Output is correct
40 Correct 5 ms 460 KB Output is correct
41 Correct 3 ms 460 KB Output is correct
42 Correct 3 ms 332 KB Output is correct
43 Correct 3 ms 332 KB Output is correct
44 Correct 3 ms 460 KB Output is correct
45 Correct 3 ms 372 KB Output is correct
46 Correct 4 ms 332 KB Output is correct
47 Correct 4 ms 460 KB Output is correct
48 Correct 3 ms 460 KB Output is correct
49 Correct 3 ms 460 KB Output is correct
50 Correct 3 ms 460 KB Output is correct
51 Correct 3 ms 332 KB Output is correct

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 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 316 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 316 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 312 KB Output is correct
28 Correct 1 ms 320 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Correct 1 ms 324 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 4 ms 460 KB Output is correct
39 Correct 4 ms 460 KB Output is correct
40 Correct 5 ms 460 KB Output is correct
41 Correct 3 ms 460 KB Output is correct
42 Correct 3 ms 332 KB Output is correct
43 Correct 3 ms 332 KB Output is correct
44 Correct 3 ms 460 KB Output is correct
45 Correct 3 ms 372 KB Output is correct
46 Correct 4 ms 332 KB Output is correct
47 Correct 4 ms 460 KB Output is correct
48 Correct 3 ms 460 KB Output is correct
49 Correct 3 ms 460 KB Output is correct
50 Correct 3 ms 460 KB Output is correct
51 Correct 3 ms 332 KB Output is correct
52 Execution timed out 2076 ms 12840 KB Time limit exceeded
53 Halted 0 ms 0 KB -