Submission #991322

#	Time	Username	Problem	Language	Result	Execution time	Memory
991322		muhammad	Feast (NOI19_feast)	C++17	0 / 100	584 ms	262144 KiB

feast

#include <bits/stdc++.h>
using namespace std ;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0) ;
  //  freopen("revegetate.in", "r", stdin);
  //  freopen("revegetate.out", "w", stdout);

  long long  n , k ;
  cin >> n >> k ;
  int p=0 , ne=0 , z =0 ;
  vector <int> ps ;
  int arn [n] ;
  vector <long long > po ;
  vector <int> neg ;
  //int ze ;
  vector <int> negsum ;
  int  nesum = 0   ;
  for (int i = 0 ; i < n ;i++ ) {
    cin >> arn[i] ;
    if (arn[i] > 0 ) {
        p++ ;
        ps.push_back(i) ;
        int pos =  arn[i] ;
        po.push_back(pos) ;
    }else if (arn[i] < 0 ) {
        ne++ ;
        int nega =arn[i] ;
        neg.push_back(nega) ;
    }else {
        z++ ;
    //     ze = 0 ;
    }
  }
  vector <vector<int>> all (p) ;

          long long  res = 0 ;
  for (int i = 1 ; i < n ; i++ ) {
    if (arn[i] > 0 && arn[i-1] > 0 ) {
        negsum.push_back(0) ;
    }else if (arn[i] < 0 && arn[i-1] > 0 ){
        nesum = arn[i] ;
        for (int j = i + 1 ; j < n ; j++ ) {
            if (arn[j] > 0 ) {
                negsum.push_back(nesum) ;
                i = j -1 ;
                break;
            }else if (arn[j] < 0 ) {
                nesum += arn[j] ;
            }else if (arn[j] == 0 ) {
                i = j - 1 ;
                break;
            }
        }
    }
  }
  /*for (int i = 0 ;i <  (int) negsum.size() ; i++   ) {
    cout << negsum[i] << " " ;
  }*/

  if (n == k ) {
    if (p == n || z == 0  ) {
        for (int i = 0 ; i < n ; i++ ) {
            res += arn[i] ;
        }
        cout << res << endl;
    }else {
        if (z >= 1 ) {
            for (int i = 0 ; i < p ; i++ ) {
               res += po[i] ;
            }
            cout << res << endl;
        }

        }
    }else if (n > k ) {
        long long dif = n - k ;
        if (ne == dif  ) {
            for (int i = 0 ; i < p ; i++ ) {
               res += po[i] ;
            }
            cout << res << endl;
        }else if (ne > dif && z == 0  ) {
            for (int i = 1 ; i < ne && neg[i] > neg[i-1]  ; i++ ) {
                swap (neg[i], neg[i-1]) ;
                for (int j =  i - 1 ; j > 0 && neg[j] > neg[j-1] ; j-- ) {
                    swap (neg[j],neg[j-1]) ;
                }
            }
            for (int i = 0 ; i < ne - dif ; i++ )  {
                res += neg[i] ;
            }
            for (int i = 0 ; i < p ; i++ ) {
                res += po[i] ;
            }
            cout << res << endl;
        }else if (z >= 1 && ne > dif ) {
            for (int i = 0 ; i < p ; i++ ) {
                res += po[i] ;
            }
            cout << res << endl;
        }else if (ne < dif ) {
    //        int wdif = dif - ne  ;
    /*
            sort (po.begin(), po.end()) ;
            int os = (int) negsum.size() ;
        if ( os > 0  ){
                sort (negsum.begin(), negsum.end()) ;

            for (int i = p-1 , j = 1 , o = (int) os - 1  ; i >=0 && o >= 0  ; i--, j++ ) {
                if (j <= k ) {
                    res += po[i] ;
                }else if (os > 0 ) {
                    if (po[i] + negsum[o] > 0 ) {
                        res += po[i] + negsum[o] ;
                    }else {
                        break;
                    }
                    o--;
                }
            }
            cout << res << endl;
        }else {
            for (int i = p-1 , j = 1; i >=0 ; i--, j++ ) {
                if (j <= k ) {
                    res += po[i] ;
                }else {
                    break;
                }
        }
            cout << res << endl;
          //  cout << os << endl;
        }
*/
       // vector <vector<int>> all (p) ;
        int sum = 0 ;
       //  cout << " 1" << endl;
       //  cout << p << " " << (int) ps.size() <<endl;
        for (int i = 0 ; i < p ; i++  ) {
       //     cout << "  ww  "  << ps[p-1] << endl;
            for (int j = ps[i] , jj = 1 ; j <= ps[p-1] /*&& jj <= p - k */   ; j++ ) {
                  if (i == 0 ) {
                      //cout << "www" << endl;
                     if (j == ps[i]) {
                            sum += arn[j] ;
                            all[i].push_back(sum) ; //cout << sum << endl;
                     }else if (j != ps[i] &&  arn[j] != 0 ) {
                        sum += arn[j] ;
                        if (j == ps[i+jj] ) {
                            all[i].push_back(sum) ;
                            jj++ ;
                           //cout << sum << endl;
                           }
                    }else if (arn[j]== 0) {
                        all[i].push_back(-1) ;
                        // cout << -1 << endl;
                        jj++;
                        for (int io = 0 ; io < p - jj + 1 ; io++  ) {
                            all[i].push_back(-1) ;
                            // cout << -1 << endl;
                        }
                        sum = 0 ;
                        break;
                    }

                    }else if ( i != 0  ) {
                        if (j == ps[i]) {
                            sum += arn[j] ;
                            all[i].push_back(sum) ;// cout << sum << endl;
                        }else if (j != ps[i] ) {
                            if (all[i-1][jj+1] != -1 && all[i-1][0] != -1 && all[i-1][1] != -1 &&   jj < (int) all[i-1].size () - 1 ) {
                                all[i].push_back(( all[i-1][jj+1] - ( all[i-1][0]   + (all[i-1][1]  -(all[i-1][0] + (arn[ps[i]]) ) )) ))     ;
                                sum+=  ( all[i-1][jj+1] - ( all[i-1][0]   + (all[i-1][1]  -(all[i-1][0] + (arn[ps[i]]) )))) ;
                              //  cout << sum << endl;
                                j = ps[i + jj ] ;
                                jj++ ;
                                //cout << "  **" << endl;
                            }else if (all[i-1][jj+1] == -1) {
                                sum += arn[j] ;
                                if (j == ps[i+jj] ) {
                                    all[i].push_back(sum) ;
                                    jj++ ;
                                  //  cout << sum << endl;
                                }else if (arn[j]== 0) {
                                    all[i].push_back(-1) ;
                                    //cout << -1 << endl;
                                    jj++;
                                    for (int io = 0 ; io < p - jj + 1 ; io++  ) {
                                        all[i].push_back(-1) ;
                                      //  cout << -1 << endl;
                                    }
                                    break;
                                }
                            }
                    }
            }
        }
            sum = 0 ;
        }
     //   long long  big , small ;
   /* for (int i = 0 ; i <= p - k  ; i++   ) {
        cout << "**** " << i << endl;

        small =  determine (i, all , k , p  ) ;
        cout << small << endl;
         if (i == 0 ) {
            big = small ;
         }else {
            if (small > big ) {
                big = small ;
            }
         }

    }*/

    }
/*cout << endl; cout << endl;
for (int o = 0 ; o < p ; o++ ) {
    for (int ii = 0 ; ii < (int) all[o].size() ; ii++   ) {
        cout << all[o][ii] <<endl;
    }
    cout << endl;
}*/
vector <vector<vector<int>>> full (p,vector<vector<int>> (p) ) ;
vector <vector<int>> ho (p , vector <int> (k , 0 ) ) ;
 int small = 0 ;
for (int i = p -1 , ii = 0 ; i >= 0 ; i-- , ii++ ) {
  //      cout << "***********" << endl;
    for (int j = ii  ; j >= 0   ; j--  ) {

        //   if (i<= p-2)            cout << small << endl;
        for (int ij = 0  , jj = j   ; ij <=  ii && ij < k  && ij <= ii - j   ; ij++  ) {
      //        cout << "i  " << i << "  j  " << j << "  ij   " << ij <<  endl;
            if (ij == 0 ) {
                if (j == 0  ) {
                    ho[i][0]++ ;
                }
                full[i][j].push_back( all[i][j] ) ;
                if (i == p-1) {
                    small = full[i][j][0] ;
                }else {
                   // cout << "here "  << full[i][j][0] << endl;
                    if (small < full[i][j][0]  ) {
                        small = full[i][j][0] ;
                    }
                 //   cout << "here " << endl;
                }
            }else {
                int ji = ij - 1 ;
       //         cout << "ij  " << ij << "  ji   " << ji << endl;
                int bb = 0 ;
                for (int no =i + 1 + j  ;  no < p ; no++  ) {
                        int oio = 0 ;
                    for (int on = 0 ; on < p - no ; on++ ) {
    //                        cout << "no  " << no << "  on  " << on << endl;
                        for (int ooo = 0 ; ooo < ji ; ooo++ ) {
                          oio +=   ho[no+on][ooo]  ;
                        }
          //              cout << "oio  " << oio << "    " <<  ho[no+on][1] << endl;
                      //  oio-- ;
                       // if (ji == 0 ) oio = 0 ;
                        if (ho[no+on][ji] != 0  ) {
                            for (int iio = oio ; iio < oio + ho[no+on][ji] ; iio++  ) {
                                if (j == 0 ) {
                                    ho[i][ij]++ ;
                                }
                                full[i][j].push_back(all[i][j] + full[no][on][iio] ) ;
                                if (small < all[i][j] + full[no][on][iio]  ) {
                                    small = all[i][j] + full[no][on][iio];
                                    }
     //        cout << "   " <<  all[i][j] << "  +  " <<   full[no][on][iio] << "  =  " << all[i][j] + full[no][on][iio] <<  endl;
                            }
                        }else {
                            if (on == 0 ) {
                                bb = 1 ;
                            }
                                break;
                        }

                    oio = 0 ;
                    }
                    if (bb == 1 ) {
                        break;
                    }
                }
                /*
                if (j == 0 ) {
                    for ( ; ij <= ii && ij < k ; ij++ ) {
                       for (int oo = 0 ; oo < ij (int) full[i+1+j][ij-1].size() ; oo++ ) {
                        full[i][j].push_back(all[i][j] + full[i+1][ij-1][oo] )  ;
                        if (small < full[i][j][oo]  ) {
                            small = full[i][j][oo] ;
                        }
                       }

                    }
                    break;
                }else {

                }*/

            }
        }
    }
}
    cout << small <<  endl;

}





    return 0 ;
 }

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:236:28: warning: unused variable 'jj' [-Wunused-variable]
  236 |         for (int ij = 0  , jj = j   ; ij <=  ii && ij < k  && ij <= ii - j   ; ij++  ) {
      |                            ^~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29