oj.uz

Submission #1034594

# Submission time Handle Problem Language Result Execution time Memory
1034594 2024-07-25T15:14:23 Z mimi Nafta (COI15_nafta) C++17
100 / 100
 427 ms 177584 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
#define dbg(v)  cout << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <ll,ll>;
using pll = pair <ll,ll>;
using pld = pair <ld,ld>;
const char el ='\n';
const char sp = ' ';
const ll maxn = 3e3+5, mod = 1e9+7, maxN = 1e6;
const ll inf = 1e18L+3;
ll n,m,id[maxn][maxn],neg[maxn][maxn],sum[maxN],total[maxn],l_[maxN], dp[maxn][maxn], ti,movx[] = {0,0,1,-1}, movy[] = {1,-1,0,0};
char c[maxn][maxn];
map<ll,bool> mark;

void DFS(ll u, ll v)
{
    id[u][v] = ti;
    l_[ti] = min(l_[ti],v);
    sum[ti]+=c[u][v]-'0';
    for(ll i=0;i<4;++i)
    {
        ll x = u+movx[i], y = v+movy[i];
        if(x>0 && x<=n && y>0 && y<=m && c[x][y]!='.' && !id[x][y])  DFS(x,y);
    }
}

void input()
{
    fill(l_,l_+maxN,inf);
    cin>>n>>m;
    for(ll i=1;i<=m;++i)   dp[m][0] = -inf;
    for(ll i=1;i<=n;++i)
        for(ll j=1;j<=m;++j)   cin>>c[i][j];
    for(ll i=1;i<=n;++i){
        for(ll j=1;j<=m;++j){
            if(!id[i][j] && c[i][j]!='.'){
                ++ti;
                DFS(i,j);
            }
        }
    }
}

void prepare()
{
    for(ll j=1;j<=m;++j)
    {
        mark.clear();
        for(ll i=1;i<=n;++i)
        {
            if(c[i][j]=='.')    continue;
            if(mark[id[i][j]])  continue;
            mark[id[i][j]] = true;
            total[j]+=sum[id[i][j]];
            neg[l_[id[i][j]]][j]+=sum[id[i][j]];
        }
        for(ll i=1;i<=m;++i)   neg[i][j]+=neg[i-1][j];
    }
}

ll cost(ll l, ll r)
{
    return total[r]-neg[l][r];
}

void cal(ll l, ll r, ll optl, ll optr, ll j)
{
    if(l>r) return;
    ll mid = (l+r)/2,best = 0;
    for(ll i=optl; i<=min(mid,optr);++i)
    {
        ll money = dp[i-1][j-1] + cost(i-1,mid);
        if(money>dp[mid][j])
        {
            dp[mid][j] = money;
            best = i;
        }
    }
    cal(l,mid-1,optl,best,j);
    cal(mid+1,r,best,optr,j);
}

void solve()
{
    for(ll i=1;i<=m;++i)
    {
        cal(1,m,1,m,i);
        ll ans = 0;
        for(ll j=1;j<=m;++j)   ans = max(ans,dp[j][i]);
        cout<<ans<<el;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll test = 1;
    while(test-->0)
    {
        input();
        prepare();
        solve();
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9052 KB Output is correct
2 Correct 5 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9052 KB Output is correct
2 Correct 5 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 10 ms 14980 KB Output is correct
8 Correct 10 ms 14940 KB Output is correct
9 Correct 10 ms 15964 KB Output is correct
10 Correct 9 ms 13916 KB Output is correct
11 Correct 9 ms 13876 KB Output is correct
12 Correct 9 ms 13916 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9052 KB Output is correct
2 Correct 5 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 8796 KB Output is correct
5 Correct 3 ms 8796 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 10 ms 14980 KB Output is correct
8 Correct 10 ms 14940 KB Output is correct
9 Correct 10 ms 15964 KB Output is correct
10 Correct 9 ms 13916 KB Output is correct
11 Correct 9 ms 13876 KB Output is correct
12 Correct 9 ms 13916 KB Output is correct
13 Correct 396 ms 136020 KB Output is correct
14 Correct 427 ms 134072 KB Output is correct
15 Correct 384 ms 177584 KB Output is correct
16 Correct 306 ms 114516 KB Output is correct
17 Correct 318 ms 112724 KB Output is correct
18 Correct 383 ms 112600 KB Output is correct