【ARC096-b】Static Sushi

Source and Judge

ARC096-b

Problem

【Description】
给出包含n个寿司的圆环的圆周c,并按顺时针给出其与源点的顺时针距离
从源点出发,从任何一个位置离开,总收获=寿司卡路里和-路上花费和
【Input】
N C
x1 v1
x2 v2
:
xN vN
【Output】
最大收获
【Limited conditions】
1≤N≤10^5
2≤C≤10^14
1≤x1<x2<…<xN<C
1≤vi≤10^9
【Sample input】
3 20
2 80
9 1
16 120
【Sample output】
192
【Sample explanation】

Record

2h

Analysis

请先思考

考试的时候傻了,居然还想单调队列……然后到目前为止还是wa两个点
代码太丑,何况还是错的,就不贴了

其实把前面的信息记录一下,然后后面就简单地取mx就好了

Code

请先思考
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//Zory in 2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
typedef long long ll;
typedef unsigned long long ull;
ll mymax(ll x,ll y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
//*******************全局常量*******************
const int MAXN=110000;
//*******************全局定义*******************
ll f[MAXN],g[MAXN];//顺时针,逆时针
ll x[MAXN],v[MAXN];
//*******************实现*******************
//*******************主函数*******************
int main()
{
//freopen("tmp.in","r",stdin);
int n;ll c;scanf("%d%lld",&n,&c);
for(int i=1;i<=n;i++) scanf("%lld%lld",&x[i],&v[i]);
ll ans=0,sum;
sum=0;for(int i=1;i<=n;i++) sum+=v[i],f[i]=sum-x[i],ans=mymax(ans,f[i]);
sum=0;for(int i=n;i>=1;i--) sum+=v[i],g[i]=sum-(c-x[i]),ans=mymax(ans,g[i]);
ll mx;
mx=0;for(int i=n-1;i>=1;i--) mx=mymax(mx,g[i+1]),ans=mymax(ans,f[i]+mx-x[i]);
mx=0;for(int i=2;i<=n;i++) mx=mymax(mx,f[i-1]),ans=mymax(ans,g[i]+mx-(c-x[i]));
printf("%lld",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-04/Static_Sushi.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%