Submission #830970

#	Time	Username	Problem	Language	Result	Execution time	Memory
830970		lalala56	Salesman (IOI09_salesman)	C++17	13 / 100	402 ms	60152 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,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;
}
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){
        int t,l,m;cin>>t>>l>>m;
        a[t].push_back(i);
        p[i]={l,m};
    }
    
    FOR(i,1,N-1){
        for(int v:a[i]){
            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';
            
        }

        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:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 100