CODE FESTIVAL 2016 Tournament Round 3 (Parallel)

Submission #1291482

Source codeソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 58;


template< class T >
std::vector< int > slideMaximum(const std::vector< T > &a, int k)
{
  int n = a.size();
  std::deque< int > deq;
  std::vector< int > res;
  for(int i = 0; i < n; i++) {
    while(deq.size() && a[deq.back()] <= a[i]) deq.pop_back();
    deq.push_back(i);
    res.push_back(deq.front());
    if(i - k + 1 >= 0) {
      if(deq.front() == i - k + 1) deq.pop_front();
    }
  }
  return res;
}


int main()
{
  int64 N, M, K, A[100000];

  cin >> N >> M >> K;
  for(int i = 0; i < N; i++) cin >> A[i];
  // dp[k][idx] := dp[k-1][j(idx-j<M)]+A_idx*k

  vector< int64 > dp1(N, 0);
  for(int i = 0; i < N; i++) dp1[i] = A[i];

  for(int i = 2; i <= K; i++) {
    vector< int64 > dp2(N, 0);
    auto dp = slideMaximum(dp1, M);
    for(int j = i - 1; j < N; j++) {
      dp2[j] = max(dp2[j], dp1[dp[j - 1]] + i * A[j]);
    }
    dp1.swap(dp2);
  }
  cout << *max_element(begin(dp1), end(dp1)) << endl;
}

Submission

Task問題 A - ストラックアウト / Struck Out
User nameユーザ名 ei1333
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 1065 Byte
File nameファイル名
Exec time実行時間 634 ms
Memory usageメモリ使用量 3552 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt,sample_3.txt
subtask1 100 / 100 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 200 / 200 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 300 / 300 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 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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 AC 1 ms 256 KB
subtask_1_2.txt AC 58 ms 648 KB
subtask_1_3.txt AC 591 ms 3552 KB
subtask_1_4.txt AC 6 ms 384 KB
subtask_1_5.txt AC 48 ms 3536 KB
subtask_1_6.txt AC 2 ms 256 KB
subtask_1_7.txt AC 225 ms 3544 KB
subtask_1_8.txt AC 594 ms 3544 KB
subtask_1_9.txt AC 3 ms 256 KB
subtask_2_1.txt AC 1 ms 256 KB
subtask_2_2.txt AC 1 ms 256 KB
subtask_2_3.txt AC 1 ms 256 KB
subtask_2_4.txt AC 1 ms 256 KB
subtask_2_5.txt AC 1 ms 256 KB
subtask_2_6.txt AC 1 ms 256 KB
subtask_2_7.txt AC 1 ms 256 KB
subtask_2_8.txt AC 1 ms 256 KB
subtask_2_9.txt AC 1 ms 256 KB
subtask_3_1.txt AC 96 ms 3552 KB
subtask_3_2.txt AC 96 ms 3544 KB
subtask_3_3.txt AC 93 ms 3552 KB
subtask_3_4.txt AC 77 ms 3016 KB
subtask_3_5.txt AC 6 ms 384 KB
subtask_3_6.txt AC 69 ms 3552 KB
subtask_3_7.txt AC 95 ms 3552 KB
subtask_3_8.txt AC 10 ms 640 KB
subtask_3_9.txt AC 98 ms 3552 KB
subtask_4_1.txt AC 603 ms 3552 KB
subtask_4_10.txt AC 320 ms 3552 KB
subtask_4_11.txt AC 634 ms 3552 KB
subtask_4_12.txt AC 632 ms 3552 KB
subtask_4_13.txt AC 626 ms 3544 KB
subtask_4_2.txt AC 619 ms 3552 KB
subtask_4_3.txt AC 598 ms 3544 KB
subtask_4_4.txt AC 601 ms 3544 KB
subtask_4_5.txt AC 513 ms 3552 KB
subtask_4_6.txt AC 83 ms 3552 KB
subtask_4_7.txt AC 344 ms 3552 KB
subtask_4_8.txt AC 591 ms 3520 KB
subtask_4_9.txt AC 288 ms 3544 KB