結果
問題 | No.866 レベルKの正方形 |
ユーザー | kotamanegi |
提出日時 | 2019-08-16 22:56:02 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3,358 ms / 6,000 ms |
コード長 | 3,320 bytes |
コンパイル時間 | 1,639 ms |
コンパイル使用メモリ | 148,640 KB |
実行使用メモリ | 410,228 KB |
最終ジャッジ日時 | 2024-05-07 19:23:38 |
合計ジャッジ時間 | 43,491 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2,637 ms
410,104 KB |
testcase_09 | AC | 2,850 ms
410,112 KB |
testcase_10 | AC | 3,358 ms
410,112 KB |
testcase_11 | AC | 3,352 ms
410,112 KB |
testcase_12 | AC | 2,679 ms
410,044 KB |
testcase_13 | AC | 3,342 ms
410,060 KB |
testcase_14 | AC | 2,510 ms
410,052 KB |
testcase_15 | AC | 3,284 ms
410,228 KB |
testcase_16 | AC | 3,131 ms
410,024 KB |
testcase_17 | AC | 3,311 ms
410,112 KB |
testcase_18 | AC | 3,317 ms
410,064 KB |
testcase_19 | AC | 2,387 ms
410,100 KB |
testcase_20 | AC | 2,140 ms
410,080 KB |
testcase_21 | AC | 2,182 ms
410,112 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
ソースコード
/* This Submission is to determine how many 120/240 min const. delivery point there are. //info 120 req. steps <= 5 test_case 1,6 == 50 delivery point 2,3,4,5,7 == 80 delivery point 8,9 == 90 delivery point 10 > 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; }