Submission #1248346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248346		andrei_n	Game (eJOI20_game)	C++20	100 / 100	1 ms	468 KiB

game

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.h>
#else
#define debug
#endif // LOCAL

using namespace std;

const int INF = 999999;
vector<int> v[500];
vector<int> lant;
vector<int> ciclu;
vector<int> mic;
int vis[500];
int cnt, out;
vector<vector<vector<int>>> dp;

void dfs(int node)
{
//    debug("%, ", node);
    if(node == 0)
    {
        out = 1;
        return;
    }
    ++cnt;
    vis[node] = 1;
    for(auto &oth : v[node])
        if(!vis[oth])
            dfs(oth);
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, m; cin>>n>>m;
    char ch;
    for(int i=1; i<=n+1; ++i)
        for(int j=1; j<=m; ++j)
        {
            cin>>ch;
            if(ch == '0')
            {
                int a = (i-1)*(m+1)+j;
                int b = i*(m+1)+j;
                if(i == 1) a = 0;
                if(i == n+1) b = 0;
                v[a].push_back(b);
                v[b].push_back(a);
            }
        }
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m+1; ++j)
        {
            cin>>ch;
            if(ch == '0')
            {
                int a = i*(m+1)+j-1;
                int b = i*(m+1)+j;
                if(j == 1) a = 0;
                if(j == m+1) b = 0;
                v[a].push_back(b);
                v[b].push_back(a);
            }
        }
    mic.push_back(INF);
    lant.push_back(INF);
    ciclu.push_back(INF);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            if(vis[i*(m+1)+j]) continue;
            cnt = out = 0;
            dfs(i*(m+1)+j);
//            debug("\n");
            if(cnt == 1 && !out) continue;
            if(cnt == 1)
                mic.push_back(1);
            else if(cnt == 2)
                mic.push_back(2);
            else if(out)
                lant.push_back(cnt);
            else
                ciclu.push_back(cnt);
        }
    sort(mic.begin(), mic.end(), greater<int>());
    sort(lant.begin(), lant.end(), greater<int>());
    sort(ciclu.begin(), ciclu.end(), greater<int>());
    int A = mic.size()-1, B = lant.size()-1, C = ciclu.size()-1;
//    debug("mic = %\nlant = %\nciclu = %\n", mic, lant, ciclu);
    dp.assign(A+5, vector<vector<int>>(B+5, vector<int>(C+5, -INF)));
    for(int a=0; a<=A; ++a)
        for(int b=0; b<=B; ++b)
            for(int c=0; c<=C; ++c)
            {
                if(!a && !b && !c) dp[a][b][c] = 0;
                int oth;
                if(a) //mic
                {
                    oth = dp[a-1][b][c] + mic[a];
                    dp[a][b][c] = max(dp[a][b][c], -oth);
                }
                if(b) //lant
                {
                    oth = max(dp[a][b-1][c] + lant[b], - dp[a][b-1][c] + lant[b] - 4);
                    dp[a][b][c] = max(dp[a][b][c], -oth);
                }
                if(c) //ciclu
                {
                    oth = max(dp[a][b][c-1] + ciclu[c], - dp[a][b][c-1] + ciclu[c] - 8);
                    dp[a][b][c] = max(dp[a][b][c], -oth);
                }
            }
    cout<<dp[A][B][C];
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20