Submission #777649

# Submission time Handle Problem Language Result Execution time Memory
777649 2023-07-09T12:10:32 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;

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;
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;
}
# Verdict Execution time Memory Grader output
1 Correct 12 ms 32240 KB Output is correct
2 Correct 12 ms 32244 KB Output is correct
3 Correct 13 ms 32264 KB Output is correct
4 Correct 12 ms 32024 KB Output is correct
5 Correct 12 ms 32084 KB Output is correct
6 Correct 12 ms 32084 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 32240 KB Output is correct
2 Correct 12 ms 32244 KB Output is correct
3 Correct 13 ms 32264 KB Output is correct
4 Correct 12 ms 32024 KB Output is correct
5 Correct 12 ms 32084 KB Output is correct
6 Correct 12 ms 32084 KB Output is correct
7 Correct 43 ms 35028 KB Output is correct
8 Correct 74 ms 34980 KB Output is correct
9 Correct 46 ms 35808 KB Output is correct
10 Correct 42 ms 34228 KB Output is correct
11 Correct 38 ms 34112 KB Output is correct
12 Correct 24 ms 34152 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 32240 KB Output is correct
2 Correct 12 ms 32244 KB Output is correct
3 Correct 13 ms 32264 KB Output is correct
4 Correct 12 ms 32024 KB Output is correct
5 Correct 12 ms 32084 KB Output is correct
6 Correct 12 ms 32084 KB Output is correct
7 Correct 43 ms 35028 KB Output is correct
8 Correct 74 ms 34980 KB Output is correct
9 Correct 46 ms 35808 KB Output is correct
10 Correct 42 ms 34228 KB Output is correct
11 Correct 38 ms 34112 KB Output is correct
12 Correct 24 ms 34152 KB Output is correct
13 Execution timed out 1082 ms 67660 KB Time limit exceeded
14 Halted 0 ms 0 KB -