제출 #464969

#제출 시각아이디문제언어결과실행 시간메모리
464969kaxzertSalesman (IOI09_salesman)C++17
62 / 100
1347 ms44888 KiB
/**
      00  00      11      00  00  111111  00000  111111  000000
      00 00      1111      0000      11   00     11  11  000000
      0000      11  11      00      11    00000  111111    00
      00 00    11111111    0000    11     00     11 11     00
      00  00  11      11  00  00  111111  00000  11  11    00
**/

#include<bits/stdc++.h>

using namespace std;

void setIO(string s) {
    freopen((s+".inp").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

void setIOusaco(string s) {
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define fast ios::sync_with_stdio(false); cin.tie(0)

void print(int x) {cout << x;}
void print(long long x) {cout << x;}
void print(unsigned x) {cout << x;}
void print(unsigned long long x) {cout << x;}
void print(double x) {cout << fixed << x;}
void print(long double x) {cout << fixed << x;}
void print(char x) {cout << "'" << x << "'";}
void print(string x) {cout << '"' << x << '"';}
void print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void print(const pair<T, V> &x) {cout << '{'; print(x.ff); cout << ", "; print(x.ss); cout << '}';}
template<typename T>
void print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), print(i); cout << "}";}
void _print() {cout << "]" << endl;}
template <typename T, typename... V>
void _print(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; _print(v...);}

#ifdef TAP
#define bug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define bug(x...) 
#endif

template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}

#define maxN 500008
const ll oo = (ll)1e16;
ll f[maxN];
int n, u, d, s;

struct segment_tree {
    vt<ll> nodes;

    segment_tree() {
        nodes.assign(n*4, -oo);
    }

    void update(int i, ll val, int root = 1, int left = 1, int right = n) {
        if (left == right && left == i) {
            nodes[root] = max(nodes[root], val);
            return;
        }

        if (left > i || right < i) return;

        int mid = (left+right)/2;

        update(i, val, root*2, left, mid);
        update(i, val, root*2+1, mid+1, right);
        nodes[root] = max(nodes[root*2], nodes[root*2+1]);
    }

    ll getquery(int i, int j, int root = 1, int left = 1, int right = n) {
        if (left >= i && right <= j) return nodes[root];

        if (left > j || right < i) return -oo;

        int mid = (left+right)/2;

        return max(getquery(i, j, root*2, left, mid), getquery(i, j, root*2+1, mid+1, right));
    }
};

int main() {

    fast;
    cin >> n >> u >> d >> s;
    vt<array<int, 3> > a;
    vt<int> b;
    b.pb(s);
    fto(i, 1, n) {
    	int day, loc, cost;
    	cin >> day >> loc >> cost;
    	a.pb({day, loc, cost});
    	b.pb(loc);
    }
    a.pb({600000, s, 0});
    sort(all(a), [](array<int, 3> a, array<int, 3> b) -> bool {
    	if (a[0] < b[0]) return 1;
        if (a[0] > b[0]) return 0;
        return a[1] < b[1];
    });

    sort(all(b));
    b.erase(unique(all(b)), b.end());

    n = sz(b);
    segment_tree up, down;

    auto tk = [=](int loc) -> int{ 
        return ((lower_bound(all(b), loc))-b.begin()) + 1;
    };

    int sth = tk(s);
    up.update(sth, -u*s);
    down.update(sth, d*s);

    // trav(c, a) {
    //     bug(c);
    // }

    int left = 0, right = 0;
    ll ans;
    fto(i, 0, sz(a)-1) {
        if (i < sz(a)-1 && a[i] == a[i+1]) {
            ++right;
            continue;
        }
        else {
            vt<ll> temp(right-left+1);
            fto(j, left, right) {
                int loc = tk(a[j][1]);
                temp[j-left] = down.getquery(1, loc) -a[j][1]*d + a[j][2];
            }
            fdto(j, right, left) {
                int loc = tk(a[j][1]);
                temp[j-left] = max(temp[j-left], up.getquery(loc, n) + a[j][1]*u + a[j][2]);
            }
            fto(j, left, right) {
                if (j == sz(a)-1) ans = temp[j-left];
                int loc = tk(a[j][1]);
                up.update(loc, temp[j-left] - u*a[j][1]);
                down.update(loc, temp[j-left] + d*a[j][1]);
            }
            left = i+1;
            right = i+1;
        }
    }

    cout << ans << '\n';

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

salesman.cpp: In function 'void setIO(std::string)':
salesman.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen((s+".inp").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp: In function 'void setIOusaco(std::string)':
salesman.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...