oj.uz

답안 #254824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254824 2020-07-30T16:48:00 Z karma Salesman (IOI09_salesman) C++14
100 / 100
 278 ms 18672 KB 
#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 + u) - sum);
              sum += sl[k].m;
              costx = max(costx, costl + cost[k] - sl[k].l * u);
              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 + d) - sum);
              sum += sl[k].m;
              costx = max(costx, cost[k] + costl + sl[k].l * d);
              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

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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 16 ms 8448 KB Output is correct
7 Correct 30 ms 8704 KB Output is correct
8 Correct 57 ms 9336 KB Output is correct
9 Correct 79 ms 9984 KB Output is correct
10 Correct 139 ms 11640 KB Output is correct
11 Correct 177 ms 11768 KB Output is correct
12 Correct 209 ms 12920 KB Output is correct
13 Correct 210 ms 12920 KB Output is correct
14 Correct 269 ms 14200 KB Output is correct
15 Correct 228 ms 14076 KB Output is correct
16 Correct 257 ms 14072 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 512 KB Output is correct
25 Correct 59 ms 10232 KB Output is correct
26 Correct 112 ms 12488 KB Output is correct
27 Correct 184 ms 15728 KB Output is correct
28 Correct 200 ms 15348 KB Output is correct
29 Correct 271 ms 18040 KB Output is correct
30 Correct 278 ms 18672 KB Output is correct