제출 #229750

#제출 시각아이디문제언어결과실행 시간메모리
229750CoderT-Covering (eJOI19_covering)C++14
0 / 100
5 ms256 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define SZ(x) (int)(x.size()) #define F0(i,n) for(int i=0;i<n;i++) #define F1(i,n) for(int i=1;i<=n;i++) #define CL(a,x) memset(x, a, sizeof(x)); #define PR(x) cerr << #x << "=" << (x) << endl; const int MOD = 1000000007; const double pi = atan(1.0)*4.0; const double eps = 1e-8; const int N = 1000001; int i, j, k, m, n; int a[N]; int b[N], d[N], c[N]; vector<pii> v; int clbest, clsum; ll ans; const int DX[]={-1,0,1,0,0}; const int DY[]={0,1,0,-1,0}; void nosol() { cout << "No" << endl; exit(0); } bool Empty(int x, int y) { if (x < 0 || x >= m || y < 0 || y >= n) return 0; return !c[x*n + y]; } int GetA(int x, int y) { return a[x*n + y]; } void Set(int x, int y, int val) { c[x*n + y] = val; } void Fill(int x, int y) { Set(x, y, 1); ans += GetA(x, y); } void DFS(int x, int y) { F0(k, 4) { int x2 = x + 2 * DX[k], y2 = y + 2 * DY[k]; if (Empty(x2, y2) && b[x2*n + y2]) { Fill(x2, y2); v.push_back(pii(x2, y2)); DFS(x2, y2); } } } int its; void go(int at) { if (its++ > 1000000) return; if (at == SZ(v)) { if (clsum > clbest) clbest = clsum; return; } F0(k, 4) { int sum = 0; F0(dir, 4) if (dir != k) { if (!Empty(v[at].first + DX[dir], v[at].second + DY[dir])) { sum = -1; break; } else sum += GetA(v[at].first + DX[dir], v[at].second + DY[dir]); } if (sum != -1) { clsum += sum; F0(dir, 4) if (dir != k) { Set(v[at].first + DX[dir], v[at].second + DY[dir], 1); } go(at + 1); F0(dir, 4) if (dir != k) { Set(v[at].first + DX[dir], v[at].second + DY[dir], 0); } clsum -= sum; } } } int main() { freopen("x.in", "r", stdin); cin >> m >> n; F0(i, m * n) scanf("%d", &a[i]); cin >> k; while (k--) { scanf("%d%d", &i, &j); b[i*n+j] = 1; } // find pairs F0(i, m) F0(j, n) if (b[i*n + j]) { for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) if (dx || dy) { int i2 = i + dx, j2 = j + dy; if (i2 < 0 || i2 >= m || j2 < 0 || j2 >= n || !b[i2*n + j2]) continue; if (d[i*n + j] && d[i2*n + j2]) continue; if (d[i*n + j] || d[i2*n + j2]) nosol(); d[i*n + j] = 1; d[i2*n + j2] = 1; F0(k, 5) if (!Empty(i + DX[k], j + DY[k])) nosol(); F0(k, 5) if (!Empty(i2 + DX[k], j2 + DY[k])) nosol(); F0(k, 5) if (Empty(i + DX[k], j + DY[k])) Fill(i + DX[k], j + DY[k]); F0(k, 5) if (Empty(i2 + DX[k], j2 + DY[k])) Fill(i2 + DX[k], j2 + DY[k]); } } } F0(i, m) F0(j, n) if (b[i*n + j] && !d[i*n + j]) { if (!Empty(i, j)) nosol(); int found = 0; F0(k, 4) { int good = 1; F0(dir, 4) if (dir != k) { if (!Empty(i + DX[dir], j + DY[dir])) { good = 0; break; } } found = 1; break; } if (!found) nosol(); } F0(i, m) F0(j, n) if (b[i*n + j] && Empty(i, j)) { v.clear(); v.push_back(pii(i, j)); Fill(i, j); DFS(i, j); clbest = -1; its = 0; go(0); if (clbest == -1) nosol(); ans += clbest; } cout << ans << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

covering.cpp: In function 'int main()':
covering.cpp:118:17: warning: variable 'good' set but not used [-Wunused-but-set-variable]
             int good = 1;
                 ^~~~
covering.cpp:88:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("x.in", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
covering.cpp:90:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     F0(i, m * n) scanf("%d", &a[i]);
                  ~~~~~^~~~~~~~~~~~~
covering.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &i, &j);
         ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...