QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56051#2432. Go with the Flowcaptured#TL 11673ms13480kbC++175.0kb2022-10-16 17:51:092022-10-16 17:51:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-16 17:51:11]
  • 评测
  • 测评结果:TL
  • 用时:11673ms
  • 内存:13480kb
  • [2022-10-16 17:51:09]
  • 提交

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