Submission #69510

#	Time	Username	Problem	Language	Result	Execution time	Memory
69510		top34051	Salesman (IOI09_salesman)	C++17	50 / 100	493 ms	66560 KiB

salesman

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 5e5 + 5;
const int maxv = 5e5 + 5;
const ll inf = 1e15;

struct node {
	int t,x,val;
};

int n,st;
ll U,D;
node a[maxn];
ll fenL[maxv+5], fenR[maxv+5], res[maxv+5];

void update(int x) {
	for(int i=x;i<=maxv;i+=(i&-i)) fenL[i] = max(fenL[i], res[x] + U*x);
	for(int i=x;i>=1;i-=(i&-i)) fenR[i] = max(fenR[i], res[x] - D*x);
}

ll query(int x) {
	ll ret = -inf;
	for(int i=x;i>=1;i-=(i&-i)) ret = max(ret, fenL[i] - U*x);
	for(int i=x;i<=maxv;i+=(i&-i)) ret = max(ret, fenR[i] + D*x);
	return ret;
}

int main() {
	scanf("%d%lld%lld%d",&n,&D,&U,&st);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].val);
	sort(&a[1],&a[n+1],[&](node x, node y) {return x.t < y.t;});

	for(int i=1;i<=maxv;i++) {
		fenL[i] = fenR[i] = res[i] = -inf;
	}

	res[st] = 0;
	update(st);

	for(int i=1;i<=n;i++) {
		int x = a[i].x, val = a[i].val;
		res[x] = max(res[x], val + query(x));
		update(x);
//		printf("\tdp %d %d = %lld\n",a[i].t,a[i].x,res[x]);
	}

	printf("%lld",query(st));
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld%lld%d",&n,&D,&U,&st);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:32:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].val);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 100