Submission #866275

#	Time	Username	Problem	Language	Result	Execution time	Memory
866275		hqminhuwu	Long Distance Coach (JOI17_coach)	C++14	100 / 100	155 ms	43376 KiB

coach

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e18;
const ll mod = 1e9 + 7;

bool flag;
struct line {
    mutable ll k,m,p;
    bool operator < (const line&u) const {
        return flag ? p < u.p : k < u.k;
    }
};

struct linecontainer : multiset <line> {
    ll fdiv (ll a, ll b){
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool its (iterator x, iterator y){
        if (y == end()) return x -> p = oo,0;
        if (y -> k == x -> k) x -> p = x -> m > y -> m ? oo : -oo;
        else x -> p = fdiv (x -> m - y -> m, y -> k - x -> k);
        return x -> p >= y -> p;
    }
    void add (ll k, ll m){
        auto z = insert({k,m,0}),y = z++, x = y;
        while (its(y,z)) z = erase(z);
        if (x != begin() && its(--x,y)) y = erase(y);
        while ((y = x) != begin() && (--x) -> p >= y -> p) its(x,y = erase(y));
    }
    ll query(ll x){
        if (empty()) return -oo;
        flag = 1;
        line l = *lower_bound({0,0,x});
        flag = 0;
        return l.k * x + l.m;
    }
};
ll x,n,m,w,t,s[N],i,sum,refd[N],dp[N];
pll f[N];
linecontainer lc;
vector <ll> ev[N];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> x >> n >> m >> w >> t;
    x--;
    forr (i,1,n)
        cin >> s[i];
    forr (i,1,m){
        cin >> f[i].st >> f[i].nd;
        if (f[i].st <= x % t)
            f[i].nd -= w,sum += w;
    }
    n++;
    s[n] = x;
    sort(f + 1, f + 1 + m);
    ll lmt = x / t;
    sum += lmt * (m + 1) * w + w;
    forr (i,1,n){
        int k = upper_bound (f + 1, f + 1 + m, mp(s[i] % t,0ll)) - f - 1;
        if (k == 0)
            continue;
        ev[k].pb(lmt - s[i] / t);
    }
    forr (i,1,m)
        refd[i] = refd[i - 1] + f[i].nd;
    //cout << lmt << " " << sum << "\n";
    ll ans = 0;
    ford (i,m,1){
        dp[i] = dp[i + 1];

        for (ll u : ev[i])
            lc.add(w * u, dp[i] + (i + 1) * u * w - refd[i]);
        ll tmp = lc.query(-i) + refd[i - 1];
        dp[i] = max (dp[i],tmp);
        ans = max (ans,dp[i]);
      //  cout << dp[i] << " " << refd[i] << " " << f[i].nd << "\n";
    }
    cout << sum - ans;
    return 0;
}
/*



*/

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