oj.uz

Submission #1073340

# Submission time Handle Problem Language Result Execution time Memory
1073340 2024-08-24T12:44:15 Z vjudge1 Tricks of the Trade (CEOI23_trade) C++17
10 / 100
 2457 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 41 ms 70736 KB Partially correct
2 Partially correct 41 ms 70740 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 40 ms 70736 KB Partially correct
2 Partially correct 43 ms 70736 KB Partially correct
3 Partially correct 42 ms 70744 KB Partially correct
4 Partially correct 74 ms 103164 KB Partially correct
5 Partially correct 78 ms 113744 KB Partially correct
6 Partially correct 42 ms 72784 KB Partially correct
7 Partially correct 59 ms 89940 KB Partially correct
8 Partially correct 66 ms 100436 KB Partially correct
9 Partially correct 62 ms 94804 KB Partially correct
10 Partially correct 54 ms 86612 KB Partially correct
11 Partially correct 55 ms 87160 KB Partially correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 40 ms 70736 KB Partially correct
2 Partially correct 43 ms 70736 KB Partially correct
3 Partially correct 42 ms 70744 KB Partially correct
4 Partially correct 74 ms 103164 KB Partially correct
5 Partially correct 78 ms 113744 KB Partially correct
6 Partially correct 42 ms 72784 KB Partially correct
7 Partially correct 59 ms 89940 KB Partially correct
8 Partially correct 66 ms 100436 KB Partially correct
9 Partially correct 62 ms 94804 KB Partially correct
10 Partially correct 54 ms 86612 KB Partially correct
11 Partially correct 55 ms 87160 KB Partially correct
12 Partially correct 40 ms 70740 KB Partially correct
13 Partially correct 41 ms 70828 KB Partially correct
14 Partially correct 47 ms 70816 KB Partially correct
15 Partially correct 69 ms 103280 KB Partially correct
16 Partially correct 78 ms 113732 KB Partially correct
17 Partially correct 49 ms 72788 KB Partially correct
18 Partially correct 64 ms 89868 KB Partially correct
19 Partially correct 70 ms 100616 KB Partially correct
20 Partially correct 63 ms 94800 KB Partially correct
21 Partially correct 55 ms 86608 KB Partially correct
22 Partially correct 57 ms 87124 KB Partially correct
23 Runtime error 1940 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 41 ms 70832 KB Partially correct
2 Partially correct 2150 ms 1958848 KB Partially correct
3 Partially correct 2182 ms 1965764 KB Partially correct
4 Partially correct 2352 ms 1963924 KB Partially correct
5 Partially correct 2297 ms 1963204 KB Partially correct
6 Partially correct 2117 ms 1963456 KB Partially correct
7 Partially correct 2317 ms 1965352 KB Partially correct
8 Partially correct 2409 ms 1965512 KB Partially correct
9 Partially correct 2141 ms 1963968 KB Partially correct
10 Partially correct 2222 ms 1961156 KB Partially correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 41 ms 70832 KB Partially correct
2 Partially correct 2150 ms 1958848 KB Partially correct
3 Partially correct 2182 ms 1965764 KB Partially correct
4 Partially correct 2352 ms 1963924 KB Partially correct
5 Partially correct 2297 ms 1963204 KB Partially correct
6 Partially correct 2117 ms 1963456 KB Partially correct
7 Partially correct 2317 ms 1965352 KB Partially correct
8 Partially correct 2409 ms 1965512 KB Partially correct
9 Partially correct 2141 ms 1963968 KB Partially correct
10 Partially correct 2222 ms 1961156 KB Partially correct
11 Partially correct 48 ms 70740 KB Partially correct
12 Partially correct 2143 ms 1958852 KB Partially correct
13 Partially correct 2295 ms 1965728 KB Partially correct
14 Partially correct 2457 ms 1963916 KB Partially correct
15 Partially correct 2378 ms 1962976 KB Partially correct
16 Partially correct 2249 ms 1963464 KB Partially correct
17 Partially correct 2235 ms 1965116 KB Partially correct
18 Partially correct 2354 ms 1965520 KB Partially correct
19 Partially correct 2309 ms 1964036 KB Partially correct
20 Partially correct 2278 ms 1961328 KB Partially correct
21 Partially correct 43 ms 70864 KB Partially correct
22 Partially correct 41 ms 70740 KB Partially correct
23 Partially correct 79 ms 103248 KB Partially correct
24 Partially correct 84 ms 113684 KB Partially correct
25 Partially correct 55 ms 72784 KB Partially correct
26 Partially correct 71 ms 89916 KB Partially correct
27 Partially correct 73 ms 100560 KB Partially correct
28 Partially correct 69 ms 94804 KB Partially correct
29 Partially correct 66 ms 86608 KB Partially correct
30 Partially correct 62 ms 87160 KB Partially correct
31 Runtime error 1934 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 41 ms 70736 KB Partially correct
2 Partially correct 41 ms 70740 KB Partially correct
3 Partially correct 40 ms 70736 KB Partially correct
4 Partially correct 43 ms 70736 KB Partially correct
5 Partially correct 42 ms 70744 KB Partially correct
6 Partially correct 74 ms 103164 KB Partially correct
7 Partially correct 78 ms 113744 KB Partially correct
8 Partially correct 42 ms 72784 KB Partially correct
9 Partially correct 59 ms 89940 KB Partially correct
10 Partially correct 66 ms 100436 KB Partially correct
11 Partially correct 62 ms 94804 KB Partially correct
12 Partially correct 54 ms 86612 KB Partially correct
13 Partially correct 55 ms 87160 KB Partially correct
14 Partially correct 40 ms 70740 KB Partially correct
15 Partially correct 41 ms 70828 KB Partially correct
16 Partially correct 47 ms 70816 KB Partially correct
17 Partially correct 69 ms 103280 KB Partially correct
18 Partially correct 78 ms 113732 KB Partially correct
19 Partially correct 49 ms 72788 KB Partially correct
20 Partially correct 64 ms 89868 KB Partially correct
21 Partially correct 70 ms 100616 KB Partially correct
22 Partially correct 63 ms 94800 KB Partially correct
23 Partially correct 55 ms 86608 KB Partially correct
24 Partially correct 57 ms 87124 KB Partially correct
25 Runtime error 1940 ms 2097152 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -