結果
| 問題 |
No.655 E869120 and Good Triangles
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:20:24 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,876 bytes |
| コンパイル時間 | 1,025 ms |
| コンパイル使用メモリ | 84,020 KB |
| 実行使用メモリ | 7,840 KB |
| 最終ジャッジ日時 | 2025-05-14 13:21:40 |
| 合計ジャッジ時間 | 5,478 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | AC * 10 TLE * 1 -- * 19 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
// Using long long for infinity to handle sums correctly against P_thresh
const long long INF = std::numeric_limits<long long>::max();
struct Point {
int r, c;
};
// Helper to check if (r, c) is a valid vertex in the N-sized main triangle
bool is_valid_coord(int r, int c, int N) {
return r >= 1 && r <= N && c >= 1 && c <= r;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N, K;
long long P_thresh;
std::cin >> N >> K >> P_thresh;
if (K == 0) {
// All a_i,j are INF. Sum for any triangle is INF.
// If P_thresh is finite, INF >= P_thresh is true. All triangles are good.
long long total_triangles = 0;
for (int r_coord = 1; r_coord <= N; ++r_coord) {
for (int c_coord = 1; c_coord <= r_coord; ++c_coord) {
total_triangles += (N - r_coord + 1);
}
}
std::cout << total_triangles << std::endl;
return 0;
}
std::vector<std::vector<long long>> a(N + 1, std::vector<long long>(N + 1, INF));
std::queue<Point> q;
for (int i = 0; i < K; ++i) {
int r_black, c_black;
std::cin >> r_black >> c_black;
if (is_valid_coord(r_black, c_black, N)) {
if (a[r_black][c_black] == INF) { // Avoid re-adding if multiple black points are same
a[r_black][c_black] = 0;
q.push({r_black, c_black});
}
}
}
// Delta r, Delta c for neighbors
// (r, c+1), (r, c-1)
// (r+1, c), (r+1, c+1)
// (r-1, c), (r-1, c-1)
int dr[] = {0, 0, 1, 1, -1, -1};
int dc[] = {1, -1, 0, 1, 0, -1};
while (!q.empty()) {
Point curr = q.front();
q.pop();
for (int i = 0; i < 6; ++i) {
int nr = curr.r + dr[i];
int nc = curr.c + dc[i];
bool structurally_valid_neighbor = true;
// Special check for (r-1, c): vertex (row, col) only exists if col <= row.
// So (curr.r-1, curr.c) is only a parent if curr.c <= curr.r-1.
if (dr[i] == -1 && dc[i] == 0) { // Trying to move to (curr.r-1, curr.c)
if (curr.c > curr.r - 1) {
structurally_valid_neighbor = false;
}
}
if (is_valid_coord(nr, nc, N) && structurally_valid_neighbor) {
if (a[nr][nc] > a[curr.r][curr.c] + 1) {
a[nr][nc] = a[curr.r][curr.c] + 1;
q.push({nr, nc});
}
}
}
}
std::vector<std::vector<long long>> rps(N + 1, std::vector<long long>(N + 1, 0));
for (int r_coord = 1; r_coord <= N; ++r_coord) {
for (int c_coord = 1; c_coord <= r_coord; ++c_coord) {
long long current_a_val = a[r_coord][c_coord];
if (c_coord == 1) {
rps[r_coord][c_coord] = current_a_val;
} else {
// Propagate INF carefully: finite + INF = INF
if (rps[r_coord][c_coord - 1] == INF || current_a_val == INF) {
if (rps[r_coord][c_coord - 1] != INF && current_a_val == INF) rps[r_coord][c_coord] = INF;
else if (rps[r_coord][c_coord - 1] == INF && current_a_val != INF) rps[r_coord][c_coord] = INF;
else rps[r_coord][c_coord] = INF; // both INF
} else {
// Check for overflow if adding two large finite numbers, though max finite sum is 6.4e10
if (rps[r_coord][c_coord-1] > INF - current_a_val) { // Should not happen with LLONG_MAX
rps[r_coord][c_coord] = INF;
} else {
rps[r_coord][c_coord] = rps[r_coord][c_coord - 1] + current_a_val;
}
}
}
}
}
long long count_good_triangles = 0;
for (int r_top = 1; r_top <= N; ++r_top) {
for (int c_top = 1; c_top <= r_top; ++c_top) {
long long current_triangle_sum = 0;
for (int s = 1; ; ++s) {
int base_r = r_top + s - 1;
if (base_r > N) break; // Sub-triangle exceeds main triangle height
int base_c_start = c_top;
int base_c_end = c_top + s - 1;
// base_c_end must be <= base_r. This is true if c_top <= r_top.
// If base_c_end > base_r, it means the base of sub-triangle is too wide for its row.
// This should not happen given c_top <= r_top ensures c_top+s-1 <= r_top+s-1.
long long new_row_sum_val;
long long rps_at_end = rps[base_r][base_c_end];
long long rps_at_start_minus_1 = (base_c_start > 1) ? rps[base_r][base_c_start - 1] : 0;
if (rps_at_start_minus_1 == INF) { // Implies rps_at_end is also INF
new_row_sum_val = INF; // Sum of INFs is INF
} else if (rps_at_end == INF) { // rps_at_end is INF, but rps_at_start_minus_1 is finite
new_row_sum_val = INF;
} else { // Both are finite
new_row_sum_val = rps_at_end - rps_at_start_minus_1;
}
if (current_triangle_sum == INF || new_row_sum_val == INF) {
if (current_triangle_sum != INF && new_row_sum_val == INF) current_triangle_sum = INF;
else if (current_triangle_sum == INF && new_row_sum_val != INF) current_triangle_sum = INF;
else current_triangle_sum = INF; // both INF
} else {
if (current_triangle_sum > INF - new_row_sum_val) { // Overflow check
current_triangle_sum = INF;
} else {
current_triangle_sum += new_row_sum_val;
}
}
// Optimization: if current_triangle_sum is already huge (but not INF), cap it.
// P_thresh can be up to 10^18. LLONG_MAX is ~9e18.
// Max finite sum is ~6.4e10. This cap is mostly for sums involving INF.
if (current_triangle_sum != INF && P_thresh > 0 && current_triangle_sum > P_thresh + N + 7) { // Arbitrary margin larger than P
current_triangle_sum = P_thresh + N + 7; // Cap to prevent large intermediate sums from slowing down or other issues.
}
if (current_triangle_sum >= P_thresh) {
int s_max = N - r_top + 1;
count_good_triangles += (s_max - s + 1);
break;
}
}
}
}
std::cout << count_good_triangles << std::endl;
return 0;
}