Submission #483170

#	Time	Username	Problem	Language	Result	Execution time	Memory
483170		TranGiaHuy1508	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	204 KiB

cake3

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")


// C++ Template

#include "bits/stdc++.h"
using namespace std;

// Type
typedef long long ll;
typedef long double ld;

// Pair/Vector
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

// Macro
#define stat(x) x && cout << "YES\n" || cout << "NO\n";
#ifdef LOCAL
    #define debug(x) cout << #x << " = " << x << "\n";
#else
    #define debug(x) ;
#endif

// Custom output
template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x){
    out << "(" << x.first << ", " << x.second << ")";
    return out;
}

template <class T>
ostream& operator << (ostream& out, vector<T> x){
    out << "[";
    for (int i=0; i<x.size(); i++){
        if (i) out << ", ";
        out << x[i];
    }
    out << "]";
    return out;
}

void fastio(string finp = "", string fout = ""){
    if (fopen(finp.c_str(), "r")){
        freopen(finp.c_str(), "r", stdin);
        freopen(fout.c_str(), "w", stdout);
    }
}

// Const
const int interactive = 0;
const ld PI = acos(-1.0);
const ll allmod[2] = {int(1e9)+7, 998244353};
const ll mod = allmod[0];
const ll maxn = 2e5;
const ll inf = 1e18;
const int multitest = 0;

#define int long long

vi x, y, v, c;
vii tmp;

typedef priority_queue<int, vi, greater<int>> pq;

int cp(ii a, ii b){
	return a.second < b.second;
}

void main_program(){
    int n, m; cin >> n >> m;
    v.assign(n, 0);
    c.assign(n, 0);
    tmp.assign(n, ii());

    for (int i=0; i<n; i++) cin >> tmp[i].first >> tmp[i].second;

    sort(tmp.begin(), tmp.end(), cp);

	debug(tmp);

	for (int i=0; i<n; i++){
		v[i] = tmp[i].first;
		c[i] = tmp[i].second;
	}

    x.assign(n, 0);
	for (int i=0; i<n; i++) x[i] = v[i] + 2*c[i];

	// y.assign(n, 0);
	// int s = 0;
	// for (int i=0; i<m-1; i++){
	// 	s += v[i];
	// 	pq.push(v[i]);
	// }
	// debug(s);
	int res = 0;
	for (int i=m-1; i<n; i++){
		pq crr;
		int s = 0;
		for (int j=i-1; j>=i-m+2; j--){
			crr.push(v[j]);
			s += v[j];
		}
		debug(s);
		for (int j=i-m+1; j>=0; j--){
			res = max(res, v[i] + v[j] + s - 2*c[i] + 2*c[j]);
			s += v[j]; crr.push(v[j]);
			int k = crr.top(); s -= k; crr.pop();
		}
	}
	cout << res;
}

void pre_main(){
    
}

signed main(){

    #ifdef LOCAL
        auto start_time = chrono::high_resolution_clock::now();
    #endif

    if (!interactive) {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}
    #ifndef ONLINE_JUDGE
        fastio(".inp", ".out");
    #endif

    int t = 1;
    if (multitest) cin >> t;
    pre_main();
    while (t--) main_program();

    #ifdef LOCAL
        auto end_time = chrono::high_resolution_clock::now();
        double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
        cout << "\n[" << duration << "ms]\n";
    #endif
}

Compilation message (stderr)

cake3.cpp: In function 'void fastio(std::string, std::string)':
cake3.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(finp.c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(fout.c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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