oj.uz

Submission #1093184

# Submission time Handle Problem Language Result Execution time Memory
1093184 2024-09-26T07:35:30 Z _callmelucian Nafta (COI15_nafta) C++14
100 / 100
 305 ms 177496 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 4e6 + 6;
int cost[2020][2020], grp[2020][2020], dp[2][2020], L[mn], sum[mn];
bool vis[2020][2020];
char ch[2020][2020];
int n, m;

const int dr[4] = {-1, 0, 0, 1};
const int dc[4] = {0, -1, 1, 0};

bool ok (int i, int j) {
    if (i < 1 || j < 1) return 0;
    if (i > n || j > m) return 0;
    return 1;
}

void dfs (int i, int j, int gr) {
    L[gr] = min(L[gr], j), sum[gr] += ch[i][j] - '0';
    grp[i][j] = gr, vis[i][j] = 1;
    for (int k = 0; k < 4; k++) {
        int i2 = i + dr[k], j2 = j + dc[k];
        if (ok(i2, j2) && ch[i2][j2] != '.' && !vis[i2][j2]) dfs(i2, j2, gr);
    }
}

void solve (int t, int a, int b, int optL, int optR) {
    int cur = (a + b) >> 1, opt = 0;
    for (int re = optL; re <= min(cur - 1, optR); re++) {
        if (dp[t ^ 1][re] == INT_MIN) continue;
        int cand = dp[t ^ 1][re] + cost[cur][re];
        if (cand > dp[t][cur])
            dp[t][cur] = cand, opt = re;
    }

    if (a < cur) solve(t, a, cur - 1, optL, opt);
    if (cur < b) solve(t, cur + 1, b, opt, optR);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> ch[i][j];

    for (int i = 1; i <= n * m; i++) L[i] = INT_MAX;

    int counter = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!vis[i][j] && ch[i][j] != '.') dfs(i, j, ++counter);

    for (int j = 1; j <= m; j++) {
        vector<int> cand;
        for (int i = 1; i <= n; i++)
            if (grp[i][j]) cand.push_back(grp[i][j]);
        sort(all(cand)); filter(cand);
        sort(all(cand), [&] (int a, int b) { return L[a] < L[b]; });

        int curSum = 0;
        for (int k = j - 1; k >= 0; k--) {
            while (cand.size() && k < L[cand.back()]) {
                curSum += sum[cand.back()];
                cand.pop_back();
            }
            cost[j][k] = curSum;
        }
    }

    for (int i = 1; i <= m; i++) dp[0][i] = INT_MIN;

    for (int ttimes = 1; ttimes <= m; ttimes++) {
        int t = ttimes & 1;
        for (int i = 0; i <= m; i++) dp[t][i] = INT_MIN;
        solve(t, 1, m, 0, m - 1);

        cout << *max_element(dp[t] + 1, dp[t] + 1 + m) << "\n";
    }

    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 868 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 868 KB Output is correct
7 Correct 5 ms 4956 KB Output is correct
8 Correct 7 ms 4856 KB Output is correct
9 Correct 8 ms 7772 KB Output is correct
10 Correct 5 ms 4192 KB Output is correct
11 Correct 5 ms 4320 KB Output is correct
12 Correct 5 ms 4188 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 868 KB Output is correct
7 Correct 5 ms 4956 KB Output is correct
8 Correct 7 ms 4856 KB Output is correct
9 Correct 8 ms 7772 KB Output is correct
10 Correct 5 ms 4192 KB Output is correct
11 Correct 5 ms 4320 KB Output is correct
12 Correct 5 ms 4188 KB Output is correct
13 Correct 198 ms 59608 KB Output is correct
14 Correct 251 ms 58716 KB Output is correct
15 Correct 305 ms 177496 KB Output is correct
16 Correct 183 ms 54520 KB Output is correct
17 Correct 178 ms 53592 KB Output is correct
18 Correct 170 ms 53592 KB Output is correct