oj.uz

답안 #682185

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682185 2023-01-16T04:07:19 Z chessmayimayi Homecoming (BOI18_homecoming) C++17
100 / 100
 175 ms 121684 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;

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 8 ms 12080 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 7 ms 11996 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 8 ms 12080 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 7 ms 11996 KB Output is correct
6 Correct 7 ms 12280 KB Output is correct
7 Correct 8 ms 12244 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 7 ms 12244 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 39380 KB Output is correct
2 Correct 9 ms 12132 KB Output is correct
3 Correct 175 ms 121676 KB Output is correct
4 Correct 10 ms 13140 KB Output is correct
5 Correct 14 ms 13256 KB Output is correct

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 8 ms 12080 KB Output is correct
4 Correct 7 ms 11988 KB Output is correct
5 Correct 7 ms 11996 KB Output is correct
6 Correct 7 ms 12280 KB Output is correct
7 Correct 8 ms 12244 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 7 ms 12244 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 50 ms 39380 KB Output is correct
12 Correct 9 ms 12132 KB Output is correct
13 Correct 175 ms 121676 KB Output is correct
14 Correct 10 ms 13140 KB Output is correct
15 Correct 14 ms 13256 KB Output is correct
16 Correct 164 ms 121684 KB Output is correct
17 Correct 76 ms 25740 KB Output is correct
18 Correct 138 ms 18076 KB Output is correct
19 Correct 137 ms 66884 KB Output is correct
20 Correct 140 ms 121632 KB Output is correct
21 Correct 133 ms 69980 KB Output is correct