Submission #559803

#	Time	Username	Problem	Language	Result	Execution time	Memory
559803		stefantaga	Nafta (COI15_nafta)	C++14	0 / 100	1 ms	1108 KiB

nafta

#include <bits/stdc++.h>

using namespace std;
int r,s,i,j,v[2005][2005];
int dl[]={1,0,0,-1};
int dc[]={0,-1,1,0};
bool interior (int x,int y)
{
    if (1<=x&&x<=r&&1<=y&&y<=s)
    {
        return 1;
    }
    return 0;
}
int viz[2005][2005],sum,minj,maxj;
void fill1(int x,int y)
{
    if (interior(x,y)==0)
    {
        return;
    }
    if (v[x][y]!=-1&&viz[x][y]==0)
    {
        viz[x][y]=1;
        sum=sum+v[x][y];
        minj=min(minj,y);
        maxj=max(maxj,y);
        for (int i=0;i<4;i++)
        {
            fill1(x+dl[i],y+dc[i]);
        }
    }
}
struct interval
{
    int st,dr;
    int sum;
};
vector <interval> inter;
int w[2005][2005],n,din[2005][2005];
void divide(int st,int dr,int opt_st,int opt_dr,int k)
{
    if (st>dr)
    {
        return;
    }
    int mij = (st+dr)/2,opt=0,j;
    for (j=1;j<=mij;j++)
    {
        if (din[mij][k]<=din[j][k-1]+w[mij][j])
        {
            din[mij][k]=din[j][k-1]+w[mij][j];
            opt=j;
        }
    }
    divide(st,mij-1,opt_st,opt,k);
    divide(mij+1,dr,opt,opt_dr,k);
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>r>>s;
    for (i=1;i<=r;i++)
    {
        for (j=1;j<=s;j++)
        {
            char ch;
            cin>>ch;
            if (ch=='.')
            {
                v[i][j]=-1;
            }
            else
            {
                v[i][j]=ch-'0';
            }
        }
    }
    for (i=1;i<=r;i++)
    {
        for (j=1;j<=s;j++)
        {
            if (v[i][j]!=-1&&viz[i][j]==0)
            {
                minj=j;
                maxj=j;
                sum=0;
                fill1(i,j);
                inter.push_back(interval{minj,maxj,sum});
            }
        }
    }
    for (j=0;j<inter.size();j++)
    {
        int st = inter[j].st;
        int dr = inter[j].dr;
        int cost = inter[j].sum;
        din[st][1]+=cost;
        din[dr+1][1]-=cost;
        w[dr][0]+=cost;
        w[dr][st]-=cost;
    }
    n=s;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            w[i][j]=w[i][j]+w[i][j-1];
        }
    }
    for (i=1;i<=n;i++)
    {
        din[i][1]=din[i][1]+din[i-1][1];
    }
    for (j=2;j<=n;j++)
    {
        divide(1,n,1,n,j);
    }
    for (i=1;i<=n;i++)
    {
        int maxim=0;
        for (j=1;j<=n;j++)
        {
            maxim=max(maxim,din[j][i]);
        }
        cout<<maxim<<'\n';
    }
    return 0;
}

Compilation message (stderr)

nafta.cpp: In function 'int main()':
nafta.cpp:98:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<interval>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (j=0;j<inter.size();j++)
      |              ~^~~~~~~~~~~~~

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