Submission #1042124

---

Source Code Expand

/// In the name of God
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define X first
#define Y second
#define all(o) o.begin(), o.end()
#define IOS ios::sync_with_stdio(0), cin.tie(0)
pii gg(vi v){
    sort(all(v), greater<int>());
    int sum = 0, cnt = 0;
    for(int i=0; i<v.size(); i++){
        if(v[i] >= 0){
            sum += v[i];
            cnt++;
        }
    }
    int ans[2];
    ans[cnt % 2] = sum;
    int oth = 1 ^ (cnt % 2);
    if(cnt == v.size())
        ans[oth] = sum - v[cnt - 1];
    else{
        if(cnt - 1 >= 0) ans[oth] = max(sum + v[cnt], sum - v[cnt - 1]);
        else ans[oth] = sum + v[cnt];
    }
    return {ans[0], ans[1]};
}
const int maxn = 2e5 + 10;
vi adj[maxn];
main(){
    int n, k;
    cin >> n >> k;
    for(int i=0; i<n; i++){
        int x;
        cin >> x;
        adj[i % k].push_back(x);
    }
    int ev = 0, od = 0;
    for(int i=0; i<k; i++){
        pii res = gg(adj[i]);
        ev += res.X, od += res.Y;
        cout << res.X << " " << res.Y << endl;
    }
    cout << max(od, ev) << endl;
}

Submission Info

Judge Result