#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#ifdef LOCAL
ostream &operator<<(ostream &out, string str)
{
for (char c : str)
out << c;
return out;
}
template <class L, class R>
ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.first << ", " << p.second << ")"; }
template <class L, class R, class S>
ostream &operator<<(ostream &out, tuple<L, R, S> p)
{
auto &[a, b, c] = p;
return out << "(" << a << ", " << b << ", " << c << ")";
}
template <class T>
auto operator<<(ostream &out, T a) -> decltype(a.begin(), out)
{
out << '{';
for (auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts>
void dump(T a, Ts... x)
{
cerr << a << ", ";
dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) 42
#endif
struct ev
{
ll cost, num, last, size;
};
ll take_photos(int m, int n, int k, vi r, vi c)
{
vl V(n);
for (int i = 0; i < n; i++)
V[i] = i;
for (int i = 0; i < m; i++)
V[min(r[i], c[i])] = max(V[min(r[i], c[i])], ll(max(r[i], c[i])) + 1);
int st = 0;
while (st < n && V[st] == st)
st++;
if (st == n)
return 0;
// debug(st, V);
ll a = 0, b = ll(n) * ll(n);
ll ans;
while (a < b)
{
ll s = (a + b) / 2;
vector<ev> DP(n);
DP[st] = ev{V[st] * V[st] + s, 1, 0, V[st]};
for (int i = st + 1; i < n; i++)
{
ll oldCost = DP[i - 1].cost, newCost = DP[i - 1].cost + (V[i] - i) * (V[i] - i) + s;
if (V[i] > DP[i - 1].size)
{
oldCost += (V[i] - DP[i - 1].last) * (V[i] - DP[i - 1].last);
oldCost -= (DP[i - 1].size - DP[i - 1].last) * (DP[i - 1].size - DP[i - 1].last);
}
if (DP[i - 1].size > i)
newCost -= (DP[i - 1].size - i) * (DP[i - 1].size - i);
if (V[i] > DP[i - 1].size && newCost < oldCost)
DP[i] = ev{newCost, DP[i - 1].num + 1, i, V[i]};
else
{
DP[i] = DP[i - 1];
DP[i].cost = oldCost;
}
}
ans = DP.back().cost - DP.back().num * s;
if (DP.back().num > k)
a = s + 1;
else
b = s;
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
300 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
300 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 9109, expected = 7696 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 1 |
2 |
Incorrect |
0 ms |
212 KB |
Wrong answer: output = 2, expected = 4 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
300 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
300 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 9109, expected = 7696 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
300 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
300 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 9109, expected = 7696 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
300 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
300 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 9109, expected = 7696 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
300 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
300 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 9109, expected = 7696 |
9 |
Halted |
0 ms |
0 KB |
- |