As932

numere2

Jan 20th, 2021
822
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. ifstream cin("numere2.in");
  8. ofstream cout("numere2.out");
  9.  
  10. const int nmax = 3e2;
  11. const int amax = 1e3;
  12.  
  13. int n;
  14. int a[nmax + 1];
  15. bool fq[nmax * amax + 1];
  16.  
  17. void read(){
  18.     cin >> n;
  19.  
  20.     for(int i = 1; i <= n; i++)
  21.         cin >> a[i];
  22. }
  23.  
  24. void solve(){
  25.     sort(a + 1, a + n + 1);
  26.  
  27.     int mx = 0;
  28.     for(int i = 1; i <= n; i++){
  29.         vector <int> nr;
  30.  
  31.         for(int j = 1; j <= mx; j++)
  32.             if(fq[j])
  33.                nr.push_back(j + a[i]);
  34.  
  35.         fq[a[i]] = 1;
  36.         mx = max(a[i], mx);
  37.         while(!nr.empty()){
  38.             fq[nr.back()] = 1;
  39.             mx = max(mx, nr.back());
  40.             nr.pop_back();
  41.         }
  42.     }
  43.  
  44.     int lg = 0, bst = 0;
  45.     for(int i = 1; i <= mx; i++)
  46.         if(fq[i])
  47.             lg++;
  48.         else {
  49.             bst = max(bst, lg);
  50.             lg = 0;
  51.         }
  52.  
  53.     bst = max(bst, lg);
  54.     cout <<bst;
  55. }
  56.  
  57. int main()
  58. {
  59.     read();
  60.     solve();
  61.  
  62.     return 0;
  63. }
  64.  
RAW Paste Data