oj.uz

Submission #869326

# Submission time Handle Problem Language Result Execution time Memory
869326 2023-11-04T03:31:14 Z abcvuitunggio Salesman (IOI09_salesman) C++17
100 / 100
 416 ms 61152 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 6 ms 31324 KB Output is correct
4 Correct 7 ms 33380 KB Output is correct
5 Correct 8 ms 33628 KB Output is correct
6 Correct 18 ms 34068 KB Output is correct
7 Correct 37 ms 35016 KB Output is correct
8 Correct 64 ms 38632 KB Output is correct
9 Correct 135 ms 42064 KB Output is correct
10 Correct 229 ms 53104 KB Output is correct
11 Correct 267 ms 53076 KB Output is correct
12 Correct 344 ms 56312 KB Output is correct
13 Correct 343 ms 56312 KB Output is correct
14 Correct 402 ms 60756 KB Output is correct
15 Correct 416 ms 61152 KB Output is correct
16 Correct 395 ms 61000 KB Output is correct
17 Correct 6 ms 31324 KB Output is correct
18 Correct 7 ms 31324 KB Output is correct
19 Correct 6 ms 31428 KB Output is correct
20 Correct 7 ms 33372 KB Output is correct
21 Correct 7 ms 33372 KB Output is correct
22 Correct 8 ms 33372 KB Output is correct
23 Correct 10 ms 33516 KB Output is correct
24 Correct 8 ms 33452 KB Output is correct
25 Correct 50 ms 36436 KB Output is correct
26 Correct 96 ms 41564 KB Output is correct
27 Correct 152 ms 47136 KB Output is correct
28 Correct 153 ms 47652 KB Output is correct
29 Correct 211 ms 50168 KB Output is correct
30 Correct 216 ms 50184 KB Output is correct