# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
845269 | 2023-09-06T12:54:54 Z | simona1230 | T-Covering (eJOI19_covering) | C++17 | 1000 ms | 79052 KB |
#include <bits/stdc++.h> using namespace std; vector<short int> a[1000000]; vector<int> used[1000000]; int n,m,k; struct edge { short int x,y; edge(){} edge(short int _x,short int _y) { x=_x; y=_y; } edge operator+(edge e) { return {e.x+x,e.y+y}; } }; edge pos[4]={{-1,0},{1,0},{0,-1},{0,1}}; edge p[1000000]; vector<int> v[1000000]; bool in_range(edge p) { return p.x>=0&&p.x<n&&p.y>=0&&p.y<m; } void read() { cin>>n>>m; for(int i=0;i<n;i++) { for(int j=1;j<=m;j++) { short int x; cin>>x; a[i].push_back(x); used[i].push_back(0); } } cin>>k; for(short int i=1;i<=k;i++) { cin>>p[i].x>>p[i].y; used[p[i].x][p[i].y]=i*10; for(int x=-2;x<=2;x++) { for(int y=-2;y<=2;y++) { if(x==0&&y==0||x==2&&y!=0||x==-2&&y!=0||y==2&&x!=0||y==-2&&x!=0)continue; edge nb={p[i].x+x,p[i].y+y}; if(in_range(nb)&&used[nb.x][nb.y]) { v[i].push_back(used[nb.x][nb.y]/10); v[used[nb.x][nb.y]/10].push_back(i); } } } } } short int minn; int sum,curr,cnt; void use(edge e) { for(int i=0;i<4;i++) { edge nb=pos[i]+e; if(in_range(nb)&&!used[nb.x][nb.y]) { used[nb.x][nb.y]=1; if(minn>a[nb.x][nb.y])minn=a[nb.x][nb.y]; sum+=a[nb.x][nb.y]; cnt++; } } } void dfs(int num) { edge e=p[num]; //cout<<e.x<<" "<<e.y<<endl; cnt++; curr++; sum+=a[e.x][e.y]; used[e.x][e.y]+=1; use(e); for(short int i=0;i<v[num].size();i++) { int nb=v[num][i]; if(in_range(p[nb])&&!(used[p[nb].x][p[nb].y]%10)) { dfs(nb); } } } void solve() { int ans=0; for(int i=1;i<=k;i++) { if(!(used[p[i].x][p[i].y]%10)) { //cout<<p[i].x<<" "<<p[i].y<<endl; cnt=0; minn=1e3; curr=0; sum=0; dfs(i); //cout<<endl; //cout<<cnt<<" "<<curr<<" "<<sum<<" "<<minn<<endl; if(cnt<curr*4) { cout<<"No"<<'\n'; exit(0); } if(cnt==curr*4) { ans+=sum; } if(cnt==curr*4+1) { ans+=sum; ans-=minn; } } } cout<<ans<<'\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); read(); solve(); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 72796 KB | Output is correct |
2 | Correct | 17 ms | 72792 KB | Output is correct |
3 | Correct | 20 ms | 73560 KB | Output is correct |
4 | Correct | 39 ms | 74832 KB | Output is correct |
5 | Correct | 71 ms | 78608 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 72796 KB | Output is correct |
2 | Correct | 17 ms | 72796 KB | Output is correct |
3 | Correct | 20 ms | 73308 KB | Output is correct |
4 | Correct | 31 ms | 74832 KB | Output is correct |
5 | Correct | 69 ms | 78576 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 73048 KB | Output is correct |
2 | Correct | 17 ms | 72796 KB | Output is correct |
3 | Correct | 20 ms | 73308 KB | Output is correct |
4 | Correct | 33 ms | 74824 KB | Output is correct |
5 | Correct | 70 ms | 78672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 72536 KB | Output is correct |
2 | Correct | 17 ms | 72536 KB | Output is correct |
3 | Correct | 19 ms | 73052 KB | Output is correct |
4 | Correct | 18 ms | 72792 KB | Output is correct |
5 | Correct | 21 ms | 73560 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 72536 KB | Output is correct |
2 | Correct | 15 ms | 72536 KB | Output is correct |
3 | Correct | 16 ms | 72536 KB | Output is correct |
4 | Correct | 15 ms | 72536 KB | Output is correct |
5 | Correct | 15 ms | 72536 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 72796 KB | Output is correct |
2 | Correct | 17 ms | 72792 KB | Output is correct |
3 | Correct | 20 ms | 73560 KB | Output is correct |
4 | Correct | 39 ms | 74832 KB | Output is correct |
5 | Correct | 71 ms | 78608 KB | Output is correct |
6 | Correct | 16 ms | 72796 KB | Output is correct |
7 | Correct | 17 ms | 72796 KB | Output is correct |
8 | Correct | 20 ms | 73308 KB | Output is correct |
9 | Correct | 31 ms | 74832 KB | Output is correct |
10 | Correct | 69 ms | 78576 KB | Output is correct |
11 | Correct | 16 ms | 73048 KB | Output is correct |
12 | Correct | 17 ms | 72796 KB | Output is correct |
13 | Correct | 20 ms | 73308 KB | Output is correct |
14 | Correct | 33 ms | 74824 KB | Output is correct |
15 | Correct | 70 ms | 78672 KB | Output is correct |
16 | Correct | 15 ms | 72536 KB | Output is correct |
17 | Correct | 17 ms | 72536 KB | Output is correct |
18 | Correct | 19 ms | 73052 KB | Output is correct |
19 | Correct | 18 ms | 72792 KB | Output is correct |
20 | Correct | 21 ms | 73560 KB | Output is correct |
21 | Correct | 16 ms | 72792 KB | Output is correct |
22 | Correct | 18 ms | 72792 KB | Output is correct |
23 | Correct | 21 ms | 73308 KB | Output is correct |
24 | Correct | 32 ms | 74844 KB | Output is correct |
25 | Correct | 70 ms | 78660 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 72796 KB | Output is correct |
2 | Correct | 17 ms | 72792 KB | Output is correct |
3 | Correct | 20 ms | 73560 KB | Output is correct |
4 | Correct | 39 ms | 74832 KB | Output is correct |
5 | Correct | 71 ms | 78608 KB | Output is correct |
6 | Correct | 16 ms | 72796 KB | Output is correct |
7 | Correct | 17 ms | 72796 KB | Output is correct |
8 | Correct | 20 ms | 73308 KB | Output is correct |
9 | Correct | 31 ms | 74832 KB | Output is correct |
10 | Correct | 69 ms | 78576 KB | Output is correct |
11 | Correct | 16 ms | 73048 KB | Output is correct |
12 | Correct | 17 ms | 72796 KB | Output is correct |
13 | Correct | 20 ms | 73308 KB | Output is correct |
14 | Correct | 33 ms | 74824 KB | Output is correct |
15 | Correct | 70 ms | 78672 KB | Output is correct |
16 | Correct | 15 ms | 72536 KB | Output is correct |
17 | Correct | 17 ms | 72536 KB | Output is correct |
18 | Correct | 19 ms | 73052 KB | Output is correct |
19 | Correct | 18 ms | 72792 KB | Output is correct |
20 | Correct | 21 ms | 73560 KB | Output is correct |
21 | Correct | 16 ms | 72536 KB | Output is correct |
22 | Correct | 15 ms | 72536 KB | Output is correct |
23 | Correct | 16 ms | 72536 KB | Output is correct |
24 | Correct | 15 ms | 72536 KB | Output is correct |
25 | Correct | 15 ms | 72536 KB | Output is correct |
26 | Correct | 16 ms | 72792 KB | Output is correct |
27 | Correct | 18 ms | 72792 KB | Output is correct |
28 | Correct | 21 ms | 73308 KB | Output is correct |
29 | Correct | 32 ms | 74844 KB | Output is correct |
30 | Correct | 70 ms | 78660 KB | Output is correct |
31 | Execution timed out | 1029 ms | 79052 KB | Time limit exceeded |
32 | Halted | 0 ms | 0 KB | - |