Submission #842447

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
842447	2023-09-02T22:04:39 Z	pera	T-Covering (eJOI19_covering)	C++17	100 / 100	247 ms	70440 KB

covering

#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};

vector<int> g[N];
 
main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n , m , ans = 0 , ok = 1;
	cin >> n >> m;
	vector<vector<int>> a(n , vector<int>(m)) , v(n , vector<int>(m)) , gd(n , vector<int>(m));
	for(int i = 0;i < n;i ++){
		for(int j = 0;j < m;j ++){
			cin >> a[i][j];
		}
	}
	int sp;cin >> sp;
	for(int i = 1;i <= sp;i ++){
		int x , y;cin >> 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){
					cout << "No" << endl;
					return 0;
				}
				assert(all.size() >= spc * 3);
				sort(all.rbegin() , all.rend());
				for(int k = 0;k < spc * 3;k ++){
					ans += all[k];
				}
			}
		}
	}
	cout << ans << endl;
}

Compilation message

covering.cpp:13:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   13 | main(){
      | ^~~~
covering.cpp: In function 'int main()':
covering.cpp:53:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |      for(int k = 0;k < g[vl].size();k ++){
      |                    ~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from covering.cpp:1:
covering.cpp:67:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   67 |     assert(all.size() >= spc * 3);
      |            ~~~~~~~~~~~^~~~~~~~~~
covering.cpp:16:24: warning: unused variable 'ok' [-Wunused-variable]
   16 |  int n , m , ans = 0 , ok = 1;
      |                        ^~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	24152 KB	Output is correct
2	Correct	7 ms	24664 KB	Output is correct
3	Correct	11 ms	26200 KB	Output is correct
4	Correct	22 ms	31064 KB	Output is correct
5	Correct	63 ms	47648 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	24152 KB	Output is correct
2	Correct	7 ms	24664 KB	Output is correct
3	Correct	11 ms	26200 KB	Output is correct
4	Correct	25 ms	31068 KB	Output is correct
5	Correct	63 ms	47696 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	24152 KB	Output is correct
2	Correct	8 ms	24664 KB	Output is correct
3	Correct	13 ms	26456 KB	Output is correct
4	Correct	24 ms	31064 KB	Output is correct
5	Correct	62 ms	47704 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	23900 KB	Output is correct
2	Correct	5 ms	23896 KB	Output is correct
3	Correct	8 ms	24920 KB	Output is correct
4	Correct	9 ms	24664 KB	Output is correct
5	Correct	13 ms	26456 KB	Output is correct

Subtask #5

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	23896 KB	Output is correct
2	Correct	5 ms	23896 KB	Output is correct
3	Correct	5 ms	23896 KB	Output is correct
4	Correct	5 ms	23896 KB	Output is correct
5	Correct	6 ms	23896 KB	Output is correct

Subtask #6

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	24152 KB	Output is correct
2	Correct	7 ms	24664 KB	Output is correct
3	Correct	11 ms	26200 KB	Output is correct
4	Correct	22 ms	31064 KB	Output is correct
5	Correct	63 ms	47648 KB	Output is correct
6	Correct	6 ms	24152 KB	Output is correct
7	Correct	7 ms	24664 KB	Output is correct
8	Correct	11 ms	26200 KB	Output is correct
9	Correct	25 ms	31068 KB	Output is correct
10	Correct	63 ms	47696 KB	Output is correct
11	Correct	6 ms	24152 KB	Output is correct
12	Correct	8 ms	24664 KB	Output is correct
13	Correct	13 ms	26456 KB	Output is correct
14	Correct	24 ms	31064 KB	Output is correct
15	Correct	62 ms	47704 KB	Output is correct
16	Correct	5 ms	23900 KB	Output is correct
17	Correct	5 ms	23896 KB	Output is correct
18	Correct	8 ms	24920 KB	Output is correct
19	Correct	9 ms	24664 KB	Output is correct
20	Correct	13 ms	26456 KB	Output is correct
21	Correct	7 ms	24152 KB	Output is correct
22	Correct	10 ms	24664 KB	Output is correct
23	Correct	11 ms	26456 KB	Output is correct
24	Correct	23 ms	31064 KB	Output is correct
25	Correct	62 ms	47696 KB	Output is correct

Subtask #7

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	24152 KB	Output is correct
2	Correct	7 ms	24664 KB	Output is correct
3	Correct	11 ms	26200 KB	Output is correct
4	Correct	22 ms	31064 KB	Output is correct
5	Correct	63 ms	47648 KB	Output is correct
6	Correct	6 ms	24152 KB	Output is correct
7	Correct	7 ms	24664 KB	Output is correct
8	Correct	11 ms	26200 KB	Output is correct
9	Correct	25 ms	31068 KB	Output is correct
10	Correct	63 ms	47696 KB	Output is correct
11	Correct	6 ms	24152 KB	Output is correct
12	Correct	8 ms	24664 KB	Output is correct
13	Correct	13 ms	26456 KB	Output is correct
14	Correct	24 ms	31064 KB	Output is correct
15	Correct	62 ms	47704 KB	Output is correct
16	Correct	5 ms	23900 KB	Output is correct
17	Correct	5 ms	23896 KB	Output is correct
18	Correct	8 ms	24920 KB	Output is correct
19	Correct	9 ms	24664 KB	Output is correct
20	Correct	13 ms	26456 KB	Output is correct
21	Correct	6 ms	23896 KB	Output is correct
22	Correct	5 ms	23896 KB	Output is correct
23	Correct	5 ms	23896 KB	Output is correct
24	Correct	5 ms	23896 KB	Output is correct
25	Correct	6 ms	23896 KB	Output is correct
26	Correct	7 ms	24152 KB	Output is correct
27	Correct	10 ms	24664 KB	Output is correct
28	Correct	11 ms	26456 KB	Output is correct
29	Correct	23 ms	31064 KB	Output is correct
30	Correct	62 ms	47696 KB	Output is correct
31	Correct	247 ms	70440 KB	Output is correct
32	Correct	63 ms	48208 KB	Output is correct
33	Correct	75 ms	50512 KB	Output is correct
34	Correct	66 ms	48124 KB	Output is correct
35	Correct	142 ms	56516 KB	Output is correct