QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#56041 | #2432. Go with the Flow | captured# | WA | 3ms | 3776kb | C++17 | 5.1kb | 2022-10-16 17:31:29 | 2022-10-16 17:31:32 |
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[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