QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#216768 | #2432. Go with the Flow | Swarthmore# | AC ✓ | 2181ms | 30972kb | C++20 | 2.3kb | 2023-10-15 22:36:53 | 2023-10-15 22:36:53 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld; // change to double if appropriate
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
const char nl = '\n';
void solve() {
int N; cin >> N;
vector<string> words(N);
vector<int> len(N);
int mxlen = 0;
F0R(i, N) {
cin >> words[i];
len[i] = sz(words[i]);
mxlen = max(mxlen, len[i]);
}
vector<vector<int>> space(2600);
vector<vector<int>> dp(2600, vector<int>(2600));
pair<int, int> best = {-1, -1};
for (int W = mxlen; W <= 2600 * 81; W++) {
int row = 0;
int col = 0;
F0R(i, N) {
if (col + (col != 0) + len[i] > W) {
row++;
col = 0;
}
assert(col + (col != 0) + len[i] <= W);
if (col > 0) {
space[row].push_back(col);
col++;
}
col += len[i];
}
// if (W == 15) {
// FOR(r, 0, row+1) {
// for (auto i: space[r]) {
// cout << i << ' ';
// }
// cout << endl;
// }
// }
int ans = 0;
for (int r = 0; r <= row; r++) {
if (r == 0) {
F0R(j, sz(space[0])) dp[0][j] = 1;
}
else {
int pt = 0;
F0R(j, sz(space[r])) {
pt = max(0, pt - 3);
dp[r][j] = 1;
while (pt < sz(space[r-1]) && space[r-1][pt] < space[r][j]-1) pt++;
while (pt < sz(space[r-1]) && abs(space[r-1][pt] - space[r][j]) <= 1) {
dp[r][j] = max(dp[r][j], dp[r-1][pt] + 1);
pt++;
}
}
}
F0R(j, sz(space[r])) {
ans = max(ans, dp[r][j]);
}
}
if (ans > best.first) {
best = {ans, W};
}
for (int i = 0; i <= row; i++) space[i].clear();
}
cout << best.second << ' ' << best.first << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
solve();
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 17ms
memory: 29756kb
Test #2:
score: 0
Accepted
time: 11ms
memory: 29736kb
Test #3:
score: 0
Accepted
time: 3ms
memory: 29796kb
Test #4:
score: 0
Accepted
time: 23ms
memory: 29720kb
Test #5:
score: 0
Accepted
time: 106ms
memory: 30140kb
Test #6:
score: 0
Accepted
time: 30ms
memory: 29692kb
Test #7:
score: 0
Accepted
time: 10ms
memory: 29892kb
Test #8:
score: 0
Accepted
time: 17ms
memory: 29784kb
Test #9:
score: 0
Accepted
time: 17ms
memory: 29696kb
Test #10:
score: 0
Accepted
time: 15ms
memory: 29860kb
Test #11:
score: 0
Accepted
time: 21ms
memory: 29840kb
Test #12:
score: 0
Accepted
time: 36ms
memory: 29736kb
Test #13:
score: 0
Accepted
time: 519ms
memory: 30240kb
Test #14:
score: 0
Accepted
time: 513ms
memory: 30312kb
Test #15:
score: 0
Accepted
time: 490ms
memory: 30492kb
Test #16:
score: 0
Accepted
time: 1444ms
memory: 30548kb
Test #17:
score: 0
Accepted
time: 1449ms
memory: 30548kb
Test #18:
score: 0
Accepted
time: 1440ms
memory: 30496kb
Test #19:
score: 0
Accepted
time: 1248ms
memory: 30452kb
Test #20:
score: 0
Accepted
time: 1204ms
memory: 30468kb
Test #21:
score: 0
Accepted
time: 1727ms
memory: 30592kb
Test #22:
score: 0
Accepted
time: 2099ms
memory: 30644kb
Test #23:
score: 0
Accepted
time: 1181ms
memory: 30380kb
Test #24:
score: 0
Accepted
time: 1213ms
memory: 30396kb
Test #25:
score: 0
Accepted
time: 1295ms
memory: 30684kb
Test #26:
score: 0
Accepted
time: 1290ms
memory: 30700kb
Test #27:
score: 0
Accepted
time: 1307ms
memory: 30724kb
Test #28:
score: 0
Accepted
time: 546ms
memory: 30356kb
Test #29:
score: 0
Accepted
time: 548ms
memory: 30352kb
Test #30:
score: 0
Accepted
time: 547ms
memory: 30352kb
Test #31:
score: 0
Accepted
time: 2064ms
memory: 30728kb
Test #32:
score: 0
Accepted
time: 1639ms
memory: 30720kb
Test #33:
score: 0
Accepted
time: 1708ms
memory: 30844kb
Test #34:
score: 0
Accepted
time: 1109ms
memory: 30308kb
Test #35:
score: 0
Accepted
time: 3ms
memory: 29840kb
Test #36:
score: 0
Accepted
time: 1727ms
memory: 30576kb
Test #37:
score: 0
Accepted
time: 2060ms
memory: 30732kb
Test #38:
score: 0
Accepted
time: 2071ms
memory: 30944kb
Test #39:
score: 0
Accepted
time: 1939ms
memory: 30584kb
Test #40:
score: 0
Accepted
time: 1958ms
memory: 30972kb
Test #41:
score: 0
Accepted
time: 1968ms
memory: 30672kb
Test #42:
score: 0
Accepted
time: 2095ms
memory: 30776kb
Test #43:
score: 0
Accepted
time: 2082ms
memory: 30676kb
Test #44:
score: 0
Accepted
time: 2061ms
memory: 30744kb
Test #45:
score: 0
Accepted
time: 1882ms
memory: 30692kb
Test #46:
score: 0
Accepted
time: 1890ms
memory: 30696kb
Test #47:
score: 0
Accepted
time: 1925ms
memory: 30724kb
Test #48:
score: 0
Accepted
time: 1897ms
memory: 30644kb
Test #49:
score: 0
Accepted
time: 2028ms
memory: 30652kb
Test #50:
score: 0
Accepted
time: 1990ms
memory: 30712kb
Test #51:
score: 0
Accepted
time: 1916ms
memory: 30536kb
Test #52:
score: 0
Accepted
time: 1886ms
memory: 30624kb
Test #53:
score: 0
Accepted
time: 1803ms
memory: 30744kb
Test #54:
score: 0
Accepted
time: 26ms
memory: 29776kb
Test #55:
score: 0
Accepted
time: 271ms
memory: 30252kb
Test #56:
score: 0
Accepted
time: 87ms
memory: 29892kb
Test #57:
score: 0
Accepted
time: 2175ms
memory: 30908kb
Test #58:
score: 0
Accepted
time: 2181ms
memory: 30916kb
Test #59:
score: 0
Accepted
time: 344ms
memory: 30232kb
Test #60:
score: 0
Accepted
time: 227ms
memory: 30492kb
Test #61:
score: 0
Accepted
time: 18ms
memory: 29848kb
Test #62:
score: 0
Accepted
time: 190ms
memory: 30184kb
Test #63:
score: 0
Accepted
time: 563ms
memory: 30280kb
Test #64:
score: 0
Accepted
time: 303ms
memory: 30248kb
Test #65:
score: 0
Accepted
time: 1842ms
memory: 30864kb
Test #66:
score: 0
Accepted
time: 4ms
memory: 29696kb