QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56052#2432. Go with the Flowcaptured#AC ✓5355ms12176kbC++175.2kb2022-10-16 17:58:102022-10-16 17:58: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:58:11]
  • 评测
  • 测评结果:AC
  • 用时:5355ms
  • 内存:12176kb
  • [2022-10-16 17:58:10]
  • 提交

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