Submission #1209033

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209033		mychecksedad	Long Distance Coach (JOI17_coach)	C++20	0 / 100	0 ms	328 KiB

coach

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2005, M = 1e5+10, K = 52, MX = 30;
const ll INF = 1e18;

struct Line{
  ll m, b; // x * m + b
  ll eval(ll x){
    return x * m + b;
  }
};

double intersect(Line x, Line y){
  return (double) (x.b - y.b) / (double)(y.m - x.m);
}

struct CH{
  vector<Line> ch;
  void add(ll b, ll m){
    Line nw = {m, b};
    while(ch.size() > 1 && intersect(ch[int(ch.size()) - 2], nw) >= intersect(ch[int(ch.size()) - 2], ch.back())){
      ch.pop_back();
    }
    ch.pb(nw);
  }
  ll get(ll x){
    if(ch.size() == 0) return 0ll;
    if(ch.size() == 1) return ch[0].eval(x);
    ll res = INF;
    int l = 0, r = int(ch.size()) - 2;
    while(l <= r){
      int mid = l+r>>1;
      double pt = intersect(ch[mid], ch[mid+1]);
      if(x >= pt){
        res = min(res, ch[mid].eval(x));
        l = mid + 1;   
      }else{
        res = min(res, ch[mid + 1].eval(x));
        res = min(res, ch[mid].eval(x));
        r = mid - 1;
      }
    }
    // for(auto ln: ch) res=min(res,ln.eval(x));
    return res;
  }
};


ll X, n, m, W, T, ans, pref[N];
ll s[N], DP[N], cost[N][N];
array<ll, 2> a[N];
void solve(){
  cin >> X >> n >> m >> W >> T;
  for(int i = 1; i <= n; ++i){
    cin >> s[i];
  }
  ans = X / T + 1;
  for(int i = 1; i <= m; ++i){
    cin >> a[i][0] >> a[i][1];
    ans += (X - a[i][0] + T - 1) / T;
  }
  ans *= W;
  sort(a+1, a+1+m); 

  pref[0] = 0;
  for(int i = 1; i <= m; ++i){
    pref[i] = pref[i - 1] + a[i][1];
  }

  for(int i = 0; i <= m; ++i){
    for(int j = 0; j <= m; ++j){
      cost[i][j] = INF;
    }
    DP[i] = 0;
  }

  int L = lower_bound(a+1, a+1+m, array<ll, 2>{X%T, -1}) - a; --L;

  vector<ll> A(m + 1, -37);

  sort(s + 1, s + 1 + n);


  s[n + 1] = X;
  for(int i = 1; i <= n + 1; ++i){
    int pos = lower_bound(a+1, a+1+m, array<ll, 2>{s[i] % T, -1}) - a;
    --pos;
    int r = pos;
    if(A[r] == -37) A[r] = ((X - ((s[i] / T) * T + a[r][0]) + T - 1) / T) * W;
  }

  CH CH1, CH2;

  CH1.add(0, 0);
  CH2.add(0, 0);
  for(int i = 1; i <= m; ++i){
    DP[i] = DP[i - 1] + pref[i - 1];
    if(A[i] == -37){
      // cerr << DP[i] << ' ';
      DP[i] -= pref[i];
      if(i <= L)
        CH1.add(DP[i], i);
      else
        CH2.add(DP[i], i);
      continue;
    }
    if(i <= L){
      // cerr << CH1.get(A[i]) + pref[i] - i * A[i] << ' ';
      DP[i] = min(DP[i], CH1.get(A[i]) + pref[i] - i * A[i]);
    }else{
      DP[i] = min(DP[i], CH1.get(A[i] + W) - L * (A[i] + W) - (i - L) * A[i] + pref[i]);
      DP[i] = min(DP[i], CH2.get(A[i]) + pref[i] - i * A[i]);
    }
    DP[i] -= pref[i];
    if(i <= L)
      CH1.add(DP[i], i);
    else
      CH2.add(DP[i], i);
    // for(int j = 0; j < i; ++j){
    //   if(i > L)
    //     DP[i] = min(DP[i], DP[j] + -(j >= L ? (i - j) * A[i] : (i - L) * A[i] + (A[i] + 1) * (L-j)) * W + pref[i]);
    //   else
    //     DP[i] = min(DP[i], DP[j] + pref[i] - W * (i - j) * A[i]);
    // }
    // cerr << DP[i] << ' ';
  }
  cout << ans + DP[m] + pref[m];
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

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