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
WA × 1
RE × 2
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