제출 #1055091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055091		Adomas08	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	29 ms	5564 KiB

bridge

        #include <bits/stdc++.h>

        using namespace std;
        int k, n;
        long long curans;
        vector <int> h;
        bool sorting(pair <int, int> a, pair <int, int> b){
        return a.first + a.second < b.first + b.second;
        }
        int findmedian(vector<int> j){
        j.erase(remove(j.begin(), j.end(), -1), j.end());
        sort (j.begin(), j.end());
        if (j.size() == 0) return 0;
        return (j[j.size() / 2] + j[j.size() / 2 - 1]) / 2;
        }
        int main(){
        long long ans = 0, dans = 0;
        int k, n;
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cin >> k >> n;
        int a[n*2];
        vector <int> z;
        vector <pair<int,int>> v;
        char b[n], d[n];
        for (int i = 0; i < n; i++){
            cin >> b[i] >> a[i*2] >> d[i] >> a[i*2+1];
            if (b[i] == d[i]){
                v.push_back({-1, -1});
                z.push_back(-1);
                z.push_back(-1);
            }
            else {
                dans++;
                v.push_back({a[i*2], a[i*2+1]});
                z.push_back(a[i*2]);
                z.push_back(a[i*2+1]);
            }
            if (a[i*2] > a[i*2+1]){
                swap(a[i*2], a[i*2+1]);
            }
            dans += a[i*2+1] - a[i*2];
        }
        int f;
        if (k == 1){
        while (k--){
            f = findmedian(z);
            for (int i = 0; i < n; i++){
                if (f >= a[i*2] && f <= a[i*2+1]){
                    v[i].first = -1;
                    v[i].second = -1;
                }
            }
        }
        for (int i = 0; i < n; i++){
            if (b[i] == d[i]){
                ans += a[i*2+1] - a[i*2];
            }
            else{
                if (v[i].first == -1){
                    ans += a[i*2+1] - a[i*2] + 1;
                }
                else{
                    if (f < a[i*2]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (a[i*2] - f);
                    if (f > a[i*2+1]) ans += 1 + a[i*2+1] - a[i*2] + 2 * (f - a[i*2+1]);
                }
            }
        }
        }
        else{
            ans = LLONG_MAX;
            long long xans;
            int f, g, c;
            sort(v.begin(), v.end(), sorting);
            for (int i = 0; i < n; i++){
                z.push_back(i * 2);
                z.push_back(i * 2 + 1);
            }
            vector <int>start(z.begin(), z.begin() + 2);
            vector <int>ends(z.begin() + 2, z.end());
            for (int N = 1; N <= n; N++){
            h = z;
            curans = dans;
            if (N != 1){
                start.push_back(z[N * 2 - 2]);
                start.push_back(z[N * 2 - 1]);
                ends.erase(ends.begin());
                ends.erase(ends.begin());
            }
            f = findmedian(start);
            g = findmedian(ends);
            for (int i = 0; i < n; i++){
                if ((f >= a[i*2] && f <= a[i*2+1]) || (g >= a[i*2] && g <= a[i*2+1])){
                    h[i*2] = -1;
                    h[i*2+1] = -1;
                }
            }
            for (int i = 0; i < n; i++){
            if (h[i*2] != -1){
                    if (f < a[i*2])  c = 2 * (a[i*2] - f);
                    else c = 2 * (f - a[i*2+1]);
                    if (g < a[i*2]) c = min(2 * (a[i*2] - g), c);
                    else c = min(2 * (g - a[i*2+1]), c);
                    curans += c;
                }
        }

        ans = min(curans, ans);
            }
        }
        cout << ans;
        }

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:72:23: warning: unused variable 'xans' [-Wunused-variable]
   72 |             long long xans;
      |                       ^~~~

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