oj.uz

Submission #496231

# Submission time Handle Problem Language Result Execution time Memory
496231 2021-12-21T03:31:53 Z CaoHuuKhuongDuy Nafta (COI15_nafta) C++14
100 / 100
 351 ms 66392 KB 
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e3+9;
typedef pair <int,int> ii;
char a[N][N];
bool check[N][N];
int n,m,cost[N][N],f[N][N],dem;
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool inside(int x,int y)
{
    return (x>=1&&x<=n&&y>=1&&y<=m);
}
void bfs(int x,int y,int &maxx)
{
    maxx=0;
    int xnew,ynew;
    queue <ii> q;
    q.push({x,y});
    check[x][y]=true;
    while (!q.empty())
      {
        x=q.front().first;
        y=q.front().second;
        dem+=a[x][y]-'0';
        maxx=max(maxx,y);
       // cout<<x<<" "<<y<<" "<<a[x][y]<<endl;
        q.pop();
        for (int i=0;i<=3;i++)
          {
            xnew=x+dx[i];
            ynew=y+dy[i];
            if (check[xnew][ynew]||!inside(xnew,ynew)) continue;
            check[xnew][ynew]=true;
            q.push({xnew,ynew});
          }
      }
}
void dp(int k,int lfind,int rfind,int l,int r)
{
    if (l>r) return;
    int mid=(l+r)/2;
    int lim=min(mid-1,rfind),pos;
    for (int i=lfind;i<=lim;i++)
      {
        int tmp=f[k-1][i]+cost[i+1][mid];;
        if (f[k][mid]<tmp)
          {
            f[k][mid]=tmp;
            pos=i;
          }
      }
    //  cout<<pos<<endl;
     // cout<<f[1][1]<<" "<<k<<" "<<mid<<endl;
    dp(k,lfind,pos,l,mid-1);
    dp(k,pos,rfind,mid+1,r);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.inp","r",stdin);
    cin>>n>>m;
    for (int i=1;i<=n;i++)
      for (int j=1;j<=m;j++)
        {
          cin>>a[i][j];
          if (a[i][j]=='.') check[i][j]=true;
        }
    for (int j=1;j<=m;j++)
      {
        for (int i=1;i<=n;i++)
          if (!check[i][j]) 
            {
              dem=0;
              int maxx;
              bfs(i,j,maxx);
              cost[j][j]+=dem;
              cost[j][maxx+1]-=dem;
            }
      }
    for (int i=1;i<=m;i++)
      for (int j=i;j<=m;j++)
        cost[i][j]+=cost[i][j-1];
    memset(f,-1,sizeof(f));
    for (int i=0;i<=m;i++)
      f[0][i]=0;
    for (int i=m;i>=1;i--)
      for (int j=i;j<=m;j++)
        cost[i][j]+=cost[i+1][j];
    for (int i=1;i<=m;i++)
    {
      dp(i,0,m,1,m);
      //break;
    }
    //cout<<cost[4][5]<<endl;
    for (int i=1;i<=m;i++)
    {
      int maxx=0;
      for (int j=1;j<=m;j++)
        maxx=max(maxx,f[i][j]);
      cout<<maxx<<endl;
    }
    return 0;
}

Compilation message

nafta.cpp: In function 'void dp(long long int, long long int, long long int, long long int, long long int)':
nafta.cpp:60:7: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     dp(k,lfind,pos,l,mid-1);
      |     ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32332 KB Output is correct
2 Correct 14 ms 32332 KB Output is correct
3 Correct 13 ms 32280 KB Output is correct
4 Correct 12 ms 32332 KB Output is correct
5 Correct 13 ms 32332 KB Output is correct
6 Correct 13 ms 32320 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32332 KB Output is correct
2 Correct 14 ms 32332 KB Output is correct
3 Correct 13 ms 32280 KB Output is correct
4 Correct 12 ms 32332 KB Output is correct
5 Correct 13 ms 32332 KB Output is correct
6 Correct 13 ms 32320 KB Output is correct
7 Correct 18 ms 34688 KB Output is correct
8 Correct 20 ms 34656 KB Output is correct
9 Correct 20 ms 34620 KB Output is correct
10 Correct 17 ms 34636 KB Output is correct
11 Correct 17 ms 34704 KB Output is correct
12 Correct 19 ms 34700 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32332 KB Output is correct
2 Correct 14 ms 32332 KB Output is correct
3 Correct 13 ms 32280 KB Output is correct
4 Correct 12 ms 32332 KB Output is correct
5 Correct 13 ms 32332 KB Output is correct
6 Correct 13 ms 32320 KB Output is correct
7 Correct 18 ms 34688 KB Output is correct
8 Correct 20 ms 34656 KB Output is correct
9 Correct 20 ms 34620 KB Output is correct
10 Correct 17 ms 34636 KB Output is correct
11 Correct 17 ms 34704 KB Output is correct
12 Correct 19 ms 34700 KB Output is correct
13 Correct 351 ms 66276 KB Output is correct
14 Correct 319 ms 66372 KB Output is correct
15 Correct 347 ms 66392 KB Output is correct
16 Correct 284 ms 66364 KB Output is correct
17 Correct 290 ms 66364 KB Output is correct
18 Correct 267 ms 66360 KB Output is correct