Submission #872784

#	Time	Username	Problem	Language	Result	Execution time	Memory
872784		mat_jur	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	348 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> t(n);
	for (auto &[v, c] : t) cin >> v >> c;
	auto comp = [&](pair<int, int> a, pair<int, int> b) {
		return mp(a.se, a.fi) < mp(b.se, b.fi);
	};
	sort(all(t), comp);
	ll curr = 0;
	REP(i, m) curr+=t[i].fi;
	curr -= 2*(t[m-1].se-t[0].se);
	ll res = curr;

	FOR(i, 1, n-m) {
		curr -= t[i-1].fi;
		curr += t[i+m-1].fi;
		curr += 2*(t[i+m-2].se-t[i-1].se);
		curr -= 2*(t[i+m-1].se-t[i].se);
		res = max(res, curr);
	}
	cout << res << '\n';
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76