Submission #300078

# Submission time Handle Problem Language Result Execution time Memory
300078 2020-09-16T13:07:23 Z tatyam Salesman (IOI09_salesman) C++17
52 / 100
1120 ms 65540 KB
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int INF = 0x3fffffff;
using pii = pair<int, int>;
using tuplis = array<int, 3>;
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
#define rep(n) for(int i = 0; i < n; i++)
#define rrep(n) for(int i = n; --i; )
#define each(i, a) for(auto&& i : a)
#define all(a) begin(a), end(a)
 
 
int n, u, d, s;
struct T{
    map<int, int> up;
    map<int, int, greater<int>> down;
    T(int s){
        up[s] = 0;
        down[s] = 0;
        up[1000000] = -INF;
        down[0] = -INF;
    }
    int operator[](int at){
        int ans = -INF;
        pii a = *up.lower_bound(at);
        chmax(ans, a.second - (a.first - at) * u);
        a = *down.lower_bound(at);
        chmax(ans, a.second - (at - a.first) * d);
        return ans;
    }
    void insert(int at, int val){
        auto p = up.try_emplace(at, -INF).first;
        if(chmax(p->second, val)){
            while(p != up.begin()){
                auto q = prev(p);
                if(p->second - q->second >= (p->first - q->first) * u) up.erase(q);
                else break;
            }
        }
        p = down.try_emplace(at, -INF).first;
        if(chmax(p->second, val)){
            while(p != down.begin()){
                auto q = prev(p);
                if(p->second - q->second >= (q->first - p->first) * d) down.erase(q);
                else break;
            }
        }
    }
};
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n >> u >> d >> s;
    T q(s);
    vector<tuplis> a(n);
    each(i, a) each(j, i) cin >> j;
    map<int, vector<pii>> b;
    each(i, a) b[i[0]].emplace_back(i[1], i[2]);
    a.clear();
    a.shrink_to_fit();
    for(auto& [_, a] : b){
        int n = a.size();
        sort(all(a));
        vector<int> up(n), down;
        rep(n) up[i] = q[a[i].first];
        down = up;
        rep(n){
            down[i] += a[i].second;
            if(i + 1 < n) chmax(down[i + 1], down[i] - (a[i + 1].first - a[i].first) * d);
        }
        rrep(n){
            up[i] += a[i].second;
            if(i) chmax(up[i - 1], up[i] - (a[i].first - a[i - 1].first) * u);
        }
        rep(n) q.insert(a[i].first, max(up[i], down[i]));
    }
    cout << q[s] << endl;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 640 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 26 ms 3328 KB Output is correct
7 Correct 78 ms 7928 KB Output is correct
8 Correct 191 ms 15460 KB Output is correct
9 Correct 311 ms 22648 KB Output is correct
10 Correct 695 ms 45544 KB Output is correct
11 Correct 630 ms 45688 KB Output is correct
12 Correct 1120 ms 59768 KB Output is correct
13 Correct 970 ms 60000 KB Output is correct
14 Runtime error 698 ms 65540 KB Execution killed with signal 9
15 Runtime error 696 ms 65540 KB Execution killed with signal 9
16 Runtime error 675 ms 65540 KB Execution killed with signal 9
17 Correct 0 ms 384 KB Output is correct
18 Incorrect 1 ms 384 KB Output isn't correct
19 Incorrect 1 ms 384 KB Output isn't correct
20 Correct 4 ms 512 KB Output is correct
21 Incorrect 3 ms 512 KB Output isn't correct
22 Incorrect 5 ms 640 KB Output isn't correct
23 Incorrect 5 ms 640 KB Output isn't correct
24 Incorrect 7 ms 768 KB Output isn't correct
25 Incorrect 77 ms 6136 KB Output isn't correct
26 Incorrect 204 ms 12016 KB Output isn't correct
27 Incorrect 314 ms 20832 KB Output isn't correct
28 Correct 528 ms 23020 KB Output is correct
29 Incorrect 476 ms 28152 KB Output isn't correct
30 Incorrect 440 ms 29544 KB Output isn't correct