Submission #1001721

---

Source Code Expand

    #include <bits/stdc++.h>
    using namespace std;
         
    typedef vector<int> VI;
    typedef vector<VI> VVI;
    typedef vector<string> VS;
    typedef pair<int, int> PII;
    typedef long long LL;
    typedef pair<LL, LL> PLL;
         
    #define ALL(a)  (a).begin(),(a).end()
    #define RALL(a) (a).rbegin(), (a).rend()
    #define PB push_back
    #define EB emplace_back
    #define MP make_pair
    #define SZ(a) int((a).size())
    #define SORT(c) sort((c).begin(),(c).end())
         
    #define FOR(i,a,b) for(int i=(a);i<(b);++i)
    #define REP(i,n)  FOR(i,0,n)
         
    #define FF first
    #define SS second
    template<class S, class T>
    istream& operator>>(istream& is, pair<S,T>& p){
      return is >> p.FF >> p.SS;
    }
         
    const double EPS = 1e-10;
    const double PI  = acos(-1.0);
    const LL MOD = 1e9+7;
         
         
    LL dp[310][100010];
    LL mx[310][100010];
     
    // 幅Wの窓で値pを追加した時の最大値
    void add(deque<PLL>& dq, PLL p, int W){
      while(!dq.empty() && dq.back().FF < p.FF)
    	dq.pop_back();
      dq.push_back(p);
      while(!dq.empty() && p.SS - dq.front().SS + 1 > W)
    	dq.pop_front();
    }
     
    int main(){
      cin.tie(0);
      ios_base::sync_with_stdio(false);
         
      LL N, M, K; cin >> N >> M >> K;
      vector<LL> xs(N);
      REP(i,N) cin >> xs[i];
      deque<PLL> dq;
      REP(i,N){
    	dp[1][i] = xs[i];
    	add(dq, MP(dp[1][i],i), M);
    	mx[1][i] = dq.front().FF;
      }
     
      for(LL i=2;i<=K;++i){
    	dq.clear();
    	for(int j=i-1;j<N;++j){
    	  LL nxt = mx[i-1][j-1] + i * xs[j];
    	  dp[i][j] = max(dp[i][j], nxt);
     
    	  add(dq, MP(dp[i][j],j), M);
    	  mx[i][j] = dq.front().FF;
    	}
      }

      LL ans = 0;
      REP(i,N) ans = max(ans, dp[K][i]);
      cout << ans << endl;
          
      return 0;
    }

Submission Info

Judge Result