Submission #366909

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
366909	2021-02-15T17:49:02 Z	kostia244	Mecho (IOI09_mecho)	C++17	0 / 100	67 ms	56192 KB

mecho

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
const int maxn = 5e5 + 5, C = 1;
using ll = long long;
const ll inf = 1ll<<55;
struct segtree {
	vector<ll> t;
	int n;
	segtree(int n) : n(n), t(2*n, -inf) {}
	void update(int pos, ll val) {
		t[pos+n] = max(t[pos+n], val);
		for(pos+=n;pos/=2;) t[pos] = max(t[2*pos], t[2*pos+1]);
	}
	ll query(int l, int r) {
		ll ans = -inf;
		for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
			if(l&1) ans = max(ans, t[l++]);
			if(r&1) ans = max(ans, t[--r]);
		}
		return ans;
	}
};
int n, s;
ll u, d;
segtree down(maxn), up(maxn);
vector<array<int, 2>> cur[maxn];
void upd(int pos, ll val) {
	down.update(pos, val - d*pos);
	up.update(pos, val + u*pos);
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> d >> u >> s;
	upd(s, 0);
	for(int d, l, c, i = 0; i < n; i++) {
		cin >> d >> l >> c;
		cur[d].push_back({l, c});
	}
	for(int day = 0; day < maxn; day++) if(!cur[day].empty()) {
		n = cur[day].size();
		sort(all(cur[day]));
		vector<ll> dp_down(n), dp_up(n);
		for(int i = 0; i < n; i++) {
			dp_down[i] = max(-inf, down.query(cur[day][i][0], maxn) + cur[day][i][0]*d);
		}
		for(int i = 0; i < n; i++) {
			if(i) dp_down[i] = max(dp_down[i], dp_down[i-1] - u*(cur[day][i][0]-cur[day][i-1][0]));
			dp_down[i] += cur[day][i][1];
		}
		for(int i = 0; i < n; i++) {
			dp_up[i] = max(-inf, up.query(0, cur[day][i][0]) - cur[day][i][0]*u);
		}
		for(int i = n; i--;) {
			if(i+1<n) dp_up[i] = max(dp_up[i], dp_up[i+1] - d*(cur[day][i+1][0]-cur[day][i][0]));
			dp_up[i] += cur[day][i][1];
		}
		
		for(int i = 0; i < n; i++) {
			upd(cur[day][i][0], max(dp_down[i], dp_up[i]));
		}
	}
	ll res = max(up.query(0, s) - u*s, down.query(s, maxn) + d*s);
	cout << res << '\n';
}

Compilation message

mecho.cpp: In constructor 'segtree::segtree(int)':
mecho.cpp:9:6: warning: 'segtree::n' will be initialized after [-Wreorder]
    9 |  int n;
      |      ^
mecho.cpp:8:13: warning:   'std::vector<long long int> segtree::t' [-Wreorder]
    8 |  vector<ll> t;
      |             ^
mecho.cpp:10:2: warning:   when initialized here [-Wreorder]
   10 |  segtree(int n) : n(n), t(2*n, -inf) {}
      |  ^~~~~~~

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	54 ms	55916 KB	Execution killed with signal 11
2	Runtime error	54 ms	55916 KB	Execution killed with signal 11
3	Runtime error	53 ms	55916 KB	Execution killed with signal 11
4	Runtime error	54 ms	56044 KB	Execution killed with signal 11
5	Runtime error	54 ms	55916 KB	Execution killed with signal 11
6	Runtime error	53 ms	55916 KB	Execution killed with signal 11
7	Runtime error	53 ms	55984 KB	Execution killed with signal 11
8	Runtime error	53 ms	55916 KB	Execution killed with signal 11
9	Runtime error	53 ms	55936 KB	Execution killed with signal 11
10	Runtime error	53 ms	55916 KB	Execution killed with signal 11
11	Runtime error	62 ms	55916 KB	Execution killed with signal 11
12	Runtime error	55 ms	56044 KB	Execution killed with signal 11
13	Runtime error	55 ms	56044 KB	Execution killed with signal 11
14	Runtime error	54 ms	56044 KB	Execution killed with signal 11
15	Runtime error	54 ms	55916 KB	Execution killed with signal 11
16	Runtime error	59 ms	56172 KB	Execution killed with signal 11
17	Runtime error	54 ms	56172 KB	Execution killed with signal 11
18	Runtime error	54 ms	56140 KB	Execution killed with signal 11
19	Runtime error	55 ms	55916 KB	Execution killed with signal 11
20	Runtime error	54 ms	56044 KB	Execution killed with signal 11
21	Runtime error	59 ms	55916 KB	Execution killed with signal 11
22	Runtime error	53 ms	55916 KB	Execution killed with signal 11
23	Runtime error	55 ms	56172 KB	Execution killed with signal 11
24	Runtime error	54 ms	56044 KB	Execution killed with signal 11
25	Runtime error	62 ms	56044 KB	Execution killed with signal 11
26	Runtime error	53 ms	56044 KB	Execution killed with signal 11
27	Runtime error	53 ms	56044 KB	Execution killed with signal 11
28	Runtime error	54 ms	56032 KB	Execution killed with signal 11
29	Runtime error	54 ms	56044 KB	Execution killed with signal 11
30	Runtime error	53 ms	56044 KB	Execution killed with signal 11
31	Runtime error	53 ms	56044 KB	Execution killed with signal 11
32	Runtime error	54 ms	56044 KB	Execution killed with signal 11
33	Runtime error	67 ms	56044 KB	Execution killed with signal 11
34	Runtime error	60 ms	56044 KB	Execution killed with signal 11
35	Runtime error	55 ms	56044 KB	Execution killed with signal 11
36	Runtime error	56 ms	56044 KB	Execution killed with signal 11
37	Runtime error	54 ms	56044 KB	Execution killed with signal 11
38	Runtime error	54 ms	56044 KB	Execution killed with signal 11
39	Runtime error	56 ms	56044 KB	Execution killed with signal 11
40	Runtime error	53 ms	56044 KB	Execution killed with signal 11
41	Runtime error	54 ms	56044 KB	Execution killed with signal 11
42	Runtime error	59 ms	56068 KB	Execution killed with signal 11
43	Runtime error	54 ms	56044 KB	Execution killed with signal 11
44	Runtime error	61 ms	56044 KB	Execution killed with signal 11
45	Runtime error	54 ms	56044 KB	Execution killed with signal 11
46	Runtime error	54 ms	56044 KB	Execution killed with signal 11
47	Runtime error	55 ms	56044 KB	Execution killed with signal 11
48	Runtime error	54 ms	56044 KB	Execution killed with signal 11
49	Runtime error	53 ms	56044 KB	Execution killed with signal 11
50	Runtime error	54 ms	56044 KB	Execution killed with signal 11
51	Runtime error	54 ms	56044 KB	Execution killed with signal 11
52	Runtime error	66 ms	56044 KB	Execution killed with signal 11
53	Runtime error	54 ms	56044 KB	Execution killed with signal 11
54	Runtime error	54 ms	56044 KB	Execution killed with signal 11
55	Runtime error	55 ms	56044 KB	Execution killed with signal 11
56	Runtime error	55 ms	56048 KB	Execution killed with signal 11
57	Runtime error	54 ms	56044 KB	Execution killed with signal 11
58	Runtime error	55 ms	56044 KB	Execution killed with signal 11
59	Runtime error	54 ms	56044 KB	Execution killed with signal 11
60	Runtime error	53 ms	56044 KB	Execution killed with signal 11
61	Runtime error	55 ms	56044 KB	Execution killed with signal 11
62	Runtime error	59 ms	56044 KB	Execution killed with signal 11
63	Runtime error	55 ms	56044 KB	Execution killed with signal 11
64	Runtime error	54 ms	56044 KB	Execution killed with signal 11
65	Runtime error	54 ms	56044 KB	Execution killed with signal 11
66	Runtime error	54 ms	56044 KB	Execution killed with signal 11
67	Runtime error	64 ms	56044 KB	Execution killed with signal 11
68	Runtime error	54 ms	56044 KB	Execution killed with signal 11
69	Runtime error	54 ms	56044 KB	Execution killed with signal 11
70	Runtime error	53 ms	56044 KB	Execution killed with signal 11
71	Runtime error	56 ms	56044 KB	Execution killed with signal 11
72	Runtime error	55 ms	56044 KB	Execution killed with signal 11
73	Runtime error	54 ms	56044 KB	Execution killed with signal 11
74	Runtime error	57 ms	56044 KB	Execution killed with signal 11
75	Runtime error	56 ms	56044 KB	Execution killed with signal 11
76	Runtime error	63 ms	55988 KB	Execution killed with signal 11
77	Runtime error	54 ms	56044 KB	Execution killed with signal 11
78	Runtime error	53 ms	56044 KB	Execution killed with signal 11
79	Runtime error	54 ms	56044 KB	Execution killed with signal 11
80	Runtime error	54 ms	56044 KB	Execution killed with signal 11
81	Runtime error	55 ms	56044 KB	Execution killed with signal 11
82	Runtime error	55 ms	56044 KB	Execution killed with signal 11
83	Runtime error	57 ms	56044 KB	Execution killed with signal 11
84	Runtime error	54 ms	56044 KB	Execution killed with signal 11
85	Runtime error	53 ms	56192 KB	Execution killed with signal 11
86	Runtime error	53 ms	56044 KB	Execution killed with signal 11
87	Runtime error	53 ms	56044 KB	Execution killed with signal 11
88	Runtime error	54 ms	56044 KB	Execution killed with signal 11
89	Runtime error	54 ms	56044 KB	Execution killed with signal 11
90	Runtime error	56 ms	56044 KB	Execution killed with signal 11
91	Runtime error	54 ms	56044 KB	Execution killed with signal 11
92	Runtime error	59 ms	56064 KB	Execution killed with signal 11