제출 #861921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861921		Warinchai	Salesman (IOI09_salesman)	C++14	0 / 100	830 ms	56068 KiB

salesman

#include<bits/stdc++.h>
using namespace std;
long long n,u,d,s;
long long e=5e5+1;
struct segtree{
    long long info[2000010];
    void upd(int st,int en,int i,int pos,long long val){
        if(st>pos||en<pos)return;
        if(st==en){
            info[i]=max(info[i],val);
            return;
        }
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=max(info[i*2],info[i*2+1]);
    }
    long long fmax(int st,int en,int i,int l,int r){
        if(st>r||en<l){
            return LLONG_MIN;
        }
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return max(fmax(st,m,i*2,l,r),fmax(m+1,en,i*2+1,l,r));
    }
    void build(int st,int en,int i){
        if(st==en){
            info[i]=LLONG_MIN;
            return;
        }
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=max(info[i*2],info[i*2+1]);
    }
}up,down;
vector<pair<long long,long long> >v[500005];
int main(){
    cin>>n>>u>>d>>s;
    for(int i=1;i<=n;i++){
        long long t,l,m;
        cin>>t>>l>>m;
        v[t].push_back({l,m});
    }
    up.build(1,e,1);
    down.build(1,e,1);
    //cerr<<down.fmax(1,e,1,1,80)<<endl;
    up.upd(1,e,1,s,(s-1)*-u);
    down.upd(1,e,1,s,(e-s)*-d);
    //cerr<<down.fmax(1,e,1,1,80)<<endl;
    //cout<<s<<" update up:"<<(s-1)*-u<<endl;
    //cout<<s<<" update down:"<<(e-s)*-d<<endl;
    for(int i=1;i<=500000;i++){
        if(v[i].size()>0){
            sort(v[i].begin(),v[i].end());
            for(int j=v[i].size()-1;j>=0;j--){
                int nn=v[i][j].first;
                long long best=up.fmax(1,e,1,nn,e);
                if(best==LLONG_MIN)continue;
                up.upd(1,e,1,nn,best+v[i][j].second);
                //cout<<nn<<" update up:"<<best+(nn-1)*u+v[i][j].second<<endl;
                down.upd(1,e,1,nn,best+(nn-1)*u+(e-nn)*-d);
                //cout<<nn<<" update down:"<<best+(nn-1)*u+(e-nn)*-d<<endl;
            }
            for(int j=0;j<v[i].size();j++){
                int nn=v[i][j].first;
                long long best=down.fmax(1,e,1,1,nn);
                if(best==LLONG_MIN)continue;
                down.upd(1,e,1,nn,best+v[i][j].second);
                //cout<<nn<<" update down:"<<best+(e-nn)*d<<endl;
                up.upd(1,e,1,nn,best+(e-nn)*d+(nn-1)*-u);
            }
        }
    }
    long long best=max(down.fmax(1,e,1,1,s)+(e-s)*d,up.fmax(1,e,1,s,e)+(s-1)*u);
    cout<<best;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

salesman.cpp: In function 'int main()':
salesman.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int j=0;j<v[i].size();j++){
      |                         ~^~~~~~~~~~~~

• Subtask 1: 0 / 100