Submission #831040

#	Time	Username	Problem	Language	Result	Execution time	Memory
831040		lalala56	Salesman (IOI09_salesman)	C++17	100 / 100	413 ms	51180 KiB

salesman

#include<bits/stdc++.h>
using namespace std;
#define PROB "Salesman"
#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for(int i=a;i<=b;(i)++)
#define FOD(i,a,b) for(int i=a;i>=b;(i)--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define SZ(x) int(x.size())
#define bit(p,i) ((p>>i)&1)

template <class T>
inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }

template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }
const int N=6e5+9;
const ll inf=1e16;
int n;
ll U,D,S;
vector<int>a[N];
pll p[N];
ll f[2][N],dp[N];
void upd(int id,ll x,int ty){
    for(int i=id;i<N;i+=i&(-i))maximize(f[ty][i],x);
}
ll findd(int id,int ty){
    ll res=-inf;
    for(int i=id;i>0;i-=i&(-i))maximize(res,f[ty][i]);
    return res;
}
bool ss(int a,int b){
    return p[a].fi<p[b].fi;
}
void giai(){
    
    cin>>n>>U>>D>>S;
    FOR(i,1,N-1)f[0][i]=f[1][i]=-inf;
    upd(S,S*D,0);
    upd(N-S,-S*U,1);
    FOR(i,1,n){
        ll t,l,m;cin>>t>>l>>m;
        a[t].push_back(i);
        p[i]={l,m};
    }
    
    FOR(i,1,N-1){
        sort(a[i].begin(),a[i].end(),ss);
        vector<ll>tmp1(SZ(a[i])),tmp2(SZ(a[i]));
        //int cnt=0;
        FOR(j,0,SZ(a[i])-1){
            
            int v=a[i][j];
            //cout<<p[v].fi<<" ";
           //++cnt;
            ll l=findd(p[v].fi-1,0);
            ll r=findd(N-p[v].fi-1,1);
            dp[v]=max(l-p[v].fi*D,r+p[v].fi*U)+p[v].se;
            //cout<<i<<" "<<v<<" "<<l<<" "<<r<<" "<<dp[v]<<" "<<dp[v]+p[v].fi*D<<" "<<dp[v]-p[v].fi*U<<'\n';
            
        }
        //if(!a[i].empty())cout<<'\n';
        FOR(j,0,SZ(a[i])-1){
            int v=a[i][j];
            if(j==0)tmp1[j]=dp[v];
            else tmp1[j]=max(dp[v],tmp1[j-1]+p[v].se-(p[v].fi-p[a[i][j-1]].fi)*D);
            
        }
        FOD(j,SZ(a[i])-1,0){
            int v=a[i][j];
            if(j==SZ(a[i])-1)tmp2[j]=dp[v];
            else tmp2[j]=max(dp[v],tmp2[j+1]+p[v].se-(p[a[i][j+1]].fi-p[v].fi)*U);
            
        }
        FOR(j,0,SZ(a[i])-1){
            //cout<<dp[a[i][j]]<<" "<<tmp1[j]<<" "<<tmp2[j]<<'\n';
            maximize(dp[a[i][j]],max(tmp1[j],tmp2[j]));
        }
        //if(!a[i].empty())cout<<'\n';

        //if(cnt>1)cout<<i<<" "<<cnt<<'\n';

        for(int v:a[i]){
            upd(p[v].fi,dp[v]+p[v].fi*D,0);
            upd(N-p[v].fi,dp[v]-p[v].fi*U,1);
        }
        //cout<<'\n';
    }
    ll res=0;
    FOR(i,1,n){
        //cout<<dp[i]<<'\n';
        if(S>p[i].fi)maximize(res,dp[i]-(S-p[i].fi)*D);
        else maximize(res,dp[i]-(p[i].fi-S)*U);
    }
    cout<<res;

}
int main(){
    if(fopen(PROB".inp","r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    giai();
    


}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100