oj.uz

답안 #789565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789565 2023-07-21T13:57:31 Z htphong0909 Nafta (COI15_nafta) C++17
100 / 100
 742 ms 238932 KB 
#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];
int ans[2001];

int cost(int j, int i, int k)
{
    //if (i == 3) cerr << DP[mid][k - 1] << " " << getV[i] << " " << posDP[mid][k - 1] << endl;
    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;
                        }
                    }
                }
                //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];
        }
    }
    for (int i = 1; i <= m2; i++)
    {
        DC(0, m2, 0, m2, i);
    }
    for (int i = 1; i <= m; i++)
    {
        int t = min(m2, i);
        cout << ans[t] << endl;
    }
    return 0;
}
/*
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠿⢿⣿⣿⠿⠛⠿⣿⣿⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠟⠉⠄⣀⡤⢤⣤⣈⠁⣠⡔⠶⣾⣿⣿⣿
⣿⣿⣿⣿⣿⣿⣿⡿⠛⠋⠁⠄⠄⠄⣼⣿⠁⡀⢹⣿⣷⢹⡇⠄⠎⣿⣿⣿
⣿⣿⣿⠿⠛⠉⠁⠄⠄⠄⠄⠄⠄⠄⠹⣇⣀⣡⣾⣿⡿⠉⠛⠒⠒⠋⠉⢸
⡿⠋⠁⠄⠄⢀⣤⣤⡀⠄⠄⠄⠄⠄⠄⠈⠙⠛⠛⠉⠄⠄⠄⠄⠄⠄⠄⠈
⠄⠄⠄⠄⠄⢹⣧⡈⠿⣷⣄⣀⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⢀⣠⢄⣾
⠄⠄⠄⠄⠄⠈⠻⢿⣶⣌⣙⡛⠛⠿⠶⠶⠶⠶⠶⠖⣒⣒⣚⣋⡩⢱⣾⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠈⠉⠛⠛⠛⠻⠿⠿⠟⠛⠛⠛⠉⢉⣥⣶⣾⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠒⠶⣿⣿⣿⣿⣿⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿
⣿⡿⠛⠛⠛⢻⣿⠿⠛⠛⠛⢿⣿⣿⡿⠛⠛⠛⢻⡟⠛⣿⡿⠛⣻⣿⣿⣿
⡟⠄⣼⣿⣿⣿⡇⠄⣾⣿⣧⠄⢻⡏⠄⣼⣿⣿⣿⡇⠄⡟⢀⣴⣿⣿⣿⣿
⡇⠄⣿⣿⣿⣿⡄⠄⣿⣿⣿⠄⢸⡇⠄⣿⣿⣿⣿⡇⠄⣀⠈⢻⣿⣿⣿⣿
⣿⣄⠈⠙⠛⢻⣧⡄⠙⠛⠉⣠⣿⣷⣄⠈⠙⠛⢹⡇⠄⣿⣧⠄⠻⣿⣿⣿

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

Compilation message

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.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 12 ms 12244 KB Output is correct
8 Correct 13 ms 12100 KB Output is correct
9 Correct 12 ms 11324 KB Output is correct
10 Correct 11 ms 11476 KB Output is correct
11 Correct 14 ms 11220 KB Output is correct
12 Correct 10 ms 10196 KB Output is correct

Subtask #3
66.0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1620 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 12 ms 12244 KB Output is correct
8 Correct 13 ms 12100 KB Output is correct
9 Correct 12 ms 11324 KB Output is correct
10 Correct 11 ms 11476 KB Output is correct
11 Correct 14 ms 11220 KB Output is correct
12 Correct 10 ms 10196 KB Output is correct
13 Correct 621 ms 238932 KB Output is correct
14 Correct 742 ms 232908 KB Output is correct
15 Correct 641 ms 198472 KB Output is correct
16 Correct 588 ms 233752 KB Output is correct
17 Correct 520 ms 227148 KB Output is correct
18 Correct 477 ms 217760 KB Output is correct