QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#216768#2432. Go with the FlowSwarthmore#AC ✓2181ms30972kbC++202.3kb2023-10-15 22:36:532023-10-15 22:36:53

Judging History

This is the latest submission verdict.

  • [2023-10-15 22:36:53]
  • Judged
  • Verdict: AC
  • Time: 2181ms
  • Memory: 30972kb
  • [2023-10-15 22:36:53]
  • Submitted

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