Submission #736035

#	Time	Username	Problem	Language	Result	Execution time	Memory
736035		Hydrolyzed	Safety (NOI18_safety)	C++14	0 / 100	124 ms	13648 KiB

safety

/*
 * AUTHOR	: Hydrolyzed~
 * SCHOOL	: RYW
 * TASK		: Safety Subtask 4
 * ALGO		: Dynamic Programming
 * DATE		: 5 May 2023
 * */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#ifndef _DEBUG
// @==== Libary ====@ //

// @================@ //
#endif

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;

// @=== Debugger ===@ //
#ifdef _DEBUG
#include "debug.hpp"
#else
#define dbg(...) 0
#endif
// @================@ //

using ll = long long;

const int MxN = 200020;
ll a[MxN];

struct slope_trick{
	multiset<ll> ms_l, ms_r;
	ll min_y = 0;
	inline void add_line(ll value){
		if(ms_l.upper_bound(value) != ms_l.end()){
			ms_l.emplace(value);
			ms_l.emplace(value);
		}
		else{
			ms_r.emplace(value);
			ms_r.emplace(value);
		}
		ll last = 0, med = 0;
		dbg(ms_l.size(), ms_r.size());
		if(ms_l.size() > ms_r.size()){
			last = *ms_l.end();
			dbg(last);
			ms_l.erase(--ms_l.end());
			ms_r.emplace(last);
			med = *(--ms_l.end());
		}
		else if(ms_r.size() > ms_l.size()){
			last = *ms_r.begin();
			ms_r.erase(ms_r.begin());
			ms_l.emplace(last);
			med = *ms_r.begin();
		}
		dbg(med);
		if(ms_l.size() + ms_r.size() != 2){
			min_y += abs(med - value);
		}
	};
} dp;

inline void solution(){
	int n, h;
	cin >> n >> h;
	assert(h == 0);
	for(int i=1; i<=n; ++i){
		cin >> a[i];
	}
	for(int i=1; i<=n; ++i){
		dp.add_line(a[i]);
		dbg(dp.min_y);
	}
	cout << dp.min_y;
	return ;
}

signed main(){
	cin.tie(nullptr)->ios::sync_with_stdio(false);	
	int q = 1;
//	cin >> q;
	while(q--){
		solution();
		cout << "\n";
	}
	return 0;
}
// https://github.com/MasterIceZ/archive/tree/main/cpp-template

Compilation message (stderr)

safety.cpp: In member function 'void slope_trick::add_line(ll)':
safety.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define dbg(...) 0
      |                  ^
safety.cpp:52:3: note: in expansion of macro 'dbg'
   52 |   dbg(ms_l.size(), ms_r.size());
      |   ^~~
safety.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define dbg(...) 0
      |                  ^
safety.cpp:55:4: note: in expansion of macro 'dbg'
   55 |    dbg(last);
      |    ^~~
safety.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define dbg(...) 0
      |                  ^
safety.cpp:66:3: note: in expansion of macro 'dbg'
   66 |   dbg(med);
      |   ^~~
safety.cpp: In function 'void solution()':
safety.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define dbg(...) 0
      |                  ^
safety.cpp:82:3: note: in expansion of macro 'dbg'
   82 |   dbg(dp.min_y);
      |   ^~~

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 5
• Subtask 5: 0 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29