20161109
binary-search 를 이용한 O(nlgn)
#include <iostream> // standard input & output cout cin
#include <cstdio> // scanf printfsssss
#include <vector> // std::vector
#include <algorithm>
#include <string> // std::string
#include <queue> // std::queue
#include <cstring> // memset
#include <set> // std::set
#include <utility> // std::pair, std::make_pair
#include <map>
#include <list>
#include <stack>
#include <deque>
#include <cmath>
#include <climits>
#include <cassert>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef long double ld;
#define mod 1000000007
const char newline = '\n';
ll powmod(ll a, ll b) {ll res=1; a %= mod; assert(b >= 0); for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}
const int MAX_N = 300001;
int n,s;
vector<pair<int, int> > a;
vector<int> bb;
int dp[MAX_N];
int p[MAX_N];
int main(int argc, char **argv)
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin>>n>>s;
a.resize(n+1);
bb.resize(n+1);
for(int i = 1; i <= n ; i++)
{
cin>>a[i].fi>>a[i].se;
}
sort(a.begin(), a.end());
bb[0] = 0;
for(int i = 1 ; i <= n ; i++)
{
bb[i] = a[i].fi;
}
dp[0] = 0;
int answer = 0;
for(int i = 1; i<= n ; i++)
{
int j = lower_bound(bb.begin(), bb.end(), bb[i] - s + 1) - bb.begin();
j--;
if(j == i)
{
dp[i] = a[i].se;
}
else
{
dp[i] = dp[j] + a[i].se;
}
dp[i] = max(dp[i] , dp[i-1]);
}
// for(int i = 0; i <= n ;i++)
// {
// cout<<dp[i]<<' ';
// }
// cout<<endl;
cout<< *max_element(dp, dp+n+1)<<newline;
return 0;
}
투포인터를 활용한 O(N)
#include <iostream> // standard input & output cout cin
#include <cstdio> // scanf printfsssss
#include <vector> // std::vector
#include <algorithm>
#include <string> // std::string
#include <queue> // std::queue
#include <cstring> // memset
#include <set> // std::set
#include <utility> // std::pair, std::make_pair
#include <map>
#include <list>
#include <stack>
#include <deque>
#include <cmath>
#include <climits>
#include <cassert>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef long double ld;
#define mod 1000000007
const char newline = '\n';
ll powmod(ll a, ll b) {ll res=1; a %= mod; assert(b >= 0); for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}
const int MAX_N = 300001;
int n,s;
vector<pair<int, int> > a;
int dp[MAX_N];
int id, answer;
int main(int argc, char **argv)
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin>>n>>s;
a.resize(n+1);
for(int i = 1; i <= n ; i++)
{
cin>>a[i].fi>>a[i].se;
}
sort(a.begin(), a.end());
id = 1;
int Maxi = 0;
for(int i = 1 ; i <= n ; i++)
{
while(id <= n && a[id].fi + s <= a[i].fi) Maxi = max(Maxi, dp[id++]);
dp[i] = Maxi + a[i].se;
answer = max(answer, dp[i]);
}
cout<<answer<<newline;
return 0;
}