Submission #675901

#	Time	Username	Problem	Language	Result	Execution time	Memory
675901		Cookie	Salesman (IOI09_salesman)	C++14	100 / 100	709 ms	55296 KiB

salesman

#include<bits/stdc++.h>
 
#include<fstream>
 
using namespace std;
//ifstream fin("INTERNET.INP");
//ofstream fout("INTERNET.OUT");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define int long long
typedef unsigned long long ull;
const int mxn = 5e5 + 3;
struct ST{
    int mx[mxn * 4 + 1];
    void init(){
        for(int i = 1; i <= 4 * mxn; i++)mx[i] = -1e9;
    }
    void upd(int nd, int l, int r, int id, int v){
        if(id < l || id > r)return;
        if(l == r){
            mx[nd] = v; return;
        }
        int mid = (l + r) >> 1;
        upd(nd * 2, l, mid, id, v); upd(nd * 2 + 1, mid + 1, r, id, v);
        mx[nd] = max(mx[nd * 2], mx[nd * 2 + 1]);
    }
    int get(int nd, int l, int r, int ql, int qr){
        if(ql > r || qr < l)return(-1e9);
        if(ql <= l && qr >= r)return(mx[nd]);
        int mid = (l + r) >> 1;
        return(max(get(nd * 2, l, mid, ql, qr), get(nd * 2 + 1, mid + 1, r, ql, qr)));
    }
};
struct th{
    int t, l, m;
    bool operator <(const th &b){
        if(t != b.t)return(t < b.t);
        return(l < b.l);
    }
};
ST down, up;
//down -> go down up -> go up
int n, d, u, s;
int dp[mxn + 1];
ll test[mxn + 1], test2[mxn + 1];
vt<th>v;
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    down.init(); up.init();
    cin >> n >> d >> u >> s; 
    forr(i, 0, n){
        
        int t, l, m; cin >> t >> l >> m;
        v.pb({t, l, m});
    }
    v.pb({mxn + 69, s, 0});
    sort(v.begin(), v.end());
   
    down.upd(1, 1, mxn, s, -d * s);  up.upd(1, 1, mxn, s, u * s);
    int r = 0;
    for(int i = 0; i < v.size();){
        while(r < v.size() && v[r].t == v[i].t)r++;
        int mxup = -1e9;
        for(int j = i; j < r; j++){
            dp[j] = max(down.get(1, 1, mxn,  v[j].l, mxn) + d * v[j].l, up.get(1, 1, mxn, 1, v[j].l) - u * v[j].l) + v[j].m;
            test[j] = mxup - u * v[j].l + v[j].m;
            mxup = max(mxup, max(dp[j], test[j]) + u * v[j].l);
        }
        int mxdown = -1e9;
        for(int j = r - 1; j >= i; j--){
            test2[j] = mxdown + d * v[j].l + v[j].m; 
            mxdown = max(mxdown, max(dp[j], test2[j]) - d * v[j].l);
        }
        for(int j = i; j < r; j++){
            dp[j] = max({dp[j], test[j], test2[j]});
            down.upd(1, 1, mxn, v[j].l, dp[j] - d * v[j].l); up.upd(1, 1, mxn, v[j].l, dp[j] + u * v[j].l);
        }
        i = r;
    }
    cout << dp[v.size() - 1];
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<th>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < v.size();){
      |                    ~~^~~~~~~~~~
salesman.cpp:70:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<th>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         while(r < v.size() && v[r].t == v[i].t)r++;
      |               ~~^~~~~~~~~~

• Subtask 1: 100 / 100