Submission #2936195


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(ll j=i;j<n;j++){
            dp[i][j] = sm.res[j-1]+v[j]*i;
        }
    }
    ll mx = 0;
    rep(i,n){
        mx = max(mx,dp[k][i]);
    }
    cout << mx << endl;
    return 0;
}

Submission Info

Submission Time
Task A - Struck Out
User mtsd
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1715 Byte
Status WA
Exec Time 636 ms
Memory 239024 KB

Judge Result

Set Name Sample subtask1 subtask2 subtask3 All
Score / Max Score 0 / 0 0 / 100 0 / 200 0 / 300 0 / 100
Status
AC × 3
AC × 2
WA × 8
AC × 5
WA × 7
AC × 5
WA × 16
AC × 9
WA × 37
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
subtask1 sample_2.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt
subtask3 sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt
All sample_1.txt, sample_2.txt, sample_3.txt, sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt, subtask_4_1.txt, subtask_4_10.txt, subtask_4_11.txt, subtask_4_12.txt, subtask_4_13.txt, subtask_4_2.txt, subtask_4_3.txt, subtask_4_4.txt, subtask_4_5.txt, subtask_4_6.txt, subtask_4_7.txt, subtask_4_8.txt, subtask_4_9.txt
Case Name Status Exec Time Memory
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
subtask_1_1.txt WA 1 ms 256 KB
subtask_1_2.txt AC 48 ms 24064 KB
subtask_1_3.txt WA 633 ms 239024 KB
subtask_1_4.txt WA 5 ms 1664 KB
subtask_1_5.txt WA 49 ms 7720 KB
subtask_1_6.txt WA 2 ms 512 KB
subtask_1_7.txt WA 237 ms 82224 KB
subtask_1_8.txt WA 633 ms 239024 KB
subtask_1_9.txt WA 3 ms 1408 KB
subtask_2_1.txt WA 1 ms 384 KB
subtask_2_2.txt AC 1 ms 256 KB
subtask_2_3.txt WA 1 ms 256 KB
subtask_2_4.txt AC 1 ms 256 KB
subtask_2_5.txt WA 1 ms 256 KB
subtask_2_6.txt WA 1 ms 256 KB
subtask_2_7.txt WA 1 ms 384 KB
subtask_2_8.txt WA 1 ms 384 KB
subtask_2_9.txt WA 1 ms 256 KB
subtask_3_1.txt WA 99 ms 27344 KB
subtask_3_2.txt WA 99 ms 27340 KB
subtask_3_3.txt WA 97 ms 26556 KB
subtask_3_4.txt WA 79 ms 21960 KB
subtask_3_5.txt WA 5 ms 1536 KB
subtask_3_6.txt WA 69 ms 15568 KB
subtask_3_7.txt WA 99 ms 27344 KB
subtask_3_8.txt WA 9 ms 2944 KB
subtask_3_9.txt WA 99 ms 27340 KB
subtask_4_1.txt WA 634 ms 239024 KB
subtask_4_10.txt WA 632 ms 239024 KB
subtask_4_11.txt WA 636 ms 239024 KB
subtask_4_12.txt WA 633 ms 239024 KB
subtask_4_13.txt WA 635 ms 239024 KB
subtask_4_2.txt WA 635 ms 239024 KB
subtask_4_3.txt WA 633 ms 239024 KB
subtask_4_4.txt WA 635 ms 239024 KB
subtask_4_5.txt WA 540 ms 202960 KB
subtask_4_6.txt WA 86 ms 21844 KB
subtask_4_7.txt WA 352 ms 127696 KB
subtask_4_8.txt WA 626 ms 235460 KB
subtask_4_9.txt WA 301 ms 107280 KB