Submission #1248569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248569		julia_08	Aliens (IOI16_aliens)	C++20	25 / 100	5 ms	2376 KiB

aliens

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

using ll = long long;

using namespace std;

const int MAXN = 5e4 + 10;
const ll INF = 1e9;

ll inter[MAXN];

vector<vector<ll>> dp;

vector<pair<int, int>> c;

void compute(int k, int l, int r, int opt_min, int opt_max){

  if(l > r) return;

  int m = (l + r) / 2;

  pair<ll, ll> best = {INF, 0};

  for(int j=opt_min; j<=opt_max; j++){
    ll cost = (c[m - 1].second - c[j].first + 1) * (c[m - 1].second - c[j].first + 1);
    best = min(best, {dp[k - 1][j] + cost - inter[j], j});
  }

  dp[k][m] = best.first;

  compute(k, l, m - 1, opt_min, best.second);
  compute(k, m + 1, r, best.second, opt_max);

}

ll take_photos(int n, int m, int K, vector<int> l, vector<int> r){

  dp.resize(K + 1, vector<ll> (n + 1));
  c.clear();

  vector<pair<int, int>> v;

  for(int i=0; i<n; i++){
    if(l[i] > r[i]) swap(l[i], r[i]);
    v.push_back({l[i], r[i]});
  }

  sort(v.begin(), v.end());

  int max_r = -1;

  for(auto [l, r] : v){
    if(max_r < r){

      if(max_r >= l){
        if(!c.empty()){
          inter[c.size()] = (max_r - l + 1) * (max_r - l + 1);
        }
      }

      c.push_back({l, r});

      max_r = r;

    }
  }

  n = c.size();

  dp[0][0] = 0;
 
  for(int i=1; i<=n; i++) dp[0][i] = INF;

  for(int k=1; k<=K; k++) compute(k, 1, n, 0, n - 1);

  return dp[K][n];

}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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