oj.uz

Submission #777650

# Submission time Handle Problem Language Result Execution time Memory
777650 2023-07-09T12:12:45 Z serkanrashid Nafta (COI15_nafta) C++14
34 / 100
 1000 ms 67660 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;
const int maxm = 1005;

int n,m;
int a[maxn][maxn],used[maxn][maxn];
bool vis[maxm*maxm];
long long mat[maxn][maxn],sum[maxm*maxm];
Point dir[4] = {{1,0},{-1,0},{0,1},{0,-1}};
vector<long long>dp_bef,dp_cur;
long long ans;
long long oldans;
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;
    oldans = ans;
    for(int j=2;j<=m;j++)
    {
        divide(1,m,1,m);
        dp_bef = dp_cur;
        cout << ans << endl;
        if(oldans==ans)
        {
            for(int k=j+1;k<=m;k++) cout << ans << endl;
            break;
        }
        oldans = ans;
    }
}

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 11 ms 32212 KB Output is correct
2 Correct 12 ms 32212 KB Output is correct
3 Correct 12 ms 32244 KB Output is correct
4 Correct 11 ms 32020 KB Output is correct
5 Correct 11 ms 32084 KB Output is correct
6 Correct 11 ms 32084 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32212 KB Output is correct
2 Correct 12 ms 32212 KB Output is correct
3 Correct 12 ms 32244 KB Output is correct
4 Correct 11 ms 32020 KB Output is correct
5 Correct 11 ms 32084 KB Output is correct
6 Correct 11 ms 32084 KB Output is correct
7 Correct 42 ms 35036 KB Output is correct
8 Correct 63 ms 34992 KB Output is correct
9 Correct 48 ms 35804 KB Output is correct
10 Correct 47 ms 34140 KB Output is correct
11 Correct 38 ms 34132 KB Output is correct
12 Correct 21 ms 34184 KB Output is correct

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32212 KB Output is correct
2 Correct 12 ms 32212 KB Output is correct
3 Correct 12 ms 32244 KB Output is correct
4 Correct 11 ms 32020 KB Output is correct
5 Correct 11 ms 32084 KB Output is correct
6 Correct 11 ms 32084 KB Output is correct
7 Correct 42 ms 35036 KB Output is correct
8 Correct 63 ms 34992 KB Output is correct
9 Correct 48 ms 35804 KB Output is correct
10 Correct 47 ms 34140 KB Output is correct
11 Correct 38 ms 34132 KB Output is correct
12 Correct 21 ms 34184 KB Output is correct
13 Execution timed out 1068 ms 67660 KB Time limit exceeded
14 Halted 0 ms 0 KB -