QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56041#2432. Go with the Flowcaptured#WA 3ms3776kbC++175.1kb2022-10-16 17:31:292022-10-16 17:31:32

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:31:32]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3776kb
  • [2022-10-16 17:31:29]
  • 提交

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[2502];


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();
    }
//    ch;
    int ans = 0;
    int linelen = n;

    for(int len=minlen;len<=sum;len++){

        lines.clear();
        int curlen=0;
        string curstring = "";
        for(string s:arr){
            int deli = 0;
            if((int)curstring.size() > 0)deli=1;
            if(curstring == ""){
                curstring = s;
            }
            else if( deli+(int)curstring.size()+(int)s.size() > len ){
                lines.pb(curstring);
                curstring = s;
            }
            else{
                curstring += " "+s;
            }
//            deb(curstring);deb((int)lines.size());dnl;
        }
        if((int)curstring.size() > 0){
            lines.pb(curstring);
        }

//        deb(len);
//        dnl;
//        for(string st:lines){
//            deb(st);
//            dnl;
//        }
        int sz = (int)lines.size();
//        deb(sz);dnl;
        if( ans >= sz )break;

        for(int i=0;i<sz;i++){
            dp[i].resize(len+1,0);
        }
//        deb(sz);dnl;
        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]);
            }
        }
        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: 3ms
memory: 3776kb

Test #2:

score: 0
Accepted
time: 2ms
memory: 3776kb

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3704kb