제출 #1315795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315795		olizarowskib	Candies (JOI18_candies)	C++20	100 / 100	308 ms	198828 KiB

candies

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ft first
#define sc second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int, int>
#define vi vector<int>
#define tii tuple<int, int, int>
#define tiii tuple<int, int, int, int>
#define tiiii tuple<int, int, int, int, int>
#define vpi vector<pi>
#define vtii vector<tii>
#define vtiii vector<tiii>

const int N = (1 << 20), MOD = 1e9 + 7, INF = int(1e12);

vi dp[N][4];
int arr[N];

int gt(int x, vi &a){
    if(x < 0) return 0;
    if(x >= int(a.size())) return -INF;
    return a[x];
}

void mrg(vi &x, vi &a, vi &b){
    int akt = 0;
    int l = 0, r = 0, n, m;
    for(auto &i : x){
        n = gt(l, a) - gt(l - 1, a); m = gt(r, b) - gt(r - 1, b);
        if(l == int(a.size()) && r == int(b.size())) break;
        if(n > m){
            akt += n;
            l++;
        }else{
            akt += m;
            r++;
        }
        i = max(i, akt);
    }
}

void rep(int u){
    for(int i = 0; i < 4; i++){
        while(!dp[u][i].empty() && dp[u][i].back() == 0) dp[u][i].pop_back();
    }
}

void rec(int u, int l, int r, int n){
    if(l > n || r < 1 || l > r) return;
    int dl = r - l + 1;
    for(int i = 0; i < 4; i++) dp[u][i].resize(dl);
    if(l == r){
        dp[u][3][0] = arr[l];
        rep(u);
        return;
    }
    rec(2 * u, l, (r + l) / 2, n);
    rec(2 * u + 1, (l + r) / 2 + 1, r, n);
    int x = 2 * u, y = 2 * u + 1;
    mrg(dp[u][0], dp[x][0], dp[y][1]);
    mrg(dp[u][0], dp[x][2], dp[y][0]);
    mrg(dp[u][1], dp[x][1], dp[y][1]);
    mrg(dp[u][1], dp[x][3], dp[y][0]);
    mrg(dp[u][2], dp[x][0], dp[y][3]);
    mrg(dp[u][2], dp[x][2], dp[y][2]);
    mrg(dp[u][3], dp[x][1], dp[y][3]);
    mrg(dp[u][3], dp[x][3], dp[y][2]);
    rep(u);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    rec(1, 1, n, n);
    for(int i = 0; i < (n + 1) / 2; i++) cout << dp[1][3][i] << "\n";
    return 0;
}

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