Submission #1248279

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

aliens

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

using ll = long long;

using namespace std;

const int MAXN = 510;

ll dp[MAXN][MAXN], inter[MAXN];

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

  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());

  vector<pair<int, int>> c;

  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[i][0] = 1e9;

  for(int i=1; i<=n; i++){
    for(int k=1; k<=K; k++){

      dp[i][k] = 1e9;

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

    }
  }

  return dp[n][K];

}

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