Submission #682184

# Submission time Handle Problem Language Result Execution time Memory
682184 2023-01-16T04:06:21 Z chessmayimayi Homecoming (BOI18_homecoming) C++17
100 / 100
201 ms 161100 KB
#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