Submission #1267346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267346		_rain_	Radio (Balkan15_RADIO)	C++20	45 / 100	43 ms	5056 KiB

radio

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1) << (x))
#define sz(x) (int)(x).size()
#define TIME_USED cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << "s \n";

template<class T1 , class T2>	
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
	
const int N = (int) 1e5;
const LL inf = (LL) 1e18;
	int n , k;
	int x[N + 2] , p[N + 2] , s[N + 2];
	
namespace subtask1{
	
	bool check(){
		return n <= 15;
	}
	
	//... solveing_
		struct Node{
			int l , r;
			bool operator < (const Node&other) {
				if (l != other.l) return l < other.l;
				return r < other.r;
			}
		};
	
	LL calc(vector<Node>&data){
		sort(data.begin() , data.end());
		LL res = inf;
		vector<int> nen , lef , rig;
		for(int i = 0; i < data.size(); ++i){
			nen.push_back(data[i].l) , nen.push_back(data[i].r);
			lef.push_back(data[i].l) , rig.push_back(data[i].r);
		}
		compress(nen);
		sort(lef.begin() , lef.end());
		sort(rig.begin() , rig.end());
		
		LL sum_lef = 0 , sum_rig = 0;
		LL sl_lef = 0 , sl_rig = 0;
		
		for(int i = 0; i < sz(lef); ++i){
			++sl_lef;
			sum_lef += lef[i];
		}
		
		for(int i = 0 , ptr_lef = 0 , ptr_rig = 0; i < sz(nen); ++i){
			while (ptr_rig < sz(rig) && rig[ptr_rig] < nen[i]){
				sum_rig += rig[ptr_rig];
				++sl_rig;
				++ptr_rig;
			}
			while (ptr_lef < sz(lef) && lef[ptr_lef] < nen[i]){
				sum_lef -= lef[ptr_lef];
				--sl_lef;
				++ptr_lef;
			}
			
			LL cost = sl_rig * nen[i] - sum_rig + sum_lef - sl_lef * nen[i];
			minimize(res , cost);
		}
		return res;
	}
	
	void main_code(){
		LL ans = -inf;
		for(int mask = 0; mask < MASK(n); ++mask){
			vector<Node> v;
			if (__builtin_popcount(mask) != k) continue;
			LL tot = 0;
			for(int i = 0; i < n; ++i){
				if (BIT(mask , i)){
					v.push_back({x[i + 1] - p[i + 1] , x[i + 1] + p[i + 1]});
				}
				else tot += s[i + 1] ;
			}		
			tot -= calc(v);
			maximize(ans , tot);	
		}
		cout << -ans;
	}
	
}

namespace subtask2{
	bool check(){
		return n == k;
	}
	
	//... solveing_
		struct Node{
			int l , r;
			bool operator < (const Node&other) {
				if (l != other.l) return l < other.l;
				return r < other.r;
			}
		};
	
	LL calc(vector<Node>&data){
		sort(data.begin() , data.end());
		LL res = inf;
		vector<int> nen , lef , rig;
		for(int i = 0; i < data.size(); ++i){
			nen.push_back(data[i].l) , nen.push_back(data[i].r);
			lef.push_back(data[i].l) , rig.push_back(data[i].r);
		}
		compress(nen);
		sort(lef.begin() , lef.end());
		sort(rig.begin() , rig.end());
		
		LL sum_lef = 0 , sum_rig = 0;
		LL sl_lef = 0 , sl_rig = 0;
		
		for(int i = 0; i < sz(lef); ++i){
			++sl_lef;
			sum_lef += lef[i];
		}
		
		for(int i = 0 , ptr_lef = 0 , ptr_rig = 0; i < sz(nen); ++i){
			while (ptr_rig < sz(rig) && rig[ptr_rig] < nen[i]){
				sum_rig += rig[ptr_rig];
				++sl_rig;
				++ptr_rig;
			}
			while (ptr_lef < sz(lef) && lef[ptr_lef] < nen[i]){
				sum_lef -= lef[ptr_lef];
				--sl_lef;
				++ptr_lef;
			}
			
			LL cost = sl_rig * nen[i] - sum_rig + sum_lef - sl_lef * nen[i];
			minimize(res , cost);
		}
		return res;
	}
	void main_code(){
		vector<Node> v;
		for(int i = 1; i <= n; ++i) v.push_back({x[i] - p[i] , x[i] + p[i]});
		cout << calc(v) << '\n';
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0)  ; cout.tie(0); 
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".ans","w",stdout);
		}
		
		cin >> n >> k;
		FOR(i , 1 , n) {
			cin >> x[i] >> p[i] >> s[i];
		}
		if (subtask2::check()) return subtask2::main_code() , 0;
		if (subtask1::check()) return subtask1::main_code() , 0;
		assert(false);
	return 0;
}

Compilation message (stderr)

radio.cpp: In function 'int main()':
radio.cpp:170:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
radio.cpp:171:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |                         freopen(name".ans","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 25