| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1082636 |
2024-08-31T23:26:54 Z |
muhammad |
Feast (NOI19_feast) |
C++17 |
|
73 ms |
13616 KB |
#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 ;
vector<int> negativez ;
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()) ;
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 ;
}
}
if (p >= k) {
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/=2) {
int g = 0 , s =0;
for (int ii = hg ; ii < p-1;ii++ ) {
if (nn[ii].first <= 0 ) {
g = nn[ii].first ;
hg = ii ;
break;
}
}
for (int ii = hs ; ii < p ; ii++) {
if (pp[ii].first > 0 ) {
s = pp[ii].first ;
hs= ii ;
break;
}
}
if (g + s >= 0 ) {
int sg = nn[hg].second.second;
int sg1= nn[hg].second.first;
if (sg>sg1) {
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 < p-k ; 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 {
swap (sg,sg1);
pp[sg].first += pp[sg1].first + g ;
nn[hg].first = 1 ;
pp[sg].second.second = pp[sg1].second.second;
if (pp[sg1].second.second !=-1) {
nn[pp[sg1].second.second ].second.first= sg;
}
pp[sg1].first = -1 ;
for (int ii = sg ; ii < p-1 && ii < p-k ; 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;
if (sg < sg1) {
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 < p-k ; 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;
}
}
}else {
swap (sg,sg1) ;
nn[sg].first += nn[sg1].first + s ;
pp[hs].first = -1 ;
nn[sg].second.second = nn[sg1].second.second;
pp[nn[sg1].second.second ].second.first= sg;
nn[sg1].first = 1 ;
for (int ii = sg ; ii < p-2 && ii < p-k ; 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 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
13616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
12092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
9272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
13616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
