Submission #453671

#TimeUsernameProblemLanguageResultExecution timeMemory
453671UltraFalconColouring a rectangle (eJOI19_colouring)C++17
0 / 100
2092 ms21896 KiB
#include <bits/stdc++.h> #define int long long using namespace std; signed main() { ios_base::sync_with_stdio(false); cin.tie(0); int m, n; cin >> m >> n; vector<int> diagonals_down(m + n - 1); vector<int> diagonals_down_used(m + n + 1, 0); for (int i=0; i<(m + n - 1); i++) { cin >> diagonals_down[i]; } vector<int> diagonals_up(m + n - 1); vector<int> diagonals_up_used(m + n + 1, 0); for (int i=0; i<(m + n - 1); i++) { cin >> diagonals_up[i]; } for (int i=0; i<(m + n - 1); i++) { int x, y; int total_cost = 0; vector<int> diagonals_idx; if (i < n) { y = 0; x = n - (i+1) + y; while (x < n && y < m) { diagonals_idx.push_back(x + y); total_cost += diagonals_up[x + y]; x++; y++; } } else { y = m-1; x = n - (i+1) + y; while (x >= 0 && y >= 0) { diagonals_idx.push_back(x + y); total_cost += diagonals_up[x + y]; x--; y--; } } if (total_cost < diagonals_down[i]) { //cerr << i << " -- i\n"; for (auto idx : diagonals_idx) { diagonals_up_used[idx]++; } } else { diagonals_down_used[i]++; } } for (int i=0; i<(m + n - 1); i++) { int x, y; int total_cost = 0; vector<int> diagonals_idx; if (i < n) { y = 0; x = i - y; while (x >= 0 && y < m) { diagonals_idx.push_back(y - x + n - 1); total_cost += diagonals_down[y - x + n - 1]; x--; y++; } } else { y = m-1; x = i - y; while (x < n && y >= 0) { diagonals_idx.push_back(y - x + n - 1); total_cost += diagonals_down[y - x + n - 1]; x++; y--; } } if (total_cost < diagonals_up[i]) { //cerr << i << " -- i\n"; for (auto idx : diagonals_idx) { diagonals_down_used[idx]++; } } else { diagonals_up_used[i]++; } } int cost = 0; for (int i=0; i<(m + n - 1); i++) { //cerr << diagonals_down_used[i] << " "; if (diagonals_down_used[i] == 2) { cost += diagonals_down[i]; } } //cerr << "\n"; for (int i=0; i<(m + n - 1); i++) { //cerr << diagonals_down_used[i] << " "; if (diagonals_up_used[i] == 2) { cost += diagonals_up[i]; } } //cerr << "\n"; cout << cost << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...