oj.uz

답안 #447120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
447120 2021-07-24T15:32:42 Z dz001 Bob (COCI14_bob) C++11
120 / 120
 497 ms 304 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;
		int lst=0;
		for(int 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]){
				lst=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()?lst: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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 204 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 292 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 204 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 288 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 359 ms 288 KB Output is correct
2 Correct 193 ms 304 KB Output is correct
3 Correct 196 ms 296 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 292 KB Output is correct
2 Correct 187 ms 296 KB Output is correct
3 Correct 187 ms 292 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 497 ms 292 KB Output is correct
2 Correct 176 ms 292 KB Output is correct
3 Correct 175 ms 292 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 464 ms 204 KB Output is correct
2 Correct 201 ms 292 KB Output is correct
3 Correct 176 ms 204 KB Output is correct