oj.uz

Submission #1034590

# Submission time Handle Problem Language Result Execution time Memory
1034590 2024-07-25T15:12:46 Z mimi Nafta (COI15_nafta) C++17
100 / 100
 391 ms 181476 KB 
#include <bits/stdc++.h>
#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 4 ms 9048 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 4 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 4 ms 9048 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 4 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 14936 KB Output is correct
8 Correct 10 ms 14988 KB Output is correct
9 Correct 10 ms 15964 KB Output is correct
10 Correct 9 ms 14132 KB Output is correct
11 Correct 9 ms 13912 KB Output is correct
12 Correct 9 ms 14008 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9048 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 4 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 14936 KB Output is correct
8 Correct 10 ms 14988 KB Output is correct
9 Correct 10 ms 15964 KB Output is correct
10 Correct 9 ms 14132 KB Output is correct
11 Correct 9 ms 13912 KB Output is correct
12 Correct 9 ms 14008 KB Output is correct
13 Correct 357 ms 139988 KB Output is correct
14 Correct 391 ms 138028 KB Output is correct
15 Correct 370 ms 181476 KB Output is correct
16 Correct 311 ms 118492 KB Output is correct
17 Correct 331 ms 116444 KB Output is correct
18 Correct 338 ms 116560 KB Output is correct