oj.uz

Submission #251092

# Submission time Handle Problem Language Result Execution time Memory
251092 2020-07-20T06:56:51 Z dvdg6566 Strah (COCI18_strah) C++14
88 / 110
 1000 ms 46456 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=2100;
const ll MAXK=1000001;
const ll INF = 1e13;
const ll MOD = 1e9+7;

ll cost[MAXN];
ll R,C;
ll A[MAXN][MAXN];
queue<ll> ep[MAXN];
stack<ll> rm[MAXN];
set<ll> S;
ll cur,ans;

void ins(ll x){
	ll r=*(S.lb(x));
	ll l=*(--S.lb(x));
	S.insert(x);
	cur-=cost[r-l-1];
	cur+=cost[r-x-1];
	cur+=cost[x-l-1];
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>R>>C;
	for(ll i=1;i<=C;++i){
		for(ll j=1;j<=i;++j){
			cost[i]+=j*(i-j+1);
		}
	}
	for(ll i=0;i<R;++i){
		string S;cin>>S;
		for(ll j=0;j<C;++j){
			if(S[j]=='#'){
				A[i][j]=1;
				ep[j].push(i);
			}
		}
	}

	// for(ll i=R-1;i>=0;--i){
	// 	for(ll j=0;j<C;++j)cerr<<A[i][j];
	// 	cerr<<'\n';
	// }

	for(ll lowp=0;lowp<R;++lowp){
		S.clear();
		S.insert(-1);S.insert(C);
		cur=cost[C];

		// cerr<<"Low row "<<lowp<<'\n';
		for(ll j=0;j<C;++j)if(SZ(ep[j])&&ep[j].front()<lowp){
			// cerr<<"Removing "<<j<<'\n';
			ep[j].pop();
		}

		for(ll j=0;j<C;++j)if(SZ(ep[j])){
			rm[ep[j].front()].push(j);
		}

		for(ll topr=lowp;topr<R;++topr){
			while(SZ(rm[topr])){
				ins(rm[topr].top());
				rm[topr].pop();
			}
			ans+=cur*(topr-lowp+1);
			// cerr<<"Bottom "<<lowp<<" top "<<topr<<" cost "<<cur*(topr-lowp+1)<<'\n';
		}
	}
	cout<<ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5248 KB Output is correct
2 Correct 26 ms 5120 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5248 KB Output is correct
2 Correct 24 ms 5120 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3328 KB Output is correct
2 Correct 24 ms 5120 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 17120 KB Output is correct
2 Correct 798 ms 30720 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 31224 KB Output is correct
2 Execution timed out 1010 ms 39672 KB Time limit exceeded

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 18544 KB Output is correct
2 Correct 831 ms 33016 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 13056 KB Output is correct
2 Correct 847 ms 28256 KB Output is correct

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 19984 KB Output is correct
2 Execution timed out 1096 ms 46456 KB Time limit exceeded