UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214381#2767. 摆烂one_zero_four_zero0850ms24668kbC++11769b2024-11-18 19:15:182024-11-19 08:28:31

answer

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

int N, maxn = -1, itmax;
int t[2000006], a[2000006];
int dp[2000006];
stack<int> stk;

int main(){
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
    freopen("../data.out", "w", stdout);
#endif

	scanf("%d", &N);
	for (int i = 1; i <= N; i ++){
		scanf("%d %d", &t[i], &a[i]);
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	for (int i = 1; i <= N; i ++){
		while (stk.size() && a[stk.top()] <= a[i]) stk.pop();
		if (!stk.size()){
			stk.push(i);
			dp[i] = t[i] + 2 * a[i];
			continue;
		}
		dp[i] = max(t[i], dp[stk.top()]) + 2 * a[i];
		if (dp[i] - dp[stk.top()] < 2 * (a[stk.top()] - a[i])) stk.push(i);
	}
	printf("%d\n", dp[N]);

    return 0;
}

详细

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

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 9052kb

input:

20
12513359 382258501
49946422 294259408
61782741 259996549
128874560 457675284
152578248 511428369
...

output:

1685889849

result:

wrong answer 1st numbers differ - expected: '2781551734', found: '1685889849'

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 0ms
memory: 9060kb

input:

1000
132699 718470029
234343 395421925
1290414 393017296
1399642 607415822
1402810 515471990
2008288...

output:

1245177914

result:

wrong answer 1st numbers differ - expected: '2991845504', found: '1245177914'

Subtask #3:

score: 0
Wrong Answer

Test #20:

score: 0
Wrong Answer
time: 23ms
memory: 9832kb

input:

100000
9326 430414358
13368 156324232
15149 550951304
22296 345034579
22578 397947033
37137 49312905...

output:

1557217627

result:

wrong answer 1st numbers differ - expected: '2999984291', found: '1557217627'

Subtask #4:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 403ms
memory: 24668kb

input:

2000000
181 24185667
293 532288461
1433 921996635
1694 629544979
2540 173534643
2662 963172401
3159 ...

output:

1790857124

result:

wrong answer 1st numbers differ - expected: '2999999604', found: '1790857124'

Subtask #5:

score: 0
Wrong Answer

Test #42:

score: 0
Wrong Answer
time: 422ms
memory: 24668kb

input:

2000000
684 624071334
1181 709831992
1397 43325781
1938 430417709
4157 60566309
4568 912818933
5265 ...

output:

-1754768743

result:

wrong answer 1st numbers differ - expected: '2999999891', found: '-1754768743'