Submission #799626

#	Time	Username	Problem	Language	Result	Execution time	Memory
799626		I_Love_EliskaM_	Salesman (IOI09_salesman)	C++14	100 / 100	645 ms	64828 KiB

salesman

#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=1e18;

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);
	}
};

void solve() {

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

	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();
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100