QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#165195#2432. Go with the FlowPetroTarnavskyi#AC ✓2306ms3980kbC++171.6kb2023-09-05 16:35:502023-09-05 16:35:52

Judging History

你现在查看的是最新测评结果

  • [2023-09-05 16:35:52]
  • 评测
  • 测评结果:AC
  • 用时:2306ms
  • 内存:3980kb
  • [2023-09-05 16:35:50]
  • 提交

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