首页 > 其他 > 详细

Codeforces Round #321 (Div. 2) B. Kefa and Company

时间:2015-09-23 10:11:07      阅读:693      评论:0      收藏:0      [点我收藏+]

排序以后O(n)枚举尾部。头部单调,维护一下就好。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define LOCAL
const int maxn = 1e5+5;
struct Node
{
    int m,s;
    void IN(){ scanf("%d%d",&m,&s); }
    bool operator < (const Node&rh) const {
        return m < rh.m;
    }
}nd[maxn];

ll ss[maxn];

int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    int n,d; scanf("%d%d",&n,&d);
    for(int i = 1; i <= n; i++){
        nd[i].IN();
    }
    sort(nd+1,nd+1+n);
    for(int i = 1; i <= n; i++){
        ss[i] = ss[i-1]+nd[i].s;
    }
    ll ans = 0;
    for(int i = 1,j = 1; i <= n; i++){
        while(j<n && nd[j+1].m - nd[i].m < d) j++;
        ans = max(ans,ss[j]-ss[i-1]);
    }
    printf("%I64d",ans);
    return 0;
}

 

Codeforces Round #321 (Div. 2) B. Kefa and Company

原文:http://www.cnblogs.com/jerryRey/p/4831291.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!