oj.uz

Submission #992534

# Submission time Handle Problem Language Result Execution time Memory
992534 2024-06-04T15:18:38 Z Khanhcsp2 Nafta (COI15_nafta) C++14
100 / 100
 243 ms 163664 KB 
#include<bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=2e3+11;
int hx[]={0, 0, -1, 1};
int hy[]={-1, 1, 0, 0};
int m, n;
char a[N][N];
int v[N][N], vit[N][N], l[N], r[N], val[N], mi=N, sum, ma, s[N][N];
vector<int> dp1, dp2;
bool valid(int x, int y)
{
    if(x<1 || x>m || y<1 || y>n || vit[x][y]) return 0;
    return 1;
}
void dfs(int i, int j)
{
    if(vit[i][j]) return;
    vit[i][j]=1;
    sum+=v[i][j];
    mi=min(mi, j);
    ma=max(ma, j);
    for(int q=0;q<=3;q++)
    {
        int x=i+hx[q], y=j+hy[q];
        if(valid(x, y))
        {
             dfs(x, y);
        }
    }
}
int calc(int l, int r)
{
    return s[l][r];
}
void dnc(int l, int r, int lll, int rrr)
{
    if(l>r) return;
    int mid=(l+r)/2;
    pii s= {0, -1};
    for(int i=lll; i<=min(mid, rrr); i++) s = max(s, {dp1[i]+calc(i+1, mid),i});
    dp2[mid]=s.fi;
    int opt=s.sc;
    dnc(l, mid-1, lll, opt);
    dnc(mid+1, r, opt, rrr);
}
void sol()
{
    cin >> m >> n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin >> a[i][j];
            if(a[i][j]=='.') vit[i][j]=1;
            else v[i][j]=a[i][j]-'0';
        }
    }
    dp1.resize(n+11, 0);
    dp2.resize(n+11, 0);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vit[i][j]) continue;
            ma=0, mi=N, sum=0;
            dfs(i, j);
            for(int _=mi;_<=ma;_++)
            {
                dp1[_]+=sum;
                s[1][_]+=sum;
                s[mi+1][_]-=sum;
            }
        }
    }
    for(int i=0;i<=n;i++) for(int j=1;j<=n;j++) s[j][i]+=s[j-1][i];
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans, dp1[i]);
    cout << ans << el;
    for(int i=2; i<=n; i++)
    {
        dnc(i, n, i-1, n-1);
        int ans=0;
        for(int j=1; j<=n; j++) dp1[j]=dp2[j], dp2[j]=0, ans=max(ans, dp1[j]);
        cout << ans << el;
    }
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10704 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10704 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct
8 Correct 6 ms 23184 KB Output is correct
9 Correct 6 ms 24412 KB Output is correct
10 Correct 4 ms 23100 KB Output is correct
11 Correct 5 ms 23212 KB Output is correct
12 Correct 5 ms 23132 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct
6 Correct 1 ms 10704 KB Output is correct
7 Correct 5 ms 23132 KB Output is correct
8 Correct 6 ms 23184 KB Output is correct
9 Correct 6 ms 24412 KB Output is correct
10 Correct 4 ms 23100 KB Output is correct
11 Correct 5 ms 23212 KB Output is correct
12 Correct 5 ms 23132 KB Output is correct
13 Correct 155 ms 103248 KB Output is correct
14 Correct 208 ms 103252 KB Output is correct
15 Correct 243 ms 163664 KB Output is correct
16 Correct 114 ms 103144 KB Output is correct
17 Correct 91 ms 103252 KB Output is correct
18 Correct 96 ms 103252 KB Output is correct