Submission #254823

#	Time	Username	Problem	Language	Result	Execution time	Memory
254823		karma	Salesman (IOI09_salesman)	C++14	60 / 100	307 ms	26096 KiB

salesman

#include<bits/stdc++.h>
#define pb       emplace_back
#define ll       long long
#define Task     "sales"

using namespace std;

template<typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}

const int N = int(5e5) + 7;
const ll oo = (ll)1e15;

struct TStore {
    int t, l, m;
    bool operator<(const TStore& o)const& {return t < o.t || (t == o.t && l < o.l);}
} sl[N];
struct TBIT {
    vector<ll> t;
    int sz;
    void Init(int n) {sz = n, t.resize(n + 1); fill(t.begin(), t.end(), -oo);}
    void Update(int x, ll val) {for(; x <= sz; x += (x & -x)) t[x] = max(t[x], val);}
    ll Get(int x) {ll res = -oo; for(; x > 0; x -= (x & -x)) res = max(res, t[x]); return res;}
} bit, rev;
int n, s, MaxPos;
ll u, d, ud, f, g, cost[N], sum, costl, costx;
vector<ll> qu;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    Cin(n, u, d, s); MaxPos = s;
    for(int i = 1; i <= n; ++i) {
        Cin(sl[i].t, sl[i].l, sl[i].m);
        MaxPos = max(MaxPos, sl[i].l);
    }
    sort(sl + 1, sl + n + 1); sl[n + 1].t = int(1e6);
    bit.Init(MaxPos), rev.Init(MaxPos);
    bit.Update(s, d * s), rev.Update(MaxPos - s + 1, -u * s);
    int j = 1;
    for(int i = 1; i <= n; ) {
        while(sl[i].t == sl[j].t && j <= n) ++j;
        if(i == j - 1) {
           f = max(bit.Get(sl[i].l) - d * sl[i].l, rev.Get(MaxPos - sl[i].l + 1) + u * sl[i].l) + sl[i].m;
           bit.Update(sl[i].l, f + d * sl[i].l), rev.Update(MaxPos - sl[i].l + 1, f - u * sl[i].l);
        } else {
           costl = costx = -oo; sum = 0;
           /// f(r) = max sum[r] - L[r] * d - sum[l - 1] + L[l] * d + cost[l]
           for(int k = i; k < j; ++k) { // x -> l -> r, l < r -> * d
              cost[k] = max(bit.Get(sl[k].l) - d * sl[k].l, rev.Get(MaxPos - sl[k].l + 1) + u * sl[k].l);
              costl = max(costl, sl[k].l * d - sum);
              sum += sl[k].m;
              costx = max(costx, costl + cost[k]);
              f = costx - sl[k].l * d + sum;
              qu.pb(f);
           }
           costl = costx = -oo; sum = 0;
           for(int k = j - 1; k >= i; --k) { // x -> r -> l, l > r -> * u
              costl = max(costl, -sl[k].l * u - sum);
              sum += sl[k].m;
              costx = max(costx, cost[k] + costl);
              f = costx + sl[k].l * u + sum;
              bit.Update(sl[k].l, f + d * sl[k].l), rev.Update(MaxPos - sl[k].l + 1, f - u * sl[k].l);
              bit.Update(sl[k].l, qu.back() + d * sl[k].l), rev.Update(MaxPos - sl[k].l + 1, qu.back() - u * sl[k].l);
              qu.pop_back();
           }
        }
        i = j;
    }
    cout << max(max(bit.Get(s) - d * s, rev.Get(MaxPos - s + 1) + u * s), 0ll);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100