Submission #2967530
Source Code Expand
#include <iostream> #include <algorithm> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <cstdio> #include <cstring> #include <math.h> using namespace std; typedef long long ll; typedef double D; typedef pair<int,int> P; #define M 1000000007 #define F first #define S second #define PB push_back int n; D t[100005],x[100005]; int main(void){ cin>>n; for(int i=1;i<=n;i++){ cin>>t[i]>>x[i]; } for(int i=n;i>0;i--){ t[i]-=t[i-1]; } D l=0,r=1000001; while(r-l>0.000001){ D m=(l+r)/2; D a[100005],b[100005]; a[0]=0; b[0]=0; bool o=true; for(int i=0;i<n&&o;i++){ D v=t[i+1]*m; if(x[i]-v<=x[i+1]&&x[i+1]<=x[i]+v){ a[i+1]=a[i]-v; b[i+1]=b[i]+v; if(a[i]-v<=x[i+1]&&x[i+1]<=b[i]+v){ a[i+1]=min(a[i+1],x[i]-v); b[i+1]=max(b[i+1],x[i]+v); } }else if(a[i]-v<=x[i+1]&&x[i+1]<=b[i]+v){ a[i+1]=x[i]-v; b[i+1]=x[i]+v; }else{ o=false; } } if(o)r=m; else l=m; } printf("%.7lf\n",l); }
Submission Info
Submission Time | |
---|---|
Task | F - ダブルス |
User | nxteru |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1302 Byte |
Status | AC |
Exec Time | 131 ms |
Memory | 3328 KB |
Judge Result
Set Name | Sample | Small | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | 200 / 200 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04 |
Small | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 01_random_00, 01_random_01, 01_random_02, 01_random_03, 01_random_04, 01_random_05, 01_random_06, 01_random_07, 01_random_08, 01_random_09, 02_X_positive_00, 02_X_positive_01, 02_X_positive_02, 02_X_positive_03, 02_X_positive_04, 03_X_negative_00, 03_X_negative_01, 03_X_negative_02, 03_X_negative_03, 03_X_negative_04, 04_T_large_00, 04_T_large_01, 04_T_large_02, 04_T_large_03, 04_T_large_04, 04_T_small_00, 04_T_small_01, 04_T_small_02, 04_T_small_03, 04_T_small_04, 05_X_negative_large_00, 05_X_negative_large_01, 05_X_negative_large_02, 05_X_negative_large_03, 05_X_negative_large_04, 05_X_positive_large_00, 05_X_positive_large_01, 05_X_positive_large_02, 05_X_positive_large_03, 05_X_positive_large_04, 05_absX_large_00, 05_absX_large_01, 05_absX_large_02, 05_absX_large_03, 05_absX_large_04, 05_absX_small_00, 05_absX_small_01, 05_absX_small_02, 05_absX_small_03, 05_absX_small_04, 08_V_minimum_nonzero_00, 09_max_00, 09_max_01, 09_max_02, 09_max_03, 09_max_04, 09_max_05, 09_max_06, 09_max_07, 09_max_08, 09_max_09, 09_max_10, 09_max_11, 09_max_12 |
All | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 01_random_00, 01_random_01, 01_random_02, 01_random_03, 01_random_04, 01_random_05, 01_random_06, 01_random_07, 01_random_08, 01_random_09, 02_X_positive_00, 02_X_positive_01, 02_X_positive_02, 02_X_positive_03, 02_X_positive_04, 03_X_negative_00, 03_X_negative_01, 03_X_negative_02, 03_X_negative_03, 03_X_negative_04, 04_T_large_00, 04_T_large_01, 04_T_large_02, 04_T_large_03, 04_T_large_04, 04_T_small_00, 04_T_small_01, 04_T_small_02, 04_T_small_03, 04_T_small_04, 05_X_negative_large_00, 05_X_negative_large_01, 05_X_negative_large_02, 05_X_negative_large_03, 05_X_negative_large_04, 05_X_positive_large_00, 05_X_positive_large_01, 05_X_positive_large_02, 05_X_positive_large_03, 05_X_positive_large_04, 05_absX_large_00, 05_absX_large_01, 05_absX_large_02, 05_absX_large_03, 05_absX_large_04, 05_absX_small_00, 05_absX_small_01, 05_absX_small_02, 05_absX_small_03, 05_absX_small_04, 08_V_minimum_nonzero_00, 09_max_00, 09_max_01, 09_max_02, 09_max_03, 09_max_04, 09_max_05, 09_max_06, 09_max_07, 09_max_08, 09_max_09, 09_max_10, 09_max_11, 09_max_12, 11_random_00, 11_random_01, 11_random_02, 11_random_03, 11_random_04, 11_random_05, 11_random_06, 11_random_07, 11_random_08, 11_random_09, 12_X_positive_00, 12_X_positive_01, 12_X_positive_02, 12_X_positive_03, 12_X_positive_04, 13_X_negative_00, 13_X_negative_01, 13_X_negative_02, 13_X_negative_03, 13_X_negative_04, 14_T_large_00, 14_T_large_01, 14_T_large_02, 14_T_large_03, 14_T_large_04, 14_T_small_00, 14_T_small_01, 14_T_small_02, 14_T_small_03, 14_T_small_04, 15_X_negative_large_00, 15_X_negative_large_01, 15_X_negative_large_02, 15_X_negative_large_03, 15_X_negative_large_04, 15_X_positive_large_00, 15_X_positive_large_01, 15_X_positive_large_02, 15_X_positive_large_03, 15_X_positive_large_04, 15_absX_large_00, 15_absX_large_01, 15_absX_large_02, 15_absX_large_03, 15_absX_large_04, 15_absX_small_00, 15_absX_small_01, 15_absX_small_02, 15_absX_small_03, 15_absX_small_04, 19_max_00, 19_max_01, 19_max_02, 19_max_03, 19_max_04, 19_max_05, 19_max_06, 19_max_07, 19_max_08, 19_max_09, 19_max_10, 19_max_11, 19_max_12 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 1 ms | 256 KB |
00_sample_01 | AC | 1 ms | 256 KB |
00_sample_02 | AC | 1 ms | 256 KB |
00_sample_03 | AC | 1 ms | 256 KB |
00_sample_04 | AC | 1 ms | 256 KB |
01_random_00 | AC | 3 ms | 256 KB |
01_random_01 | AC | 3 ms | 256 KB |
01_random_02 | AC | 2 ms | 256 KB |
01_random_03 | AC | 1 ms | 256 KB |
01_random_04 | AC | 1 ms | 256 KB |
01_random_05 | AC | 2 ms | 256 KB |
01_random_06 | AC | 3 ms | 256 KB |
01_random_07 | AC | 2 ms | 256 KB |
01_random_08 | AC | 3 ms | 256 KB |
01_random_09 | AC | 3 ms | 256 KB |
02_X_positive_00 | AC | 2 ms | 256 KB |
02_X_positive_01 | AC | 2 ms | 256 KB |
02_X_positive_02 | AC | 2 ms | 256 KB |
02_X_positive_03 | AC | 2 ms | 256 KB |
02_X_positive_04 | AC | 4 ms | 256 KB |
03_X_negative_00 | AC | 2 ms | 256 KB |
03_X_negative_01 | AC | 3 ms | 256 KB |
03_X_negative_02 | AC | 4 ms | 256 KB |
03_X_negative_03 | AC | 2 ms | 256 KB |
03_X_negative_04 | AC | 3 ms | 256 KB |
04_T_large_00 | AC | 4 ms | 384 KB |
04_T_large_01 | AC | 3 ms | 256 KB |
04_T_large_02 | AC | 3 ms | 256 KB |
04_T_large_03 | AC | 3 ms | 256 KB |
04_T_large_04 | AC | 3 ms | 256 KB |
04_T_small_00 | AC | 2 ms | 256 KB |
04_T_small_01 | AC | 3 ms | 256 KB |
04_T_small_02 | AC | 1 ms | 256 KB |
04_T_small_03 | AC | 2 ms | 256 KB |
04_T_small_04 | AC | 2 ms | 256 KB |
05_X_negative_large_00 | AC | 2 ms | 256 KB |
05_X_negative_large_01 | AC | 2 ms | 256 KB |
05_X_negative_large_02 | AC | 3 ms | 256 KB |
05_X_negative_large_03 | AC | 4 ms | 384 KB |
05_X_negative_large_04 | AC | 1 ms | 256 KB |
05_X_positive_large_00 | AC | 3 ms | 256 KB |
05_X_positive_large_01 | AC | 3 ms | 256 KB |
05_X_positive_large_02 | AC | 3 ms | 256 KB |
05_X_positive_large_03 | AC | 1 ms | 256 KB |
05_X_positive_large_04 | AC | 2 ms | 256 KB |
05_absX_large_00 | AC | 2 ms | 256 KB |
05_absX_large_01 | AC | 3 ms | 256 KB |
05_absX_large_02 | AC | 3 ms | 256 KB |
05_absX_large_03 | AC | 2 ms | 256 KB |
05_absX_large_04 | AC | 3 ms | 256 KB |
05_absX_small_00 | AC | 1 ms | 256 KB |
05_absX_small_01 | AC | 2 ms | 256 KB |
05_absX_small_02 | AC | 3 ms | 384 KB |
05_absX_small_03 | AC | 2 ms | 256 KB |
05_absX_small_04 | AC | 2 ms | 256 KB |
08_V_minimum_nonzero_00 | AC | 1 ms | 256 KB |
09_max_00 | AC | 4 ms | 384 KB |
09_max_01 | AC | 4 ms | 384 KB |
09_max_02 | AC | 4 ms | 384 KB |
09_max_03 | AC | 4 ms | 384 KB |
09_max_04 | AC | 4 ms | 384 KB |
09_max_05 | AC | 90 ms | 384 KB |
09_max_06 | AC | 4 ms | 256 KB |
09_max_07 | AC | 4 ms | 384 KB |
09_max_08 | AC | 4 ms | 384 KB |
09_max_09 | AC | 3 ms | 384 KB |
09_max_10 | AC | 3 ms | 384 KB |
09_max_11 | AC | 3 ms | 384 KB |
09_max_12 | AC | 3 ms | 384 KB |
11_random_00 | AC | 39 ms | 1152 KB |
11_random_01 | AC | 109 ms | 2944 KB |
11_random_02 | AC | 67 ms | 1792 KB |
11_random_03 | AC | 63 ms | 1792 KB |
11_random_04 | AC | 125 ms | 3328 KB |
11_random_05 | AC | 67 ms | 1920 KB |
11_random_06 | AC | 36 ms | 1152 KB |
11_random_07 | AC | 110 ms | 2944 KB |
11_random_08 | AC | 70 ms | 1920 KB |
11_random_09 | AC | 109 ms | 3072 KB |
12_X_positive_00 | AC | 62 ms | 1792 KB |
12_X_positive_01 | AC | 84 ms | 2432 KB |
12_X_positive_02 | AC | 90 ms | 2560 KB |
12_X_positive_03 | AC | 39 ms | 1280 KB |
12_X_positive_04 | AC | 117 ms | 3200 KB |
13_X_negative_00 | AC | 65 ms | 1792 KB |
13_X_negative_01 | AC | 41 ms | 1280 KB |
13_X_negative_02 | AC | 69 ms | 1920 KB |
13_X_negative_03 | AC | 29 ms | 896 KB |
13_X_negative_04 | AC | 86 ms | 2432 KB |
14_T_large_00 | AC | 88 ms | 2560 KB |
14_T_large_01 | AC | 85 ms | 2304 KB |
14_T_large_02 | AC | 68 ms | 1920 KB |
14_T_large_03 | AC | 112 ms | 2944 KB |
14_T_large_04 | AC | 76 ms | 2176 KB |
14_T_small_00 | AC | 16 ms | 640 KB |
14_T_small_01 | AC | 97 ms | 2944 KB |
14_T_small_02 | AC | 102 ms | 2944 KB |
14_T_small_03 | AC | 85 ms | 2560 KB |
14_T_small_04 | AC | 94 ms | 2816 KB |
15_X_negative_large_00 | AC | 30 ms | 896 KB |
15_X_negative_large_01 | AC | 101 ms | 2688 KB |
15_X_negative_large_02 | AC | 36 ms | 1152 KB |
15_X_negative_large_03 | AC | 41 ms | 1280 KB |
15_X_negative_large_04 | AC | 109 ms | 2944 KB |
15_X_positive_large_00 | AC | 38 ms | 1152 KB |
15_X_positive_large_01 | AC | 113 ms | 3200 KB |
15_X_positive_large_02 | AC | 19 ms | 640 KB |
15_X_positive_large_03 | AC | 79 ms | 2304 KB |
15_X_positive_large_04 | AC | 90 ms | 2560 KB |
15_absX_large_00 | AC | 14 ms | 512 KB |
15_absX_large_01 | AC | 89 ms | 2432 KB |
15_absX_large_02 | AC | 122 ms | 3328 KB |
15_absX_large_03 | AC | 58 ms | 1664 KB |
15_absX_large_04 | AC | 18 ms | 768 KB |
15_absX_small_00 | AC | 10 ms | 512 KB |
15_absX_small_01 | AC | 21 ms | 768 KB |
15_absX_small_02 | AC | 102 ms | 3200 KB |
15_absX_small_03 | AC | 51 ms | 1664 KB |
15_absX_small_04 | AC | 7 ms | 384 KB |
19_max_00 | AC | 125 ms | 3328 KB |
19_max_01 | AC | 123 ms | 3328 KB |
19_max_02 | AC | 126 ms | 3328 KB |
19_max_03 | AC | 121 ms | 3328 KB |
19_max_04 | AC | 131 ms | 3328 KB |
19_max_05 | AC | 106 ms | 3328 KB |
19_max_06 | AC | 125 ms | 3328 KB |
19_max_07 | AC | 130 ms | 3328 KB |
19_max_08 | AC | 129 ms | 3328 KB |
19_max_09 | AC | 105 ms | 3328 KB |
19_max_10 | AC | 108 ms | 3328 KB |
19_max_11 | AC | 113 ms | 3328 KB |
19_max_12 | AC | 111 ms | 3328 KB |