제출 #223067

#제출 시각아이디문제언어결과실행 시간메모리
223067staniewzki휴가 (IOI14_holiday)C++17
30 / 100
1064 ms11284 KiB
#include<bits/stdc++.h> using namespace std; #define REP(i, n) for(int i = 0; i < n; i++) #define FOR(i, a, b) for(int i = a; i <= b; i++) #define ST first #define ND second ostream& operator<<(ostream &out, string str) { for(char c : str) out << c; return out; } template<class L, class R> ostream& operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.ST << ", " << p.ND << ")"; } template<class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) { out << "{"; for(auto it = a.begin(); it != a.end(); it = next(it)) out << (it != a.begin() ? ", " : "") << *it; return out << "}"; } void dump() { cerr << "\n"; } template<class T, class... Ts> void dump(T a, Ts... x) { cerr << a << ", "; dump(x...); } #ifdef DEBUG # define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__) #else # define debug(...) false #endif template<class T> int size(T && a) { return (int) a.size(); } using LL = long long; using PII = pair<int, int>; #include"holiday.h" struct SegTree { using T = pair<LL, int>; vector<T> tree; int sz = 1; T f(T a, T b) { T ret = {0, 0}; if(a.ND != 0) { ret.ST += a.ST; ret.ND += a.ND; } if(b.ND != 0) { ret.ST += b.ST; ret.ND += b.ND; } return ret; } SegTree(vector<int> a) { int n = size(a); while(sz < n) sz *= 2; tree.resize(sz * 2); REP(i, n) tree[i + sz].ST = a[i]; } void update(int v, int q) { tree[v += sz].ND = q; while(v /= 2) tree[v] = f(tree[v * 2], tree[v * 2 + 1]); } LL query(int k) { int v = 1; LL ret = 0; while(v < sz) { if(k < tree[v * 2].ND) v *= 2; else { k -= tree[v * 2].ND; if(tree[v * 2].ND) ret += tree[v * 2].ST; v = v * 2 + 1; } } return ret; } }; long long int findMaxAttraction(int n, int start, int d, int attraction[]) { auto get_on_right = [&](int cost) { vector<int> a(n), per(n); REP(i, n) { a[i] = attraction[i]; per[i] = i; } debug(a); sort(per.begin(), per.end(), [&](int i, int j) { return a[i] > a[j]; }); sort(a.rbegin(), a.rend()); vector<int> ord(n); REP(i, n) ord[per[i]] = i; SegTree tree(a); vector<LL> ret(d + 1); auto solve = [&](auto self, int d_l, int d_r, int opt_l, int opt_r) { if(opt_l > opt_r) return; if(d_l > d_r) { FOR(i, opt_l, opt_r) tree.update(ord[i], true); return; } int cur_d = (d_l + d_r) / 2; pair<LL, int> best = {0, opt_l}; FOR(i, opt_l, opt_r) { tree.update(ord[i], true); LL x = tree.query(cur_d - cost * (i - start)); best = max(best, {x, i}); } FOR(i, opt_l, opt_r) tree.update(ord[i], false); int opt = best.ND; ret[cur_d] = best.ST; self(self, d_l, cur_d - 1, opt_l, opt); tree.update(ord[opt], false); self(self, cur_d + 1, d_r, opt, opt_r); }; solve(solve, 0, d, start + cost - 1, n - 1); FOR(i, start, n - 1) tree.update(ord[i], false); return ret; }; auto rev = [&]() { reverse(attraction, attraction + n); start = n - 1 - start; }; auto left_then_right = [&]() { auto A = get_on_right(1); rev(); auto B = get_on_right(2); FOR(i, 0, d) debug(i, A[i], B[i]); LL ret = 0; FOR(i, 0, d) ret = max(ret, A[i] + B[d - i]); return ret; }; return max(left_then_right(), left_then_right()); }

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

holiday.cpp: In lambda function:
holiday.cpp:99:11: warning: statement has no effect [-Wunused-value]
   debug(a);
           ^
holiday.cpp: In lambda function:
holiday.cpp:158:24: warning: statement has no effect [-Wunused-value]
    debug(i, A[i], B[i]);
                        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...