# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
842451 | 2023-09-02T22:12:21 Z | pera | T-Covering (eJOI19_covering) | C++17 | 262 ms | 70652 KB |
#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e6 + 1; int dx[4] = {0 , 0 , -1 , 1}; int dy[4] = {1 , -1 , 0 , 0}; int n , m , ans = 0 , ok = 1; vector<vector<int>> a , v , gd; vector<int> g[N]; main(){ scanf("%lld%lld" , &n , &m); a.resize(n) , v.resize(n); gd.resize(n); for(int i = 0;i < n;i ++){ a[i].resize(m); v[i].resize(m); gd[i].resize(m); for(int j = 0;j < m;j ++){ scanf("%lld" , &a[i][j]); } } int sp; scanf("%lld" , &sp); for(int i = 1;i <= sp;i ++){ int x , y; scanf("%lld%lld" , &x , &y); gd[x][y] = 1; ans += a[x][y]; for(int k = 0;k < 4;k ++){ int I = x + dx[k] , J = y + dy[k]; if(0 <= I && I < n && 0 <= J && J < m){ g[I * m + J].push_back(x * m + y); g[x * m + y].push_back(I * m + J); } } } for(int i = 0;i < n;i ++){ for(int j = 0;j < m;j ++){ if(v[i][j] == 0 && gd[i][j] == 1){ int spc = 0 , sz = 0; queue<int> q; vector<int> all; q.push(i * m + j); v[i][j] = 1;/* cout << "st: ";*/ while(q.size()){ int vl = q.front(); q.pop(); int I = vl / m , J = vl % m;/* cout << I << " " << J << endl;*/ spc += gd[I][J]; if(gd[I][J] == 0) all.push_back(a[I][J]); for(int k = 0;k < g[vl].size();k ++){ if(v[g[vl][k] / m][g[vl][k] % m] == 0){ v[g[vl][k] / m][g[vl][k] % m] = 1; q.push(g[vl][k]); } } sz ++; } /*cout << "---" << endl; cout << "i , j : " << i << " " << j << " " << sz << endl;*/ if(sz < spc * 4){ printf("%s" , "No"); return 0; } assert(all.size() >= spc * 3); sort(all.rbegin() , all.rend()); for(int k = 0;k < spc * 3;k ++){ ans += all[k]; } } } } printf("%lld" , ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24152 KB | Output is correct |
2 | Correct | 8 ms | 24668 KB | Output is correct |
3 | Correct | 15 ms | 26520 KB | Output is correct |
4 | Correct | 32 ms | 31068 KB | Output is correct |
5 | Correct | 86 ms | 47436 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24152 KB | Output is correct |
2 | Correct | 9 ms | 24668 KB | Output is correct |
3 | Correct | 14 ms | 26312 KB | Output is correct |
4 | Correct | 29 ms | 30952 KB | Output is correct |
5 | Correct | 83 ms | 47552 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24156 KB | Output is correct |
2 | Correct | 7 ms | 24440 KB | Output is correct |
3 | Correct | 12 ms | 26068 KB | Output is correct |
4 | Correct | 33 ms | 31112 KB | Output is correct |
5 | Correct | 81 ms | 47532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 23900 KB | Output is correct |
2 | Correct | 5 ms | 23900 KB | Output is correct |
3 | Correct | 9 ms | 24920 KB | Output is correct |
4 | Correct | 8 ms | 24668 KB | Output is correct |
5 | Correct | 18 ms | 26204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 23900 KB | Output is correct |
2 | Correct | 5 ms | 23896 KB | Output is correct |
3 | Correct | 5 ms | 23900 KB | Output is correct |
4 | Correct | 5 ms | 23928 KB | Output is correct |
5 | Correct | 5 ms | 23900 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24152 KB | Output is correct |
2 | Correct | 8 ms | 24668 KB | Output is correct |
3 | Correct | 15 ms | 26520 KB | Output is correct |
4 | Correct | 32 ms | 31068 KB | Output is correct |
5 | Correct | 86 ms | 47436 KB | Output is correct |
6 | Correct | 6 ms | 24152 KB | Output is correct |
7 | Correct | 9 ms | 24668 KB | Output is correct |
8 | Correct | 14 ms | 26312 KB | Output is correct |
9 | Correct | 29 ms | 30952 KB | Output is correct |
10 | Correct | 83 ms | 47552 KB | Output is correct |
11 | Correct | 6 ms | 24156 KB | Output is correct |
12 | Correct | 7 ms | 24440 KB | Output is correct |
13 | Correct | 12 ms | 26068 KB | Output is correct |
14 | Correct | 33 ms | 31112 KB | Output is correct |
15 | Correct | 81 ms | 47532 KB | Output is correct |
16 | Correct | 5 ms | 23900 KB | Output is correct |
17 | Correct | 5 ms | 23900 KB | Output is correct |
18 | Correct | 9 ms | 24920 KB | Output is correct |
19 | Correct | 8 ms | 24668 KB | Output is correct |
20 | Correct | 18 ms | 26204 KB | Output is correct |
21 | Correct | 6 ms | 24156 KB | Output is correct |
22 | Correct | 7 ms | 24476 KB | Output is correct |
23 | Correct | 13 ms | 26204 KB | Output is correct |
24 | Correct | 27 ms | 31048 KB | Output is correct |
25 | Correct | 79 ms | 47488 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24152 KB | Output is correct |
2 | Correct | 8 ms | 24668 KB | Output is correct |
3 | Correct | 15 ms | 26520 KB | Output is correct |
4 | Correct | 32 ms | 31068 KB | Output is correct |
5 | Correct | 86 ms | 47436 KB | Output is correct |
6 | Correct | 6 ms | 24152 KB | Output is correct |
7 | Correct | 9 ms | 24668 KB | Output is correct |
8 | Correct | 14 ms | 26312 KB | Output is correct |
9 | Correct | 29 ms | 30952 KB | Output is correct |
10 | Correct | 83 ms | 47552 KB | Output is correct |
11 | Correct | 6 ms | 24156 KB | Output is correct |
12 | Correct | 7 ms | 24440 KB | Output is correct |
13 | Correct | 12 ms | 26068 KB | Output is correct |
14 | Correct | 33 ms | 31112 KB | Output is correct |
15 | Correct | 81 ms | 47532 KB | Output is correct |
16 | Correct | 5 ms | 23900 KB | Output is correct |
17 | Correct | 5 ms | 23900 KB | Output is correct |
18 | Correct | 9 ms | 24920 KB | Output is correct |
19 | Correct | 8 ms | 24668 KB | Output is correct |
20 | Correct | 18 ms | 26204 KB | Output is correct |
21 | Correct | 6 ms | 23900 KB | Output is correct |
22 | Correct | 5 ms | 23896 KB | Output is correct |
23 | Correct | 5 ms | 23900 KB | Output is correct |
24 | Correct | 5 ms | 23928 KB | Output is correct |
25 | Correct | 5 ms | 23900 KB | Output is correct |
26 | Correct | 6 ms | 24156 KB | Output is correct |
27 | Correct | 7 ms | 24476 KB | Output is correct |
28 | Correct | 13 ms | 26204 KB | Output is correct |
29 | Correct | 27 ms | 31048 KB | Output is correct |
30 | Correct | 79 ms | 47488 KB | Output is correct |
31 | Correct | 262 ms | 70652 KB | Output is correct |
32 | Correct | 84 ms | 48488 KB | Output is correct |
33 | Correct | 95 ms | 50516 KB | Output is correct |
34 | Correct | 84 ms | 48208 KB | Output is correct |
35 | Correct | 162 ms | 56516 KB | Output is correct |