QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380765 | #2432. Go with the Flow | 8BQube# | AC ✓ | 4605ms | 11108kb | C++20 | 1.7kb | 2024-04-07 11:26:59 | 2024-04-07 11:26:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
int vis[1000005], dp[1000005];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
vector<string> vec(n);
for (auto &s : vec)
cin >> s;
pii ans = pii(-1, 0);
auto check = [&](int width) {
vector<int> arr;
int cur = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
if (cur == 0 || cur + 1 + SZ(vec[i]) > width) {
if (cur != 0) ++cnt;
cur = SZ(vec[i]);
}
else {
vis[cnt * width + cur] = width;
arr.pb(cnt * width + cur);
dp[cnt * width + cur] = 1;
cur += 1 + SZ(vec[i]);
}
}
++cnt;
auto get_val = [&](int x, int y, int &mx) {
if (x < 0 || y < 0 || x >= cnt || y >= width || vis[x * width + y] != width) return;
mx = max(dp[x * width + y], mx);
};
int nw = 0;
for (int i : arr) {
int x = i / width, y = i % width;
int mx = 0;
get_val(x - 1, y - 1, mx);
get_val(x - 1, y, mx);
get_val(x - 1, y + 1, mx);
dp[i] = max(1, mx + 1);
nw = max(nw, dp[i]);
}
if (nw > ans.X)
ans = pii(nw, width);
};
int sum = SZ(vec[0]), mx = SZ(vec[0]);
for (int i = 1; i < n; ++i)
sum += 1 + SZ(vec[i]), mx = max(mx, SZ(vec[i]));
for (int i = mx; i <= sum; ++i)
check(i);
cout << ans.Y << " " << ans.X << "\n";
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 5612kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 5936kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 5704kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 5612kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 5612kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 5616kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 5672kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 5608kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 5676kb
Test #10:
score: 0
Accepted
time: 1ms
memory: 5644kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 5840kb
Test #12:
score: 0
Accepted
time: 1ms
memory: 5672kb
Test #13:
score: 0
Accepted
time: 68ms
memory: 5800kb
Test #14:
score: 0
Accepted
time: 64ms
memory: 5764kb
Test #15:
score: 0
Accepted
time: 70ms
memory: 5696kb
Test #16:
score: 0
Accepted
time: 865ms
memory: 5944kb
Test #17:
score: 0
Accepted
time: 843ms
memory: 8036kb
Test #18:
score: 0
Accepted
time: 765ms
memory: 7968kb
Test #19:
score: 0
Accepted
time: 200ms
memory: 6028kb
Test #20:
score: 0
Accepted
time: 131ms
memory: 5808kb
Test #21:
score: 0
Accepted
time: 2077ms
memory: 6468kb
Test #22:
score: 0
Accepted
time: 4233ms
memory: 11100kb
Test #23:
score: 0
Accepted
time: 68ms
memory: 5976kb
Test #24:
score: 0
Accepted
time: 133ms
memory: 5744kb
Test #25:
score: 0
Accepted
time: 1270ms
memory: 8260kb
Test #26:
score: 0
Accepted
time: 1282ms
memory: 6292kb
Test #27:
score: 0
Accepted
time: 1409ms
memory: 6268kb
Test #28:
score: 0
Accepted
time: 307ms
memory: 5864kb
Test #29:
score: 0
Accepted
time: 340ms
memory: 8052kb
Test #30:
score: 0
Accepted
time: 322ms
memory: 5964kb
Test #31:
score: 0
Accepted
time: 3801ms
memory: 9544kb
Test #32:
score: 0
Accepted
time: 2049ms
memory: 10240kb
Test #33:
score: 0
Accepted
time: 1663ms
memory: 6604kb
Test #34:
score: 0
Accepted
time: 66ms
memory: 5740kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 5552kb
Test #36:
score: 0
Accepted
time: 2014ms
memory: 6392kb
Test #37:
score: 0
Accepted
time: 3954ms
memory: 10984kb
Test #38:
score: 0
Accepted
time: 3877ms
memory: 10992kb
Test #39:
score: 0
Accepted
time: 3189ms
memory: 6860kb
Test #40:
score: 0
Accepted
time: 3327ms
memory: 10384kb
Test #41:
score: 0
Accepted
time: 3414ms
memory: 8944kb
Test #42:
score: 0
Accepted
time: 3932ms
memory: 11108kb
Test #43:
score: 0
Accepted
time: 4051ms
memory: 7360kb
Test #44:
score: 0
Accepted
time: 4255ms
memory: 10696kb
Test #45:
score: 0
Accepted
time: 3208ms
memory: 8976kb
Test #46:
score: 0
Accepted
time: 3079ms
memory: 6836kb
Test #47:
score: 0
Accepted
time: 3143ms
memory: 9092kb
Test #48:
score: 0
Accepted
time: 3054ms
memory: 6796kb
Test #49:
score: 0
Accepted
time: 3715ms
memory: 10076kb
Test #50:
score: 0
Accepted
time: 3448ms
memory: 6972kb
Test #51:
score: 0
Accepted
time: 3175ms
memory: 10312kb
Test #52:
score: 0
Accepted
time: 3437ms
memory: 6856kb
Test #53:
score: 0
Accepted
time: 2639ms
memory: 6684kb
Test #54:
score: 0
Accepted
time: 1ms
memory: 5848kb
Test #55:
score: 0
Accepted
time: 123ms
memory: 6068kb
Test #56:
score: 0
Accepted
time: 6ms
memory: 5760kb
Test #57:
score: 0
Accepted
time: 4605ms
memory: 10232kb
Test #58:
score: 0
Accepted
time: 4605ms
memory: 10920kb
Test #59:
score: 0
Accepted
time: 144ms
memory: 5964kb
Test #60:
score: 0
Accepted
time: 77ms
memory: 5788kb
Test #61:
score: 0
Accepted
time: 0ms
memory: 5564kb
Test #62:
score: 0
Accepted
time: 51ms
memory: 7852kb
Test #63:
score: 0
Accepted
time: 450ms
memory: 8360kb
Test #64:
score: 0
Accepted
time: 177ms
memory: 5968kb
Test #65:
score: 0
Accepted
time: 2844ms
memory: 6700kb
Test #66:
score: 0
Accepted
time: 0ms
memory: 5676kb