oj.uz

답안 #1073329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1073329 2024-08-24T12:34:31 Z vjudge1 Tricks of the Trade (CEOI23_trade) C++17
5 / 100
 2132 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;
      
      
      for(auto x : g[node]) {
         calcdp(cost, atr, x);
         bool swapped = 0;
         
         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]);
      }
      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:122:19: warning: unused variable 'x' [-Wunused-variable]
  122 |    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:152:97:   required from here
trade.cpp:91:15: warning: unused variable 'swapped' [-Wunused-variable]
   91 |          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:153:95:   required from here
trade.cpp:91: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:90:16:   required from 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; ll = long long int]'
trade.cpp:152:97:   required from here
trade.cpp:91: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:90:16:   required from 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; ll = long long int]'
trade.cpp:153:95:   required from here
trade.cpp:91:15: warning: unused variable 'swapped' [-Wunused-variable]

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 45 ms 70908 KB Partially correct
2 Partially correct 53 ms 70864 KB Partially correct

Subtask #1
5.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 40 ms 70712 KB Partially correct
2 Partially correct 40 ms 70740 KB Partially correct
3 Partially correct 43 ms 70740 KB Partially correct
4 Partially correct 97 ms 133088 KB Partially correct
5 Partially correct 119 ms 152148 KB Partially correct
6 Partially correct 49 ms 74416 KB Partially correct
7 Partially correct 99 ms 108120 KB Partially correct
8 Partially correct 94 ms 119888 KB Partially correct
9 Partially correct 84 ms 114744 KB Partially correct
10 Partially correct 74 ms 101456 KB Partially correct
11 Partially correct 81 ms 100948 KB Partially correct

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 40 ms 70712 KB Partially correct
2 Partially correct 40 ms 70740 KB Partially correct
3 Partially correct 43 ms 70740 KB Partially correct
4 Partially correct 97 ms 133088 KB Partially correct
5 Partially correct 119 ms 152148 KB Partially correct
6 Partially correct 49 ms 74416 KB Partially correct
7 Partially correct 99 ms 108120 KB Partially correct
8 Partially correct 94 ms 119888 KB Partially correct
9 Partially correct 84 ms 114744 KB Partially correct
10 Partially correct 74 ms 101456 KB Partially correct
11 Partially correct 81 ms 100948 KB Partially correct
12 Partially correct 44 ms 70736 KB Partially correct
13 Partially correct 42 ms 70740 KB Partially correct
14 Partially correct 41 ms 70920 KB Partially correct
15 Partially correct 96 ms 132992 KB Partially correct
16 Partially correct 129 ms 152140 KB Partially correct
17 Partially correct 48 ms 74332 KB Partially correct
18 Partially correct 75 ms 108112 KB Partially correct
19 Partially correct 86 ms 119888 KB Partially correct
20 Partially correct 89 ms 114620 KB Partially correct
21 Partially correct 83 ms 101644 KB Partially correct
22 Partially correct 70 ms 100948 KB Partially correct
23 Runtime error 2040 ms 2097152 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 45 ms 70736 KB Partially correct
2 Runtime error 2132 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 45 ms 70736 KB Partially correct
2 Runtime error 2132 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 45 ms 70908 KB Partially correct
2 Partially correct 53 ms 70864 KB Partially correct
3 Partially correct 40 ms 70712 KB Partially correct
4 Partially correct 40 ms 70740 KB Partially correct
5 Partially correct 43 ms 70740 KB Partially correct
6 Partially correct 97 ms 133088 KB Partially correct
7 Partially correct 119 ms 152148 KB Partially correct
8 Partially correct 49 ms 74416 KB Partially correct
9 Partially correct 99 ms 108120 KB Partially correct
10 Partially correct 94 ms 119888 KB Partially correct
11 Partially correct 84 ms 114744 KB Partially correct
12 Partially correct 74 ms 101456 KB Partially correct
13 Partially correct 81 ms 100948 KB Partially correct
14 Partially correct 44 ms 70736 KB Partially correct
15 Partially correct 42 ms 70740 KB Partially correct
16 Partially correct 41 ms 70920 KB Partially correct
17 Partially correct 96 ms 132992 KB Partially correct
18 Partially correct 129 ms 152140 KB Partially correct
19 Partially correct 48 ms 74332 KB Partially correct
20 Partially correct 75 ms 108112 KB Partially correct
21 Partially correct 86 ms 119888 KB Partially correct
22 Partially correct 89 ms 114620 KB Partially correct
23 Partially correct 83 ms 101644 KB Partially correct
24 Partially correct 70 ms 100948 KB Partially correct
25 Runtime error 2040 ms 2097152 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -