이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//
// 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 = 2e5 + 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;
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) return getsum(v) - getsum(last);
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);
}
}
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));
}
llong ans = -INF;
for(llong i = 1; i <= n; i++){
for(llong j = i + m - 1; j <= n; j++){
ans = max(ans, get(t[j], t[i - 1], m) - 2 * (p[j].F - p[i].F));
}
}
cout << ans;
}
컴파일 시 표준 에러 (stderr) 메시지
cake3.cpp: In function 'void istxt(bool)':
cake3.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("balancing.in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("balancing.out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |