oj.uz

Submission #241489

# Submission time Handle Problem Language Result Execution time Memory
241489 2020-06-24T09:16:03 Z osaaateiasavtnl Long Distance Coach (JOI17_coach) C++17
71 / 100
 430 ms 51172 KB 
#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 = 1e5+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;
    const int INF = 1e9;
    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));
            }   

            for (int i = j - 2; i <= j - 2; ++i) {
                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]);

        //cout << j << ' ' << mn << ' ' << save << ' ' << mn + save << endl;
        //cout << "query " << -h.query(j-1)+pref[j] << endl;
        dp[j] = mn + save;
    }       
    cout << (int)dp[a.size()] << endl;
}

Compilation message

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:149:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); ++i)
                     ~~^~~~~~~~~~
coach.cpp:152:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 2; j <= a.size(); ++j) {
                     ~~^~~~~~~~~~~
coach.cpp:153:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (mem[j-1] != s.size()) {
coach.cpp:167:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (j < a.size())
             ~~^~~~~~~~~~
coach.cpp:146:15: warning: unused variable 'INF' [-Wunused-variable]
     const int INF = 1e9;
               ^~~
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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 5 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 5 ms 384 KB Output is correct
38 Correct 7 ms 640 KB Output is correct
39 Correct 7 ms 768 KB Output is correct
40 Correct 7 ms 640 KB Output is correct
41 Correct 7 ms 640 KB Output is correct
42 Correct 7 ms 640 KB Output is correct
43 Correct 7 ms 640 KB Output is correct
44 Correct 6 ms 640 KB Output is correct
45 Correct 6 ms 640 KB Output is correct
46 Correct 6 ms 768 KB Output is correct
47 Correct 7 ms 640 KB Output is correct
48 Correct 7 ms 640 KB Output is correct
49 Correct 7 ms 640 KB Output is correct
50 Correct 6 ms 640 KB Output is correct
51 Correct 6 ms 640 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 4 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 384 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Correct 5 ms 384 KB Output is correct
31 Correct 5 ms 384 KB Output is correct
32 Correct 5 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 5 ms 384 KB Output is correct
35 Correct 5 ms 384 KB Output is correct
36 Correct 5 ms 384 KB Output is correct
37 Correct 5 ms 384 KB Output is correct
38 Correct 7 ms 640 KB Output is correct
39 Correct 7 ms 768 KB Output is correct
40 Correct 7 ms 640 KB Output is correct
41 Correct 7 ms 640 KB Output is correct
42 Correct 7 ms 640 KB Output is correct
43 Correct 7 ms 640 KB Output is correct
44 Correct 6 ms 640 KB Output is correct
45 Correct 6 ms 640 KB Output is correct
46 Correct 6 ms 768 KB Output is correct
47 Correct 7 ms 640 KB Output is correct
48 Correct 7 ms 640 KB Output is correct
49 Correct 7 ms 640 KB Output is correct
50 Correct 6 ms 640 KB Output is correct
51 Correct 6 ms 640 KB Output is correct
52 Runtime error 430 ms 51172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -