結果
| 問題 |
No.60 魔法少女
|
| コンテスト | |
| ユーザー |
 reika727
|
| 提出日時 | 2024-02-04 03:36:59 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 194 ms / 5,000 ms |
| コード長 | 6,053 bytes |
| コンパイル時間 | 3,176 ms |
| コンパイル使用メモリ | 256,952 KB |
| 実行使用メモリ | 12,288 KB |
| 最終ジャッジ日時 | 2024-09-28 11:08:45 |
| 合計ジャッジ時間 | 4,792 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 10 |
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:210:14: warning: narrowing conversion of 'y' from 'int' to 'long unsigned int' [-Wnarrowing]
210 | {y, x},
| ^
main.cpp:210:17: warning: narrowing conversion of 'x' from 'int' to 'long unsigned int' [-Wnarrowing]
210 | {y, x},
| ^
main.cpp:211:20: warning: narrowing conversion of '((y + h) + 1)' from 'int' to 'long unsigned int' [-Wnarrowing]
211 | {y + h + 1, x + w + 1},
| ~~~~~~^~~
main.cpp:211:31: warning: narrowing conversion of '((x + w) + 1)' from 'int' to 'long unsigned int' [-Wnarrowing]
211 | {y + h + 1, x + w + 1},
| ~~~~~~^~~
ソースコード
#include "bits/stdc++.h"
template <std::default_initializable T, size_t Dimension>
class imos
: protected std::conditional_t<
Dimension == 1,
std::vector<T>,
std::vector<imos<T, Dimension - 1>>
>
{
static_assert(Dimension != 0, "Dimension must not be 0.");
friend imos<T, Dimension + 1>;
private:
using lower_dimension = std::conditional_t<
Dimension == 1,
T,
imos<T, Dimension - 1>
>;
imos<T, Dimension> &operator+=(const imos<T, Dimension> &ci)
{
for (auto i = 0uz; i < this->size(); ++i) {
(*this)[i] += ci[i];
}
return *this;
}
public:
explicit imos(const std::size_t size, const auto... sizes)
: std::vector<lower_dimension>(
size + 1,
lower_dimension(sizes...)
)
{
static_assert(
1 + sizeof...(sizes) == Dimension,
"Number of sizes must be equal to Dimension."
);
if (size == 0) {
throw std::invalid_argument("Each size of dimension must not be 0.");
}
}
const T& at(const std::size_t index, const auto... indices) const
{
static_assert(
1 + sizeof...(indices) == Dimension,
"Number of indices must be equal to Dimension."
);
if constexpr (sizeof...(indices) == 0) {
return (*this)[index];
} else {
return (*this)[index].at(indices...);
}
}
void set(
const std::span<const std::size_t, Dimension> begin,
const std::span<const std::size_t, Dimension> end,
const T weight
)
{
const auto begin0 = std::min(begin.front(), this->size() - 1);
const auto end0 = std::min(end.front(), this->size() - 1);
if constexpr (Dimension > 1) {
(*this)[begin0].set(
begin.template last<Dimension - 1>(),
end.template last<Dimension - 1>(),
weight
);
(*this)[end0].set(
begin.template last<Dimension - 1>(),
end.template last<Dimension - 1>(),
-weight
);
} else {
(*this)[begin0] += weight;
(*this)[end0] -= weight;
}
}
void set(
const std::array<std::size_t, Dimension> &begin,
const std::array<std::size_t, Dimension> &end,
const T weight
)
{
set(std::span{begin}, std::span{end}, weight);
}
void set(std::size_t begin, std::size_t end, const T weight)
{
static_assert(
Dimension == 1,
"set(size_t, size_t, T) can be called only when Dimension == 1."
);
return set(std::array{begin}, std::array{end}, weight);
}
void accumulate()
{
for (auto i = 0uz; i < this->size() - 1; ++i) {
(*this)[i + 1] += (*this)[i];
}
if constexpr (Dimension > 1) {
for (auto &child : *this) {
child.accumulate();
}
}
}
};
template <class T, size_t Dimension>
class cyclic_imos final : public imos<T, Dimension> {
public:
using imos<T, Dimension>::imos;
void set_cyclic(
const std::span<const std::size_t, Dimension> begin,
const std::span<const std::size_t, Dimension> end,
const T weight
)
{
this->set(begin, end, weight);
if constexpr (Dimension > 1) {
for (unsigned i = 1; i < (1 << Dimension); ++i) {
std::array<std::size_t, Dimension> correction_begin, correction_end;
for (auto j = 0uz; j < Dimension; ++j) {
if (i & (1 << j)) {
if (begin[j] <= end[j]) {
goto CONTINUE;
}
correction_begin[j] = 0;
correction_end[j] = this->size() - 1;
} else {
correction_begin[j] = begin[j];
correction_end[j] = end[j];
}
}
this->set(correction_begin, correction_end, weight);
CONTINUE:
;
}
} else {
if (begin.front() > end.front()) {
(*this).front() += weight;
(*this).back() -= weight;
}
}
}
void set_cyclic(
const std::array<std::size_t, Dimension> &begin,
const std::array<std::size_t, Dimension> &end,
const T weight
)
{
set_cyclic(std::span{begin}, std::span{end}, weight);
}
void set_cyclic(std::size_t begin, std::size_t end, const T weight)
{
static_assert(
Dimension == 1,
"set_cyclic(size_t, size_t, T) can be called only when Dimension == 1."
);
return set_cyclic(std::array{begin}, std::array{end}, weight);
}
};
template <class T>
auto make_imos(auto... sizes)
{
return imos<T, sizeof...(sizes)>(sizes...);
}
template <class T>
auto make_cyclic_imos(auto... sizes)
{
return cyclic_imos<T, sizeof...(sizes)>(sizes...);
}
int main()
{
struct enemy {
int x, y, hp;
};
int n, k;
std::cin >> n >> k;
std::vector<enemy> enemies(n);
for (int i = 0; i < n; ++i) {
int x, y, hp;
std::cin >> x >> y >> hp;
enemies[i] = {
x + 500,
y + 500,
hp
};
}
auto imos = make_imos<int>(1001, 1001);
for (int i = 0; i < k; ++i) {
int x, y, w, h, d;
std::cin >> x >> y >> w >> h >> d;
x += 500;
y += 500;
imos.set(
{y, x},
{y + h + 1, x + w + 1},
d
);
}
imos.accumulate();
std::cout << std::accumulate(
enemies.begin(), enemies.end(), 0,
[imos](int acc, const enemy &e) {
return acc + std::max(0, e.hp - imos.at(e.y, e.x));
}
) << std::endl;
}