제출 #680510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680510		chessmayimayi	Homecoming (BOI18_homecoming)	C++17	0 / 100	1004 ms	46864 KiB

homecoming

#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[]) {
  vector<ll> b(n + 1), a(n + 1), sum1(n + 1), sum2(n + 1);
  rep1(i, n) {
    a[i] = aa[i - 1];
    sum1[i] += sum1[i - 1] + a[i];
  }
  rep1(i, n) {
    b[i] = bb[i - 1];
    sum2[i] += sum2[i - 1] + b[i];
  }
  vector<ll> dp(n + 1);
  rep1(i, n) {
    dp[i] = a[i] - sum2[i + k - 1] + sum2[i - 1];
    dd("start");
    dd(i);
    dd(dp[i]);
    rep1(j, i - 1) {
      if (i <= j + k - 1)
        dp[i] =
            max(sum1[i] - sum1[j - 1] - sum2[i + k - 1] + sum2[j - 1], dp[i]);
      dd(i);
      dd(j);
      dd(dp[i]);
    }
  }
  ll res = 0;
  rep1(i, n) { res = max(res, dp[i]); }
  cout << res << nn;
}
// int main() {
// fastio();
// // int T;
// // cin >> T;
//
//
// cout<<
// 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;

컴파일 시 표준 에러 (stderr) 메시지

homecoming.cpp: In function 'll solve(int, int, int*, int*)':
homecoming.cpp:429:1: warning: no return statement in function returning non-void [-Wreturn-type]
  429 | }
      | ^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38