oj.uz

Submission #53528

# Submission time Handle Problem Language Result Execution time Memory
53528 2018-06-30T07:25:12 Z !?!?(#2015) Salesman (IOI09_salesman) C++11
100 / 100
 845 ms 36872 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 524288;
const int INF = 0x3f3f3f3f;
//day, place, price
vector<pair<int, int> > market[MAXN];

struct Tree
{
    int idx[2*MAXN];
    void init()
    {
        memset(idx, 0xc0, sizeof idx);
    }
    void setv(int a, int v)
    {
        a += MAXN;
        idx[a]=max(idx[a], v);
        while((a=a/2))
            idx[a] = max(idx[2*a], idx[2*a+1]);
    }
    int getv(int a, int b)
    {
        a += MAXN; b += MAXN;
        int res = -INF;
        while(a<=b)
        {
            if(a%2==1) res = max(res, idx[a++]);
            if(b%2==0) res = max(res, idx[b--]);
            a /= 2; b /= 2;
        }
        return res;
    }
}UTree, DTree; 
int N, U, D, S;

void setv(int a, int v)
{
    DTree.setv(a, v+D*a);
    UTree.setv(a, v-U*a);
}
int getv(int a)
{
    int ans = max(DTree.getv(0, a) - D*a, UTree.getv(a, MAXN-1) + U*a);
    return ans;
}

void solve(vector<pair<int, int> >& market)
{
    if(market.size() == 0) return;
    sort(market.begin(), market.end());
    vector<int> Uv(market.size());
    vector<int> Dv(market.size());
    for(int i=0; i<market.size(); ++i)
        Uv[i] = Dv[i] = getv(market[i].first);
    for(int i=0; i<market.size(); ++i)
    {
        if(i != 0)
            Dv[i] = max(Dv[i], Dv[i-1] - D*(market[i].first-market[i-1].first));
        Dv[i] += market[i].second;
    }
    for(int i=market.size()-1; i>=0; --i)
    {
        if(i != market.size()-1)
            Uv[i] = max(Uv[i], Uv[i+1] - U*(market[i+1].first-market[i].first));
        Uv[i] += market[i].second;
    }
    for(int i=0; i<market.size(); ++i)
        setv(market[i].first, max(Dv[i], Uv[i]));
}

int main()
{
    int St;
    scanf("%d%d%d%d", &N, &U, &D, &S);
    for(int i=0; i<N; ++i)
    {
        int t, l, m; scanf("%d%d%d", &t, &l, &m);
        market[t].emplace_back(l, m);
    }
    UTree.init(); DTree.init();
    setv(S, 0);
    for(int i=1; i<=500001; ++i)
        solve(market[i]);
    printf("%d\n", getv(S));
    
}

Compilation message

salesman.cpp: In function 'void solve(std::vector<std::pair<int, int> >&)':
salesman.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<market.size(); ++i)
                  ~^~~~~~~~~~~~~~
salesman.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<market.size(); ++i)
                  ~^~~~~~~~~~~~~~
salesman.cpp:64:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i != market.size()-1)
            ~~^~~~~~~~~~~~~~~~~~
salesman.cpp:68:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<market.size(); ++i)
                  ~^~~~~~~~~~~~~~
salesman.cpp: In function 'int main()':
salesman.cpp:74:9: warning: unused variable 'St' [-Wunused-variable]
     int St;
         ^~
salesman.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &N, &U, &D, &S);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:78:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t, l, m; scanf("%d%d%d", &t, &l, &m);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20856 KB Output is correct
2 Correct 20 ms 20856 KB Output is correct
3 Correct 20 ms 21048 KB Output is correct
4 Correct 22 ms 21048 KB Output is correct
5 Correct 24 ms 21120 KB Output is correct
6 Correct 50 ms 21764 KB Output is correct
7 Correct 133 ms 22544 KB Output is correct
8 Correct 205 ms 24340 KB Output is correct
9 Correct 252 ms 25796 KB Output is correct
10 Correct 459 ms 30484 KB Output is correct
11 Correct 537 ms 30540 KB Output is correct
12 Correct 667 ms 33728 KB Output is correct
13 Correct 714 ms 33776 KB Output is correct
14 Correct 780 ms 36752 KB Output is correct
15 Correct 753 ms 36780 KB Output is correct
16 Correct 845 ms 36872 KB Output is correct
17 Correct 20 ms 36872 KB Output is correct
18 Correct 23 ms 36872 KB Output is correct
19 Correct 24 ms 36872 KB Output is correct
20 Correct 22 ms 36872 KB Output is correct
21 Correct 22 ms 36872 KB Output is correct
22 Correct 24 ms 36872 KB Output is correct
23 Correct 23 ms 36872 KB Output is correct
24 Correct 24 ms 36872 KB Output is correct
25 Correct 142 ms 36872 KB Output is correct
26 Correct 193 ms 36872 KB Output is correct
27 Correct 307 ms 36872 KB Output is correct
28 Correct 408 ms 36872 KB Output is correct
29 Correct 454 ms 36872 KB Output is correct
30 Correct 491 ms 36872 KB Output is correct