Submission #55069

#	Time	Username	Problem	Language	Result	Execution time	Memory
55069		okaybody10	Salesman (IOI09_salesman)	C++98	50 / 100	937 ms	66560 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 543210;
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]);
}
int 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) U[i]=max(U[i],U[i-1]-u*(market[i].first-market[i-1].first));
        U[i]+=market[i].second;
    }
    for(int i=sz-1;i>=0;i--)
    {
        if(i!=sz-1) D[i]=max(D[i],D[i-1]-d*(market[i].first-market[i-1].second));
        D[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<=500000;i++) markt(mark[i]);
    return !printf("%d",realquery(s));
}

Compilation message (stderr)

salesman.cpp: In function 'int updatep(int, int)':
salesman.cpp:29:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 100