이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "aliens.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 4010;
long long f[N][N];
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
assert(n != 1);
vector <pair <int, int> > P, Q;
for (int i = 0; i < n; ++i) {
if (r[i] > c[i]) swap(r[i], c[i]);
P.push_back({r[i], c[i]});
}
sort(P.begin(), P.end());
for (auto [x, y]: P) {
while (Q.size() && y <= Q.back().second) Q.pop_back();
Q.push_back({x, y});
}
swap(P, Q);
for (int i = 0; i < P.size(); ++i) {
f[i][1] = 1LL * (P[i].second - P[0].first + 1) * (P[i].second - P[0].first + 1);
for (int j = 2; j <= k; ++j) {
f[i][j] = f[i][j - 1];
for (int ii = 1; ii <= i; ++ii) {
long long cur = 1LL * (P[i].second - P[ii].first + 1) * (P[i].second - P[ii].first + 1);
if (P[ii].first <= P[ii - 1].second) {
cur -= 1LL * (P[ii - 1].second - P[ii].first + 1) * (P[ii - 1].second - P[ii].first + 1);
}
f[i][j] = min(f[i][j], f[ii - 1][j - 1] + cur);
}
}
}
return f[P.size() - 1][k];
}
//int main() {
// int n, m, k;
// assert(3 == scanf("%d %d %d", &n, &m, &k));
// std::vector<int> r(n), c(n);
// for (int i = 0; i < n; i++) {
// assert(2 == scanf("%d %d", &r[i], &c[i]));
// }
// long long ans = take_photos(n, m, k, r, c);
//
//
// printf("%lld\n", ans);
// return 0;
//}
컴파일 시 표준 에러 (stderr) 메시지
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:26:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
26 | for (auto [x, y]: P) {
| ^
aliens.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0; i < P.size(); ++i) {
| ~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |