oj.uz

Submission #61248

# Submission time Handle Problem Language Result Execution time Memory
61248 2018-07-25T13:21:29 Z zubec Salesman (IOI09_salesman) C++14
62 / 100
 466 ms 66560 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 500100;

struct str1{
    int t, l, m;
    int ans;

    bool operator < (const str1& se) const{
        return (t < se.t || (t == se.t && l < se.l));
    }
};

struct set_cmp{
    bool operator() (const str1& fi, const str1& se){
        return fi.l < se.l;
    }
};

str1 a[N];
set<str1, set_cmp> q;

int d, u, s, n;

int rast(int a, int b){
    if (a < b)
        return (b-a)*d; else
        return (a-b)*u;
}

int get(int pos){
    auto it = q.lower_bound(a[pos]);
    auto it2 = it;
    if (it != q.begin())
        --it;
    if (it2 == q.end())
        --it2;
    return max(it->ans-rast(it->l, a[pos].l), it2->ans-rast(it2->l, a[pos].l)) + a[pos].m;
}

void insrt(int pos){
    q.insert(a[pos]);
    auto my_it = q.lower_bound(a[pos]);
    auto it = my_it;
    while(it != q.begin()){
        --it;
        if (it->ans - rast(it->l, a[pos].l) >= a[pos].ans){
            q.erase(my_it);
            return;
        }
        if (a[pos].ans - rast(a[pos].l, it->l) < it->ans)
            break;
        q.erase(it);
        it = my_it;
    }
    it = my_it;
    ++it;
    while(it != q.end()){
        if (it->ans - rast(it->l, a[pos].l) >= a[pos].ans){
            q.erase(my_it);
            return;
        }
        if (a[pos].ans - rast(a[pos].l, it->l) < it->ans)
            break;
        q.erase(it);
        it = my_it;
        ++it;
    }
}

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

    cin >> n >> u >> d >> s;
    for (int i = 1; i <= n; i++){
        cin >> a[i].t >> a[i].l >> a[i].m;
    }
    a[0].l = s;
    a[n+1].l = s;
    a[n+1].t = 1e9;
    ++n;
    sort(a+1, a+n+1);
    insrt(0);
    for (int i = 1; i <= n; i++){
        a[i].ans = get(i);
        insrt(i);
    }
    cout << a[n].ans;

}

Subtask #1
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 612 KB Output is correct
4 Correct 4 ms 612 KB Output is correct
5 Correct 7 ms 696 KB Output is correct
6 Correct 16 ms 1456 KB Output is correct
7 Correct 47 ms 2724 KB Output is correct
8 Correct 93 ms 5368 KB Output is correct
9 Correct 125 ms 8660 KB Output is correct
10 Correct 261 ms 17224 KB Output is correct
11 Correct 272 ms 21128 KB Output is correct
12 Correct 363 ms 29044 KB Output is correct
13 Correct 350 ms 35292 KB Output is correct
14 Correct 447 ms 45708 KB Output is correct
15 Correct 466 ms 56404 KB Output is correct
16 Correct 461 ms 62020 KB Output is correct
17 Correct 3 ms 62020 KB Output is correct
18 Incorrect 2 ms 62020 KB Output isn't correct
19 Incorrect 3 ms 62020 KB Output isn't correct
20 Incorrect 5 ms 62020 KB Output isn't correct
21 Incorrect 5 ms 62020 KB Output isn't correct
22 Incorrect 4 ms 62020 KB Output isn't correct
23 Incorrect 7 ms 62020 KB Output isn't correct
24 Incorrect 7 ms 62020 KB Output isn't correct
25 Incorrect 61 ms 62020 KB Output isn't correct
26 Incorrect 215 ms 62028 KB Output isn't correct
27 Runtime error 305 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
28 Runtime error 351 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
29 Runtime error 400 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
30 Runtime error 317 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.