Submission #1545436


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <utility>
#include <functional>

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;
typedef pair<int,int> pii;

const double PI = acos(-1);
const int inf = 1 << 30;

int lis(vector<int> &v, int infi) {
    vector<int> ans(v.size(), infi);
    REP (i, 0, v.size()) {
        (*lower_bound(ans.begin(), ans.end(), v[i])) = v[i];
    }
    return lower_bound(ans.begin(), ans.end(), infi) - ans.begin();
}

int sign(lli s) {
    return (s >= 0 ? 1 : -1);
}

int main () {
    lli sx, sy, gx, gy;
    int N;
    cin >> sx >> sy >> gx >> gy;
    cin >> N;
    vector<pii> XY(N);
    int ml = sign((sx - gx) * (sy - gy));
    REP (i, 0, N) cin >> XY[i].first >> XY[i].second;
    double ans = 100 * (abs(sx - gx) + abs(sy - gy));
    vector<pii> lim;
    REP (i, 0, N) {
        if (min(sx, gx) <= XY[i].first && XY[i].first <= max(sx, gx) && min(sy, gy) <= XY[i].second && XY[i].second <= max(sy, gy)) {
            lim.push_back(XY[i]);
        }
    }
    int mx = 0, my = 0;
    {
        sort(lim.begin(), lim.end(), [&](pii a, pii b) { return a.first < b.first;});
        vector<int> temp;
        REP (i, 0, lim.size()) {
            temp.push_back(ml * lim[i].second);
        }
        my = lis(temp, ml * inf);
    }
    {
        sort(lim.begin(), lim.end(), [&](pii a, pii b) { return a.second < b.second;});
        vector<int> temp;
        REP (i, 0, lim.size()) {
            temp.push_back(ml * lim[i].first);
        }
        mx = lis(temp, ml * inf);
    }
    if (mx - 1 == abs(sx - gx) || my - 1 == abs(sy - gy)) {
        ans += (10 * PI - 20) - (20 - 5 * PI) * (max(mx, my) - 1);
    } else {
        ans -= (20 - 5 * PI) * max(mx, my);
    }
    cout << fixed << setprecision(15) << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Fountain Walk
User commy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1975 Byte
Status
Exec Time 200 ms
Memory 5232 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 0 / 900 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 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
subtask_1_01.txt 1 ms 256 KB
subtask_1_02.txt 1 ms 256 KB
subtask_1_03.txt 1 ms 256 KB
subtask_1_04.txt 1 ms 256 KB
subtask_1_05.txt 1 ms 256 KB
subtask_1_06.txt 1 ms 256 KB
subtask_1_07.txt 1 ms 256 KB
subtask_1_08.txt 1 ms 256 KB
subtask_1_09.txt 52 ms 768 KB
subtask_1_10.txt 107 ms 1408 KB
subtask_1_11.txt 29 ms 512 KB
subtask_1_12.txt 188 ms 5232 KB
subtask_1_13.txt 115 ms 1408 KB
subtask_1_14.txt 53 ms 768 KB
subtask_1_15.txt 26 ms 512 KB
subtask_1_16.txt 188 ms 5232 KB
subtask_1_17.txt 94 ms 1280 KB
subtask_1_18.txt 75 ms 1024 KB
subtask_1_19.txt 73 ms 1024 KB
subtask_1_20.txt 176 ms 5232 KB
subtask_1_21.txt 188 ms 5232 KB
subtask_1_22.txt 180 ms 5232 KB
subtask_1_23.txt 188 ms 5232 KB
subtask_1_24.txt 1 ms 256 KB
subtask_1_25.txt 1 ms 256 KB
subtask_1_26.txt 1 ms 256 KB
subtask_1_27.txt 1 ms 256 KB
subtask_1_28.txt 120 ms 1920 KB
subtask_1_29.txt 148 ms 1920 KB
subtask_1_30.txt 200 ms 5232 KB
subtask_1_31.txt 135 ms 5232 KB
subtask_1_32.txt 149 ms 5232 KB
subtask_1_33.txt 146 ms 5232 KB
subtask_1_34.txt 144 ms 5232 KB
subtask_1_35.txt 180 ms 5232 KB
subtask_1_36.txt 189 ms 5232 KB
subtask_1_37.txt 183 ms 5232 KB
subtask_1_38.txt 176 ms 5232 KB
subtask_1_39.txt 186 ms 5232 KB
subtask_1_40.txt 170 ms 5232 KB
subtask_1_41.txt 170 ms 5232 KB