oj.uz

Submission #1073346

# Submission time Handle Problem Language Result Execution time Memory
1073346 2024-08-24T12:52:02 Z vjudge1 Tricks of the Trade (CEOI23_trade) C++17
10 / 100
 2116 ms 2097152 KB 
#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

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&&, int) [with int persistent = 1; CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>; CB3 = main()::<lambda(int)>; Cine = Persistente::mdeq]':
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&&, int) [with int persistent = 0; CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>; CB3 = main()::<lambda(int)>; Cine = Nepersistente::mdeq]':
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&&, int) [with int persistent = 1; CB = main()::<lambda(int)>&; CB2 = main()::<lambda(int)>&; CB3 = main()::<lambda(int)>&; Cine = Persistente::mdeq]':
trade.cpp:117:28:   required from 'void Tree<Cine>::calcdp(CB&&, CB2&&, CB3&&, int) [with int persistent = 1; CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>; CB3 = main()::<lambda(int)>; Cine = Persistente::mdeq]'
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&&, int) [with int persistent = 0; CB = main()::<lambda(int)>&; CB2 = main()::<lambda(int)>&; CB3 = main()::<lambda(int)>&; Cine = Nepersistente::mdeq]':
trade.cpp:117:28:   required from 'void Tree<Cine>::calcdp(CB&&, CB2&&, CB3&&, int) [with int persistent = 0; CB = main()::<lambda(int)>; CB2 = main()::<lambda(int)>; CB3 = main()::<lambda(int)>; Cine = Nepersistente::mdeq]'
trade.cpp:227:5:   required from here
trade.cpp:118:15: warning: unused variable 'swapped' [-Wunused-variable]

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 52 ms 58964 KB Partially correct
2 Partially correct 35 ms 58964 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 34 ms 58972 KB Partially correct
2 Partially correct 38 ms 58964 KB Partially correct
3 Partially correct 36 ms 59012 KB Partially correct
4 Partially correct 57 ms 75180 KB Partially correct
5 Partially correct 59 ms 80724 KB Partially correct
6 Partially correct 40 ms 59984 KB Partially correct
7 Partially correct 49 ms 68688 KB Partially correct
8 Partially correct 64 ms 73808 KB Partially correct
9 Partially correct 52 ms 70996 KB Partially correct
10 Partially correct 49 ms 66932 KB Partially correct
11 Partially correct 46 ms 67152 KB Partially correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 34 ms 58972 KB Partially correct
2 Partially correct 38 ms 58964 KB Partially correct
3 Partially correct 36 ms 59012 KB Partially correct
4 Partially correct 57 ms 75180 KB Partially correct
5 Partially correct 59 ms 80724 KB Partially correct
6 Partially correct 40 ms 59984 KB Partially correct
7 Partially correct 49 ms 68688 KB Partially correct
8 Partially correct 64 ms 73808 KB Partially correct
9 Partially correct 52 ms 70996 KB Partially correct
10 Partially correct 49 ms 66932 KB Partially correct
11 Partially correct 46 ms 67152 KB Partially correct
12 Partially correct 35 ms 58964 KB Partially correct
13 Partially correct 38 ms 58924 KB Partially correct
14 Partially correct 51 ms 58972 KB Partially correct
15 Partially correct 58 ms 75344 KB Partially correct
16 Partially correct 60 ms 80468 KB Partially correct
17 Partially correct 39 ms 59988 KB Partially correct
18 Partially correct 73 ms 68608 KB Partially correct
19 Partially correct 52 ms 73804 KB Partially correct
20 Partially correct 55 ms 70996 KB Partially correct
21 Partially correct 42 ms 66896 KB Partially correct
22 Partially correct 50 ms 67228 KB Partially correct
23 Runtime error 2116 ms 2097152 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 38 ms 58984 KB Partially correct
2 Partially correct 1325 ms 1011660 KB Partially correct
3 Partially correct 1307 ms 1016936 KB Partially correct
4 Partially correct 1497 ms 1015808 KB Partially correct
5 Partially correct 1449 ms 1015364 KB Partially correct
6 Partially correct 1481 ms 1016064 KB Partially correct
7 Partially correct 1472 ms 1016052 KB Partially correct
8 Partially correct 1417 ms 1016324 KB Partially correct
9 Partially correct 1372 ms 1015336 KB Partially correct
10 Partially correct 1290 ms 1014096 KB Partially correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 38 ms 58984 KB Partially correct
2 Partially correct 1325 ms 1011660 KB Partially correct
3 Partially correct 1307 ms 1016936 KB Partially correct
4 Partially correct 1497 ms 1015808 KB Partially correct
5 Partially correct 1449 ms 1015364 KB Partially correct
6 Partially correct 1481 ms 1016064 KB Partially correct
7 Partially correct 1472 ms 1016052 KB Partially correct
8 Partially correct 1417 ms 1016324 KB Partially correct
9 Partially correct 1372 ms 1015336 KB Partially correct
10 Partially correct 1290 ms 1014096 KB Partially correct
11 Partially correct 53 ms 58920 KB Partially correct
12 Partially correct 1322 ms 1011648 KB Partially correct
13 Partially correct 1227 ms 1016900 KB Partially correct
14 Partially correct 1366 ms 1016016 KB Partially correct
15 Partially correct 1333 ms 1015360 KB Partially correct
16 Partially correct 1195 ms 1016108 KB Partially correct
17 Partially correct 1446 ms 1016148 KB Partially correct
18 Partially correct 1311 ms 1016444 KB Partially correct
19 Partially correct 1297 ms 1015400 KB Partially correct
20 Partially correct 1240 ms 1013980 KB Partially correct
21 Partially correct 35 ms 58972 KB Partially correct
22 Partially correct 38 ms 58972 KB Partially correct
23 Partially correct 51 ms 75404 KB Partially correct
24 Partially correct 56 ms 80468 KB Partially correct
25 Partially correct 50 ms 60080 KB Partially correct
26 Partially correct 46 ms 68756 KB Partially correct
27 Partially correct 55 ms 73812 KB Partially correct
28 Partially correct 55 ms 70992 KB Partially correct
29 Partially correct 45 ms 66896 KB Partially correct
30 Partially correct 58 ms 67152 KB Partially correct
31 Runtime error 1979 ms 2097152 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 52 ms 58964 KB Partially correct
2 Partially correct 35 ms 58964 KB Partially correct
3 Partially correct 34 ms 58972 KB Partially correct
4 Partially correct 38 ms 58964 KB Partially correct
5 Partially correct 36 ms 59012 KB Partially correct
6 Partially correct 57 ms 75180 KB Partially correct
7 Partially correct 59 ms 80724 KB Partially correct
8 Partially correct 40 ms 59984 KB Partially correct
9 Partially correct 49 ms 68688 KB Partially correct
10 Partially correct 64 ms 73808 KB Partially correct
11 Partially correct 52 ms 70996 KB Partially correct
12 Partially correct 49 ms 66932 KB Partially correct
13 Partially correct 46 ms 67152 KB Partially correct
14 Partially correct 35 ms 58964 KB Partially correct
15 Partially correct 38 ms 58924 KB Partially correct
16 Partially correct 51 ms 58972 KB Partially correct
17 Partially correct 58 ms 75344 KB Partially correct
18 Partially correct 60 ms 80468 KB Partially correct
19 Partially correct 39 ms 59988 KB Partially correct
20 Partially correct 73 ms 68608 KB Partially correct
21 Partially correct 52 ms 73804 KB Partially correct
22 Partially correct 55 ms 70996 KB Partially correct
23 Partially correct 42 ms 66896 KB Partially correct
24 Partially correct 50 ms 67228 KB Partially correct
25 Runtime error 2116 ms 2097152 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -