Submission #6365637
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;
vector<PL> F;
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();
LCIN(x1, y1, x2, y2, N);
REP(i, N) {
LCIN(x, y);
F.emplace_back(x, y);
}
if(x1 > x2) {
x1 = sup - x1;
x2 = sup - x2;
REP(i, N) F[i].fi = sup - F[i].fi;
}
if(y1 > y2) {
y1 = sup - y1;
y2 = sup - y2;
REP(i, N) F[i].se = sup - F[i].se;
}
REP(i, N) {
if(y1 > F[i].se || F[i].se > y2 || x1 > F[i].fi || F[i].fi > x2)
F.erase(F.begin() + i);
}
sort(All(F));
VL ys(1, -1);
REP(i, F.size()) ys.emplace_back(F[i].se);
ys.emplace_back(LINF);
LIS lis(ys);
double ans = 100.0 * (x2 - x1 + y2 - y1);
ans -= (20 - 5 * PI) * lis.lis;
if(lis.lis == min(x2 - x1, y2 - y1) + 1) ans += 5 * PI;
printf("%.15f\n", ans);
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
arktan763 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4936 Byte |
Status |
RE |
Exec Time |
2103 ms |
Memory |
15724 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
AC |
× 1 |
WA |
× 29 |
TLE |
× 7 |
RE |
× 10 |
|
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 |
RE |
100 ms |
256 KB |
sample_02.txt |
WA |
1 ms |
256 KB |
sample_03.txt |
RE |
100 ms |
256 KB |
subtask_1_01.txt |
RE |
99 ms |
256 KB |
subtask_1_02.txt |
RE |
101 ms |
256 KB |
subtask_1_03.txt |
RE |
99 ms |
256 KB |
subtask_1_04.txt |
WA |
1 ms |
256 KB |
subtask_1_05.txt |
WA |
1 ms |
256 KB |
subtask_1_06.txt |
WA |
1 ms |
256 KB |
subtask_1_07.txt |
WA |
1 ms |
256 KB |
subtask_1_08.txt |
WA |
1 ms |
256 KB |
subtask_1_09.txt |
AC |
1331 ms |
2420 KB |
subtask_1_10.txt |
TLE |
2103 ms |
5232 KB |
subtask_1_11.txt |
RE |
476 ms |
1400 KB |
subtask_1_12.txt |
WA |
179 ms |
14828 KB |
subtask_1_13.txt |
TLE |
2103 ms |
6384 KB |
subtask_1_14.txt |
WA |
1412 ms |
2420 KB |
subtask_1_15.txt |
RE |
411 ms |
1400 KB |
subtask_1_16.txt |
WA |
178 ms |
14828 KB |
subtask_1_17.txt |
TLE |
2103 ms |
2420 KB |
subtask_1_18.txt |
TLE |
2103 ms |
2420 KB |
subtask_1_19.txt |
TLE |
2103 ms |
2420 KB |
subtask_1_20.txt |
RE |
264 ms |
14828 KB |
subtask_1_21.txt |
WA |
181 ms |
14828 KB |
subtask_1_22.txt |
WA |
178 ms |
14828 KB |
subtask_1_23.txt |
WA |
179 ms |
14828 KB |
subtask_1_24.txt |
WA |
1 ms |
256 KB |
subtask_1_25.txt |
WA |
1 ms |
256 KB |
subtask_1_26.txt |
WA |
1 ms |
256 KB |
subtask_1_27.txt |
WA |
1 ms |
256 KB |
subtask_1_28.txt |
TLE |
2103 ms |
5616 KB |
subtask_1_29.txt |
TLE |
2103 ms |
5488 KB |
subtask_1_30.txt |
WA |
179 ms |
15340 KB |
subtask_1_31.txt |
WA |
133 ms |
14828 KB |
subtask_1_32.txt |
WA |
139 ms |
14828 KB |
subtask_1_33.txt |
WA |
139 ms |
15212 KB |
subtask_1_34.txt |
WA |
133 ms |
15084 KB |
subtask_1_35.txt |
WA |
167 ms |
15596 KB |
subtask_1_36.txt |
WA |
169 ms |
14956 KB |
subtask_1_37.txt |
WA |
168 ms |
14828 KB |
subtask_1_38.txt |
WA |
168 ms |
14956 KB |
subtask_1_39.txt |
WA |
168 ms |
15724 KB |
subtask_1_40.txt |
WA |
164 ms |
15308 KB |
subtask_1_41.txt |
WA |
164 ms |
15468 KB |