Submission #1073332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073332		vjudge1	Tricks of the Trade (CEOI23_trade)	C++17	10 / 100	2499 ms	2097152 KiB

trade

#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 PVector {
   struct Vector {
      T val;
      Vector *L, *R;
   } *nil = new Vector{0, 0, 0}, *root = nil;
   PVector() {
      nil -> L = nil -> R = nil;
      root = nil;
   }
   using ns = Vector*;
   T access(int p, ns node, int cl = 0, int cr = nmax) const {
      int mid = (cl + cr) >> 1;
      if(p == mid) { return node -> val; }
      if(p < mid) { return access(p, node -> L, cl, mid - 1); }
      return access(p, node -> R, mid + 1, cr);
   }
   pair<T*, ns> overwrite(int p, ns node, int cl = 0, int cr = nmax) {
      int mid = (cl + cr) >> 1;
      if(p == mid) { auto tK = new Vector{node -> val, node -> L, node -> R}; return make_pair(&(tK -> val), tK); }
      if(p < mid) { auto a = overwrite(p, node -> L, cl, mid - 1); return make_pair(a.first, new Vector{node -> val, a.second, node -> R}); }
      auto a = overwrite(p, node -> R, mid + 1, cr);
      return make_pair(a.first, new Vector{node -> val, node -> L, a.second});
   }
   
   T operator[](const int& a) const {
      return access(a, root);
   }
   T* operator()(const int& a) {
      auto [x, y] = overwrite(a, root);
      root = y;
      return x;
   }
};



template<typename T>
struct Deq {
   int dim = 0, ldim = 0;
   PVector<T> v;
   void push_front(T x) { auto H = v(dim); (*H) = x; dim++;}
   T operator[](const int& x) { return v[dim - x - 1]; }
   T& operator()(const int& x) { auto H = v(dim - x - 1); return (*H); }
   void resize(int k)  {
      ldim = max(ldim, dim - k);
   }
   int size() { return dim - ldim; }
}; 

struct Tree {
   vector<int> g[nmax];
   void add_edge(int a, int b) {
      g[a].emplace_back(b);
   }
   
   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;
      
      vector<ll> updates;
      
      for(auto x : g[node]) {
         calcdp(cost, atr, x);
         bool swapped = 0;
      }
      sort(all(g[node]), [&](int a, int b) { return sz(dp[a]) > sz(dp[b]); });
      for(auto x : g[node]) {
         auto T = dp[x];
         T.resize(K + 1);
         
         if(sz(T) > sz(dp[node]))
            swap(T, dp[node]);
         
         updates.resize(max(sz(updates), sz(T)), (ll)(-1e18));
            
         for(int i = 0; i < sz(T); i++)
            updates[i] = max(T[i] + T.lazy - dp[node].lazy, updates[i]);
      }
      for(int i = 0; i < sz(updates); i++)
         dp[node](i) = max(dp[node](i), updates[i]);
      dp[node].push_front(cost(node) - dp[node].lazy);
      dp[node].lazy += atr(node);
      //cerr << node << ": ";
      //for(int i = 0; i < sz(dp[node]); i++)
         //cerr << dp[node][i] + dp[node].lazy << ' ';
      //cerr << '\n';
      return;
   }
   template<class CB> void propmerge(CB&& atr, vector<int> order) {
      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];
   //for(int i = 1; i <= n; i++) {
      //if(v[i] >= 10000)cerr << i << ' ';
   //}cerr << '\n';
   Tree toleft(n), toright(n);
   
   vector<int> st;
   
   for(int i = 1; i <= n; i++) {
      while(sz(st) && v[st.back()] <= v[i]) { toright.add_edge(st.back(), i); toleft.add_edge(i, st.back()); st.pop_back(); }
      toleft.add_edge(0, i);
      if(sz(st)) toright.add_edge(st.back(), i), toleft.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]) { toleft.add_edge(st.back(), i); toright.add_edge(i, st.back()); st.pop_back(); }
      toright.add_edge(0, i);
      if(sz(st)) toleft.add_edge(st.back(), i), toright.add_edge(i, st.back());
      st.emplace_back(i);
   }
   st.clear();
   
   toleft.calcdp([&](int x) { return x == 0? 0 : spart[x - 1]; }, [&](int x) { return v[x]; }, 0);
   toright.calcdp([&](int x) { return x == 0? 0 : -spart[x]; }, [&](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);
   }
   
   cout << best_cost << '\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:129:19: warning: unused variable 'x' [-Wunused-variable]
  129 |    for(int i = 1, x; i <= n; i++) {
      |                   ^
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; ll = long long int]':
trade.cpp:159:97:   required from here
trade.cpp:92:15: warning: unused variable 'swapped' [-Wunused-variable]
   92 |          bool swapped = 0;
      |               ^~~~~~~
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; ll = long long int]':
trade.cpp:160:95:   required from here
trade.cpp:92:15: warning: unused variable 'swapped' [-Wunused-variable]
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>&; CB2 = main()::<lambda(ll)>; ll = long long int]':
trade.cpp:91:16:   required from 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; ll = long long int]'
trade.cpp:159:97:   required from here
trade.cpp:92:15: warning: unused variable 'swapped' [-Wunused-variable]
trade.cpp: In instantiation of 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>&; CB2 = main()::<lambda(ll)>; ll = long long int]':
trade.cpp:91:16:   required from 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; ll = long long int]'
trade.cpp:160:95:   required from here
trade.cpp:92:15: warning: unused variable 'swapped' [-Wunused-variable]

• Subtask 0: 0 / 0
• Subtask 1: 5 / 10
• Subtask 2: 0 / 10
• Subtask 3: 5 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45