Submission #992708

#	Time	Username	Problem	Language	Result	Execution time	Memory
992708		chanhchuong123	Palembang Bridges (APIO15_bridge)	C++14	78 / 100	165 ms	13580 KiB

bridge

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

const bool multiTest = false;
#define task ""
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)

template<typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) a = b; else return 0; return 1;
}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) a = b; else return 0; return 1;
}

const int MAX = 100010;
int n, k;
long long sumA;
long long sumB;
multiset<int> A;
multiset<int> B;
long long add = 0;
vector<pair<int, int>> info;

void ins(int value) {
    if (A.empty() || value <= (*A.rbegin())) A.insert(value), sumA += value; else B.insert(value), sumB += value;
    if (int(A.size()) - int(B.size()) > 1) {
        int temp = (*A.rbegin());
        A.erase(A.find(temp));
        B.insert(temp);
        sumA -= temp;
        sumB += temp;
    }
    if (int(B.size()) > int(A.size())) {
        int temp = (*B.begin());
        B.erase(B.find(temp));
        A.insert(temp);
        sumB -= temp;
        sumA += temp;
    }
}


void process(void) {
    cin >> k >> n;
    for (int i = 1; i <= n; ++i) {
        char P, Q; int S, T; cin >> P >> S >> Q >> T;
        if (P == Q) add += abs(S - T);
        else info.emplace_back(S, T);
    }

    if (info.empty()) {
        cout << add;
        return;
    }

    if (k == 1) {
        vector<int> value;
        for (pair<int, int> &p: info) {
            value.push_back(p.fi);
            value.push_back(p.se);
        }
        sort(all(value));
        int median = value[value.size() / 2];
        for (int &v: value)
            add += abs(median - v);
        cout << add;
    } else {
        sort(all(info), [](pair<int, int> &u, pair<int, int> &v) {
            return u.fi + u.se < v.fi + v.se;
        });
        vector<long long> f(info.size());
        for (int i = 0; i < info.size(); ++i) {
            ins(info[i].fi);
            ins(info[i].se);
            int median = (*A.rbegin());
            f[i] = 1LL * (A.size()) * median - sumA + sumB - 1LL * (B.size()) * median;
        }

        long long res = add + f[info.size() - 1];
        sumA = 0;
        sumB = 0;
        A.clear();
        B.clear();
        for (int i = info.size() - 1; i > 0; --i) {
            ins(info[i].fi);
            ins(info[i].se);
            int median = (*A.rbegin());
            mini(res, f[i - 1] + 1LL * (A.size()) * median - sumA + sumB - 1LL * (B.size()) * median + add);
        }

        cout << res + (info.size());
    }
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r",  stdin);
		freopen(task".out", "w", stdout);
	}

	int nTest = 1; if (multiTest) cin >> nTest;
	while (nTest--) {
		process();
	}

	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void process()':
bridge.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i = 0; i < info.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~
bridge.cpp: In instantiation of 'bool mini(T1&, T2) [with T1 = long long int; T2 = long long unsigned int]':
bridge.cpp:93:107:   required from here
bridge.cpp:14:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   14 |  if (a > b) a = b; else return 0; return 1;
      |      ~~^~~
bridge.cpp: In function 'int main()':
bridge.cpp:103:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   freopen(task".inp", "r",  stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:104:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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