Submission #566615

#	Time	Username	Problem	Language	Result	Execution time	Memory
566615		ac2hu	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	0 / 100	1 ms	468 KiB

skyscraper

#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n,k;cin >> k >> n;
    assert(k == 1);
    vector<pair<int,int>> loc;
    int same_part = 0;
    for(int i = 0;i<n;i++){
        char c1, c2;
        int a,b;
        cin >> c1 >> a >> c2 >> b;
        if(c1 == c2){
            same_part += abs(a - b);
        }
        else{
            same_part++;
            if(a > b)swap(a, b);
            loc.emplace_back(a, b);
        }
    }
    deb(loc);
    multiset<pair<int,int>> aset, bset;
    for(auto e : loc)aset.insert(e);
    int ans = 1e18;
    int sump1 = 0;
    int sump2 = 0;
    int sump3 = 0;
    int inp2 = 0;
    for(auto e : aset)sump1 += e.first + e.second;
    set<pair<int,int>> extra;
    for(int i = 0;i<=10;i++){
        while(aset.size() > 0){
            auto it = *aset.begin();
            if(i >= it.first){
                bset.insert({it.second, it.first});
                aset.erase(aset.begin());
                sump1 -= it.first + it.second;
                sump3 += abs(it.first - it.second);
            }
            else
                break;
        }
        while(bset.size() > 0){
            auto it = *bset.begin();
            if(i >= it.first){
                bset.erase(bset.begin());
                extra.insert(it);
                sump2 += it.first + it.second;
                sump3 -= abs(it.first - it.second);
                inp2++;
            }
            else break;
        }
        deb(aset, bset, extra);
        int p1 = sump1 - 2*i*aset.size();
        int p2 = inp2*2*i - sump2;
        deb(same_part, p1, p2, sump3);
        ans = min(ans, same_part + (sump1 - 2*i*(int)aset.size()) + (inp2*2*i - sump2) + sump3);
    }
    cout << ans << "\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:63:13: warning: unused variable 'p1' [-Wunused-variable]
   63 |         int p1 = sump1 - 2*i*aset.size();
      |             ^~
skyscraper.cpp:64:13: warning: unused variable 'p2' [-Wunused-variable]
   64 |         int p2 = inp2*2*i - sump2;
      |             ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43