Submission #77432

#TimeUsernameProblemLanguageResultExecution timeMemory
77432HassoonyBob (COCI14_bob)C++17
0 / 120
178 ms8632 KiB
#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); } } 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 (stderr)

bob.cpp: In function 'int main()':
bob.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...