Submission #427524

#	Time	Username	Problem	Language	Result	Execution time	Memory
427524		InternetPerson10	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	204 KiB

aliens

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

using namespace std;

vector<pair<int, int>> ps;
vector<pair<int, int>> pso;
ll dp[4001][4001];

ll DP(int n, int k) {
    if(dp[n][k] > -1) return dp[n][k];
    ll ans = 99999999999999999;
    if(k == 0) {
        if(n == 0) return dp[n][k] = 0;
        return dp[n][k] = ans;
    }
    ll x = 0;
    for(int i = n-1; i >= k-1; i--) {
        x += (ll)(pso[n].second - pso[i].second) * (pso[i+1].first - pso[i].first);
        ans = min(ans, DP(i, k-1) + x);
    }
    return ans;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    swap(m, n);
    ps.resize(m);
    for(int i = 0; i < m; i++) {
        if(r[i] > c[i]) ps[i] = {c[i], r[i]};
        else ps[i] = {r[i], c[i]};
    }
    sort(ps.begin(), ps.end());
    int best = n+1;
    for(int i = m-1; i >= 0; i--) {
        // cout << ps[i].first << ' ' << ps[i].second << '\n';
        if(i == m-1) pso.push_back({-1, -1});
        if(ps[i].first == pso.back().first) continue;
        if(i == m-1) pso.pop_back();
        if(ps[i].second < best) {
            pso.push_back(ps[i]);
            best = ps[i].second;
        }
    }
    reverse(pso.begin(), pso.end());
    for(int i = 0; i <= pso.size(); i++) {
        for(int j = 0; j <= k; j++) {
            dp[i][j] = -1;
        }
    }
    for(int i = 0; i < pso.size(); i++) cout << pso[i].first << ' ' << pso[i].second << '\n';
    ll ans = max(pso[pso.size()-1].first, pso[pso.size()-1].second) - min(pso[0].first, pso[0].second) + 1;
    ans *= ans;
    return ans - 2 * DP(pso.size() - 1, k-1);
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i <= pso.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
aliens.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < pso.size(); i++) cout << pso[i].first << ' ' << pso[i].second << '\n';
      |                    ~~^~~~~~~~~~~~

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