Submission #00131

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#pragma GCC optimize("Ofast")
#include <bits/extc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) begin(x), end(x)
#define Fixed fixed << setprecision(12)
#define int int_fast64_t
using pii = pair<int,int>;
constexpr int32_t INF = 0x3f3f3f3f;
constexpr int_fast64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7;
constexpr int mod2 = 998244353;
template <class Func>
class FixPoint : Func {
public:
explicit constexpr FixPoint(Func&& f) noexcept : Func(forward<Func>(f)) {}
template <class... Args>
constexpr decltype(auto) operator()(Args&&... args) const {
return Func::operator()(*this, std::forward<Args>(args)...);
}
};
template <class Func>
static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept {
return FixPoint<Func>{forward<Func>(f)};
}
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
template <class T> using max_heap = priority_queue<T>;
template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class A, class B> using umap = unordered_map<A,B>;
template <class T> using Max_Heap = __gnu_pbds::priority_queue<T, less<T>, __gnu_pbds::rc_binomial_heap_tag>;
template <class T> using Min_Heap = __gnu_pbds::priority_queue<T, greater<T>, __gnu_pbds::rc_binomial_heap_tag>;
template <class T> using Set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template <class K, class V> using Umap = __gnu_pbds::gp_hash_table<K, V>;
using Trie = __gnu_pbds::trie<string, __gnu_pbds::null_type, __gnu_pbds::trie_string_access_traits<>, __gnu_pbds::pat_trie_tag, __gnu_pbds::trie_prefix_search_node_update>;
template <class T> inline void bye(T x) { cout << x << '\n', exit(0); }
inline int square(int a){ return a * a;}
inline int updiv(int a,int b){ return (a + b - 1) / b; }
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
signed main(void){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout.setf(ios_base::fixed);
cout.precision(10);
int n;
while(cin >> n, n){
int sx, sy, gx, gy;
cin >> sx >> sy >> gx >> gy;
--sx, --sy, --gx, --gy;
vector<vector<int> > matv(1e3 + 5, vector<int>(1e3 + 5));
vector<vector<int> > math(1e3 + 5, vector<int>(1e3 + 5));
vector<vector<int> > dp(1e3 + 5, vector<int>(1e3 + 5, LINF));
vector<int> x(n), y(n), r(n);
for(int i = 0; i < n; ++i){
cin >> x[i] >> y[i] >> r[i];
--x[i], --y[i];
}
if(sy > gy){
for(int i = 0; i < n; ++i){
y[i] = 1e3 - y[i] - 1;
}
sy = 1e3 - sy - 1;
gy = 1e3 - gy - 1;
}
if(sx > gx){
for(int i = 0; i < n; ++i){
x[i] = 1e3 - x[i] - 1;
}
sx = 1e3 - sx - 1;
gx = 1e3 - gx - 1;
}
/*
cout << sy << ' ' << gy << endl;
cout << sx << ' ' << gx << endl;
*/
++sy, ++sx, ++gy, ++gx;
dp[sy][sx] = 0;
for(int i = 0; i < n; ++i){
++x[i], ++y[i];
int lx = max<int>(0, x[i] - r[i]);
int hx = min<int>(1e3 + 2, x[i] + r[i]);
int ly = max<int>(0, y[i] - r[i]);
int hy = min<int>(1e3 + 2, y[i] + r[i]);
if(ly <= sy && sy <= hy && lx <= sx && sx <= hx){
++dp[sy][sx];
}else{
math[ly][lx]++;
math[ly][hx + 1]--;
matv[ly][lx]++;
matv[hy + 1][lx]--;
}
}
for(int i = 0; i <= 1e3 + 2; ++i){
for(int j = 1; j <= 1e3 + 2; ++j){
math[i][j] += math[i][j - 1];
}
}
for(int j = 0; j <= 1e3 + 2; ++j){
for(int i = 1; i <= 1e3 + 2; ++i){
matv[i][j] += matv[i - 1][j];
}
}
for(int i = sy; i <= gy; ++i){
for(int j = sx; j <= gx; ++j){
if(i == sy && j == sx) continue;
chmin(dp[i][j], dp[i - 1][j] + math[i][j]);
chmin(dp[i][j], dp[i][j - 1] + matv[i][j]);
}
}
cout << dp[gy][gx] << '\n';
}
return 0;
}

ステータス

項目 データ
問題 0007 - 忍ぶべし
ユーザー名 ei1903
投稿日時 2021-03-30 14:23:42
言語 C++17
状態 Accepted
得点 30
ソースコード長 4647 Byte
最大実行時間 1036 ms
最大メモリ使用量 26780 KB

セット

セット 得点 Cases
1 ALL 30 / 30 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
C1 AC 963 ms 26756 KB
1
C2 AC 964 ms 26780 KB
1
C3 AC 956 ms 26596 KB
1
C4 AC 1036 ms 26596 KB
1