Submission #771325

#	Time	Username	Problem	Language	Result	Execution time	Memory
771325		Ahmed57	Salesman (IOI09_salesman)	C++17	50 / 100	3080 ms	44420 KiB

salesman

#include <bits/stdc++.h>

using namespace std;
//BIT Fenwick tree
struct fenwick{
long long bit[500001]={0} , n  = 500000;
void build(){
    for(int i = 0;i<=500000;i++)bit[i] = -1e18;
}
void add(int e,long long v){
    while(e<=n){
        bit[e]=max(bit[e],v);
        e+=e&-e;
    }
}
long long sum(int e){
    long long res = -1e18;
    while(e>=1){
        res=max(res,bit[e]);
        e -= e&-e;
    }
    return res;
}
};
fenwick s1,s2;
long long n,u,d,s;
void update(int i,int val){
    s1.add(i,val+d*i);
    s2.add(500001-i,val-u*i);
}long long get(int i){
    return max(s2.sum(500001-i)+u*i,s1.sum(i)-d*i);
}
//end BIT
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    s1.build();s2.build();
    cin>>n>>u>>d>>s;
    vector<pair<int,int>> v[500001];
    for(int i = 0;i<n;i++){
        long long a,b,c;
        cin>>a>>b>>c;
        v[a].push_back({b,c});
    }
    update(s,0);
    long long ma = 0;
    for(int i = 0;i<=500000;i++){
        if(v[i].empty())continue;
        sort(v[i].begin(),v[i].end());
        long long cur[v[i].size()] ;
        long long maxD[v[i].size()] ;
        long long maxU[v[i].size()];
        for(int j = 0;j<v[i].size();j++){
            cur[j] = -1e18 , maxD[j] =-1e18 , maxU[j] = -1e18;
            cur[j] = get(v[i][j].first)+v[i][j].second;
        }
        long long tempD = -1e18,tempU = -1e18;
        for(int j = 0;j<v[i].size();j++){
            maxD[j] = max(maxD[j],tempD-d*v[i][j].first+v[i][j].second);
            tempD = max(tempD,maxD[j]+d*v[i][j].first);
        }
        for(int j = v[i].size()-1;j>=0;j--){
            maxU[j] = max(maxU[j],tempU+u*v[i][j].first+v[i][j].second);
            tempU = max(tempU,maxU[j]-u*v[i][j].first);
        }
        for(int j = 0;j<v[i].size();j++){
            cur[j] = max({cur[j],maxD[j],maxU[j]});
            update(v[i][j].first,cur[j]);
        }
    }
    cout<<max(get(s),0ll)<<endl;
}

Compilation message (stderr)

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

• Subtask 1: 50 / 100