제출 #1129915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129915		alosza	Candies (JOI18_candies)	C++20	8 / 100	5093 ms	4164 KiB

candies

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int n2 = (n+1)/2;
    vector<int> candies(n);
    for(int i = 0; i < n; i++)
    {
        cin >> candies[i];
    }
    // vector<vector<ll>> dp(n+1); //index, k
    vector<vector<ll>> lastcols(2);
    vector<ll> newcol(n2+1);
    // for(int i = 0; i < n+1; i++)
    // {
    //     dp[i] = vector<ll>(n2+1);
    //     if(i == 1)
    //     {
    //         for(int k = 1; k < n2+1; k++)
    //         {
    //             dp[i][k] = candies[0];
    //         }
    //     }
    // }
    lastcols[0] = vector<ll>(n2+1);
    lastcols[1] = vector<ll>(n2+1);
    lastcols[1][1] = candies[0];
    // for(int i = 2; i < n+1; i++)
    // {
    //     for(int k = 1; k < n2+1; k++)
    //     {
    //         if(2*(k-1) < i) dp[i][k] = max(dp[i-1][k], dp[i-2][k-1] + candies[i-1]);
    //     }
    // }
    for(int i = 2; i < n+1; i++)
    {
        newcol = vector<ll>(n2+1);
        for(int k = 1; k < n2+1; k++)
        {
            if(2*(k-1) < i) newcol[k] = max(lastcols[1][k], lastcols[0][k-1] + candies[i-1]);
        }
        lastcols[0] = lastcols[1];
        lastcols[1] = newcol;
    }

    // for(int k = 1; k < n2+1; k++)
    // {
    //     cout << dp[n][k] << "\n";
    // }

    for(int k = 1; k < n2+1; k++)
    {
        cout << lastcols[1][k] << "\n";
    }

    return 0;
}

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