Task: | Uolevin kalansaalis |
Sender: | Tipu |
Submission time: | 2023-11-12 23:59:14 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 37 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 37 |
#2 | WRONG ANSWER | 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 | ACCEPTED | 0.00 s | 1, 2 | details |
#15 | ACCEPTED | 0.00 s | 1, 2 | details |
#16 | ACCEPTED | 0.08 s | 2 | details |
#17 | WRONG ANSWER | 0.08 s | 2 | details |
#18 | ACCEPTED | 0.15 s | 2 | details |
#19 | WRONG ANSWER | 0.03 s | 2 | details |
#20 | ACCEPTED | 0.08 s | 2 | details |
#21 | ACCEPTED | 0.06 s | 2 | details |
#22 | ACCEPTED | 0.05 s | 2 | details |
#23 | ACCEPTED | 0.03 s | 2 | details |
#24 | ACCEPTED | 0.07 s | 2 | details |
Code
#include<bits/stdc++.h>using namespace std;typedef long long ll;struct Hex {public:ll l = 0;ll r = 0;};const ll SIZE = 555;ll n, m, k;ll v[SIZE][SIZE];ll v2[SIZE][SIZE];Hex d[SIZE][SIZE];ll count_l_colum(ll i, ll j, ll l){bool add = (i % 2 == 0);return (d[i][j].l - d[i-l][j - ((l-add)/2 + (l-add)%2)].l);}ll count_r_colum(ll i, ll j, ll l){bool add = (i % 2 == 0);return (d[i][j].r - d[i-l][j + (l+add)/2].r);}ll scan(ll p, bool skip1){for (ll i = n; i > 1; i--) {if(skip1 && (i == 1)){break;}ll h = i - skip1;ll j2 = 1;ll j1 = 1;ll l = 1;ll ms = d[i][1].l - d[i-1][(i % 2 == 0)].l;ll s = ms;ll safety = 0;while (j1 <= m){safety++;// if(s == 0){// cout << "HEI" << endl;// }// if(s == 1){// cout << "I" << endl;// }p = min(s, p);if(j2 < j1+h - 1 && j2 < m){j2++;ms += count_l_colum(i, j2, (j2-j1 + 1));continue;}//elseif((ms - s) < 0){l++;s += count_l_colum(i, (j1+l-1), l);continue;}//elseif((ms - s) > 0 && j1 <= j2 && l > 1){s -= count_r_colum(i, j1, l);ms -= count_r_colum(i, j1, (j2-j1 + 1));j1++;l--;continue;}else if (j2 >= m + 1){break;}else{s -= count_r_colum(i, j1, l);ms -= count_r_colum(i, j1, (j2-j1 + 1));j1++;j2++;s += count_l_colum(i, (j1+l-1), l);ms += count_l_colum(i, j2, (j2-j1 + 1));continue;}}// if(s == 0){// cout << "MOI" << endl;// }// if(s == 1){// cout << "J" << endl;// }p = min(s, p);}ll s = 0;for (int j = 1; j <= m; j++){s = d[1][j].l;p = min(s,p);}return p;}int main() {// freopen("input.txt", "r", stdin);cin >> n >> m >> k;ll a, b;char c;ll os = 0;for (ll i = 0; i < k; i++) {cin >> a >> b >> c;if(c == 'H'){v[a][b] = 1;os += 1;}else{v[a][b] = -10;os -= 10;}}for (ll i = 1; i <= n; i++) {for (ll j = 1; j <= m; j++) {bool add = 0;if(i % 2 == 0){add = 1;}d[i][j].l = v[i][j] + d[i-1][j-1+add].l;d[i][j].r = v[i][j] + d[i-1][j+add].r;}}// for (ll i = 1; i <= n; i++) {// for (ll j = 1; j <= m; j++) {// cout << "(" << d[i][j].l << " ; " << d[i][j].r << ") " ;// }// cout << "\n";// }ll p = 1e9;p = scan(p,false);// cout << p << endl;// cout << os << endl;// assert(p >= os);// cout << "\n\n";bool fix = (n%2 == 0);n = n + fix;for (ll i = 1; i <= n; i++) {for (ll j = 1; j <= m; j++) {v2[n+1-i][j] = v[i][j];}}for (ll i = 1; i <= n; i++) {for (ll j = 1; j <= m; j++) {bool add = 0;if(i % 2 == 0){add = 1;}d[i][j].l = v2[i][j] + d[i-1][j-1+add].l;d[i][j].r = v2[i][j] + d[i-1][j+add].r;}}// for (ll i = 1; i <= n; i++) {// for (ll j = 1; j <= m; j++) {// cout << "(" << d[i][j].l << " ; " << d[i][j].r << ") " ;// }// cout << "\n";// }p = min(scan(p, fix), p);// assert((n <= 5 && m <= 5));assert(p != 1e9);cout << os - p;}
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: ACCEPTED
input |
---|
10 10 100 2 9 H 5 4 H 5 9 K 6 1 K ... |
correct output |
---|
-439 |
user output |
---|
-439 |
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: ACCEPTED
input |
---|
500 500 125000 125 261 K 84 78 K 11 200 K 481 246 K ... |
correct output |
---|
-624270 |
user output |
---|
-624270 |
Test 17
Group: 2
Verdict: WRONG ANSWER
input |
---|
500 500 125100 16 61 H 37 62 H 459 125 H 318 476 H ... |
correct output |
---|
124020 |
user output |
---|
124010 |
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: WRONG ANSWER
input |
---|
500 500 32000 30 81 H 315 34 H 78 112 H 367 166 H ... |
correct output |
---|
10126 |
user output |
---|
10089 |
Test 20
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 126745 164 390 H 126 331 H 164 126 H 55 92 H ... |
correct output |
---|
-104692 |
user output |
---|
-104692 |
Test 21
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 71200 106 191 H 314 189 H 482 485 H 344 401 H ... |
correct output |
---|
-335853 |
user output |
---|
-335853 |
Test 22
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 67772 421 277 H 428 470 H 169 142 H 256 345 H ... |
correct output |
---|
-208567 |
user output |
---|
-208567 |
Test 23
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 27434 366 481 H 38 22 H 126 107 H 135 169 H ... |
correct output |
---|
-57100 |
user output |
---|
-57100 |
Test 24
Group: 2
Verdict: ACCEPTED
input |
---|
500 500 93982 183 13 H 463 230 H 264 351 H 399 290 H ... |
correct output |
---|
-52800 |
user output |
---|
-52800 |