Submission #790628

#	Time	Username	Problem	Language	Result	Execution time	Memory
790628		Amylopectin	Salesman (IOI09_salesman)	C++14	30 / 100	318 ms	65536 KiB

salesman

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mxn = 2e6 + 10,mni = -1e9 - 10;
// const int mxn = 310,mni = -1e9 - 10;

struct we
{
    int dat,loc,mon;
};
bool cmp(const struct we &l,const struct we &r)
{
    return l.loc < r.loc;
}
struct we sot[mxn] = {};
vector<int> eve[mxn] = {};
int val[mxn] = {},dco,uco,sel[mxn] = {},ser[mxn] = {},ale,ari,cval[mxn] = {}
,cvar[mxn] = {},fvap[mxn] = {},ans;
int fimi(int l,int r)
{
    if(l < r)
    {
        return l;
    }
    return r;
}
int fima(int l,int r)
{
    if(l > r)
    {
        return l;
    }
    return r;
}
int bui(int cl,int cr,int no)
{
    sel[no] = mni;
    ser[no] = mni;
    if(cl == cr)
    {
        return 0;
    }
    int mid = (cl+cr) / 2;
    bui(cl,mid,no*2);
    bui(mid+1,cr,no*2+1);
    return 0;
}
int ad(int cl,int cr,int no,int tar,int ava)
{
    if(cl > tar || cr < tar)
    {
        return 0;
    }
    if(cl == cr)
    {
        sel[no] = ava;
        ser[no] = ava;
        return 0;
    }
    int mid = (cl+cr) / 2;
    ad(cl,mid,no*2,tar,ava);
    ad(mid+1,cr,no*2+1,tar,ava);
    sel[no] = fima(sel[no*2],sel[no*2+1] - (mid+1 - cl) * uco);
    ser[no] = fima(ser[no*2+1],ser[no*2] - (cr - mid) * dco);
    return 0;
}
int fiva(int cl,int cr,int no,int tar)
{
    if(cr < tar)
    {
        ale = fima(ale,ser[no] - (tar-cr) * dco);
        return 0;
    }
    if(cl > tar)
    {
        ari = fima(ari,sel[no] - (cl - tar) * uco);
        return 0;
    }
    if(cl == cr)
    {
        ale = fima(ale,val[cl]);
        ari = fima(ari,val[cl]);
        return 0;
    }
    int mid = (cl+cr) / 2;
    fiva(cl,mid,no*2,tar);
    fiva(mid+1,cr,no*2+1,tar);
    return 0;
}
int main()
{
    int i,j,n,m = 0,spo,dma = 0,cn,cm,fn,fm,cva;
    ans = 0;
    scanf("%d %d %d %d",&n,&uco,&dco,&spo);
    for(i=0; i<n; i++)
    {
        scanf("%d %d %d",&sot[i].dat,&sot[i].loc,&sot[i].mon);
        dma = fima(dma,sot[i].dat);
    }
    sot[n] = {0,spo,0};
    sort(sot,sot + n+1,cmp);
    m = sot[n].loc;
    for(i=0; i<n+1; i++)
    {
        eve[sot[i].dat].push_back(i);
    }
    for(i=0; i<=m; i++)
    {
        val[i] = mni;
    }
    val[spo] = 0;
    bui(0,m,1);
    ad(0,m,1,spo,0);
    for(i=1; i<=dma; i++)
    {
        if(eve[i].size() == 0)
        {
            continue;
        }
        for(j=0; j<eve[i].size(); j++)
        {
            cn = eve[i][j];
            ale = mni;
            ari = mni;
            fiva(0,m,1,sot[cn].loc);
            cval[j] = ale + sot[cn].mon;
            cvar[j] = ari + sot[cn].mon;
            fvap[j] = val[sot[cn].loc];
            if(j != 0)
            {
                cval[j] = fima(cval[j],cval[j-1]
                 - (sot[cn].loc - sot[eve[i][j-1]].loc) * dco + sot[cn].mon);
            }
        }
        for(j=eve[i].size()-2; j>=0; j--)
        {
            cn = eve[i][j];
            {
                cvar[j] = fima(cvar[j],cvar[j+1]
                 - (sot[eve[i][j+1]].loc - sot[cn].loc) * uco + sot[cn].mon);
            }
        }
        for(j=0; j<eve[i].size(); j++)
        {
            cn = eve[i][j];
            fvap[j] = fima(cval[j],fima(fvap[j],cvar[j]));
            ad(0,m,1,sot[cn].loc,fvap[j]);
            if(sot[cn].loc > spo)
            {
                cva = -uco * (sot[cn].loc - spo);
            }
            else 
            {
                cva = -dco * (spo - sot[cn].loc);
            }
            ans = fima(ans,fvap[j] + cva);
            val[sot[cn].loc] = fvap[j];
        }
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for(j=0; j<eve[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
salesman.cpp:145:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for(j=0; j<eve[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
salesman.cpp:94:36: warning: unused variable 'cm' [-Wunused-variable]
   94 |     int i,j,n,m = 0,spo,dma = 0,cn,cm,fn,fm,cva;
      |                                    ^~
salesman.cpp:94:39: warning: unused variable 'fn' [-Wunused-variable]
   94 |     int i,j,n,m = 0,spo,dma = 0,cn,cm,fn,fm,cva;
      |                                       ^~
salesman.cpp:94:42: warning: unused variable 'fm' [-Wunused-variable]
   94 |     int i,j,n,m = 0,spo,dma = 0,cn,cm,fn,fm,cva;
      |                                          ^~
salesman.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d %d %d %d",&n,&uco,&dco,&spo);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d %d %d",&sot[i].dat,&sot[i].loc,&sot[i].mon);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 100