| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 202427 | Rakhmand | Cake 3 (JOI19_cake3) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//
// ROIGold.cpp
// Main calisma
//
// Created by Rakhman on 05/02/2019.
// Copyright © 2019 Rakhman. All rights reserved.
//
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)
const long long MXN = 1e6 + 10;
const long long MNN = 1e6 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e16;
const long long OO = 1e9 + 10;
typedef long long llong;
typedef unsigned long long ullong;
using namespace std;
void istxt(bool yes){
if(yes == 1){
freopen("balancing.in", "r", stdin);
freopen("balancing.out", "w", stdout);
}else{
freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
}
}
llong n, m, answer = -INF;
pair<llong, llong> p[MXN];
vector<llong> c;
llong find_pos(llong x) { return (lower_bound(c.begin(), c.end(), x) - c.begin()); }
struct node{
node *l, *r;
llong cnt;
llong sum;
node(){
l = r = nullptr;
cnt = sum = 0;
}
};
typedef node* pnode;
pnode t[MXN];
llong getcnt(pnode x) {return (x == nullptr ? 0 : x -> cnt); }
llong getsum(pnode x) { return (x == nullptr ? 0 : x -> sum); }
pnode upd(pnode last, llong pos, llong tl = 0, llong tr = c.size() - 1){
pnode cur = new node();
if(tl == tr){
cur -> sum = getsum(last) + c[pos];
cur -> cnt = getcnt(last) + 1;
return cur;
}
llong tm = (tl + tr) / 2;
if(pos <= tm){
cur -> l = new node();
if(last != nullptr){
cur -> l = upd(last -> l, pos, tl, tm);
cur -> r = last -> r;
}else{
cur -> l = upd(nullptr, pos, tl, tm);
cur -> r = nullptr;
}
}else{
cur -> r = new node();
if(last != nullptr){
cur -> l = last -> l;
cur -> r = upd(last -> r, pos, tm + 1, tr);
}else{
cur -> l = nullptr;
cur -> r = upd(nullptr, pos, tm + 1, tr);
}
}
cur -> sum = getsum(cur->l) + getsum(cur->r);
cur -> cnt = getcnt(cur->l) + getcnt(cur->r);
return cur;
}
llong get(pnode v, pnode last, llong k, llong tl = 0, llong tr = c.size() - 1){
if(k == 0) return 0;
if(tl == tr) {
if(v == nullptr) return 0;
llong x = v -> sum / v -> cnt;
return x * k;
}
llong right = 0;
if(v != nullptr) right = getcnt(v -> r);
if(last != nullptr) right -= getcnt(last -> r);
llong tm = (tl + tr) / 2;
if(right < k){
llong sum = 0;
if(v != nullptr) sum += getsum(v -> r);
if(last != nullptr) sum -= getsum(last -> r);
return sum + get((v == nullptr ? nullptr : v -> l), (last == nullptr ? nullptr : last -> l), k - right, tl, tm);
}else{
return get((v == nullptr ? nullptr : v -> r), (last == nullptr ? nullptr : last -> r), k, tm + 1, tr);
}
}
void f(llong L, llong R, llong optl, llong optr){
llong M = (L + R) / 2;
llong ans = -INF, pos = -1;
for(llong i = max(M, optl); i <= optr; i++){
llong kek = get(t[i], t[M - m], m) - 2 * (p[i].F - p[M - m + 1].F);
if(kek > ans){
ans = kek;
pos = i;
}
}
answer = max(ans, answer);
if(M - 1 >= L)
f(L, M - 1, optl, pos);
if(M + 1 <= R)
f(M + 1, R, pos, optr);
}
int main () {
ios;
istxt(0);
cin >> n >> m;
for(llong i = 1; i <= n; i++){
cin >> p[i].S >> p[i].F;
c.push_back(p[i].S);
}
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
sort(p + 1, p + n + 1);
t[0] = new node();
for(llong i = 1; i <= n; i++){
t[i] = upd(t[i - 1], find_pos(p[i].S));
}
f(m, n, m, n);
cout << answer;
}
v