oj.uz

Submission #869323

# Submission time Handle Problem Language Result Execution time Memory
869323 2023-11-04T03:24:20 Z abcvuitunggio Salesman (IOI09_salesman) C++17
65 / 100
 455 ms 65368 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;
        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
65.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 31444 KB Output is correct
4 Correct 8 ms 33372 KB Output is correct
5 Correct 8 ms 33660 KB Output is correct
6 Correct 21 ms 34648 KB Output is correct
7 Correct 43 ms 35780 KB Output is correct
8 Correct 71 ms 39808 KB Output is correct
9 Correct 105 ms 43608 KB Output is correct
10 Correct 204 ms 55632 KB Output is correct
11 Correct 243 ms 55924 KB Output is correct
12 Correct 312 ms 59528 KB Output is correct
13 Correct 297 ms 59644 KB Output is correct
14 Correct 385 ms 65368 KB Output is correct
15 Correct 361 ms 65216 KB Output is correct
16 Correct 455 ms 65320 KB Output is correct
17 Correct 7 ms 31324 KB Output is correct
18 Correct 7 ms 31332 KB Output is correct
19 Incorrect 6 ms 31324 KB Output isn't correct
20 Incorrect 7 ms 33372 KB Output isn't correct
21 Incorrect 7 ms 33372 KB Output isn't correct
22 Incorrect 8 ms 33372 KB Output isn't correct
23 Incorrect 9 ms 33696 KB Output isn't correct
24 Incorrect 8 ms 33540 KB Output isn't correct
25 Incorrect 43 ms 37456 KB Output isn't correct
26 Incorrect 80 ms 43224 KB Output isn't correct
27 Incorrect 143 ms 49608 KB Output isn't correct
28 Incorrect 176 ms 50496 KB Output isn't correct
29 Incorrect 204 ms 53748 KB Output isn't correct
30 Incorrect 231 ms 54216 KB Output isn't correct