Submission #298656

#	Time	Username	Problem	Language	Result	Execution time	Memory
298656		Hemimor	Salesman (IOI09_salesman)	C++14	95 / 100	801 ms	44408 KiB

salesman

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=2000000001;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Segment_Tree{
	private:
	int n;
	vl date;
	public:
	Segment_Tree(int n_){
		n=1;
		while(n<n_) n*=2;
		date=vl(2*n-1,-INF);
	}
	void Update(int k,ll x){
		k+=n-1;
		date[k]=max(date[k],x);
		while(k>0){
			k=(k-1)/2;
			date[k]=max(date[k*2+1],date[k*2+2]);
		}
	}
	ll Query(int a,int b){
		a+=n-1;b+=n-1;
		ll m=-INF;
		while(a<b){
			if(a%2==0) m=max(m,date[a++]);
			if(b%2==0) m=max(m,date[--b]);
			a/=2;b/=2;
		}
		return m;
	}
	ll Open(int k){return date[k+n-1];}
};

const int M=500000;
int n,L,R,s;
vp a[M];

int main(){
	scanf("%d%d%d%d",&n,&L,&R,&s);
	s--;
	for(int i=0;i<n;i++){
		int t,x,v;
		scanf("%d%d%d",&t,&x,&v);
		t--,x--;
		a[t].push_back({x,v});
	}
	Segment_Tree st1(M),st2(M);
	st1.Update(s,-R*(M-s-1));
	st2.Update(s,-L*s);
	ll res=0;
	for(int i=0;i<M;i++) if(!a[i].empty()){
		sort(a[i].begin(),a[i].end());
		int m=a[i].size();
		vl b(m),c(m),d(m);
		for(int j=0;j<m;j++){
			int x=a[i][j].first;
			b[j]=max(st1.Query(0,x)+R*(M-x-1),st2.Query(x,M)+L*x)+a[i][j].second;
		}
		ll t=b[0];
		for(int j=0;j<m;j++){
			if(j) t=max(t-(a[i][j].first-a[i][j-1].first)*R+a[i][j].second,b[j]);
			c[j]=t;
		}
		t=b[m-1];
		for(int j=m-1;j>=0;j--){
			if(j<m-1) t=max(t-(a[i][j+1].first-a[i][j].first)*L+a[i][j].second,b[j]);
			d[j]=t;
		}
		for(int j=0;j<m;j++){
			b[j]=max(c[j],d[j]);
			int x=a[i][j].first;
			res=max(res,b[j]-(x<s?R*(s-x):L*(x-s)));
			st1.Update(x,b[j]-R*(M-x-1));
			st2.Update(x,b[j]-L*x);
		}
	}
	printf("%lld\n",res);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  scanf("%d%d%d%d",&n,&L,&R,&s);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |   scanf("%d%d%d",&t,&x,&v);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 95 / 100