Submission #869326

#	Time	Username	Problem	Language	Result	Execution time	Memory
869326		abcvuitunggio	Salesman (IOI09_salesman)	C++17	100 / 100	416 ms	61152 KiB

salesman

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
int n,u,d,dp[500001][2],t[500001],l[500001],m[500001],mx[2],f[500002][2],sum[500001],a[500001];
vector <int> ve[500001];
void update(int i, int j, int val){
    if (j)
        i=500002-i;
    for (;i<=500001;i+=i&(-i))
        f[i][j]=max(f[i][j],val);
}
int get(int i, int j){
    if (j)
        i=500002-i;
    int res=-INF;
    for (;i;i-=i&(-i))
        res=max(res,f[i][j]);
    return res;
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> u >> d >> l[0];
    for (int i=1;i<=n;i++){
        cin >> t[i] >> l[i] >> m[i];
        ve[t[i]].push_back(i);
    }
    mx[0]=mx[1]=-INF;
    for (int i=1;i<=500001;i++)
        f[i][0]=f[i][1]=-INF;
    ve[0].push_back(0);
    for (int i=500000;i>=0;i--){
        if (ve[i].empty())
            continue;
        sort(ve[i].begin(),ve[i].end(),[](int i, int j){return l[i]<l[j];});
        for (int j:ve[i])
            dp[j][0]=dp[j][1]=max(-abs(l[0]-l[j])*(l[0]>l[j]?d:u),max(get(l[j],0)-l[j]*u,get(l[j],1)+l[j]*d));
        for (int j=0;j<ve[i].size();j++)
            sum[j]=(j?sum[j-1]:0)+m[ve[i][j]];
        int cur=-INF;
        for (int k=ve[i].size()-1;k>=0;k--){
            int j=ve[i][k];
            cur=max(cur,dp[j][1]+sum[k]-l[j]*d);
            a[j]=cur-sum[k]+l[j]*d;
        }
        cur=-INF;
        for (int j:ve[i]){
            cur=max(cur,a[j]+m[j]+l[j]*u);
            dp[j][0]=max(dp[j][0],cur-l[j]*u-m[j]);
        }
        cur=-INF;
        for (int k=0;k<ve[i].size();k++){
            int j=ve[i][k];
            cur=max(cur,dp[j][1]-sum[k]+m[j]+l[j]*u);
            a[j]=cur+sum[k]-l[j]*u;
        }
        cur=-INF;
        reverse(ve[i].begin(),ve[i].end());
        for (int j:ve[i]){
            cur=max(cur,a[j]-l[j]*d);
            dp[j][0]=max(dp[j][0],cur+l[j]*d-m[j]);
        }
        for (int j:ve[i]){
            update(l[j],0,dp[j][0]+m[j]+l[j]*u);
            update(l[j],1,dp[j][0]+m[j]-l[j]*d);
        }
    }
    cout << dp[0][0];
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100