Submission #1224684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224684		maya_s	Aliens (IOI16_aliens)	C++20	0 / 100	0 ms	328 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pair<pll, pll>> ppll;
const ll inf = 1e18;

pll united_loc(pll a, pll b){
    return {min(a.first, b.first), max(a.second, b.second)};
}

ll calc_difference(pll a, pll b){
    ll big_dist = max(a.second, b.second) - min(a.first, b.first), small_dist = min(a.second, b.second) - max(a.first, b.first);
    return big_dist * big_dist - a.second * a.second - b.second * b.second + small_dist * small_dist;
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    ll cnt = 0;
    vector<ll> v(m);
    for(ll i = 0; i < n; i++) v[r[i]] = max(v[r[i]], (ll)abs(r[i] - c[i]) + 1);
    set<pll> s;
    ll ans = 0;
    for(ll i = 0; i < n; i++) s.insert({r[i], v[r[i]]}), ans += v[r[i]] * v[r[i]];
    // cout << ans << "\n";
    while(s.size() > k){
        pll prev = {-1, -1};
        ppll mi = {inf, {{-1, -1}, {-1, -1}}};
        for(pll i : s){
            if(prev.first != -1) mi = min(mi, {calc_difference(prev, i), {prev, i}});
            prev = i;
        }
        auto[x, p] = mi;
        auto[a, b] = p;
        s.erase(a); s.erase(b);
        s.insert(united_loc(a, b));
        ans += x;
        // cout << x << "\n";
    }
    return ans;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40