Submission #1111390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111390		SuperVOI	Feast (NOI19_feast)	C++14	51 / 100	33 ms	62544 KiB

feast

#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define el '\n'
#define fu(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fd(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)
#define fa(x, a) for(auto x : a)
#define re(i, n) fu(i,0,n - 1)
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
#define pof pop_front
#define pob pop_back
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define MP make_pair
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define db double
#define ld long double
#define squr(a) 1LL * (a) * (a)

using namespace std;

const int maxn = 3e5;
const ll  lim  = 1e9;
const ll  inf  = 1e18;
const ll  mod  = 1e9 + 7; /// 1007050321
const ll  base = 33137;

template<class T1,class T2>
bool maximize(T1 &a,T2 b){
    if(a < b){
        a = b;
        return 1;
    }
    return 0;
}

template<class T1,class T2>
bool minimize(T1 &a,T2 b){
    if(a > b){
        a = b;
        return 1;
    }
    return 0;
}

template<class T1,class T2>
void Add(T1 &a,T2 b){
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
    return;
}

template<class T1>
void temp_compress(vector<T1> &a){
    sort(all(a));
    a.resize(unique(all(a)) - a.begin());
    return;
}

ll max(ll a,ll b){return (a > b ? a : b);}
ll min(ll a,ll b){return (a < b ? a : b);}
bool takeBit(ll th,ll n){return ((n >> th) & 1LL);}
ll gcd(ll a,ll b){return (__gcd(a, b));}

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch(). count());
#define rand rd

ll ran(ll lo,ll hi){
    return (lo + rand() % (hi - lo + 1));
}

//int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
//int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dx[3] = {1, 0, 0};
int dy[3] = {0, -1, 1};

int n,m;
ll a[maxn + 5];

bool check_sub1(){
    fu(i,1,n) if(a[i] < 0) return 0;
    return 1;
}

namespace sub1 {
    void solve(){
        ll sum = 0LL;
        fu(i,1,n) sum += a[i];
        cout<<sum;
        return;
    }
}

bool check_sub2(){
    int cnt = 0;
    fu(i,1,n) if(a[i] < 0) ++cnt;
    return (cnt == 1);
}

namespace sub2 {
    void solve(){
        int pos = 0;
        fu(i,1,n) if(a[i] < 0){
            pos = i;
            break;
        }
        ll sum1 = 0LL, sum2 = 0LL;
        fu(i,1,pos - 1) sum1 += a[i];
        fu(i,pos + 1,n) sum2 += a[i];
        if(m > 1) cout<<sum1 + sum2;
        else{
            ll sum = sum1 + sum2 + a[pos];
            cout<<max({sum, sum1, sum2});
        }
        return;
    }
}

bool check_sub3(){
    return (m == 1);
}

namespace sub3 {
    void solve(){
        ll res = 0LL, sum = 0LL;
        fu(i,1,n){
            sum += a[i];
            maximize(res, sum);
            maximize(sum, 0LL);
        }
        cout<<res;
        return;
    }
}

bool check_sub5(){
    return (n <= 300);
}

namespace sub5 {
    ll dp[305][305], pre[305];

    void solve(){
        fu(i,1,n) pre[i] = pre[i - 1] + a[i];
        memset(dp, -0x3f, sizeof dp);
        fu(i,0,n) dp[i][0] = 0LL;
        re(i, n) fu(j,0,min(i, m)){
            if(j < m) maximize(dp[i][j + 1], dp[i][j]);
            maximize(dp[i + 1][j], dp[i][j]);
            if(j < m) fu(k,i + 1,n) maximize(dp[k][j + 1], dp[i][j] + pre[k] - pre[i]);
        }
        // fu(i,1,n){
        //     cout<<"Position : "<<i<<el;
        //     fu(j,1,min(i, m)) cout<<dp[i][j]<<' ';
        //     cout<<el;
        // }
        cout<<dp[n][m];
        return;
    }
}

bool check_sub6(){
    return (n <= 2000);
}

namespace sub6 {
    ll dp[2005][2005], g[2005][2005];
    void solve(){
        fu(i,1,n) fu(j,1,m){
            dp[i][j] = dp[i - 1][j] + a[i];
            if(j) maximize(dp[i][j], g[i - 1][j - 1] + a[i]);
            g[i][j] = max(g[i - 1][j], dp[i][j]);
        }
        ll res = 0LL;
        fu(j,1,m) maximize(res, dp[n][j]); 
        cout<<res;
        return;
    }
}

void input(){
    cin>>n>>m;
    fu(i,1,n) cin>>a[i];
    return;
}

int main(){
    fast
    // freopen("feas.INP", "r", stdin);
    // freopen("feas.OUT", "w", stdout);
    // clock_t start = clock();

    input();
    if(check_sub1()) return sub1::solve(), 0;
    if(check_sub2()) return sub2::solve(), 0;
    if(check_sub3()) return sub3::solve(), 0;
    if(check_sub5()) return sub5::solve(), 0;
    if(check_sub6()) return sub6::solve(), 0;

    // cerr<<el<<"Time elapsed : "<<(clock() - start)<<el;
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29