Submission #989841

#	Time	Username	Problem	Language	Result	Execution time	Memory
989841		muhammad	Feast (NOI19_feast)	C++17	4 / 100	52 ms	9452 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 ;
  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++ ;
        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 ;
    }
  }
          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;
        }

    }

    }


    return 0 ;
 }

• Subtask 1: 4 / 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