Submission #2936193

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

template <typename T> class SlideMin
{
public:
    vector<int> deq;
    vector<T> res;
    int n,k;
    SlideMin(vector<T> Array,int sz){
        n = (int)Array.size(), k = sz;
        deq.resize(n), res.resize(n);
        int s = 0, t = 0;
        rep(i,n){
            //iを追加した場合に添字deq[t-1]の値がa[i]以上のときdeqから削除されるまで採用されることはないので
            //最大値を取る場合は Array[deq[t-1]] <= Array[i] とする
            while(s < t && Array[deq[t-1]] <= Array[i]){
                t--;
            }
            deq[t++] = i;
                res[i] = Array[deq[s]];
                if(deq[s] == i-k+1){
                    s++;
                }
            
        }
    }
};

int main(){
    int n,k;
    ll m;
    cin >> n >> m >> k;
    vector<ll> v(n);
    rep(i,n){
        cin >> v[i];
    }
    vector<vector<ll> > dp(k+1,vector<ll>(n));
    dp[1] = v;
    for(ll i=2;i<=k;i++){
        SlideMin<ll> sm(dp[i-1],k);
        for(int j=0;j<n;j++){
            cout << sm.res[j] << " " ;
        }
        cout << endl;
        for(ll j=i;j<n;j++){
            dp[i][j] = sm.res[j-i]+v[j]*i;
        }
    }
    ll mx = 0;
    rep(i,n){
        mx = max(mx,dp[k][i]);
    }
    cout << mx << endl;
    return 0;
}

Submission Info

Judge Result