oj.uz

Submission #496271

# Submission time Handle Problem Language Result Execution time Memory
496271 2021-12-21T04:29:44 Z CaoHuuKhuongDuy Nafta (COI15_nafta) C++14
100 / 100
 382 ms 62568 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);
        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,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;
          }
      }
    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);
    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:57:7: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |     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 32248 KB Output is correct
3 Correct 13 ms 32344 KB Output is correct
4 Correct 13 ms 32332 KB Output is correct
5 Correct 13 ms 32244 KB Output is correct
6 Correct 13 ms 32244 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 32248 KB Output is correct
3 Correct 13 ms 32344 KB Output is correct
4 Correct 13 ms 32332 KB Output is correct
5 Correct 13 ms 32244 KB Output is correct
6 Correct 13 ms 32244 KB Output is correct
7 Correct 18 ms 34636 KB Output is correct
8 Correct 19 ms 34636 KB Output is correct
9 Correct 19 ms 34608 KB Output is correct
10 Correct 19 ms 34608 KB Output is correct
11 Correct 24 ms 34568 KB Output is correct
12 Correct 19 ms 34636 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 32248 KB Output is correct
3 Correct 13 ms 32344 KB Output is correct
4 Correct 13 ms 32332 KB Output is correct
5 Correct 13 ms 32244 KB Output is correct
6 Correct 13 ms 32244 KB Output is correct
7 Correct 18 ms 34636 KB Output is correct
8 Correct 19 ms 34636 KB Output is correct
9 Correct 19 ms 34608 KB Output is correct
10 Correct 19 ms 34608 KB Output is correct
11 Correct 24 ms 34568 KB Output is correct
12 Correct 19 ms 34636 KB Output is correct
13 Correct 339 ms 62568 KB Output is correct
14 Correct 345 ms 62432 KB Output is correct
15 Correct 382 ms 62436 KB Output is correct
16 Correct 291 ms 62420 KB Output is correct
17 Correct 323 ms 62448 KB Output is correct
18 Correct 299 ms 62532 KB Output is correct