oj.uz

Submission #447119

# Submission time Handle Problem Language Result Execution time Memory
447119 2021-07-24T15:31:47 Z dz001 Bob (COCI14_bob) C++11
120 / 120
 469 ms 2244 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
 
typedef long long ll;

const int N=1e3+10;
ll a[N],h[N],num[N];
int n,m;

signed main(){
	cin>>n>>m;
	
	ll ans=0;
	a[0]=h[0]=num[0]=0;
	for(int i=1;i<=n;++i){
		stack<int> st;
		for(int tmp=0,j=1;j<=m;++j){
			int idx=-1,x; cin>>x;
			h[j]=(a[j]==x?h[j]:0)+1,a[j]=x;
			if(a[j]!=a[j-1]){
				tmp=j-1;
				num[j-1]=0;
				while(!st.empty())st.pop();
			}
			
			while(!st.empty()&&h[st.top()]>=h[j])st.pop();
			if(idx==-1)idx=(st.empty()?tmp:st.top());
			assert(idx!=-1);
			num[j]=num[idx]+(j-idx)*h[j];
			st.push(j);
			ans+=num[j];
		}
	}
	cout<<ans;
	
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.";
#endif
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 204 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 288 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 288 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 292 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 288 KB Output is correct
2 Correct 208 ms 2244 KB Output is correct
3 Correct 184 ms 2216 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 324 KB Output is correct
2 Correct 182 ms 2204 KB Output is correct
3 Correct 178 ms 2212 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 204 KB Output is correct
2 Correct 178 ms 2244 KB Output is correct
3 Correct 180 ms 2204 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 296 KB Output is correct
2 Correct 185 ms 2220 KB Output is correct
3 Correct 178 ms 2240 KB Output is correct