oj.uz

Submission #720417

# Submission time Handle Problem Language Result Execution time Memory
720417 2023-04-08T08:22:44 Z joelgun14 Palembang Bridges (APIO15_bridge) C++17
22 / 100
 36 ms 1920 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    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);
        sort(a.begin(), a.end());
        ll res = 0;
        for(int i = 0; i < a.size(); ++i) {
            res += abs(a[i] - a[med]);
        }
        //cout << a[med] << endl;
        //cout << base << " " << res << " " << a.size() / 2 << endl;
        cout << res + base + a.size() / 2 << 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:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i = 0; i < a.size(); ++i) {
      |                        ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 21 ms 1876 KB Output is correct
13 Correct 36 ms 1852 KB Output is correct
14 Correct 28 ms 1740 KB Output is correct
15 Correct 22 ms 1240 KB Output is correct
16 Correct 28 ms 1756 KB Output is correct
17 Correct 26 ms 1824 KB Output is correct
18 Correct 35 ms 1836 KB Output is correct
19 Correct 36 ms 1788 KB Output is correct
20 Correct 28 ms 1920 KB Output is correct
21 Correct 34 ms 1804 KB Output is correct

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 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -