Submission #1132571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132571		altern23	Table Tennis (info1cup20_tabletennis)	C++20	0 / 100	37 ms	26556 KiB

tabletennis

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define ld long double

template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
template <typename T>
ostream& operator << (ostream& os, multiset<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";
 
    return os;
}
 
ostream& operator << (ostream& os, pii x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";
 
    return os;
}

const ll MOD = 998244353;
const ll N = 2e5 + 5;
const ll INF = 2e18;

// modulo operations
void add(ll &a, ll b) { a = (a + b) % MOD; }
void sub(ll &a, ll b) { a -= b; while(a < 0) a += MOD; a %= MOD; }
void mul(ll &a, ll b) { a = (a * b) % MOD; }

ll expo(ll a, ll b) {
    ll ans = 1;
    while(b > 0){
        if(b & 1) mul(ans, a);
        mul(a, a);
        b /= 2;
    }

    return ans;
}

ll ask(vector<ll> &v){
    cout << "? ";
    for(auto i : v) cout << i << " ";
    cout << endl;
    ll x; cin >> x;
    return x;
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, k; cin >> n >> k;
        vector<ll>a(n + k + 5);
        for(int i = 1; i <= n + k; i++) cin >> a[i];
        vector<vector<pii>> dp(n + k + 5, vector<pii>(k + 5));
        for(int i = 1; i <= n + k + 1; i++){
            for(int j = 0; j <= k; j++){
                dp[i][j] = {-INF, INF};
            }
        }

        dp[n + k + 1][0] = {0, 0};

        for(int i = n + k; i >= 1; --i){
            for(int j = 0; j <= k; j++){
                // ambil
                if(abs(dp[i][j].fi - dp[i][j].sec) > abs(dp[i + 1][j].fi - dp[i + 1][j].sec - a[i])){
                    dp[i][j] = dp[i + 1][j];
                    if(dp[i][j].fi < dp[i][j].sec) dp[i][j].fi += a[i];
                    else dp[i][j].sec += a[i];
                }
                // skip
                if(j){
                    if(abs(dp[i][j].fi - dp[i][j].sec) > abs(dp[i + 1][j - 1].fi - dp[i + 1][j - 1].sec)){
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }

        vector<ll> v;
        ll curi = 1, curK = k;
        while(curi <= n + k){
            pii tmp = dp[curi + 1][curK];
            if(tmp.fi < tmp.sec) tmp.fi += a[curi];
            else tmp.sec += a[curi];
            if(dp[curi][curK] == tmp){
                v.push_back(a[curi]);
                curi++;
            }
            else{
                curi++, curK--;
            }
        }

        for(auto x : v) cout << x << " ";
        cout << "\n";
    }   

}
 
/*

*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 9
• Subtask 6: 0 / 14
• Subtask 7: 0 / 15
• Subtask 8: 0 / 13