#include <bits/stdc++.h>
using namespace std ;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0) ;
// freopen("tallbarn.in", "r", stdin);
// freopen("tallbarn.out", "w", stdout);
int p=0 , n , k ;
cin >> n >> k ;
int answer = 0 ;
int all [n] ;
vector <pair<int,pair<int,int>>> pp ;
vector <pair<int,pair<int,int>>> nn ;
int neg = 0 ;
for (int i = 0 ; i < n ; i++ ) {
cin >> all[i] ;
if (all[i] > 0 ) {
p++ ;
pp.push_back( {all[i], {-1,-1} } ) ;
if (p>=2) {
pp[p-2].second.second = p-2 ;
pp[p-1].second.first = p-2 ;
nn.push_back({neg, {p-2,p-1} } ) ;
neg = 0 ;
}
}else if (p >=1 && all[i] <= 0 ) {
neg+= all[i] ;
}
}
//sort (pp.begin(),pp.end()) ;
if (p >= k) {
/*
for (int i = 0 ; i < p ; i++ ) {
if (pp[i].second.first!=-1) {
int sf = pp[i].second.first ;
nn[sf].second.second = i ;
}
if (pp[i].second.second!=-1) {
int sf = pp[i].second.second ;
nn[sf].second.first = i ;
}
}*/
// sort (nn.rbegin(),nn.rend()) ;
/*for (int i = 0 ; i < p-1;i++) {
int sf = nn[i].second.first;
pp[sf].second.second = i ;
sf = nn[i].second.second ;
pp[sf].second.first = i ;
}*/
int kk = p;
int hg=0,hs=0 ;
for (int i = kk ; i > k ; i--) {
int g = 0 , s =1;
for (int ii = 0 ; ii < p-1;ii++) {
if (ii ==0 ) { g = nn[ii].first; }
if ((nn[ii].first > g || g > 0) && nn[ii].first <= 0 ) {
g = nn[ii].first ;
hg= ii ;
}
}
// cout << "g " << g << endl;
for (int ii = 0 ; ii < p ; ii++) {
if (ii == 0 ) { s = pp[ii].first; }
if ((pp[ii].first < s || s < 0) && pp[ii].first > 0 ) {
s = pp[ii].first ;
hs= ii ;
}
}
// cout << "s " << s << endl;
if (g + s >= 0 ) {
int sg = nn[hg].second.second;
int sg1= nn[hg].second.first;
pp[sg].first += pp[sg1].first + g ;
nn[hg].first = 1 ;
pp[sg].second.first = pp[sg1].second.first;
if (pp[sg1].second.first !=-1) {
nn[pp[sg1].second.first ].second.second= sg;
}
pp[sg1].first = -1 ;
for (int ii = sg ; ii < p-1 ; ii++ ) {
if (pp[ii].first > pp[ii+1].first) {
swap (pp[ii],pp[ii+1]);
if ( pp[ii+1].second.first !=-1) {
nn[pp[ii+1].second.first].second.second = ii+1;
}
if ( pp[ii+1].second.second!=-1) {
nn[pp[ii+1].second.second].second.first = ii+1;
}
if (pp[ii].first != -1 ){
if ( pp[ii].second.first!=-1) {
nn[pp[ii].second.first].second.second = ii ;
}
if (pp[ii].second.second!=-1) {
nn[pp[ii].second.second].second.first = ii ;
}
}
}else {
break;
}
}
}else {
if (pp[hs].second.first == -1 || pp[hs].second.second == -1 ) {
pp[hs].first = -1;
if (pp[hs].second.first == -1 ) {
nn[pp[hs].second.second].first = 1 ;
pp[nn[pp[hs].second.second].second.second].second.first = -1 ;
}else {
nn[pp[hs].second.first].first = 1 ;
pp[nn[pp[hs].second.first].second.first].second.second = -1;
}
}else {
int sg = pp[hs].second.second;
int sg1= pp[hs].second.first;
nn[sg].first += nn[sg1].first + s ;
pp[hs].first = -1 ;
nn[sg].second.first = nn[sg1].second.first;
pp[nn[sg1].second.first ].second.second= sg;
nn[sg1].first = 1 ;
for (int ii = sg ; ii < p-2 ; ii++ ) {
if (nn[ii].first < nn[ii+1].first) {
swap (nn[ii],nn[ii+1]);
pp[nn[ii+1].second.first].second.second = ii+1;
pp[nn[ii+1].second.second].second.first = ii+1;
if (nn[ii].first !=1) {
pp[nn[ii].second.first].second.second = ii ;
pp[nn[ii].second.second].second.first = ii ;
}
}else {
break;
}
}
}
}
}
for (int i = 0 ; i < p ; i++ ) {
if ( pp[i].first!= -1 ) {
answer += pp[i].first ;
}
}
cout << answer << endl;
}else {
for (int i = 0 ; i < p ; i++ ) {
answer += pp[i].first ;
}
cout << answer << endl;
}
return 0 ;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1071 ms |
15412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1032 ms |
15412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1028 ms |
10292 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1071 ms |
15412 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
