제출 #245809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
245809		RealSuperman1	Candies (JOI18_candies)	C++17	8 / 100	29 ms	16384 KiB

candies

//#pragma comment(linker, "\stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcount,abm,mmx,avx,avx2,tune=native")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;
using namespace __gnu_pbds;

typedef
tree<
	ll,
	null_type,
	less_equal<ll>,
	rb_tree_tag,
	tree_order_statistics_node_update>
	ordered_set;
	

const int N = 2e3 + 10;
const int mod = 1e9 + 7;


ll n, a[N], dp[N][N];


int main() {
	ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
// 	freopen("input.txt", "r", stdin);
// 	freopen("input.in", "r", stdin);
// 	freopen("input.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        dp[i][1] = max(dp[i - 1][1], a[i]);
    ll lim = (n + 1) / 2;
    for (int j = 2; j <= lim; j++) {
        for (int i = 2 * j - 1; i <= n; i++)
            dp[i][j] = max(dp[i - 1][j], dp[i - 2][j - 1] + a[i]);
    }
    for (int j = 1; j <= lim; j++)
        cout << dp[n][j] << "\n";
}

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