oj.uz

Submission #593448

# Submission time Handle Problem Language Result Execution time Memory
593448 2022-07-11T07:57:33 Z cheissmart Bodyguard (JOI21_bodyguard) C++14
42 / 100
 25000 ms 951972 KB 
#include <bits/stdc++.h>
#define int ll
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7;

struct DS {
	V<pair<ll, ll>> tt;
	void insert(ll m, ll b) {
		tt.EB(m, b);
	}
	ll qry(ll x) {
		ll mx = 0;
		for(auto[m, b]:tt) {
			mx = max(mx, m * x + b);
		}
		return mx;
	}
};

void claim(bool b) {
	if(!b) while(1);
}

signed main()
{
	IO_OP;

	int n, q;
	cin >> n >> q;
	V<pair<pair<pi, pi>, int>> ev;
	vi xs, ys;
	for(int i = 0; i < n; i++) {
		int t, x, y, c, d;
		cin >> t >> x >> y >> c, d = abs(x - y);
		claim(c % 2 == 0);
		c /= 2;
		pi a = {t + x, t - x};
		pi b = {t + d + y, t + d - y};
		ev.EB(MP(a, b), c);
		xs.PB(a.F), ys.PB(a.S);
		xs.PB(b.F), ys.PB(b.S);

		assert((a.F == b.F || a.S == b.S) && a != b);
		if(a.F == b.F) {
			assert(a.S < b.S);
		} else {
			assert(a.F < b.F);
		}
	}
	sort(ALL(xs)), xs.resize(unique(ALL(xs)) - xs.begin());
	sort(ALL(ys)), ys.resize(unique(ALL(ys)) - ys.begin());

	V<vi> dx, dy;
	dx = dy = V<vi>(SZ(xs), vi(SZ(ys)));
	V<V<ll>> dp = V<V<ll>>(SZ(xs), V<ll>(SZ(ys)));

	for(auto[pab, c]:ev) {
		auto[a, b] = pab;
		a.F = lower_bound(ALL(xs), a.F) - xs.begin();
		a.S = lower_bound(ALL(ys), a.S) - ys.begin();
		b.F = lower_bound(ALL(xs), b.F) - xs.begin();
		b.S = lower_bound(ALL(ys), b.S) - ys.begin();
		claim((a.F == b.F || a.S == b.S) && a != b);
		if(a.F == b.F) {
			claim(a.S < b.S);
			for(int i = a.S; i < b.S; i++)
				dy[a.F][i] = max(dy[a.F][i], c);
		} else {
			claim(a.F < b.F);
			for(int i = a.F; i < b.F; i++)
				dx[i][a.S] = max(dx[i][a.S], c);
		}
	}

	for(int i = SZ(xs) - 1; i >= 0; i--) {
		for(int j = SZ(ys) - 1; j >= 0; j--) {
			if(i + 1 < SZ(xs)) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1LL * dx[i][j] * (xs[i + 1] - xs[i]));
			if(j + 1 < SZ(ys)) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1LL * dy[i][j] * (ys[j + 1] - ys[j]));
		}
	}

	V<V<V<pair<pi, int>>>> qq(SZ(xs), V<V<pair<pi, int>>>(SZ(ys)));
	V<ll> ans(q);
	for(int i = 0; i < q; i++) {
		int t, x;
		cin >> t >> x;
		pi a = {t + x, t - x};
		int he = lower_bound(ALL(xs), a.F) - xs.begin();
		int be = lower_bound(ALL(ys), a.S) - ys.begin();
		if(he < SZ(xs) && be < SZ(ys)) {
			qq[he][be].EB(a, i);
		}
	}
	for(int j = 0; j < SZ(ys); j++) {
		DS ds;
		for(int i = SZ(xs) - 1; i >= 0; i--) {
			int c = j ? dy[i][j - 1] : 0;
			ds.insert(c, dp[i][j]);
			for(auto[a, qi]:qq[i][j])
				ans[qi] = max(ans[qi], ds.qry(ys[j] - a.S));
		}
	}
	for(int i = 0; i < SZ(xs); i++) {
		DS ds;
		for(int j = SZ(ys) - 1; j >= 0; j--) {
			int c = i ? dx[i - 1][j] : 0;
			ds.insert(c, dp[i][j]);
			for(auto[a, qi]:qq[i][j])
				ans[qi] = max(ans[qi], ds.qry(xs[i] - a.F));
		}
	}

	for(int i = 0; i < q; i++)
		cout << ans[i] << '\n';
}

Compilation message

bodyguard.cpp: In member function 'll DS::qry(ll)':
bodyguard.cpp:41:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   for(auto[m, b]:tt) {
      |           ^
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:85:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |  for(auto[pab, c]:ev) {
      |          ^
bodyguard.cpp:86:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |   auto[a, b] = pab;
      |       ^
bodyguard.cpp:127:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |    for(auto[a, qi]:qq[i][j])
      |            ^
bodyguard.cpp:136:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  136 |    for(auto[a, qi]:qq[i][j])
      |            ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15061 ms 569284 KB Output is correct
2 Correct 15145 ms 572984 KB Output is correct
3 Correct 4767 ms 236644 KB Output is correct
4 Correct 3398 ms 98968 KB Output is correct
5 Execution timed out 25106 ms 951972 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1389 ms 830052 KB Output is correct
2 Correct 1456 ms 829992 KB Output is correct
3 Correct 1400 ms 818728 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 1508 ms 830124 KB Output is correct
6 Correct 1397 ms 829992 KB Output is correct
7 Correct 1432 ms 828812 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1389 ms 830052 KB Output is correct
2 Correct 1456 ms 829992 KB Output is correct
3 Correct 1400 ms 818728 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 1508 ms 830124 KB Output is correct
6 Correct 1397 ms 829992 KB Output is correct
7 Correct 1432 ms 828812 KB Output is correct
8 Correct 1458 ms 830320 KB Output is correct
9 Correct 1524 ms 830228 KB Output is correct
10 Correct 1391 ms 817244 KB Output is correct
11 Correct 8 ms 1252 KB Output is correct
12 Correct 1572 ms 830232 KB Output is correct
13 Correct 1586 ms 830244 KB Output is correct
14 Correct 1423 ms 830156 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1389 ms 830052 KB Output is correct
2 Correct 1456 ms 829992 KB Output is correct
3 Correct 1400 ms 818728 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 1508 ms 830124 KB Output is correct
6 Correct 1397 ms 829992 KB Output is correct
7 Correct 1432 ms 828812 KB Output is correct
8 Correct 1458 ms 830320 KB Output is correct
9 Correct 1524 ms 830228 KB Output is correct
10 Correct 1391 ms 817244 KB Output is correct
11 Correct 8 ms 1252 KB Output is correct
12 Correct 1572 ms 830232 KB Output is correct
13 Correct 1586 ms 830244 KB Output is correct
14 Correct 1423 ms 830156 KB Output is correct
15 Correct 1843 ms 833076 KB Output is correct
16 Correct 1852 ms 832968 KB Output is correct
17 Correct 1575 ms 822076 KB Output is correct
18 Correct 30 ms 2740 KB Output is correct
19 Correct 1865 ms 832836 KB Output is correct
20 Correct 1847 ms 832780 KB Output is correct
21 Correct 1796 ms 832260 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 15061 ms 569284 KB Output is correct
2 Correct 15145 ms 572984 KB Output is correct
3 Correct 4767 ms 236644 KB Output is correct
4 Correct 3398 ms 98968 KB Output is correct
5 Execution timed out 25106 ms 951972 KB Time limit exceeded
6 Halted 0 ms 0 KB -