Submission #462591

#	Time	Username	Problem	Language	Result	Execution time	Memory
462591		AdamGS	T-Covering (eJOI19_covering)	C++14	15 / 100	1097 ms	588 KiB

covering

#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") 
#pragma GCC option("arch=native","tune=native","no-zero-upper") 
#pragma GCC target("avx2","popcnt","rdrnd","bmi2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	int T[n][m], kiedy[n][m];
	rep(i, n) rep(j, m) {
		cin >> T[i][j];
		kiedy[i][j]=-1;
	}
	int k;
	cin >> k;
	pair<int,int>S[k];
	rep(i, k) cin >> S[i].st >> S[i].nd;
	int ma=-1, akt=0;
	rep(i, 1<<k) rep(j, 1<<k) {
		int sum=0;
		bool ok=true;
		rep(l, k) {
			sum+=T[S[l].st][S[l].nd];
			kiedy[S[l].st][S[l].nd]=akt;
			int a=0;
			if(i&(1<<l)) a+=2;
			if(j&(1<<l)) ++a;
			if(0<=S[l].st-1) sum+=T[S[l].st-1][S[l].nd];
			if(S[l].st+1<n) sum+=T[S[l].st+1][S[l].nd];
			if(0<=S[l].nd-1) sum+=T[S[l].st][S[l].nd-1];
			if(S[l].nd+1<m) sum+=T[S[l].st][S[l].nd+1];
			kiedy[S[l].st][S[l].nd]=akt;
			if(a==0) {
				if(0<=S[l].st-1 && 0<=S[l].nd-1 && S[l].nd+1<m) {
					if(kiedy[S[l].st-1][S[l].nd]==akt) ok=false;
					kiedy[S[l].st-1][S[l].nd]=akt;
					if(kiedy[S[l].st][S[l].nd-1]==akt) ok=false;
					kiedy[S[l].st][S[l].nd-1]=akt;
					if(kiedy[S[l].st][S[l].nd+1]==akt) ok=false;
					kiedy[S[l].st][S[l].nd+1]=akt;
					if(S[l].st+1<n) sum-=T[S[l].st+1][S[l].nd];
				} else ok=false;
			} else if(a==1) {
				if(S[l].st+1<n && 0<=S[l].nd-1 && S[l].nd+1<m) {
					if(kiedy[S[l].st+1][S[l].nd]==akt) ok=false;
					kiedy[S[l].st+1][S[l].nd]=akt;
					if(kiedy[S[l].st][S[l].nd-1]==akt) ok=false;
					kiedy[S[l].st][S[l].nd-1]=akt;
					if(kiedy[S[l].st][S[l].nd+1]==akt) ok=false;
					kiedy[S[l].st][S[l].nd+1]=akt;
					if(0<=S[l].st-1) sum-=T[S[l].st-1][S[l].nd];
				} else ok=false;
			} else if(a==2) {
				if(0<=S[l].st-1 && S[l].st+1<n && S[l].nd+1<m) {
					if(kiedy[S[l].st-1][S[l].nd]==akt) ok=false;
					kiedy[S[l].st-1][S[l].nd]=akt;
					if(kiedy[S[l].st+1][S[l].nd]==akt) ok=false;
					kiedy[S[l].st+1][S[l].nd]=akt;
					if(kiedy[S[l].st][S[l].nd+1]==akt) ok=false;
					kiedy[S[l].st][S[l].nd+1]=akt;
					if(0<=S[l].nd-1) sum-=T[S[l].st][S[l].nd-1];
				} else ok=false;
			} else {
				if(0<=S[l].st-1 && S[l].st+1<n && 0<=S[l].nd-1) {
					if(kiedy[S[l].st-1][S[l].nd]==akt) ok=false;
					kiedy[S[l].st-1][S[l].nd]=akt;
					if(kiedy[S[l].st+1][S[l].nd]==akt) ok=false;
					kiedy[S[l].st+1][S[l].nd]=akt;
					if(kiedy[S[l].st][S[l].nd-1]==akt) ok=false;
					kiedy[S[l].st][S[l].nd-1]=akt;
					if(S[l].nd+1<m) sum-=T[S[l].st][S[l].nd+1];
				} else ok=false;
			}
		}
		if(ok) ma=max(ma, sum);
		++akt;
	}
	if(ma==-1) cout << "No\n";
	else cout << ma << '\n';
}

Compilation message (stderr)

covering.cpp:2: warning: ignoring '#pragma GCC option' [-Wunknown-pragmas]
    2 | #pragma GCC option("arch=native","tune=native","no-zero-upper")
      |

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 15 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 30