이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
--
*/
컴파일 시 표준 에러 (stderr) 메시지
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;
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |