답안 #682158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682158 2023-01-16T02:20:12 Z chessmayimayi Homecoming (BOI18_homecoming) C++17
13 / 100
165 ms 121664 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];
  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);

  // A1 is not taken;
  take[1] = -inf;
  dp[1] = 0;
  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] - sumb[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;
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12100 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12100 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12244 KB Output is correct
7 Correct 7 ms 12344 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12244 KB Output is correct
10 Incorrect 8 ms 12116 KB Output isn't correct
11 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 39420 KB Output is correct
2 Correct 8 ms 12136 KB Output is correct
3 Correct 165 ms 121664 KB Output is correct
4 Correct 10 ms 13184 KB Output is correct
5 Incorrect 15 ms 14928 KB Output isn't correct
6 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12100 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 5 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 12244 KB Output is correct
7 Correct 7 ms 12344 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12244 KB Output is correct
10 Incorrect 8 ms 12116 KB Output isn't correct
11 Halted 0 ms 0 KB -