oj.uz

답안 #789576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789576 2023-07-21T14:08:38 Z htphong0909 Nafta (COI15_nafta) C++17
100 / 100
 721 ms 203600 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 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

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 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 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 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 11 ms 10324 KB Output is correct
8 Correct 13 ms 10232 KB Output is correct
9 Correct 11 ms 9416 KB Output is correct
10 Correct 10 ms 9472 KB Output is correct
11 Correct 10 ms 9556 KB Output is correct
12 Correct 10 ms 9556 KB Output is correct

Subtask #3
66.0 / 66.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 11 ms 10324 KB Output is correct
8 Correct 13 ms 10232 KB Output is correct
9 Correct 11 ms 9416 KB Output is correct
10 Correct 10 ms 9472 KB Output is correct
11 Correct 10 ms 9556 KB Output is correct
12 Correct 10 ms 9556 KB Output is correct
13 Correct 612 ms 203600 KB Output is correct
14 Correct 721 ms 197696 KB Output is correct
15 Correct 620 ms 163288 KB Output is correct
16 Correct 587 ms 198488 KB Output is correct
17 Correct 594 ms 198252 KB Output is correct
18 Correct 572 ms 199052 KB Output is correct