Submission #71905530

Source Code Expand

// Problem: B - Traffic Light
// Contest: AtCoder - AtCoder Grand Contest 075
// URL: https://atcoder.jp/contests/agc075/tasks/agc075_b
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
// Written by yhm.
// Start codeing:2025-12-21 22:34:43
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define db long double
#define mems(a,x) memset((a),(x),sizeof(a))
using namespace std;
inline int read(){
	int x=0,fl=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')fl=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*fl;
}
const int maxn=400010;
const int inf=1e18;
bool mbe;

int n,m,x,y,ans;
int a[maxn],c[maxn];
int lsh[maxn],len;
int f[maxn],sum[maxn];
void work(){
	n=read();m=read();x=read();y=read();ans=0;
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)c[i]=read();
	for(int i=1;i<=n;i++)lsh[++len]=a[i],lsh[++len]=a[i]-y;
	sort(lsh+1,lsh+len+1),len=unique(lsh+1,lsh+len+1)-lsh-1;lsh[0]=inf;
	for(int i=1;i<=len;i++)sum[i]=0;
	for(int i=1;i<=n;i++){
		int pl=lower_bound(lsh+1,lsh+len+1,a[i]-x+1)-lsh,pr=lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
		sum[pl]+=c[i],sum[pr+1]-=c[i];
	}
	for(int i=1;i<=len;i++)sum[i]+=sum[i-1];
	for(int i=1,j=0,mx=0;i<=len;i++){
		while(lsh[j+1]+y<=lsh[i]){
			j++;
			mx=max(mx,f[j]);
		}
		f[i]=mx-m+sum[i];
		ans=max(ans,f[i]);
	}
	printf("%lld\n",ans);
}

bool med;
int T;
signed main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	
	// cerr<<(&mbe-&med)/1024.0/1024.0<<"\n";
	
	T=read();
	while(T--)work();
}

Submission Info

Submission Time
Task B - Traffic Light
User gdfyhm
Language C++23 (GCC 15.2.0)
Score 0
Code Size 1730 Byte
Status WA
Exec Time 1123 ms
Memory 17224 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 1
AC × 46
WA × 53
Set Name Test Cases
Sample example_00.txt
All example_00.txt, test_000.txt, test_001.txt, test_002.txt, test_003.txt, test_004.txt, test_005.txt, test_006.txt, test_007.txt, test_008.txt, test_009.txt, test_010.txt, test_011.txt, test_012.txt, test_013.txt, test_014.txt, test_015.txt, test_016.txt, test_017.txt, test_018.txt, test_019.txt, test_020.txt, test_021.txt, test_022.txt, test_023.txt, test_024.txt, test_025.txt, test_026.txt, test_027.txt, test_028.txt, test_029.txt, test_030.txt, test_031.txt, test_032.txt, test_033.txt, test_034.txt, test_035.txt, test_036.txt, test_037.txt, test_038.txt, test_039.txt, test_040.txt, test_041.txt, test_042.txt, test_043.txt, test_044.txt, test_045.txt, test_046.txt, test_047.txt, test_048.txt, test_049.txt, test_050.txt, test_051.txt, test_052.txt, test_053.txt, test_054.txt, test_055.txt, test_056.txt, test_057.txt, test_058.txt, test_059.txt, test_060.txt, test_061.txt, test_062.txt, test_063.txt, test_064.txt, test_065.txt, test_066.txt, test_067.txt, test_068.txt, test_069.txt, test_070.txt, test_071.txt, test_072.txt, test_073.txt, test_074.txt, test_075.txt, test_076.txt, test_077.txt, test_078.txt, test_079.txt, test_080.txt, test_081.txt, test_082.txt, test_083.txt, test_084.txt, test_085.txt, test_086.txt, test_087.txt, test_088.txt, test_089.txt, test_090.txt, test_091.txt, test_092.txt, test_093.txt, test_094.txt, test_095.txt, test_096.txt, test_097.txt
Case Name Status Exec Time Memory
example_00.txt AC 2 ms 3632 KiB
test_000.txt AC 54 ms 3724 KiB
test_001.txt AC 54 ms 3700 KiB
test_002.txt AC 54 ms 3812 KiB
test_003.txt AC 54 ms 3676 KiB
test_004.txt AC 54 ms 3724 KiB
test_005.txt AC 54 ms 3724 KiB
test_006.txt AC 54 ms 3628 KiB
test_007.txt AC 54 ms 3784 KiB
test_008.txt WA 1067 ms 6156 KiB
test_009.txt WA 1123 ms 6104 KiB
test_010.txt WA 1080 ms 6104 KiB
test_011.txt WA 1015 ms 6244 KiB
test_012.txt WA 1108 ms 6116 KiB
test_013.txt WA 1072 ms 6128 KiB
test_014.txt WA 1092 ms 6104 KiB
test_015.txt WA 1046 ms 6284 KiB
test_016.txt AC 94 ms 16244 KiB
test_017.txt AC 93 ms 16268 KiB
test_018.txt AC 91 ms 16328 KiB
test_019.txt AC 92 ms 16056 KiB
test_020.txt AC 94 ms 16140 KiB
test_021.txt AC 93 ms 16148 KiB
test_022.txt AC 92 ms 16172 KiB
test_023.txt AC 91 ms 16244 KiB
test_024.txt AC 92 ms 16140 KiB
test_025.txt AC 92 ms 16216 KiB
test_026.txt AC 91 ms 16220 KiB
test_027.txt AC 90 ms 16140 KiB
test_028.txt WA 100 ms 16356 KiB
test_029.txt AC 100 ms 16060 KiB
test_030.txt AC 97 ms 16120 KiB
test_031.txt AC 98 ms 16052 KiB
test_032.txt AC 97 ms 16216 KiB
test_033.txt AC 98 ms 16172 KiB
test_034.txt AC 98 ms 16268 KiB
test_035.txt AC 41 ms 13168 KiB
test_036.txt AC 40 ms 13100 KiB
test_037.txt AC 41 ms 13196 KiB
test_038.txt WA 43 ms 16148 KiB
test_039.txt WA 43 ms 16332 KiB
test_040.txt WA 44 ms 16332 KiB
test_041.txt WA 44 ms 16220 KiB
test_042.txt WA 44 ms 16212 KiB
test_043.txt WA 44 ms 16220 KiB
test_044.txt AC 41 ms 13068 KiB
test_045.txt AC 40 ms 13148 KiB
test_046.txt AC 40 ms 12984 KiB
test_047.txt WA 46 ms 16164 KiB
test_048.txt WA 47 ms 16032 KiB
test_049.txt WA 47 ms 16244 KiB
test_050.txt WA 95 ms 16220 KiB
test_051.txt WA 95 ms 16148 KiB
test_052.txt WA 92 ms 16056 KiB
test_053.txt WA 93 ms 16204 KiB
test_054.txt WA 93 ms 16220 KiB
test_055.txt WA 96 ms 16060 KiB
test_056.txt WA 94 ms 16216 KiB
test_057.txt AC 44 ms 15076 KiB
test_058.txt WA 45 ms 14964 KiB
test_059.txt AC 44 ms 14860 KiB
test_060.txt WA 44 ms 14776 KiB
test_061.txt WA 44 ms 14964 KiB
test_062.txt AC 45 ms 15048 KiB
test_063.txt WA 45 ms 14860 KiB
test_064.txt WA 49 ms 14868 KiB
test_065.txt WA 48 ms 15116 KiB
test_066.txt WA 48 ms 14752 KiB
test_067.txt WA 48 ms 14932 KiB
test_068.txt WA 48 ms 14776 KiB
test_069.txt WA 47 ms 15048 KiB
test_070.txt WA 48 ms 15076 KiB
test_071.txt WA 93 ms 16952 KiB
test_072.txt WA 92 ms 17116 KiB
test_073.txt WA 96 ms 17140 KiB
test_074.txt WA 90 ms 17224 KiB
test_075.txt WA 93 ms 17140 KiB
test_076.txt WA 92 ms 16956 KiB
test_077.txt WA 102 ms 17044 KiB
test_078.txt WA 92 ms 16396 KiB
test_079.txt WA 94 ms 16240 KiB
test_080.txt WA 93 ms 16212 KiB
test_081.txt WA 93 ms 16300 KiB
test_082.txt WA 93 ms 16204 KiB
test_083.txt AC 93 ms 16216 KiB
test_084.txt AC 94 ms 16356 KiB
test_085.txt AC 94 ms 16204 KiB
test_086.txt AC 95 ms 16148 KiB
test_087.txt AC 93 ms 16328 KiB
test_088.txt WA 89 ms 16012 KiB
test_089.txt WA 88 ms 15944 KiB
test_090.txt WA 88 ms 15700 KiB
test_091.txt WA 89 ms 15828 KiB
test_092.txt WA 89 ms 15892 KiB
test_093.txt AC 93 ms 16396 KiB
test_094.txt AC 93 ms 16216 KiB
test_095.txt AC 92 ms 16216 KiB
test_096.txt AC 92 ms 16060 KiB
test_097.txt AC 92 ms 16244 KiB