fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int K, N, M;
  5. vector<string> words;
  6. int maxCnt=0;
  7.  
  8. void backtrack(int i, vector<int> &lines, int cnt, const vector<string> &w){
  9.     if(i == w.size()){
  10.         if(cnt > maxCnt) maxCnt = cnt;
  11.         return;
  12.     }
  13.     if(cnt + (w.size()-i) <= maxCnt) return;
  14.     for(int j=0; j<N; j++){
  15.         if(lines[j]==0){
  16.             lines[j] = w[i].size();
  17.             backtrack(i+1, lines, cnt+1, w);
  18.             lines[j] = 0;
  19.  
  20.             break;
  21.         }
  22.         else{
  23.             if(lines[j] + 1 + w[i].size() <= M){
  24.                 lines[j] += 1 + w[i].size();
  25.                 backtrack(i+1, lines, cnt+1, w);
  26.                 lines[j] -= 1 + w[i].size();
  27.             }
  28.         }
  29.     }
  30.     backtrack(i+1, lines, cnt, w);
  31. }
  32.  
  33. int main(){
  34.     ios::sync_with_stdio(false);
  35.     cin.tie(0);
  36.     cin>>K;
  37.     words.resize(K);
  38.     for(auto &s: words) cin>>s;
  39.     cin>>N>>M;
  40.     vector<string> valid;
  41.     for(auto &s: words) if((int)s.size() <= M) valid.push_back(s);
  42.     sort(valid.begin(), valid.end(), [&](const string &a, const string &b)->bool{
  43.         if(a.size() != b.size()) return a.size() > b.size();
  44.         return a < b;
  45.     });
  46.     vector<int> lines(N, 0);
  47.     backtrack(0, lines, 0, valid);
  48.     cout<<maxCnt;
  49. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5
1 1 1 34
1200
2 3 2 10
100 10 1
3 3 3 3
1 2 3
4 2 2 7
5 8
999 1 999 6
3
stdout
copy 
3
https://ideone.com/o32Kk6
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!