제출 #682982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682982		bane	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	233 ms	13640 KiB

bridge

#include<iostream>
#include<set>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
           
using ll = long long;
using db = long double;
using llu = unsigned long long;
using str = string;
           
// pairs
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdb = pair<db,db>;
#define mp make_pair
#define fr first
#define sc second
           
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>; 
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pii>;
using vpl = V<pll>;
using vpd = V<pdb>;
#define ms0(x) memset(x , 0, sizeof(x))
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sor(x) sort(all(x)) 
#define rsz resize
#define ins insert 
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()
           
#define lb lower_bound
#define ub upper_bound
tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
tcT> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }
           
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
           
const int MOD = (int)2019201949; // 998244353;
const int MX = (int)2e5+5;
const ll BIG = 1e18; 
const db PI = acos((db)-1);
using ld = long double;
const int dx[4] = {0,1,0,-1};
const int dy[4] = {-1,0,1,0};
 
void setIO(string name = "") {
    cin.tie(0)->sync_with_stdio(0); 
    if (sz(name)) {
        freopen((name + ".in").c_str(), "r", stdin); 
        freopen((name + ".out").c_str(), "w", stdout);
    }
}
multiset<int>lower, upper;
int n, k; 
long long lmas = 0, rmas = 0;
void insertion(int val){
    int a = (lower.empty() ? 1000000000 : *lower.rbegin());
    if (val <= a){
		lower.insert(val);
		lmas+=val;
	}else{
		upper.insert(val);
		rmas+=val;
	}
	
	if (upper.size() + 1 < lower.size()){
		upper.insert(*lower.rbegin());
		lmas-=*lower.rbegin();
		rmas+=*lower.rbegin();
		lower.erase(lower.find(*lower.rbegin()));
	}else if (upper.size() > lower.size()){
		lower.insert(*upper.begin());
		lmas+=*upper.begin();
		rmas-=*upper.begin();
		upper.erase(upper.find(*upper.begin()));
		
	}
}
void solve(){
	cin >> k >> n;
	
	ll prefix[n + 10];
	vector<pii>p;
	ll ans = 0;
	ll dummy = 0;
	for (int i = 0; i < n; i++){
		char a,b;
		int c,d;
		cin >> a >> c >> b >> d;
		if (a == b)dummy+=abs(c - d);
		else p.pb(mp(c, d));
	}
	if (p.size() == 0){
		cout<<dummy<<endl;
		return ;
	}
	sort(p.begin(), p.end(), [](auto &x, auto &y){
		return (x.fr + x.sc < y.fr + y.sc);
	});
	n = (int)p.size();
	dummy+= p.size();
	//memset(prefix, 0, sizeof(prefix));
	for (int i = 0; i < n; i++){
		insertion(p[i].fr);
		insertion(p[i].sc);
		prefix[i] = rmas - lmas;
	}
	ans+=prefix[n - 1];    
	if (k == 2){
		while(!lower.empty())lower.erase(lower.find(*lower.begin()));
		while(!upper.empty())upper.erase(upper.find(*upper.begin()));
		rmas = 0, lmas = 0;
		for (int i = n-1; i > 0; i--){
			insertion(p[i].fr);
			insertion(p[i].sc);
			ans = min(ans, prefix[i - 1] + rmas - lmas);
		}
	}
	cout<<ans + dummy;
	
}
 
int main() {
    setIO("");
///  freopen("input.txt", "r", stdin);
///  freopen("output.txt", "w", stdout);
    solve();
    return 0;   
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'void setIO(std::string)':
bridge.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37