제출 #1281182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281182		aren_dance	Strah (COCI18_strah)	C++20	99 / 110	1066 ms	47612 KiB

strah

// oj us strah.cpp : This file contains the 'main' function. Program execution begins and ends there.
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <complex>
#include <cassert>
#include <cfloat>
#include <memory>
#include <chrono>
#include <random>
#include <climits>
#include <limits>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <tuple>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
#define ll long long 
using namespace std;
const int N = 2e3 + 1;
const int M = 12;
int a[N][N];
ll s[N][N];
ll sp[N][M];
ll dp[N];
int n,m;
void fill() {
	for (int i = 1;i <= n;++i) {
		for (int j = 1;j <= m;++j) {
			if (a[i][j]) {
				s[i][j] = s[i - 1][j] + 1;
			}
			else {
				s[i][j] = 0;
			}
		}
	}
}
void ar_cin(){
	cin >> n >> m;
	for (int i = 1;i <= n;++i) {
		string s;
		cin >> s;
		for (int j = 1;j <= m;++j) {
			if (s[j - 1]=='.') {
				a[i][j] = 1;
			}
			else {
				a[i][j] = 0;
			}
		}
	}
}
ll get(int l,int r) {
	if (l > r) {
		return 1e9;
	}
	int x = log2(r - l + 1);
	return min(sp[l][x],sp[r-(1<<x)+1][x]);
}
void build(int ind) {
	for (int i = 1;i <= m;++i) {
		sp[i][0] = s[ind][i];
	}
	for (int i = 1;i < M;++i) {
		for (int j = 1;j <= m;++j) {
			sp[j][i] = min(sp[j][i-1],sp[j+(1<<(i-1))][i-1]);
		}
	}
}
int main()
{
	ar_cin();
	fill();
	ll answ = 0ll;
	for (int i = 1;i <= m;++i) {
		for (int j = 1;j <= i;++j) {
			dp[i]+=j*(i-j+1);
		}
	}
	for (int i = 1;i <= n;++i) {
		build(i);
		for (int j = 1;j <= m;++j) {
			int l = 1;
			int r = j-1;
			ll answl=j;
			while (l<=r) {
				ll mid = (l + r) / 2;
				if (get(mid, j-1) > s[i][j]) {
					r = mid - 1;
					answl = mid;
				}
				else {
					l = mid + 1;
				}
			}
			ll answr = j;
			l = j + 1;
			r = m;
			while (l <= r) {
				ll mid = (l + r) / 2;
				if (get(j,mid) == s[i][j]) {
					l = mid + 1;
					answr = mid;
				}
				else {
					r = mid - 1;
				}
			}
			ll f = (j - answl + 1) * (j - answl+2) / 2;
			ll e = (answr - j + 1) * (answr - j) / 2;swap(e, f);
			answ += (e*(answr-j+1)+f*(j-answl+1))*s[i][j]*(s[i][j]+1)/2;
		}
	}
	cout << answ << '\n';
	return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11