Task: | Uolevin kalansaalis |
Sender: | martinm17 |
Submission time: | 2023-11-03 10:58:52 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 37 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 37 |
#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 | ACCEPTED | 0.00 s | 1, 2 | details |
#15 | ACCEPTED | 0.00 s | 1, 2 | details |
#16 | TIME LIMIT EXCEEDED | -- | 2 | details |
#17 | TIME LIMIT EXCEEDED | -- | 2 | details |
#18 | TIME LIMIT EXCEEDED | -- | 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 |
Code
#include <iostream>#include <vector>#include <algorithm>using namespace std;int triangleScan(vector<vector<int>> &grid, vector<vector<int>> &dp, int size, int n, int m){// cout << "///// size is " << size << endl;int minTriangle = 1000000;for (int i = 0; i < n - size + 1; i++){for (int j = 0; j < m - size + 1; j++){// cout << "looking at node " << i << " " << j << endl;int line = i;int column = j;int current_min = 0;int right_border = column + size - 1;int left_border = column;for (int k = line; k < line + size; k++){// cout << "start " << left_border << " end " << right_border << endl;if (left_border > 0){// cout << "line is " << k << " left border is " << left_border << " right border is " << right_border << endl;// cout << "**** sum is " << dp[k][right_border] << " - " << dp[k][left_border - 1] << " = " << dp[k][right_border] - dp[k][left_border - 1] << endl;current_min += dp[k][right_border] - dp[k][left_border - 1];}else{// cout << "**** sum is " << dp[k][right_border] << endl;current_min += dp[k][right_border];}if (k % 2 == 1)left_border++;elseright_border--;// cout << current_min << endl;}// cout << "current min is " << current_min << endl;minTriangle = min(minTriangle, current_min);}// cout << endl;}for (int i = n - 1; i >= size - 1; i--){for (int j = 0; j <= m - size; j++){// cout << "looking at node " << i << " " << j << endl;int line = i;int column = j;int current_min = 0;int right_border = column + size - 1;int left_border = column;// cout << "right border is " << right_border << " left border is " << left_border << "line is " << line << endl;for (int k = size; k > 0; k--){// cout << "start " << left_border << " end " << right_border << endl;if (left_border > 0){// cout << "line is " << line - size + k << " left border is " << left_border << " right border is " << right_border << endl;// cout << "**** sum is " << dp[line - size + k][right_border] << " - " << dp[line - size + k][left_border - 1] << " = " << dp[line - size + k][right_border] - dp[line - size + k][left_border - 1] << endl;current_min += dp[line - size + k][right_border] - dp[line - size + k][left_border - 1];}else{// cout << "**** sum is " << dp[line - size + k][right_border] << endl;current_min += dp[line - size + k][right_border];}if ((line - size + k) % 2 == 1)left_border++;elseright_border--;// cout << current_min << endl;}// cout << "current min is " << current_min << endl;minTriangle = min(minTriangle, current_min);}// cout << endl;}return minTriangle;}int main(){int n, m, k;cin >> n >> m >> k;vector<vector<int>> adj(n, vector<int>(m, 0));int total_points = 0;for (int i = 0; i < k; i++){int a, b;char c;cin >> a >> b >> c;if (c == 'K'){// cout << "shrimp detected" << endl;adj[a - 1][b - 1] = -10;total_points -= 10;}else if (c == 'H'){adj[a - 1][b - 1] = 1;total_points += 1;}}int size = min(n, m);vector<vector<int>> dp(n, vector<int>(m, 0));// scan the graph to caclulate the toatal points from each cell and the beginning of the rowfor (int i = 0; i < n; i++){int sum = 0;for (int j = 0; j < m; j++){sum += adj[i][j];dp[i][j] = sum;}}// loop to display dp table// for (int i = 0; i < n; i++)// {// for (int j = 0; j < m; j++)// {// cout << dp[i][j] << " ";// }// cout << endl;// }// for a triangle of size "size" use the dp table to calculate the sum of the triangle using substractionint result = triangleScan(adj, dp, size, n, m);// cout << "total points is " << total_points << endl;// cout << "result is " << total_points - result << endl;for (int i = size - 1; i >= 1; i--){// cout << "in for loop " << i << endl;int current = triangleScan(adj, dp, i, n, m);// if (current >= result)// {// break;// }result = min(current, result);}cout << total_points - result << endl;return 0;}
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: 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: TIME LIMIT EXCEEDED
input |
---|
500 500 249999 22 214 H 356 145 H 341 29 H 393 262 H ... |
correct output |
---|
249999 |
user output |
---|
(empty) |
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) |