oj.uz

Submission #892645

# Submission time Handle Problem Language Result Execution time Memory
892645 2023-12-25T16:04:32 Z marvinthang Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 281428 KB 
/*************************************
*    author: marvinthang             *
*    created: 25.12.2023 20:42:18    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { return a > b ? a = b, true : false; }
template <class A, class B> bool maximize(A &a, B b)  { return a < b ? a = b, true : false; }

// end of template

const int MAXN = 2801;
const int MAXQ = 3003;
const int MAXV = MAXN * 2 + MAXQ;

int ma[MAXV][MAXV][2];
long long dp[MAXV][MAXV];

void process(void) {
	int n, q; cin >> n >> q;
	vector <long long> x(n), y(n), u(n), v(n), c(n);
	vector <long long> cx, cy;
	REP(i, n) {
		long long t, a, b;
		cin >> t >> a >> b >> c[i]; c[i] /= 2;
		x[i] = t + a; 
		y[i] = t - a;
		u[i] = t + abs(a - b) + b;
		v[i] = t + abs(a - b) - b;
		cx.push_back(x[i]); cx.push_back(u[i]);
		cy.push_back(y[i]); cy.push_back(v[i]);
	}
	vector <long long> s(q), t(q);
	sort(ALL(cx)); cx.erase(unique(ALL(cx)), cx.end());
	sort(ALL(cy)); cy.erase(unique(ALL(cy)), cy.end());

	REP(i, n) {
		x[i] = lower_bound(ALL(cx), x[i]) - cx.begin();
		y[i] = lower_bound(ALL(cy), y[i]) - cy.begin();
		u[i] = lower_bound(ALL(cx), u[i]) - cx.begin();
		v[i] = lower_bound(ALL(cy), v[i]) - cy.begin();
		if (x[i] == u[i]) {
			FOR(p, y[i], v[i]) maximize(ma[x[i]][p][0], c[i]);
		} else {
			FOR(p, x[i], u[i]) maximize(ma[p][y[i]][1], c[i]);
		}
	}

	REPD(x, cx.size()) REPD(y, cy.size()) {
		if (y + 1 < (int) cy.size()) maximize(dp[x][y], dp[x][y + 1] + 1LL * (cy[y + 1] - cy[y]) * ma[x][y][0]);
		if (x + 1 < (int) cx.size()) maximize(dp[x][y], dp[x + 1][y] + 1LL * (cx[x + 1] - cx[x]) * ma[x][y][1]);
	}

	while (q--) {
		long long p, q; cin >> p >> q; 
		tie(p, q) = pair{p + q, p - q};	
		int u = lower_bound(ALL(cx), p) - cx.begin();
		int v = lower_bound(ALL(cy), q) - cy.begin();
		long long res = 0;
		FOR(x, u, cx.size()) maximize(res, dp[x][v] + (v ? 1LL * (cy[v] - q) * ma[x][v - 1][0] : 0));
		FOR(y, v, cy.size()) maximize(res, dp[u][y] + (u ? 1LL * (cx[u] - p) * ma[u - 1][y][1] : 0));
		cout << res << '\n';
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("JOI21_bodyguard");
	// int t; cin >> t; while (t--)
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:103:2: note: in expansion of macro 'file'
  103 |  file("JOI21_bodyguard");
      |  ^~~~
bodyguard.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:103:2: note: in expansion of macro 'file'
  103 |  file("JOI21_bodyguard");
      |  ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25111 ms 194292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 279380 KB Output is correct
2 Correct 222 ms 278076 KB Output is correct
3 Correct 189 ms 276008 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 213 ms 203608 KB Output is correct
6 Correct 158 ms 153936 KB Output is correct
7 Correct 188 ms 188028 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 279380 KB Output is correct
2 Correct 222 ms 278076 KB Output is correct
3 Correct 189 ms 276008 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 213 ms 203608 KB Output is correct
6 Correct 158 ms 153936 KB Output is correct
7 Correct 188 ms 188028 KB Output is correct
8 Correct 430 ms 279888 KB Output is correct
9 Correct 413 ms 278180 KB Output is correct
10 Correct 217 ms 274476 KB Output is correct
11 Correct 8 ms 856 KB Output is correct
12 Correct 345 ms 203760 KB Output is correct
13 Correct 401 ms 154192 KB Output is correct
14 Correct 367 ms 203708 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 279380 KB Output is correct
2 Correct 222 ms 278076 KB Output is correct
3 Correct 189 ms 276008 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 213 ms 203608 KB Output is correct
6 Correct 158 ms 153936 KB Output is correct
7 Correct 188 ms 188028 KB Output is correct
8 Correct 430 ms 279888 KB Output is correct
9 Correct 413 ms 278180 KB Output is correct
10 Correct 217 ms 274476 KB Output is correct
11 Correct 8 ms 856 KB Output is correct
12 Correct 345 ms 203760 KB Output is correct
13 Correct 401 ms 154192 KB Output is correct
14 Correct 367 ms 203708 KB Output is correct
15 Correct 3012 ms 281260 KB Output is correct
16 Correct 2947 ms 281428 KB Output is correct
17 Correct 592 ms 278404 KB Output is correct
18 Correct 63 ms 2384 KB Output is correct
19 Correct 2310 ms 206032 KB Output is correct
20 Correct 3611 ms 155980 KB Output is correct
21 Correct 2620 ms 205380 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25111 ms 194292 KB Time limit exceeded
2 Halted 0 ms 0 KB -