#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define piii pair<int, pii>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
freopen("in.txt", "r", stdin);
int n, T; cin >> n >> T;
tiiii A[n];
for(auto &[a, b, c, d] : A) cin >> a >> b >> c >> d;
vector<long long> prX, prY;
for(auto &[a, b, c, d] : A)
{
if(b < c)
{
prX.push_back(1ll * a + b);
prX.push_back(1ll * a - b + 2 * c);
prY.push_back(1ll * a - b);
}
else
{
prX.push_back(1ll * a + b);
prY.push_back(1ll * a + b - 2 * c);
prY.push_back(1ll * a - b);
}
}
prX.push_back((long long)4e9+7);
prY.push_back((long long)4e9+7);
sort(prX.begin(), prX.end());
sort(prY.begin(), prY.end());
prX.resize(unique(prX.begin(), prX.end()) - prX.begin());
prY.resize(unique(prY.begin(), prY.end()) - prY.begin());
int N = prX.size(), M = prY.size();
int CX[N + 1][M + 1]{}, CY[N + 1][M + 1]{};
for(auto &[a, b, c, d] : A)
{
if(b < c)
{
int x1 = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
int x2 = lower_bound(prX.begin(), prX.end(), 1ll * a - b + 2 * c) - prX.begin();
int y = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin();
for(int j = x1; j < x2; ++j) CX[j][y] = max(CX[j][y], d / 2);
}
else
{
int x = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin();
int y1 = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin();
int y2 = lower_bound(prY.begin(), prY.end(), 1ll * a + b - 2 * c) - prY.begin();
for(int j = y1; j < y2; ++j) CY[x][j] = max(CY[x][j], d / 2);
}
}
long long dp[N + 1][M + 1]{};
for(int i = N; i >= 0; --i)
{
for(int j = M; j >= 0; --j)
{
if(i < N) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1ll * CX[i][j] * (prX[i + 1] - prX[i]));
if(j < M) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1ll * CY[i][j] * (prY[j + 1] - prY[j]));
}
}
// for(int i = 0; i <= N; ++i)
// {
// for(int j = 0; j <= M; ++j)
// cout << dp[i][j] << ' ';
// cout << endl;
// }
vector<pll> lsX[N + 1][M + 1], lsY[N + 1][M + 1];
for(int i = 0; i < T; ++i)
{
int x, y; cin >> x >> y;
int xi = lower_bound(prX.begin(), prX.end(), x + y) - prX.begin();
int yi = lower_bound(prY.begin(), prY.end(), x - y) - prY.begin();
lsX[xi][yi].push_back({prX[xi] - x - y, i});
lsY[xi][yi].push_back({prY[yi] - x + y, i});
}
long long ans[T]{};
for(int i = 0; i <= N; ++i)
{
for(int j = 0; j <= M; ++j)
{
for(auto [x, q] : lsX[i][j])
for(int k = j; k <= M; ++k) ans[q] = max(ans[q], dp[i][k] + 1ll * x * (i ? CX[i - 1][k] : 0));
for(auto [x, q] : lsY[i][j])
for(int k = i; k <= N; ++k) ans[q] = max(ans[q], dp[k][j] + 1ll * x * (j ? CY[k][j - 1] : 0));
}
}
for(auto i : ans) cout << i << '\n';
}
Compilation message
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
4304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
4276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
4276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
4276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
4304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
