Submission #789110

#	Time	Username	Problem	Language	Result	Execution time	Memory
789110		htphong0909	Nafta (COI15_nafta)	C++17	0 / 100	2 ms	1756 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 get2Pos[2002][2002];
int DP[2001][2001];
int W[2001][2001];
int posDP[2001][2001];
vector <int> prog[2001];

int cost(int i, int mid, int k)
{
    //if (i == 3) cerr << DP[mid][k - 1] << " " << getV[i] << " " << posDP[mid][k - 1] << endl;
    return (getV[i] + DP[mid][k - 1] - W[i][posDP[mid][k - 1]]);
}

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;
                        }
                    }
                }
                //cerr << " id " << cnt << " " << L << " " << R << " " << value[cnt] << endl;
                for (int k = L; k <= R; k++)
                {
                    get2Pos[k][L] += value[cnt];
                    get2Pos[k][R + 1] -= value[cnt];
                    //cerr << k << " " << L << " " << R + 1 << endl;
                }
                cnt++;
            }
        }
    }
    //cerr << cnt << endl;
    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]);
            }
        }
    }
    vector <int> cur;
    cur.push_back(0);
    for (int i = 1; i <= m; i++)
    {
        if (cur.empty() || sGet[i] != sGet[cur.back()])
        {
            cur.push_back(i);
            for (const int& x : sGet[i]) getV[(int)cur.size() - 1] += value[x];
        }
    }
    int m2 = (int)cur.size() - 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            get2Pos[i][j] += get2Pos[i][j - 1];
        }
    }
    for (int i = 1; i <= m2; i++)
    {
        for (int j = 1; j <= m2; j++)
        {
            int posI = cur[i];
            int posJ = cur[j];
            W[i][j] = get2Pos[posI][posJ];
        }
    }
    prog[0].push_back(0);
    for (int i = 1; i <= m2; i++)
    {
        for (int k = 1; k <= m2; k++)
        {
            int l = 0;
            int r = (int)prog[k - 1].size() - 1;
            DP[i][k] = DP[i - 1][k];
            posDP[i][k] = posDP[i - 1][k];
            int maxx = -1e18;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                int vL = -1e18;
                int vR = -1e18;
                if (mid != 0) vL = cost(i, prog[k - 1][mid - 1], k);
                if (mid != (int)prog[k - 1].size() - 1) vR = cost(i, prog[k - 1][mid + 1], k);
                maxx = max(maxx, cost(i, prog[k - 1][mid], k));
                //if (i == 9 && k == 3) cerr << prog[k - 1][mid] << " " << prog[k - 1][mid - 1] << " " << prog[k - 1][mid + 1] << endl;
                if (vL > vR) r = mid - 1;
                else l = mid + 1;
            }
            if (maxx > DP[i][k])
            {
                prog[k].push_back(i);
                //if (i == 4 && k == 2) cerr << DP[i][k] << " " << maxx << endl;
                DP[i][k] = maxx;
                posDP[i][k] = i;
            }
        }
    }
    //for (int a : cur) cerr << a << endl;
    //cerr << cost(2, 1, 2);
    //cerr << DP[3][2] << " " << DP[4][2] << " " << DP[5][2] << endl;
    for (int i = 1; i <= m; i++)
    {
        int k = min(i, m2);
        cout << DP[m2][k] << 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: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 66