This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
int n , k ;
cin >> n >> k ;
int p=0 , ne=0 , z =0 ;
int arn [n] ;
vector <int> 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 ;
}
}
int 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 ) {
int dif = n - k ;
if (ne == dif ) {
for (int i = 0 ; i < p ; i++ ) {
res += po[i] ;
}
}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--;
}
}
}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 ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |