Submission #1546371


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int main()
{
  double cost = 20 * acos(-1) / 4.0;

  int a, b, c, d, n, x[200000], y[200000];

  cin >> a >> b >> c >> d;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }

  if(a > c) swap(a, c), swap(b, d);
  bool flip = false;
  if(b > d) swap(b, d), flip = true;


  vector< pair< int, int > > idx;
  for(int i = 0; i < n; i++) {
    if(a <= x[i] && x[i] <= c && b <= y[i] && y[i] <= d) {
      if(flip) idx.emplace_back(x[i], y[i] * -1);
      else idx.emplace_back(x[i], y[i]);
    }
  }
  sort(begin(idx), end(idx));

  vector< int > dp(idx.size(), INF);
  for(auto &p : idx) {
    *lower_bound(begin(dp), end(dp), p.second) = p.second;
  }
  int pos = lower_bound(begin(dp), end(dp), INF) - begin(dp);
  double ret = (c - a) * 100.0 + (d - b) * 100.0;
  if(min(c - a, d - b) + 1 == pos) ret += cost;
  ret -= pos * (20.0 - cost);
  cout << fixed << setprecision(15) << ret << endl;
}

Submission Info

Submission Time
Task C - Fountain Walk
User ei13333
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1027 Byte
Status
Exec Time 183 ms
Memory 4980 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 900 / 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 51 ms 768 KB
subtask_1_10.txt 106 ms 1408 KB
subtask_1_11.txt 28 ms 512 KB
subtask_1_12.txt 173 ms 4208 KB
subtask_1_13.txt 114 ms 1408 KB
subtask_1_14.txt 53 ms 768 KB
subtask_1_15.txt 26 ms 512 KB
subtask_1_16.txt 174 ms 4208 KB
subtask_1_17.txt 94 ms 1280 KB
subtask_1_18.txt 74 ms 1024 KB
subtask_1_19.txt 72 ms 1024 KB
subtask_1_20.txt 161 ms 4208 KB
subtask_1_21.txt 172 ms 4208 KB
subtask_1_22.txt 174 ms 4208 KB
subtask_1_23.txt 183 ms 4208 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 119 ms 1920 KB
subtask_1_29.txt 146 ms 1920 KB
subtask_1_30.txt 173 ms 4208 KB
subtask_1_31.txt 127 ms 4208 KB
subtask_1_32.txt 133 ms 4208 KB
subtask_1_33.txt 139 ms 4208 KB
subtask_1_34.txt 134 ms 4208 KB
subtask_1_35.txt 161 ms 4208 KB
subtask_1_36.txt 162 ms 4208 KB
subtask_1_37.txt 162 ms 4980 KB
subtask_1_38.txt 161 ms 4208 KB
subtask_1_39.txt 161 ms 4208 KB
subtask_1_40.txt 158 ms 4208 KB
subtask_1_41.txt 158 ms 4208 KB