oj.uz

Submission #559804

# Submission time Handle Problem Language Result Execution time Memory
559804 2022-05-10T15:43:47 Z stefantaga Nafta (COI15_nafta) C++14
100 / 100
 517 ms 138056 KB 
#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;
    din[mij][k]=-1e9;
    for (j=opt_st;j<=min(opt_dr,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 fr[2005];
vector <pair <int,int> > ev[2005];
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;
    }
    n=s;
    /// care il contin pe i dar care nu l contin pe j
    for (j=0;j<inter.size();j++)
    {
        ev[inter[j].st].push_back({inter[j].sum,j});
        ev[inter[j].dr+1].push_back({-inter[j].sum,j});
    }
    long long suma=0;
    for (i=1;i<=n;i++)
    {
        for (j=0;j<ev[i].size();j++)
        {
            int poz = ev[i][j].second;
            suma=suma+ev[i][j].first;
            fr[inter[poz].st]+=ev[i][j].first;
        }
        for (j=i;j>=1;j--)
        {
            w[i][j]=w[i][j+1]+fr[j+1];
        }
    }
    #ifdef HOME
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=i;j++)
            {
                cout<<w[i][j]<<" ";
            }
            cout<<'\n';
        }
    #endif // HOME
    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

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

Subtask #1
11.0 / 11.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 10 ms 6992 KB Output is correct
8 Correct 11 ms 6668 KB Output is correct
9 Correct 12 ms 8096 KB Output is correct
10 Correct 8 ms 5972 KB Output is correct
11 Correct 9 ms 5820 KB Output is correct
12 Correct 8 ms 5792 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 10 ms 6992 KB Output is correct
8 Correct 11 ms 6668 KB Output is correct
9 Correct 12 ms 8096 KB Output is correct
10 Correct 8 ms 5972 KB Output is correct
11 Correct 9 ms 5820 KB Output is correct
12 Correct 8 ms 5792 KB Output is correct
13 Correct 443 ms 85408 KB Output is correct
14 Correct 469 ms 76012 KB Output is correct
15 Correct 517 ms 138056 KB Output is correct
16 Correct 377 ms 70444 KB Output is correct
17 Correct 387 ms 61960 KB Output is correct
18 Correct 373 ms 61708 KB Output is correct