Submission #56099

# Submission time Handle Problem Language Result Execution time Memory
56099 2018-07-10T00:39:38 Z okaybody10 Salesman (IOI09_salesman) C++
100 / 100
983 ms 36068 KB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500009;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vpi;
vpi mark[MAXN];
int n,u,d,s,uptree[2*MAXN],downtree[2*MAXN];
int query(int *arr,int l,int r)
{
    int ans=-INF;
    for(l+=MAXN,r+=MAXN;l<=r;l>>=1,r>>=1)
    {
        if(l&1) ans=max(ans,arr[l++]);
        if(~r&1) ans=max(ans,arr[r--]);
    }
    return ans;
}
void update(int *arr,int x,int v)
{
    x+=MAXN;
    arr[x]=max(arr[x],v);
    for(;x>1;x>>=1) arr[x>>1]=max(arr[x],arr[x^1]);
}
void updatep(int x,int v)
{
    update(uptree,x,v-u*x);
    update(downtree,x,v+d*x);
}
int realquery(int a)
{
    return max(query(downtree,0,a)-d*a,query(uptree,a,MAXN-1)+u*a);
}
void markt(vpi &market)
{
    if(market.size()==0) return;
    sort(market.begin(),market.end());
    vector<int> U,D;
    int sz=market.size();
    for(int i=0;i<sz;i++)
    {
        int temp=realquery(market[i].first);
        U.push_back(temp),D.push_back(temp);
    }
    for(int i=0;i<sz;i++)
    {
        if(i!=0) D[i]=max(D[i],D[i-1]-d*(market[i].first-market[i-1].first));
        D[i]+=market[i].second;
    }
    for(int i=sz-1;i>=0;i--)
    {
        if(i!=sz-1) U[i]=max(U[i],U[i+1]-u*(market[i+1].first-market[i].first));
        U[i]+=market[i].second;
    }
    for(int i=0;i<sz;i++) updatep(market[i].first,max(U[i],D[i]));
}
int main()
{
    scanf("%d %d %d %d",&n,&u,&d,&s);
    for(int i=0,x,y,z;i<n;i++)
    {
        scanf("%d %d %d",&x,&y,&z);
        mark[x].push_back(make_pair(y,z));
    }
    memset(uptree,0xc0,sizeof(uptree));
    memset(downtree,0xc0,sizeof(downtree));
    updatep(s,0);
    for(int i=1;i<=500001;i++) markt(mark[i]);
    return !printf("%d",realquery(s));
}

Compilation message

salesman.cpp: In function 'int main()':
salesman.cpp:59: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:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&x,&y,&z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 20 ms 19832 KB Output is correct
2 Correct 27 ms 20068 KB Output is correct
3 Correct 27 ms 20248 KB Output is correct
4 Correct 23 ms 20248 KB Output is correct
5 Correct 34 ms 20248 KB Output is correct
6 Correct 64 ms 20708 KB Output is correct
7 Correct 114 ms 21612 KB Output is correct
8 Correct 224 ms 23180 KB Output is correct
9 Correct 303 ms 24852 KB Output is correct
10 Correct 591 ms 29648 KB Output is correct
11 Correct 605 ms 29648 KB Output is correct
12 Correct 758 ms 32812 KB Output is correct
13 Correct 760 ms 32812 KB Output is correct
14 Correct 820 ms 36068 KB Output is correct
15 Correct 983 ms 36068 KB Output is correct
16 Correct 889 ms 36068 KB Output is correct
17 Correct 19 ms 36068 KB Output is correct
18 Correct 19 ms 36068 KB Output is correct
19 Correct 20 ms 36068 KB Output is correct
20 Correct 21 ms 36068 KB Output is correct
21 Correct 21 ms 36068 KB Output is correct
22 Correct 22 ms 36068 KB Output is correct
23 Correct 21 ms 36068 KB Output is correct
24 Correct 27 ms 36068 KB Output is correct
25 Correct 97 ms 36068 KB Output is correct
26 Correct 241 ms 36068 KB Output is correct
27 Correct 275 ms 36068 KB Output is correct
28 Correct 451 ms 36068 KB Output is correct
29 Correct 390 ms 36068 KB Output is correct
30 Correct 484 ms 36068 KB Output is correct