| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 991322 |
2024-06-02T03:04:33 Z |
muhammad |
Feast (NOI19_feast) |
C++17 |
|
584 ms |
262144 KB |
#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 ;
vector <int> ps ;
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++ ;
ps.push_back(i) ;
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 ;
}
}
vector <vector<int>> all (p) ;
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;
}
*/
// vector <vector<int>> all (p) ;
int sum = 0 ;
// cout << " 1" << endl;
// cout << p << " " << (int) ps.size() <<endl;
for (int i = 0 ; i < p ; i++ ) {
// cout << " ww " << ps[p-1] << endl;
for (int j = ps[i] , jj = 1 ; j <= ps[p-1] /*&& jj <= p - k */ ; j++ ) {
if (i == 0 ) {
//cout << "www" << endl;
if (j == ps[i]) {
sum += arn[j] ;
all[i].push_back(sum) ; //cout << sum << endl;
}else if (j != ps[i] && arn[j] != 0 ) {
sum += arn[j] ;
if (j == ps[i+jj] ) {
all[i].push_back(sum) ;
jj++ ;
//cout << sum << endl;
}
}else if (arn[j]== 0) {
all[i].push_back(-1) ;
// cout << -1 << endl;
jj++;
for (int io = 0 ; io < p - jj + 1 ; io++ ) {
all[i].push_back(-1) ;
// cout << -1 << endl;
}
sum = 0 ;
break;
}
}else if ( i != 0 ) {
if (j == ps[i]) {
sum += arn[j] ;
all[i].push_back(sum) ;// cout << sum << endl;
}else if (j != ps[i] ) {
if (all[i-1][jj+1] != -1 && all[i-1][0] != -1 && all[i-1][1] != -1 && jj < (int) all[i-1].size () - 1 ) {
all[i].push_back(( all[i-1][jj+1] - ( all[i-1][0] + (all[i-1][1] -(all[i-1][0] + (arn[ps[i]]) ) )) )) ;
sum+= ( all[i-1][jj+1] - ( all[i-1][0] + (all[i-1][1] -(all[i-1][0] + (arn[ps[i]]) )))) ;
// cout << sum << endl;
j = ps[i + jj ] ;
jj++ ;
//cout << " **" << endl;
}else if (all[i-1][jj+1] == -1) {
sum += arn[j] ;
if (j == ps[i+jj] ) {
all[i].push_back(sum) ;
jj++ ;
// cout << sum << endl;
}else if (arn[j]== 0) {
all[i].push_back(-1) ;
//cout << -1 << endl;
jj++;
for (int io = 0 ; io < p - jj + 1 ; io++ ) {
all[i].push_back(-1) ;
// cout << -1 << endl;
}
break;
}
}
}
}
}
sum = 0 ;
}
// long long big , small ;
/* for (int i = 0 ; i <= p - k ; i++ ) {
cout << "**** " << i << endl;
small = determine (i, all , k , p ) ;
cout << small << endl;
if (i == 0 ) {
big = small ;
}else {
if (small > big ) {
big = small ;
}
}
}*/
}
/*cout << endl; cout << endl;
for (int o = 0 ; o < p ; o++ ) {
for (int ii = 0 ; ii < (int) all[o].size() ; ii++ ) {
cout << all[o][ii] <<endl;
}
cout << endl;
}*/
vector <vector<vector<int>>> full (p,vector<vector<int>> (p) ) ;
vector <vector<int>> ho (p , vector <int> (k , 0 ) ) ;
int small = 0 ;
for (int i = p -1 , ii = 0 ; i >= 0 ; i-- , ii++ ) {
// cout << "***********" << endl;
for (int j = ii ; j >= 0 ; j-- ) {
// if (i<= p-2) cout << small << endl;
for (int ij = 0 , jj = j ; ij <= ii && ij < k && ij <= ii - j ; ij++ ) {
// cout << "i " << i << " j " << j << " ij " << ij << endl;
if (ij == 0 ) {
if (j == 0 ) {
ho[i][0]++ ;
}
full[i][j].push_back( all[i][j] ) ;
if (i == p-1) {
small = full[i][j][0] ;
}else {
// cout << "here " << full[i][j][0] << endl;
if (small < full[i][j][0] ) {
small = full[i][j][0] ;
}
// cout << "here " << endl;
}
}else {
int ji = ij - 1 ;
// cout << "ij " << ij << " ji " << ji << endl;
int bb = 0 ;
for (int no =i + 1 + j ; no < p ; no++ ) {
int oio = 0 ;
for (int on = 0 ; on < p - no ; on++ ) {
// cout << "no " << no << " on " << on << endl;
for (int ooo = 0 ; ooo < ji ; ooo++ ) {
oio += ho[no+on][ooo] ;
}
// cout << "oio " << oio << " " << ho[no+on][1] << endl;
// oio-- ;
// if (ji == 0 ) oio = 0 ;
if (ho[no+on][ji] != 0 ) {
for (int iio = oio ; iio < oio + ho[no+on][ji] ; iio++ ) {
if (j == 0 ) {
ho[i][ij]++ ;
}
full[i][j].push_back(all[i][j] + full[no][on][iio] ) ;
if (small < all[i][j] + full[no][on][iio] ) {
small = all[i][j] + full[no][on][iio];
}
// cout << " " << all[i][j] << " + " << full[no][on][iio] << " = " << all[i][j] + full[no][on][iio] << endl;
}
}else {
if (on == 0 ) {
bb = 1 ;
}
break;
}
oio = 0 ;
}
if (bb == 1 ) {
break;
}
}
/*
if (j == 0 ) {
for ( ; ij <= ii && ij < k ; ij++ ) {
for (int oo = 0 ; oo < ij (int) full[i+1+j][ij-1].size() ; oo++ ) {
full[i][j].push_back(all[i][j] + full[i+1][ij-1][oo] ) ;
if (small < full[i][j][oo] ) {
small = full[i][j][oo] ;
}
}
}
break;
}else {
}*/
}
}
}
}
cout << small << endl;
}
return 0 ;
}
Compilation message
feast.cpp: In function 'int main()':
feast.cpp:236:28: warning: unused variable 'jj' [-Wunused-variable]
236 | for (int ij = 0 , jj = j ; ij <= ii && ij < k && ij <= ii - j ; ij++ ) {
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
555 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
404 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
584 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
555 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
