QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#751904#4906. 球球NineSuns5 24ms28264kbC++142.1kb2024-11-15 21:14:422024-11-15 21:14:49

Judging History

你现在查看的是最新测评结果

  • [2024-11-15 21:14:49]
  • 评测
  • 测评结果:5
  • 用时:24ms
  • 内存:28264kb
  • [2024-11-15 21:14:42]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define int long long

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5005, inf = 0x3f3f3f3f3f3f3f3f; 
int n, g[N], t[N], x[N]; 
bool f[N][N], h[N]; 

void solve () {
	cin >> n; 
	for (int i = 1;i <= n;i++) cin >> t[i] >> x[i]; 
	memset(g, 0x3f, sizeof g); 
	g[0] = 0; h[0] = 1; 
	for (int i = 0;i <= n;i++) {
		if (i) g[i] = min(g[i], max(t[i-1], g[i-1])+llabs(x[i]-x[i-1])); 
		if (i && x[i] == x[i-1]) g[i] = min(g[i], g[i-1]);  
		if (g[i] > t[i]) g[i] = inf; 
		for (int j = 0;j <= n;j++) h[i] |= f[i][j]; 
		if (i < n && h[i]) {
			h[i+1] |= (t[i+1]-t[i] >= llabs(x[i+1]-x[i])); 
			for (int j = i+1;j <= n;j++) f[i+1][j] |= t[i+1]-t[i] >= llabs(x[j]-x[i])+llabs(x[i+1]-x[j]); 
		}
		if (i && f[i-1][i] && i < n) {
			g[i+1] = min(g[i+1], max(t[i], t[i-1]+llabs(x[i+1]-x[i-1])));
			h[i+1] |= t[i+1]-t[i-1] >= llabs(x[i+1]-x[i-1]); 
			for (int j = i+1;j <= n;j++) f[i+1][j] |= t[i+1]-max(t[i], t[i-1]+llabs(x[i-1]-x[j])) >= llabs(x[j]-x[i+1]); //, cout << i << " " << j << " " << "DCHK:" << t[i+1]-t[i-1] << " " << abs(x[i]-x[j]) << " " << abs(x[j]-x[i+1]) << " " << f[i+1][j] << endl;
		}
		if (g[i] <= t[i] && i < n) {
			h[i+1] |= t[i+1]-g[i] >= llabs(x[i+1]-x[i]); 
			for (int j = i+1;j <= n;j++) f[i+1][j] |= t[i+1]-max(t[i], g[i]+llabs(x[i]-x[j])) >= llabs(x[j]-x[i+1]); 
//			for (int j = i+1;j <= n;j++) f[i+1][j] |= (t[i+1]-g[i]) >= abs(x[i]-x[j])+abs(x[j]-x[i+1]); //, cout << i << " " << j << " " << "CHK:" << t[i+1]-g[i] << " " << abs(x[i]-x[j]) << " " << abs(x[j]-x[i+1]) << " " << f[i+1][j] << endl;  
		} 
		for (int j = 0;j <= n;j++) f[i+1][j] |= f[i][j]&(t[i+1]-t[i] >= llabs(x[i+1]-x[i])); 
//		for (int j = 0;j <= n;j++) cout << f[i][j] << " "; cout << endl; 
//		cout << g[i] << endl; 
	} //	cout << endl; 
	int fl = g[n] <= t[n] || f[n-1][n] || h[n]; 
	puts(fl ? "YES" : "NO"); 
}

signed main () {
	int T = 1; 
	while (T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 3772kb

input:

5
2 1
3 2
9 6
10 5
13 -1

output:

NO

result:

ok single line: 'NO'

Test #2:

score: 5
Accepted
time: 0ms
memory: 3840kb

input:

5
1 1
3 2
4 -1
6 4
10 -1

output:

NO

result:

ok single line: 'NO'

Test #3:

score: 5
Accepted
time: 0ms
memory: 3708kb

input:

4
16 13
18 4
20 3
21 5

output:

NO

result:

ok single line: 'NO'

Test #4:

score: 5
Accepted
time: 0ms
memory: 3708kb

input:

5
2 1
3 2
8 6
10 5
13 0

output:

YES

result:

ok single line: 'YES'

Test #5:

score: 5
Accepted
time: 0ms
memory: 3656kb

input:

5
2 1
3 2
9 6
10 5
13 0

output:

YES

result:

ok single line: 'YES'

Test #6:

score: 5
Accepted
time: 0ms
memory: 3712kb

input:

5
1 1
3 2
4 0
6 4
10 -1

output:

YES

result:

ok single line: 'YES'

Test #7:

score: 5
Accepted
time: 0ms
memory: 3640kb

input:

3
1 0
5 5
6 2

output:

YES

result:

ok single line: 'YES'

Test #8:

score: 5
Accepted
time: 0ms
memory: 3656kb

input:

5
2 1
6 0
7 -1
8 2
9 -2

output:

YES

result:

ok single line: 'YES'

Test #9:

score: 5
Accepted
time: 0ms
memory: 3652kb

input:

5
30 10
40 -10
51 9
52 8
53 20

output:

YES

result:

ok single line: 'YES'

Test #10:

score: 5
Accepted
time: 0ms
memory: 3768kb

input:

3
2 2
5 5
6 1

output:

YES

result:

ok single line: 'YES'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #11:

score: 5
Accepted
time: 1ms
memory: 6140kb

input:

100
51823 -51823
80072 -23574
152202 48556
263343 -14629
356859 -38607
441850 -193136
442857 -192129
471412 -108145
504392 -187704
582081 -265393
680615 -220684
775219 -261463
781624 -267868
801370 -287614
899570 -166859
982377 -272221
1048767 -338611
1094930 -189414
1170308 -460152
1222829 -512673
...

output:

YES

result:

ok single line: 'YES'

Test #12:

score: 5
Accepted
time: 1ms
memory: 4040kb

input:

100
106661 51112
155727 44629
204995 -4639
289968 -89612
352826 -26754
358628 -32556
456755 -130683
458435 -4437
484255 -103183
506353 -125281
537685 -93949
599460 -129003
697511 -32174
746550 -179264
749060 -176754
751112 -178806
756783 -173135
847195 -82723
886372 -43546
953837 23919
1050796 -7304...

output:

YES

result:

ok single line: 'YES'

Test #13:

score: 0
Wrong Answer
time: 0ms
memory: 5956kb

input:

100
51953 51953
178909 4607
255989 -75003
303522 -152083
375771 -271865
422215 -318309
446399 -294125
534441 -382167
591666 -324942
665189 -398465
759160 -492436
856968 -394628
878236 -415896
978225 -199616
1004339 -342021
1011649 -349331
1056555 -304425
1121330 -315907
1124074 -242394
1192744 -3110...

output:

NO

result:

wrong answer 1st lines differ - expected: 'YES', found: 'NO'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #91:

score: 0
Wrong Answer
time: 24ms
memory: 28264kb

input:

5000
6 6
80 80
170 48
240 106
243 179
329 176
412 93
485 176
552 249
555 316
613 371
650 313
733 251
735 253
736 334
815 254
893 333
943 255
965 227
1022 284
1116 205
1174 320
1230 376
1318 378
1336 288
1430 212
1494 276
1562 344
1597 309
1638 350
1716 272
1793 349
1809 365
1908 306
1951 464
2037 42...

output:

NO

result:

wrong answer 1st lines differ - expected: 'YES', found: 'NO'

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #4:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%