oj.uz

Submission #1073345

# Submission time Handle Problem Language Result Execution time Memory
1073345 2024-08-24T12:51:17 Z vjudge1 Tricks of the Trade (CEOI23_trade) C++17
10 / 100
 1984 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&&, 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 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 40 ms 63056 KB Partially correct
2 Partially correct 39 ms 63060 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 40 ms 63056 KB Partially correct
2 Partially correct 41 ms 63068 KB Partially correct
3 Partially correct 39 ms 63064 KB Partially correct
4 Partially correct 52 ms 79284 KB Partially correct
5 Partially correct 59 ms 84564 KB Partially correct
6 Partially correct 49 ms 63824 KB Partially correct
7 Partially correct 52 ms 72788 KB Partially correct
8 Partially correct 54 ms 77908 KB Partially correct
9 Partially correct 49 ms 75088 KB Partially correct
10 Partially correct 50 ms 70996 KB Partially correct
11 Partially correct 52 ms 71072 KB Partially correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 40 ms 63056 KB Partially correct
2 Partially correct 41 ms 63068 KB Partially correct
3 Partially correct 39 ms 63064 KB Partially correct
4 Partially correct 52 ms 79284 KB Partially correct
5 Partially correct 59 ms 84564 KB Partially correct
6 Partially correct 49 ms 63824 KB Partially correct
7 Partially correct 52 ms 72788 KB Partially correct
8 Partially correct 54 ms 77908 KB Partially correct
9 Partially correct 49 ms 75088 KB Partially correct
10 Partially correct 50 ms 70996 KB Partially correct
11 Partially correct 52 ms 71072 KB Partially correct
12 Partially correct 40 ms 63052 KB Partially correct
13 Partially correct 42 ms 63060 KB Partially correct
14 Partially correct 45 ms 63080 KB Partially correct
15 Partially correct 57 ms 79320 KB Partially correct
16 Partially correct 60 ms 84476 KB Partially correct
17 Partially correct 43 ms 63828 KB Partially correct
18 Partially correct 51 ms 72532 KB Partially correct
19 Partially correct 57 ms 77904 KB Partially correct
20 Partially correct 52 ms 75088 KB Partially correct
21 Partially correct 43 ms 70996 KB Partially correct
22 Partially correct 50 ms 71004 KB Partially correct
23 Runtime error 1984 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 63068 KB Partially correct
2 Partially correct 1222 ms 1025284 KB Partially correct
3 Partially correct 1267 ms 1031876 KB Partially correct
4 Partially correct 1310 ms 1030100 KB Partially correct
5 Partially correct 1318 ms 1029048 KB Partially correct
6 Partially correct 1227 ms 1029572 KB Partially correct
7 Partially correct 1421 ms 1031436 KB Partially correct
8 Partially correct 1376 ms 1032592 KB Partially correct
9 Partially correct 1304 ms 1030392 KB Partially correct
10 Partially correct 1337 ms 1027524 KB Partially correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 38 ms 63068 KB Partially correct
2 Partially correct 1222 ms 1025284 KB Partially correct
3 Partially correct 1267 ms 1031876 KB Partially correct
4 Partially correct 1310 ms 1030100 KB Partially correct
5 Partially correct 1318 ms 1029048 KB Partially correct
6 Partially correct 1227 ms 1029572 KB Partially correct
7 Partially correct 1421 ms 1031436 KB Partially correct
8 Partially correct 1376 ms 1032592 KB Partially correct
9 Partially correct 1304 ms 1030392 KB Partially correct
10 Partially correct 1337 ms 1027524 KB Partially correct
11 Partially correct 36 ms 63056 KB Partially correct
12 Partially correct 1277 ms 1025268 KB Partially correct
13 Partially correct 1385 ms 1031900 KB Partially correct
14 Partially correct 1630 ms 1029880 KB Partially correct
15 Partially correct 1383 ms 1028992 KB Partially correct
16 Partially correct 1370 ms 1029572 KB Partially correct
17 Partially correct 1428 ms 1031640 KB Partially correct
18 Partially correct 1328 ms 1031360 KB Partially correct
19 Partially correct 1288 ms 1030340 KB Partially correct
20 Partially correct 1282 ms 1027692 KB Partially correct
21 Partially correct 43 ms 63056 KB Partially correct
22 Partially correct 38 ms 62876 KB Partially correct
23 Partially correct 59 ms 79184 KB Partially correct
24 Partially correct 66 ms 84448 KB Partially correct
25 Partially correct 40 ms 63828 KB Partially correct
26 Partially correct 51 ms 72532 KB Partially correct
27 Partially correct 58 ms 77904 KB Partially correct
28 Partially correct 48 ms 75092 KB Partially correct
29 Partially correct 51 ms 70996 KB Partially correct
30 Partially correct 52 ms 70992 KB Partially correct
31 Runtime error 1951 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 40 ms 63056 KB Partially correct
2 Partially correct 39 ms 63060 KB Partially correct
3 Partially correct 40 ms 63056 KB Partially correct
4 Partially correct 41 ms 63068 KB Partially correct
5 Partially correct 39 ms 63064 KB Partially correct
6 Partially correct 52 ms 79284 KB Partially correct
7 Partially correct 59 ms 84564 KB Partially correct
8 Partially correct 49 ms 63824 KB Partially correct
9 Partially correct 52 ms 72788 KB Partially correct
10 Partially correct 54 ms 77908 KB Partially correct
11 Partially correct 49 ms 75088 KB Partially correct
12 Partially correct 50 ms 70996 KB Partially correct
13 Partially correct 52 ms 71072 KB Partially correct
14 Partially correct 40 ms 63052 KB Partially correct
15 Partially correct 42 ms 63060 KB Partially correct
16 Partially correct 45 ms 63080 KB Partially correct
17 Partially correct 57 ms 79320 KB Partially correct
18 Partially correct 60 ms 84476 KB Partially correct
19 Partially correct 43 ms 63828 KB Partially correct
20 Partially correct 51 ms 72532 KB Partially correct
21 Partially correct 57 ms 77904 KB Partially correct
22 Partially correct 52 ms 75088 KB Partially correct
23 Partially correct 43 ms 70996 KB Partially correct
24 Partially correct 50 ms 71004 KB Partially correct
25 Runtime error 1984 ms 2097152 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -