oj.uz

Submission #256906

# Submission time Handle Problem Language Result Execution time Memory
256906 2020-08-03T11:40:10 Z uacoder123 Strah (COCI18_strah) C++14
0 / 110
 250 ms 70748 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
  
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
char arr[2000][2000];
lli arr1[2000][2000],dp[2001][2001]={};
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lli n,m;
  cin>>n>>m;
  for(lli i=0;i<n;++i)
    for(lli j=0;j<m;++j)
      cin>>arr[i][j];
  for(lli j=0;j<m;++j)
  {
    lli c=-1;
    for(lli i=0;i<n;++i)
    {
      if(arr[i][j]=='#')
      {
        arr1[i][j]=i;
        c=i;
      }
      else
        arr1[i][j]=c;
    }
  }
  for(lli i=1;i<=2000;++i)
  {
    for(lli j=1;j<=2000;++j)
    {
      dp[i][j]=dp[i][j-1]+(i)*(i+1)*(j)/2;
    }
  }
  stack<pair<ii,ii>> s;
  lli ans1=0,ans=0;
  for(lli i=0;i<n;++i)
  {
    ans=dp[1][i-arr1[i][0]];
    s.push(mp(mp(0,0),mp(i-arr1[i][0],i-arr1[i][0])));
    ans1+=ans;
    lli arr2[m]={};
    arr2[0]=dp[1][i-arr1[i][0]];
    for(lli j=1;j<m;++j)
    {
      lli c=j,v=0;
      while(s.size())
      {
        if(s.top().S.F>=(i-arr1[i][j]))
        {
          ans-=arr2[s.top().F.S];
          c-=s.top().F.S-s.top().F.F+1;
          s.pop();
        }
        else
          break;
      }
      if(s.size())
      {
        v=s.top().S.S;
        ans+=(v)*(j-s.top().F.S);
        arr2[j]+=(v)*(j-s.top().F.S);
      }
      ans+=dp[j-c+1][(i-arr1[i][j])];
      arr2[j]+=dp[j-c+1][(i-arr1[i][j])];
      ans1+=ans;
      v+=(j-c+1)*(i-arr1[i][j]);
      s.push(mp(mp(c,j),mp((i-arr1[i][j]),v)));
    }
    while(s.size())
      s.pop();
  }
  cout<<ans1<<endl;
  return(0);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 31740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 31744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 34304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 34296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 34296 KB Output is correct
2 Incorrect 32 ms 34304 KB Output isn't correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 45944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 57464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 48248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 44920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 70748 KB Output isn't correct
2 Halted 0 ms 0 KB -