QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#344621 | #2476. Pizzo Collectors | PetroTarnavskyi# | TL | 0ms | 0kb | C++20 | 5.4kb | 2024-03-04 20:32:35 | 2024-03-04 20:32:35 |
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 55;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const vector<PII> knightMoves = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
int n;
string s[N];
bool illuminated[N][N];
bool g[N][N]; // for dfs
int flockIdx[N][N];
int connectedToBorder[N][N];
int width[N * N];
bool ok(int i, int j)
{
return 0 <= i && i < n && 0 <= j && j < n;
}
void dfs(int i, int j, int used[N][N])
{
FOR(k, 0, 4)
{
int ni = i + dx[k], nj = j + dy[k];
if (ok(ni, nj) && g[ni][nj] && used[ni][nj] == -1)
{
used[ni][nj] = used[i][j];
dfs(ni, nj, used);
}
}
}
void calcWidth(int i, int j, int di, int dj)
{
int w = 0;
while (ok(i, j))
{
int fl = flockIdx[i][j];
if (fl == -1)
w = 0;
else
{
w++;
width[fl] = max(width[fl], w);
}
i += di;
j += dj;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
getline(cin, s[0]);
FOR(i, 0, n)
getline(cin, s[i]);
LL ans = 0;
// suns
FOR(i, 0, n)
{
FOR(j, 0, n)
{
FOR(di, -1, 2)
{
FOR(dj, -1, 2)
{
int r = i + di, c = j + dj;
while (ok(r, c) && s[r][c] == ' ')
{
r += di;
c += dj;
}
if (ok(r, c) && s[r][c] != '*')
illuminated[r][c] = true;
}
}
}
}
FOR(i, 0, n)
FOR(j, 0, n)
if (illuminated[i][j])
ans += 100;
// birds
FOR(i, 0, n)
FOR(j, 0, n)
{
flockIdx[i][j] = -1;
g[i][j] = s[i][j] == 'v' || s[i][j] == 'D';
}
int flocks = 0;
FOR(i, 0, n)
{
FOR(j, 0, n)
{
if (g[i][j] && flockIdx[i][j] == -1)
{
flockIdx[i][j] = flocks++;
dfs(i, j, flockIdx);
}
}
}
FOR(i, 0, n)
{
// horizontal
calcWidth(i, 0, 0, 1);
// vertical
calcWidth(0, i, 1, 0);
// diagonal
calcWidth(i, 0, 1, 1);
calcWidth(0, i, 1, 1);
calcWidth(i, 0, -1, 1);
calcWidth(n - 1, i, -1, 1);
}
FOR(i, 0, flocks)
ans += 500 * width[i];
// flock perimeter
FOR(i, 0, n)
{
FOR(j, 0, n)
{
if (g[i][j])
{
FOR(k, 0, 4)
{
int ni = i + dx[k], nj = j + dy[k];
if (!ok(ni, nj) || !g[ni][nj])
ans += 60;
}
}
}
}
#warning
// house view up and down
FOR(i, 0, n)
{
FOR(j, 0, n)
{
if (s[i][j] == '^')
{
// up
for (int k = i - 1; k >= 0 && s[k][j] == ' '; k--)
{
ans += 10;
}
// down
for (int k = i + 1; k < n && s[k][j] == ' '; k++)
{
ans += 5;
}
}
}
}
// 3x3 blocks
set<string> uniqueBlocks;
FOR(i, 0, n - 2)
{
FOR(j, 0, n - 2)
{
string t;
FOR(ii, i, i + 3)
{
FOR(jj, j, j + 3)
{
t += s[ii][jj];
}
}
uniqueBlocks.insert(t);
}
}
ans += SZ(uniqueBlocks);
// animals i
FOR(i, 0, n)
{
FOR(j, 0, n)
{
if (s[i][j] != '!' && s[i][j] != 'v' && s[i][j] != 'D')
{
continue;
}
FOR(k, 0, 4)
{
int ni = i + dx[k], nj = j + dy[k];
if (ok(ni, nj) && s[ni][nj] == ' ')
ans += 15;
}
}
}
// freedom
FOR(i, 0, n)
FOR(j, 0, n)
g[i][j] = (i == 0 || i == n - 1 || j == 0 || j == n - 1) && s[i][j] == ' ';
FOR(i, 0, n)
FOR(j, 0, n)
if (g[i][j] && connectedToBorder[i][j] == 0)
{
connectedToBorder[i][j] = 1;
dfs(i, j, connectedToBorder);
}
FOR(i, 0, n)
FOR(j, 0, n)
{
if (s[i][j] == ' ')
continue;
bool freedom = false;
FOR(k, 0, 4)
{
int ni = i + dx[k], nj = j + dy[k];
freedom |= ok(ni, nj) && connectedToBorder[ni][nj];
}
if (freedom)
{
ans += 7;
}
}
// chupakabra
FOR(i, 0, n)
{
FOR(j, 0, n)
{
if (s[i][j] != 'v' && s[i][j] != 'B')
{
continue;
}
bool can = false;
for (auto [kdx, kdy] : knightMoves)
{
int ni = i + kdx, nj = j + kdy;
can |= ok(ni, nj) && s[ni][nj] == '!';
}
if (can)
ans += 200;
}
}
// peaks
vector<PII> peaks;
FOR(i, 0, n)
FOR(j, 0, n - 1)
{
if (s[i][j] == '/' && s[i][j] == '\\')
peaks.PB({i, j});
}
for (auto [i1, j1] : peaks)
{
int mx = 0;
for (auto [i2, j2] : peaks)
{
int d = abs(i2 - i1) + abs(j2 - j1);
if (d != 0)
mx = max(mx, d);
}
ans += 50 * mx;
}
vector<tuple<char, char, int>> drakeGrill = {{'D', 'G', 500}, {'G', 'D', 50}};
// drake/grill and grill/drake
for (auto [c1, c2, score] : drakeGrill)
{
FOR(i, 0, n)
{
FOR(j, 0, n)
{
if (s[i][j] != c1)
continue;
bool can = false;
FOR(k, 0, 4)
{
int ni = i + dx[k], nj = j + dy[k];
can |= ok(ni, nj) && s[ni][nj] == 'G';
}
if (can)
ans += score;
}
}
}
map<char, int> cnt;
// minimum frequency
FOR(i, 0, n)
{
FOR(j, 0, n)
{
cnt[s[i][j]]++;
}
}
int mn = n * n + 1;
for (auto [c, cn] : cnt)
if (c != ' ')
mn = min(mn, cn);
if (mn <= n * n)
ans += 10 * mn;
// empty fields
ans += cnt[' '];
// animals ii
ans += (LL)cnt['!'] * cnt['b'] * cnt['D'];
ans += 3 * min(cnt['^'], cnt['G']);
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
8 ?A?B?A?C 3 A 1 B 1000 C 100000