답안 #862079

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862079 2023-10-17T13:46:02 Z deepaung Salesman (IOI09_salesman) C++14
0 / 100
28 ms 65536 KB
#include <bits/stdc++.h>

#define int long long
#define ll long long

#define f first
#define s second
#define pii pair<int, int>

using namespace std;

const int MAXN = 500005;

int N, U, D, S;
int days[MAXN+1], dollars[MAXN+1];
ll tmp[MAXN+1];
vector<pii> vec[MAXN+1];

struct SegmentTree {
    ll seg[(MAXN+2)*4];
    ll lazy[(MAXN+2)*4];

    SegmentTree() {
        memset(seg, 0, sizeof(seg));
        memset(lazy, 0, sizeof(lazy));
    }

    //|  1  |  2  |  3  | ==> location (index)
    //| -2D | -1D | -0D | ==> segl
    //| -0U | -1U | -2U | ==> segr

    void prop(int val, int idx, int l, int r) {
        seg[idx] += val;
        if (l != r) {
            lazy[idx*2] += val;
            lazy[idx*2+1] += val;
        }
    }

    void update(int ui, ll val, int idx, int l, int r) {
        if (lazy[idx] != 0) {
            prop(lazy[idx], idx, l, r);
            lazy[idx] = 0;
        }

        if (ui < l || r < ui) return;
        if (l == r) {
            seg[idx] = max(seg[idx], val);
            return;
        }

        int mid = (l + r) >> 1;

        update(ui, val, idx*2, l, mid);
        update(ui, val, idx*2+1, mid+1, r);

        seg[idx] = max(seg[idx*2], seg[idx*2+1]);
    }

    ll gett(int gl, int gr, int idx, int l, int r) {
        if (lazy[idx] != 0) {
            prop(lazy[idx], idx, l, r);
            lazy[idx] = 0;
        }

        if (gr < l || r < gl) return LLONG_MIN;
        if (gl <= l && r <= gr) {
            return seg[idx];
        }

        int mid = (l + r) >> 1;

        ll resl = gett(gl, gr, idx*2, l, mid);
        ll resr = gett(gl, gr, idx*2+1, mid+1, r);

        return max(resl, resr);
    }

    void update(int ui, ll val) { update(ui, val, 1, 1, MAXN); }
    ll gett(int gl, int gr) { return gett(gl, gr, 1, 1, MAXN); }

} segl, segr;

void buildAll(int idx, int l, int r) {
    if (l == r) {
        segl.seg[idx] = segr.seg[idx] = LLONG_MIN;
        return;
    }

    int mid = (l + r) >> 1;

    buildAll(idx*2, l, mid);
    buildAll(idx*2+1, mid+1, r);

    segl.seg[idx] = segr.seg[idx] = LLONG_MIN;
}

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

    cin >> N >> U >> D >> S;

    int t, l, m; // days, location, dollars
    for (int i = 1; i <= N; i++) {
        cin >> t >> l >> m;
        days[l] = t;
        dollars[l] = m;
    }

    for (int l = 1; l <= MAXN; l++) {
        if (days[l] != 0) vec[days[l]].push_back({ l, dollars[l] });
    }

    buildAll(1, 1, MAXN);

    for (int t = 1; t <= MAXN; t++) {
        if (vec[t].empty()) continue;

        // cerr << "t: " << t << "\n";

        // from day t-1 to day t
        for (int i = 0; i < vec[t].size(); i++) {
            auto [l, m] = vec[t][i];

            // set default value
            if (l < S) tmp[i] = m - (S - l) * U;
            else tmp[i] = m - (l - S) * D;

            ll resl = LLONG_MIN, resr = LLONG_MIN;
            if (1 <= l-1) resl = segl.gett(1, l-1) + (MAXN-l) * D + m;
            if (l+1 <= MAXN) resr = segr.gett(l+1, MAXN) + (l-1) * U + m;

            tmp[i] = max(tmp[i], max(resl, resr));
        }

        // assign new value
        for (int i = 0; i < vec[t].size(); i++) {
            if (tmp[i] == LLONG_MIN) continue;

            auto [l, m] = vec[t][i];
            // cerr << "tmp: " << l << " = " << tmp[i] << "\n";
            segl.update(l, tmp[i] - (MAXN-l) * D);
            segr.update(l, tmp[i] - (l-1) * U);
        }

        // from day t to day t (l to r)
        for (int i = 0; i < vec[t].size(); i++) {
            auto [l, m] = vec[t][i];

            ll resl = LLONG_MIN;
            if (1 <= l-1) resl = segl.gett(1, l-1) + (MAXN-l) * D + m;
            if (resl == LLONG_MIN || segl.gett(1, l-1) == LLONG_MIN) continue;

            tmp[i] = max(tmp[i], resl);
            segl.update(l, resl - (MAXN-l) * D);
        }

        // from day t to day t (r to l)
        for (int i = (int)vec[t].size()-1; i >= 0; i--) {
            auto [l, m] = vec[t][i];

            ll resr = LLONG_MIN;
            if (l+1 <= MAXN) resr = segr.gett(l+1, MAXN) + (l-1) * U + m;
            if (resr == LLONG_MIN || segr.gett(l+1, MAXN) == LLONG_MIN) continue;

            tmp[i] = max(tmp[i], resr);
            segr.update(l, resr - (l-1) * U);
        }

        // assign new value
        for (int i = 0; i < vec[t].size(); i++) {
            if (tmp[i] == LLONG_MIN) continue;

            auto [l, m] = vec[t][i];
            segl.update(l, tmp[i] - (MAXN-l) * D);
            segr.update(l, tmp[i] - (l-1) * U);

            // cerr << l << " is " << segl.gett(l, l) + (MAXN-l) * D << "\n";
        }

        continue;
        continue;
        continue;
        continue;

        // (again) from day t to day t (l to r)
        for (int i = 0; i < vec[t].size(); i++) {
            auto [l, m] = vec[t][i];

            ll resr = LLONG_MIN;
            if (l+1 <= MAXN) resr = segr.gett(l+1, MAXN) + (l-1) * U + m;
            if (resr == LLONG_MIN || segr.gett(l+1, MAXN) == LLONG_MIN) continue;

            tmp[i] = max(tmp[i], resr);
            segr.update(l, resr - (l-1) * U);
        }

        // (again) from day t to day t (r to l)
        for (int i = vec[t].size()-1; i >= 0; i--) {
            auto [l, m] = vec[t][i];

            ll resl = LLONG_MIN;
            if (1 <= l-1) resl = segl.gett(1, l-1) + (MAXN-l) * D + m;
            if (resl == LLONG_MIN || segl.gett(1, l-1) == LLONG_MIN) continue;

            tmp[i] = max(tmp[i], resl);
            segl.update(l, resl - (MAXN-l) * D);
        }

        // (again) assign new value
        for (int i = 0; i < vec[t].size(); i++) {
            if (tmp[i] == LLONG_MIN) continue;

            auto [l, m] = vec[t][i];
            segl.update(l, tmp[i] - (MAXN-l) * D);
            segr.update(l, tmp[i] - (l-1) * U);

            // cerr << "(again) " << l << " is " << segl.gett(l, l) + (MAXN-l) * D << "\n";
        }

    }


    ll resl = LLONG_MIN, resr = LLONG_MIN;
    if (1 <= S-1) resl = segl.gett(1, S-1) + (MAXN-S) * D;
    if (S+1 <= MAXN) resr = segr.gett(S+1, MAXN) + (S-1) * U;

    cout << max({ 0LL, resl, resr }) << "\n";

    return 0;
}

Compilation message

salesman.cpp: In function 'int32_t main()':
salesman.cpp:122:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:123:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:137:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:140:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:147:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:148:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:160:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  160 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:171:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:174:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  174 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:187:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:188:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  188 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:200:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  200 |             auto [l, m] = vec[t][i];
      |                  ^
salesman.cpp:211:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  211 |         for (int i = 0; i < vec[t].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
salesman.cpp:214:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  214 |             auto [l, m] = vec[t][i];
      |                  ^
# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 65536 KB Execution killed with signal 9
2 Runtime error 11 ms 65536 KB Execution killed with signal 9
3 Runtime error 12 ms 65536 KB Execution killed with signal 9
4 Runtime error 12 ms 65536 KB Execution killed with signal 9
5 Runtime error 12 ms 65536 KB Execution killed with signal 9
6 Runtime error 12 ms 65536 KB Execution killed with signal 9
7 Runtime error 28 ms 65536 KB Execution killed with signal 9
8 Runtime error 11 ms 65536 KB Execution killed with signal 9
9 Runtime error 11 ms 65536 KB Execution killed with signal 9
10 Runtime error 13 ms 65536 KB Execution killed with signal 9
11 Runtime error 13 ms 65536 KB Execution killed with signal 9
12 Runtime error 15 ms 65536 KB Execution killed with signal 9
13 Runtime error 27 ms 65536 KB Execution killed with signal 9
14 Runtime error 13 ms 65536 KB Execution killed with signal 9
15 Runtime error 10 ms 65536 KB Execution killed with signal 9
16 Runtime error 24 ms 65536 KB Execution killed with signal 9
17 Runtime error 13 ms 65536 KB Execution killed with signal 9
18 Runtime error 10 ms 65536 KB Execution killed with signal 9
19 Runtime error 14 ms 65536 KB Execution killed with signal 9
20 Runtime error 10 ms 65536 KB Execution killed with signal 9
21 Runtime error 12 ms 65536 KB Execution killed with signal 9
22 Runtime error 12 ms 65536 KB Execution killed with signal 9
23 Runtime error 12 ms 65536 KB Execution killed with signal 9
24 Runtime error 10 ms 65536 KB Execution killed with signal 9
25 Runtime error 12 ms 65536 KB Execution killed with signal 9
26 Runtime error 12 ms 65536 KB Execution killed with signal 9
27 Runtime error 28 ms 65536 KB Execution killed with signal 9
28 Runtime error 12 ms 65536 KB Execution killed with signal 9
29 Runtime error 13 ms 65536 KB Execution killed with signal 9
30 Runtime error 27 ms 65536 KB Execution killed with signal 9