Submission #240692

#	Time	Username	Problem	Language	Result	Execution time	Memory
240692		oscarsierra12	Salesman (IOI09_salesman)	C++14	60 / 100	1491 ms	47868 KiB

salesman

#include <iostream>
#include <stdio.h>
#include <fstream>
#include <string.h>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <set>
#include <deque>
#include <utility>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <algorithm>
#include <limits.h>
using namespace std ;

#define ff    first
#define ss    second
#define pb    push_back

const int N = 5e5+2 ;
const int oo = 2e9+2 ;
struct fair {
    int d, l, m ;
    bool operator < ( const fair &e ) const {
        return ( e.d == d ? e.l < l : d < e.d ) ;
    }
};

fair fairs[N] ;

int mx[20*N][2] ;
int dp[N] ;
vector <int> ofT[N] ;
int best[N][2] ;

void build ( int l, int r, int node ) {
    mx[node][0] = mx[node][1] = -oo ;
    if ( l == r ) {
        return ;
    }
    build ( l, (l+r)/2, node*2 ) ;
    build ((l+r)/2+1, r, (node*2)+1 );
}

void update ( int l, int r, int a, int v, int flag, int node ) {
    if ( l > a || r < a ) return ;
    if ( l == a && r == a ) {
        mx[node][flag] = max ( mx[node][flag], v ) ;
        return;
    }
    update ( l, (l+r)/2, a, v, flag, node*2 ) ;
    update ( (l+r)/2+1, r, a, v, flag, (node*2)+1 ) ;
    mx[node][flag] = max ( mx[node*2][flag], mx[(node*2)+1][flag] ) ;
}

int query ( int l, int r, int a, int b, int flag, int node ) {
    if ( a>r || b<l ) return -oo ;
    if ( a <= l && r <= b ) {
        return mx[node][flag] ;
    }
    int MX = max ( query (l,(l+r)/2, a, b,flag, node*2), query((l+r)/2+1,r,a,b,flag,(node*2)+1) ) ;
    return MX ;
}

int n, u, d, s ;

void fun ( int i, int flag ) {
    vector <pair <int,int> > X ;
    int su = 0, sz = ofT[i].size() ;
    for ( int j = 0 ; j < sz ; ++j ) {
        X.pb ( make_pair(su,j) ) ;
        su += fairs[ofT[i][j]].m - (d+u) * abs(fairs[ofT[i][min(sz-1,j+1)]].l - fairs[ofT[i][j]].l) ;
    }
    sort ( X.rbegin(), X.rend() ) ;
    int l = 0 ;
    su = 0;
    for ( int j = 0 ; j < sz ; ++j ) {
        while ( l <= X[j].ss ) {
            best[ofT[i][l]][flag] = X[j].ff - su ;
            su += (d+u) * abs(fairs[ofT[i][min(sz-1,l+1)]].l - fairs[ofT[i][l]].l) - fairs[ofT[i][l]].m ;
            ++l ;
        }
    }
}

int main() {
    cin >> n >> d >> u >> s ;
    for ( int i = 0 ; i < n ; ++ i ) {
        cin >> fairs[i].d >> fairs[i].l >> fairs[i].m ;
    }
    sort ( fairs, fairs+n ) ;
    for ( int i = 0 ; i < n ; ++i )
        ofT[fairs[i].d].pb ( i ) ;
    for ( int i = 0 ; i < N ; ++i ) {
        fun ( i, 0 ) ;
        reverse ( ofT[i].begin(), ofT[i].end() ) ;
        fun ( i, 1 ) ;
        reverse ( ofT[i].begin(), ofT[i].end() ) ;
    }
    build ( 0,N-1,1 ) ;
    update ( 0, N-1, s, s*u, 0,1 ) ;
    update ( 0, N-1, s, -s*d, 1,1) ;
    for ( int i = N-1 ; i >= 0 ; --i ) {
        vector <int> l1 ;
        for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
            l1.pb ( fairs[ofT[i][j]].m + best[ofT[i][j]][0] - fairs[ofT[i][j]].l * u + query (0,N-1,0,fairs[ofT[i][j]].l,0,1) ) ;
            update (0,N-1,fairs[ofT[i][j]].l,l1.back()+fairs[ofT[i][j]].l*u,0,1) ;
        }
        reverse ( ofT[i].begin(), ofT[i].end() ) ;
        for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
            int l2 = fairs[ofT[i][j]].m + best[ofT[i][j]][1] + fairs[ofT[i][j]].l * d + query (0,N-1,fairs[ofT[i][j]].l,N-1,1,1) ;
            dp[ofT[i][j]] = max ( l1[j], l2 ) ;
           // cout << best[ofT[i][j]][0] << ' ' << best[ofT[i][j]][1] << endl ;
           // cout << ofT[i][j] << ' ' <<l1[j] << ' ' << l2 << endl ;
            update (0,N-1,fairs[ofT[i][j]].l, l2 - fairs[ofT[i][j]].l*d,1,1) ;
        }
        for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
            update(0,N-1,fairs[ofT[i][j]].l, dp[ofT[i][j]]+fairs[ofT[i][j]].l*u,0,1) ;
            update(0,N-1,fairs[ofT[i][j]].l, dp[ofT[i][j]]-fairs[ofT[i][j]].l*d,1,1) ;
        }
    }
    int ans = max (-s * u + query (0,N-1,0,s,0,1), d*s + query(0,N-1,s,N-1,1,1) ) ;
    cout << ans << endl ;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:111:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
                           ~~^~~~~~~~~~~~~~~
salesman.cpp:116:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
                           ~~^~~~~~~~~~~~~~~
salesman.cpp:123:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for ( int j = 0 ; j < ofT[i].size() ; ++j ) {
                           ~~^~~~~~~~~~~~~~~

• Subtask 1: 60 / 100