Submission #1073345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073345		vjudge1	Tricks of the Trade (CEOI23_trade)	C++17	10 / 100	1984 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;

namespace Persistente {
   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 mdeq : Deq<ll> {
      ll lazy = 0;
   };
};

namespace Nepersistente {
   template<typename T>
   struct Deq {
      vector<T> v;
      int ldim = 0;
      void push_front(T x) { v.emplace_back(x); }
      T& operator()(const int& x) { return rbegin(v)[x]; }
      T operator[](const int& x) const { return rbegin(v)[x]; }
      void resize(int k) {
         ldim = max(sz(v) - k, ldim);
         return;
      }
      int size() { return sz(v) - ldim; }
   }; // trebuie facut persistent

   struct mdeq : Deq<ll> {
      ll lazy = 0;
   };
   
}


template<typename Cine>
struct Tree {
   vector<int> g[nmax];
   void add_edge(int a, int b) {
      g[a].emplace_back(b);
   }
   
   
   Cine dp[nmax];
   vector<bool> merge[nmax];
   int calculated[nmax];
   Tree(int n) {
      memset(calculated, 0, sizeof(calculated));
   }
   template<int persistent, class CB, class CB2, class CB3> void calcdp(CB&& cost, CB2&& atr, CB3&& after_convolution, int node) {
      if(calculated[node]) return;
      calculated[node] = 1;
      
      vector<ll> updates;
      
      for(auto x : g[node]) {
         calcdp<persistent>(cost, atr, after_convolution, x);
         bool swapped = 0;
      }
      sort(all(g[node]), [&](int a, int b) { return sz(dp[a]) > sz(dp[b]); });
      for(auto x : g[node]) {
         if(persistent) {
            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]);
         }
         else {
            auto& T = dp[x];
            T.resize(K + 1);
            
            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));
            
         }
      }
      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';
      
      after_convolution(node);
      
      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<Persistente::mdeq> toleft(n);
   Tree<Nepersistente::mdeq> 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();
   
   ll best_cost = -1e18;


   toleft.calcdp<1>([&](int x) { return x == 0? 0 : spart[x - 1]; }, [&](int x) { return v[x]; }, [&](int a) {;}, 0);
   toright.calcdp<0>([&](int x) { return x == 0? 0 : -spart[x]; }, [&](int x) { return v[x]; }, [&](int P) {
      if(P == 0) return;
      auto& X = toleft.dp[P];
      auto& Y = toright.dp[P];
      if(sz(X) > sz(Y)) {      
         for(int j = 0; j < min(K, sz(Y)); j++) {
            int i = K - j - 1;
            if(i >= sz(X)) continue;
            best_cost = max(best_cost, X[i] + Y[j] + X.lazy + Y.lazy - v[P]);
         } 
      }
      else {
         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]);
         } 
      }
   },
   0);

   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:172:19: warning: unused variable 'x' [-Wunused-variable]
  172 |    for(int i = 1, x; i <= n; i++) {
      |                   ^
trade.cpp: In instantiation of 'void Tree<Cine>::calcdp(CB&&, CB2&&, CB3&&, ll) [with long long int persistent = 1; CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; CB3 = main()::<lambda(ll)>; Cine = Persistente::mdeq; ll = long long int]':
trade.cpp:206:116:   required from here
trade.cpp:118:15: warning: unused variable 'swapped' [-Wunused-variable]
  118 |          bool swapped = 0;
      |               ^~~~~~~
trade.cpp: In instantiation of 'void Tree<Cine>::calcdp(CB&&, CB2&&, CB3&&, ll) [with long long int persistent = 0; CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; CB3 = main()::<lambda(ll)>; Cine = Nepersistente::mdeq; ll = long long int]':
trade.cpp:227:5:   required from here
trade.cpp:118:15: warning: unused variable 'swapped' [-Wunused-variable]
trade.cpp: In instantiation of 'void Tree<Cine>::calcdp(CB&&, CB2&&, CB3&&, ll) [with long long int persistent = 1; CB = main()::<lambda(ll)>&; CB2 = main()::<lambda(ll)>&; CB3 = main()::<lambda(ll)>&; Cine = Persistente::mdeq; ll = long long int]':
trade.cpp:117:28:   required from 'void Tree<Cine>::calcdp(CB&&, CB2&&, CB3&&, ll) [with long long int persistent = 1; CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; CB3 = main()::<lambda(ll)>; Cine = Persistente::mdeq; ll = long long int]'
trade.cpp:206:116:   required from here
trade.cpp:118:15: warning: unused variable 'swapped' [-Wunused-variable]
trade.cpp: In instantiation of 'void Tree<Cine>::calcdp(CB&&, CB2&&, CB3&&, ll) [with long long int persistent = 0; CB = main()::<lambda(ll)>&; CB2 = main()::<lambda(ll)>&; CB3 = main()::<lambda(ll)>&; Cine = Nepersistente::mdeq; ll = long long int]':
trade.cpp:117:28:   required from 'void Tree<Cine>::calcdp(CB&&, CB2&&, CB3&&, ll) [with long long int persistent = 0; CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; CB3 = main()::<lambda(ll)>; Cine = Nepersistente::mdeq; ll = long long int]'
trade.cpp:227:5:   required from here
trade.cpp:118: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