Submission #328525

#	Time	Username	Problem	Language	Result	Execution time	Memory
328525		Mackerel_Pike	Salesman (IOI09_salesman)	C++14	100 / 100	376 ms	22028 KiB

salesman

#include<bits/stdc++.h>

using namespace std;

#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double Lf;
typedef pair<int, int> pii;

const int maxn = 5e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, u, d, s;
ll ans = 0;
ll f[maxn], g[maxn];

class Fair{
public:
	int t, l, m;
	Fair(){}
	Fair(int t_, int l_, int m_): t(t_), l(l_), m(m_){}
	inline bool operator < (const Fair &oth)const{ return MP(t, l) < MP(oth.t, oth.l); }
} a[maxn];

class PrefixFenwickTree{
public:
	ll dat[maxn];
	inline PrefixFenwickTree(){ FOR(i, 0, maxn) dat[i] = -INF; return; }
	inline void update(int x, ll k){ for(++x; x < maxn; x += x & (-x)) dat[x] = max(dat[x], k); return; }
	inline ll query(int x){ ll ret = -INF; for(++x; x; x -= x & (-x)) ret = max(ret, dat[x]); return ret; }
}pre;

class SuffixFenwickTree{
public:
	ll dat[maxn];
	inline SuffixFenwickTree(){ FOR(i, 0, maxn) dat[i] = -INF; return; }
	inline void update(int x, ll k){ for(++x; x; x -= x & (-x)) dat[x] = max(dat[x], k); return; }
	inline ll query(int x){ ll ret = -INF; for(++x; x < maxn; x += x & (-x)) ret = max(ret, dat[x]); return ret; }
}suf;

inline void update(int p){
	pre.update(a[p].l, f[p] + a[p].l * d);
	suf.update(a[p].l, f[p] - a[p].l * u);
	return;
}

int main(){
	scanf("%d%d%d%d", &n, &u, &d, &s);
	
	FOR(i, 0, n)
		scanf("%d%d%d", &a[i].t, &a[i].l, &a[i].m);
	a[n++] = Fair(0, s, 0);
	sort(a, a + n);
	
	update(0);
	
	for(int i = 1, j; i < n; i = j){
		for(j = i; j < n && a[j].t == a[i].t; ++j)
			g[j] = max(pre.query(a[j].l) - a[j].l * d, suf.query(a[j].l) + a[j].l * u), f[j] = -INF;
		ll mx = -INF, sum = 0;
		for(j = i; j < n && a[j].t == a[i].t; ++j){
			mx = max(mx, g[j] + a[j].l * d - sum);
			sum += a[j].m;
			f[j] = max(f[j], mx - a[j].l * d + sum);
		}
		mx = -INF, sum = 0;
		for(--j; j >= i; --j){
			mx = max(mx, g[j] - a[j].l * u - sum);
			sum += a[j].m;
			f[j] = max(f[j], mx + a[j].l * u + sum);
		}
		for(j = i; j < n && a[j].t == a[i].t; ++j)
			update(j);
	}
	
	FOR(i, 0, n)
		ans = max(ans, f[i] - (a[i].l < a[0].l ? (a[0].l - a[i].l) * d : (a[i].l - a[0].l) * u));
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d%d%d%d", &n, &u, &d, &s);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d%d%d", &a[i].t, &a[i].l, &a[i].m);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100