QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#56052 | #2432. Go with the Flow | captured# | AC ✓ | 5355ms | 12176kb | C++17 | 5.2kb | 2022-10-16 17:58:10 | 2022-10-16 17:58:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define LL long long
#define READ(x) freopen(x,"r",stdin)
#define WRITE(x) freopen(x,"w",stdout)
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define mem(x,y) memset(x,y,sizeof x )
#define ch printf("Came Here!!!!!!!!!!!!!!!\n")
#define deb(x) cerr<<#x<<" :: "<<x<<" "
#define dnl cerr<<endl
#define FOR(i,n) for(int i=0;i<n;i++)
#define cnd tree[idx]
#define lc tree[idx*2]
#define rc tree[idx*2+1]
#define lnd (2*idx),(b),( (b+e) /2 )
#define rnd ((2*idx)+1),(((b+e)/2)+1),(e)
#define popcount __builtin_popcount
const LL INF = 1LL<<60;
const double PI = 2.0 * acos(0.0);
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;
//// Including Policy Based DS
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/////cout<<*X.find_by_order(1)<<endl;
/////cout<<X.order_of_key(-5)<<endl;
//typedef tree<
//pii,
//null_type,
//less<pii>,
//rb_tree_tag,
//tree_order_statistics_node_update>
//ordered_set;
// Grid direction array [4]
int X[4]={0,0,-1,1};
int Y[4]={1,-1,0,0};
// Grid direction array [8]
int X8[8]={0,0,1,-1,-1,1,1,-1};
int Y8[8]={1,-1,0,0,-1,-1,1,1};
// Bishop direction array
int BX[8]={0,0,1,-1,-1,1,1,-1};
int BY[8]={1,-1,0,0,-1,-1,1,1};
// Knight Direction Array
int KX[8] = {1,1,2,2,-1,-1,-2,-2};
int KY[8] = {2,-2,1,-1,2,-2,1,-1};
inline LL modMul(LL a, LL b,LL mod){
LL ans = 0;
a = a % mod;
while (b > 0){
if ( b % 2 )ans = (ans%mod+ a%mod) % mod;
a = (a%mod * 2%mod) % mod;
b /= 2;
}
return ans % mod;
}
inline LL power(LL a,LL b,LL mod){
if(b==0)return 1LL%mod;
LL x=power( a,b/2,mod );
x = (x*x) % mod;
if( b%2==1 )x = (x*a)%mod;
return x%mod;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
LL my_rand(LL l, LL r) {
return uniform_int_distribution<LL>(l, r) (rng);
}
//-------------------------------------------------------------------------------
//-------------------------------------------------------------------------------
const int mx = 234567;
vector<string> arr;
vector<string> lines;
vector<int> dp[2505];
int plen[2505];
/*
4
a bc
d ef
*/
void solve(int cs){
int n,m,k;
cin>>n;
int minlen=0;
int sum = 0;
FOR(i,n){
string s;cin>>s;
arr.pb(s);
minlen = max((int)s.size(),minlen);
sum += (int)s.size();
}
int ans = 0;
int linelen = n;
for(int len=minlen;len<=sum+n;len++){
lines.clear();
int curlen=0;
string curstring = "";
for(string &s:arr){
int deli = 0;
if((int)curstring.size() > 0)deli=1;
if( deli+(int)curstring.size()+(int)s.size() > len ){
lines.pb(curstring);
curstring = s;
}
else{
if( (int)curstring.size()==0 )curstring = s;
else curstring += " "+s;
}
}
if((int)curstring.size() > 0){
lines.pb(curstring);
}
int sz = (int)lines.size();
bool fnd = 0;
FOR(i,sz){
int cur = (int)lines[i].size();
if( cur != plen[i] ){
fnd=1;
}
plen[i] = cur;
}
if(!fnd)continue;
if(ans >= sz){
break;
}
for(int i=0;i<sz;i++){
dp[i].resize(len+2,0);
}
int curans = 0;
for(int i=0;i<=len;i++){
if(i >= (int)lines[0].size())dp[0][i] = 0;
else{
if(lines[0][i]==' ')dp[0][i] = 1, curans=1;
else dp[0][i] = 0;
}
}
for(int i=1;i<sz;i++){
int z = (int)lines[i].size();
for(int j=0;j<z;j++){
int p=j-1,q=j,r=j+1;
dp[i][j] = 0;
if(lines[i][j]==' '){
if(p>=0) {
dp[i][j] = max(dp[i][j],dp[i-1][p]+1);
}
dp[i][j] = max(dp[i][j],dp[i-1][q]+1);
if(r<len){
dp[i][j] = max(dp[i][j],dp[i-1][r]+1);
}
}
curans = max(curans,dp[i][j]);
}
for(int j=z;j<=len;j++)dp[i][j] = 0;
}
if(curans > ans){
ans = curans;
linelen = len;
}
}
cout<<linelen<<" ";
cout<<ans<<endl;
}
int main(){
BOOST;
// READ("in.txt");
// WRITE("out.txt");
#ifdef MujahidPC
double start = clock();
#endif
int t;
t = 1;
// cin>>t;
FOR(cs,t)solve(cs+1);
#ifdef MujahidPC
double tim = (clock() - start)/CLOCKS_PER_SEC;
cerr<<"Running Time : "<<tim<<" \n";
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3716kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3640kb
Test #3:
score: 0
Accepted
time: 2ms
memory: 3708kb
Test #4:
score: 0
Accepted
time: 2ms
memory: 3648kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3752kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3636kb
Test #7:
score: 0
Accepted
time: 2ms
memory: 3704kb
Test #8:
score: 0
Accepted
time: 2ms
memory: 3708kb
Test #9:
score: 0
Accepted
time: 2ms
memory: 3632kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 3716kb
Test #11:
score: 0
Accepted
time: 2ms
memory: 3808kb
Test #12:
score: 0
Accepted
time: 0ms
memory: 3652kb
Test #13:
score: 0
Accepted
time: 24ms
memory: 4116kb
Test #14:
score: 0
Accepted
time: 30ms
memory: 4092kb
Test #15:
score: 0
Accepted
time: 31ms
memory: 4264kb
Test #16:
score: 0
Accepted
time: 584ms
memory: 5736kb
Test #17:
score: 0
Accepted
time: 519ms
memory: 5736kb
Test #18:
score: 0
Accepted
time: 510ms
memory: 5700kb
Test #19:
score: 0
Accepted
time: 26ms
memory: 4288kb
Test #20:
score: 0
Accepted
time: 3ms
memory: 4004kb
Test #21:
score: 0
Accepted
time: 1723ms
memory: 8276kb
Test #22:
score: 0
Accepted
time: 10ms
memory: 5716kb
Test #23:
score: 0
Accepted
time: 3ms
memory: 3840kb
Test #24:
score: 0
Accepted
time: 3ms
memory: 3972kb
Test #25:
score: 0
Accepted
time: 1173ms
memory: 7284kb
Test #26:
score: 0
Accepted
time: 1391ms
memory: 7432kb
Test #27:
score: 0
Accepted
time: 1357ms
memory: 7396kb
Test #28:
score: 0
Accepted
time: 290ms
memory: 5440kb
Test #29:
score: 0
Accepted
time: 363ms
memory: 5544kb
Test #30:
score: 0
Accepted
time: 343ms
memory: 5516kb
Test #31:
score: 0
Accepted
time: 2869ms
memory: 11268kb
Test #32:
score: 0
Accepted
time: 127ms
memory: 6608kb
Test #33:
score: 0
Accepted
time: 23ms
memory: 5416kb
Test #34:
score: 0
Accepted
time: 1ms
memory: 3856kb
Test #35:
score: 0
Accepted
time: 0ms
memory: 3640kb
Test #36:
score: 0
Accepted
time: 1875ms
memory: 8292kb
Test #37:
score: 0
Accepted
time: 2466ms
memory: 11420kb
Test #38:
score: 0
Accepted
time: 2681ms
memory: 11352kb
Test #39:
score: 0
Accepted
time: 3733ms
memory: 11012kb
Test #40:
score: 0
Accepted
time: 3864ms
memory: 11468kb
Test #41:
score: 0
Accepted
time: 4073ms
memory: 11432kb
Test #42:
score: 0
Accepted
time: 2160ms
memory: 11240kb
Test #43:
score: 0
Accepted
time: 2417ms
memory: 11440kb
Test #44:
score: 0
Accepted
time: 2665ms
memory: 11416kb
Test #45:
score: 0
Accepted
time: 4519ms
memory: 11160kb
Test #46:
score: 0
Accepted
time: 4516ms
memory: 11024kb
Test #47:
score: 0
Accepted
time: 4372ms
memory: 11312kb
Test #48:
score: 0
Accepted
time: 4329ms
memory: 11164kb
Test #49:
score: 0
Accepted
time: 4386ms
memory: 12176kb
Test #50:
score: 0
Accepted
time: 4025ms
memory: 11636kb
Test #51:
score: 0
Accepted
time: 4674ms
memory: 11460kb
Test #52:
score: 0
Accepted
time: 4588ms
memory: 11284kb
Test #53:
score: 0
Accepted
time: 2628ms
memory: 10004kb
Test #54:
score: 0
Accepted
time: 5ms
memory: 3764kb
Test #55:
score: 0
Accepted
time: 235ms
memory: 4824kb
Test #56:
score: 0
Accepted
time: 28ms
memory: 4148kb
Test #57:
score: 0
Accepted
time: 20ms
memory: 6188kb
Test #58:
score: 0
Accepted
time: 41ms
memory: 6168kb
Test #59:
score: 0
Accepted
time: 282ms
memory: 5260kb
Test #60:
score: 0
Accepted
time: 152ms
memory: 4640kb
Test #61:
score: 0
Accepted
time: 3ms
memory: 3848kb
Test #62:
score: 0
Accepted
time: 160ms
memory: 4644kb
Test #63:
score: 0
Accepted
time: 796ms
memory: 6252kb
Test #64:
score: 0
Accepted
time: 542ms
memory: 5556kb
Test #65:
score: 0
Accepted
time: 5355ms
memory: 10696kb
Test #66:
score: 0
Accepted
time: 1ms
memory: 3628kb