제출 #754308

#제출 시각아이디문제언어결과실행 시간메모리
754308TimDeeSalesman (IOI09_salesman)C++17
100 / 100
656 ms42372 KiB
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i];

const int inf=1.5e9;

struct q {
	int t,p,x;
};

struct sgt {
	vector<int> t; int sz=1;
	sgt(int n) {
		while (sz<n) sz<<=1;
		t.assign(2*sz-1,-inf);
	}
	void upd(int v, int l, int r, int i) {
		if (r-l==1) return;
		int m=(l+r)>>1;
		if (i<m) upd(2*v+1,l,m,i);
		else upd(2*v+2,m,r,i);
		t[v]=max(t[2*v+1],t[2*v+2]);
	}
	void set(int i, int x) {
		t[sz-1+i]=x;
		upd(0,0,sz,i);
	}
	int query(int v, int l, int r, int lx, int rx) {
		if (rx<=l || r<=lx) return -inf;
		if (lx<=l && r<=rx) return t[v];
		int m=(l+r)>>1;
		int lq=query(2*v+1,l,m,lx,rx);
		int rq=query(2*v+2,m,r,lx,rx);
		return max(lq,rq);
	}
	int query(int l, int r) {
		return query(0,0,sz,l,r);
	}
};

bool foo(q a, q b) {
	return a.t < b.t;
}

void old(int n, int u, int d, int s, vector<q>&a) {
	sgt st1(5e5+5), st2(5e5+5);
	st1.set(s,s*d);
	st2.set(s,-s*u);

	sort(all(a),foo);
	for(auto&x:a) {
		int pos=x.p, val=x.x;
		int left = st1.query(0,pos);
		int right = st2.query(pos,5e5+5);
		left -= pos*d;
		right += pos*u;
		int z=max(left,right)+val;
		st1.set(pos,z+pos*d);
		st2.set(pos,z-pos*u);
	}
	int left = st1.query(0,s);
	left -= s*d;
	int right = st2.query(s,5e5+5);
	right += s*u;
	int ans = max(left,right);
	cout<<ans<<'\n';
	exit(0);
}

void solve() {

	int n,u,d,s; cin>>n>>u>>d>>s;
	vector<q> a(n);
	vector<vector<pi>> z(5e5+5);
	int jopa=1;
	forn(i,n) {
		cin>>a[i].t>>a[i].p>>a[i].x;
		z[a[i].t].pb({a[i].p,a[i].x});
		jopa&=z[a[i].t].size()==1;
	}
	if (jopa) old(n,u,d,s,a);

	forn(i,5e5+5) sort(all(z[i]));

	sgt st1(5e5+5), st2(5e5+5);
	st1.set(s,s*d);
	st2.set(s,-s*u);

	forn(i,5e5+5){
		if (!z[i].size()) continue;
		sort(all(z[i]));
		vector<int> q(z[i].size(),-inf);
		vector<int> p(z[i].size(),-inf);

		forn(j,z[i].size()) {
			int pos=z[i][j].f, val=z[i][j].s;
			int left = st1.query(0,pos);
			int right = st2.query(pos,5e5+5);
			left -= pos*d;
			right += pos*u;
			int zzz=max(left,right);
			p[j]=zzz;
		}

		int m=z[i].size();
		vector<int> pr(m+1,0);
		vector<int> dist(m,0);

		forn(j,m) pr[j+1]=pr[j]+z[i][j].s;
		forn(j,m) dist[j]=(z[i][j].f-z[i][0].f)*u;
		vector<int> dp(m+1,0);
		dp[m]=pr[m]+p[m-1]-dist[m-1];
		for (int j=m-1; j; --j) dp[j]=max(dp[j+1],pr[j]+p[j-1]-dist[j-1]);
		forn(j,m) q[j]=max(q[j],dp[j+1]-pr[j]+dist[j]);

		reverse(all(z[i]));
		reverse(all(p));
		reverse(all(q));
		forn(j,m) pr[j+1]=pr[j]+z[i][j].s;
		forn(j,m) dist[j]=(z[i][0].f-z[i][j].f)*d;
		dp[m]=pr[m]+p[m-1]-dist[m-1];
		for (int j=m-1; j; --j) dp[j]=max(dp[j+1],pr[j]+p[j-1]-dist[j-1]);
		forn(j,m) q[j]=max(q[j],dp[j+1]-pr[j]+dist[j]);
		reverse(all(q));
		reverse(all(z[i]));

		forn(j,z[i].size()) {
			int pos=z[i][j].f;
			int zzz=q[j];
			st1.set(pos,zzz+pos*d);
			st2.set(pos,zzz-pos*u);
		}
	}
	int left = st1.query(0,s);
	left -= s*d;
	int right = st2.query(s,5e5+5);
	right += s*u;
	int ans = max(left,right);
	cout<<ans<<'\n';

}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	solve();
}

컴파일 시 표준 에러 (stderr) 메시지

salesman.cpp: In function 'void solve()':
salesman.cpp:5:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define forn(i,n) for(int i=0;i<n;++i)
......
  103 |   forn(j,z[i].size()) {
      |        ~~~~~~~~~~~~~            
salesman.cpp:103:3: note: in expansion of macro 'forn'
  103 |   forn(j,z[i].size()) {
      |   ^~~~
salesman.cpp:104:23: warning: unused variable 'val' [-Wunused-variable]
  104 |    int pos=z[i][j].f, val=z[i][j].s;
      |                       ^~~
salesman.cpp:5:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define forn(i,n) for(int i=0;i<n;++i)
......
  135 |   forn(j,z[i].size()) {
      |        ~~~~~~~~~~~~~            
salesman.cpp:135:3: note: in expansion of macro 'forn'
  135 |   forn(j,z[i].size()) {
      |   ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...