/* AUTHOR: TUAN ANH - BUI */ // ~~ icebear ~~ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef pair<int, ii> iii; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) return x = y, true; return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) return x = y, true; return false; } #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORR(i,a,b) for(int i=(a); i>=(b); --i) #define REP(i, n) for(int i=0; i<(n); ++i) #define RED(i, n) for(int i=(n)-1; i>=0; --i) #define MASK(i) (1LL << (i)) #define BIT(S, i) (((S) >> (i)) & 1) #define mp make_pair #define pb push_back #define fi first #define se second #define all(x) x.begin(), x.end() #define task "icebear" /*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */ const int MOD = 1e9 + 7; const int inf = (int)1e9 + 27092008; const ll INF = (ll)1e18 + 27092008; const int N = 2000 + 5; int numPiece, numChoose; ll best[N]; int compress[N]; struct Piece { int beauty, color, index; bool operator < (const Piece &other) const { return color < other.color; } } piece[N]; struct FenwickTree { int sizeTree; vector<int> cnt; vector<ll> ft; FenwickTree(int n = 0): sizeTree(n), cnt(n + 5, 0), ft(n + 5, 0) {} void update(int x, int val) { for(; x <= sizeTree; x += x & -x) { ft[x] += val; cnt[x] += (val < 0 ? -1 : +1); } } ll walk(int num) { ll sum = 0; int pos = 0, cur = 0; RED(i, 20) { if (pos + MASK(i) <= sizeTree && cur + cnt[pos + MASK(i)] <= num) { pos += MASK(i); sum += ft[pos]; cur += cnt[pos]; } } return sum; } } ft; bool comp(const Piece &X, const Piece &Y) { return X.beauty > Y.beauty; } int L = 1, R = 0; void MO(int l, int r) { while(L > l) --L, ft.update(compress[piece[L].index], piece[L].beauty); while(R < r) ++R, ft.update(compress[piece[R].index], piece[R].beauty); while(L < l) ft.update(compress[piece[L].index], -piece[L].beauty), L++; while(R > r) ft.update(compress[piece[R].index], -piece[R].beauty), R--; } void DnC(int l, int r, int optL, int optR) { if (l > r || optL > optR) return; int mid = (l + r) >> 1; pair<ll, int> opt = mp(-INF, optL); FOR(i, optL, min(mid - numChoose + 1, optR)) { MO(i + 1, mid - 1); maximize(opt, mp(ft.walk(numChoose - 2) + piece[mid].beauty + piece[i].beauty - 2 * piece[mid].color + 2 * piece[i].color, i)); } best[mid] = opt.first; DnC(l, mid - 1, optL, opt.second); DnC(mid + 1, r, opt.second, optR); } void init(void) { cin >> numPiece >> numChoose; FOR(i, 1, numPiece) cin >> piece[i].beauty >> piece[i].color, piece[i].index = i; } void process(void) { sort(piece + 1, piece + numPiece + 1, comp); FOR(i, 1, numPiece) compress[piece[i].index] = i; sort(piece + 1, piece + numPiece + 1); ft = FenwickTree(numPiece); DnC(1, numPiece, 1, numPiece); cout << *max_element(best + 1, best + numPiece + 1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int tc = 1; // cin >> tc; while(tc--) { init(); process(); } return 0; }

cake3.cpp: In function 'int main()':
cake3.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~