제출 #591264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591264		Drew_	휴가 (IOI14_holiday)	C++17	컴파일 에러	0 ms	0 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

using ll = long long;

bool flag = false;

struct Segtree
{
    int n;
    pair<ll, int> st[1 << 18];
    
    Segtree() {}
    Segtree(int n_) : n(n_) { fill(st, st + (1 << 18), mp(0, 0)); }

    inline void modify(int p, ll val)
    {
        const auto _modify = [&](const auto &self, int node, int l, int r) -> void
        {
            if (l > p || r < p)
                return;
            if (l == r)
            {
                st[node] = { val, val > 0 };
                return;
            }
            int mid = (l + r) >> 1;
            self(self, node << 1, l, mid);
            self(self, node << 1 | 1, mid+1, r);

            st[node].f1 = st[node << 1].f1 + st[node << 1 | 1].f1;
            st[node].s2 = st[node << 1].s2 + st[node << 1 | 1].s2;
        };
        _modify(_modify, 1, 0, n-1);
    }

    inline ll query(int x)
    {
        const auto _query = [&](const auto &self, int node, int l, int r) -> ll
        {
            if (flag) cerr << x << " " << node << " " << l << " " << r << " " << st[node].f1 << " " << st[node].s2 << '\n';

            if (x <= 0)
                return 0;
            if (l == r)
                return st[node].f1;

            int mid = (l + r) >> 1;
            if (x <= st[node << 1].s2)
                return self(self, node << 1, l, mid);
            x -= st[node << 1].s2;
            return st[node << 1].f1 + self(self, node << 1 | 1, mid+1, r);
        };
        return _query(_query, 1, 0, n-1);
    }
};

vector<ll> solve(vector<int> item, int D, int C)
{
    if (item.empty())
        return vector<ll>(D+1, 0);

    int N = (int)item.size();
    Segtree st(N);
    vector<ll> res(D+1);

    vector<int> id(N);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](const int &x, const int &y){
        return item[x] > item[y];
    });

    {
        vector<int> tmp(N);
        for (int i = 0; i < N; ++i)
            tmp[id[i]] = i;
        id = tmp;
    }

    const auto dnc = [&](const auto &self, int l, int r, int optL, int optR) -> void
    {
        if (l > r)
            return;
        int mid = (l + r) >> 1;

        ll optVal = -1;
        int optIdx = -1;

        // costs `C * i` stamina to get to that spot
        for (int i = optL; i <= optR && C*i <= mid; ++i)
        {
            st.modify(id[i], item[i]);
            ll val = st.query(mid - C*i);

            if (val > optVal)
            {
                optVal = val;
                optIdx = i;
            }
        }
        res[mid] = optVal;


        for (int i = optL; i <= min(mid, optR); ++i)
            st.modify(id[i], 0);
        self(self, l, mid-1, optL, optIdx);

        for (int i = optL; i < optIdx; ++i)
            st.modify(id[i], item[i]);
        self(self, mid+1, r, optIdx, optR);
    };
    dnc(dnc, 0, D, 0, N-1);

    return res;
}

ll findMaxAttraction(int n, int start, int d, int attraction[])
{
    vector<int> vl = { 0 }, vr;
    for (int i = start-1; i >= 0; --i)
        vl.pb(attraction[i]);
    for (int i = start; i < n; ++i)
        vr.pb(attraction[i]);

    ll res = 0;
    for (int rep = 0; rep < 2; ++rep)
    {
        vector<ll> L = solve(vl, d, 1);
        vector<ll> R = solve(vr, d, 2);

        for (int i = 0; i <= d; ++i)
            res = max(res, L[i] + R[d - i]);

        vl.swap(vr);
    }
    
    return res;
}

int main() {
    int n, start, d;
    int attraction[100000];
    int i, n_s;
    n_s = scanf("%d %d %d", &n, &start, &d);
    for (i = 0 ; i < n; ++i) {
    n_s = scanf("%d", &attraction[i]);
    }
    printf("%lld\n", findMaxAttraction(n, start, d,  attraction));
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'int main()':
holiday.cpp:149:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
  149 |     int i, n_s;
      |            ^~~
/usr/bin/ld: /tmp/ccZmU4Qg.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccyZ6Pf.o:holiday.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status