首页 > 代码库 > BZOJ 1537 Aut- The Bus
BZOJ 1537 Aut- The Bus
BIT.
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100050 using namespace std; long long n,m,k,hash[maxn],tot=0,t[maxn],f[maxn]; struct pnt { long long x,y,w; }p[maxn]; bool cmp(pnt x,pnt y) { if (x.x!=y.x) return x.x<y.x; return x.y<y.y; } long long find(long long x) { return lower_bound(hash+1,hash+tot+1,x)-hash; } long long lowbit(long long x) {return (x&(-x));} long long ask(long long x) { long long ret=0; for (long long i=x;i>=1;i-=lowbit(i)) ret=max(ret,t[i]); return ret; } void modify(long long x,long long val) { for (long long i=x;i<=tot;i+=lowbit(i)) t[i]=max(t[i],val); } int main() { scanf("%lld%lld%lld",&n,&m,&k); for (long long i=1;i<=k;i++) { scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].w); hash[++tot]=p[i].y; } k++;p[k].x=n;p[k].y=m;p[k].w=0;hash[++tot]=m; sort(p+1,p+k+1,cmp);sort(hash+1,hash+tot+1);tot=unique(hash+1,hash+tot+1)-hash-1; for (long long i=1;i<=k;i++) { long long ret=find(p[i].y); f[i]=ask(ret)+p[i].w;modify(ret,f[i]); } printf("%lld\n",f[k]); return 0; }
BZOJ 1537 Aut- The Bus
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。