QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#222038#2432. Go with the Flowucup-team2172#AC ✓2526ms60244kbC++141.7kb2023-10-21 15:31:572023-10-21 15:31:58

Judging History

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

  • [2023-10-21 15:31:58]
  • 评测
  • 测评结果:AC
  • 用时:2526ms
  • 内存:60244kb
  • [2023-10-21 15:31:57]
  • 提交

answer

#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
	int ch = 0, f = 0; x = 0;
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
	for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
	if(f) x = -x;
}
const int N = 2000005;
char s[100];
int a[N], dp[N], tim[N], n;
vector<int> vec[N];
int main(){
	read(n);
	int c = 0, sum = 0;
	for(int i = 1; i <= n; i++){
		scanf("%s", s);
		a[i] = strlen(s);
		c = max(a[i], c);
		sum += a[i] + 1;
	}
	int ans_d = 0, res = 0;
	for(int d = c; d <= sum; d++){
		int cur_text = a[1], cur_line = 1; vec[1].clear();
		for(int i = 2; i <= n; i++){
			vec[i].clear();
			if(cur_text + 1 + a[i] > d){
				//for(int j = cur_text + 1; j <= d; j++)
				//	vec[cur_line].push_back(j);
				cur_line++;
				cur_text = a[i];
			}
			else{
				vec[cur_line].push_back(++cur_text);
				cur_text += a[i];
			}
		}
		//if(d == 9) cout << d << " " << cur_line << endl;
		int m = cur_line;
		//for(int i = cur_text + 1; i <= d; i++)
		//	vec[m].push_back(i);
		for(int i = 1; i <= m; i++){
			for(auto x : vec[i]){
				//if(d == 9) cout << x << " ";
				tim[i*d+x] = d, dp[i*d+x] = 1;
				if(i > 1 && x > 1 && tim[(i-1)*d+(x-1)] == d)
					dp[i*d+x] = max(dp[i*d+x], dp[(i-1)*d+(x-1)] + 1);
				if(i > 1 && tim[(i-1)*d+x] == d)
					dp[i*d+x] = max(dp[i*d+x], dp[(i-1)*d+x] + 1);
				if(i > 1 && x < d && tim[(i-1)*d+(x+1)] == d)
					dp[i*d+x] = max(dp[i*d+x], dp[(i-1)*d+(x+1)] + 1);
				if(dp[i*d+x] > res){
					res = dp[i*d+x];
					ans_d = d;
				}
			}
		}
	}
	printf("%d %d\n", ans_d, res);
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 55652kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 54876kb

Test #3:

score: 0
Accepted
time: 6ms
memory: 55772kb

Test #4:

score: 0
Accepted
time: 4ms
memory: 55512kb

Test #5:

score: 0
Accepted
time: 13ms
memory: 55296kb

Test #6:

score: 0
Accepted
time: 4ms
memory: 56256kb

Test #7:

score: 0
Accepted
time: 3ms
memory: 56940kb

Test #8:

score: 0
Accepted
time: 4ms
memory: 55060kb

Test #9:

score: 0
Accepted
time: 4ms
memory: 55272kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 55804kb

Test #11:

score: 0
Accepted
time: 6ms
memory: 56260kb

Test #12:

score: 0
Accepted
time: 4ms
memory: 55240kb

Test #13:

score: 0
Accepted
time: 47ms
memory: 55500kb

Test #14:

score: 0
Accepted
time: 47ms
memory: 58672kb

Test #15:

score: 0
Accepted
time: 43ms
memory: 56436kb

Test #16:

score: 0
Accepted
time: 478ms
memory: 55896kb

Test #17:

score: 0
Accepted
time: 459ms
memory: 55716kb

Test #18:

score: 0
Accepted
time: 457ms
memory: 56260kb

Test #19:

score: 0
Accepted
time: 148ms
memory: 57020kb

Test #20:

score: 0
Accepted
time: 98ms
memory: 56340kb

Test #21:

score: 0
Accepted
time: 1168ms
memory: 57840kb

Test #22:

score: 0
Accepted
time: 2526ms
memory: 59032kb

Test #23:

score: 0
Accepted
time: 44ms
memory: 56740kb

Test #24:

score: 0
Accepted
time: 100ms
memory: 56752kb

Test #25:

score: 0
Accepted
time: 740ms
memory: 56072kb

Test #26:

score: 0
Accepted
time: 739ms
memory: 59156kb

Test #27:

score: 0
Accepted
time: 759ms
memory: 56180kb

Test #28:

score: 0
Accepted
time: 184ms
memory: 57244kb

Test #29:

score: 0
Accepted
time: 199ms
memory: 56628kb

Test #30:

score: 0
Accepted
time: 190ms
memory: 55464kb

Test #31:

score: 0
Accepted
time: 2310ms
memory: 59456kb

Test #32:

score: 0
Accepted
time: 1114ms
memory: 57572kb

Test #33:

score: 0
Accepted
time: 1009ms
memory: 57896kb

Test #34:

score: 0
Accepted
time: 45ms
memory: 55956kb

Test #35:

score: 0
Accepted
time: 4ms
memory: 55460kb

Test #36:

score: 0
Accepted
time: 1144ms
memory: 56144kb

Test #37:

score: 0
Accepted
time: 2389ms
memory: 59276kb

Test #38:

score: 0
Accepted
time: 2325ms
memory: 58364kb

Test #39:

score: 0
Accepted
time: 1672ms
memory: 59520kb

Test #40:

score: 0
Accepted
time: 1837ms
memory: 60052kb

Test #41:

score: 0
Accepted
time: 1905ms
memory: 56468kb

Test #42:

score: 0
Accepted
time: 2369ms
memory: 59560kb

Test #43:

score: 0
Accepted
time: 2465ms
memory: 60244kb

Test #44:

score: 0
Accepted
time: 2395ms
memory: 58608kb

Test #45:

score: 0
Accepted
time: 1671ms
memory: 56516kb

Test #46:

score: 0
Accepted
time: 1624ms
memory: 56348kb

Test #47:

score: 0
Accepted
time: 1672ms
memory: 58896kb

Test #48:

score: 0
Accepted
time: 1606ms
memory: 56500kb

Test #49:

score: 0
Accepted
time: 2225ms
memory: 56772kb

Test #50:

score: 0
Accepted
time: 1921ms
memory: 58324kb

Test #51:

score: 0
Accepted
time: 1693ms
memory: 60032kb

Test #52:

score: 0
Accepted
time: 1676ms
memory: 58280kb

Test #53:

score: 0
Accepted
time: 1347ms
memory: 56480kb

Test #54:

score: 0
Accepted
time: 0ms
memory: 55396kb

Test #55:

score: 0
Accepted
time: 75ms
memory: 55844kb

Test #56:

score: 0
Accepted
time: 7ms
memory: 56308kb

Test #57:

score: 0
Accepted
time: 2468ms
memory: 60104kb

Test #58:

score: 0
Accepted
time: 2494ms
memory: 59148kb

Test #59:

score: 0
Accepted
time: 85ms
memory: 56436kb

Test #60:

score: 0
Accepted
time: 49ms
memory: 55120kb

Test #61:

score: 0
Accepted
time: 4ms
memory: 55000kb

Test #62:

score: 0
Accepted
time: 36ms
memory: 56364kb

Test #63:

score: 0
Accepted
time: 229ms
memory: 55724kb

Test #64:

score: 0
Accepted
time: 92ms
memory: 55608kb

Test #65:

score: 0
Accepted
time: 1504ms
memory: 58812kb

Test #66:

score: 0
Accepted
time: 6ms
memory: 54996kb