# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
845265 | 2023-09-06T12:53:42 Z | simona1230 | T-Covering (eJOI19_covering) | C++17 | 1000 ms | 82740 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"<<endl; exit(0); } if(cnt==curr*4) { ans+=sum; } if(cnt==curr*4+1) { ans+=sum; ans-=minn; } } } cout<<ans<<endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); read(); solve(); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 72976 KB | Output is correct |
2 | Correct | 17 ms | 73048 KB | Output is correct |
3 | Correct | 20 ms | 73564 KB | Output is correct |
4 | Correct | 32 ms | 76008 KB | Output is correct |
5 | Correct | 69 ms | 82260 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 72736 KB | Output is correct |
2 | Correct | 17 ms | 73048 KB | Output is correct |
3 | Correct | 20 ms | 73564 KB | Output is correct |
4 | Correct | 31 ms | 76112 KB | Output is correct |
5 | Correct | 72 ms | 82520 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 72732 KB | Output is correct |
2 | Correct | 17 ms | 73048 KB | Output is correct |
3 | Correct | 21 ms | 73556 KB | Output is correct |
4 | Correct | 32 ms | 76120 KB | Output is correct |
5 | Correct | 71 ms | 82476 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 72540 KB | Output is correct |
2 | Correct | 15 ms | 72792 KB | Output is correct |
3 | Correct | 18 ms | 73304 KB | Output is correct |
4 | Correct | 17 ms | 73048 KB | Output is correct |
5 | Correct | 21 ms | 73860 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 72536 KB | Output is correct |
2 | Correct | 15 ms | 72536 KB | Output is correct |
3 | Correct | 15 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 | 17 ms | 72976 KB | Output is correct |
2 | Correct | 17 ms | 73048 KB | Output is correct |
3 | Correct | 20 ms | 73564 KB | Output is correct |
4 | Correct | 32 ms | 76008 KB | Output is correct |
5 | Correct | 69 ms | 82260 KB | Output is correct |
6 | Correct | 16 ms | 72736 KB | Output is correct |
7 | Correct | 17 ms | 73048 KB | Output is correct |
8 | Correct | 20 ms | 73564 KB | Output is correct |
9 | Correct | 31 ms | 76112 KB | Output is correct |
10 | Correct | 72 ms | 82520 KB | Output is correct |
11 | Correct | 16 ms | 72732 KB | Output is correct |
12 | Correct | 17 ms | 73048 KB | Output is correct |
13 | Correct | 21 ms | 73556 KB | Output is correct |
14 | Correct | 32 ms | 76120 KB | Output is correct |
15 | Correct | 71 ms | 82476 KB | Output is correct |
16 | Correct | 15 ms | 72540 KB | Output is correct |
17 | Correct | 15 ms | 72792 KB | Output is correct |
18 | Correct | 18 ms | 73304 KB | Output is correct |
19 | Correct | 17 ms | 73048 KB | Output is correct |
20 | Correct | 21 ms | 73860 KB | Output is correct |
21 | Correct | 16 ms | 72792 KB | Output is correct |
22 | Correct | 17 ms | 73048 KB | Output is correct |
23 | Correct | 21 ms | 73564 KB | Output is correct |
24 | Correct | 31 ms | 76120 KB | Output is correct |
25 | Correct | 70 ms | 82516 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 72976 KB | Output is correct |
2 | Correct | 17 ms | 73048 KB | Output is correct |
3 | Correct | 20 ms | 73564 KB | Output is correct |
4 | Correct | 32 ms | 76008 KB | Output is correct |
5 | Correct | 69 ms | 82260 KB | Output is correct |
6 | Correct | 16 ms | 72736 KB | Output is correct |
7 | Correct | 17 ms | 73048 KB | Output is correct |
8 | Correct | 20 ms | 73564 KB | Output is correct |
9 | Correct | 31 ms | 76112 KB | Output is correct |
10 | Correct | 72 ms | 82520 KB | Output is correct |
11 | Correct | 16 ms | 72732 KB | Output is correct |
12 | Correct | 17 ms | 73048 KB | Output is correct |
13 | Correct | 21 ms | 73556 KB | Output is correct |
14 | Correct | 32 ms | 76120 KB | Output is correct |
15 | Correct | 71 ms | 82476 KB | Output is correct |
16 | Correct | 15 ms | 72540 KB | Output is correct |
17 | Correct | 15 ms | 72792 KB | Output is correct |
18 | Correct | 18 ms | 73304 KB | Output is correct |
19 | Correct | 17 ms | 73048 KB | Output is correct |
20 | Correct | 21 ms | 73860 KB | Output is correct |
21 | Correct | 15 ms | 72536 KB | Output is correct |
22 | Correct | 15 ms | 72536 KB | Output is correct |
23 | Correct | 15 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 | 17 ms | 73048 KB | Output is correct |
28 | Correct | 21 ms | 73564 KB | Output is correct |
29 | Correct | 31 ms | 76120 KB | Output is correct |
30 | Correct | 70 ms | 82516 KB | Output is correct |
31 | Execution timed out | 1010 ms | 82740 KB | Time limit exceeded |
32 | Halted | 0 ms | 0 KB | - |