NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#206628	#3709. road	wyz_	100	11ms	1636kb	C++11	831b	2024-07-23 19:11:13	2024-07-23 20:13:48

answer

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

int n,pre = 1, mn = INT_MAX, d[100005];
ll ans;

void f(int l,int r,int mn){
	ans += mn;
	int mn2 = INT_MAX, pre = l;
	bool flag = 0;
	for(int i = l; i <= r; i++){
		if(d[i])
			d[i] -= mn;
		if(d[i]){
			if(!flag)
				pre = i, flag = 1;
			mn2 = min(mn2,d[i]);
		}
		else{
			if(flag)
				f(pre,i-1,mn2), mn2 = INT_MAX;
			flag = 0;
		}
	}
	if(flag)
		f(pre,r,mn2);
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin >> n;
	bool flag = 0;
	for(int i = 1; i <= n; i++){
		cin >> d[i];
		if(d[i]){
			if(!flag)
				pre = i, flag = 1;
			mn = min(mn,d[i]);
		}
		else{
			if(flag)
				f(pre,i-1,mn), mn = INT_MAX;
			flag = 0;
		}
	}
	if(flag)
		f(1,n,mn);
	
	cout << ans;
	
	return 0;
}

源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10

Accepted

time: 1ms

memory: 1248kb

input:

3
3 1 1

output:

result:

ok single line: '3'

Test #2:

score: 10

Accepted

time: 0ms

memory: 1252kb

input:

6
6 8 3 2 0 9

output:

result:

ok single line: '17'

Test #3:

score: 10

Accepted

time: 0ms

memory: 1248kb

input:

10
7 18 29 0 47 0 41 40 28 7

output:

result:

ok single line: '117'

Test #4:

score: 10

Accepted

time: 0ms

memory: 1252kb

input:

20
99 27 61 62 17 79 61 22 13 49 71 61 8 81 67 80 47 83 88 30

output:

result:

ok single line: '381'

Test #5:

score: 10

Accepted

time: 0ms

memory: 1248kb

input:

50
12 74 78 33 23 58 83 76 59 77 85 25 18 98 16 100 79 88 36 53 72 95 93 39 78 5 15 56 26 62 65 57 6...

output:

result:

ok single line: '755'

Test #6:

score: 10

Accepted

time: 0ms

memory: 1252kb

input:

250
10 907 960 459 737 614 650 664 12 662 983 803 56 704 255 356 966 746 486 719 496 37 891 976 242 ...

output:

result:

ok single line: '44356'

Test #7:

score: 10

Accepted

time: 0ms

memory: 1256kb

input:

1000
198 276 974 388 435 817 424 649 959 180 70 662 283 526 58 973 773 770 981 578 416 566 28 645 23...

output:

result:

ok single line: '163692'

Test #8:

score: 10

Accepted

time: 1ms

memory: 1288kb

input:

10000
756 214 223 686 31 864 369 733 235 623 150 944 691 961 63 753 621 913 534 787 771 344 669 505 ...

output:

result:

ok single line: '1667465'

Test #9:

score: 10

Accepted

time: 0ms

memory: 1452kb

input:

50000
8376 7573 9441 5255 8061 7257 9681 5433 3130 2350 5791 4395 6264 5621 9138 5434 7483 611 2845 ...

output:

83301706

result:

ok single line: '83301706'

Test #10:

score: 10

Accepted

time: 9ms

memory: 1636kb

input:

100000
4429 7325 4658 8976 1076 9705 2591 5563 8327 2532 3195 98 760 4850 3310 1567 4893 8353 5623 9...

output:

166653075

result:

ok single line: '166653075'