oj.uz

Submission #861950

# Submission time Handle Problem Language Result Execution time Memory
861950 2023-10-17T08:59:42 Z 12345678 Salesman (IOI09_salesman) C++17
40 / 100
 651 ms 48468 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;
int n, u, d, s, x, y, z;
vector<pair<int, int>> t[nx];

struct segtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=-2e9);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=max(d[i], vl));
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (r<ql||qr<l) return INT_MIN;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} up, dn;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>u>>d>>s;
    for (int i=0; i<n; i++) cin>>x>>y>>z, t[x].push_back({y, z});
    up.build(1, nx-1, 1); dn.build(1, nx-1, 1);
    up.update(1, nx-1, 1, s, -s*u); dn.update(1, nx-1, 1, s, s*d);
    for (int i=1; i<nx; i++)
    {
        sort(t[i].begin(), t[i].end());
        vector<int> tmp(t[i].size()), rtmp(t[i].size());
        for (int j=0; j<t[i].size(); j++)
        {
            int y=t[i][j].first, z=t[i][j].second;
            int qup=up.query(1, nx-1, 1, y, nx-1);
            int qdn=dn.query(1, nx-1, 1, 1, y);
            int mx=max(qup+y*u, qdn-y*d)+z;
            if (j>=1) mx=max(mx, tmp[j-1]+(y-t[i][j-1].first)*d+z);
            tmp[j]=mx;
        }
        for (int j=t[i].size()-1; j>=0; j--)
        {
            int y=t[i][j].first, z=t[i][j].second;
            int qup=up.query(1, nx-1, 1, y, nx-1);
            int qdn=dn.query(1, nx-1, 1, 1, y);
            int mx=max(qup+y*u, qdn-y*d)+z;
            if (j<=t[i].size()-2) mx=max(mx, rtmp[j+1]+(t[i][j+1].first-y)*u+z);
            //cout<<"here "<<y<<' '<<z<<' '<<mx<<'\n';
            rtmp[j]=mx;
        }
        for (int j=0; j<t[i].size(); j++) 
        {
            int y=t[i][j].first;
            //cout<<i<<' '<<j<<' '<<tmp[j]<<' '<<rtmp[j]<<'\n';
            up.update(1, nx-1, 1, y, max(tmp[j], rtmp[j])-y*u);
            dn.update(1, nx-1, 1, y, max(tmp[j], rtmp[j])+y*d);
        }
    }
    cout<<max(up.query(1, nx-1, 1, s, nx-1)+s*u, dn.query(1, nx-1, 1, 1, s)-s*d);
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:49: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]
   49 |         for (int j=0; j<t[i].size(); j++)
      |                       ~^~~~~~~~~~~~
salesman.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             if (j<=t[i].size()-2) mx=max(mx, rtmp[j+1]+(t[i][j+1].first-y)*u+z);
      |                 ~^~~~~~~~~~~~~~~
salesman.cpp:68: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]
   68 |         for (int j=0; j<t[i].size(); j++)
      |                       ~^~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 23644 KB Output isn't correct
2 Correct 8 ms 23576 KB Output is correct
3 Incorrect 7 ms 23644 KB Output isn't correct
4 Correct 9 ms 23752 KB Output is correct
5 Correct 11 ms 23896 KB Output is correct
6 Correct 30 ms 24708 KB Output is correct
7 Incorrect 64 ms 26204 KB Output isn't correct
8 Correct 125 ms 28492 KB Output is correct
9 Correct 177 ms 30544 KB Output is correct
10 Correct 316 ms 37716 KB Output is correct
11 Incorrect 375 ms 38484 KB Output isn't correct
12 Correct 479 ms 42348 KB Output is correct
13 Correct 490 ms 42836 KB Output is correct
14 Correct 622 ms 48468 KB Output is correct
15 Correct 527 ms 47416 KB Output is correct
16 Correct 651 ms 47392 KB Output is correct
17 Incorrect 7 ms 23644 KB Output isn't correct
18 Incorrect 10 ms 23564 KB Output isn't correct
19 Incorrect 8 ms 23644 KB Output isn't correct
20 Incorrect 11 ms 23816 KB Output isn't correct
21 Incorrect 9 ms 23896 KB Output isn't correct
22 Incorrect 11 ms 23832 KB Output isn't correct
23 Incorrect 11 ms 23900 KB Output isn't correct
24 Incorrect 11 ms 23900 KB Output isn't correct
25 Incorrect 99 ms 26204 KB Output isn't correct
26 Incorrect 200 ms 28948 KB Output isn't correct
27 Incorrect 317 ms 32064 KB Output isn't correct
28 Incorrect 373 ms 33244 KB Output isn't correct
29 Incorrect 464 ms 34896 KB Output isn't correct
30 Incorrect 479 ms 36808 KB Output isn't correct