Submission #838716

#TimeUsernameProblemLanguageResultExecution timeMemory
838716vjudge1Salesman (IOI09_salesman)C++17
49 / 100
867 ms65536 KiB
#include<bits/stdc++.h>
using namespace std;

#define            task       "a"
#define             ll        long long
#define          FORE(i, v)   for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define             ed        << "\n";
#define             el        cout<<'\n';
#define            ALL(s)     s.begin(),s.end()
#define             fi        first
#define             se        second
#define            SQ(a)      (a)*(a)
#define            A(a)        abs(a)
#define            SZ(a)      ((int)(a.size()))
#define          REP(i,a,b)    for (int i = (a), _b = (b); i < _b; i++)
#define          FOR(i,a,b)    for (int i = (a), _b = (b); i <= _b; i++)
#define          FOD(i,r,l)    for(int i=r; i>=l; i--)
#define           MASK(x)      (1LL << (x))
#define           BIT(x, i)          ((x) >> (i) & 1)
#define           pii          pair<int,int>
#define           db           double
#define           II(a, b)     make_pair((a),(b))
#define           pb(x)        push_back(x)
#define int ll
const int mod = 1e9 + 7;
const ll MOD = 1e12 + 7;
const ll INF = 1e18;
/// 998244353;
/// 1e9 + 7;
/// 1e9 + 25;
/// 999999939;
/// 1e12 + 7;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int random(int l, int r) {
    return l + rd() % (r - l + 1);
}

int mul(ll a, ll b) {
    if(a >= mod) a %= mod;
    if(b >= mod) b %= mod;
    return 1LL * a * b % mod;
}

int add(int a, int b) {
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;

    return a;
}

int pw(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1)
            res = mul(res, a);
        b = b >> 1;
        a = mul(a, a);
    }
    return res;
}

template <class T> inline bool minimize(T &a, const T &b) {
    return (a > b ? (a = b),1 : 0);
}

template <class T> inline bool maximize(T &a, const T &b) {
    return (a < b ? (a = b),1 : 0);
}

void ReadInp() {
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

#define task "a"
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }

#define task "LONG"
    if(fopen(task".in","r")) {
        freopen(task".in","r",stdin);
        freopen(task".out","w",stdout);
    }
}

const int maxn = 5e5 + 5;
int n, U, D, S;

int T[maxn];
int L[maxn];
int K[maxn];
int p[maxn];
int f[maxn];
int s[maxn];

vector <pii> event[maxn];

struct BIT{
    vector <int> st; int n;

    void init(const int sz = 0){
        n = sz; st = vector <int> (4 * n + 2, - INF);
    }

    void upd(int i, int val){
        int l = 1, r = n, id = 1;
        while(l <= r){
            maximize(st[id], val);
            int m = (l + r) / 2;
            if(l == r) return;

            if(i > m){
                l = m + 1;
                id = id * 2 + 1;
            }else{
                r = m;
                id = id * 2;
            }
        }
    }


    int get(int u, int v, int l, int r, int id) const{
        if(u <= l && r <= v) return st[id];
        if(u > r || v < l) return - INF;
        int m = (l + r) / 2;
        return max(get(u, v, l, m, id * 2), get(u, v, m + 1, r, id * 2 + 1));
    }

    int get(int u, int v) const{
        return get(u, v, 1, n, 1);
    }
}it_D, it_U;

void sol() {
    cin >> n >> U >> D >> S;

    it_D.init(500000); it_U.init(500000);
    memset(f, -0x3f, sizeof f);
    memset(p, -0x3f, sizeof p);
    memset(s, -0x3f, sizeof s);

    swap(U, D);


    f[S] = 0; it_D.upd(S, U * S); it_U.upd(S, - D * S);

    FOR(i, 1, n){
        int t; cin >> t;
        int l, m; cin >> l >> m;
        event[t].push_back(II(l, m));
    }

    FOR(i, 1, 500000){
        sort(ALL(event[i]));
        vector <int> st;

        for(auto [Loc, earn] : event[i]){
            maximize(p[Loc], it_D.get(1, Loc) - U * Loc + earn);
            maximize(p[Loc], it_U.get(Loc, 500000) + D * Loc + earn);

            s[Loc] = p[Loc];
        }

        for(auto [Loc, earn] : event[i]){
            maximize(p[Loc], it_D.get(1, Loc) - U * Loc + earn);
            it_D.upd(Loc, p[Loc] + U * Loc);
        }

        reverse(ALL(event[i]));

        for(auto [Loc, earn] : event[i]){
            maximize(s[Loc], it_U.get(Loc, 500000) + D * Loc + earn);
            it_U.upd(Loc, s[Loc] - D * Loc);
        }

        for(auto [Loc, earn] : event[i]){
            maximize(f[Loc], max(p[Loc], s[Loc]));
            it_U.upd(Loc, f[Loc] - D * Loc);
            it_D.upd(Loc, f[Loc] + U * Loc);
        }
    }

    int ans = 0;
    FOR(i, 1, 50000) ans = max(ans, f[i] - (S <= i ? (i - S) * D : (S - i) * U));

    cout << ans;
}



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    ReadInp();

    int t = 1;  /// cin >> t;
    while(t --) sol();
    return 0;
}

Compilation message (stderr)

salesman.cpp:85: warning: "task" redefined
   85 | #define task "LONG"
      | 
salesman.cpp:79: note: this is the location of the previous definition
   79 | #define task "a"
      | 
salesman.cpp: In function 'void ReadInp()':
salesman.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(task".in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
salesman.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...