Submission #763487

#	Time	Username	Problem	Language	Result	Execution time	Memory
763487		doowey	Aliens (IOI16_aliens)	C++14	25 / 100	2063 ms	16936 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

const int N = 4010;
ll dp[N][N];

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

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;
    vector<pii> ff;
    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();
    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)));
            }
        }
        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:32: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]
   32 |     for(int i = 0 ; i < segm.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~~

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