Submission #1258902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258902		StefanSebez	Homecoming (BOI18_homecoming)	C++20	0 / 100	1094 ms	12496 KiB

homecoming

#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=5010;
int n;
ll dp[2*N][2*N],a[2*N],b[2*N];
/*int Dist(int l,int r){
    if(l<=r) return r-l+1;
    return r+n-l+1;
}*/
long long solve(int n1, int K, int *A, int *B){
    n=n1;
    for(int i=0;i<n;i++) a[i]=A[i],b[i]=B[i];
    for(int i=n;i<2*n;i++) a[i]=a[i-n],b[i]=b[i-n];
    ll res=0;
    for(int l=0;l<2*n;l++){
        for(int r=l;r<2*n;r++){
            for(int i=l;i<=r;i++){
                if(i+K-1>r) break;
                ll sum=0,sum1=0;
                for(int j=l;j<=i;j++) sum+=a[j];
                for(int j=l;j<=i+K-1;j++) sum1+=b[j];
                for(int j=i+K;j<=r;j++){
                    dp[l][r]=max(dp[l][r],dp[j][r]+sum-sum1);
                }
            }
            /*for(int j=l;j!=r;j=(j+1)%n){
                sum+=a[j];sum1+=b[j];
                for(int i=(j+K)%n;i!=r;i++){
                    dp[l][r]=max(dp[l][r],dp[i][r]+sum-sum1);
                }
            }*/
            //res=max(res,dp[l][r]);
        }
    }
    for(int i=0;i<n;i++) res=max(res,dp[i][i+n-1]);
    /*for(int r=0;r<n;r++){
        for(int l=0;l<n;l++){
            if(Dist(l,r)<K) continue;
            ll sum=0,sum1=0;
            for(int j=l,ct=K-1;ct--;j=(j+1)%n) sum1+=B[j];
            for(int j=l;j!=r;j=(j+1)%n){
                sum+=A[j];sum1+=B[j];
                for(int i=(j+K)%n;i!=r;i++){
                    dp[l][r]=max(dp[l][r],dp[i][r]+sum-sum1);
                }
            }
            res=max(res,dp[l][r]);
        }
    }*/
    return res;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38