Submission #249116

#	Time	Username	Problem	Language	Result	Execution time	Memory
249116		fedoseevtimofey	Aliens (IOI16_aliens)	C++14	25 / 100	2075 ms	7040 KiB

aliens

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

#include "aliens.h"

const ll Inf = 1e18;

ll take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
  vector <pair <int, int>> seg;
  for (int i = 0; i < n; ++i) {
    int cr = r[i], cc = c[i];
    if (cc - cr < 0) {
      swap(cr, cc);
    }
   seg.push_back({cr, cc});
  }
  sort(seg.begin(), seg.end(), [&] (pair <int, int> f, pair <int, int> s) {
    if (f.second != s.second) return f.second < s.second;
    else return f.first > s.first;
  });
  {
    vector <pair <int, int>> nseg;
    int mn_l = m;
    for (int i = (int)seg.size() - 1; i >= 0; --i) {
      if (seg[i].first < mn_l) {
        nseg.push_back(seg[i]);
        mn_l = seg[i].first;
      }
    }
    seg = nseg;
    reverse(seg.begin(), seg.end());
  }
  n = seg.size();
  vector <vector <ll>> dp(n + 1, vector <ll> (k + 1, Inf));
  dp[0][0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= k; ++j) {
      for (int p = i - 1; p >= 0; --p) {
        int need_l = seg[p].first;
        int len = seg[i - 1].second - need_l + 1;
        int inter = 0;
        if (p > 0) {
          inter = max(0, seg[p - 1].second - need_l + 1);
        }
        dp[i][j] = min(dp[i][j], dp[p][j - 1] + (ll)len * len - (ll)inter * inter);
      }
    }
  }
  ll ans = Inf;
  for (int j = 0; j <= k; ++j) ans = min(ans, dp[n][j]);
  return ans;
}   

#ifdef LOCAL
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> r(n), c(n);
  for (int i = 0; i < n; i++) {
    cin >> r[i] >> c[i];
  }
  long long ans = take_photos(n, m, k, r, c);
  cout << ans << '\n';  
}
#endif

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