# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
842450 | 2023-09-02T22:10:14 Z | pera | T-Covering (eJOI19_covering) | C++17 | 80 ms | 47592 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 24160 KB | Output is correct |
2 | Correct | 9 ms | 24428 KB | Output is correct |
3 | Correct | 13 ms | 26120 KB | Output is correct |
4 | Correct | 28 ms | 30984 KB | Output is correct |
5 | Correct | 80 ms | 47424 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24152 KB | Output is correct |
2 | Incorrect | 8 ms | 24668 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24156 KB | Output is correct |
2 | Correct | 8 ms | 24664 KB | Output is correct |
3 | Correct | 14 ms | 26200 KB | Output is correct |
4 | Correct | 29 ms | 31116 KB | Output is correct |
5 | Correct | 78 ms | 47592 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 23900 KB | Output is correct |
2 | Correct | 5 ms | 23940 KB | Output is correct |
3 | Correct | 9 ms | 24920 KB | Output is correct |
4 | Correct | 8 ms | 24564 KB | Output is correct |
5 | Correct | 16 ms | 26204 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 23900 KB | Output is correct |
2 | Incorrect | 5 ms | 23908 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 24160 KB | Output is correct |
2 | Correct | 9 ms | 24428 KB | Output is correct |
3 | Correct | 13 ms | 26120 KB | Output is correct |
4 | Correct | 28 ms | 30984 KB | Output is correct |
5 | Correct | 80 ms | 47424 KB | Output is correct |
6 | Correct | 6 ms | 24152 KB | Output is correct |
7 | Incorrect | 8 ms | 24668 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 24160 KB | Output is correct |
2 | Correct | 9 ms | 24428 KB | Output is correct |
3 | Correct | 13 ms | 26120 KB | Output is correct |
4 | Correct | 28 ms | 30984 KB | Output is correct |
5 | Correct | 80 ms | 47424 KB | Output is correct |
6 | Correct | 6 ms | 24152 KB | Output is correct |
7 | Incorrect | 8 ms | 24668 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |