| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1211815 | sano | Aliens (IOI16_aliens) | C++20 | 0 ms | 0 KiB |
//#include "aliens.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
long long take_photos_rychle(int n, int m, int k, vector<int> r, vector<int> c) {
//zapnime kompresiu suradnic
set<int> sc;
For(i, n) {
if (r[i] > c[i]) swap(r[i], c[i]);
sc.insert(c[i]);
}
unordered_map<int, int> umap;
vec<int> comp;
sc.insert(0);
int poc = 0;
for (auto i : sc) {
umap[i] = poc;
poc++;
comp.push_back(i);
}
vec<int> pr(m, -1), ps(comp.size(), m);
For(i, n) {
pr[r[i]] = max(pr[r[i]], umap[c[i]]);
ps[umap[c[i]]] = min(ps[umap[c[i]]], r[i]);
}
vec<int> kto_p(comp.size(), m);
kto_p[comp.size() - 1] = ps[comp.size() - 1];
for (int i = comp.size() - 2; i >= 0; i--) {
kto_p[i] = min(kto_p[i + 1], ps[i]);
}
vec<vec<ll>> dp(comp.size() + 1, vec<ll>(k + 1, NEK));
For(i, k+1) dp[comp.size()][i] = 0;
ffor(j, 1, k+1) {
rfor(i, comp.size() - 1) {
int som = kto_p[i];
int pred = -1;
if (i != 0) pred = comp[i - 1];
for (int l = pr[som]; l < comp.size(); l++) {
//berieme az po stlpec comp[l], teda stvorec velkosti comp[l] - som + 1
ll hod1 = ((ll)comp[l] - (ll)som + (ll)1);
ll hod2 = max((ll)0, ((ll)pred - (ll)som + (ll)1));
dp[i][j] = min(dp[i][j], dp[l+1][j - 1] + hod1 * hod1 - hod2 * hod2);
}
}
}
return dp[0][k];
}
long long take_photos_pomale(int n, int m, int k, vector<int> r, vector<int> c) {
vec<vec<int>> dp(m + 1, vec<int>(k + 1, NEK));
vec<int> pr(m, -1), ps(m, 0);
For(i, n) {
if (r[i] > c[i]) swap(r[i], c[i]);
pr[r[i]] = max(pr[r[i]], c[i]);
ps[c[i]]++;
}
For(i, k + 1) dp[m][i] = 0;
int pos = 0;
rfor(i, m - 1) {
pos = i;
if (ps[i] == 0) For(j, k + 1) dp[i][j] = 0;
else break;
}
ffor(j, 1, k + 1) {
rfor(i, pos) {
int som = -1;
For(l, m) {
if (pr[l] >= i) {
som = l;
break;
}
}
for (int l = pr[som]; l < m; l++) {
//berieme az po stlpec l, teda stvorec velkosti l - som + 1
dp[i][j] = min(dp[i][j], dp[l + 1][j - 1] + (l - som + 1) * (l - som + 1) - max(0, (i - som)) * max(0, (i - som)));
}
}
}
return dp[0][k];
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int cnt = 0;
while (1) {
int n, m, k;
cin >> n >> m >> k;
vec<int> r(n), c(n);
For(i, n) {
cin >> r[i] >> c[i];
}
ll odp2 = take_photos_rychle(n, m, k, r, c);
cout << odp2 << '\n';
return 0;
}
return 0;
}