Submission #5307011
Source Code Expand
#include <stdio.h> #include <assert.h> #include <fstream> #include <iostream> #include <algorithm> #include <array> #include <vector> #include <queue> #include <set> #include <cmath> #include <iomanip> //#include <unordered_map> //#include <unordered_set> //#include <boost/container/static_vector.hpp> //#include <boost/unordered_set.hpp> //#include <boost/unordered_map.hpp> //#include <unistd.h> //#include <cv.h> //#include <highgui.h> #include <stdlib.h> #include <string> const int MAX_N = 200050; const int MAX_L = 100000000; int N; int X[MAX_N], Y[MAX_N]; int seq[MAX_N], dp_lis[MAX_N]; int main(int argc, char **argv) { int x1, y1, x2, y2; std::cin >> x1 >> y1 >> x2 >> y2; std::cin >> N; for (int i = 1; i <= N; i++) { std::cin >> X[i] >> Y[i]; } if (x2 < x1) { for (int i = 1; i <= N; i++) { X[i] = MAX_L - 1 - X[i]; } x1 = MAX_L - 1 - x1; x2 = MAX_L - 1 - x2; } if (y2 < y1) { for (int i = 1; i <= N; i++) { Y[i] = MAX_L - 1 - Y[i]; } y1 = MAX_L - 1 - y1; y2 = MAX_L - 1 - y2; } std::vector<std::pair<int, int>> vec; for (int i = 1; i <= N; i++) { if (x1 <= X[i] && X[i] <= x2 && y1 <= Y[i] && Y[i] <= y2) { vec.push_back(std::pair<int, int>({X[i], Y[i]})); } } std::sort(vec.begin(), vec.end(), [](const std::pair<int, int>& a, const std::pair<int, int> b) { return a.first < b.first; } ); int seq_size = vec.size(); for (int i = 1; i <= seq_size; i++) { seq[i] = vec[i-1].second; } for (int i = 1; i <= seq_size; i++) { dp_lis[i] = MAX_L; } dp_lis[0] = 0; for (int i = 1; i <= seq_size; i++) { int lb = 0; int ub = seq_size; while(lb + 1 < ub) { int mid = (lb + ub) / 2; if (dp_lis[mid] < seq[i]) { lb = mid; } else { ub = mid; } } dp_lis[ub] = std::min(dp_lis[ub], seq[i]); } int length = 0; for (int i = 1; i <= seq_size; i++) { if (dp_lis[i] < MAX_L) { length++; } else { break; } } double PI = acos(-1.0); double ret = (x2 - x1 + y2 - y1) * 100.0; if (length == std::min(x2 - x1 + 1, y2 - y1 + 1)) { ret += (length - 1) * (5.0 * PI - 20.0); ret += 10.0 * PI - 20.0; } else { ret += length * (5.0 * PI - 20.0); } std::cout << std::setprecision(14) << ret << std::endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Fountain Walk |
User | critter |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 2704 Byte |
Status | AC |
Exec Time | 197 ms |
Memory | 5104 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 900 | ||||
Status |
|
|
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 | AC | 1 ms | 256 KB |
subtask_1_02.txt | AC | 1 ms | 256 KB |
subtask_1_03.txt | AC | 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 | 52 ms | 768 KB |
subtask_1_10.txt | AC | 107 ms | 1408 KB |
subtask_1_11.txt | AC | 28 ms | 512 KB |
subtask_1_12.txt | AC | 176 ms | 5104 KB |
subtask_1_13.txt | AC | 114 ms | 1536 KB |
subtask_1_14.txt | AC | 53 ms | 768 KB |
subtask_1_15.txt | AC | 26 ms | 512 KB |
subtask_1_16.txt | AC | 197 ms | 5104 KB |
subtask_1_17.txt | AC | 94 ms | 1280 KB |
subtask_1_18.txt | AC | 74 ms | 1024 KB |
subtask_1_19.txt | AC | 72 ms | 1024 KB |
subtask_1_20.txt | AC | 164 ms | 5104 KB |
subtask_1_21.txt | AC | 178 ms | 5104 KB |
subtask_1_22.txt | AC | 178 ms | 5104 KB |
subtask_1_23.txt | AC | 176 ms | 5104 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 | 119 ms | 2048 KB |
subtask_1_29.txt | AC | 146 ms | 1920 KB |
subtask_1_30.txt | AC | 185 ms | 5104 KB |
subtask_1_31.txt | AC | 133 ms | 5104 KB |
subtask_1_32.txt | AC | 136 ms | 5104 KB |
subtask_1_33.txt | AC | 135 ms | 5104 KB |
subtask_1_34.txt | AC | 131 ms | 5104 KB |
subtask_1_35.txt | AC | 165 ms | 5104 KB |
subtask_1_36.txt | AC | 166 ms | 5104 KB |
subtask_1_37.txt | AC | 165 ms | 5104 KB |
subtask_1_38.txt | AC | 165 ms | 5104 KB |
subtask_1_39.txt | AC | 165 ms | 5104 KB |
subtask_1_40.txt | AC | 163 ms | 5104 KB |
subtask_1_41.txt | AC | 163 ms | 5104 KB |