| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 457643 |
2021-08-07T09:15:41 Z |
8e7 |
Bodyguard (JOI21_bodyguard) |
C++17 |
|
3501 ms |
2097156 KB |
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#define ll long long
#define maxn 3005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct seg{
pii st, ed;
ll cost;
seg(){st = {0, 0}, ed = {0, 0}, cost = 0;}
seg(pii x, pii y, ll c){st = x, ed = y, cost = c;};
} arr[maxn];
vector<ll> xv, yv;
vector<vector<pii> > cost;
vector<vector<ll> > dp;
int main() {
io
int n, q;
cin >> n >> q;
auto turn = [&](pii p) {return make_pair((p.ff - p.ss), (p.ff + p.ss));};
for (int i = 0;i < n;i++) {
ll t, a, b, c;
cin >> t >> a >> b >> c;
pii p1 = {t, a}, p2 = {t + abs(b - a), b};
p1 = turn(p1), p2 = turn(p2);
arr[i] = seg(p1, p2, c / 2);
xv.push_back(p1.ff), xv.push_back(p2.ff);
yv.push_back(p1.ss), yv.push_back(p2.ss);
}
for (int i = -3000;i < 6001;i++) xv.push_back(i), yv.push_back(i);
sort(xv.begin(), xv.end()), sort(yv.begin(), yv.end());
xv.resize(int(unique(xv.begin(), xv.end()) - xv.begin()));
yv.resize(int(unique(yv.begin(), yv.end()) - yv.begin()));
//pary(xv.begin(), xv.end());
//pary(yv.begin(), yv.end());
int xs = xv.size(), ys = yv.size();
for (int i = 0;i < xs;i++) {
vector<pii> ac(ys, {0, 0});
vector<ll> dc(ys, 0);
cost.push_back(ac), dp.push_back(dc);
}
for (int i = 0;i < n;i++) {
int sx = lower_bound(xv.begin(), xv.end(), arr[i].st.ff) - xv.begin();
int tx = lower_bound(xv.begin(), xv.end(), arr[i].ed.ff) - xv.begin();
int sy = lower_bound(yv.begin(), yv.end(), arr[i].st.ss) - yv.begin();
int ty = lower_bound(yv.begin(), yv.end(), arr[i].ed.ss) - yv.begin();
if (sx == tx) {
for (int j = sy;j < ty;j++) cost[sx][j].ss = max(cost[sx][j].ss, arr[i].cost);
} else {
for (int j = sx;j < tx;j++) cost[j][sy].ff = max(cost[j][sy].ff, arr[i].cost);
}
}
for (int i = xs - 1;i >= 0;i--) {
for (int j = ys - 1;j >= 0;j--) {
dp[i][j] = max((i < xs - 1 ? dp[i + 1][j] + (xv[i + 1] - xv[i]) * cost[i][j].ff : 0),
(j < ys - 1 ? dp[i][j + 1] + (yv[j + 1] - yv[j]) * cost[i][j].ss : 0));
}
}
while (q--) {
pii p;
cin >> p.ff >> p.ss;
p = turn(p);
int x = lower_bound(xv.begin(), xv.end(), p.ff) - xv.begin();
int y = lower_bound(yv.begin(), yv.end(), p.ss) - yv.begin();
//debug(x, y);
/*
ll ans = 0;
if (x < xs) {
for (int i = y;i < ys;i++) {
ans = max(ans, dp[x][i] + (x ? (xv[x] - p.ff) * cost[x-1][i].ff : 0));
}
}
if (y < ys) {
for (int i = x;i < xs;i++) {
ans = max(ans, dp[i][y] + (y ? (yv[y] - p.ss) * cost[i][y-1].ss : 0));
}
}
cout << ans << "\n";
*/
cout << dp[x][y] << "\n";
//debug();
}
}
/*
2 2
1 2 1 4
3 1 3 2
1 2
3 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3501 ms |
2016476 KB |
Output is correct |
| 2 |
Correct |
3451 ms |
2020188 KB |
Output is correct |
| 3 |
Correct |
3233 ms |
1962700 KB |
Output is correct |
| 4 |
Correct |
3431 ms |
1954128 KB |
Output is correct |
| 5 |
Runtime error |
1012 ms |
2097156 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1074 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1074 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1074 ms |
2097156 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3501 ms |
2016476 KB |
Output is correct |
| 2 |
Correct |
3451 ms |
2020188 KB |
Output is correct |
| 3 |
Correct |
3233 ms |
1962700 KB |
Output is correct |
| 4 |
Correct |
3431 ms |
1954128 KB |
Output is correct |
| 5 |
Runtime error |
1012 ms |
2097156 KB |
Execution killed with signal 9 |
