oj.uz

Submission #720413

# Submission time Handle Problem Language Result Execution time Memory
720413 2023-04-08T08:18:16 Z joelgun14 Palembang Bridges (APIO15_bridge) C++17
0 / 100
 1 ms 304 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -