Submission #50147

#	Time	Username	Problem	Language	Result	Execution time	Memory
50147		spencercompton	Candies (JOI18_candies)	C++17	8 / 100	180 ms	35328 KiB

candies

#include<bits/stdc++.h>
using namespace std;
long long ar[200000];
int n;
long long dp[2000][1001];
long long inf = 200000000000000003LL;
long long go(int now, int rem){
    if(rem==0){
        return 0LL;
    }
    if(now>=n){
        return -inf;
    }
    if(dp[now][rem]>=-inf){
        return dp[now][rem];
    }
    long long ret = -inf;
    ret = max(ret,go(now+1,rem));
    ret = max(ret,go(now+2,rem-1)+ar[now]);
    dp[now][rem] = ret;
    return ret;
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i<n; i++){
        cin >> ar[i];
    }
    for(int a = 0; a<n; a++){
        for(int b = 0; b<=(n+1)/2; b++){
            dp[a][b] = -inf-2LL;
        }
    }
    vector<long long> ans;
    for(int i = 1; i<=(n+1)/2; i++){
        ans.push_back(go(0,i));
    }
    for(int i = 2; i<ans.size(); i++){
        assert((ans[i]-ans[i-1])<=(ans[i-1]-ans[i-2]));
    }
    for(int i = 0; i<ans.size(); i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:39:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 2; i<ans.size(); i++){
                    ~^~~~~~~~~~~
candies.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i<ans.size(); i++){
                    ~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 92