제출 #1297072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297072		NotLinux	Peru (RMI20_peru)	C++20	컴파일 에러	0 ms	0 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()

typedef long long ll;

const ll inf = 1e18 + 7;
const ll mod = 1e9 + 7;

struct MinStack{
    stack<pair<ll,ll>>st;
    ll getmin(){
        return st.empty() ? inf : st.top().second;
    }
    void push(ll x){
        st.push({x , min(x , getmin())});
    }
    ll pop(){
        if(!st.empty()){
            ll x = st.top().first;
            st.pop();
            return x;
        }
        else return -1;
    }
    int getsz(){
        return sz(st);
    }
    void swap(MinStack &x){
        st.swap(x.st);
    }
};

struct MinDeque{
    MinStack s1 , s2 , s3;
    ll getmin(){
        return min(s1.getmin() , s2.getmin());
    }
    void push_front(ll x){
        s1.push(x);
    }
    void push_back(ll x){
        s2.push(x);
    }
    ll pop_front(){
        if(s1.getsz() == 0){
            int len = s2.getsz();
            for(int i = 0;i<len / 2;i++){
                s3.push(s2.pop());
            }
            while(s2.getsz()){
                s1.push(s2.pop());
            }
            while(s3.getsz()){
                s2.push(s3.pop());
            }
        }
        return s1.pop();
    }
    ll pop_back(){
        if(s2.getsz() == 0){
            int len = s1.getsz();
            for(int i = 0;i<len / 2;i++){
                s3.push(s1.pop());
            }
            while(s1.getsz()){
                s2.push(s1.pop());
            }
            while(s3.getsz()){
                s1.push(s3.pop());
            }
        }
        return s2.pop();
    }
};
int solve(int n, int k, int* arr){
    deque<pair<int,ll>>dq;// i , dp[prev] + arr[i]
    MinDeque mdq;

    ll dp[n];
    int maxi = 0;
    for(int i = 0;i<n;i++){
        dp[i] = arr[i] + dp[i-1];
        
        while(!dq.empty() and i - dq[0].first > k){
            dq.pop_front();
            mdq.pop_front();
        }
        while(!dq.empty() and arr[dq.back().first] < arr[i]){
            if(sz(dq) > 1)
                dp[i] = min(dp[i] , dq.back().second - arr[dq.back().first] + arr[i]);
            dq.pop_back();
            mdq.pop_back();
        }

        ll x = mdq.pop_front();
        dp[i] = min(dp[i] , mdq.getmin());

        if(!dq.empty()){
            dp[i] = min(dp[i] , arr[dq[0].first] + dp[max(0 , i-k)]);
        }
        else{
            dp[i] = min(dp[i] , arr[i] + dp[max(0 , i-k)]);
        }

        if(x != -1)mdq.push_front(x);

        // cout << i << " : ";for(auto itr : dq)cout << itr.first << "," << itr.second << "   ";cout << endl;
        maxi = max(maxi , arr[i]);
        if(i < k){
            dp[i] = min(dp[i] , (ll)maxi);
        }
        // cerr << "DP " << i << " : " << dp[i] << endl;
        // cout << endl;
        ll prevdp = 0;
        if(!dq.empty()){
            prevdp = dp[dq.back().first];
        }
        dq.push_back({i , prevdp + arr[i]});
        mdq.push_back(prevdp + arr[i]);
    }

    ll ans = 0 , kat = 1;
    for(int i = n-1;i>=0;i--){
        ans = (ans + dp[i] * kat % mod) % mod;
        kat = kat * 23 % mod;
    }
    return ans;
}

signed main(){
    int n,k;
    cin >> n >> k;
    int arr[n];
    for(int i = 0;i<n;i++)cin >> arr[i];
    cout << solve(n,k,arr) << endl;
}

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

/usr/bin/ld: /tmp/ccoFk65g.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc2F99VR.o:peru.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status