QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369604#3976. Delivery DelaysatgcAC ✓322ms19736kbC++142.0kb2024-03-28 15:16:302024-03-28 15:16:32

Judging History

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

  • [2024-03-28 15:16:32]
  • 评测
  • 测评结果：AC
  • 用时：322ms
  • 内存：19736kb
查看
  • [2024-03-28 15:16:30]
  • 提交

answer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define int long long

using namespace std;
const int maxn = 2010;
int n,m;
int k;

struct{int nxt,v,w;}edge[maxn*20];
int head[maxn],ec;
void add(int u,int v,int w){edge[++ec]={head[u],v,w};head[u]=ec;}
void adds(int u,int v,int w){add(u,v,w),add(v,u,w);}

int dis[maxn][maxn];

void dijkstra(int s,int(&dis)[maxn]) {
	memset(dis,0x3f,sizeof dis);
	static bool vis[maxn];
	static priority_queue<pii,vector<pii>,greater<pii>>pq;
	pq.push({dis[s]=0,s});memset(vis,0,sizeof vis);
	while(!pq.empty()) {
		int u=pq.top().second;pq.pop();
		if(vis[u])continue;vis[u]=1;
		for(int i=head[u];i;i=edge[i].nxt){
			int v=edge[i].v,w=edge[i].w;
			if(dis[v]>dis[u]+w)pq.push({dis[v]=dis[u]+w,v});
		}
	}
}

struct {
	int s,u,t;
}t[maxn];

// template<class...a>
// void deb(a... b){(cout<<...<<(cout<<b,' '))<<'\n';}

int dp[maxn];

bool chk(int h) {
	memset(dp,0x3f,sizeof dp);
	dp[0]=0;
	// infun(h);
	for(int pos=0;pos <= k;++pos) {
		if(dp[pos] > t[pos].s + h)return 0;
		// infun(pos,dp[pos],t[pos].u);
		int curtime = dp[pos]+dis[t[pos].u][1], curmax = INT_MIN, ppt = curtime;
		// deb(ppt);
		int ee=1;
		swap(ee,t[pos].u);
		// if(curtime )
		for(int i=pos+1;i<=k;++i) {
			// deb(i,curtime,curmax);
			int nxtime = curtime+max(0ll,t[i].t-max(t[i-1].t,ppt))+dis[t[i-1].u][t[i].u];
			int nxtmax = max(curmax+max(0ll,t[i].t-max(t[i-1].t,ppt)),nxtime-t[i].s);
			// deb(nxtime,nxtmax);
			if(nxtmax > h) break;
			tie(curtime,curmax)={nxtime,nxtmax};
			if(curmax > h) break;
			dp[i]=min(dp[i],curtime);
		}
		swap(ee,t[pos].u);
	}
	return dp[k]<=t[k].s+h;
}

signed main() {
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;++i)cin>>u>>v>>w,adds(u,v,w);

	for(int i=1;i<=n;++i)dijkstra(i,dis[i]);

	cin>>k;
	t[0].u=1;
	for(int i=1;i<=k;++i)cin>>t[i].s>>t[i].u>>t[i].t;
	int l = 0,r = LLONG_MAX;
	while(l < r){
		int mid = (l+r)>>1;
		if(chk(mid))r=mid;
		else l=mid+1;
	}cout<<r;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3656kb

input:

4 4
1 2 2
2 3 4
3 4 1
4 1 2
3
1 4 2
3 3 3
4 3 6

output:

6

result:

ok single line: '6'

Test #2:

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

input:

3 2
1 2 1
3 2 2
4
0 3 1
1 3 3
2 2 4
4 3 6

output:

8

result:

ok single line: '8'

Test #3:

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

input:

100 99
93 43 2
14 58 5
57 64 1
95 87 6
36 78 1
92 65 8
41 14 3
93 70 1
29 80 4
5 76 5
73 7 4
58 18 8
35 93 1
93 81 7
2 67 4
82 59 1
65 55 0
95 48 4
94 86 0
88 49 0
72 85 1
23 47 6
27 22 1
28 55 0
78 30 3
30 53 3
12 100 6
64 65 2
98 8 1
16 96 7
60 3 2
81 24 3
6 18 2
45 30 1
98 17 6
75 57 6
50 33 8
63...

output:

6854

result:

ok single line: '6854'

Test #4:

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

input:

100 99
57 37 4
95 89 5
11 3 7
4 5 2
46 76 5
68 32 4
66 28 7
66 74 8
63 59 7
31 61 6
72 98 7
8 95 4
98 82 6
78 24 3
30 31 2
6 47 7
93 59 4
73 45 8
64 36 6
52 92 1
70 34 1
5 15 1
85 29 5
78 14 2
56 20 8
87 75 2
18 66 6
65 64 1
1 8 1
91 100 0
79 22 2
18 23 4
21 97 6
33 48 3
77 72 5
17 88 7
78 12 2
36 9...

output:

2969

result:

ok single line: '2969'

Test #5:

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

input:

100 99
18 57 3
54 65 4
94 34 8
90 42 8
61 77 6
92 14 0
84 92 7
58 50 5
56 100 0
18 5 0
60 2 2
54 39 0
30 44 1
61 32 0
9 19 1
91 57 7
10 48 0
82 43 1
1 31 8
66 98 8
93 77 7
15 81 5
61 40 2
85 55 5
22 78 1
75 53 5
20 67 6
78 86 6
30 48 4
69 75 5
61 79 4
12 61 3
97 53 5
9 63 6
86 90 1
50 65 2
64 28 8
7...

output:

282

result:

ok single line: '282'

Test #6:

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

input:

100 99
91 66 1
57 81 8
83 4 2
78 75 5
91 74 2
81 99 2
5 39 2
30 21 5
69 67 7
71 12 5
72 82 4
3 52 8
73 48 0
77 37 2
35 62 0
98 33 4
63 22 1
38 1 8
43 69 1
90 61 7
6 34 7
32 23 8
3 20 1
11 94 8
89 98 3
66 25 6
62 15 4
40 30 5
93 58 3
71 27 2
6 60 0
38 74 0
26 53 5
17 12 8
11 6 7
40 34 4
40 88 8
56 37...

output:

4991

result:

ok single line: '4991'

Test #7:

score: 0
Accepted
time: 290ms
memory: 19684kb

input:

1000 5000
729 279 53479479
520 788 28270992
527 934 28340161
928 454 51158146
917 261 60090787
152 249 37047363
65 290 86316785
154 289 0
152 196 68719529
382 68 59798216
241 71 0
356 306 11805202
249 957 11605881
751 6 62425243
650 125 28087608
894 698 42697781
360 636 48942200
976 201 81667831
912...

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 67ms
memory: 19488kb

input:

1000 999
323 324 100000000
371 372 100000000
676 677 100000000
137 138 100000000
962 963 100000000
153 154 100000000
855 856 100000000
957 958 100000000
180 181 100000000
374 375 100000000
278 279 100000000
497 498 100000000
438 439 100000000
264 265 100000000
807 808 100000000
270 271 100000000
694...

output:

99800199999001

result:

ok single line: '99800199999001'

Test #9:

score: 0
Accepted
time: 322ms
memory: 19736kb

input:

1000 5000
784 609 33124
146 962 485809
523 444 1
859 872 203401
110 962 608400
142 578 1
686 535 162409
67 926 1
859 195 436921
712 222 1
859 594 348100
535 88 318096
445 510 1
831 393 1
859 586 613089
971 296 1
962 331 404496
859 151 811801
322 217 1
454 609 190096
859 666 404496
609 255 393129
790...

output:

3740733

result:

ok single line: '3740733'

Test #10:

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

input:

100 99
41 24 3
90 41 2
44 9 1
74 14 5
47 100 0
50 63 6
1 77 1
17 1 5
26 85 8
61 62 2
24 36 5
94 44 6
53 59 6
70 87 6
15 42 3
76 1 7
21 64 4
1 69 7
60 99 6
20 84 6
46 95 2
47 54 4
95 11 4
58 28 7
53 36 4
48 32 6
46 52 0
3 52 5
55 14 4
80 66 7
87 91 4
7 21 2
81 27 7
49 70 0
71 3 1
25 68 7
8 23 3
35 84...

output:

4237

result:

ok single line: '4237'

Test #11:

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

input:

100 990
95 23 4
81 36 6
54 17 5
82 8 8
74 23 2
4 96 1
45 67 5
7 74 5
68 32 7
76 78 0
51 92 5
62 42 2
57 88 2
56 49 0
8 28 5
79 30 2
14 78 0
74 26 3
6 99 8
5 85 8
58 49 7
91 99 1
67 33 0
56 12 1
62 9 1
43 33 6
38 76 8
64 83 3
11 35 4
3 53 0
79 63 7
16 72 8
38 69 7
99 56 4
21 28 0
72 69 3
25 51 2
44 2...

output:

10378

result:

ok single line: '10378'

Test #12:

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

input:

100 990
42 93 2
9 62 2
84 18 7
98 94 2
18 33 0
42 8 5
11 86 6
89 38 5
25 42 6
99 6 1
56 85 6
53 13 2
10 27 4
47 68 6
61 26 1
67 21 5
9 34 5
36 11 8
37 67 8
25 35 4
61 68 7
34 6 1
83 97 4
11 83 6
14 11 4
36 8 7
47 34 1
74 72 7
7 28 7
30 73 2
75 30 8
79 52 2
23 30 0
15 94 2
6 9 5
42 71 7
30 87 8
85 22...

output:

1213

result:

ok single line: '1213'

Test #13:

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

input:

100 990
41 35 2
77 13 4
6 45 3
9 27 0
87 92 5
48 55 2
78 14 5
49 79 7
61 88 7
34 19 5
39 40 6
67 35 6
38 89 2
47 60 5
84 67 4
97 48 1
11 36 5
14 75 1
81 53 7
68 12 4
24 52 8
77 8 3
88 32 0
15 77 6
26 30 5
66 9 7
65 1 4
89 53 0
74 61 8
21 90 2
69 91 5
14 56 6
2 11 0
38 52 7
63 52 5
84 11 0
24 99 1
95...

output:

736

result:

ok single line: '736'

Test #14:

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

input:

100 990
48 36 1
33 44 7
7 97 0
31 53 1
50 96 6
4 48 6
52 8 3
74 31 8
83 63 8
35 22 8
29 26 3
55 96 6
68 84 6
91 89 8
17 30 8
30 24 6
95 26 6
66 18 0
50 38 0
69 59 5
4 78 7
45 42 2
59 73 1
52 60 4
32 19 4
78 16 5
22 74 1
14 3 3
70 7 5
52 24 0
26 96 8
23 81 8
73 69 2
84 85 6
82 69 3
2 57 7
9 51 0
48 7...

output:

135

result:

ok single line: '135'

Test #15:

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

input:

100 990
89 16 6
88 32 4
39 76 3
93 71 7
83 10 3
94 93 7
6 24 4
61 78 1
31 30 2
27 16 0
44 15 1
64 34 6
13 93 5
69 58 8
25 45 7
82 51 6
100 74 5
75 93 5
62 58 4
79 82 3
85 58 2
95 24 5
48 29 7
76 93 2
79 49 7
85 48 7
74 17 6
49 98 0
23 100 6
71 91 6
71 58 0
84 46 5
94 74 6
6 67 4
93 31 5
7 40 8
30 90...

output:

4

result:

ok single line: '4'

Test #16:

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

input:

100 1980
33 91 1
72 15 8
53 2 2
28 32 8
48 61 6
91 10 1
76 21 8
79 87 1
26 24 7
92 49 5
84 28 3
45 48 5
30 40 7
3 20 6
3 61 3
90 54 4
75 2 5
71 61 7
37 44 4
77 31 5
30 51 6
82 49 7
21 7 7
32 38 0
60 57 8
10 68 2
79 49 6
15 58 4
8 62 0
41 47 0
11 91 7
24 4 3
37 36 3
70 52 5
74 53 5
84 82 2
2 31 8
92 ...

output:

10639

result:

ok single line: '10639'

Test #17:

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

input:

100 1980
31 99 0
1 84 2
43 84 1
99 62 5
75 48 0
90 7 2
97 10 3
37 94 6
35 82 7
41 91 2
100 94 0
47 42 2
36 38 2
58 45 6
49 22 6
57 80 8
25 51 5
90 76 4
73 33 8
81 57 2
40 95 7
5 91 8
58 31 2
56 96 4
91 40 3
65 89 5
89 44 0
24 39 6
11 39 4
17 88 3
13 35 2
18 29 0
40 56 6
14 51 3
25 30 7
72 82 1
42 92...

output:

2427

result:

ok single line: '2427'

Test #18:

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

input:

100 1980
85 67 5
91 32 6
79 82 0
100 54 0
26 12 4
37 40 8
83 98 2
54 37 6
87 80 4
87 84 2
73 94 6
66 41 1
71 99 1
9 45 7
33 11 2
96 60 0
66 4 3
35 52 2
44 16 8
19 48 0
88 100 4
10 56 4
49 47 5
42 85 3
18 89 0
26 27 3
61 24 5
1 60 4
52 28 7
58 1 0
95 80 5
47 80 3
27 53 8
41 54 6
13 2 2
68 96 7
43 70 ...

output:

748

result:

ok single line: '748'

Test #19:

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

input:

100 1980
70 50 6
53 13 5
64 62 6
38 16 2
63 46 8
12 68 1
42 31 4
35 26 4
82 41 7
53 8 0
22 18 3
96 37 5
75 32 0
10 100 5
29 74 5
59 2 2
76 49 2
43 44 7
21 6 2
43 93 0
58 60 6
26 14 8
27 87 6
37 35 8
79 65 6
91 74 6
34 31 6
69 18 0
52 65 7
92 7 6
43 67 1
39 48 2
4 27 0
16 95 2
75 59 3
81 97 5
14 96 1...

output:

72

result:

ok single line: '72'

Test #20:

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

input:

100 1980
65 27 5
17 27 6
8 83 8
26 50 0
70 13 0
1 67 1
14 64 2
25 54 6
91 79 6
19 86 4
64 33 4
82 20 6
50 55 8
47 80 2
58 20 0
96 5 2
61 59 7
30 88 3
8 43 0
55 39 3
63 16 5
50 21 7
36 68 7
34 28 3
13 89 2
49 91 2
74 97 0
60 59 2
12 28 3
44 74 7
21 29 5
75 17 7
98 12 1
76 29 3
21 38 8
69 82 3
62 29 5...

output:

1

result:

ok single line: '1'

Test #21:

score: 0
Accepted
time: 9ms
memory: 5340kb

input:

100 2970
94 95 0
2 95 4
44 18 2
89 62 7
17 25 8
72 50 1
100 13 7
98 99 1
48 5 8
38 1 3
23 59 8
4 99 5
60 58 8
59 1 3
29 45 6
71 83 7
60 90 3
3 1 4
27 13 3
66 98 1
63 91 0
44 27 7
81 60 1
5 45 1
8 37 5
77 51 1
36 27 8
82 1 5
1 64 6
2 61 3
9 92 3
90 86 0
28 39 0
89 76 6
65 45 8
8 60 4
47 74 2
31 13 1
...

output:

6033

result:

ok single line: '6033'

Test #22:

score: 0
Accepted
time: 7ms
memory: 5364kb

input:

100 2970
35 37 3
57 17 3
90 76 3
13 91 6
35 97 0
14 78 3
86 16 8
71 64 8
40 37 2
53 86 4
1 99 1
87 8 8
96 39 8
13 92 6
31 4 5
96 5 6
20 22 4
99 28 2
64 92 0
27 46 0
87 94 8
64 8 3
8 78 2
18 9 1
24 99 8
99 44 4
20 86 2
91 64 4
55 81 1
41 63 0
63 77 8
33 4 5
8 36 0
31 83 6
98 22 7
73 68 2
37 67 6
25 8...

output:

1100

result:

ok single line: '1100'

Test #23:

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

input:

100 2970
32 26 3
20 3 2
36 56 8
85 57 6
82 56 6
29 1 4
64 15 8
95 42 8
96 27 0
97 80 5
81 59 0
38 98 6
57 16 5
88 63 2
75 98 4
67 73 8
40 12 7
28 59 5
64 79 0
18 26 4
63 18 2
84 38 2
31 100 4
28 49 4
4 59 7
80 85 5
22 45 6
31 2 4
79 91 5
18 45 8
31 8 8
21 66 4
19 94 4
2 37 5
70 97 2
94 87 7
43 18 8
...

output:

927

result:

ok single line: '927'

Test #24:

score: 0
Accepted
time: 7ms
memory: 5392kb

input:

100 2970
31 94 4
74 40 4
26 70 6
79 25 4
52 73 2
97 87 0
92 45 1
81 63 2
46 82 8
24 61 1
23 44 3
73 75 7
88 99 5
26 99 8
85 41 0
7 43 4
65 96 3
32 24 1
35 63 6
93 18 5
9 13 5
88 23 4
45 75 7
33 92 1
45 77 4
76 21 5
71 73 8
7 95 4
3 28 0
19 21 2
1 37 4
96 58 7
59 61 8
58 34 8
87 89 8
94 14 1
42 50 0
...

output:

99

result:

ok single line: '99'

Test #25:

score: 0
Accepted
time: 8ms
memory: 5388kb

input:

100 2970
92 69 5
29 41 4
55 70 6
70 71 1
54 65 4
22 93 7
73 35 2
98 51 2
9 36 1
35 48 0
1 44 0
67 56 1
13 37 1
89 49 7
38 56 2
76 11 0
8 6 0
49 67 8
72 17 1
37 42 8
39 9 7
42 51 6
78 29 3
85 48 6
39 34 6
31 30 6
44 51 6
65 29 0
52 2 1
30 66 6
50 18 6
13 90 3
96 6 0
70 19 1
96 60 6
62 13 8
49 43 6
97...

output:

1

result:

ok single line: '1'

Test #26:

score: 0
Accepted
time: 8ms
memory: 5380kb

input:

100 3960
46 52 5
99 97 5
35 21 8
69 49 6
81 45 8
93 35 7
62 25 0
31 69 5
33 20 4
49 29 6
79 65 4
18 73 7
70 43 8
73 50 5
49 92 2
33 28 4
84 67 4
24 76 0
33 72 8
59 30 1
61 78 8
47 67 1
69 62 8
1 80 4
10 62 4
56 20 6
12 81 1
39 26 5
75 55 8
62 49 2
84 23 3
63 38 0
58 82 0
59 92 8
86 21 8
38 74 7
33 8...

output:

5460

result:

ok single line: '5460'

Test #27:

score: 0
Accepted
time: 8ms
memory: 5420kb

input:

100 3960
82 69 0
28 19 3
44 57 2
47 88 2
77 53 6
98 95 3
90 5 2
18 38 6
31 25 3
96 49 7
33 19 8
85 15 1
56 92 6
3 52 7
46 68 4
8 58 3
53 1 1
89 15 3
79 95 8
82 44 7
29 93 0
95 55 5
87 70 2
64 54 5
34 31 5
53 37 7
88 25 8
81 19 0
64 9 8
23 99 4
9 2 2
23 59 6
15 98 4
70 13 3
2 36 5
83 91 2
44 30 1
5 4...

output:

2721

result:

ok single line: '2721'

Test #28:

score: 0
Accepted
time: 4ms
memory: 5428kb

input:

100 3960
45 63 6
79 15 0
36 30 3
61 5 3
96 52 3
19 24 7
26 97 8
42 22 5
70 17 8
41 97 6
7 58 0
15 45 6
71 17 5
34 40 5
48 70 6
76 66 1
93 29 8
9 8 0
80 96 0
99 9 3
79 88 1
78 95 1
99 37 2
20 29 1
21 93 7
77 65 1
87 31 8
59 80 7
61 51 6
79 98 2
4 21 6
39 97 8
28 75 4
21 38 0
99 19 8
44 94 6
12 43 4
8...

output:

161

result:

ok single line: '161'

Test #29:

score: 0
Accepted
time: 8ms
memory: 5372kb

input:

100 3960
14 9 7
61 23 4
49 4 4
42 92 2
53 55 7
11 98 7
24 71 1
19 3 6
97 27 5
8 32 0
39 61 2
69 64 3
16 77 2
54 14 1
61 14 6
99 70 1
49 32 6
78 25 5
58 39 5
97 87 4
83 24 6
29 82 2
8 91 4
78 8 7
25 98 1
79 72 8
78 6 1
36 13 5
74 61 1
69 22 1
79 92 6
21 18 5
59 24 8
22 24 4
2 43 2
18 65 0
86 19 1
25 ...

output:

38

result:

ok single line: '38'

Test #30:

score: 0
Accepted
time: 8ms
memory: 5440kb

input:

100 3960
91 18 8
67 10 5
18 90 4
32 21 3
26 14 6
38 71 0
79 66 5
9 77 7
35 39 4
88 92 6
65 67 3
41 92 0
53 95 3
93 76 7
46 62 8
35 6 6
89 50 4
29 36 0
32 93 0
91 27 0
94 85 0
30 83 7
75 5 2
86 29 4
71 23 6
54 22 4
18 17 6
67 43 0
9 72 0
21 70 0
26 68 7
2 6 2
79 85 0
97 31 0
87 51 4
47 33 4
80 89 6
7...

output:

0

result:

ok single line: '0'

Test #31:

score: 0
Accepted
time: 115ms
memory: 19440kb

input:

1000 999
878 482 2
714 611 4
304 667 8
576 119 5
528 996 5
994 645 6
239 614 6
561 449 5
840 558 7
263 780 8
961 950 7
725 978 0
148 110 1
274 803 8
750 493 0
581 755 3
781 688 4
69 825 2
471 892 2
188 986 6
86 783 8
752 554 5
989 756 3
937 489 5
439 740 5
103 974 3
620 598 5
606 189 5
276 757 7
192...

output:

449968

result:

ok single line: '449968'

Test #32:

score: 0
Accepted
time: 112ms
memory: 19388kb

input:

1000 999
418 896 3
664 661 1
293 574 4
846 915 8
479 467 4
793 348 8
754 709 1
759 773 6
515 902 5
444 635 7
150 666 6
304 696 8
182 267 3
330 52 4
751 625 0
206 611 3
186 918 3
907 808 2
806 62 1
982 971 4
222 613 5
619 390 7
783 213 3
783 705 7
909 882 4
796 542 8
451 109 2
568 787 8
148 975 6
40 ...

output:

15394

result:

ok single line: '15394'

Test #33:

score: 0
Accepted
time: 120ms
memory: 19376kb

input:

1000 999
211 50 4
139 940 8
649 154 7
884 554 0
236 838 5
181 590 6
404 414 5
109 740 1
187 148 3
663 707 0
196 23 4
835 9 4
504 609 7
340 127 8
786 697 3
939 147 6
845 57 4
323 663 6
391 467 4
777 165 2
501 320 4
35 16 0
219 164 1
178 744 8
602 26 4
121 338 7
960 949 1
875 212 3
948 926 2
834 838 4...

output:

46343

result:

ok single line: '46343'

Test #34:

score: 0
Accepted
time: 131ms
memory: 19384kb

input:

1000 999
416 749 2
739 681 5
483 414 6
37 513 6
693 905 7
207 592 6
574 952 0
654 797 4
15 621 3
135 881 5
478 234 8
320 23 7
818 25 2
593 316 4
84 748 0
398 904 7
35 431 3
683 361 5
735 964 7
212 288 3
791 325 4
803 25 1
270 997 5
158 681 1
590 302 7
271 575 8
156 830 1
803 436 8
74 155 8
799 999 8...

output:

146983

result:

ok single line: '146983'

Test #35:

score: 0
Accepted
time: 86ms
memory: 19424kb

input:

1000 999
823 170 2
955 55 6
481 959 0
757 610 6
801 73 4
77 761 2
156 795 6
166 488 0
378 163 3
154 847 2
910 490 7
505 436 3
869 664 2
21 253 7
691 150 5
931 834 3
145 539 6
584 154 1
660 361 3
14 626 7
714 673 4
484 27 4
19 945 2
472 400 1
295 308 1
365 501 5
428 843 6
780 240 6
123 38 7
619 995 4...

output:

199999

result:

ok single line: '199999'

Test #36:

score: 0
Accepted
time: 124ms
memory: 19500kb

input:

1000 999
94 465 6
285 646 6
805 726 7
999 907 2
213 188 2
432 484 3
120 773 1
538 786 2
562 252 5
122 130 3
231 552 4
89 32 8
317 721 7
742 422 4
78 210 5
292 308 8
456 886 8
473 515 1
707 725 1
461 946 6
322 873 5
785 761 7
620 948 7
41 151 5
600 839 2
429 208 5
664 170 6
2 13 3
923 891 1
826 932 8...

output:

13469

result:

ok single line: '13469'

Test #37:

score: 0
Accepted
time: 115ms
memory: 19432kb

input:

1000 999
849 362 4
472 187 4
526 71 6
505 525 7
728 729 8
714 3 4
111 29 7
60 310 5
521 221 7
23 444 2
563 962 8
60 146 7
802 216 3
151 857 4
877 48 1
706 317 6
739 478 0
992 923 7
126 998 0
799 433 2
4 50 1
374 327 7
38 174 6
220 586 8
486 438 4
832 275 3
675 945 8
401 636 8
530 87 6
599 442 1
953 ...

output:

90663

result:

ok single line: '90663'

Test #38:

score: 0
Accepted
time: 141ms
memory: 19476kb

input:

1000 999
83 30 7
170 989 5
180 892 6
735 182 3
95 817 0
45 632 4
619 132 4
910 143 1
132 265 2
191 630 6
264 722 4
675 181 8
254 995 0
123 310 6
774 777 0
587 289 8
321 455 0
776 954 8
915 570 2
686 340 6
784 176 2
644 288 6
8 693 2
71 370 8
81 334 3
415 333 1
454 662 5
238 283 5
390 442 1
100 976 3...

output:

132382

result:

ok single line: '132382'

Test #39:

score: 0
Accepted
time: 95ms
memory: 19404kb

input:

1000 999
815 490 0
714 30 1
517 710 5
632 980 2
651 692 3
427 909 8
583 472 0
534 770 5
245 848 5
991 535 5
251 372 1
616 888 4
749 598 7
946 283 8
790 5 5
609 886 0
584 562 4
557 462 0
904 845 0
473 637 7
796 819 8
950 375 7
124 686 5
164 255 6
555 123 4
265 667 5
601 280 1
632 129 2
396 661 0
961 ...

output:

156971

result:

ok single line: '156971'

Test #40:

score: 0
Accepted
time: 100ms
memory: 19380kb

input:

1000 999
832 256 3
933 712 7
714 676 7
583 189 1
954 75 1
37 204 4
299 570 1
266 8 5
567 617 0
668 358 2
647 142 6
682 389 3
6 344 7
566 778 8
248 274 0
614 206 7
727 522 4
444 511 7
76 147 2
688 358 6
634 633 3
242 788 5
772 47 4
749 530 6
505 440 1
99 740 4
638 465 7
569 222 5
608 586 7
729 525 1
...

output:

12437

result:

ok single line: '12437'

Test #41:

score: 0
Accepted
time: 128ms
memory: 19520kb

input:

1000 999
714 978 4
755 896 5
564 425 5
744 512 1
721 274 3
686 404 8
471 980 2
671 149 6
107 510 6
344 574 2
739 205 4
746 385 8
703 29 7
28 740 6
121 308 7
379 385 5
684 170 5
82 361 8
322 663 0
177 830 8
81 36 4
212 334 8
132 662 1
273 752 6
315 657 2
33 440 4
110 409 0
696 460 7
710 566 1
574 55 ...

output:

91631

result:

ok single line: '91631'

Test #42:

score: 0
Accepted
time: 140ms
memory: 19388kb

input:

1000 999
124 860 3
7 603 2
801 595 1
501 408 5
117 836 3
159 599 8
24 528 2
813 872 1
250 710 6
837 650 4
816 783 5
983 96 4
50 450 8
865 497 6
465 45 5
337 982 4
582 581 7
696 173 0
683 163 1
855 20 4
182 933 0
949 990 5
557 185 4
302 292 5
807 549 0
97 521 0
420 499 1
891 738 6
635 82 0
665 946 0
...

output:

138564

result:

ok single line: '138564'

Test #43:

score: 0
Accepted
time: 104ms
memory: 19496kb

input:

1000 999
250 635 16
93 501 7
799 182 16
903 999 1
385 300 2
172 393 1
765 707 11
268 762 11
705 667 15
540 96 5
994 574 16
786 674 3
836 52 12
401 80 15
799 375 6
621 801 16
858 301 10
738 758 15
999 731 3
235 282 10
881 133 9
345 975 3
23 743 7
785 962 9
175 126 13
376 18 0
417 815 1
692 982 2
395 ...

output:

821919

result:

ok single line: '821919'

Test #44:

score: 0
Accepted
time: 105ms
memory: 19388kb

input:

1000 999
243 492 2
346 10 4
147 699 16
423 377 1
24 722 14
454 785 15
505 744 12
784 543 18
660 275 18
340 121 20
254 993 16
487 734 7
747 21 15
94 236 16
578 718 15
857 375 1
704 949 6
611 300 19
41 184 15
886 133 16
631 491 5
242 386 18
275 320 7
19 495 11
915 97 1
174 617 11
889 81 3
130 272 7
86...

output:

351865

result:

ok single line: '351865'

Test #45:

score: 0
Accepted
time: 97ms
memory: 19436kb

input:

1000 999
603 787 8
957 779 19
372 311 18
870 719 6
812 348 1
605 317 18
789 929 17
208 866 4
183 835 16
324 145 15
911 626 16
603 828 19
903 344 1
620 89 3
942 465 17
703 537 4
302 180 17
782 699 10
223 387 8
296 20 6
495 176 2
848 480 13
338 205 15
514 430 16
894 865 1
376 774 7
102 935 6
746 668 1...

output:

13502

result:

ok single line: '13502'

Test #46:

score: 0
Accepted
time: 126ms
memory: 19384kb

input:

1000 999
139 162 19
172 687 15
522 357 8
279 587 1
98 24 18
584 511 15
494 201 7
450 679 18
616 319 10
497 90 4
543 791 4
1000 656 7
928 499 5
675 645 12
158 451 14
33 551 11
844 600 11
431 793 14
549 452 1
652 528 17
536 55 18
531 427 17
159 416 5
173 743 17
636 739 2
847 993 18
952 383 1
277 883 1...

output:

224267

result:

ok single line: '224267'

Test #47:

score: 0
Accepted
time: 98ms
memory: 19496kb

input:

1000 999
118 699 12
657 522 20
272 832 4
162 446 12
94 382 10
456 465 11
398 611 3
475 513 2
841 313 0
109 892 9
470 637 14
479 942 11
574 906 8
121 285 3
1 312 4
960 259 2
111 719 5
279 241 13
286 337 14
59 984 17
433 397 17
779 549 16
201 722 13
770 836 3
871 626 0
721 557 2
753 766 11
425 467 17
...

output:

1433723

result:

ok single line: '1433723'

Test #48:

score: 0
Accepted
time: 104ms
memory: 19424kb

input:

1000 999
547 225 19
178 491 2
493 637 11
955 357 1
46 813 20
571 580 19
385 121 11
134 893 12
456 112 11
997 387 18
135 692 15
716 397 14
631 459 0
181 877 9
626 813 11
722 653 2
720 416 5
53 403 20
765 771 17
951 508 17
78 455 13
190 330 15
834 182 20
843 393 2
273 270 6
208 754 18
321 908 13
702 1...

output:

99344

result:

ok single line: '99344'

Test #49:

score: 0
Accepted
time: 100ms
memory: 19444kb

input:

1000 999
298 756 1
333 693 6
300 443 7
849 17 7
313 772 17
556 509 2
995 174 9
266 503 9
431 67 8
186 196 17
476 136 15
183 360 15
540 88 6
19 566 17
746 274 5
161 71 0
157 22 11
36 665 20
642 409 14
858 816 15
631 654 4
981 94 11
88 830 5
570 97 2
335 480 15
491 137 13
278 701 5
915 425 19
21 120 3...

output:

18387

result:

ok single line: '18387'

Test #50:

score: 0
Accepted
time: 115ms
memory: 19436kb

input:

1000 999
677 173 9
418 87 2
201 291 8
184 546 8
42 121 17
195 423 15
985 220 1
362 609 8
762 336 11
959 961 13
916 65 16
221 434 10
799 980 13
847 192 17
863 913 18
325 126 15
922 933 1
334 880 19
339 452 2
986 115 14
159 750 12
731 227 2
894 312 4
86 724 14
167 408 0
717 158 0
412 226 3
829 93 1
76...

output:

442887

result:

ok single line: '442887'

Test #51:

score: 0
Accepted
time: 113ms
memory: 19472kb

input:

1000 999
666 201 17
963 91 15
972 29 2
967 699 15
735 536 17
519 926 18
735 659 10
451 337 12
496 149 15
21 394 11
367 340 3
182 741 19
220 59 19
271 39 14
819 983 15
219 667 13
193 259 14
940 489 8
652 528 5
841 591 13
781 135 2
663 99 12
123 717 5
526 557 0
718 259 5
462 279 2
825 877 19
117 558 3...

output:

513588

result:

ok single line: '513588'

Test #52:

score: 0
Accepted
time: 109ms
memory: 19500kb

input:

1000 999
552 704 1
714 791 0
662 601 0
370 52 7
756 881 16
434 593 9
788 905 18
93 737 8
196 130 3
261 216 0
6 441 6
534 817 16
737 173 14
344 34 20
416 60 7
639 186 7
835 797 12
446 19 13
583 806 20
143 814 11
534 672 11
262 496 16
75 49 8
799 531 14
795 743 8
46 658 9
628 875 8
858 765 18
698 962 ...

output:

108374

result:

ok single line: '108374'

Test #53:

score: 0
Accepted
time: 120ms
memory: 19444kb

input:

1000 999
798 120 15
737 362 20
552 452 2
563 890 17
587 71 12
883 971 11
14 571 15
931 854 3
595 334 8
495 423 15
615 18 2
524 660 16
856 651 19
306 846 13
110 655 16
327 163 0
732 671 18
997 958 20
43 301 16
856 986 6
335 831 16
68 226 20
648 818 6
601 836 9
263 470 19
511 614 0
428 746 13
264 575 ...

output:

31592

result:

ok single line: '31592'

Test #54:

score: 0
Accepted
time: 114ms
memory: 19384kb

input:

1000 999
23 944 6
710 55 19
334 663 15
283 40 17
954 931 19
796 135 19
91 228 7
454 757 0
535 854 16
816 631 3
475 941 20
629 601 4
35 642 18
450 583 14
277 176 10
952 415 8
849 243 14
142 305 18
117 630 10
542 49 0
386 433 4
847 690 9
862 477 4
891 94 10
877 470 4
774 149 0
880 867 3
87 230 17
933 ...

output:

361087

result:

ok single line: '361087'

Test #55:

score: 0
Accepted
time: 83ms
memory: 19476kb

input:

1000 999
835 220 18
360 918 972
683 633 729
335 875 266
585 231 575
136 52 997
712 124 697
964 146 469
847 232 642
566 380 558
236 899 530
681 249 472
458 578 322
894 18 10
137 236 30
600 66 589
841 366 463
656 222 804
854 650 129
123 708 136
512 578 896
420 847 856
354 319 577
807 124 201
507 314 2...

output:

1342817

result:

ok single line: '1342817'

Test #56:

score: 0
Accepted
time: 101ms
memory: 19500kb

input:

1000 999
677 78 214
899 414 5
604 64 754
23 957 452
573 94 940
992 196 554
441 520 537
276 973 878
753 222 29
315 287 208
833 811 485
473 592 402
676 520 257
558 702 173
305 280 608
115 212 538
965 523 71
857 636 732
36 976 964
241 364 876
125 829 490
661 795 990
122 967 56
425 756 934
124 933 920
6...

output:

1622772

result:

ok single line: '1622772'

Test #57:

score: 0
Accepted
time: 100ms
memory: 19376kb

input:

1000 999
567 929 984
731 3 428
828 888 70
813 157 882
29 237 909
643 17 524
974 397 134
863 538 572
374 534 670
512 147 50
453 775 981
665 488 150
300 82 757
462 265 118
498 657 724
278 840 822
77 237 930
5 187 135
296 827 896
663 708 897
496 521 722
10 498 367
367 850 883
349 269 888
894 487 526
52...

output:

6395642

result:

ok single line: '6395642'

Test #58:

score: 0
Accepted
time: 121ms
memory: 19484kb

input:

1000 999
59 765 854
320 401 427
91 919 855
124 572 716
374 996 323
22 372 336
352 406 573
492 172 790
847 120 287
417 692 991
504 81 435
316 887 683
621 417 814
828 334 226
502 33 853
724 757 237
417 580 920
103 852 921
137 860 802
615 438 564
840 463 524
805 849 883
292 387 891
935 972 692
569 315 ...

output:

18419085

result:

ok single line: '18419085'

Test #59:

score: 0
Accepted
time: 92ms
memory: 19468kb

input:

1000 999
839 763 831
825 788 510
115 526 173
839 452 241
346 851 472
498 785 324
891 475 930
976 846 504
561 738 185
424 942 828
168 251 968
449 103 221
79 706 437
660 743 652
110 565 812
125 749 485
393 208 439
7 806 763
517 236 546
490 504 486
840 907 932
437 281 650
362 951 444
403 354 781
721 40...

output:

1476436

result:

ok single line: '1476436'

Test #60:

score: 0
Accepted
time: 78ms
memory: 19468kb

input:

1000 999
723 967 297
565 363 593
375 336 259
468 42 596
483 852 999
698 214 837
924 236 447
720 835 406
302 855 726
533 873 812
326 814 221
606 690 802
60 398 402
597 384 741
663 261 574
52 637 707
666 82 210
122 54 521
650 284 93
744 605 780
64 341 187
69 902 258
440 517 529
905 137 774
436 641 279...

output:

851148

result:

ok single line: '851148'

Test #61:

score: 0
Accepted
time: 124ms
memory: 19472kb

input:

1000 999
850 656 892
804 174 981
749 373 737
241 191 189
482 666 829
824 822 88
999 982 203
41 195 874
111 199 696
579 295 534
304 859 192
117 825 783
792 257 718
164 563 367
457 334 935
536 361 494
111 455 294
910 887 598
785 109 100
553 941 459
733 167 636
652 919 989
59 320 218
160 180 220
553 63...

output:

8757038

result:

ok single line: '8757038'

Test #62:

score: 0
Accepted
time: 124ms
memory: 19380kb

input:

1000 999
389 908 776
453 698 964
977 585 751
90 329 866
725 481 69
438 622 373
55 619 777
904 64 703
897 682 135
858 527 182
739 981 736
723 133 44
534 920 673
339 148 210
541 959 138
510 148 491
186 124 908
528 299 632
846 97 342
828 574 905
371 139 809
317 72 949
454 866 145
143 854 592
602 379 24...

output:

16253723

result:

ok single line: '16253723'

Test #63:

score: 0
Accepted
time: 86ms
memory: 19468kb

input:

1000 999
493 145 56
620 386 774
920 735 99
812 537 668
166 780 548
433 183 983
125 472 265
404 677 315
662 997 776
593 515 12
557 142 744
594 133 694
701 27 341
46 322 717
240 325 966
517 842 468
362 28 974
656 226 659
268 182 278
497 738 925
926 540 917
882 692 139
564 568 573
111 206 125
372 733 2...

output:

1751619

result:

ok single line: '1751619'

Test #64:

score: 0
Accepted
time: 92ms
memory: 19480kb

input:

1000 999
461 986 560
727 529 734
808 263 642
232 979 934
202 308 118
442 312 830
869 661 967
716 436 425
442 579 418
431 228 858
224 697 371
230 773 7
981 470 387
910 671 329
37 637 753
636 32 585
262 384 782
902 221 741
163 14 754
281 240 577
633 259 527
979 125 871
152 450 528
589 391 547
778 626 ...

output:

1520300

result:

ok single line: '1520300'

Test #65:

score: 0
Accepted
time: 108ms
memory: 19432kb

input:

1000 999
833 565 80
902 301 551
831 985 828
125 513 788
115 877 285
459 264 233
263 708 477
366 889 687
904 797 861
389 977 769
416 957 167
251 579 353
676 726 767
35 26 719
970 601 239
266 323 85
301 917 657
540 25 839
164 132 406
367 878 387
813 55 837
254 739 978
574 729 237
342 589 913
941 817 4...

output:

4319499

result:

ok single line: '4319499'

Test #66:

score: 0
Accepted
time: 107ms
memory: 19468kb

input:

1000 999
348 826 116
427 569 799
589 875 353
432 909 962
392 979 57
873 140 477
244 356 40
816 69 860
102 832 711
336 126 954
459 591 665
351 103 941
717 453 238
559 712 15
377 943 514
140 899 576
820 939 260
910 847 695
465 675 844
233 38 301
329 23 832
383 285 185
399 872 707
587 947 772
660 609 9...

output:

25097404

result:

ok single line: '25097404'

Test #67:

score: 0
Accepted
time: 108ms
memory: 19372kb

input:

1000 999
980 646 2992
361 125 3542
632 511 6512
213 461 1072
1000 552 2695
858 962 2197
492 261 1612
604 434 2543
298 791 6141
736 882 7575
154 493 9490
310 220 3013
843 8 2465
250 812 1646
210 867 6916
374 333 812
118 459 8499
650 375 964
154 155 209
582 474 7401
272 544 5332
933 868 3034
698 366 4...

output:

155345705

result:

ok single line: '155345705'

Test #68:

score: 0
Accepted
time: 114ms
memory: 19432kb

input:

1000 999
406 335 3081
912 673 3169
187 404 6486
632 690 1744
889 263 6015
642 606 3522
870 862 3338
34 933 6049
870 808 4313
771 587 5104
94 788 9906
77 65 5618
258 427 2398
390 232 789
180 950 5024
430 819 6528
530 474 578
144 37 9648
938 989 3268
419 309 5573
646 50 2160
408 495 5857
884 578 7191
...

output:

110093020

result:

ok single line: '110093020'

Test #69:

score: 0
Accepted
time: 117ms
memory: 19340kb

input:

1000 999
372 337 4321
73 940 1446
100 108 9064
973 556 7135
690 322 4916
990 882 7586
818 698 4407
704 20 5797
870 410 225
391 257 4149
204 826 1470
155 522 9383
824 163 5994
466 369 4472
205 847 7248
189 850 8725
744 188 3541
947 244 6381
411 834 3392
609 344 2510
381 865 2824
972 343 9414
76 451 2...

output:

179272264

result:

ok single line: '179272264'

Test #70:

score: 0
Accepted
time: 110ms
memory: 19444kb

input:

1000 999
77 419 5979
214 135 6058
468 856 3783
752 304 447
889 804 2170
406 411 6668
135 978 4686
86 980 8329
116 376 798
651 592 8346
288 166 7445
173 731 290
511 576 8386
843 507 977
172 303 3977
76 267 9724
990 942 3280
774 672 7140
370 575 4622
301 45 904
179 382 1522
224 892 6955
287 672 6390
9...

output:

70318884

result:

ok single line: '70318884'

Test #71:

score: 0
Accepted
time: 124ms
memory: 19432kb

input:

1000 999
309 514 5544
770 172 7916
443 960 1460
675 650 6342
231 488 3218
173 693 3658
40 980 2131
819 380 7223
199 983 9931
626 334 2927
324 858 3823
644 891 5661
213 316 8777
664 544 9985
962 298 1522
939 341 8923
47 259 2790
697 162 3869
277 219 4217
645 586 5619
497 510 6898
584 597 9647
666 285...

output:

112277522

result:

ok single line: '112277522'

Test #72:

score: 0
Accepted
time: 112ms
memory: 19368kb

input:

1000 999
354 514 7780
977 482 5851
854 739 9795
565 732 410
223 845 4841
157 144 4284
336 365 8358
766 331 3924
880 65 9244
272 716 6527
982 811 651
344 312 9772
757 52 6846
111 41 9035
134 842 9009
180 332 5733
631 975 4763
978 60 2488
873 218 3909
538 621 3333
565 280 5205
783 332 7563
402 324 226...

output:

157135340

result:

ok single line: '157135340'

Test #73:

score: 0
Accepted
time: 112ms
memory: 19380kb

input:

1000 999
348 238 3552
877 401 5104
943 754 1868
293 552 5705
804 560 8554
934 230 6517
554 268 6188
437 233 8125
281 622 8046
854 567 6379
834 255 1278
396 72 8010
86 180 584
66 948 5875
693 492 762
734 993 54
250 769 1721
799 781 1971
575 808 1477
760 58 7305
879 355 8062
513 248 8431
617 222 5908
...

output:

90162817

result:

ok single line: '90162817'

Test #74:

score: 0
Accepted
time: 113ms
memory: 19480kb

input:

1000 999
858 30 8449
503 497 8700
61 920 4521
427 814 4029
212 242 2682
147 317 269
807 187 8164
71 379 6352
101 903 3182
730 202 1671
432 68 7131
823 736 2132
679 269 5733
85 358 1265
413 557 4000
208 719 7610
257 929 8583
508 584 8907
99 210 5695
827 759 1294
422 883 9481
718 421 7089
146 69 3593
...

output:

158766600

result:

ok single line: '158766600'

Test #75:

score: 0
Accepted
time: 119ms
memory: 19428kb

input:

1000 999
462 194 9502
504 155 892
675 222 6772
291 850 5684
759 132 4875
881 787 7122
32 727 8048
397 771 6555
814 752 5991
683 827 6898
155 239 8837
333 584 871
977 436 3660
620 688 215
858 168 4351
67 138 9604
542 537 4571
662 916 3201
678 876 8340
902 312 4559
396 441 4631
765 869 1757
804 100 69...

output:

178223186

result:

ok single line: '178223186'
English 繁體中文 简体中文

Server Time: 2024-12-05 05:11:14 | OpenSource Project