제출 #241491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241491		osaaateiasavtnl	Long Distance Coach (JOI17_coach)	C++17	100 / 100	529 ms	42148 KiB

coach

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
 
const int N = 2e5+7;

const ll inf = 5e18;
bool Q = 0;
struct Line {
    mutable ll m, b, x;
 
    bool operator < (const Line ot) const {
        return Q ? x < ot.x : m < ot.m;
    }
}; 
ll ceil (ll a, ll b) {
    if (a < 0 != b < 0) return a / b;
    return (abs(a) + abs(b) - 1) / abs(b);
} 
ll intersection (const Line &p, const Line &q) {
    return ceil(q.b - p.b, p.m - q.m);
}
struct Hull : multiset<Line> {
    bool valid (auto it) {
        if (it == begin()) {
            auto sig = it;
            sig++;
            if (sig != end()) sig->x = intersection(*it, *sig);
            return it->x = -inf;
        }
 
        auto ant = it, sig = it;
        ant--, sig++;
 
        if (sig == end()) {
            it->x = intersection(*it, *ant);
            return 1;
        }
 
        ll x = intersection(*it, *ant);
        ll y = intersection(*it, *sig);
 
        if (x > y) return 0;
        it->x = x, sig->x = y;
        return 1;
    }
 
    void add (ll m, ll b) {
        m = -m;
        b = -b;

        auto it = lower_bound({m, b, -inf});
 
        if (it != end() && it->m == m) {
            if (it->b > b) return;
            it->b = b;
        } else {
            it = insert({m, b, -inf});
        }
 
        if (!valid(it)) {
            erase(it);
            return;
        }
 
        auto ant = it;
        while (ant != begin()) {
            if (valid(--ant)) break;
            erase(ant);
            if (it == begin()) { it->x = -inf; break; }
            ant = it;
        }
 
        auto sig = it;
        sig++;
        while (sig != end() && !valid(sig))
            erase(sig++);
    }
 
    ll query (ll x) {
        if (empty()) return -inf;
 
        Q = 1;
        auto it = upper_bound({0, 0, x});
        it--;
        Q = 0;
        return x * it->m + it->b;
    }
} h;

int pref[N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int x, n, m, w, t;
    cin >> x >> n >> m >> w >> t;
 
    //first - d, second - c
 
    vector <int> s(n);
    for (int i = 0; i < n; ++i) 
        cin >> s[i];
    sort(all(s));
    s.app(x);
 
    vector <ii> a(m);
    for (int i = 0; i < m; ++i) 
        cin >> a[i].f >> a[i].s;
 
    sort(all(a));
    reverse(all(a));
    a.insert(a.begin(), mp(0, 0));
 
    map <int, int> pos;
    for (int i = 0; i < a.size(); ++i)
        pos[a[i].f] = i;        
 
    vector <int> c;
    for (auto e : a)    
        c.app(e.f);
    sort(all(c));
 
    vector <int> last(s.size()), mem(a.size(), s.size());
    for (int i = 0; i < s.size(); ++i) {
        int p = lower_bound(all(c), s[i]%t) - c.begin();
        p = (p - 1 + c.size()) % c.size();
        last[i] = pos[c[p]];
        mem[last[i]] = min(mem[last[i]], i);
    }
    vector <int> dp(a.size()+1);
    dp[0] = (x/t+1)*w;
    dp[1] = dp[0]+(x/t+(a[1].f<=(x%t)))*w;

    for (int i = 0; i < a.size(); ++i)
        pref[i+1] = pref[i] + a[i].s;

    for (int j = 2; j <= a.size(); ++j) {
        if (mem[j-1] != s.size()) {
            int k = s[mem[j-1]]/t*w;
            int x = -h.query(j-2);
            if (x != inf) {
                h.add(k, x-k*(j-2));
            }   
            int i = j - 2;
            h.add(k, dp[i]-pref[i+1]-i*k);
        } 
        int save = 0;
        if (j < a.size())
            save = (x/t+(a[j].f<=(x%t)))*w;
        int mn = -h.query(j-1)+pref[j];
        mn = min(mn, dp[j-1]);
        dp[j] = mn + save;
    }       
    cout << (int)dp[a.size()] << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

coach.cpp: In function 'long long int ceil(long long int, long long int)':
coach.cpp:26:11: warning: suggest parentheses around comparison in operand of '!=' [-Wparentheses]
     if (a < 0 != b < 0) return a / b;
         ~~^~~
coach.cpp: In function 'int main()':
coach.cpp:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i)
                     ~~^~~~~~~~~~
coach.cpp:138:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i) {
                     ~~^~~~~~~~~~
coach.cpp:148:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i)
                     ~~^~~~~~~~~~
coach.cpp:151:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 2; j <= a.size(); ++j) {
                     ~~^~~~~~~~~~~
coach.cpp:152:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (mem[j-1] != s.size()) {
coach.cpp:162:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (j < a.size())
             ~~^~~~~~~~~~
coach.cpp: In instantiation of 'bool Hull::valid(auto:1) [with auto:1 = std::_Rb_tree_const_iterator<Line>]':
coach.cpp:70:22:   required from here
coach.cpp:38:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
             return it->x = -inf;
                             ^~~

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