oj.uz

Submission #635588

# Submission time Handle Problem Language Result Execution time Memory
635588 2022-08-26T13:26:20 Z Iwanttobreakfree Salesman (IOI09_salesman) C++17
62 / 100
 928 ms 52308 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 13 ms 31532 KB Output is correct
3 Correct 14 ms 31572 KB Output is correct
4 Correct 18 ms 31672 KB Output is correct
5 Correct 23 ms 31668 KB Output is correct
6 Correct 59 ms 32340 KB Output is correct
7 Correct 111 ms 33676 KB Output is correct
8 Correct 195 ms 35744 KB Output is correct
9 Correct 284 ms 37560 KB Output is correct
10 Correct 504 ms 43372 KB Output is correct
11 Correct 563 ms 44108 KB Output is correct
12 Correct 716 ms 47116 KB Output is correct
13 Correct 697 ms 47308 KB Output is correct
14 Correct 902 ms 52308 KB Output is correct
15 Correct 817 ms 51280 KB Output is correct
16 Correct 928 ms 51416 KB Output is correct
17 Correct 13 ms 31572 KB Output is correct
18 Incorrect 13 ms 31572 KB Output isn't correct
19 Incorrect 14 ms 31572 KB Output isn't correct
20 Incorrect 16 ms 31640 KB Output isn't correct
21 Incorrect 16 ms 31700 KB Output isn't correct
22 Incorrect 20 ms 31800 KB Output isn't correct
23 Incorrect 19 ms 31804 KB Output isn't correct
24 Incorrect 19 ms 31796 KB Output isn't correct
25 Incorrect 175 ms 35340 KB Output isn't correct
26 Incorrect 332 ms 39112 KB Output isn't correct
27 Incorrect 540 ms 44320 KB Output isn't correct
28 Incorrect 586 ms 45060 KB Output isn't correct
29 Incorrect 794 ms 49996 KB Output isn't correct
30 Incorrect 798 ms 50752 KB Output isn't correct