QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372084 | #2432. Go with the Flow | UFRJ# | WA | 1ms | 3820kb | C++20 | 2.1kb | 2024-03-30 21:17:42 | 2024-03-30 21:17:44 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
using lint = int64_t;
int main(void) {
cin.tie(nullptr)->sync_with_stdio(false);
int n; cin>>n;
vector<int> v(n);
int left = 0, right = 0;
for(int i =0; i<n; i++){
string s; cin>>s;
v[i] = int(s.size());
left = max(left, v[i]);
right += v[i];
}
auto test = [&](int tam) -> int {
vector<vector<int>> mat = {{}};
int cur = 0;
for(int x : v){
if(cur == 0){
cur = x;
mat.back().push_back(cur);
} else if(cur + 1 + x <= tam){
cur += 1 + x;
mat.back().push_back(cur);
} else {
mat.push_back({});
cur = x;
mat.back().push_back(cur);
}
}
for(auto &row : mat){
row.pop_back();
}
// for(int i =0; i <int(mat.size()); i++){
// for(int x : mat[i])
// cout<<x<<" ";
// cout<<"\n";
// }
// cout<<"DP\n";
const int t = int(mat.size());
int ans = 0;
vector<int> dp(mat[0].size(), 1);
for(int i = 0; i + 1 < t; i++){
for(int d : dp){
ans = max(ans, d);
}
vector<int> nxt(mat[i+1].size(), 1);
for(int l = 0, r = 0; l < int(mat[i].size()); l++){
int x = mat[i][l];
while(mat[i+1][r] < (x - 1) && r < int(mat[i+1].size())) r++;
for(int j = r; j < int(mat[i+1].size()); j++){
if(mat[i+1][j] > x + 1) break;
nxt[j] = max(nxt[j], dp[l] + 1);
}
}
dp = nxt;
}
for(int d : dp) ans = max(ans, d);
return ans;
};
pair<int, int> ans = {0, left};
for(int tam = left; tam <= right; tam++){
int cur = test(tam);
if(cur > ans.first){
ans = {cur, tam};
}
}
cout<<ans.second<<" "<<ans.first<<"\n";
return 0;
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3820kb
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3588kb