QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#111942#1880. Nikanor Loves GameszhanghaojieWA 131ms24076kbC++141.5kb2023-06-09 10:42:272023-06-09 10:42:28

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-09 10:42:28]
  • Judged
  • Verdict: WA
  • Time: 131ms
  • Memory: 24076kb
Show
  • [2023-06-09 10:42:27]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
typedef long long LL;
const LL INF = 1e18;

struct Node
{
	int x,opt,v;
}node[N];
LL dp[N],sa[N],sb[N],x[N],y[N],ans;
int n,cnt,q[N],hh,tt;

bool cmp(Node a,Node b)
{
	return a.x<b.x;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b,c; 
		scanf("%d%d%d",&a,&b,&c);
		if(a>b) swap(a,b);
		node[++cnt]={a,-1,c};
		node[++cnt]={b,1,c};
	}
	sort(node+1,node+cnt+1,cmp);
	for(int i=1;i<=cnt;i++)
	{
		sa[i]=sa[i-1];
		sa[i]+=node[i].v;
	}
	for(int i=cnt;i>=1;i--)
	{
		sb[i]=sb[i+1];
		sb[i]-=node[i].v;
	}
	
//	for(int i=1;i<=cnt;i++)
//	cout<<sb[i]<<' ';
//	cout<<endl;
	
	y[0]=sb[1];
	x[0]=1;
	
	for(int i=1;i<=cnt;i++)
	x[i]=node[i].x,y[i]=sa[i]+sb[i+1];
	
//	for(int i=1;i<=cnt;i++)
//	cout<<node[i].x<<' '<<node[i].opt<<' '<<node[i].v<<endl;
//	cout<<endl<<endl<<endl;
	
//	for(int i=0;i<=cnt;i++)
//	cout<<x[i]<<' '<<y[i]<<endl;
	
	ans=sb[1]*2-4;
	for(int i=1;i<=cnt;i++)
	{
		while(hh<tt&&(double)(y[i]-y[q[tt]])/(x[i]-x[q[tt]])>=(double)(y[i]-y[q[tt-1]])/(x[i]-x[q[tt-1]]))
		tt--;
		q[++tt]=i;
		
		LL k=4*node[i].x;
		int l=hh,r=tt;
		while(l<r)
		{
			int mid=l+r>>1;
			if((double)(y[q[mid+1]]-y[q[mid]])/(x[q[mid+1]]-x[q[mid]])>k) l=mid+1;
			else r=mid;
		}
		dp[i]=-k*x[q[l]]+y[q[l]]+sa[i]+sb[i+1];
//		cout<<dp[i]<<' ';
		ans=max(ans,dp[i]);
	}
//	cout<<endl;
	printf("%.8lf",(double)ans/4);
//	cout<<ans<<endl;
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3572kb

input:

2
1 4 15
3 5 10

output:

2.50000000

result:

ok found '2.5000000', expected '2.5000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

1
2 2 8

output:

4.00000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

3
94 68 49
51 2 63
26 85 20

output:

-73.00000000

result:

ok found '-73.0000000', expected '-73.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3728kb

input:

2
14 68 12
28 2 46

output:

-16.00000000

result:

ok found '-16.0000000', expected '-16.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3756kb

input:

5
6 6 8
6 1 11
6 1 13
6 1 5
5 1 2

output:

9.50000000

result:

ok found '9.5000000', expected '9.5000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

5
5 4 2
4 1 10
3 1 3
2 1 3
5 1 5

output:

5.50000000

result:

ok found '5.5000000', expected '5.5000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3628kb

input:

5
1 5 2
4 2 7
2 2 2
2 5 14
1 4 2

output:

4.50000000

result:

ok found '4.5000000', expected '4.5000000', error '0.0000000'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3628kb

input:

5
4 1 9
1 5 13
3 6 10
6 5 8
3 5 5

output:

9.00000000

result:

ok found '9.0000000', expected '9.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3676kb

input:

5
3 7 9
5 7 12
4 6 13
3 6 6
2 1 2

output:

-6.00000000

result:

ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

10
8 10 26
11 2 28
13 4 13
11 1 26
6 15 23
12 8 7
9 8 11
11 10 17
8 11 18
3 10 27

output:

32.00000000

result:

ok found '32.0000000', expected '32.0000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

10
6 5 10
10 15 21
7 2 30
14 6 12
1 11 6
1 13 19
8 13 29
9 4 14
1 4 29
4 12 17

output:

12.00000000

result:

ok found '12.0000000', expected '12.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

10
5 15 15
3 14 20
11 14 26
15 12 22
5 15 11
12 10 10
1 12 18
7 7 14
3 5 10
12 9 23

output:

-6.00000000

result:

ok found '-6.0000000', expected '-6.0000000', error '-0.0000000'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3516kb

input:

10
3 9 29
9 5 27
14 13 21
3 15 15
14 11 24
9 14 22
9 3 20
12 15 27
5 13 21
13 11 14

output:

-5.00000000

result:

ok found '-5.0000000', expected '-5.0000000', error '-0.0000000'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

10
3 13 11
3 5 20
9 10 1
5 5 25
10 1 29
6 10 26
1 15 1
10 10 18
6 6 2
14 6 20

output:

21.00000000

result:

ok found '21.0000000', expected '21.0000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

100
68 91 90
56 38 71
69 57 87
80 62 21
31 80 25
36 48 40
71 66 49
15 57 78
96 69 43
25 73 57
86 13 5
23 98 18
83 94 9
8 22 43
46 3 50
81 11 26
14 35 39
49 68 73
41 11 25
35 47 48
5 96 15
15 56 60
42 1 40
11 4 25
57 72 9
43 3 90
16 45 36
83 50 17
55 40 39
72 37 6
70 84 24
12 36 95
43 15 13
82 28 68
...

output:

35.50000000

result:

ok found '35.5000000', expected '35.5000000', error '0.0000000'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

100
92 35 39
34 92 36
45 45 46
66 5 64
22 21 48
53 70 91
93 19 98
97 67 54
57 77 64
90 81 23
12 83 92
59 3 26
13 65 47
19 23 58
27 58 38
60 18 70
32 94 53
100 66 97
33 53 16
56 2 64
8 9 55
93 92 22
27 25 39
45 49 24
76 80 89
73 55 77
69 53 90
39 77 40
86 12 11
23 87 25
8 96 31
73 45 98
52 62 55
98 9...

output:

-100.00000000

result:

ok found '-100.0000000', expected '-100.0000000', error '-0.0000000'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

100
20 84 93
15 45 13
28 33 2
49 41 12
12 50 59
62 89 49
11 60 42
74 84 33
14 94 85
51 2 89
26 66 87
92 12 26
47 32 84
34 16 80
20 16 27
48 34 14
54 61 66
52 47 21
41 87 3
81 45 68
24 18 94
71 23 87
12 49 34
79 6 6
91 92 56
3 15 64
22 69 41
91 3 60
21 76 79
65 41 48
46 9 35
34 54 92
68 10 1
22 82 17...

output:

25.50000000

result:

ok found '25.5000000', expected '25.5000000', error '0.0000000'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

100
44 28 47
89 7 89
7 21 57
27 92 56
14 96 86
79 11 7
29 4 95
56 93 16
71 2 6
100 14 59
53 32 82
24 20 35
73 7 22
44 9 91
5 70 24
31 41 50
72 19 80
100 44 46
33 26 94
2 4 72
27 35 29
49 54 44
92 73 33
13 55 92
6 3 31
37 76 47
75 77 87
44 33 80
63 48 51
12 90 66
83 17 46
99 59 78
76 61 35
39 52 91
9...

output:

-57.00000000

result:

ok found '-57.0000000', expected '-57.0000000', error '-0.0000000'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

100
68 73 96
63 60 58
86 13 29
13 32 95
4 25 97
96 30 61
55 57 43
34 98 95
32 14 27
65 26 38
79 10 69
56 33 35
98 82 59
55 9 5
82 25 12
19 53 94
90 82 6
48 29 70
29 60 76
23 59 89
38 44 64
31 81 10
77 96 24
51 99 79
25 19 11
68 32 34
28 89 38
100 64 4
94 16 19
58 40 89
17 34 57
64 69 80
92 12 81
63 ...

output:

-81.50000000

result:

ok found '-81.5000000', expected '-81.5000000', error '-0.0000000'

Test #20:

score: 0
Accepted
time: 54ms
memory: 24060kb

input:

200000
14 11 10
2 6 10
18 13 7
8 5 11
13 5 14
16 14 2
4 5 17
4 20 7
7 3 9
9 8 11
15 1 20
19 13 3
19 17 15
9 16 20
5 5 15
2 1 6
11 14 13
8 13 7
2 3 10
7 18 9
1 4 12
17 3 7
14 4 17
12 14 11
18 11 6
11 7 15
10 4 13
13 2 14
2 1 18
7 3 18
12 16 19
17 13 7
7 17 1
20 9 2
2 1 2
6 13 11
7 11 9
20 16 3
9 4 4
...

output:

2100856.00000000

result:

ok found '2100856.0000000', expected '2100856.0000000', error '0.0000000'

Test #21:

score: 0
Accepted
time: 62ms
memory: 23928kb

input:

200000
18 20 15
4 20 7
1 5 6
6 8 19
3 2 5
14 17 17
2 18 18
17 18 10
8 11 11
6 9 2
1 19 11
16 18 7
13 8 13
7 9 2
6 4 12
6 9 10
5 5 6
16 2 15
18 18 1
8 9 1
8 10 11
14 18 12
19 8 8
18 11 17
9 19 1
17 3 2
3 11 15
9 17 10
12 17 6
14 17 20
10 16 11
18 2 6
16 5 3
4 2 16
3 16 16
16 11 14
4 2 4
5 8 6
17 8 9
...

output:

2101118.00000000

result:

ok found '2101118.0000000', expected '2101118.0000000', error '0.0000000'

Test #22:

score: 0
Accepted
time: 65ms
memory: 24056kb

input:

200000
6 4 9
1 13 15
16 13 6
13 8 19
5 11 12
11 3 11
4 19 6
3 7 9
9 20 12
3 17 12
4 6 6
8 3 8
19 3 6
14 13 13
19 18 20
13 20 10
3 20 4
4 11 15
15 12 12
9 16 9
20 7 6
12 1 17
4 11 7
12 16 4
8 11 17
11 19 5
16 3 14
5 3 18
15 17 17
20 7 19
8 9 18
7 12 16
12 12 17
8 11 10
4 19 11
18 18 17
13 9 12
10 20 ...

output:

2100494.00000000

result:

ok found '2100494.0000000', expected '2100494.0000000', error '0.0000000'

Test #23:

score: 0
Accepted
time: 58ms
memory: 23928kb

input:

200000
10 4 6
3 15 8
20 17 1
15 3 10
16 12 3
12 2 13
7 4 19
5 16 12
18 20 9
16 17 2
6 4 17
4 16 16
13 18 8
5 6 7
4 13 17
17 12 10
17 10 6
16 16 4
7 19 19
14 11 13
3 4 5
10 13 15
5 15 6
10 4 18
11 2 4
1 15 7
1 11 4
14 17 2
10 9 5
7 16 2
18 1 5
12 1 10
20 3 19
16 20 4
5 14 17
19 17 16
9 4 11
14 12 15
...

output:

2104832.00000000

result:

ok found '2104832.0000000', expected '2104832.0000000', error '0.0000000'

Test #24:

score: 0
Accepted
time: 57ms
memory: 24072kb

input:

200000
14 9 12
13 9 5
7 10 8
13 7 10
6 2 10
9 4 3
9 12 7
3 6 11
15 12 10
1 10 9
12 19 4
17 4 16
6 5 5
19 7 6
1 3 6
20 3 14
15 5 20
7 10 4
11 13 10
15 2 5
14 13 16
12 8 20
6 15 17
4 17 20
7 18 3
12 15 10
14 19 19
10 8 6
1 1 9
14 6 4
12 2 16
13 10 4
8 15 13
20 1 19
2 1 11
5 8 15
14 16 15
19 8 18
9 19 ...

output:

2103344.00000000

result:

ok found '2103344.0000000', expected '2103344.0000000', error '0.0000000'

Test #25:

score: 0
Accepted
time: 60ms
memory: 24036kb

input:

200000
18 17 6
14 18 10
18 18 4
15 7 14
20 3 1
18 19 6
7 17 8
8 19 7
16 20 11
18 10 19
18 13 4
13 17 20
12 20 3
6 20 20
6 18 19
20 15 18
17 12 13
11 15 4
7 11 12
16 13 14
18 10 15
14 19 1
15 2 16
18 6 11
6 2 19
2 15 17
11 15 1
6 14 13
4 5 1
20 11 3
10 6 4
18 19 19
5 18 3
17 15 5
3 8 6
11 6 2
10 11 1...

output:

2099791.00000000

result:

ok found '2099791.0000000', expected '2099791.0000000', error '0.0000000'

Test #26:

score: 0
Accepted
time: 72ms
memory: 24056kb

input:

200000
6 17 15
12 20 7
6 18 19
2 18 17
6 16 8
15 1 16
5 2 16
6 8 6
13 9 8
15 2 17
12 3 15
5 18 4
18 11 5
13 12 15
19 12 15
20 6 14
15 10 7
7 12 17
19 6 19
1 8 18
5 15 15
16 2 19
4 6 7
12 11 13
1 13 6
16 19 4
16 19 16
2 20 17
19 13 13
7 5 2
4 3 15
7 16 13
13 9 17
1 4 19
4 15 8
17 13 5
15 2 18
5 12 11...

output:

2097689.00000000

result:

ok found '2097689.0000000', expected '2097689.0000000', error '0.0000000'

Test #27:

score: 0
Accepted
time: 64ms
memory: 23840kb

input:

200000
6 10 9
9 13 3
1 6 19
20 18 1
17 9 7
12 20 18
7 15 9
4 17 9
10 9 10
15 3 8
18 2 2
18 7 8
3 6 18
11 13 13
15 11 4
7 14 18
13 17 1
15 13 13
15 20 10
2 15 10
16 16 10
13 17 20
17 6 6
2 8 19
16 9 5
6 20 7
10 7 7
14 11 5
14 9 16
9 15 20
2 15 18
20 5 7
9 8 19
17 1 13
5 10 3
3 12 20
12 18 17
14 17 2
...

output:

2104030.00000000

result:

ok found '2104030.0000000', expected '2104030.0000000', error '0.0000000'

Test #28:

score: 0
Accepted
time: 61ms
memory: 23876kb

input:

200000
14 14 19
19 15 8
4 18 14
2 17 9
11 7 18
9 6 8
9 15 9
1 11 8
11 17 11
16 15 14
16 12 1
10 20 13
17 5 20
18 10 12
20 5 13
11 18 2
7 16 14
3 2 5
7 18 17
3 6 18
20 10 9
11 8 5
6 13 5
16 12 6
11 1 5
17 16 14
3 3 13
7 1 17
13 9 8
20 4 7
19 16 5
5 11 1
17 16 1
17 14 7
6 1 1
9 2 3
16 5 1
7 9 5
13 3 1...

output:

2098865.00000000

result:

ok found '2098865.0000000', expected '2098865.0000000', error '0.0000000'

Test #29:

score: 0
Accepted
time: 63ms
memory: 24004kb

input:

200000
14 1 14
8 20 15
2 15 11
20 16 8
3 15 5
20 19 2
1 18 11
8 16 7
4 17 12
14 15 17
8 9 10
5 20 10
2 4 11
15 20 19
20 15 16
14 13 14
5 17 15
17 3 7
8 8 7
3 8 14
19 6 13
4 15 19
10 18 9
7 20 17
5 8 8
7 6 6
18 3 15
2 17 14
3 17 5
11 2 19
12 20 10
10 5 2
7 18 9
13 11 12
20 13 15
12 20 2
15 17 3
13 18...

output:

2102647.00000000

result:

ok found '2102647.0000000', expected '2102647.0000000', error '0.0000000'

Test #30:

score: -100
Wrong Answer
time: 131ms
memory: 24076kb

input:

200000
558273441 797132086 95394395
410375788 603346154 991788394
501822655 954838746 104557620
987594944 800261563 456008910
944698458 473660405 947257686
43525951 515134254 221154267
581712330 247867513 268703732
553202136 786196487 556214428
384021989 736444004 231738414
760952860 568578734 24958...

output:

288238114859554944.00000000

result:

wrong answer 1st numbers differ - expected: '-999998979.0000000', found: '288238114859554944.0000000', error = '288238410.1509707'
English 繁體中文 简体中文

Server Time: 2025-03-13 15:07:42 | OpenSource Project