Submission #1073219

#TimeUsernameProblemLanguageResultExecution timeMemory
1073219vjudge1Tricks of the Trade (CEOI23_trade)C++17
30 / 100
2180 ms2097152 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; //#define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int nmax = 25e4 + 5; int K; template<typename T> struct Deq { vector<T> v; void push_front(T x) { v.emplace_back(x); } T& operator[](const int& x) { return rbegin(v)[x]; } void resize(int k) { if(k >= sz(v)) return; v.erase(begin(v), begin(v) + sz(v) - k); return; } int size() { return sz(v); } }; // trebuie facut persistent struct Tree { vector<int> g[nmax]; int p[nmax]; void add_edge(int a, int b) { g[a].emplace_back(b); p[b] = a; } struct mdeq : Deq<ll> { ll lazy = 0; }; mdeq dp[nmax]; vector<bool> merge[nmax]; int calculated[nmax]; Tree(int n) { memset(calculated, 0, sizeof(calculated)); } template<class CB, class CB2> void calcdp(CB&& cost, CB2 atr, int node) { if(calculated[node]) return; calculated[node] = 1; for(auto x : g[node]) { calcdp(cost, atr, x); dp[x].resize(K); bool swapped = 0; auto T = dp[x]; if(sz(T) > sz(dp[node])) swap(T, dp[node]); for(int i = 0; i < sz(T); i++) dp[node][i] = max(T[i] + T.lazy - dp[node].lazy, dp[node][i]); } dp[node].push_front(cost(node) - dp[node].lazy); dp[node].lazy += atr(node); merge[node].assign(sz(dp[node]), 0); return; } template<class CB> void propmerge(CB&& atr, vector<int> order) { for(auto node : order) { for(auto x : g[node]) { auto T = dp[x]; for(int i = 0; i < sz(T) && i + 1 < sz(dp[node]); i++) { if(T[i] + T.lazy - dp[node].lazy + atr(node) == dp[node][i + 1]) merge[x][i] = merge[x][i] || merge[node][i + 1]; } } } return; } }; ll spart[nmax]; signed main() { cin.tie(0) -> sync_with_stdio(0); int n; cin >> n >> K; for(int i = 1, x; i <= n; i++) { cin >> spart[i]; spart[i] += spart[i - 1]; } vector<int> v(n + 1); for(int i = 1; i <= n; i++) cin >> v[i]; Tree toleft(n), toright(n); vector<int> st; for(int i = 1; i <= n; i++) { while(sz(st) && v[st.back()] <= v[i]) st.pop_back(); if(sz(st) == 0) toleft.add_edge(0, i); else toleft.add_edge(st.back(), i), toright.add_edge(i, st.back()); st.emplace_back(i); } st.clear(); for(int i = n; i > 0; i--) { while(sz(st) && v[st.back()] < v[i]) st.pop_back(); if(sz(st) == 0) toright.add_edge(0, i); else toright.add_edge(st.back(), i), toleft.add_edge(i, st.back()); st.emplace_back(i); } st.clear(); toleft.calcdp([&](int x) { return x == 0? 0 : -spart[x]; }, [&](int x) { return v[x]; }, 0); toright.calcdp([&](int x) { return x == 0? 0 : spart[x - 1]; }, [&](int x) { return v[x]; }, 0); ll best_cost = -1e18; for(int P = 1; P <= n; P++) { auto& X = toleft.dp[P]; auto& Y = toright.dp[P]; bool swapped = 0; if(sz(X) > sz(Y)) swapped = 1, swap(X, Y); for(int i = 0; i < min(K, sz(X)); i++) { int j = K - i - 1; if(j >= sz(Y)) continue; best_cost = max(best_cost, X[i] + Y[j] + X.lazy + Y.lazy - v[P]); } if(swapped) swap(X, Y); } for(int P = 1; P <= n; P++) { auto& X = toleft.dp[P]; auto& Y = toright.dp[P]; bool swapped = 0; if(sz(X) > sz(Y)) swapped = 1, swap(X, Y); for(int i = 0; i < min(K, sz(X)); i++) { int j = K - i - 1; if(j >= sz(Y)) continue; if(best_cost == X[i] + Y[j] + X.lazy + Y.lazy - v[P]) { if(!swapped) toleft.merge[P][i] = 1, toright.merge[P][j] = 1; else toright.merge[P][i] = 1, toleft.merge[P][j] = 1; } } if(swapped) swap(X, Y); } vector<int> order(n); iota(all(order), 1); toleft.propmerge([&](int x) { return v[x]; }, order); reverse(all(order)); toright.propmerge([&](int x) { return v[x]; }, order); cout << best_cost << '\n'; for(int i = 1; i <= n; i++) { bool ok = 0; for(auto x : toleft.merge[i]) { if(ok) break; if(x) { ok = 1; break; } } for(auto x : toright.merge[i]) { if(ok) break; if(x) { ok = 1; break; } } cout << ok; } cout << '\n'; } /** Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen -- */

Compilation message (stderr)

trade.cpp: In function 'int main()':
trade.cpp:93:19: warning: unused variable 'x' [-Wunused-variable]
   93 |    for(int i = 1, x; i <= n; i++) {
      |                   ^
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>]':
trade.cpp:120:94:   required from here
trade.cpp:57:15: warning: unused variable 'swapped' [-Wunused-variable]
   57 |          bool swapped = 0;
      |               ^~~~~~~
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>]':
trade.cpp:121:98:   required from here
trade.cpp:57:15: warning: unused variable 'swapped' [-Wunused-variable]
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>&; CB2 = main()::<lambda(int)>]':
trade.cpp:55:16:   required from 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>]'
trade.cpp:120:94:   required from here
trade.cpp:57:15: warning: unused variable 'swapped' [-Wunused-variable]
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>&; CB2 = main()::<lambda(int)>]':
trade.cpp:55:16:   required from 'void Tree::calcdp(CB&&, CB2, int) [with CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>]'
trade.cpp:121:98:   required from here
trade.cpp:57:15: warning: unused variable 'swapped' [-Wunused-variable]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...