Submission #1540576
Source Code Expand
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }
int longestIncreaseSequence(int a[], int n) {
vector<int> A(n, INF);
for (int i = 0; i < n; i ++)
*lower_bound(A.begin(), A.end(), a[i]) = a[i];
return find(A.begin(), A.end(), INF) - A.begin();
}
int main() {
const double weight = 4.292036732051034;
const double weight2 = 11.415926535897931;
int x1; int y1; int x2; int y2;
while (~scanf("%d%d%d%d", &x1, &y1, &x2, &y2)) {
int W = abs(x2 - x1), H = abs(y2 - y1);
bool flipx = x1 > x2, flipy = y1 > y2;
int N;
scanf("%d", &N);
vpii points;
rep(i, N) {
int X; int Y;
scanf("%d%d", &X, &Y);
X -= x1, Y -= y1;
if (flipx) X = -X;
if (flipy) Y = -Y;
if (0 <= X && X <= W && 0 <= Y && Y <= H)
points.emplace_back(X, Y);
}
sort(points.begin(), points.end());
vi ys;
for (auto p : points)
ys.push_back(p.second);
int num = ys.empty() ? 0 : longestIncreaseSequence(ys.data(), (int)ys.size());
double ans = (W + H) * 100.;
if (num < min(W, H) + 1) {
ans -= num * weight;
} else {
ans -= (num - 1) * weight;
ans += weight2;
}
printf("%.10f\n", ans);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
anta |
Language |
C++14 (GCC 5.4.1) |
Score |
900 |
Code Size |
1718 Byte |
Status |
AC |
Exec Time |
68 ms |
Memory |
4080 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:26:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:30:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &X, &Y);
^
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 |
14 ms |
256 KB |
subtask_1_10.txt |
AC |
29 ms |
256 KB |
subtask_1_11.txt |
AC |
8 ms |
256 KB |
subtask_1_12.txt |
AC |
68 ms |
3568 KB |
subtask_1_13.txt |
AC |
31 ms |
256 KB |
subtask_1_14.txt |
AC |
15 ms |
256 KB |
subtask_1_15.txt |
AC |
8 ms |
256 KB |
subtask_1_16.txt |
AC |
67 ms |
3568 KB |
subtask_1_17.txt |
AC |
25 ms |
256 KB |
subtask_1_18.txt |
AC |
20 ms |
256 KB |
subtask_1_19.txt |
AC |
20 ms |
256 KB |
subtask_1_20.txt |
AC |
65 ms |
4080 KB |
subtask_1_21.txt |
AC |
67 ms |
3568 KB |
subtask_1_22.txt |
AC |
67 ms |
3568 KB |
subtask_1_23.txt |
AC |
68 ms |
3568 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 |
36 ms |
384 KB |
subtask_1_29.txt |
AC |
40 ms |
384 KB |
subtask_1_30.txt |
AC |
68 ms |
3568 KB |
subtask_1_31.txt |
AC |
45 ms |
3568 KB |
subtask_1_32.txt |
AC |
51 ms |
3568 KB |
subtask_1_33.txt |
AC |
50 ms |
3568 KB |
subtask_1_34.txt |
AC |
45 ms |
3568 KB |
subtask_1_35.txt |
AC |
55 ms |
3568 KB |
subtask_1_36.txt |
AC |
57 ms |
3568 KB |
subtask_1_37.txt |
AC |
56 ms |
3568 KB |
subtask_1_38.txt |
AC |
56 ms |
3568 KB |
subtask_1_39.txt |
AC |
56 ms |
3568 KB |
subtask_1_40.txt |
AC |
52 ms |
4080 KB |
subtask_1_41.txt |
AC |
53 ms |
3568 KB |