# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
77433 | 2018-09-27T19:30:58 Z | Hassoony | Bob (COCI14_bob) | C++17 | 195 ms | 8436 KB |
#include <bits/stdc++.h> #define F first #define S second using namespace std; typedef long long ll; typedef double D; const ll mod=998244353; const ll inf=(1ll<<61); const int MX=1009; int n,m,a[MX][MX],dp[MX][MX]; ll k[MX]; int DP(int x,int y){ int &ret=dp[x][y];if(ret!=-1)return ret; if(x==0)return ret=1; if(a[x-1][y]==a[x][y])return ret=DP(x-1,y)+1; return ret=1; } ll ans=0; void solve(int x,int b,int c){ stack<int>s; for(int j=b;j<=c;j++){ ll i=j; while(!s.empty()&&a[x][s.top()]>=a[x][j])i=s.top(),s.pop(); // cout<<j<<" "<<i<<" "<<k[i]<<endl; if(i==j){ ans+=dp[x][j]*(j-b+1); k[j]=dp[x][j]*(j-b+1); s.push(j); continue; } k[j]=dp[x][j]*(j-i) + k[i]; ans+=k[j]; s.push(j); } for(int j=b;j<=c;j++)k[j]=0; while(!s.empty())s.pop(); } int main(){ memset(dp,-1,sizeof(dp)); cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&a[i][j]); } } puts(""); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ DP(i,j); } } // puts(""); for(int i=0;i<n;i++){ int j=0,j1=0; while(j1<m){ while(j1<m&&a[i][j1]==a[i][j])j1++; solve(i,j,j1-1); j=j1; } } cout<<ans<<endl; } /* 5 3 2 2 2 2 2 1 1 1 1 2 1 2 1 2 1 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 4472 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 4476 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 37 ms | 6312 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 36 ms | 6312 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 48 ms | 6384 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 40 ms | 6388 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 185 ms | 8428 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 195 ms | 8428 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 180 ms | 8436 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 180 ms | 8436 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |