#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long inf=1e18;
long long n,m,d,ps[2][400069];
pair<long long,pair<long long,long long>> a[400069];
int main()
{
long long i,ii,k,l,w,c[2]={0,0},e,p,z=0;
scanf("%lld%lld%lld",&n,&m,&d);
for(i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&k,&w,&l);
a[i*4-3]={k-1,{0,1}};
a[i*4-2]={k+w-1,{1,1}};
a[i*4-1]={l,{0,-1}};
a[i*4]={l,{1,-1}};
}
sort(a+1,a+n*4+1);
for(i=1;i<=n*4;i++)
{
k=a[i].fr;
e=a[i].sc.fr;
w=a[i].sc.sc;
for(ii=0;ii<2;ii++)
{
ps[ii][i]=ps[ii][i-1];
}
c[e]+=w;
if(!e)
{
if(c[0]>=m&&c[0]-w<m)
{
ps[0][i]-=c[1];
ps[1][i]-=k*c[1];
}
else if(c[0]<m&&c[0]-w>=m)
{
ps[0][i]+=c[1];
ps[1][i]+=k*c[1];
}
}
else if(c[0]>=m)
{
ps[0][i]-=w;
ps[1][i]-=k*w;
}
p=upper_bound(a+1,a+n*4+1,mp(k-d,mp(inf,inf)))-a-1;
z=max(z,ps[1][i]+k*-ps[0][i]-(ps[1][p]+(k-d)*-ps[0][p]));
}
printf("%lld\n",z);
}
Compilation message
autobahn.cpp: In function 'int main()':
autobahn.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | scanf("%lld%lld%lld",&n,&m,&d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
autobahn.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | scanf("%lld%lld%lld",&k,&w,&l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
460 KB |
Output is correct |
| 13 |
Correct |
1 ms |
512 KB |
Output is correct |
| 14 |
Correct |
2 ms |
460 KB |
Output is correct |
| 15 |
Correct |
1 ms |
460 KB |
Output is correct |
| 16 |
Correct |
1 ms |
460 KB |
Output is correct |
| 17 |
Correct |
1 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
460 KB |
Output is correct |
| 13 |
Correct |
1 ms |
512 KB |
Output is correct |
| 14 |
Correct |
2 ms |
460 KB |
Output is correct |
| 15 |
Correct |
1 ms |
460 KB |
Output is correct |
| 16 |
Correct |
1 ms |
460 KB |
Output is correct |
| 17 |
Correct |
1 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
460 KB |
Output is correct |
| 21 |
Correct |
104 ms |
15816 KB |
Output is correct |
| 22 |
Correct |
100 ms |
15852 KB |
Output is correct |
| 23 |
Correct |
103 ms |
15812 KB |
Output is correct |
| 24 |
Correct |
96 ms |
15816 KB |
Output is correct |
| 25 |
Correct |
103 ms |
15912 KB |
Output is correct |
| 26 |
Correct |
112 ms |
15812 KB |
Output is correct |
| 27 |
Correct |
96 ms |
15996 KB |
Output is correct |
| 28 |
Correct |
91 ms |
15880 KB |
Output is correct |
| 29 |
Correct |
94 ms |
15812 KB |
Output is correct |
