oj.uz

Submission #50147

# Submission time Handle Problem Language Result Execution time Memory
50147 2018-06-07T21:38:04 Z spencercompton Candies (JOI18_candies) C++17
8 / 100
 180 ms 35328 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 16124 KB Output is correct
2 Correct 75 ms 16272 KB Output is correct
3 Correct 63 ms 16360 KB Output is correct
4 Correct 61 ms 16360 KB Output is correct
5 Correct 68 ms 16360 KB Output is correct
6 Correct 86 ms 16456 KB Output is correct
7 Correct 64 ms 16456 KB Output is correct
8 Correct 76 ms 16456 KB Output is correct
9 Correct 72 ms 16480 KB Output is correct
10 Correct 67 ms 16480 KB Output is correct
11 Correct 69 ms 16480 KB Output is correct
12 Correct 66 ms 16480 KB Output is correct
13 Correct 66 ms 16572 KB Output is correct
14 Correct 66 ms 16572 KB Output is correct
15 Correct 64 ms 16572 KB Output is correct
16 Correct 63 ms 16572 KB Output is correct
17 Correct 67 ms 16588 KB Output is correct
18 Correct 69 ms 16588 KB Output is correct
19 Correct 70 ms 16588 KB Output is correct
20 Correct 70 ms 16588 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 16124 KB Output is correct
2 Correct 75 ms 16272 KB Output is correct
3 Correct 63 ms 16360 KB Output is correct
4 Correct 61 ms 16360 KB Output is correct
5 Correct 68 ms 16360 KB Output is correct
6 Correct 86 ms 16456 KB Output is correct
7 Correct 64 ms 16456 KB Output is correct
8 Correct 76 ms 16456 KB Output is correct
9 Correct 72 ms 16480 KB Output is correct
10 Correct 67 ms 16480 KB Output is correct
11 Correct 69 ms 16480 KB Output is correct
12 Correct 66 ms 16480 KB Output is correct
13 Correct 66 ms 16572 KB Output is correct
14 Correct 66 ms 16572 KB Output is correct
15 Correct 64 ms 16572 KB Output is correct
16 Correct 63 ms 16572 KB Output is correct
17 Correct 67 ms 16588 KB Output is correct
18 Correct 69 ms 16588 KB Output is correct
19 Correct 70 ms 16588 KB Output is correct
20 Correct 70 ms 16588 KB Output is correct
21 Runtime error 180 ms 35328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -