Submission #720413

#	Time	Username	Problem	Language	Result	Execution time	Memory
720413		joelgun14	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	304 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    int k, n;
    cin >> k >> n;
    if(k == 1) {
        ll base = 0;
        vector<int> a;
        for(int i = 1; i <= n; ++i) {
            char x, y;
            int e, f;
            cin >> x >> e >> y >> f;
            if(x != y)
                a.push_back(e), a.push_back(f);
            else
                base += abs(e - f);
        }
        // k = 1 -> cari sum r suffix dan l prefix
        // pakai prefix sum bisa
        // k = 2 -> cari sum r suffix dan l prefix
        // untuk mid cari l tengah dan r tengah
        // l tengah r tengah -> choose closest
        // semakin tinggi r -> semakin dikit l tengah
        // obs 1: k = 1 -> always choose median?
        // no?
        // karena based on l and r juga
        // median belum tentu optimal karena
        // l l r r 
        // l r l r
        // eh median pasti optimal???
        int med = a.size() / 2;
        if(a.size() == 0)
            cout << base << endl, exit(0);
        ll res = 0;
        for(int i = 0; i < a.size(); ++i) {
            res += abs(a[i] - a[med]);
        }
        cout << res + base << endl;
    }
    // a itu isinya pair
    // bridge: semua yg dikiri lewat bridge semua yg di kanan lewat bridge
    // bridge at index idx
    // k = 1
    // r < idx -> 2 * (idx - r) penalty
    // l > idx -> 2 * (l - idx) penalty
    // coba tiap idx1 hitung r < idx dan l > idx pakai segment tree/bit
    // bridge at index idx1, idx2; idx1 < idx2
    // r < idx1 -> 2 * (idx1 - r) penalty
    // l > idx2 -> 2 * (l - idx2) penalty
    // l <= idx1 and r >= idx1 aman
    // l <= idx2 and r >= idx2 aman
    // l > idx1 and r < idx2
    // penalty -> pilih terkecil antara l - idx1 dan idx2 - r terus kali 2
    // apakah bisa ternary search???
    // teori sum ambil median???
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i = 0; i < a.size(); ++i) {
      |                        ~~^~~~~~~~~~

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