QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#165195 | #2432. Go with the Flow | PetroTarnavskyi# | AC ✓ | 2306ms | 3980kb | C++17 | 1.6kb | 2023-09-05 16:35:50 | 2023-09-05 16:35:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 1 << 12;
string s[N];
int row[N], pos[N], firstInRow[N], dp[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
int minWidth = 0, sum = 0;
FOR(i, 0, n) {
cin >> s[i];
minWidth = max(minWidth, SZ(s[i]));
sum += SZ(s[i]);
}
int bestW = 0, ans = 0;
FOR(w, minWidth, sum + n + 47) {
FILL(dp, 0);
int curPos = 0, curRow = 0;
FOR(i, 0, n) {
if (curPos + SZ(s[i]) <= w) {
curPos += SZ(s[i]) + 1;
}
else {
curRow++;
curPos = SZ(s[i]) + 1;
firstInRow[curRow] = i;
}
pos[i] = curPos - 1;
row[i] = curRow;
}
firstInRow[curRow + 1] = n;
int ptr = 0;
FOR(i, 0, n - 1) {
if (row[i] != row[i + 1]) {
continue;
}
dp[i] = max(dp[i], 1);
if (dp[i] > ans) {
bestW = w;
ans = dp[i];
}
if (i == 0 || row[i] != row[i - 1]) {
ptr = firstInRow[row[i] + 1];
}
while (ptr < n && row[ptr] == row[i] + 1 && pos[ptr] < pos[i] - 1) {
ptr++;
}
FOR(j, ptr, ptr + 2) {
if (j < n && row[j] == row[i] + 1 && pos[j] <= pos[i] + 1) {
dp[j] = max(dp[j], dp[i] + 1);
}
}
}
}
cout << bestW << " " << ans << "\n";
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3552kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 3552kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 3536kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3588kb
Test #6:
score: 0
Accepted
time: 2ms
memory: 3596kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 3716kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 3596kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 3592kb
Test #10:
score: 0
Accepted
time: 1ms
memory: 3680kb
Test #11:
score: 0
Accepted
time: 1ms
memory: 3556kb
Test #12:
score: 0
Accepted
time: 1ms
memory: 3728kb
Test #13:
score: 0
Accepted
time: 51ms
memory: 3568kb
Test #14:
score: 0
Accepted
time: 52ms
memory: 3608kb
Test #15:
score: 0
Accepted
time: 52ms
memory: 3736kb
Test #16:
score: 0
Accepted
time: 560ms
memory: 3672kb
Test #17:
score: 0
Accepted
time: 553ms
memory: 3584kb
Test #18:
score: 0
Accepted
time: 572ms
memory: 3744kb
Test #19:
score: 0
Accepted
time: 164ms
memory: 3752kb
Test #20:
score: 0
Accepted
time: 94ms
memory: 3748kb
Test #21:
score: 0
Accepted
time: 1218ms
memory: 3752kb
Test #22:
score: 0
Accepted
time: 2137ms
memory: 3820kb
Test #23:
score: 0
Accepted
time: 57ms
memory: 3580kb
Test #24:
score: 0
Accepted
time: 93ms
memory: 3712kb
Test #25:
score: 0
Accepted
time: 747ms
memory: 3660kb
Test #26:
score: 0
Accepted
time: 774ms
memory: 3728kb
Test #27:
score: 0
Accepted
time: 807ms
memory: 3724kb
Test #28:
score: 0
Accepted
time: 181ms
memory: 3632kb
Test #29:
score: 0
Accepted
time: 197ms
memory: 3788kb
Test #30:
score: 0
Accepted
time: 182ms
memory: 3660kb
Test #31:
score: 0
Accepted
time: 1940ms
memory: 3824kb
Test #32:
score: 0
Accepted
time: 1071ms
memory: 3744kb
Test #33:
score: 0
Accepted
time: 1203ms
memory: 3724kb
Test #34:
score: 0
Accepted
time: 51ms
memory: 3624kb
Test #35:
score: 0
Accepted
time: 1ms
memory: 3552kb
Test #36:
score: 0
Accepted
time: 1191ms
memory: 3756kb
Test #37:
score: 0
Accepted
time: 2042ms
memory: 3920kb
Test #38:
score: 0
Accepted
time: 1974ms
memory: 3808kb
Test #39:
score: 0
Accepted
time: 1713ms
memory: 3820kb
Test #40:
score: 0
Accepted
time: 1720ms
memory: 3816kb
Test #41:
score: 0
Accepted
time: 1792ms
memory: 3784kb
Test #42:
score: 0
Accepted
time: 2019ms
memory: 3808kb
Test #43:
score: 0
Accepted
time: 2025ms
memory: 3812kb
Test #44:
score: 0
Accepted
time: 2040ms
memory: 3980kb
Test #45:
score: 0
Accepted
time: 1631ms
memory: 3760kb
Test #46:
score: 0
Accepted
time: 1634ms
memory: 3904kb
Test #47:
score: 0
Accepted
time: 1641ms
memory: 3780kb
Test #48:
score: 0
Accepted
time: 1604ms
memory: 3776kb
Test #49:
score: 0
Accepted
time: 1939ms
memory: 3912kb
Test #50:
score: 0
Accepted
time: 1738ms
memory: 3728kb
Test #51:
score: 0
Accepted
time: 1679ms
memory: 3888kb
Test #52:
score: 0
Accepted
time: 1717ms
memory: 3888kb
Test #53:
score: 0
Accepted
time: 1424ms
memory: 3880kb
Test #54:
score: 0
Accepted
time: 2ms
memory: 3600kb
Test #55:
score: 0
Accepted
time: 69ms
memory: 3716kb
Test #56:
score: 0
Accepted
time: 8ms
memory: 3572kb
Test #57:
score: 0
Accepted
time: 2306ms
memory: 3816kb
Test #58:
score: 0
Accepted
time: 2252ms
memory: 3952kb
Test #59:
score: 0
Accepted
time: 80ms
memory: 3704kb
Test #60:
score: 0
Accepted
time: 46ms
memory: 3760kb
Test #61:
score: 0
Accepted
time: 2ms
memory: 3676kb
Test #62:
score: 0
Accepted
time: 36ms
memory: 3628kb
Test #63:
score: 0
Accepted
time: 228ms
memory: 3680kb
Test #64:
score: 0
Accepted
time: 92ms
memory: 3608kb
Test #65:
score: 0
Accepted
time: 1546ms
memory: 3924kb
Test #66:
score: 0
Accepted
time: 1ms
memory: 3592kb