#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Tran The Bao - ghostwriter
Training for VOI23 gold medal
----------------------------------------------------------------
DIT ME CHUYEN BAO LOC
----------------------------------------------------------------
*/
namespace subtask123 {
const int oo = 1e9 + 5;
const int M = 1001;
int f[M][M], d[M][M], d1[M][M], rs = oo;
int get(int x1, int y1, int x2, int y2) {
if (x1 > x2 || y1 > y2) return 0;
return f[x2][y2] - (x1? f[x1 - 1][y2] : 0) - (y1? f[x2][y1 - 1] : 0) + (x1 && y1? f[x1 - 1][y1 - 1] : 0);
}
ll take_photos(int n, int m, int k, vi r, vi c) {
FRN(i, n) ++f[r[i]][c[i]];
FRN(i, m)
FRN(j, m)
f[i][j] += (j? f[i][j - 1] : 0) + (i? f[i - 1][j] : 0) - (i && j? f[i - 1][j - 1] : 0);
FRN(i, m)
FRN(j, m) {
d1[i][j] = oo;
FOS(z, m - 1, i) {
int pre = get(j, j, m - 1, m - 1), cur = get(i, i, z, z);
int uni = get(j, j, z, z);
int total = get(i, i, m - 1, m - 1);
if (cur + pre - uni == total) d1[i][j] = z;
}
// debug(i, j, d1[i][j]);
}
FRN(i, m)
FRN(j, k) {
d[i][j] = oo;
if (j) {
FRN(z, i)
if (d1[z][i] != oo) {
int len = d1[z][i] - z + 1;
int len1 = max(0, min(d1[i][m - 1] - i + 1, d1[z][i] - i + 1));
d[i][j] = min(d[i][j], len * len - len1 * len1 + d[z][j - 1]);
// debug(i, j, z, len, len * len - len1 * len1 + d[z][j - 1]);
}
}
int pre = get(i, i, m - 1, m - 1), cur = get(0, 0, m - 1, m - 1);
if (pre == cur) d[i][j] = min(d[i][j], 0);
}
FRN(i, m) {
int len;
if (d1[i][m - 1] < oo) len = d1[i][m - 1] - i + 1;
else len = m - i;
rs = min(rs, len * len + d[i][k - 1]);
// debug(i, len, d[i][k - 1]);
}
return rs;
}
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
if (n <= 500 && m <= 1000) return subtask123::take_photos(n, m, k, r, c);
return 0;
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
2 6 2
1 4
4 1
----------------------------------------------------------------
From Benq:
stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/
Compilation message
aliens.cpp: In function 'll subtask123::take_photos(int, int, int, vi, vi)':
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
aliens.cpp:62:9: note: in expansion of macro 'FRN'
62 | FRN(i, n) ++f[r[i]][c[i]];
| ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
aliens.cpp:63:9: note: in expansion of macro 'FRN'
63 | FRN(i, m)
| ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
aliens.cpp:64:9: note: in expansion of macro 'FRN'
64 | FRN(j, m)
| ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
aliens.cpp:66:9: note: in expansion of macro 'FRN'
66 | FRN(i, m)
| ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
aliens.cpp:67:9: note: in expansion of macro 'FRN'
67 | FRN(j, m) {
| ^~~
aliens.cpp:35:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
35 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
| ^
aliens.cpp:69:13: note: in expansion of macro 'FOS'
69 | FOS(z, m - 1, i) {
| ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
aliens.cpp:77:9: note: in expansion of macro 'FRN'
77 | FRN(i, m)
| ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
aliens.cpp:78:9: note: in expansion of macro 'FRN'
78 | FRN(j, k) {
| ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
aliens.cpp:81:17: note: in expansion of macro 'FRN'
81 | FRN(z, i)
| ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
| ^
aliens.cpp:92:9: note: in expansion of macro 'FRN'
92 | FRN(i, m) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
1 ms |
312 KB |
Correct answer: answer = 4 |
| 4 |
Correct |
1 ms |
316 KB |
Correct answer: answer = 12 |
| 5 |
Incorrect |
1 ms |
340 KB |
Wrong answer: output = 38, expected = 52 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 1 |
| 2 |
Incorrect |
1 ms |
340 KB |
Wrong answer: output = 1, expected = 4 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
1 ms |
312 KB |
Correct answer: answer = 4 |
| 4 |
Correct |
1 ms |
316 KB |
Correct answer: answer = 12 |
| 5 |
Incorrect |
1 ms |
340 KB |
Wrong answer: output = 38, expected = 52 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
1 ms |
312 KB |
Correct answer: answer = 4 |
| 4 |
Correct |
1 ms |
316 KB |
Correct answer: answer = 12 |
| 5 |
Incorrect |
1 ms |
340 KB |
Wrong answer: output = 38, expected = 52 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
1 ms |
312 KB |
Correct answer: answer = 4 |
| 4 |
Correct |
1 ms |
316 KB |
Correct answer: answer = 12 |
| 5 |
Incorrect |
1 ms |
340 KB |
Wrong answer: output = 38, expected = 52 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
1 ms |
340 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
1 ms |
312 KB |
Correct answer: answer = 4 |
| 4 |
Correct |
1 ms |
316 KB |
Correct answer: answer = 12 |
| 5 |
Incorrect |
1 ms |
340 KB |
Wrong answer: output = 38, expected = 52 |
| 6 |
Halted |
0 ms |
0 KB |
- |
