Submission #763500

#	Time	Username	Problem	Language	Result	Execution time	Memory
763500		doowey	Aliens (IOI16_aliens)	C++14	60 / 100	2102 ms	355476 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

vector<vector<ll>> dp;

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

vector<pii> ff;

ll cost(int k, int i, int j){
    return dp[i - 1][k - 1] + sq(ff[j].se - ff[i].fi + 1) - sq(max(0, ff[i - 1].se - ff[i].fi + 1));
}

void solve(int ki, int cl, int cr, int optl, int optr){
    if(cl > cr) return;
    int mid = (cl + cr) / 2;
    int opt = optl;
    ll cur = (ll)2e18;
    ll chk;
    for(int j = optl; j <= min(mid, optr); j ++ ){
        chk = cost(ki, j, mid);
        if(chk < cur){
            cur = chk;
            opt = j;
        }
    }
    dp[mid][ki] = cur;
    solve(ki, cl, mid - 1, optl, opt);
    solve(ki, mid + 1, cr, opt, optr);
}

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();
    dp.resize(t);
    for(int i = 0 ;i < t; i ++ ){
        dp[i].resize(k + 1);
    }
    for(int i = 0 ; i < t; i ++) {
        for(int j = 0 ; j <= k ; j ++ ){
            dp[i][j]=(ll)1e18;
        }
    }
    dp[0][0]=0;
    ll ans = (ll)1e18;
    for(int j = 1; j <= k ; j ++ ){
        /*
        for(int r = 1; r < t; r ++ ){
            for(int l = r; l > 0; l -- ){
                dp[r][j]=min(dp[r][j], dp[l - 1][j - 1] + sq(ff[r].se - ff[l].fi + 1) - sq(max(0, ff[l - 1].se - ff[l].fi + 1)));
            }
        }
        */
        solve(j, 1, t - 1, 1, t - 1);
        ans = min(ans, dp[t - 1][j]);
    }
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:54: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]
   54 |     for(int i = 0 ; i < segm.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~~

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