Submission #3424838


Source Code Expand

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する


int X1, Y1, X2, Y2;

bool check(int x, int y) {
    return x >= min(X1, X2) && x <= max(X1, X2) && y >= min(Y1, Y2) && y <= max(Y1, Y2);
}


int compute_LIS(vector<int> v) {
    vector<int> dp(v.size() + 1, INF);

    for (auto e : v) {
        int key = lower_bound(all(dp), e) - dp.begin();
        dp[key] = e;
    }

//    int ret = lower_bound(all(dp),INF) - dp.begin() - 1;
    int ret = lower_bound(all(dp), INF) - dp.begin();
    return ret;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(13);

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    X1 = x1, Y1 = y1, X2 = x2, Y2 = y2;

    int N;
    cin >> N;

    // x1 < x2, y1 < y2と同じ状況にしたい
    // x1 == x2 or y1 == y2 なら特別なことをする
    // x1 > x2なら順番を反転, y1 > y2ならvalueを反転


    using P = pair<int, int>;
    vector<P> vp;

    rep(i, 0, N) {
        P p;
        cin >> p.first >> p.second;
        if (check(p.first, p.second)) {
            vp.push_back(p);
        }
    }

    sort(all(vp));
    vector<int> v;
    for (auto e : vp) {
        v.push_back(e.second);
    }


    const double pi = 3.14159265358979323846;
    if (x1 == x2 || y1 == y2) {
        //hogeをする
        double ans = 100.0 * (abs(x1 - x2) + abs(y1 - y2));
        if (v.size()) {
            ans += 10.0 * pi - 20;
        }
        cout << ans << endl;
        return 0;
    }

    if (1ll * (x2 - x1) * (y2 - y1) < 0) {
        //reverseする
        reverse(all(v));
    }

//    if (y1 > y2) {
//        //反転する
//        for (int i = 0; i < v.size(); ++i) {
//            v[i] *= -1;
//        }
//    }

    //vの最長増加部分列を求める
    int len = compute_LIS(v);
    double ans;
    if (len == v.size() && v.size() > 0) {
        ans = 100.0 * (abs(x1 - x2) + abs(y1 - y2)) + (len - 1) * (-20.0 + 5 * pi) + (10.0 * pi - 20);
    } else {
        ans = 100.0 * (abs(x1 - x2) + abs(y1 - y2)) + len * (-20.0 + 5 * pi);
    }
    cout << ans << endl;


    return 0;
}

Submission Info

Submission Time
Task C - Fountain Walk
User homesentinel
Language C++14 (Clang 3.8.0)
Score 0
Code Size 3345 Byte
Status WA
Exec Time 429 ms
Memory 4464 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 39
WA × 8
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 WA 1 ms 256 KB
subtask_1_02.txt WA 1 ms 256 KB
subtask_1_03.txt WA 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 137 ms 256 KB
subtask_1_10.txt AC 287 ms 256 KB
subtask_1_11.txt AC 74 ms 256 KB
subtask_1_12.txt AC 422 ms 4464 KB
subtask_1_13.txt AC 305 ms 256 KB
subtask_1_14.txt AC 141 ms 256 KB
subtask_1_15.txt AC 67 ms 256 KB
subtask_1_16.txt AC 424 ms 4464 KB
subtask_1_17.txt WA 253 ms 256 KB
subtask_1_18.txt WA 197 ms 256 KB
subtask_1_19.txt WA 192 ms 256 KB
subtask_1_20.txt WA 395 ms 4464 KB
subtask_1_21.txt WA 429 ms 4464 KB
subtask_1_22.txt AC 422 ms 4464 KB
subtask_1_23.txt AC 423 ms 4464 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 318 ms 384 KB
subtask_1_29.txt AC 392 ms 384 KB
subtask_1_30.txt AC 424 ms 4464 KB
subtask_1_31.txt AC 319 ms 4464 KB
subtask_1_32.txt AC 320 ms 4464 KB
subtask_1_33.txt AC 318 ms 4464 KB
subtask_1_34.txt AC 315 ms 4464 KB
subtask_1_35.txt AC 401 ms 4464 KB
subtask_1_36.txt AC 407 ms 4464 KB
subtask_1_37.txt AC 406 ms 4464 KB
subtask_1_38.txt AC 402 ms 4464 KB
subtask_1_39.txt AC 400 ms 4464 KB
subtask_1_40.txt AC 398 ms 4464 KB
subtask_1_41.txt AC 400 ms 4464 KB