Submission #332781

#TimeUsernameProblemLanguageResultExecution timeMemory
332781vitkishloh228Strah (COCI18_strah)C++14
110 / 110
270 ms71020 KiB
#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])*((i-arr1[i][0])+1)/2))); ans1+=ans; lli arr2[m]={},ans2[m]; arr2[0]=dp[1][i-arr1[i][0]]; ans2[0]=ans; 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; ans2[j]=ans; s.push(mp(mp(c,j),mp(i-arr1[i][j],v+(i-arr1[i][j]+1)*(i-arr1[i][j])*(j-c+1)/2))); } while(s.size()) s.pop(); } cout<<ans1<<endl; return(0); }

Compilation message (stderr)

strah.cpp: In function 'int main()':
strah.cpp:59:20: warning: variable 'ans2' set but not used [-Wunused-but-set-variable]
   59 |     lli arr2[m]={},ans2[m];
      |                    ^~~~
#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...