QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#56051 | #2432. Go with the Flow | captured# | TL | 11673ms | 13480kb | C++17 | 5.0kb | 2022-10-16 17:51:09 | 2022-10-16 17:51: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];
/*
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();
if(ans >= sz){
break;
}
for(int i=0;i<sz;i++){
dp[i].clear();
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: 2ms
memory: 3804kb
Test #2:
score: 0
Accepted
time: 2ms
memory: 3620kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 3784kb
Test #4:
score: 0
Accepted
time: 2ms
memory: 3652kb
Test #5:
score: 0
Accepted
time: 2ms
memory: 3656kb
Test #6:
score: 0
Accepted
time: 2ms
memory: 3712kb
Test #7:
score: 0
Accepted
time: 2ms
memory: 3640kb
Test #8:
score: 0
Accepted
time: 2ms
memory: 3576kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 3624kb
Test #10:
score: 0
Accepted
time: 2ms
memory: 3632kb
Test #11:
score: 0
Accepted
time: 2ms
memory: 3628kb
Test #12:
score: 0
Accepted
time: 2ms
memory: 3740kb
Test #13:
score: 0
Accepted
time: 35ms
memory: 4296kb
Test #14:
score: 0
Accepted
time: 39ms
memory: 4292kb
Test #15:
score: 0
Accepted
time: 38ms
memory: 4348kb
Test #16:
score: 0
Accepted
time: 815ms
memory: 5804kb
Test #17:
score: 0
Accepted
time: 709ms
memory: 5552kb
Test #18:
score: 0
Accepted
time: 710ms
memory: 5588kb
Test #19:
score: 0
Accepted
time: 32ms
memory: 4388kb
Test #20:
score: 0
Accepted
time: 1ms
memory: 3904kb
Test #21:
score: 0
Accepted
time: 3159ms
memory: 8544kb
Test #22:
score: 0
Accepted
time: 35ms
memory: 6120kb
Test #23:
score: 0
Accepted
time: 3ms
memory: 3964kb
Test #24:
score: 0
Accepted
time: 1ms
memory: 3848kb
Test #25:
score: 0
Accepted
time: 2185ms
memory: 7464kb
Test #26:
score: 0
Accepted
time: 2679ms
memory: 7716kb
Test #27:
score: 0
Accepted
time: 2766ms
memory: 7688kb
Test #28:
score: 0
Accepted
time: 543ms
memory: 5544kb
Test #29:
score: 0
Accepted
time: 675ms
memory: 5648kb
Test #30:
score: 0
Accepted
time: 656ms
memory: 5448kb
Test #31:
score: 0
Accepted
time: 6127ms
memory: 12464kb
Test #32:
score: 0
Accepted
time: 269ms
memory: 6556kb
Test #33:
score: 0
Accepted
time: 43ms
memory: 5508kb
Test #34:
score: 0
Accepted
time: 3ms
memory: 3736kb
Test #35:
score: 0
Accepted
time: 2ms
memory: 3716kb
Test #36:
score: 0
Accepted
time: 3560ms
memory: 8696kb
Test #37:
score: 0
Accepted
time: 6116ms
memory: 12384kb
Test #38:
score: 0
Accepted
time: 6517ms
memory: 13044kb
Test #39:
score: 0
Accepted
time: 9174ms
memory: 11616kb
Test #40:
score: 0
Accepted
time: 9899ms
memory: 12312kb
Test #41:
score: 0
Accepted
time: 10418ms
memory: 12156kb
Test #42:
score: 0
Accepted
time: 4878ms
memory: 12100kb
Test #43:
score: 0
Accepted
time: 6193ms
memory: 12684kb
Test #44:
score: 0
Accepted
time: 6909ms
memory: 12496kb
Test #45:
score: 0
Accepted
time: 11334ms
memory: 12396kb
Test #46:
score: 0
Accepted
time: 11109ms
memory: 11980kb
Test #47:
score: 0
Accepted
time: 11118ms
memory: 12256kb
Test #48:
score: 0
Accepted
time: 10505ms
memory: 11724kb
Test #49:
score: 0
Accepted
time: 11237ms
memory: 13480kb
Test #50:
score: 0
Accepted
time: 9758ms
memory: 12464kb
Test #51:
score: 0
Accepted
time: 11673ms
memory: 12168kb
Test #52:
score: 0
Accepted
time: 11416ms
memory: 12292kb
Test #53:
score: 0
Accepted
time: 5912ms
memory: 10216kb
Test #54:
score: 0
Accepted
time: 10ms
memory: 3964kb
Test #55:
score: 0
Accepted
time: 529ms
memory: 5096kb
Test #56:
score: 0
Accepted
time: 80ms
memory: 4180kb
Test #57:
score: 0
Accepted
time: 68ms
memory: 6584kb
Test #58:
score: 0
Accepted
time: 100ms
memory: 6916kb
Test #59:
score: 0
Accepted
time: 643ms
memory: 5356kb
Test #60:
score: 0
Accepted
time: 330ms
memory: 4756kb
Test #61:
score: 0
Accepted
time: 11ms
memory: 4148kb
Test #62:
score: 0
Accepted
time: 370ms
memory: 4604kb
Test #63:
score: 0
Accepted
time: 1836ms
memory: 6492kb
Test #64:
score: 0
Accepted
time: 1321ms
memory: 5876kb
Test #65:
score: -100
Time Limit Exceeded