結果
問題 | No.962 LCPs |
ユーザー | Leonardone |
提出日時 | 2019-12-25 19:48:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,565 bytes |
コンパイル時間 | 735 ms |
コンパイル使用メモリ | 74,240 KB |
実行使用メモリ | 9,988 KB |
最終ジャッジ日時 | 2024-09-25 10:04:39 |
合計ジャッジ時間 | 3,064 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 64 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; void bins(int col, int minRow, int maxRow); int n; vector<string> vs(2e5); long long ans; int main() { cin >> n; vs.resize(n); for (int i = 0; i < n; i++) { cin >> vs[i]; } // sort(vs.begin(), vs.end()); // for (int i = 0; i < n; i++) cout << vs[i] << endl; bins(0, 0, n-1); cout << ans << endl; return 0; } void bins(int col, int minRow, int maxRow) { int lRow = minRow; for (int row = minRow; row <= maxRow; row++) { if (vs[lRow].size() <= col) { lRow = row; continue; } if (vs[row].size() > col && vs[row][col] == vs[lRow][col]) { continue; } int len = row - lRow; if (len == 1) { ans += (long long)vs[lRow].size() - (long long)col; } else { long long lp = 1, rp = len; while (lp <= rp) { ans += lp * rp * (lp == rp ? 1LL : 2LL); lp++; rp--; } bins(col + 1, lRow, row - 1); } lRow = row; } if (vs[lRow].size() >= col) { int row = maxRow + 1; int len = row - lRow; if (len == 1) { ans += (long long)vs[lRow].size() - (long long)col; } else { long long lp = 1, rp = len; while (lp <= rp) { ans += lp * rp * (lp == rp ? 1LL : 2LL); lp++; rp--; } bins(col + 1, lRow, row - 1); } } }