Submission #1245183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245183		InvMOD	Long Distance Coach (JOI17_coach)	C++17	100 / 100	199 ms	17640 KiB

coach

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

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define ROF(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) "[" #x " = " << (x) << "]"
#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;

struct Lichao{
    struct Line{
        ld a, b;
        Line(ld a = 0, ld b = -INF): a(a), b(b) {}
        ll slope(){return a;}
        ll f(ll x){return a * x + b;}
        ld intersect(Line &q){return(1.0l * b - q.b) / (1.0l * q.a - a);}
    };

    vector<Line> st; int trsz;
    Lichao(int n = 0): st(n + 1, Line()), trsz(n) {}

    void update(int l, int r, Line curLine){
        if(l > r) return;
        if(l == r){
            st[l] = (st[l].f(l) > curLine.f(l) ? st[l] : curLine);
        }
        else{
            int mid = l+r>>1;
            if(st[mid].f(mid) < curLine.f(mid)) swap(curLine, st[mid]);
            if(st[mid].slope() > curLine.slope()) update(l, mid - 1, curLine);
            if(st[mid].slope() < curLine.slope()) update(mid + 1, r, curLine);
        }
    }

    void addLine(ll a, ll b){
        //cout << "Add: " << a <<" " << b << "\n";
        update(0, trsz, Line(a, b));
    }

    ll query(int l, int r, ll x){
        if(l > r) return LLONG_MIN;
        if(l == r){
            return st[l].f(l);
        }
        int m = l+r>>1;
        if(x < m)
            return max(st[m].f(x), query(l, m - 1, x));
        else return max(st[m].f(x), query(m + 1, r, x));
    }

    ll query(ll x){
        //cout << "Query: " << x << " ";
        return query(0, trsz, x);
    }
};


void solve()
{
    ll X; int n,m,W,T; cin >> X >> n >> m >> W >> T;

    vector<int> S(n + 2), D(m + 1), C(m + 1);

    FOR(i, 1, n) cin >> S[i]; S[n + 1] = X;
    FOR(i, 1, m) cin >> D[i] >> C[i];

    vector<ll> sum(m + 1), sumC(m + 1), lpos(n + 2);
    auto preprocess = [&]() -> void{
        vector<int> _D(D.begin(), D.end());
        vector<int> _C(C.begin(), C.end());

        vector<int> idx(m + 1); iota(all(idx), 0);

        sort(1 + all(idx), [&](int x, int y){ // holy hours of debug cause of this >:(
            return D[x] > D[y];
        });

        FOR(i, 1, m){
            D[i] = _D[idx[i]], C[i] = _C[idx[i]];
            sum[i] = sum[i - 1] + ((X / T) + (X % T >= D[i])) * W;

            sumC[i] = sumC[i - 1] + C[i];
        }
        sort(1 + all(S), [&](int x, int y){return x % T > y % T;});

        FOR(i, 1, n + 1){
            int l = 0, r = m + 1;
            while(l + 1 < r){
                int mid = l+r>>1;
                (D[mid] > S[i] % T ? l = mid : r = mid);
            }
            lpos[i] = l;
        }
    };
    preprocess();

    vector<ll> dp(m + 1, 0); Lichao tree(m);
    for(int i = 1, j = 1; i <= m; i++){
//        for(int z = 1; z <= (n + 1); z++){
//            if(S[z] % T > D[i]){
//                int l = lpos[z];
//                ll cost = (sum[i] - sum[l]) - (sumC[i] - sumC[l]) - W * (S[z] / T) * (i - l);
//                dp[i] = max(dp[i], dp[l] + cost);
//            }
//        }
//        dp[i] = max(dp[i], dp[i - 1]);

        while(j <= (n + 1) && S[j] % T > D[i]){
            int l = lpos[j];
            tree.addLine(-W * (S[j] / T), dp[l] - sum[l] + sumC[l] + W * (S[j] / T) * (l));
            j++;
        }
        dp[i] = max(dp[i - 1], tree.query(i) + sum[i] - sumC[i]);

        //cout << "DP: " << dp[i] << " " << sum[i] - sumC[i] << "\n";
    }

    cout << (sum[m] + ((ll) X / T) * W + W) - dp[m] << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
coach.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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