oj.uz

Submission #1073332

# Submission time Handle Problem Language Result Execution time Memory
1073332 2024-08-24T12:38:17 Z vjudge1 Tricks of the Trade (CEOI23_trade) C++17
10 / 100
 2499 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;

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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 51 ms 70736 KB Partially correct
2 Partially correct 44 ms 70736 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 50 ms 70736 KB Partially correct
2 Partially correct 43 ms 70740 KB Partially correct
3 Partially correct 42 ms 70740 KB Partially correct
4 Partially correct 78 ms 103360 KB Partially correct
5 Partially correct 97 ms 113744 KB Partially correct
6 Partially correct 44 ms 72612 KB Partially correct
7 Partially correct 69 ms 90044 KB Partially correct
8 Partially correct 80 ms 100432 KB Partially correct
9 Partially correct 97 ms 94900 KB Partially correct
10 Partially correct 62 ms 86612 KB Partially correct
11 Partially correct 64 ms 87120 KB Partially correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 50 ms 70736 KB Partially correct
2 Partially correct 43 ms 70740 KB Partially correct
3 Partially correct 42 ms 70740 KB Partially correct
4 Partially correct 78 ms 103360 KB Partially correct
5 Partially correct 97 ms 113744 KB Partially correct
6 Partially correct 44 ms 72612 KB Partially correct
7 Partially correct 69 ms 90044 KB Partially correct
8 Partially correct 80 ms 100432 KB Partially correct
9 Partially correct 97 ms 94900 KB Partially correct
10 Partially correct 62 ms 86612 KB Partially correct
11 Partially correct 64 ms 87120 KB Partially correct
12 Partially correct 43 ms 70744 KB Partially correct
13 Partially correct 48 ms 70860 KB Partially correct
14 Partially correct 55 ms 70740 KB Partially correct
15 Partially correct 75 ms 103112 KB Partially correct
16 Partially correct 93 ms 113748 KB Partially correct
17 Partially correct 50 ms 72788 KB Partially correct
18 Partially correct 67 ms 89936 KB Partially correct
19 Partially correct 78 ms 100436 KB Partially correct
20 Partially correct 69 ms 94724 KB Partially correct
21 Partially correct 62 ms 86804 KB Partially correct
22 Partially correct 56 ms 87124 KB Partially correct
23 Runtime error 2004 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 53 ms 70992 KB Partially correct
2 Partially correct 2161 ms 1958796 KB Partially correct
3 Partially correct 2236 ms 1965740 KB Partially correct
4 Partially correct 2418 ms 1963940 KB Partially correct
5 Partially correct 2281 ms 1963136 KB Partially correct
6 Partially correct 2282 ms 1963384 KB Partially correct
7 Partially correct 2424 ms 1965140 KB Partially correct
8 Partially correct 2499 ms 1965516 KB Partially correct
9 Partially correct 2351 ms 1964088 KB Partially correct
10 Partially correct 2214 ms 1961152 KB Partially correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 53 ms 70992 KB Partially correct
2 Partially correct 2161 ms 1958796 KB Partially correct
3 Partially correct 2236 ms 1965740 KB Partially correct
4 Partially correct 2418 ms 1963940 KB Partially correct
5 Partially correct 2281 ms 1963136 KB Partially correct
6 Partially correct 2282 ms 1963384 KB Partially correct
7 Partially correct 2424 ms 1965140 KB Partially correct
8 Partially correct 2499 ms 1965516 KB Partially correct
9 Partially correct 2351 ms 1964088 KB Partially correct
10 Partially correct 2214 ms 1961152 KB Partially correct
11 Partially correct 48 ms 70736 KB Partially correct
12 Partially correct 2297 ms 1958700 KB Partially correct
13 Partially correct 2286 ms 1965856 KB Partially correct
14 Partially correct 2452 ms 1963980 KB Partially correct
15 Partially correct 2351 ms 1963200 KB Partially correct
16 Partially correct 2173 ms 1963576 KB Partially correct
17 Partially correct 2377 ms 1965012 KB Partially correct
18 Partially correct 2171 ms 1965580 KB Partially correct
19 Partially correct 2241 ms 1963928 KB Partially correct
20 Partially correct 2151 ms 1961348 KB Partially correct
21 Partially correct 68 ms 70808 KB Partially correct
22 Partially correct 44 ms 70736 KB Partially correct
23 Partially correct 76 ms 103248 KB Partially correct
24 Partially correct 85 ms 113684 KB Partially correct
25 Partially correct 70 ms 72788 KB Partially correct
26 Partially correct 60 ms 89940 KB Partially correct
27 Partially correct 77 ms 100572 KB Partially correct
28 Partially correct 65 ms 94892 KB Partially correct
29 Partially correct 57 ms 86828 KB Partially correct
30 Partially correct 61 ms 87120 KB Partially correct
31 Runtime error 1916 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 51 ms 70736 KB Partially correct
2 Partially correct 44 ms 70736 KB Partially correct
3 Partially correct 50 ms 70736 KB Partially correct
4 Partially correct 43 ms 70740 KB Partially correct
5 Partially correct 42 ms 70740 KB Partially correct
6 Partially correct 78 ms 103360 KB Partially correct
7 Partially correct 97 ms 113744 KB Partially correct
8 Partially correct 44 ms 72612 KB Partially correct
9 Partially correct 69 ms 90044 KB Partially correct
10 Partially correct 80 ms 100432 KB Partially correct
11 Partially correct 97 ms 94900 KB Partially correct
12 Partially correct 62 ms 86612 KB Partially correct
13 Partially correct 64 ms 87120 KB Partially correct
14 Partially correct 43 ms 70744 KB Partially correct
15 Partially correct 48 ms 70860 KB Partially correct
16 Partially correct 55 ms 70740 KB Partially correct
17 Partially correct 75 ms 103112 KB Partially correct
18 Partially correct 93 ms 113748 KB Partially correct
19 Partially correct 50 ms 72788 KB Partially correct
20 Partially correct 67 ms 89936 KB Partially correct
21 Partially correct 78 ms 100436 KB Partially correct
22 Partially correct 69 ms 94724 KB Partially correct
23 Partially correct 62 ms 86804 KB Partially correct
24 Partially correct 56 ms 87124 KB Partially correct
25 Runtime error 2004 ms 2097152 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -