Submission #767920

#	Time	Username	Problem	Language	Result	Execution time	Memory
767920		doowey	Aliens (IOI16_aliens)	C++17	4 / 100	9 ms	340 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

ll sq(ll x){
    return x * 1ll * x;
}

vector<pii> ff;

const int N = (int)1e5 + 10;
ll dp[N];
ll cnt[N];

ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    vector<pii> segm;
    for(int i = 0 ; i < n; i ++ ){
        segm.push_back(mp(min(r[i],c[i]), max(r[i],c[i])));
    }
    sort(segm.begin(), segm.end(), [&](pii A, pii B){
        if(A.fi == B.fi) return A.se > B.se;
        else return A.fi < B.fi;
    });
    int big = -1;
    ff.push_back(mp(-1,-1));
    for(int i = 0 ; i < segm.size(); i ++ ){
        if(segm[i].se > big){
            ff.push_back(segm[i]);
            big = segm[i].se;
        }
    }
    int t = ff.size();
    ll L = 0;
    ll R = (ll)1e18;
    ll mid;
    ll cost;
    while(L < R){
        mid = (L + R) / 2ll;
        for(int i = 1 ; i < t; i ++ ){
            dp[i] = (ll)1e18;
            cnt[i] = (ll)1e18;
        }
        for(int i = 1; i < t; i ++ ){
            for(int j = 1 ; j <= i ; j ++ ){
                cost = dp[j - 1] + sq(ff[i].se - ff[j].fi + 1) - sq(max(0, ff[j - 1].se - ff[j].fi + 1)) + mid;
                if(cost < dp[i]){
                    dp[i] = cost;
                    cnt[i] = cnt[j - 1] + 1;
                }
                else if(cost == dp[i]){
                    cnt[i] = min(cnt[i], cnt[j - 1] + 1);
                }
                //dp[i]=min(dp[i],dp[j] + sq(ff[i].se - ff[j].fi + 1) - sq(max(0, ff[j - 1].se - ff[j].fi + 1)) + mid);
            }
        }
        if(cnt[t - 1] > k){
            L = mid + 1;
        }
        else{
            R = mid;
        }
    }
    for(int i = 1 ; i < t; i ++ ){
        dp[i] = (ll)1e18;
        cnt[i] = (ll)1e18;
    }
    for(int i = 1; i < t; i ++ ){
        for(int j = 1 ; j <= i ; j ++ ){
            cost = dp[j - 1] + sq(ff[i].se - ff[j].fi + 1) - sq(max(0, ff[j - 1].se - ff[j].fi + 1)) + L;
            if(cost < dp[i]){
                dp[i] = cost;
                cnt[i] = cnt[j - 1] + 1;
            }
            //dp[i]=min(dp[i],dp[j] + sq(ff[i].se - ff[j].fi + 1) - sq(max(0, ff[j - 1].se - ff[j].fi + 1)) + mid);
        }
    }
    return dp[t - 1] - cnt[t - 1] * L;
}

Compilation message (stderr)

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

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