oj.uz

Submission #981748

# Submission time Handle Problem Language Result Execution time Memory
981748 2024-05-13T14:03:02 Z 12345678 Nafta (COI15_nafta) C++17
34 / 100
 1000 ms 106904 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;

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++)
    {
        for (int j=1; j<=m; j++)
        {
            for (int k=0; k<i; k++)
            {
                dp[i][j]=max(dp[i][j], dp[k][j-1]+cnt[i][k]);
            }
            ans[j]=max(ans[j], 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 13404 KB Output is correct
3 Correct 2 ms 13404 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 2 ms 13148 KB Output is correct
6 Correct 2 ms 13012 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 13404 KB Output is correct
3 Correct 2 ms 13404 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 2 ms 13148 KB Output is correct
6 Correct 2 ms 13012 KB Output is correct
7 Correct 23 ms 27040 KB Output is correct
8 Correct 28 ms 27216 KB Output is correct
9 Correct 24 ms 27380 KB Output is correct
10 Correct 21 ms 25944 KB Output is correct
11 Correct 21 ms 25948 KB Output is correct
12 Correct 21 ms 25940 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13404 KB Output is correct
2 Correct 2 ms 13404 KB Output is correct
3 Correct 2 ms 13404 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 2 ms 13148 KB Output is correct
6 Correct 2 ms 13012 KB Output is correct
7 Correct 23 ms 27040 KB Output is correct
8 Correct 28 ms 27216 KB Output is correct
9 Correct 24 ms 27380 KB Output is correct
10 Correct 21 ms 25944 KB Output is correct
11 Correct 21 ms 25948 KB Output is correct
12 Correct 21 ms 25940 KB Output is correct
13 Execution timed out 1033 ms 106904 KB Time limit exceeded
14 Halted 0 ms 0 KB -