Submission #218154

#	Time	Username	Problem	Language	Result	Execution time	Memory
218154		arnold518	Salesman (IOI09_salesman)	C++14	100 / 100	834 ms	54392 KiB

salesman

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5e5;
const int MAXVAL = 5e5+10;
const ll NEGINF= -1e17;

struct SEG
{
    ll tree[4*MAXVAL+10];

    SEG() { for(int i=1; i<=4*MAXVAL; i++) tree[i]=NEGINF; }

    void update(int node, int tl, int tr, int pos, ll val)
    {
        if(tr<pos || pos<tl) return;
        if(tl==tr) { tree[node]=max(tree[node], val); return; }
        int mid=tl+tr>>1;
        update(node*2, tl, mid, pos, val);
        update(node*2+1, mid+1, tr, pos, val);
        tree[node]=max(tree[node*2], tree[node*2+1]);
    }

    ll query(int node, int tl, int tr, int l, int r)
    {
        if(r<tl || tr<l) return NEGINF;
        if(l<=tl && tr<=r) return tree[node];
        int mid=tl+tr>>1;
        return max(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
    }

    void update(int pos, ll val) { update(1, 1, MAXVAL, pos, val); }
    ll query(int l, int r) { return query(1, 1, MAXVAL, l, r); }
};
SEG sega, segb;

struct Data
{
    int T, L, M;
    bool operator < (const Data &p)
    {
        if(T!=p.T) return T<p.T;
        return L<p.L;
    }
};

int N, U, D, S;
Data A[MAXN+10];
ll dpl[MAXN+10], dpr[MAXN+10];

int main()
{
    int i, j;

    scanf("%d%d%d%d", &N, &U, &D, &S);
    for(i=1; i<=N; i++) scanf("%d%d%d", &A[i].T, &A[i].L, &A[i].M);
    sort(A+1, A+N+1);

    sega.update(S, -U*S);
    segb.update(S, D*S);
    for(i=1; i<=N; )
    {
        int now=A[i].T;
        vector<int> V;
        for(; i<=N && now==A[i].T; i++) V.push_back(i);

        for(int it : V) dpl[it]=dpr[it]=max(sega.query(A[it].L, MAXVAL)+U*A[it].L, segb.query(1, A[it].L)-D*A[it].L)+A[it].M;

        for(j=V.size()-2; j>=0; j--) dpl[V[j]]=max(dpl[V[j]], dpl[V[j+1]]-U*(A[V[j+1]].L-A[V[j]].L)+A[V[j]].M);
        for(j=1; j<V.size(); j++) dpr[V[j]]=max(dpr[V[j]], dpr[V[j-1]]-D*(A[V[j]].L-A[V[j-1]].L)+A[V[j]].M);

        for(int it : V) sega.update(A[it].L, max(dpl[it], dpr[it])-A[it].L*U), segb.update(A[it].L, max(dpl[it], dpr[it])+A[it].L*D);
    }
    printf("%lld", max(sega.query(S, MAXVAL)+U*S, segb.query(1, S)-D*S));

}

Compilation message (stderr)

salesman.cpp: In member function 'void SEG::update(int, int, int, int, ll)':
salesman.cpp:22:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
salesman.cpp: In member function 'll SEG::query(int, int, int, int, int)':
salesman.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
salesman.cpp: In function 'int main()':
salesman.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=1; j<V.size(); j++) dpr[V[j]]=max(dpr[V[j]], dpr[V[j-1]]-D*(A[V[j]].L-A[V[j-1]].L)+A[V[j]].M);
                  ~^~~~~~~~~
salesman.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &N, &U, &D, &S);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:60:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d%d%d", &A[i].T, &A[i].L, &A[i].M);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100