oj.uz

Submission #60845

# Submission time Handle Problem Language Result Execution time Memory
60845 2018-07-24T20:28:22 Z Benq Candies (JOI18_candies) C++11
8 / 100
 66 ms 32532 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N, A[2001];
ll dp[2001][2001];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    FOR(i,1,N+1) cin >> A[i];
    F0R(i,N+1) FOR(j,1,N+1) dp[i][j] = -INF;
    FOR(i,1,N+1) FOR(j,1,N+1) dp[i][j] = max(dp[i-1][j],(i>1?dp[i-2][j-1]+A[i]:dp[i-1][j-1]+A[i]));
    // cout << dp[3][2] << " " << dp[1][1] << "\n";
    FOR(j,1,(N+1)/2+1) {
        ll ans = 0;
        // FOR(i,1,N+1) cout << dp[i][j] << " ";
        FOR(i,1,N+1) ans = max(ans,dp[i][j]);
        cout << ans << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31736 KB Output is correct
2 Correct 56 ms 32008 KB Output is correct
3 Correct 55 ms 32008 KB Output is correct
4 Correct 55 ms 32008 KB Output is correct
5 Correct 58 ms 32008 KB Output is correct
6 Correct 54 ms 32032 KB Output is correct
7 Correct 49 ms 32052 KB Output is correct
8 Correct 44 ms 32128 KB Output is correct
9 Correct 66 ms 32148 KB Output is correct
10 Correct 57 ms 32360 KB Output is correct
11 Correct 50 ms 32360 KB Output is correct
12 Correct 61 ms 32360 KB Output is correct
13 Correct 47 ms 32360 KB Output is correct
14 Correct 62 ms 32360 KB Output is correct
15 Correct 61 ms 32360 KB Output is correct
16 Correct 52 ms 32360 KB Output is correct
17 Correct 55 ms 32532 KB Output is correct
18 Correct 52 ms 32532 KB Output is correct
19 Correct 45 ms 32532 KB Output is correct
20 Correct 51 ms 32532 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31736 KB Output is correct
2 Correct 56 ms 32008 KB Output is correct
3 Correct 55 ms 32008 KB Output is correct
4 Correct 55 ms 32008 KB Output is correct
5 Correct 58 ms 32008 KB Output is correct
6 Correct 54 ms 32032 KB Output is correct
7 Correct 49 ms 32052 KB Output is correct
8 Correct 44 ms 32128 KB Output is correct
9 Correct 66 ms 32148 KB Output is correct
10 Correct 57 ms 32360 KB Output is correct
11 Correct 50 ms 32360 KB Output is correct
12 Correct 61 ms 32360 KB Output is correct
13 Correct 47 ms 32360 KB Output is correct
14 Correct 62 ms 32360 KB Output is correct
15 Correct 61 ms 32360 KB Output is correct
16 Correct 52 ms 32360 KB Output is correct
17 Correct 55 ms 32532 KB Output is correct
18 Correct 52 ms 32532 KB Output is correct
19 Correct 45 ms 32532 KB Output is correct
20 Correct 51 ms 32532 KB Output is correct
21 Runtime error 4 ms 32532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -