結果
問題 | No.866 レベルKの正方形 |
ユーザー |
![]() |
提出日時 | 2019-08-16 22:56:02 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,430 ms / 6,000 ms |
コード長 | 3,320 bytes |
コンパイル時間 | 1,466 ms |
コンパイル使用メモリ | 149,920 KB |
実行使用メモリ | 410,112 KB |
最終ジャッジ日時 | 2024-11-30 14:40:58 |
合計ジャッジ時間 | 44,182 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
/*This Submission is to determine how many 120/240 min const. delivery point there are.//info120 req. steps <= 5test_case 1,6 == 50 delivery point2,3,4,5,7 == 80 delivery point8,9 == 90 delivery point10 > 100 delivery point*/#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <algorithm>#include <utility>#include <functional>#include <cstring>#include <queue>#include <stack>#include <math.h>#include <iterator>#include <vector>#include <string>#include <set>#include <math.h>#include <iostream>#include <random>#include<map>#include <iomanip>#include <time.h>#include <stdlib.h>#include <list>#include <typeinfo>#include <list>#include <set>#include <cassert>#include<fstream>#include <unordered_map>#include <cstdlib>#include <complex>#include <cctype>#include <bitset>using namespace std;typedef string::const_iterator State;#define Ma_PI 3.141592653589793#define eps 0.00000001#define LONG_INF 1e18#define GOLD 1.61803398874989484820458#define MAX_MOD 1000000007#define MOD 1000000007#define seg_size 262144#define REP(a,b) for(long long a = 0;a < b;++a)unsigned long xor128() {static unsigned long x = time(NULL), y = 362436069, z = 521288629, w = 88675123;unsigned long t = (x ^ (x << 11));x = y; y = z; z = w;return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));}long long h, w;int cnt[2002][2002][26];long long earn_point(int left_x, int left_y, int right_x, int right_y, int t) {long long ans = cnt[right_x][right_y][t];ans -= cnt[left_x - 1][right_y][t];ans -= cnt[right_x][left_y - 1][t];ans += cnt[left_x - 1][left_y - 1][t];return ans;}long long func(long long k) {long long ans = 0;for (int i = 1; i <= w; ++i) {long long now_x = 1;long long now_y = i;long long back = 0;for (int j = 0; now_y <= w && now_x <= h; ++j) {while (true) {int now_cnt = 0;back++;REP(t, 26) {if (earn_point(back + 1, back + i, now_x, now_y, t) >= 1) {now_cnt++;}}if (now_cnt < k) {back--;break;}}int now_cnt = 0;REP(t, 26) {if (earn_point(back+1, back + i, now_x, now_y, t) >= 1) {now_cnt++;}}if (now_cnt >= k) {ans += back + 1LL;}now_x++;now_y++;}}for (int i = 2; i <= h; ++i) {long long now_x = i;long long now_y = 1;long long back = 0;for (int j = 0; now_y <= w && now_x <= h; ++j) {while (true) {int now_cnt = 0;back++;REP(t, 26) {if (earn_point(back + i, back + 1, now_x, now_y, t) >= 1) {now_cnt++;}}if (now_cnt < k) {back--;break;}}int now_cnt = 0;REP(t, 26) {if (earn_point(back + i, back + 1, now_x, now_y, t) >= 1) {now_cnt++;}}if (now_cnt >= k) {ans += (back + 1LL);}now_x++;now_y++;}}return ans;}int main(){iostream::sync_with_stdio(false);long long k;cin >> h >> w >> k;for (int i = 1; i <= h;++i) {string a;cin >> a;for (int q = 1; q <= w; ++q) {REP(j, 26) {cnt[i][q][j] += cnt[i][q - 1][j];}cnt[i][q][a[q - 1] - 'a']++;}}for (int i = 1; i <= h; ++i) {for (int q = 1; q <= w; ++q) {REP(j, 26) {cnt[i][q][j] += cnt[i - 1][q][j];}}}cout << func(k) - func(k+1) << endl;return 0;}