oj.uz

Submission #777648

# Submission time Handle Problem Language Result Execution time Memory
777648 2023-07-09T12:07:47 Z serkanrashid Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 71592 KB 
#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

struct Point
{
    int x,y;
    Point(){};
    Point(int xi, int yi)
    {
        x = xi;
        y = yi;
    }
    Point operator+(Point ed)
    {
        Point res;
        res.x = x + ed.x;
        res.y = y + ed.y;
        return res;
    }
};

const int maxn = 2005;

int n,m;
int a[maxn][maxn],used[maxn][maxn];
bool vis[maxn*maxn];
long long mat[maxn][maxn],sum[maxn*maxn];
Point dir[4] = {{1,0},{-1,0},{0,1},{0,-1}};
vector<long long>dp_bef,dp_cur;
long long ans;
int idx;

void read()
{
    memset(mat,-1,sizeof(mat));
    cin >> n >> m;
    char z;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin >> z;
            if(z=='.') used[i][j] = -1;
            else a[i][j] = z-'0';
        }
    }
    for(int i=0;i<=n+1;i++) used[i][0] = used[i][m+1] = -1;
    for(int j=0;j<=m+1;j++) used[0][j] = used[n+1][j] = -1;
}

void dfs(Point beg)
{
    used[beg.x][beg.y] = idx;
    sum[idx] += a[beg.x][beg.y];
    Point nb;
    for(int i=0;i<4;i++)
    {
        nb = beg + dir[i];
        if(!used[nb.x][nb.y]) dfs(nb);
    }
}

void pre()
{
    for(int j=1;j<=m;j++)
    {
        for(int i=1;i<=n;i++)
        {
            if(!used[i][j])
            {
                idx++;
                dfs({i,j});
            }
        }
    }
    dp_bef.clear();
    dp_cur.clear();
    dp_bef.resize(m+1);
    dp_cur.resize(m+1);
}

long long cost(int l, int r)
{
    if(mat[l][r]!=-1) return mat[l][r];
    long long oil = 0;
    for(int i=1;i<=n;i++)
    {
        if(used[i][l]==-1) continue;
        vis[used[i][l]] = 1;
    }
    for(int i=1;i<=n;i++)
    {
        if(used[i][r]==-1) continue;
        if(!vis[used[i][r]]) oil += sum[used[i][r]];
        vis[used[i][r]] = 1;
    }
    for(int i=1;i<=n;i++)
    {
        if(used[i][l]!=-1) vis[used[i][l]] = 0;
        if(used[i][r]!=-1) vis[used[i][r]] = 0;
    }
    mat[l][r] = oil;
    return oil;
}

void divide(int l, int r, int optl, int optr)
{
    if(l>r) return;
    int mid = (l+r)/2;
    pair<long long, int> best = {0,-1};
    for(int i=optl;i<=min(mid,optr);i++)
    {
        long long pom = dp_bef[i] + cost(i,mid);
        if(pom>best.first) best = {pom,i};
    }
    dp_cur[mid] = best.first;
    ans = max(ans,dp_cur[mid]);
    int opt = best.second;
    divide(l,mid-1,optl,opt);
    divide(mid+1,r,opt,optr);
}

void solve()
{
    pre();
    for(int i=1;i<=m;i++)
    {
        dp_bef[i] = cost(0,i);
        ans = max(ans,dp_bef[i]);
    }
    cout << ans << endl;
    for(int j=2;j<=m;j++)
    {
        divide(1,m,1,m);
        dp_bef = dp_cur;
        cout << ans << endl;
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	read();
	solve();
return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32212 KB Output is correct
2 Correct 13 ms 32132 KB Output is correct
3 Correct 15 ms 32212 KB Output is correct
4 Correct 12 ms 32060 KB Output is correct
5 Correct 15 ms 32100 KB Output is correct
6 Correct 12 ms 32084 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32212 KB Output is correct
2 Correct 13 ms 32132 KB Output is correct
3 Correct 15 ms 32212 KB Output is correct
4 Correct 12 ms 32060 KB Output is correct
5 Correct 15 ms 32100 KB Output is correct
6 Correct 12 ms 32084 KB Output is correct
7 Correct 45 ms 35128 KB Output is correct
8 Correct 65 ms 35072 KB Output is correct
9 Correct 46 ms 35884 KB Output is correct
10 Correct 44 ms 34260 KB Output is correct
11 Correct 41 ms 34252 KB Output is correct
12 Correct 25 ms 34244 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 32212 KB Output is correct
2 Correct 13 ms 32132 KB Output is correct
3 Correct 15 ms 32212 KB Output is correct
4 Correct 12 ms 32060 KB Output is correct
5 Correct 15 ms 32100 KB Output is correct
6 Correct 12 ms 32084 KB Output is correct
7 Correct 45 ms 35128 KB Output is correct
8 Correct 65 ms 35072 KB Output is correct
9 Correct 46 ms 35884 KB Output is correct
10 Correct 44 ms 34260 KB Output is correct
11 Correct 41 ms 34252 KB Output is correct
12 Correct 25 ms 34244 KB Output is correct
13 Execution timed out 1067 ms 71592 KB Time limit exceeded
14 Halted 0 ms 0 KB -