Submission #635588

#	Time	Username	Problem	Language	Result	Execution time	Memory
635588		Iwanttobreakfree	Salesman (IOI09_salesman)	C++17	62 / 100	928 ms	52308 KiB

salesman

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
#define pii pair<int,int>
const int max_n=5e5+7;
void pupd(int n,int l,int r,vector<int>& t,int a,int x){
    if(l>a||r<a)return;
    if(l==r)t[n]=x;
    else{
        int mid=(r+l)/2;
        pupd(n<<1,l,mid,t,a,x);
        pupd((n<<1)+1,mid+1,r,t,a,x);
        t[n]=max(t[n<<1],t[(n<<1)+1]);
    }
    //cout<<l<<' '<<r<<' '<<t[n]<<'\n';
}
int val(int n,int l,int r,vector<int>& t,int a,int b){
    if(l>b||r<a)return -1e18;
    if(l>=a&&r<=b)return t[n];
    int mid=(r+l)/2;
    int valls=val(n<<1,l,mid,t,a,b);
    int valrs=val((n<<1)+1,mid+1,r,t,a,b);
    return max(valls,valrs);
}
signed main(){
    int n,u,d,s,time,x,k,ans=0;
    cin>>n>>d>>u>>s;
    s--;
    vector<pair<int,pii>> fair(n);
    vector<int> t(4*max_n,-1e18),t2(4*max_n,-1e18);
    //t->upstream
    //t2->downstream
    for(int i=0;i<n;i++){
        cin>>time>>x>>k;
        x--;
        fair[i]={time,{x,k}};
    }
    pupd(1,0,max_n-1,t,s,0+u*s);
    pupd(1,0,max_n-1,t2,s,0-d*s);
    sort(fair.begin(),fair.end());
    for(int i=0;i<n;i++){
        int best=max(val(1,0,max_n-1,t,0,fair[i].second.first)-u*fair[i].second.first,val(1,0,max_n-1,t2,fair[i].second.first,max_n-1)+d*fair[i].second.first)+fair[i].second.second;
        //cout<<val(1,0,max_n-1,t,0,fair[i].second.first)-u*fair[i].second.first<<'\n';
        //cout<<val(1,0,max_n-1,t2,fair[i].second.first,max_n-1)+d*fair[i].second.first<<'\n';
        pupd(1,0,max_n-1,t,fair[i].second.first,best+u*fair[i].second.first);
        pupd(1,0,max_n-1,t2,fair[i].second.first,best-d*fair[i].second.first);
        //cout<<fair[i].second.second<<' '<<best<<'\n';
        //ans=max(ans,best);
    }
    cout<<max(val(1,0,max_n-1,t,0,s)-u*s,val(1,0,max_n-1,t2,s,max_n-1)+d*s)<<'\n';
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:28:26: warning: unused variable 'ans' [-Wunused-variable]
   28 |     int n,u,d,s,time,x,k,ans=0;
      |                          ^~~

• Subtask 1: 62 / 100