Submission #789576

#	Time	Username	Problem	Language	Result	Execution time	Memory
789576		htphong0909	Nafta (COI15_nafta)	C++17	100 / 100	721 ms	203600 KiB

nafta

#include<bits/stdc++.h>
using namespace std;
#define int long long

void File() {
#define file "test"
    freopen(file".in", "r", stdin);
    freopen(file".out", "w", stdout);
}

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

bool visited[2001][2001];
int par[2001][2001];
int value[4000001];
int getV[2001];
set<int> sGet[2001];
int W[2002][2002];
int DP[2001][2001];
int posDP[2001][2001];
int ans[2001];

int cost(int j, int i, int k)
{
    return (DP[j][k - 1] + getV[i] - W[j][i]);
}

void DC(int l, int r, int gL, int gR, int k)
{
    if (l > r) return;
    int mid = (l + r) / 2;
    posDP[mid][k] = mid;
    DP[mid][k] = cost(mid, mid, k);
    for (int i = gL; i <= gR; i++)
    {
        if (i <= mid && cost(i, mid, k) > DP[mid][k])
        {
            DP[mid][k] = cost(i, mid, k);
            posDP[mid][k] = i;
        }
    }
    int minL = posDP[mid][k];
    int maxR = posDP[mid][k];
    for (int i = gL; i <= gR; i++)
    {
        if (i <= mid && cost(i, mid, k) == DP[mid][k])
        {
            minL = min(minL, i);
            maxR = min(maxR, i);
        }
    }
    ans[k] = max(ans[k], DP[mid][k]);
    DC(l, mid - 1, gL, maxR, k);
    DC(mid + 1, r, minL, gR, k);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //File();
    int n, m;
    cin >> n >> m;
    vector <vector<int>> arr(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char in;
            cin >> in;
            if (in == '.') arr[i][j] = -1;
            else arr[i][j] = in - '0';
        }
    }
    int cnt = 0;
    queue<pair<int, int>> q;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (!visited[i][j] && arr[i][j] != -1)
            {
                visited[i][j] = true;
                q.emplace(i, j);
                int L = 1e18, R = -1e18;
                while (!q.empty())
                {
                    int ux, uy;
                    tie(ux, uy) = q.front();
                    q.pop();
                    value[cnt] += arr[ux][uy];
                    par[ux][uy] = cnt;
                    L = min(L, uy);
                    R = max(R, uy);
                    for (int k = 0; k < 4; k++)
                    {
                        int vx = ux + dx[k];
                        int vy = uy + dy[k];
                        if (min(vx, vy) >= 1 && vx <= n && vy <= m && !visited[vx][vy] && arr[vx][vy] != -1)
                        {
                            q.emplace(vx, vy);
                            visited[vx][vy] = true;
                        }
                    }
                }
                for (int k = L; k <= R; k++)
                {
                    W[k][L] += value[cnt];
                    W[k][R + 1] -= value[cnt];
                }
                cnt++;
            }
        }
    }
    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++) if (arr[i][j] != -1) sGet[j].insert(par[i][j]);
    }
    for (int i = 1; i <= m; i++)
    {
        for (const int& x : sGet[i]) getV[i] += value[x];
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m; j++) W[i][j] += W[i][j - 1];
    }
    for (int i = 1; i <= m; i++) DC(0, m, 0, m, i);
    for (int i = 1; i <= m; i++) cout << ans[i] << endl;
    return 0;
}
/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⢿⣿⣿⠿⠛⠿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠉⠄⣀⡤⢤⣤⣈⠁⣠⡔⠶⣾⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⠛⠋⠁⠄⠄⠄⣼⣿⠁⡀⢹⣿⣷⢹⡇⠄⠎⣿⣿⣿
⣿⣿⣿⠿⠛⠉⠁⠄⠄⠄⠄⠄⠄⠄⠹⣇⣀⣡⣾⣿⡿⠉⠛⠒⠒⠋⠉⢸
⡿⠋⠁⠄⠄⢀⣤⣤⡀⠄⠄⠄⠄⠄⠄⠈⠙⠛⠛⠉⠄⠄⠄⠄⠄⠄⠄⠈
⠄⠄⠄⠄⠄⢹⣧⡈⠿⣷⣄⣀⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣠⢄⣾
⠄⠄⠄⠄⠄⠈⠻⢿⣶⣌⣙⡛⠛⠿⠶⠶⠶⠶⠶⠖⣒⣒⣚⣋⡩⢱⣾⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠈⠉⠛⠛⠛⠻⠿⠿⠟⠛⠛⠛⠉⢉⣥⣶⣾⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠒⠶⣿⣿⣿⣿⣿⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿
⣿⡿⠛⠛⠛⢻⣿⠿⠛⠛⠛⢿⣿⣿⡿⠛⠛⠛⢻⡟⠛⣿⡿⠛⣻⣿⣿⣿
⡟⠄⣼⣿⣿⣿⡇⠄⣾⣿⣧⠄⢻⡏⠄⣼⣿⣿⣿⡇⠄⡟⢀⣴⣿⣿⣿⣿
⡇⠄⣿⣿⣿⣿⡄⠄⣿⣿⣿⠄⢸⡇⠄⣿⣿⣿⣿⡇⠄⣀⠈⢻⣿⣿⣿⣿
⣿⣄⠈⠙⠛⢻⣧⡄⠙⠛⠉⣠⣿⣷⣄⠈⠙⠛⢹⡇⠄⣿⣧⠄⠻⣿⣿⣿

 ___  ___  _________        ________  ___  ___  ________  ________   ________          ________  ________  ________  ________
|\  \|\  \|\___   ___\     |\   __  \|\  \|\  \|\   __  \|\   ___  \|\   ____\        |\   __  \|\   ____\|\   __  \|\   __  \
\ \  \\\  \|___ \  \_|     \ \  \|\  \ \  \\\  \ \  \|\  \ \  \\ \  \ \  \___|        \ \  \|\  \ \  \___|\ \  \|\ /\ \  \|\  \
 \ \   __  \   \ \  \       \ \   ____\ \   __  \ \  \\\  \ \  \\ \  \ \  \  ___       \ \  \\\  \ \  \    \ \   __  \ \  \\\  \
  \ \  \ \  \   \ \  \       \ \  \___|\ \  \ \  \ \  \\\  \ \  \\ \  \ \  \|\  \       \ \  \\\  \ \  \____\ \  \|\  \ \  \\\  \
   \ \__\ \__\   \ \__\       \ \__\    \ \__\ \__\ \_______\ \__\\ \__\ \_______\       \ \_______\ \_______\ \_______\ \_______\
    \|__|\|__|    \|__|        \|__|     \|__|\|__|\|_______|\|__| \|__|\|_______|        \|_______|\|_______|\|_______|\|_______|
*/

Compilation message (stderr)

nafta.cpp: In function 'void File()':
nafta.cpp:7:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     freopen(file".in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
nafta.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66