| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1082471 |
2024-08-31T13:00:30 Z |
muhammad |
Feast (NOI19_feast) |
C++17 |
|
1000 ms |
13872 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) {
if (all[i]== 0) {
negativez.push_back(1);
}else {
negativez.push_back(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--) {
int g , s;
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;
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 {
sort (negativez.begin(),negativez.end());
for (int i = 0 ; i < p ; i++ ) {
answer += pp[i].first ;
}
int negative = (int) negativez.size() ;
if (negativez[negative-1] == 1 ) {
cout << answer << endl;
}else {
int kkk = k - p ;
for (int i = negative-1 ; i >= 0 && kkk > 0 ; i-- , kkk-- ) {
answer += negativez[i] ;
}
cout << answer << endl;
}
}/*
//cout << endl; cout << endl;
for (int i = 0 ; i < p ; i++) {
cout << pp[i].first << " " << pp[i].second.first << " " << pp[i].second.second<< endl;
if (i < p-1) {
cout << nn[i].first << " * " << nn[i].second.first << " * " << nn[i].second.second<< endl;
}
}*/
return 0 ;
}
/*
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
int n, k;
cin >> n >> k;
int a[n];
for (int &i : a) { cin >> i; }
auto solve_lambda = [&](ll lmb) {
pair<ll, ll> dp[n][2];
dp[0][0] = {0, 0};
dp[0][1] = {a[0] - lmb, 1};
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] =
max(make_pair(dp[i - 1][0].first + a[i] - lmb,
dp[i - 1][0].second + 1),
make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
}
return max(dp[n - 1][0], dp[n - 1][1]);
};
ll lo = 0;
ll hi = 1e18;
while (lo < hi) {
ll mid = (lo + hi + 1) / 2;
solve_lambda(mid).second >= k ? lo = mid : hi = mid - 1;
}
cout << solve_lambda(lo).first + lo * k << endl;
}*/
Compilation message
feast.cpp: In function 'int main()':
feast.cpp:81:19: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | if (g + s >= 0 ) {
| ~~^~~
feast.cpp:84:47: warning: 'g' may be used uninitialized in this function [-Wmaybe-uninitialized]
84 | pp[sg].first += pp[sg1].first + g ;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1008 ms |
13860 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1100 ms |
13872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1035 ms |
11316 KB |
Time limit exceeded |
| 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 |
Execution timed out |
1008 ms |
13860 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
