Submission #202392

#TimeUsernameProblemLanguageResultExecution timeMemory
202392RakhmandCake 3 (JOI19_cake3)C++14
0 / 100
5 ms256 KiB
// // 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(); cur -> cnt = getcnt(last); cur -> sum = getsum(last); if(tl == tr){ cur -> sum += c[pos]; cur -> cnt++; 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); } c.erase(unique(c.begin(), c.end()), c.end()); sort(c.begin(), 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 << nl; }

Compilation message (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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...