Submission #712710

#	Time	Username	Problem	Language	Result	Execution time	Memory
712710		minhnhatnoe	Aliens (IOI16_aliens)	C++14	41 / 100	2096 ms	2644 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll sq(ll a) {return a * a;}
pair<ll, int> alien_solve(const vector<pair<ll, ll>> &p, ll cost){
    vector<pair<ll, int>> dp(p.size());
    for (int i=0; i<dp.size(); i++){
        dp[i] = make_pair(sq(p[i].second - p[0].first + 1) + cost, 1);
        for (int j=1; j<=i; j++){
            ll value = dp[j-1].first + sq(p[i].second - p[j].first + 1) -
                sq(max(0LL, p[j-1].second - p[j].first + 1)) + cost;
            int used = dp[j-1].second + 1;
            dp[i] = min(dp[i], make_pair(value, used));
        }
    }
    return dp.back();
}
vector<pair<ll, ll>> simplify(vector<pair<ll, ll>> &p){
    sort(p.begin(), p.end(), [](const pair<ll, ll> &a, const pair<ll, ll> &b){
        return make_pair(a.first, -a.second) < make_pair(b.first, -b.second);
    });
    vector<pair<ll, ll>> r; r.reserve(p.size());
    for (const pair<ll, ll> &a: p){
        if (r.size() && a.second <= r.back().second) continue;
        r.push_back(a);
    }
    return r;
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
    vector<pair<ll, ll>> p(n);
    for (int i=0; i<n; i++)
        p[i] = minmax(r[i], c[i]);
    p = simplify(p);
    ll bl = 0, br = 1e18;
    while (bl < br){
        ll bm = (bl + br)>>1;
        if (alien_solve(p, bm).second > k) bl = bm + 1;
        else br = bm;
    }
    pair<ll, int> result = alien_solve(p, bl);
    return result.first - k * bl;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, int> alien_solve(const std::vector<std::pair<long long int, long long int> >&, ll)':
aliens.cpp:9:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i=0; i<dp.size(); i++){
      |                   ~^~~~~~~~~~

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