oj.uz

Submission #981754

# Submission time Handle Problem Language Result Execution time Memory
981754 2024-05-13T14:11:14 Z 12345678 Nafta (COI15_nafta) C++17
100 / 100
 416 ms 114304 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=2005;

int n, m, mp[nx][nx], dp[nx][nx], mn[nx][nx], cnt[nx][nx], g[nx][nx], t, s[nx][nx],vs[nx][nx], dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0}, ans[nx];
char ch;
queue<pair<int, int>> q;

void solve(int l, int r, int optl, int optr, int layer)
{
    if (r<l) return;
    int md=(l+r)/2;
    pair<int, int> mx={INT_MIN, -1};
    for (int i=optl; i<=min(md-1, optr); i++) mx=max(mx, {dp[layer-1][i]+cnt[md][i], i});
    dp[layer][md]=mx.first;
    solve(l, md-1, optl, mx.second, layer);
    solve(md+1, r, mx.second, optr, layer);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) cin>>ch, mp[i][j]=(ch=='.')?-1:ch-'0';
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=m; j++)
        {
            if (vs[i][j]||mp[i][j]==-1) continue;
            q.push({i, j});
            vs[i][j]=1;
            int k=INT_MAX, sm=0;
            vector<pair<int, int>> v;
            while (!q.empty())
            {
                v.push_back(q.front());
                auto [x, y]=q.front();
                q.pop();
                k=min(k, y);
                sm+=mp[x][y];
                for (int d=0; d<4; d++)
                {
                    int nwx=x+dx[d], nwy=y+dy[d];
                    if (nwx<1||nwx>n||nwy<1||nwy>m||mp[nwx][nwy]==-1||vs[nwx][nwy]) continue;
                    q.push({nwx, nwy});
                    vs[nwx][nwy]=1;
                }
            }
            ++t;
            for (auto [x, y]:v) g[x][y]=t, mn[x][y]=k, s[x][y]=sm; //cout<<"group "<<t<<' '<<x<<' '<<y<<'\n';
        }
    }
    for (int i=1; i<=m; i++)
    {
        set<int> mem;
        for (int j=1; j<=n; j++)
        {
            if (mp[j][i]==-1||mem.find(g[j][i])!=mem.end()) continue;
            mem.insert(g[j][i]);
            cnt[i][mn[j][i]-1]+=s[j][i];
        }
        for (int j=i; j>=0; j--) cnt[i][j]+=cnt[i][j+1]; //cout<<"debug "<<i<<' '<<j<<' '<<cnt[i][j]<<'\n';
    }
    for (int i=1; i<=m; i++) solve(1, m, 0, m, i);
    for (int i=1; i<=m; i++) for (int j=1; j<=m; j++) ans[i]=max(ans[i], dp[i][j]);
    for (int i=1; i<=m; i++) cout<<ans[i]<<'\n';
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13404 KB Output is correct
2 Correct 2 ms 13400 KB Output is correct
3 Correct 2 ms 13404 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 3 ms 13156 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13404 KB Output is correct
2 Correct 2 ms 13400 KB Output is correct
3 Correct 2 ms 13404 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 3 ms 13156 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 11 ms 28504 KB Output is correct
8 Correct 12 ms 28508 KB Output is correct
9 Correct 11 ms 28612 KB Output is correct
10 Correct 10 ms 27420 KB Output is correct
11 Correct 9 ms 27344 KB Output is correct
12 Correct 9 ms 27228 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13404 KB Output is correct
2 Correct 2 ms 13400 KB Output is correct
3 Correct 2 ms 13404 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 3 ms 13156 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 11 ms 28504 KB Output is correct
8 Correct 12 ms 28508 KB Output is correct
9 Correct 11 ms 28612 KB Output is correct
10 Correct 10 ms 27420 KB Output is correct
11 Correct 9 ms 27344 KB Output is correct
12 Correct 9 ms 27228 KB Output is correct
13 Correct 338 ms 110536 KB Output is correct
14 Correct 413 ms 114244 KB Output is correct
15 Correct 416 ms 114304 KB Output is correct
16 Correct 304 ms 110408 KB Output is correct
17 Correct 266 ms 110396 KB Output is correct
18 Correct 275 ms 110400 KB Output is correct