Submission #1069209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069209		modwwe	Salesman (IOI09_salesman)	C++17	100 / 100	274 ms	44544 KiB

salesman

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
void phongbeo();
const int inf=1e14;
const int mod2=1e9+7;
const int  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,l,r,mid;
int  i,s10,s12;
int kk;
int el=29;

main()
{
#ifndef ONLINE_JUDGE
//fin(task),fou(task);
#endif
    NHP
    /// cin>>s1;
    //  modwwe
    phongbeo();
}
struct fenwick
{
    int bit[500007];

    void upd(int x,int y)
    {
        for(x; x<=m; x+=x&-x)
            bit[x]=max(bit[x],y);
    }
    int get(int x)
    {
        int s=-inf;
        for(x; x; x-=x&-x)
            s=max(s,bit[x]);
        return s;
    }
} fen1;
struct fenwick2
{
    int bit[500007];
    void upd(int x,int y)
    {
        for(x; x; x-=x&-x)
            bit[x]=max(bit[x],y);
    }
    int get(int x)
    {
        int s=-inf;
        for(x; x<=m; x+=x&-x)
            s=max(s,bit[x]);
        return s;
    }
} fen2;
bool cmp(ib a,ib b)
{
    return a.a<b.a;
}
vector<ib> v[500007];
        vector<ib> v2;
void phongbeo()
{
    cin>>n>>l>>r>>k;
    for(int i=1; i<=n; i++)
        cin>>s3>>s4>>s5,s2=max(s2,s4),v[s3].pb({s4,s5});
    s2=max(s2,k);
    m=s2;
    for(int i=1; i<=m; i++)fen1.bit[i]=fen2.bit[i]=-inf;
    fen1.upd(k,r*k);
    fen2.upd(k,-l*k);
    for(int f=1; f<=500000; f++)
    {
        sort(v[f].begin(),v[f].end(),cmp);
        s4=-inf;
        v2.clear();
        for(auto x:v[f])
        {
            s2=fen1.get(x.a)-x.a*r;
            s2=max(s2,fen2.get(x.a)+x.a*l);
            if(s2>s4-x.a*r)
            {
                s4=s2+x.a*r;
            }
            s2=max(s2,s4-x.a*r);
                        s4+=x.b;
            v2.pb({x.a,s2+x.b});

        }
        reverse(v[f].begin(),v[f].end());
        s4=-inf;
        for(auto x:v[f])
        {
            s2=fen1.get(x.a)-x.a*r;
            s2=max(s2,fen2.get(x.a)+x.a*l);
            if(s2>s4+x.a*l)
            {
                s4=s2-x.a*l;
            }
            s2=max(s2,s4+x.a*l);
            s4+=x.b;
                            v2.pb({x.a,s2+x.b});
        }
        for(auto x:v2)
        {
           fen1.upd(x.a,x.b+x.a*r);
              fen2.upd(x.a,x.b-x.a*l);

        }
    }
     s2=max(fen2.get(k)+k*l,fen1.get(k)-k*r);
     cout<<s2;

}

Compilation message (stderr)

salesman.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main()
      | ^~~~
salesman.cpp: In member function 'void fenwick::upd(long long int, long long int)':
salesman.cpp:66:13: warning: statement has no effect [-Wunused-value]
   66 |         for(x; x<=m; x+=x&-x)
      |             ^
salesman.cpp: In member function 'long long int fenwick::get(long long int)':
salesman.cpp:72:13: warning: statement has no effect [-Wunused-value]
   72 |         for(x; x; x-=x&-x)
      |             ^
salesman.cpp: In member function 'void fenwick2::upd(long long int, long long int)':
salesman.cpp:82:13: warning: statement has no effect [-Wunused-value]
   82 |         for(x; x; x-=x&-x)
      |             ^
salesman.cpp: In member function 'long long int fenwick2::get(long long int)':
salesman.cpp:88:13: warning: statement has no effect [-Wunused-value]
   88 |         for(x; x<=m; x+=x&-x)
      |             ^

• Subtask 1: 100 / 100