oj.uz

답안 #1073304

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1073304 2024-08-24T12:07:22 Z vjudge1 Tricks of the Trade (CEOI23_trade) C++17
0 / 100
 209 ms 163876 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 Deq {
   vector<T> v;
   void push_front(T x) { v.emplace_back(x); }
   T& operator[](const int& x) { return rbegin(v)[x]; }
   void resize(int k) {
      if(k >= sz(v)) return;
      v.erase(begin(v), begin(v) + sz(v) - k);
      return;
   }
   int size() { return sz(v); }
}; // trebuie facut persistent

struct Tree {
   vector<int> g[nmax];
   int p[nmax];
   void add_edge(int a, int b) {
      g[a].emplace_back(b);
      p[b] = a;
   }
   
   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);
      for(auto &x : dp[node].v) x += atr(node);
      dp[node].lazy = 0;
      merge[node].assign(sz(dp[node]), 0);
      return;
   }
   template<class CB> void propmerge(CB&& atr, vector<int> order) {
      for(auto node : order) {
         for(auto x : g[node]) {
            auto T = dp[x];
            for(int i = 0; i < sz(T) && i + 1 < sz(dp[node]); i++) {
               if(T[i] + T.lazy + atr(node) == dp[node][i + 1] +  dp[node].lazy) {
                  merge[x][i] = merge[x][i] || merge[node][i + 1];
                  //if(x == 66)
                     //cerr << merge[node][i + 1] << ' ' << node << ' ' << i + 1 << " -> " << x << ' ' << i << '\n';
               }
            }
         }
      }
      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]) st.pop_back();
      if(sz(st) == 0) toleft.add_edge(0, i);
      else toleft.add_edge(st.back(), i), toright.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]) st.pop_back();
      if(sz(st) == 0) toright.add_edge(0, i);
      else toright.add_edge(st.back(), i), toleft.add_edge(i, st.back());
      st.emplace_back(i);
   }
   st.clear();
   
   toleft.calcdp([&](int x) { return x == 0? 0 : -spart[x]; }, [&](int x) { return v[x]; }, 0);
   toright.calcdp([&](int x) { return x == 0? 0 : spart[x - 1]; }, [&](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);
   }
   
   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;
         
         if(best_cost == X[i] + Y[j] + X.lazy + Y.lazy - v[P]) {
            if(!swapped)
               toleft.merge[P][i] = 1, toright.merge[P][j] = 1;
            else
               toright.merge[P][i] = 1, toleft.merge[P][j] = 1;
         }  
      }
      if(swapped) swap(X, Y);
   }
   
   vector<int> order(n);
   iota(all(order), 1);
   toleft.propmerge([&](int x) { return v[x]; }, order);
   
   reverse(all(order));
   toright.propmerge([&](int x) { return v[x]; }, order);
   
   cout << best_cost << '\n';
   for(int i = 1; i <= n; i++) {
      bool ok = 0;
      for(auto x : toleft.merge[i]) {
         if(ok) break;
         if(x) { ok = 1; break; }
      }
      for(auto x : toright.merge[i]) {
         if(ok) break;
         if(x) { ok = 1; break; }
      }
      cout << ok;
      //if(!ok)cerr << i << '\n';
   }
   cout << '\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:97:19: warning: unused variable 'x' [-Wunused-variable]
   97 |    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:127:94:   required from here
trade.cpp:56:15: warning: unused variable 'swapped' [-Wunused-variable]
   56 |          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:128:98:   required from here
trade.cpp:56: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:55:16:   required from 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; ll = long long int]'
trade.cpp:127:94:   required from here
trade.cpp:56: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:55:16:   required from 'void Tree::calcdp(CB&&, CB2, ll) [with CB = main()::<lambda(ll)>; CB2 = main()::<lambda(ll)>; ll = long long int]'
trade.cpp:128:98:   required from here
trade.cpp:56:15: warning: unused variable 'swapped' [-Wunused-variable]

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 55128 KB Output is correct
2 Correct 37 ms 55120 KB Output is correct

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 55120 KB Output is correct
2 Correct 36 ms 55124 KB Output is correct
3 Incorrect 31 ms 55216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 55120 KB Output is correct
2 Correct 36 ms 55124 KB Output is correct
3 Incorrect 31 ms 55216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 55120 KB Output is correct
2 Incorrect 209 ms 163876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 55120 KB Output is correct
2 Incorrect 209 ms 163876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 55128 KB Output is correct
2 Correct 37 ms 55120 KB Output is correct
3 Correct 34 ms 55120 KB Output is correct
4 Correct 36 ms 55124 KB Output is correct
5 Incorrect 31 ms 55216 KB Output isn't correct
6 Halted 0 ms 0 KB -