oj.uz

Submission #1073699

# Submission time Handle Problem Language Result Execution time Memory
1073699 2024-08-24T18:33:16 Z cadmiumsky Tricks of the Trade (CEOI23_trade) C++17
50 / 100
 6619 ms 22144 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;

const ll inf = 1e18;

struct KthHeap {
   multiset<int> outside, inside;
   void repair() {
      while(sz(inside) > K) {
         int x = *inside.begin();
         inside.erase(inside.find(x));
         outside.insert(x);
         sum -= x;
      }
      while(sz(inside) < K && sz(outside)) {
         int x = *outside.rbegin();
         outside.erase(outside.find(x));
         inside.insert(x);
         sum += x;
      }
      while(sz(inside) && sz(outside) && *inside.begin() < *outside.rbegin()) {
         int x = *outside.rbegin(), y = *inside.begin();
         outside.erase(outside.find(x));
         inside.erase(inside.find(y));
         outside.emplace(y);
         inside.emplace(x);
         sum += x - y;
      }
      return;
   }
   void erase(int x) {
      if(outside.find(x) != outside.end())
         outside.erase(outside.find(x));
      else if(inside.find(x) != inside.end())
         inside.erase(inside.find(x)), sum -= x;
      else assert(false);
      repair();
   }
   void insert(int x) {
      outside.emplace(x);
      repair();
   }
   ll query() {
      repair();
      if(sz(inside) < K) return -inf;
      return sum;
   }
   
   private:
      ll sum = 0;
};

int bestcut[nmax];
ll dp[nmax];

ll spart[nmax];
ll v[nmax];

ll S(int l, int r) { return spart[r] - spart[l - 1]; }

namespace Divide {
   KthHeap hint;
   
   //void brut(int p)  {
      //vector<int> pul;
      //int best = -inf, atr = p -1;
      //for(int i = p; i <= 200; i++) {
         //pul.emplace_back(v[i]);
         //if(sz(pul) < K) continue;
         //sort(all(pul), greater<int>());
         
         //if(accumulate(all(pul), 0ll) - S(p, i) > best) tie(best, atr) = make_pair(accumulate(all(pul), 0ll) - S(p, i), i);
      //}
      //if(bestcut[p] != atr)
         //cerr << "COAIE\nCOAIE\nCOAIE\nCOAIE\nCOAIE\nCOAIE\n";
      //cerr << p << ' ' << atr << '\n';
   //}
   
   void divide(int l, int r) {
      if(l + 1 == r) return;
      int optl = bestcut[l], optr = bestcut[r];
      
      //cerr << r << ' ' << optl << '\t' << sz(hint.inside) + sz(hint.outside) << '\n';
      
      int mid = l + r >> 1;
      if(r <= optl) {
         for(int i = mid; i < r; i++) hint.insert(v[i]);
         ll best = hint.query() - S(mid, optl);
         int atr = optl;
         for(int i = optl + 1; i <= optr; i++) {
            hint.insert(v[i]);
            if(hint.query() - S(mid, i) > best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i);
         }
         bestcut[mid] = atr, dp[mid] = best;
         //cerr << mid << ' ' << best << ' ' << atr << '\t' << l << ' ' << r << " -- " << optl << ' ' << optr << '\t' << sz(hint.inside) + sz(hint.outside) << "\n\t";;
         //brut(mid); 
         //cerr << '\n';
         if(atr - mid + 1 == K) {
            int SA = S(mid, atr), SB = 0;
            for(int i = mid; i <= atr; i++) SB += v[i];
            //cout << "\t" << SB << ' ' << SA << '\t' << SB - SA<< '\n';
         }
         
         for(int i = optl + 1; i <= optr; i++) hint.erase(v[i]);
         divide(l, mid);
         for(int i = mid; i < r; i++) hint.erase(v[i]);
         for(int i = optl + 1; i <= atr; i++) hint.insert(v[i]);
         divide(mid, r);
         for(int i = optl + 1; i <= atr; i++) hint.erase(v[i]);
      }
      else {
         int border = max(mid - 1, optl);
         for(int i = mid; i <= border; i++) hint.insert(v[i]);
         ll best = hint.query() - S(mid, border), atr = border;
         for(int i = border + 1; i <= optr; i++) {
            hint.insert(v[i]);
            if(hint.query() - S(mid, i) > best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i);
         }
         
         assert(atr - mid + 1 >= K);
         //cerr << mid << ' ' << best << ' ' << atr << '\n';
         //if(atr - mid + 1 == K) {
            //int SA = S(mid, atr), SB = 0;
            //for(int i = mid; i <= atr; i++) SB += v[i];
            //cout << "\t" << SB << ' ' << SA << '\t' << SB - SA<< '\n';
         //}
         
         bestcut[mid] = atr, dp[mid] = best;
         
         for(int i = optr; i > border; i--) hint.erase(v[i]);
         divide(l, mid);
         for(int i = mid; i <= border; i++) hint.erase(v[i]);
         for(int i = r; i <= atr; i++) hint.insert(v[i]);
         //cerr << '\t' << r << ' ' << atr << ' ' << sz(hint.inside) << '\n';
         divide(mid, r);
         for(int i = r; i <= atr; i++) hint.erase(v[i]);
      }
   }
   
}


signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n >> K;
   for(int i = 1; i <= n; i++) {
      cin >> spart[i];
      spart[i] += spart[i - 1];
   }
   for(int i = 1; i <= n; i++)
      cin >> v[i];
      
   bestcut[0] = 0;
   bestcut[n - K + 2] = n;
   Divide::divide(0, n - K + 2);
   ll mn = -inf;
   for(int i = 1; i <= n - K + 1; i++) 
      mn = max(mn, dp[i]);

   cout << mn << '\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 'void Divide::divide(ll, ll)':
trade.cpp:99:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |       int mid = l + r >> 1;
      |                 ~~^~~
trade.cpp:113:17: warning: unused variable 'SA' [-Wunused-variable]
  113 |             int SA = S(mid, atr), SB = 0;
      |                 ^~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 KB Partially correct
2 Partially correct 1 ms 4444 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4444 KB Partially correct
2 Partially correct 0 ms 2396 KB Partially correct
3 Partially correct 1 ms 4444 KB Partially correct
4 Partially correct 1 ms 4444 KB Partially correct
5 Partially correct 1 ms 4444 KB Partially correct
6 Partially correct 1 ms 4564 KB Partially correct
7 Partially correct 1 ms 4696 KB Partially correct
8 Partially correct 1 ms 2396 KB Partially correct
9 Partially correct 2 ms 4444 KB Partially correct
10 Partially correct 1 ms 2396 KB Partially correct
11 Partially correct 1 ms 4444 KB Partially correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4444 KB Partially correct
2 Partially correct 0 ms 2396 KB Partially correct
3 Partially correct 1 ms 4444 KB Partially correct
4 Partially correct 1 ms 4444 KB Partially correct
5 Partially correct 1 ms 4444 KB Partially correct
6 Partially correct 1 ms 4564 KB Partially correct
7 Partially correct 1 ms 4696 KB Partially correct
8 Partially correct 1 ms 2396 KB Partially correct
9 Partially correct 2 ms 4444 KB Partially correct
10 Partially correct 1 ms 2396 KB Partially correct
11 Partially correct 1 ms 4444 KB Partially correct
12 Partially correct 1 ms 2396 KB Partially correct
13 Partially correct 1 ms 4444 KB Partially correct
14 Partially correct 1 ms 4444 KB Partially correct
15 Partially correct 1 ms 4444 KB Partially correct
16 Partially correct 1 ms 4444 KB Partially correct
17 Partially correct 1 ms 4444 KB Partially correct
18 Partially correct 1 ms 4440 KB Partially correct
19 Partially correct 1 ms 2648 KB Partially correct
20 Partially correct 1 ms 2396 KB Partially correct
21 Partially correct 1 ms 4444 KB Partially correct
22 Partially correct 1 ms 4444 KB Partially correct
23 Partially correct 4 ms 2780 KB Partially correct
24 Partially correct 20 ms 2856 KB Partially correct
25 Partially correct 51 ms 4920 KB Partially correct
26 Partially correct 37 ms 4904 KB Partially correct
27 Partially correct 24 ms 2820 KB Partially correct
28 Partially correct 7 ms 2852 KB Partially correct
29 Partially correct 46 ms 4884 KB Partially correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2396 KB Partially correct
2 Partially correct 329 ms 13940 KB Partially correct
3 Partially correct 511 ms 17232 KB Partially correct
4 Partially correct 1563 ms 20052 KB Partially correct
5 Partially correct 1647 ms 17024 KB Partially correct
6 Partially correct 960 ms 16600 KB Partially correct
7 Partially correct 3950 ms 22012 KB Partially correct
8 Partially correct 553 ms 16972 KB Partially correct
9 Partially correct 500 ms 15468 KB Partially correct
10 Partially correct 460 ms 16180 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 2396 KB Partially correct
2 Partially correct 329 ms 13940 KB Partially correct
3 Partially correct 511 ms 17232 KB Partially correct
4 Partially correct 1563 ms 20052 KB Partially correct
5 Partially correct 1647 ms 17024 KB Partially correct
6 Partially correct 960 ms 16600 KB Partially correct
7 Partially correct 3950 ms 22012 KB Partially correct
8 Partially correct 553 ms 16972 KB Partially correct
9 Partially correct 500 ms 15468 KB Partially correct
10 Partially correct 460 ms 16180 KB Partially correct
11 Partially correct 1 ms 4440 KB Partially correct
12 Partially correct 321 ms 15068 KB Partially correct
13 Partially correct 511 ms 17088 KB Partially correct
14 Partially correct 1576 ms 20052 KB Partially correct
15 Partially correct 1568 ms 16908 KB Partially correct
16 Partially correct 1018 ms 16744 KB Partially correct
17 Partially correct 3999 ms 22144 KB Partially correct
18 Partially correct 611 ms 16968 KB Partially correct
19 Partially correct 537 ms 15528 KB Partially correct
20 Partially correct 483 ms 16092 KB Partially correct
21 Partially correct 0 ms 2396 KB Partially correct
22 Partially correct 1 ms 4444 KB Partially correct
23 Partially correct 1 ms 4440 KB Partially correct
24 Partially correct 1 ms 4444 KB Partially correct
25 Partially correct 1 ms 2392 KB Partially correct
26 Partially correct 1 ms 2396 KB Partially correct
27 Partially correct 1 ms 2396 KB Partially correct
28 Partially correct 1 ms 4444 KB Partially correct
29 Partially correct 1 ms 2396 KB Partially correct
30 Partially correct 1 ms 4560 KB Partially correct
31 Partially correct 1348 ms 17108 KB Partially correct
32 Partially correct 1525 ms 16988 KB Partially correct
33 Partially correct 2863 ms 19544 KB Partially correct
34 Partially correct 2345 ms 16512 KB Partially correct
35 Partially correct 1836 ms 16172 KB Partially correct
36 Partially correct 4959 ms 21324 KB Partially correct
37 Partially correct 989 ms 14928 KB Partially correct

Subtask #5
25.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 4440 KB Partially correct
2 Partially correct 1 ms 4444 KB Partially correct
3 Partially correct 1 ms 4444 KB Partially correct
4 Partially correct 0 ms 2396 KB Partially correct
5 Partially correct 1 ms 4444 KB Partially correct
6 Partially correct 1 ms 4444 KB Partially correct
7 Partially correct 1 ms 4444 KB Partially correct
8 Partially correct 1 ms 4564 KB Partially correct
9 Partially correct 1 ms 4696 KB Partially correct
10 Partially correct 1 ms 2396 KB Partially correct
11 Partially correct 2 ms 4444 KB Partially correct
12 Partially correct 1 ms 2396 KB Partially correct
13 Partially correct 1 ms 4444 KB Partially correct
14 Partially correct 1 ms 2396 KB Partially correct
15 Partially correct 1 ms 4444 KB Partially correct
16 Partially correct 1 ms 4444 KB Partially correct
17 Partially correct 1 ms 4444 KB Partially correct
18 Partially correct 1 ms 4444 KB Partially correct
19 Partially correct 1 ms 4444 KB Partially correct
20 Partially correct 1 ms 4440 KB Partially correct
21 Partially correct 1 ms 2648 KB Partially correct
22 Partially correct 1 ms 2396 KB Partially correct
23 Partially correct 1 ms 4444 KB Partially correct
24 Partially correct 1 ms 4444 KB Partially correct
25 Partially correct 4 ms 2780 KB Partially correct
26 Partially correct 20 ms 2856 KB Partially correct
27 Partially correct 51 ms 4920 KB Partially correct
28 Partially correct 37 ms 4904 KB Partially correct
29 Partially correct 24 ms 2820 KB Partially correct
30 Partially correct 7 ms 2852 KB Partially correct
31 Partially correct 46 ms 4884 KB Partially correct
32 Partially correct 1 ms 2396 KB Partially correct
33 Partially correct 329 ms 13940 KB Partially correct
34 Partially correct 511 ms 17232 KB Partially correct
35 Partially correct 1563 ms 20052 KB Partially correct
36 Partially correct 1647 ms 17024 KB Partially correct
37 Partially correct 960 ms 16600 KB Partially correct
38 Partially correct 3950 ms 22012 KB Partially correct
39 Partially correct 553 ms 16972 KB Partially correct
40 Partially correct 500 ms 15468 KB Partially correct
41 Partially correct 460 ms 16180 KB Partially correct
42 Partially correct 1 ms 4440 KB Partially correct
43 Partially correct 321 ms 15068 KB Partially correct
44 Partially correct 511 ms 17088 KB Partially correct
45 Partially correct 1576 ms 20052 KB Partially correct
46 Partially correct 1568 ms 16908 KB Partially correct
47 Partially correct 1018 ms 16744 KB Partially correct
48 Partially correct 3999 ms 22144 KB Partially correct
49 Partially correct 611 ms 16968 KB Partially correct
50 Partially correct 537 ms 15528 KB Partially correct
51 Partially correct 483 ms 16092 KB Partially correct
52 Partially correct 0 ms 2396 KB Partially correct
53 Partially correct 1 ms 4444 KB Partially correct
54 Partially correct 1 ms 4440 KB Partially correct
55 Partially correct 1 ms 4444 KB Partially correct
56 Partially correct 1 ms 2392 KB Partially correct
57 Partially correct 1 ms 2396 KB Partially correct
58 Partially correct 1 ms 2396 KB Partially correct
59 Partially correct 1 ms 4444 KB Partially correct
60 Partially correct 1 ms 2396 KB Partially correct
61 Partially correct 1 ms 4560 KB Partially correct
62 Partially correct 1348 ms 17108 KB Partially correct
63 Partially correct 1525 ms 16988 KB Partially correct
64 Partially correct 2863 ms 19544 KB Partially correct
65 Partially correct 2345 ms 16512 KB Partially correct
66 Partially correct 1836 ms 16172 KB Partially correct
67 Partially correct 4959 ms 21324 KB Partially correct
68 Partially correct 989 ms 14928 KB Partially correct
69 Partially correct 1 ms 4444 KB Partially correct
70 Partially correct 319 ms 14932 KB Partially correct
71 Partially correct 504 ms 17032 KB Partially correct
72 Partially correct 1586 ms 19932 KB Partially correct
73 Partially correct 1559 ms 17044 KB Partially correct
74 Partially correct 997 ms 16604 KB Partially correct
75 Partially correct 3903 ms 22096 KB Partially correct
76 Partially correct 612 ms 16976 KB Partially correct
77 Partially correct 504 ms 15536 KB Partially correct
78 Partially correct 491 ms 16160 KB Partially correct
79 Partially correct 1 ms 2392 KB Partially correct
80 Partially correct 1 ms 4444 KB Partially correct
81 Partially correct 1 ms 4444 KB Partially correct
82 Partially correct 1 ms 4444 KB Partially correct
83 Partially correct 1 ms 2396 KB Partially correct
84 Partially correct 1 ms 2396 KB Partially correct
85 Partially correct 1 ms 2520 KB Partially correct
86 Partially correct 1 ms 2396 KB Partially correct
87 Partially correct 1 ms 4444 KB Partially correct
88 Partially correct 1 ms 2396 KB Partially correct
89 Partially correct 1326 ms 17228 KB Partially correct
90 Partially correct 1551 ms 17068 KB Partially correct
91 Partially correct 2781 ms 19620 KB Partially correct
92 Partially correct 2276 ms 16324 KB Partially correct
93 Partially correct 1822 ms 16212 KB Partially correct
94 Partially correct 4884 ms 21184 KB Partially correct
95 Partially correct 930 ms 14920 KB Partially correct
96 Partially correct 4 ms 4952 KB Partially correct
97 Partially correct 24 ms 4844 KB Partially correct
98 Partially correct 46 ms 4916 KB Partially correct
99 Partially correct 38 ms 4696 KB Partially correct
100 Partially correct 24 ms 4700 KB Partially correct
101 Partially correct 8 ms 4700 KB Partially correct
102 Partially correct 47 ms 4956 KB Partially correct
103 Partially correct 5422 ms 19912 KB Partially correct
104 Partially correct 2282 ms 16452 KB Partially correct
105 Partially correct 2596 ms 16392 KB Partially correct
106 Partially correct 4138 ms 17940 KB Partially correct
107 Partially correct 4814 ms 18784 KB Partially correct
108 Partially correct 6619 ms 17308 KB Partially correct
109 Partially correct 2347 ms 15952 KB Partially correct
110 Partially correct 4831 ms 20072 KB Partially correct
111 Partially correct 1506 ms 18512 KB Partially correct
112 Partially correct 2238 ms 17748 KB Partially correct