#include <assert.h>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
typedef long double lld;
typedef priority_queue<ll> pqb;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqs;
typedef priority_queue<pll> ppqb;
typedef priority_queue<pll, vector<pll>, greater<pll>> ppqs;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<pll> vpll;
typedef vector<double> vd;
typedef vector<pdd> vpdd;
typedef vector<vd> vvd;
//.................useful constant...................//
const long long inf = 1e18;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int dx2[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy2[8] = {0, 1, 1, 1, 0, -1, -1, -1};
//....................END useful constant...............//
//.................useful #define...................//
#define INF 0x3f3f3f3f
#define rep(i, n) for (int i = 0; i < (ll)n; ++i)
#define rep1(i, n) for (int i = 1; i <= (ll)n; ++i)
#define rep2(i, k, n) for (int i = (ll)k; i <= (ll)n; ++i)
#define fastio() \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL)
#define nn "\n"
#define pb push_back
#define x first
#define y second
#define vc vector<ll>
#define vvc vector<vector<ll>>
#define all(x) x.begin(), x.end()
#define add0(mu) mu.insert(mu.begin(), 0)
#define sortb(x) \
sort(all(x)); \
reverse(all(x));
#define minl(v) *min_element(all(v))
#define maxl(v) *max_element(all(v))
#define lb(c, x) lower_bound(all(c), (x))
#define ub(c, x) upper_bound(all(c), (x))
#define lb1(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub1(c, x) distance((c).begin(), upper_bound(all(c), (x)))
//.................END useful #define...................//
//............ debug setup...............................//
#ifndef ONLINE_JUDGE
#define dd(x) \
cerr << #x << " "; \
_print(x); \
cerr << endl;
#else
#define dd(x)
#endif
void _print(ll t) { cerr << t; }
void _print(int t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(lld t) { cerr << t; }
void _print(double t) { cerr << t; }
void _print(ull t) { cerr << t; }
template <class T>
void _print(queue<T> v);
template <class T>
void _print(deque<T> v);
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T>
void _print(queue<T> v) {
cerr << "[ ";
for (T i : v) {
_print(i);
cerr << " ";
}
cerr << "]";
}
template <class T>
void _print(deque<T> v) {
cerr << "[ ";
for (T i : v) {
_print(i);
cerr << " ";
}
cerr << "]";
}
template <class T, class V>
void _print(pair<T, V> p) {
cerr << "{";
_print(p.first);
cerr << ",";
_print(p.second);
cerr << "}";
}
template <class T>
void _print(vector<T> v) {
cerr << "[ ";
for (T i : v) {
_print(i);
cerr << " ";
}
cerr << "]";
}
template <class T>
void _print(set<T> v) {
cerr << "[ ";
for (T i : v) {
_print(i);
cerr << " ";
}
cerr << "]";
}
template <class T>
void _print(multiset<T> v) {
cerr << "[ ";
for (T i : v) {
_print(i);
cerr << " ";
}
cerr << "]";
}
template <class T, class V>
void _print(map<T, V> v) {
cerr << "[ ";
for (auto i : v) {
_print(i);
cerr << " ";
}
cerr << "]";
}
//.............END debug setup..............//
//..........General setup .....................//
const int N = 500010;
ll n, m, k, q, d;
//..........END General Setup....................//
//.......... Data Structure ..............//
// Union-Find
int fa[N];
int find(int u) {
// 返回根编号 + 集合内元素的父编号统一成根编号
if (u != fa[u]) fa[u] = find(fa[u]);
return fa[u];
}
// Segment Tree
namespace atcoder {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)>
int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F>
int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)>
int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F>
int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
//..........END Data Structure ..............//
//...............Math Function..................//
// modular
const ll mod = 1e9 + 7;
int mul(ll a, ll b) { return (1LL * a * b) % mod; }
int ad(ll a, ll b) {
int s = (a + b);
if (s >= mod) s -= mod;
return s;
}
ll sub(ll a, ll b) {
int s = (a + mod - b);
if (s >= mod) s -= mod;
return s;
}
ll qpow(ll x, ll y) {
x %= mod;
ll res = 1ll;
while (y) {
if (y & 1) res *= x, res %= mod;
x *= x;
x %= mod;
y >>= 1;
}
return res;
}
inline ll inv(ll x) { return qpow(x, mod - 2); }
// C(m,n)
ll fac[N], ifac[N];
void init_fac(ll n) {
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
ifac[n] = inv(fac[n]);
for (int i = n; i; --i) ifac[i - 1] = ifac[i] * i % mod;
}
inline ll comb(int x, int y) {
if (x < y || y < 0) return 0;
return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}
//..............END Math Function.................//
//............... Graph ...............//
const int M = 2 * N; //无向图
// const int M = N; //有向图
int vis[N];
ll dist[N];
//邻接表的vector表示a->b, weights c
vector<ll> adj[N];
//邻接表的链式前向星表示
int h[N], e[M], ne[M], w[M], idx;
// 添加一条边a->b,h[a]是a的第一条边（即当前idx的边)，
// ne是a指向第二条边(即idx-1指向的边），next直到idx=-1
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c;
h[a] = idx++;
}
//遍历邻接表
// for (int i = h[u]; i != -1; i = ne[i])
// edge for kruskal
struct Edge {
int a, b, c;
bool operator<(const Edge& w) const { return c < w.c; }
} edge[N];
// dfs
ll sz[N]; // sz[leaf] = 1
ll dep[N]; // dep[root]=0;
ll deg[N]; //拓扑排序入度
void dfs(int u, int p = 0) {
sz[u] = 1;
for (int v : adj[u]) {
if (v == p) continue;
dep[v] = dep[u] + 1;
dfs(v, u);
sz[u] += sz[v];
}
}
//...............END Graph ...............//
//..........helper functions..................//
// pair 1st <, 2nd >;
bool cmp(pll a, pll b) { return a.x != b.x ? a.x < b.x : a.y > b.y; };
//..........END helper functions..............//
//...............Main Program..................//
ll solve(int n, int k, int aa[], int bb[]) {
fastio();
vector<ll> b(n + 1), a(n + 1), suma(n + 1), sumb(n + 1);
rep1(i, n) {
a[i] = aa[i - 1];
suma[i] += suma[i - 1] + a[i];
}
rep1(i, n) {
b[i] = bb[i - 1];
sumb[i] += sumb[i - 1] + b[i];
}
vll dp(n + 1);
vll take(n + 1);
ll res = 0;
// A1 is taken;
take[1] = a[1] - sumb[k];
dp[1] = take[1];
res = max(res, dp[1]);
rep2(i, 2, n) {
if (i + k - 1 <= n) {
take[i] = max(take[i - 1] + a[i] - b[i + k - 1],
dp[i - 1] + a[i] - sumb[i + k - 1] + sumb[i - 1]);
} else {
take[i] =
max(take[i - 1] + a[i], dp[i - 1] + a[i] - sumb[n] + sumb[i - 1]);
}
dp[i] = max(dp[i - 1], take[i]);
res = max(res, dp[i]);
}
// dp.clear();
// dp.resize(n + 1, -inf);
// take.clear();
// take.resize(n + 1, -inf);
if (n == k) return res;
// A1 is not taken;
take[1] = -inf;
dp[1] = 0;
res = max(res, dp[1]);
rep2(i, 2, n) {
if (i + k - 1 <= n) {
take[i] = max(take[i - 1] + a[i] - b[i + k - 1],
dp[i - 1] + a[i] - sumb[i + k - 1] + sumb[i - 1]);
} else {
take[i] =
max(take[i - 1] + a[i] - b[i + k - 1 - n],
dp[i - 1] + a[i] - sumb[n] + sumb[i - 1] - sumb[i + k - 1 - n]);
}
dp[i] = max(dp[i - 1], take[i]);
res = max(res, dp[i]);
}
return res;
}
//
// int aa[N], bb[N];
// int main() {
// fastio();
// // int T;
// // cin >> T;
//
// int T = 1;
// while (T--) {
// cin >> n >> k;
// rep(i, n) { cin >> aa[i]; }
// rep(i, n) { cin >> bb[i]; }
// cout << solve(n, k, aa, bb);
// }
// return 0;
// }
// string erase(it), replace(it,it,cnt, 'a');
// memset(h, -1, sizeof h);
// memset(a,0,sizeof(a)) ; // initialize with 0
// memset(a,-1,sizeof(a)); // initializing with -1
// memset(a,0xc0,sizeof(a)); // initializing with negative infinity
// memset(a,0x3f,sizeof(a)); // initializing with positive infinity
// memset(h, -1, sizeof h);
// rep(i, n + 3) { adj[i].clear(); }
// k = 0; n = 0;
// vector<vector<ll>>adj(n, vector<ll>());
// std::cout << std::setprecision(2) << std::fixed;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12088 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
6 ms |
12080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12088 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
6 ms |
12080 KB |
Output is correct |
| 6 |
Correct |
7 ms |
12344 KB |
Output is correct |
| 7 |
Correct |
7 ms |
12372 KB |
Output is correct |
| 8 |
Correct |
8 ms |
12244 KB |
Output is correct |
| 9 |
Correct |
8 ms |
12372 KB |
Output is correct |
| 10 |
Correct |
9 ms |
12180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
48872 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12628 KB |
Output is correct |
| 3 |
Correct |
201 ms |
141456 KB |
Output is correct |
| 4 |
Correct |
8 ms |
13396 KB |
Output is correct |
| 5 |
Correct |
14 ms |
14864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12088 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
6 ms |
12080 KB |
Output is correct |
| 6 |
Correct |
7 ms |
12344 KB |
Output is correct |
| 7 |
Correct |
7 ms |
12372 KB |
Output is correct |
| 8 |
Correct |
8 ms |
12244 KB |
Output is correct |
| 9 |
Correct |
8 ms |
12372 KB |
Output is correct |
| 10 |
Correct |
9 ms |
12180 KB |
Output is correct |
| 11 |
Correct |
54 ms |
48872 KB |
Output is correct |
| 12 |
Correct |
9 ms |
12628 KB |
Output is correct |
| 13 |
Correct |
201 ms |
141456 KB |
Output is correct |
| 14 |
Correct |
8 ms |
13396 KB |
Output is correct |
| 15 |
Correct |
14 ms |
14864 KB |
Output is correct |
| 16 |
Correct |
200 ms |
161100 KB |
Output is correct |
| 17 |
Correct |
92 ms |
37304 KB |
Output is correct |
| 18 |
Correct |
151 ms |
55048 KB |
Output is correct |
| 19 |
Correct |
146 ms |
94148 KB |
Output is correct |
| 20 |
Correct |
147 ms |
144224 KB |
Output is correct |
| 21 |
Correct |
147 ms |
94572 KB |
Output is correct |
