Task: | Uolevin kalansaalis |
Sender: | Luc |
Submission time: | 2023-11-08 17:35:07 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | TIME LIMIT EXCEEDED | 0 |
#2 | TIME LIMIT EXCEEDED | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | ACCEPTED | 0.00 s | 1, 2 | details |
#3 | ACCEPTED | 0.00 s | 1, 2 | details |
#4 | ACCEPTED | 0.00 s | 1, 2 | details |
#5 | ACCEPTED | 0.00 s | 1, 2 | details |
#6 | ACCEPTED | 0.00 s | 1, 2 | details |
#7 | ACCEPTED | 0.00 s | 1, 2 | details |
#8 | ACCEPTED | 0.00 s | 1, 2 | details |
#9 | ACCEPTED | 0.00 s | 1, 2 | details |
#10 | ACCEPTED | 0.00 s | 1, 2 | details |
#11 | ACCEPTED | 0.00 s | 1, 2 | details |
#12 | ACCEPTED | 0.00 s | 1, 2 | details |
#13 | ACCEPTED | 0.00 s | 1, 2 | details |
#14 | TIME LIMIT EXCEEDED | -- | 1, 2 | details |
#15 | ACCEPTED | 0.00 s | 1, 2 | details |
#16 | TIME LIMIT EXCEEDED | -- | 2 | details |
#17 | TIME LIMIT EXCEEDED | -- | 2 | details |
#18 | ACCEPTED | 0.08 s | 2 | details |
#19 | TIME LIMIT EXCEEDED | -- | 2 | details |
#20 | TIME LIMIT EXCEEDED | -- | 2 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2 | details |
#22 | TIME LIMIT EXCEEDED | -- | 2 | details |
#23 | TIME LIMIT EXCEEDED | -- | 2 | details |
#24 | TIME LIMIT EXCEEDED | -- | 2 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result] 15 | scanf("%d %d %d", &h, &w, &n); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~ input/code.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result] 21 | scanf("%d %d %c", &y, &x, &c); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h>using namespace std;int sum(int * a, int n){int r = 0;while(n--) r+=a[n];return r;}int main(){int w,h,n,x,y, rs=0, r, i;char c;scanf("%d %d %d", &h, &w, &n);vector<pair<pair<int,int>, int>> k;vector<pair<int, int>> e;vector<int> f;i=n;while(i--){scanf("%d %d %c", &y, &x, &c);if(c == 'K'){k.push_back({{(y-1)-2*(x-1)-((y-1)%2), 2*(x-1)+(y-1)+((y-1)%2)},(y-1)});rs -= 10;}else{f.push_back((y-1)*w+(x-1));rs += 1;}}//printf("%d\n", rs);if(k.empty()) r = rs - ((((int)f.size())==w*h)?1:0);else r = max(rs, k.empty()?rs:rs+10);//printf("%d\n", r);sort(f.begin(), f.end());n = k.size();rs += n*(10);while(n>1){//printf("%d\n", n);i = 0;int l = k.size();int ii[n];ii[0] = 0;while(i<n-1) {ii[i+1]=ii[i]+1;i++;}while(ii[0]+n-1<l){ //// [BEGIN] do stuffif(r>=rs) break;int ba = k[ii[0]].first.first;int da = k[ii[0]].first.second;y = k[ii[0]].second;int bi = k[ii[0]].first.first;int di = k[ii[0]].first.second;x = k[ii[0]].second;i = 1;//printf("\n %d", ii[0]);while(i<n){//printf(" %d", ii[i]);ba = max(ba, k[ii[i]].first.first);da = max(da, k[ii[i]].first.second);bi = min(bi, k[ii[i]].first.first);di = min(di, k[ii[i]].first.second);y = max(y, k[ii[i]].second);x = min(x, k[ii[i]].second);i++;}//printf("\n");int rr = rs;int xt = (int)floor(((float)(di-y))/2);i = ((int)floor(((float)(y-bi))/2))-xt;//printf(" ^%d %d %d (%d, %d)\n", xt, i, y, bi, di);if(xt+i<w && xt>=0 && y-i>=0 && rr>r){while(i>=0){auto kl = lower_bound(f.begin(), f.end(), y*w+xt);auto ku = upper_bound(f.begin(), f.end(), y*w+(xt+i));rr -= ku-kl;i--;xt += y%2;y--;}r = max(r, rr);//printf(" ^%d\n", rr);}rr = rs;xt = (int)floor(((float)(x-ba))/2);i = ((int)floor(((float)(da-x))/2))-xt;//printf(" v%d %d %d (%d, %d) %d\n", xt, i, x, ba, da, ((int)floor(((float)(da-y))/2)));if(xt+i<w && xt>=0 && x+i<h && rr>r){while(i>=0){//printf(" %d %d", x*w+xt, x*w+(xt+i));auto kl = lower_bound(f.begin(), f.end(), x*w+xt);auto ku = upper_bound(f.begin(), f.end(), x*w+(xt+i));rr -= ku-kl;i--;xt += x%2;x++;}r = max(r, rr);//printf(" v%d\n", rr);}// [END] do stuffint iii = n;ii[n-1]++;while(iii-->1){if(ii[iii]+(n-iii-1)>=l){// printf(" %d + %d\n", ii[iii], (n-iii-1));ii[iii-1]++;if(ii[iii-1]+(n-iii-2)<l){i=0;while(i<n-iii) {ii[iii+i]=ii[iii+i-1]+1;i++;}}}//printf(" %d %d\n", iii, ii[iii]);}}n--;rs -= 10;}printf("%d\n", r);}
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 6 13 1 1 K 5 1 K 2 2 H 4 2 H ... |
correct output |
---|
-16 |
user output |
---|
-16 |
Test 2
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 6 7 1 5 K 4 6 K 2 4 H 2 5 H ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 3
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 6 7 5 5 K 2 6 K 2 4 H 2 5 H ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 4
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 51 3 3 H 6 3 H 9 5 H 5 10 H ... |
correct output |
---|
50 |
user output |
---|
50 |
Test 5
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 52 3 5 H 3 1 H 9 6 H 2 8 H ... |
correct output |
---|
40 |
user output |
---|
40 |
Test 6
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 60 6 10 H 2 8 H 5 8 H 8 10 H ... |
correct output |
---|
-15 |
user output |
---|
-15 |
Test 7
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 60 4 7 H 7 4 H 4 10 H 3 6 H ... |
correct output |
---|
60 |
user output |
---|
60 |
Test 8
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 40 9 9 H 5 10 H 5 6 H 4 9 H ... |
correct output |
---|
2 |
user output |
---|
2 |
Test 9
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1 1 0 |
correct output |
---|
0 |
user output |
---|
0 |
Test 10
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1 1 1 1 1 K |
correct output |
---|
0 |
user output |
---|
0 |
Test 11
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1 1 1 1 1 H |
correct output |
---|
0 |
user output |
---|
0 |
Test 12
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 5 32 10 3 H 4 4 H 3 3 H 5 4 H ... |
correct output |
---|
20 |
user output |
---|
20 |
Test 13
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 10 32 5 9 H 2 4 H 2 9 H 2 5 H ... |
correct output |
---|
28 |
user output |
---|
28 |
Test 14
Group: 1, 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
10 10 100 2 9 H 5 4 H 5 9 K 6 1 K ... |
correct output |
---|
-439 |
user output |
---|
(empty) |
Test 15
Group: 1, 2
Verdict: ACCEPTED
input |
---|
10 10 100 8 9 H 5 10 H 5 4 H 3 9 H ... |
correct output |
---|
88 |
user output |
---|
88 |
Test 16
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 125000 125 261 K 84 78 K 11 200 K 481 246 K ... |
correct output |
---|
-624270 |
user output |
---|
(empty) |
Test 17
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 125100 16 61 H 37 62 H 459 125 H 318 476 H ... |
correct output |
---|
124020 |
user output |
---|
(empty) |
Test 18
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 249999 22 214 H 356 145 H 341 29 H 393 262 H ... |
correct output |
---|
249999 |
user output |
---|
249999 |
Test 19
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 32000 30 81 H 315 34 H 78 112 H 367 166 H ... |
correct output |
---|
10126 |
user output |
---|
(empty) |
Test 20
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 126745 164 390 H 126 331 H 164 126 H 55 92 H ... |
correct output |
---|
-104692 |
user output |
---|
(empty) |
Test 21
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 71200 106 191 H 314 189 H 482 485 H 344 401 H ... |
correct output |
---|
-335853 |
user output |
---|
(empty) |
Test 22
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 67772 421 277 H 428 470 H 169 142 H 256 345 H ... |
correct output |
---|
-208567 |
user output |
---|
(empty) |
Test 23
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 27434 366 481 H 38 22 H 126 107 H 135 169 H ... |
correct output |
---|
-57100 |
user output |
---|
(empty) |
Test 24
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
500 500 93982 183 13 H 463 230 H 264 351 H 399 290 H ... |
correct output |
---|
-52800 |
user output |
---|
(empty) |