Task: | Uolevin kalansaalis |
Sender: | Username* |
Submission time: | 2023-11-02 16:28:16 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#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 | WRONG ANSWER | 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 |
Compiler report
input/code.cpp:129:21: warning: "/*" within comment [-Wcomment] 129 | /*for (Cell& cell : it->second) { | input/code.cpp: In function 'int main()': input/code.cpp:84:10: warning: variable 'start2' set but not used [-Wunused-but-set-variable] 84 | auto start2 = std::chrono::steady_clock::now(); | ^~~~~~
Code
#include <iostream>#include <vector>#include <algorithm>#include <chrono>using namespace std;typedef long long int ll;struct Cell {int row;int column;int value;};template<typename T>struct sort_pair {bool operator()(const pair<int, T>& left, const pair<int, T>& right) {return left.first < right.first;}};template <class result_t = std::chrono::milliseconds,class clock_t = std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}int answer;ll totalscore;ll maxtri = 0;int main() {//freopen("input.txt", "r", stdin);//auto start = std::chrono::steady_clock::now();int n, m, k;cin >> n;cin >> m;cin >> k;if (k == 0) {cout << "0" << "\n";return 0;}vector<vector<Cell>> rows(n); // vec of rows of cells in order//cout << rows.size();//auto start = std::chrono::steady_clock::now();for (int i = 0; i < k; ++i) {int row, column;char fish;cin >> row; row -= 1;cin >> column; column -= 1;cin >> fish;int value;if (fish == 'K') {value = 10;}else {value = -1;}totalscore -= value;Cell c;c.row = row; c.column = column; c.value = value;rows[row].push_back(c);}for (vector<Cell>& row : rows) {sort(row.begin(), row.end(), [](auto& x, auto& y) { return (x.column < y.column); });/*for (Cell cd : row.second) {cout << cd.row << "-" << cd.column << "\n";}*/}auto start2 = std::chrono::steady_clock::now();bool even = false;//int debugitercount = 0;for (int i = 1; i <= n; ++i) { // i, n height//cout << i << "\n";for (int j = 1; j <= m; ++j) { // j, m width//cout << "\n\nstarting " << i << " " << j;int maxT, minT;if (!even) { // odd// TODO: Issue with maxTmaxT = max(0, min({ i - 1, (j - 1) * 2 + 1, (m - j) * 2 + 1 })); // top, left, rightminT = max(0, min({ n - i, (j - 1) * 2 + 1, (m - j) * 2 + 1 })); // bottom, left, right}else { // evenmaxT = max(0, min({ i - 1, j * 2 - 1, (m - j) * 2 - 1 })); // top, left, rightminT = max(0, min({ n - i, j * 2 - 1, (m - j) * 2 - 1 })); // bottom, left, right}minT = 0 - minT;int triSum = 0;int minX, maxX; minX = maxX = j - 1;//cout << "\n\n Up";//maxT = -1;//bool lineEven = !&even;for (int x = 0; x <= maxT; ++x) {int line = 0;int rrow = i - x - 1;vector<Cell>& row = rows[rrow];for (Cell& cell : row) {if (minX <= cell.column) {if (cell.column <= maxX) {line += cell.value;}else {break; // over limit, no more left}}}/*auto it = lower_bound(rows.begin(), rows.end(),[&i, &rrow](const pair<int, vector<Cell>>& element) { return element.first == rrow; });if (it != rows.end()) {/*for (Cell& cell : it->second) {if (minX <= cell.column) {if (cell.column <= maxX) {line += cell.value;}else {break; // over limit, no more left}}}}*///cout << "\nline " << line << " at triangle part " << x << ", Realrow: " << rrow << " and min/max X: " << minX << "/" << maxX;triSum += line;if (triSum > maxtri) {maxtri = triSum;//cout << "\n !!!!!!!!!!!!!!!!!!!!!New maxtri " << maxtri << " at " << i << " " << j << " with height " << x << " and min/max " << minT << "/" << maxT;}if (!(rrow & 1)) { // is evenminX -= 1;}else {maxX += 1;}//if (x == 0) {// triSum = line;// minX, maxX; minX = maxX = j - 1;//}}//cout << "\n-- TRIDONE";/*for (vector<int>::reverse_iterator it = upLines.rbegin(); it != upLines.rend(); ++it) {triSum -= *it;if (triSum > maxtri) {maxtri = triSum;//cout << "\n! New maxtri " << maxtri << " at " << i << " " << j;}}*/////////cout << "\n\n Down";//////triSum = 0;minX = maxX = j - 1;for (int x = 0; x >= minT; --x) {int line = 0;int rrow = i - x - 1;vector<Cell>& row = rows[rrow];for (Cell& cell : row) {if (minX <= cell.column) {if (cell.column <= maxX) {line += cell.value;}else {break; // over limit, no more left}}}//cout << "\nline " << line << " at triangle part " << x;triSum += line;if (triSum > maxtri) {maxtri = triSum;//cout << "\n dNew maxtri " << maxtri << " at " << i << " " << j;}if (!(rrow & 1)) { // is evenminX -= 1;}else {maxX += 1;}//if (x == 0) {// triSum = line;// minX, maxX; minX = maxX = j - 1;//}}/*for (int x = 0; x >= minT; --x) {int line = 0;int rrow = i - x - 1;bool lineEven = (rrow % 2 == 0);//cout << "\nRow : " << rrow;//cout << "\nXrange : " << minX << " - " << maxX;auto it = find_if(rows.begin(), rows.end(),[&i,&rrow](const pair<int, vector<Cell>>& element) { return element.first == rrow; });if (it != rows.end()) {for (Cell& cell : it->second) {if (minX <= cell.column) {if (cell.column <= maxX) {line += cell.value;}else {break; // over limit, no more left}}}}//cout << "\nline " << line << " at triangle part " << x;triSum += line;downLines.push_back(line);if (lineEven) {minX -= 1;}else {maxX += 1;}}//cout << "\n-- TRIDONE";*/}//cout << "\n " << maxtri;even = !even;}//cout << debugitercount;//cout << "\n-- THE END --\nElapsed (ms)=" << since(start).count() << " , #2: " << since(start2).count() << endl;//cout << "\n\nRowsize: " << rows.size() << " \nTotalscore: " << totalscore << "\nMaxtri: " << maxtri << "\n\n";answer = totalscore + maxtri;cout << answer << "\n";}
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: WRONG ANSWER
input |
---|
1 1 1 1 1 H |
correct output |
---|
0 |
user output |
---|
1 |
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) |