This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef pair <int,int> ppair;
pair <int,int> A[100001];
pair <int,int> B[100001];
pair <ppair,int> Stick[100001];
int N, L;
long long D[2][100001], Ans;
void input(void)
{
int i, t, d, Acnt=0, Bcnt=0;
scanf("%d %d",&N,&L);
for(i=1 ; i<=N ; i++)
{
scanf("%d %d",&t,&d);
A[i]=make_pair(t,i);
B[i]=make_pair(d,i);
Stick[i].second=abs(t-d)+L;
}
sort(A+1,A+N+1);
sort(B+1,B+N+1);
A[0].first=B[0].first=-1;
for(i=1 ; i<=N ; i++)
{
if(A[i].first!=A[i-1].first)
Acnt++;
if(B[i].first!=B[i-1].first)
Bcnt++;
Stick[A[i].second].first.first=Acnt;
Stick[B[i].second].first.second=Bcnt;
}
sort(Stick+1,Stick+N+1);
}
void process(void)
{
int i;
long long temp;
for(i=1 ; i<=N ; i++)
{
temp=0;
if(D[0][Stick[i].first.first]<D[1][Stick[i].first.second]+Stick[i].second)
{
temp=D[1][Stick[i].first.second]+Stick[i].second;
if(Ans<temp)
Ans=temp;
}
if(D[1][Stick[i].first.second]<D[0][Stick[i].first.first]+Stick[i].second)
{
D[1][Stick[i].first.second]=D[0][Stick[i].first.first]+Stick[i].second;
if(Ans<D[1][Stick[i].first.second])
Ans=D[1][Stick[i].first.second];
}
if(temp)
D[0][Stick[i].first.first]=temp;
}
}
void output(void)
{
printf("%lld",Ans);
}
int main(void)
{
input();
process();
output();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |