Submission #00040

ソースコード

?
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
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
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>;
template <class T> using Rope = __gnu_cxx::rope<T>;
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>;
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(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout.setf(ios_base::fixed);
cout.precision(10);
int w, h, n;
cin >> w >> h >> n;
vector<tuple<int, int, int> > pos(n);
int cnt = 0;
for(auto &&[y, x, z] : pos){
cin >> x >> y;
z = cnt;
++cnt;
}
auto y_sort = pos;
auto x_sort = pos;
for(int i = 0; i < n; ++i){
swap(get<0>(x_sort[i]), get<1>(x_sort[i]));
}
sort(all(y_sort));
sort(all(x_sort));
umap<int, int> ypos;
for(int i = 0; i < n; ++i){
ypos[get<2>(y_sort[i])] = i;
}
auto dist = [](int y1, int x1, int y2, int x2){
return (abs(y1 - y2) + abs(x1 - x2));
};
auto get_cost = [&](int x, int y){
int maxp = 0, maxv = 0;
for(int i = 0; i < n; ++i){
if(chmax(maxv, dist(y, x, get<1>(x_sort[i]), get<0>(x_sort[i])))){
maxp = i;
}
}
int sum = 0;
for(int i = 0; i < n; ++i){
sum += dist(y, x, get<1>(x_sort[i]), get<0>(x_sort[i]));
if(i != maxp){
sum += dist(y, x, get<1>(x_sort[i]), get<0>(x_sort[i]));
}
}
return (sum);
};
int min_y, min_x, minv = LINF;
for(int i = 1; i <= 50; ++i){
for(int j = 1; j <= 50; ++j){
if(chmin(minv, get_cost(i, j))){
min_y = j;
min_x = i;
}
}
}
cout << minv << '\n';
cout << min_x << ' ' << min_y << '\n';
return 0;
}

ステータス

項目 データ
問題 0005 - 歩くサンタクロース (Walking Santa)
ユーザー名 ei1903
投稿日時 2020-12-08 17:27:56
言語 C++17
状態 Wrong Answer
得点 10
ソースコード長 4058 Byte
最大実行時間 1000 ms
最大メモリ使用量 55592 KB

セット

セット 得点 Cases
1 Subtask1 5 / 5 01-*
2 Subtask2 0 / 5 02-*
3 Subtask3 0 / 5 03-*
4 Subtask4 5 / 5 04-*
5 Subtask5 0 / 5 05-*
6 Subtask6 0 / 5 06-*
7 Subtask7 0 / 5 07-*
8 Subtask8 0 / 5 08-*
9 Subtask9 0 / 5 09-*
10 Subtask10 0 / 5 10-*
11 Subtask11 0 / 5 11-*
12 Subtask12 0 / 5 12-*
13 Subtask13 0 / 5 13-*
14 Subtask14 0 / 5 14-*
15 Subtask15 0 / 5 15-*
16 Subtask16 0 / 5 16-*
17 Subtask17 0 / 5 17-*
18 Subtask18 0 / 5 18-*
19 Subtask19 0 / 5 19-*
20 Subtask20 0 / 5 20-*

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01-01.in AC 34 ms 604 KB
1
01-02.in AC 18 ms 688 KB
1
01-03.in AC 22 ms 648 KB
1
01-04.in AC 19 ms 604 KB
1
01-05.in AC 25 ms 564 KB
1
02-01.in AC 32 ms 520 KB
2
02-02.in WA 21 ms 604 KB
2
02-03.in WA 27 ms 544 KB
2
02-04.in WA 41 ms 608 KB
2
02-05.in WA 30 ms 552 KB
2
03-01.in WA 18 ms 744 KB
3
03-02.in WA 26 ms 808 KB
3
03-03.in WA 20 ms 752 KB
3
03-04.in WA 21 ms 692 KB
3
03-05.in WA 24 ms 756 KB
3
04-01.in AC 23 ms 824 KB
4
04-02.in AC 24 ms 740 KB
4
04-03.in AC 23 ms 656 KB
4
04-04.in AC 19 ms 704 KB
4
04-05.in AC 27 ms 620 KB
4
05-01.in WA 31 ms 784 KB
5
05-02.in WA 28 ms 880 KB
5
05-03.in WA 28 ms 712 KB
5
05-04.in WA 36 ms 804 KB
5
05-05.in WA 38 ms 896 KB
5
06-01.in WA 30 ms 860 KB
6
06-02.in WA 27 ms 816 KB
6
06-03.in WA 36 ms 912 KB
6
06-04.in WA 29 ms 1008 KB
6
06-05.in WA 28 ms 972 KB
6
07-01.in WA 33 ms 1068 KB
7
07-02.in WA 25 ms 904 KB
7
07-03.in WA 28 ms 992 KB
7
07-04.in WA 24 ms 1084 KB
7
07-05.in WA 28 ms 1044 KB
7
08-01.in WA 35 ms 1140 KB
8
08-02.in WA 46 ms 1236 KB
8
08-03.in WA 34 ms 1072 KB
8
08-04.in WA 30 ms 1168 KB
8
08-05.in WA 33 ms 1132 KB
8
09-01.in WA 769 ms 13156 KB
9
09-02.in WA 764 ms 14028 KB
9
09-03.in WA 774 ms 14900 KB
9
09-04.in WA 746 ms 15772 KB
9
09-05.in WA 791 ms 16644 KB
9
10-01.in WA 749 ms 17520 KB
10
10-02.in WA 762 ms 18264 KB
10
10-03.in WA 808 ms 19264 KB
10
10-04.in WA 782 ms 20140 KB
10
10-05.in WA 746 ms 21016 KB
10
11-01.in WA 766 ms 22652 KB
11
11-02.in WA 828 ms 24552 KB
11
11-03.in WA 789 ms 26188 KB
11
11-04.in WA 831 ms 27956 KB
11
11-05.in WA 793 ms 29856 KB
11
12-01.in WA 818 ms 31884 KB
12
12-02.in WA 780 ms 33652 KB
12
12-03.in WA 745 ms 35676 KB
12
12-04.in WA 756 ms 37572 KB
12
12-05.in WA 747 ms 39476 KB
12
13-01.in WA 748 ms 41496 KB
13
13-02.in WA 737 ms 43512 KB
13
13-03.in WA 740 ms 45536 KB
13
13-04.in WA 776 ms 47304 KB
13
13-05.in WA 751 ms 49204 KB
13
14-01.in WA 757 ms 51232 KB
14
14-02.in WA 754 ms 53252 KB
14
14-03.in WA 748 ms 55148 KB
14
14-04.in WA 739 ms 55372 KB
14
14-05.in WA 738 ms 55348 KB
14
15-01.in AC 27 ms 44280 KB
15
15-02.in WA 21 ms 44232 KB
15
15-03.in WA 737 ms 55488 KB
15
15-04.in WA 730 ms 55592 KB
15
15-05.in WA 733 ms 55440 KB
15
16-01.in WA 745 ms 55416 KB
16
16-02.in WA 722 ms 55396 KB
16
16-03.in WA 733 ms 55376 KB
16
16-04.in WA 747 ms 55480 KB
16
16-05.in TLE 1000 ms 55456 KB
16
17-01.in WA 757 ms 55436 KB
17
17-02.in WA 740 ms 55408 KB
17
17-03.in WA 743 ms 55384 KB
17
17-04.in WA 739 ms 55360 KB
17
17-05.in WA 742 ms 55340 KB
17
18-01.in WA 736 ms 55316 KB
18
18-02.in WA 726 ms 55416 KB
18
18-03.in WA 726 ms 55388 KB
18
18-04.in AC 795 ms 55364 KB
18
18-05.in WA 763 ms 55336 KB
18
19-01.in WA 733 ms 55316 KB
19
19-02.in WA 746 ms 55416 KB
19
19-03.in WA 747 ms 55516 KB
19
19-04.in WA 745 ms 55360 KB
19
19-05.in WA 778 ms 55464 KB
19
20-01.in WA 739 ms 55436 KB
20
20-02.in WA 739 ms 55540 KB
20
20-03.in WA 723 ms 55392 KB
20
20-04.in WA 722 ms 55492 KB
20
20-05.in WA 741 ms 55464 KB
20