| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 208140 | achibasadzishvili | Cake 3 (JOI19_cake3) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
pair<ll,ll>a[200005];
ll n,m,ans=-9999999999999999,mid,ra,kk,pp,raod,sum1,sum2,ff;
bool lst[3000005];
struct node {
vector<int>v,b;
vector<ll>s1,s2;
int num;
node *l,*r;
node() : num(0) , l(NULL) , r(NULL) {}
};
node *root = NULL;
void build(node *&x,int L,int R){
if((int)(x -> v).size() == 1){
lst[x -> num] = 1;
return;
}
mid = (L + R) / 2;
x -> l = new node();
ra++;
x -> l -> num = ra;
x -> r = new node();
ra++;
x -> r -> num = ra;
(*(x -> l)).v.pb(0);(*(x -> r)).v.pb(0);
(*(x -> l)).b.pb(0);(*(x -> r)).b.pb(0);
(*(x -> l)).s1.pb(0);(*(x -> r)).s1.pb(0);
(*(x -> l)).s2.pb(0);(*(x -> r)).s2.pb(0);
kk = (x -> v)[1];pp = 0;raod = 0;
sum1 = 0,sum2 = 0;
for(int i=1; i<(x -> v).size(); i++){
if((x -> v)[i] != kk)pp = 1;
if((x -> v)[i] <= mid){
(x -> l -> v).pb((x -> v)[i]);
sum1 += (x -> v)[i];
raod++;
}
else {
(x -> r -> v).pb((x -> v)[i]);
sum2 += (x -> v)[i];
}
(x -> b).pb(raod);
(x -> s1).pb(sum1);
(x -> s2).pb(sum2);
}
if(pp == 0){lst[(x -> num)] = 1;return;}
build(x -> l, L, mid);
build(x -> r, mid + 1, R);
}
void sum(node *x,int L, int R,int s,int t,int maxraod){
if(x == NULL)return;
if(lst[x -> num] == 1){
if((x -> v).size() == 0)return;
if((x -> v)[1] == 0)return;
ff += maxraod * (x -> v)[1];
return;
}
if(t - s + 1 - ((x -> b)[t] - (x -> b)[s - 1]) >= maxraod){
sum(x -> r,(L + R)/2 + 1,R , s - (x -> b)[s - 1] , t - (x -> b)[t] ,maxraod);
}
else {
ff += (x -> s2)[t] - (x -> s2)[s - 1];
sum(x -> l,L, (L + R) / 2 , (x -> b)[s - 1] + 1 , (x -> b)[t], maxraod - (t - s + 1 - ((x -> b)[t] - (x -> b)[s - 1])));
}
}
void solve(ll l,ll r,ll x,ll y){
l = max(l , x + m - 1);
if(l > r)return;
ll k = (l + r) / 2;
ll mx = -9999999999999999 , ind = y;
st.clear();
ll cur = 0;
for(int i=min(y , k - m + 1); i>=x; i--){
ff = 0;
sum(root , 1 , 1000000000 , i + 1 , k - 1 , m - 2);
cur = ff + a[i].s + a[k].s - 2 * (a[k].f - a[i].f);
if(cur > mx)
mx = cur,
ind = i;
}
if(mx == -9999999999999999)return;
ans = max(ans , mx);
if(l == r)return;
solve(l , k , x , ind);
solve(k + 1 , r , ind , y);
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=1; i<=n; i++){
cin >> a[i].s >> a[i].f;
}
sort(a + 1 , a + n + 1);
root = new node();
(root -> v).pb(0);
(root -> b).pb(0);
(root -> s1).pb(0);
(root -> s2).pb(0);
root->num = 0;
for(int i=1; i<=n; i++){
(root -> v).pb(a[i].s);
}
build(root,1 , 1000000000);
solve(1 , n , 1 , n);
cout << ans << '\n';
return 0;
}