Submission #1205684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205684		AIF_is_carving	Colouring a rectangle (eJOI19_colouring)	C++20	30 / 100	64 ms	17944 KiB

colouring

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL mod = 998244353;

void solve() {
    
    LL n, m; cin>>n>>m;
    vector<LL> a, b;
    LL sum = 0;
    for(LL i  =1; i<=n+m-1; i++){
        LL x; cin>>x;
        a.push_back(x);
        sum+= x;
    }

    for(LL i  =1; i<=n+m-1; i++){
        LL x; cin>>x;
        b.push_back(x);
        sum+=x;
    }

    if(n < m){
        swap(n, m);
        swap(a, b);
    }

    if(m == 1){
        LL ans = 0;
        for(int i = 0; i<n+m-1; i++){
            ans+= min(a[i], b[n+m-2 - i]);
        }

        cout<<ans<<"\n";
        return;
    }
    LL l = max(n, m);
    vector<LL> Ax, Bx;
    for(LL i = 1; i<= n - m; i++) Ax.push_back(0);
    for(LL i = 0; i<a.size(); i++) Ax.push_back(a[i]);

    for(LL i = 0; i<b.size(); i++) Bx.push_back(b[i]);
    for(LL i = 1; i<= n - m; i++) Bx.push_back(0);

    vector<LL> A, B;
    for(LL i = 0; i<Ax.size(); i++) if(i%2 == 0) A.push_back(Ax[i]);
    for(LL i = 0; i<Ax.size(); i++) {
        if(l%2 == 1){
            if(i%2 == 0) B.push_back(Bx[i]);
        }
        else if(i%2 == 1) B.push_back(Bx[i]);
    }
    
    if(A.size() < B.size()) swap(A, B);

            // for(auto x: A) cout<<x<<" ";
            // cout<<"\n";
            // for(auto x: B) cout<<x<<" ";
            // cout<<"\n";

            for(LL i = 0; i<A.size()/2; i++){
                A[i]+= A[A.size() - i - 1];
            }
            for(LL i = 0; i<B.size()/2; i++){
                B[i]+= B[B.size() - i - 1];
            }
            for(LL i = 1; i<=A.size()/2; i++){
                A[i]+= A[i-1];
            }
            for(LL i = 1; i<=B.size()/2; i++){
                B[i]+= B[i-1];
            }

            A.insert(A.begin(), 0);
            B.insert(B.begin(), 0);

            // for(auto x: A) cout<<x<<" ";
            // cout<<"\n";
            // for(auto x: B) cout<<x<<" ";
            // cout<<"\n";

            LL mex1 = 0;

            for(LL i = 0; i<=A.size()/2; i++){
                mex1 = max<LL>(mex1, A[i] + B[A.size()/2-i]);
            }

            //cout<<mex1<<"\n";

    //cout<<sum - mex<<"\n";

    A.clear();
    B.clear();

    for(LL i = 0; i<Ax.size(); i++) if(i%2 == 1) A.push_back(Ax[i]);
    for(LL i = 0; i<Ax.size(); i++) {
        if(l%2 == 1){
            if(i%2 == 1) B.push_back(Bx[i]);
        }
        else if(i%2 == 0) B.push_back(Bx[i]);
    }

            // for(auto x: A) cout<<x<<" ";
            // cout<<"\n";
            // for(auto x: B) cout<<x<<" ";
            // cout<<"\n";

            for(LL i = 0; i<A.size()/2; i++){
                A[i]+= A[A.size() - i - 1];
            }
            for(LL i = 0; i<B.size()/2; i++){
                B[i]+= B[B.size() - i - 1];
            }
            for(LL i = 1; i<=A.size()/2; i++){
                A[i]+= A[i-1];
            }
            for(LL i = 1; i<=B.size()/2; i++){
                B[i]+= B[i-1];
            }

            A.insert(A.begin(), 0);
            B.insert(B.begin(), 0);

            // for(auto x: A) cout<<x<<" ";
            // cout<<"\n";
            // for(auto x: B) cout<<x<<" ";
            // cout<<"\n";

            LL mex2 = 0;

            for(LL i = 0; i<=A.size()/2; i++){
                mex2 = max<LL>(mex2, A[i] + B[A.size()/2-i]);
            }

            //cout<<mex2<<"\n";


    cout<<sum - mex1 - mex2<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    LL T=1;
    //cin >> T;
    while (T--) solve();
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20