oj.uz

Submission #256825

# Submission time Handle Problem Language Result Execution time Memory
256825 2020-08-03T09:05:07 Z uacoder123 Strah (COCI18_strah) C++14
88 / 110
 1000 ms 39416 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;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lli n,m;
  cin>>n>>m;
  char arr[n][m];
  lli arr1[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]=='#')
        c=i;
      else
        arr1[i][j]=c;
    }
  }
  lli ans=0;
  for(lli i=0;i<n;++i)
  {
    for(lli j=0;j<m;++j)
    {
      lli c=-1;
      if(arr[i][j]=='#')
        continue;
      for(lli k=j;k>=0;--k)
      {
        if(arr[i][k]=='#')
          break;
        c=max(c,arr1[i][k]);
        ans+=(j-k+1)*(i-(c+1)+1)*(i-(c+1)+1+1)/2;
      }
    }
  }
  cout<<ans<<endl;
  return(0);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 6 ms 1152 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 6 ms 1152 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1152 KB Output is correct
2 Correct 7 ms 1152 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 10616 KB Output is correct
2 Correct 191 ms 23748 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 24568 KB Output is correct
2 Correct 304 ms 36216 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 15608 KB Output is correct
2 Correct 216 ms 25864 KB Output is correct

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2944 KB Output is correct
2 Execution timed out 1094 ms 29048 KB Time limit exceeded

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 39416 KB Time limit exceeded
2 Halted 0 ms 0 KB -