Submission #155449

#	Time	Username	Problem	Language	Result	Execution time	Memory
155449		Mercenary	Salesman (IOI09_salesman)	C++14	100 / 100	739 ms	51724 KiB

salesman

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "SALES"
#define int ll
using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
//typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const ll inf = -1e18;

const int maxn = 5e5 + 5;
vector<ii> a[maxn];

int n,u,d,s;
int dp[maxn];
int dp1[maxn];

int read(){
    int x = 0;
    char ch;
    for(ch = getchar() ; ch > '9' || ch < '0' ; ch = getchar());
    for( ; ch >= '0' && ch <= '9' ; ch = getchar())x = x * 10 + ch - '0';
    return x;
}

struct BIT{
    int bit[maxn];
    BIT(){fill_n(bit,maxn,inf);};
    void update(int x , bool type , int val){
        if(type == 1){
            for( ; x > 0 ; x &= x - 1){
                if(val != inf)bit[x] = max(bit[x] , val);
                else bit[x] = inf;
            }
        }else{
            for( ; x < maxn ; x += x & -x){
                if(val != inf)bit[x] = max(bit[x] , val);
                else bit[x] = inf;
            }
        }
    }
    int query(int x , bool type){
        int res = inf;
        if(type == 0){
            for( ; x > 0 ; x &= x - 1){
                res = max(res , bit[x]);
            }
        }else{
            for( ; x < maxn ; x += x & -x){
                res = max(res , bit[x]);
            }
        }
        return res;
    }
}data[4];

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    n = read();u = read();d = read();s = read();
    for(int i = 1 ; i <= n ; ++i){
        int time = read(), pos = read(), profit = read();
        a[time].pb(mp(pos , profit));
    }
    fill_n(dp,maxn,inf);
    fill_n(dp1,maxn,inf);
    dp[s] = 0;dp1[s] = 0;
    a[0].pb(mp(s , 0));
    a[maxn - 1].pb(mp(s , 0));
    data[0].update(s , 0 , s * d);
    data[1].update(s , 1 , - s * u);
    for(int i = 0 ; i < maxn ; ++i){
        sort(a[i].begin(),a[i].end());
        for(int j = 1 ; j < (int)a[i].size() ; ++j){
            a[i][j].second += a[i][j - 1].second;
        }
        for(int j = 0 ; j < (int)a[i].size() ; ++j){
            ii c = a[i][j];
            int sum = (j == 0 ? 0 : a[i][j - 1].second);
            dp1[c.first] = max(data[0].query(c.first , 0) - d * c.first , data[1].query(c.first , 1) + u * c.first);
            data[2].update(c.first , 0 , dp1[c.first] + d * c.first - sum);
            data[3].update(c.first , 1 , dp1[c.first] - u * c.first + c.second);
        }
        for(int j = 0 ; j < (int)a[i].size() ; ++j){
            ii c = a[i][j];
            int sum = (j == 0 ? 0 : a[i][j - 1].second);
            dp[c.first] = max(data[2].query(c.first , 0) - d * c.first + c.second , data[3].query(c.first , 1) + u * c.first - sum);
            dp[c.first] = max({dp[c.first] , data[0].query(c.first , 0) + c.second - sum - d * c.first ,
                               data[1].query(c.first , 1) + c.second - sum + u * c.first});;
        }
        for(int j = 0 ; j < (int)a[i].size() ; ++j){
            ii c = a[i][j];
            data[0].update(c.first , 0 , dp[c.first] + d * c.first);
            data[1].update(c.first , 1 , dp[c.first] - u * c.first);
            data[2].update(c.first , 0 , inf);
            data[3].update(c.first , 1 , inf);
        }
    }
    cout << max(dp[s],0ll);
    return 0;
//
}

Compilation message (stderr)

salesman.cpp: In function 'int32_t main()':
salesman.cpp:70:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:71:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100