Submission #712634

#	Time	Username	Problem	Language	Result	Execution time	Memory
712634		minhnhatnoe	Aliens (IOI16_aliens)	C++17	0 / 100	13 ms	316 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(int m, 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));
            int used = dp[j-1].second + 1;
            dp[i] = min(dp[i], make_pair(value + cost, used));
        }
    }
    return dp.back();
}
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]);
    sort(p.begin(), p.end());
    ll bl = 0, br = 1e12;
    while (bl < br){
        ll bm = (bl + br)>>1;
        if (alien_solve(m, p, bm).second > k) bl = bm + 1;
        else br = bm;
    }
    pair<ll, int> result = alien_solve(m, p, bl);
    return result.first - result.second * bl;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, int> alien_solve(int, const std::vector<std::pair<long long int, long long int> >&, ll)':
aliens.cpp:8: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]
    8 |     for (int i=0; i<dp.size(); i++){
      |                   ~^~~~~~~~~~

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