Submission #1145834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145834		ssafarov	Palembang Bridges (APIO15_bridge)	C++20	0 / 100	0 ms	328 KiB

bridge

#define Magic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define en '\n'
#define tsts int tetss; cin >> tetss; while(tetss--)
#define all(a) a.begin() , a.end()
#define pb push_back
#define ld long double
#define fi first
#define se second
ll INF = 1e18;
const int N = 1e6;
const int mod = 998244353;
using namespace std;
using namespace __gnu_pbds;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; 
 
// order_of_key(n) - The number of items in a set that are strictly smaller than k
// find_by_order(k) - It returns an iterator to the ith largest element

// abs((x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3)) / 2 = S



ll lcm(ll a, ll b)
{
  ll gc = __gcd(a, b);
  return   a / gc * b;
}
 
ll binpow (ll a, ll n) {
  if (n == 0)
    return 1;
  if (n % 2 == 1)
    return binpow (a, n-1) * a;
  else {
    ll b = binpow (a, n/2);
    return b * b;
  }
}

 
ll binpow_mod(ll a, ll b, ll md)
{
    ll res = 1;
    a = a % md;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % md;
        a = (a * a) % md;
        b >>= 1;
    }
    return res;
}

ll in() {ll x; cin >> x; return x;};

ll gcd (ll a, ll b, ll & x, ll & y) {
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	ll x1, y1;
	ll d = gcd (b%a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

ll gcdinv(ll a, ll b){
	ll x, y;
	gcd(a, b, x, y);
	return x;
}

// -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- чё

void solve(){
	ll k, n; cin >> k >> n;
	ll ans = 0;
	vector<ll> v;
	for(ll i = 1; i <= n; ++i){
		char a, b;
		ll x, y; cin >> a >> x >> b >> y;
		if(a == b) ans += abs(x - y);
		else{
			ans++;
			v.pb(x);
			v.pb(y);
		}
	}
	sort(all(v));
	ll sz = v.size();
	ll sm1 = 0;
	ll sm2 = 0;
	ll c1 = 0;
	ll c2 = 0;
	for(auto g : v){
		sm1 += g;
		c1++;
	}
	ll tans = INF;
	for(auto g : v){
		sm1 -= g;
		c1--;
		sm2 += g;
		c2++;
		tans = min(tans, (g * c2 - sm2) + (sm1 - g * c1));
	}
	cout << ans + tans;
}

main(){
	Magic
 // freopen ("bomb.in", "r", stdin); freopen("bomb.out", "w", stdout);
	// tsts{
	    solve();
		cout << endl;
	// }
}

Compilation message (stderr)

bridge.cpp:123:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  123 | main(){
      | ^~~~

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