QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#26559#1880. Nikanor Loves GamesCrysfly#WA 6ms16024kbC++111.9kb2022-04-07 18:42:522022-04-29 03:57:59

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 03:57:59]
  • 评测
  • 测评结果：WA
  • 用时：6ms
  • 内存：16024kb
查看
  • [2022-04-07 18:42:52]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
  
#define x first
#define y second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 2000005
#define inf 0x3f3f3f3f3f3f3f3f

int n,res;
int a[maxn],b[maxn],x[maxn];
int t[maxn],len,y[maxn];

int c[maxn];

pii stk[maxn];
int top;
void ins(int x,int y){
	while(top>1 && (__int128)(y-stk[top].y)*(stk[top].x-stk[top-1].x) > (__int128)(stk[top].y-stk[top-1].y)*(x-stk[top].x)) --top;
	stk[++top]=mkp(x,y); 
}

inline int F(pii f,int x){
	return f.y-x*f.x;
} 

signed main()
{
	n=read();
	For(i,1,n){
		a[i]=read(),b[i]=read(),x[i]=read();
		if(a[i]>b[i])swap(a[i],b[i]);
		t[++len]=a[i],t[++len]=b[i];
	}
	sort(t+1,t+len+1),len=unique(t+1,t+len+1)-t-1;
	int now=0;
	For(i,1,n)now-=x[i];
	res=-inf;
	For(i,1,n){
		int p=lower_bound(t+1,t+len+1,a[i])-t;
		c[p]+=x[i];
		p=lower_bound(t+1,t+len+1,b[i])-t;
		c[p]+=x[i];
	}
	if(t[1]!=1)ins(1,now);
	For(i,1,len){
		now+=c[i];
		y[i]=now;
	//	cout<<t[i]<<' '<<y[i]<<endl;
		ins(t[i],y[i]);
	}
	
	now=0;
	For(i,1,n)now-=x[i];
	int pos=top;
	if(t[1]!=1){
		while(pos>1 && F(stk[pos-1],2*1)>=F(stk[pos],2*1)) --pos;
		res=max(res,now+F(stk[pos],2*1)); 
	}
	For(i,1,len){
		// A = t[i]
		while(pos>1 && F(stk[pos-1],2*t[i])>=F(stk[pos],2*t[i])) --pos;	
	//	cout<<"ans: "<<t[i]<<' '<<stk[pos].x<<' '<<y[i]+F(stk[pos],2*t[i])<<endl;
		res=max(res,y[i]+F(stk[pos],2*t[i]));
	}
	printf("%lld.%lld",res>>1,(res%2)*5);
    return 0;
}

/*
a<a[i] -x/2
a[i]<=a<b[i] 0
b[i]>=a x/2

f(A) + f(B) - 2*A*B
枚举 A
tmp + F(B) - A*B 
*/
源文件, 语言: C++11

詳細信息

Test #1:

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

input:

2
1 4 15
3 5 10

output:

2.5

result:

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

Test #2:

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

input:

1
2 2 8

output:

4.0

result:

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

Test #3:

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

input:

3
94 68 49
51 2 63
26 85 20

output:

-73.0

result:

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

Test #4:

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

input:

2
14 68 12
28 2 46

output:

-16.0

result:

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

Test #5:

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

input:

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

output:

9.5

result:

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

Test #6:

score: 0
Accepted
time: 6ms
memory: 15996kb

input:

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

output:

5.5

result:

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

Test #7:

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

input:

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

output:

4.5

result:

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

Test #8:

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

input:

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

output:

9.0

result:

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

Test #9:

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

input:

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

output:

-6.0

result:

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

Test #10:

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

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.0

result:

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

Test #11:

score: 0
Accepted
time: 3ms
memory: 16004kb

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.0

result:

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

Test #12:

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

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.0

result:

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

Test #13:

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

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.0

result:

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

Test #14:

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

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.0

result:

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

Test #15:

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

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.5

result:

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

Test #16:

score: 0
Accepted
time: 5ms
memory: 15876kb

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.0

result:

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

Test #17:

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

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.5

result:

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

Test #18:

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

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.0

result:

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

Test #19:

score: -100
Wrong Answer
time: 3ms
memory: 15992kb

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:

-82.-5

result:

wrong output format Expected double, but "-82.-5" found
English 繁體中文 简体中文

伺服器時間: 2025-01-21 04:58:10 | 開源專案