Submission #6365696
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x) \
for(auto &youso_ : (x)) cin >> youso_
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
T x;
cin >> x;
return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
cin >> head;
CIN(move(tail)...);
}
#define CINT(...) \
int __VA_ARGS__; \
CIN(__VA_ARGS__)
#define DCIN(...) \
double __VA_ARGS__; \
CIN(__VA_ARGS__)
#define LCIN(...) \
ll __VA_ARGS__; \
CIN(__VA_ARGS__)
#define SCIN(...) \
string __VA_ARGS__; \
CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v) \
{ \
FOREACH(x, v) { cout << x << " "; } \
cout << "\n"; \
}
template <typename T = string> inline void eputs(T s) {
cout << s << "\n";
exit(0);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
std::fill((T *)array, (T *)(array + N), val);
}
template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using PQ = priority_queue<T>;
typedef long long ll;
typedef unsigned long long ul;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const double PI = atan(1.0) * 4.0;
// const int MOD = 998244353;
const ll LINF = 9e18;
const ll dx[] = {1, 0, -1, 0};
const ll dy[] = {0, 1, 0, -1};
void cinfast() {
cin.tie(0);
ios::sync_with_stdio(false);
}
const ll sup = 1e8;
struct LIS {
vector<int> &v;
vector<int> dp, id, ret, info;
// info 1:unused 2:使っても良い 3:必ず使う
int n, lis;
LIS(vector<int> &_v) : v(_v) {
n = v.size();
dp.resize(n, INT_MAX / 2);
id.resize(n, 0);
REP(i, n) {
// 狭義単調増加列
// id[i] = lower_bound(dp.begin(), dp.end(), v[i]) - dp.begin();
// 広義単調増加列
id[i] = upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin();
dp[id[i]] = v[i];
}
int nl = *max_element(id.begin(), id.end());
lis = nl;
ret.resize(nl + 1, 0);
REPR(i, n - 1) if(id[i] == nl) ret[nl] = v[i], nl--;
info.resize(n);
vector<int> ma(n + 1), cnt(n);
ma[lis] = INT_MAX / 2;
REPR(i, n - 1) {
// 狭義単調増加列
// if (ma[id[i] + 1] <= v[i]) info[i] = 1;
// 広義単調増加列
if(ma[id[i] + 1] < v[i])
info[i] = 1;
else
cnt[id[i]]++, ma[id[i]] = max(ma[id[i]], v[i]);
}
REPR(i, n - 1) if(info[i] == 0 && cnt[id[i]] == 1) info[i] = 3;
REP(i, n) if(info[i] == 0) info[i] = 2;
lis--;
}
};
signed main() {
// cinfast();
CINT(x1, y1, x2, y2, N);
vector<int> X(N), Y(N);
REP(i, N) cin >> X[i] >> Y[i];
if(x1 > x2) {
x1 = sup - x1;
x2 = sup - x2;
REP(i, N) X[i] = sup - X[i];
}
if(y1 > y2) {
y1 = sup - y1;
y2 = sup - y2;
REP(i, N) Y[i] = sup - Y[i];
}
vector<pair<int, int>> v;
REP(i, N)
if(y1 <= Y[i] && Y[i] <= y2 && x1 <= X[i] && X[i] <= x2)
v.push_back({X[i], Y[i]});
sort(v.begin(), v.end());
vector<int> vv;
vv.push_back(-1);
FOREACH(p, v) vv.push_back(p.second);
vv.push_back(INT_MAX / 2 - 1);
LIS lis(vv);
double ans = 100.0 * (x2 - x1 + y2 - y1);
ans += (5.0 * PI - 20.0) * lis.lis;
if(lis.lis == min(x2 - x1, y2 - y1) + 1) ans += 5.0 * PI;
printf("%.15f\n", ans);
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
arktan763 |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
4951 Byte |
Status |
AC |
Exec Time |
181 ms |
Memory |
18796 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
900 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
1 ms |
256 KB |
subtask_1_03.txt |
AC |
1 ms |
256 KB |
subtask_1_04.txt |
AC |
1 ms |
256 KB |
subtask_1_05.txt |
AC |
1 ms |
256 KB |
subtask_1_06.txt |
AC |
1 ms |
256 KB |
subtask_1_07.txt |
AC |
1 ms |
256 KB |
subtask_1_08.txt |
AC |
1 ms |
256 KB |
subtask_1_09.txt |
AC |
51 ms |
1280 KB |
subtask_1_10.txt |
AC |
107 ms |
2560 KB |
subtask_1_11.txt |
AC |
28 ms |
768 KB |
subtask_1_12.txt |
AC |
181 ms |
18028 KB |
subtask_1_13.txt |
AC |
114 ms |
2688 KB |
subtask_1_14.txt |
AC |
57 ms |
1408 KB |
subtask_1_15.txt |
AC |
26 ms |
768 KB |
subtask_1_16.txt |
AC |
180 ms |
18796 KB |
subtask_1_17.txt |
AC |
94 ms |
2304 KB |
subtask_1_18.txt |
AC |
74 ms |
1792 KB |
subtask_1_19.txt |
AC |
72 ms |
1920 KB |
subtask_1_20.txt |
AC |
168 ms |
17900 KB |
subtask_1_21.txt |
AC |
180 ms |
18540 KB |
subtask_1_22.txt |
AC |
180 ms |
17900 KB |
subtask_1_23.txt |
AC |
180 ms |
17900 KB |
subtask_1_24.txt |
AC |
1 ms |
256 KB |
subtask_1_25.txt |
AC |
1 ms |
256 KB |
subtask_1_26.txt |
AC |
1 ms |
256 KB |
subtask_1_27.txt |
AC |
1 ms |
256 KB |
subtask_1_28.txt |
AC |
119 ms |
3840 KB |
subtask_1_29.txt |
AC |
149 ms |
3712 KB |
subtask_1_30.txt |
AC |
179 ms |
16620 KB |
subtask_1_31.txt |
AC |
133 ms |
16620 KB |
subtask_1_32.txt |
AC |
142 ms |
18412 KB |
subtask_1_33.txt |
AC |
139 ms |
17132 KB |
subtask_1_34.txt |
AC |
134 ms |
17004 KB |
subtask_1_35.txt |
AC |
167 ms |
16876 KB |
subtask_1_36.txt |
AC |
168 ms |
17132 KB |
subtask_1_37.txt |
AC |
172 ms |
17516 KB |
subtask_1_38.txt |
AC |
168 ms |
17132 KB |
subtask_1_39.txt |
AC |
168 ms |
16876 KB |
subtask_1_40.txt |
AC |
167 ms |
17900 KB |
subtask_1_41.txt |
AC |
166 ms |
17132 KB |