Submission #1570382
Source Code Expand
#include <bits/stdc++.h> using namespace std; long long xi, yi, x2, y2, N, x, y; vector<pair<int, int> > A; int dp[1<<20]; const long double pi = 3.141592653589793; bool inside() { if(x < min(xi, x2)) return false; if(x > max(xi, x2)) return false; if(y < min(yi, y2)) return false; if(y > max(yi, y2)) return false; return true; } int LIS() { if((int)A.size() == 0) return 0; dp[0] = A[0].second; int C = 1; for(int i = 1;i < (int)A.size();i++) { if(A[i].second > dp[C-1]) { dp[C++] = A[i].second; continue; } dp[lower_bound(dp, dp+C, A[i].second)-dp] = A[i].second; } return C; } int main() { //freopen("input.in","r",stdin); //freopen("output.out","w",stdout); cin>>xi>>yi>>x2>>y2; cin>>N; for(int i = 0;i < N;i++) { cin>>x>>y; if(inside()) { A.push_back(make_pair(x, y)); } } sort(A.begin(), A.end()); int length = LIS(); cout << fixed << setprecision(15); long long tans = (abs(xi-x2)+abs(yi-y2))*100; vector<pair<int, int> > dirs{{xi, yi}, {x2, y2}, {xi, y2}, {x2, yi}}; sort(dirs.begin(), dirs.end()); if(length == abs(dirs[3].second-dirs[0].second)+1) { cout << tans + (10*pi-20) + (5*pi-20)*(length-1) << endl; } else { cout << tans + (5*pi-20)*(length) << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Fountain Walk |
User | cryptomanic |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1485 Byte |
Status | WA |
Exec Time | 173 ms |
Memory | 2672 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | WA | 51 ms | 256 KB |
subtask_1_10.txt | WA | 111 ms | 256 KB |
subtask_1_11.txt | WA | 28 ms | 256 KB |
subtask_1_12.txt | WA | 162 ms | 2672 KB |
subtask_1_13.txt | AC | 115 ms | 256 KB |
subtask_1_14.txt | WA | 52 ms | 256 KB |
subtask_1_15.txt | AC | 25 ms | 256 KB |
subtask_1_16.txt | AC | 165 ms | 2672 KB |
subtask_1_17.txt | AC | 93 ms | 256 KB |
subtask_1_18.txt | WA | 73 ms | 256 KB |
subtask_1_19.txt | AC | 71 ms | 256 KB |
subtask_1_20.txt | AC | 150 ms | 2672 KB |
subtask_1_21.txt | AC | 162 ms | 2672 KB |
subtask_1_22.txt | WA | 162 ms | 2420 KB |
subtask_1_23.txt | WA | 162 ms | 2420 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 | 118 ms | 384 KB |
subtask_1_29.txt | WA | 145 ms | 384 KB |
subtask_1_30.txt | AC | 173 ms | 2420 KB |
subtask_1_31.txt | AC | 128 ms | 2420 KB |
subtask_1_32.txt | AC | 122 ms | 2672 KB |
subtask_1_33.txt | AC | 124 ms | 2420 KB |
subtask_1_34.txt | AC | 130 ms | 2420 KB |
subtask_1_35.txt | AC | 158 ms | 2420 KB |
subtask_1_36.txt | AC | 159 ms | 2420 KB |
subtask_1_37.txt | AC | 153 ms | 2544 KB |
subtask_1_38.txt | AC | 154 ms | 2420 KB |
subtask_1_39.txt | AC | 155 ms | 2420 KB |
subtask_1_40.txt | AC | 151 ms | 2420 KB |
subtask_1_41.txt | AC | 152 ms | 2420 KB |