#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int inf = int(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) (((x) + (y) - 1) / (y))
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
signed main()
{
fast();
int n, q;
cin >> n >> q;
vi balls(n);
rep(i, n) cin >> balls[i];
vi delta(q);
rep(i, q) cin >> delta[i];
n += 2;
balls.insert(balls.begin(), - inf);
balls.push_back(inf);
bool posfirst = delta[0] > 0;
vi pref(delta);
repp(i, 1, q) pref[i] += pref[i - 1];
vi prefmax(pref);
vi prefmin(pref);
repp(i, 1, q) prefmax[i] = max(prefmax[i], prefmax[i - 1]);
repp(i, 1, q) prefmin[i] = min(prefmin[i], prefmin[i - 1]);
prefmax.insert(prefmax.begin(), 0LL);
prefmin.insert(prefmin.begin(), 0LL);
delta.insert(delta.begin(), 0LL);
q++;
repp(i, 1, n - 1)
{
int l = 0;
rep(j, q)
{
int mlo = balls[i] + prefmin[j];
int phi = balls[i - 1] + prefmax[j];
if (phi>=mlo)
{
if (delta[j] > 0) l = balls[i] - mlo;
else l = balls[i] - phi;
break;
}
else
{
l = max(l, balls[i] - mlo);
}
}
int r = 0;
rep(j, q)
{
int mhi = balls[i] + prefmax[j];
int plo = balls[i + 1] + prefmin[j];
if (mhi>=plo)
{
if (delta[j] > 0) r = plo-balls[i];
else r = mhi-balls[i];
break;
}
else
{
r = max(r, mhi - balls[i]);
}
}
cout << l + r << "\n";
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:40:10: warning: unused variable 'posfirst' [-Wunused-variable]
40 | bool posfirst = delta[0] > 0;
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
604 KB |
Output is correct |
| 5 |
Correct |
4 ms |
604 KB |
Output is correct |
| 6 |
Correct |
4 ms |
612 KB |
Output is correct |
| 7 |
Incorrect |
4 ms |
468 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
4 ms |
604 KB |
Output is correct |
| 5 |
Correct |
4 ms |
604 KB |
Output is correct |
| 6 |
Correct |
4 ms |
612 KB |
Output is correct |
| 7 |
Incorrect |
4 ms |
468 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
