제출 #1184178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184178		Jovica	Nafta (COI15_nafta)	C++20	100 / 100	294 ms	23956 KiB

nafta

#include <bits/stdc++.h>

using namespace std;
int const maxn = 2001;
char pocetno[maxn][maxn];
bool visited[maxn][maxn];
int levo,desno;
int mat[maxn][maxn],n,m;

void bfs(int pocx,int pocy)
{
    //cout<<"ulava na "<<pocx<<" "<<pocy<<endl;
    queue<array<int,2> > q;q.push({pocx,pocy});
    visited[pocx][pocy] = true;
    int z = 0;levo = m;desno = -1;
    while (q.size())
    {
        int x = q.front()[0],y = q.front()[1];
        q.pop();

        //cout<<"mine "<<x<<" "<<y<<endl;
        visited[x][y] = true;
        z += pocetno[x][y] - '0';
        levo = min(levo,y);desno = max(desno,y);

        if (x>0 && visited[x-1][y] == false && pocetno[x-1][y] != '.'){
            visited[x-1][y] = true;
            q.push({x-1,y});
        }
        if (x+1<n && visited[x+1][y] == false && pocetno[x+1][y] != '.'){
            visited[x+1][y] = true;
            q.push({x+1,y});
        }
        if (y>0 && visited[x][y-1] == false && pocetno[x][y-1] != '.'){
            visited[x][y-1] = true;
            q.push({x,y-1});
        }
        if (y+1<m && visited[x][y+1] == false && pocetno[x][y+1] != '.'){
            visited[x][y+1] = true;
            q.push({x,y+1});
        }
    }


    for (int i=levo;i<=desno;i++)
        for (int j=levo;j<=desno;j++) mat[i][j] += z;
}

int dp[maxn][2];

void dnc(int l,int r,int optl,int optr)
{
    if (l>r) return;
    int mid = (l+r)/2;

    int ans = mat[mid][mid],p=mid;
    //cout<<"mid = "<<mid<<" optl = "<<optl<<" optr = "<<optr<<endl;
    for (int i=optl;i<=min(optr,mid);i++){
        int x = mat[mid][mid] + dp[i][0] - mat[mid][i];
        if (x>ans)
        {
            ans = x;
            p = i;
        }
    }

    dp[mid][1] = ans;
    dnc(l,mid-1,optl,p);
    dnc(mid+1,r,p,optr);
}

int main()
{
    cin>>n>>m;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++) cin>>pocetno[i][j];

    for (int j=0;j<m;j++)
        for (int i=0;i<n;i++)
            if (visited[i][j] == false && pocetno[i][j] != '.') bfs(i,j);

    /*
    for (int i=0;i<m;i++)
    {
        for (int j=0;j<m;j++) cout<<mat[i][j]<<" ";
        cout<<endl;
    }*/

    int ans = -1;
    //for (int i=0;i<m;i++) dp[i] = mat[i][i],ans = max(ans,mat[i][i]);

    //cout<<ans<<"\n";
    for (int i=0;i<m;i++)
    {
        dnc(0,m-1,0,m-1);
        for (int j=0;j<m;j++) dp[j][0] = dp[j][1];
        ans = -1;
        for (int j=0;j<m;j++) ans = max(ans,dp[j][0]);
        cout<<ans<<"\n";
    }

    return 0;
}
/*

5 7
111....
.......
..111..
.......
9...111


k = 2 odg = 18
*/

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 66 / 66