제출 #680510

#제출 시각아이디문제언어결과실행 시간메모리
680510chessmayimayiHomecoming (BOI18_homecoming)C++17
0 / 100
1004 ms46864 KiB
#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 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...