Submission #997945


Source Code Expand

#ifndef KOMAKI_LOCAL
#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

std::string dbgDelim(int &i){ return (i++ == 0 ? "" : ", "); }
#define dbgEmbrace(exp) { int i = 0; os << "{"; { exp; } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> v);
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q);
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE> void dbgDeploy(std::ostream &os, TUPLE tuple){}
template <int INDEX, class TUPLE, class H, class ...Ts> void dbgDeploy(std::ostream &os, TUPLE t)
{ os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t); dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t); }
template <class T, class K> void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim)
{ os << "(" << p.first << delim << p.second << ")"; }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, std::tuple<Ts...> t)
{ os << "("; dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> p)
{ dbgDeploy(os, p, ", "); return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> v)
{ dbgEmbrace( for(T t: v){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> s)
{ dbgEmbrace( for(T t: s){ os << dbgDelim(i) << t; }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.front(); }); }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> q)
{ dbgEmbrace( for(; q.size(); q.pop()){ os << dbgDelim(i) << q.top();   }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> mp)
{ dbgEmbrace( for(auto p: mp){ os << dbgDelim(i); dbgDeploy(os, p, "->"); }); }
#define DBG_OUT std::cerr
#define DBG_OVERLOAD(_1, _2, _3, _4, _5, _6, macro_name, ...) macro_name
#define DBG_LINE() { char s[99]; sprintf(s, "line:%3d | ", __LINE__); DBG_OUT << s; }
#define DBG_OUTPUT(v) { DBG_OUT << (#v) << "=" << (v); }
#define DBG1(v, ...) { DBG_OUTPUT(v); }
#define DBG2(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG1(__VA_ARGS__); }
#define DBG3(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG2(__VA_ARGS__); }
#define DBG4(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG3(__VA_ARGS__); }
#define DBG5(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG4(__VA_ARGS__); }
#define DBG6(v, ...) { DBG_OUTPUT(v); DBG_OUT << ", "; DBG5(__VA_ARGS__); }

#define DEBUG0() { DBG_LINE(); DBG_OUT << std::endl; }
#define DEBUG(...)                                                      \
  {                                                                     \
    DBG_LINE();                                                         \
    DBG_OVERLOAD(__VA_ARGS__, DBG6, DBG5, DBG4, DBG3, DBG2, DBG1)(__VA_ARGS__); \
    DBG_OUT << std::endl;                                               \
  }


const i64 MAX = 100500;
i64 dp[2][MAX];
i64 a[MAX];

int main()
{
  i64 n, m, k;
  cin >> n >> m >> k;
  rep(i, n) cin >> a[i + 1];

  rep(i, n) dp[0][i] = 0;
  rep(step, k){
    i64 *cur = dp[step % 2];
    i64 *nex = dp[1 - step % 2];

    i64 ans = 0;
    i64 v_index = 0;
    vector<pair<i64, i64>> v;
    for(int i = step + 1; i <= n; ++i){
      while(v_index < sz(v) && v.back().second <= cur[i - 1]){
        v.pop_back();
      }
      v.push_back(make_pair(i, cur[i - 1]));
      if(m < i - v[v_index].first) ++v_index;
      nex[i] = v[v_index].second + (step + 1) * a[i];
      ans = max(ans, nex[i]);
    }
    if(step + 1 == k) cout << ans << endl;
  }
}

Submission Info

Submission Time
Task A - Struck Out
User Komaki
Language C++14 (GCC 5.4.1)
Score 600
Code Size 4634 Byte
Status WA
Exec Time 402 ms
Memory 4072 KB

Judge Result

Set Name Sample subtask1 subtask2 subtask3 All
Score / Max Score 0 / 0 100 / 100 200 / 200 300 / 300 0 / 100
Status
AC × 3
AC × 10
AC × 12
AC × 21
AC × 38
WA × 5
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, 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 3 ms 256 KB
sample_2.txt AC 3 ms 256 KB
sample_3.txt AC 3 ms 256 KB
subtask_1_1.txt AC 3 ms 256 KB
subtask_1_2.txt AC 38 ms 512 KB
subtask_1_3.txt AC 381 ms 2560 KB
subtask_1_4.txt AC 6 ms 384 KB
subtask_1_5.txt AC 49 ms 2560 KB
subtask_1_6.txt AC 3 ms 256 KB
subtask_1_7.txt AC 161 ms 2560 KB
subtask_1_8.txt AC 383 ms 2560 KB
subtask_1_9.txt AC 3 ms 256 KB
subtask_2_1.txt AC 3 ms 256 KB
subtask_2_2.txt AC 3 ms 256 KB
subtask_2_3.txt AC 3 ms 256 KB
subtask_2_4.txt AC 3 ms 256 KB
subtask_2_5.txt AC 3 ms 256 KB
subtask_2_6.txt AC 3 ms 256 KB
subtask_2_7.txt AC 3 ms 256 KB
subtask_2_8.txt AC 3 ms 256 KB
subtask_2_9.txt AC 3 ms 256 KB
subtask_3_1.txt AC 77 ms 2560 KB
subtask_3_2.txt AC 77 ms 2560 KB
subtask_3_3.txt AC 76 ms 2560 KB
subtask_3_4.txt AC 63 ms 2176 KB
subtask_3_5.txt AC 6 ms 384 KB
subtask_3_6.txt AC 61 ms 2560 KB
subtask_3_7.txt AC 78 ms 2560 KB
subtask_3_8.txt AC 10 ms 512 KB
subtask_3_9.txt AC 78 ms 2560 KB
subtask_4_1.txt AC 397 ms 2560 KB
subtask_4_10.txt WA 351 ms 4072 KB
subtask_4_11.txt WA 402 ms 2944 KB
subtask_4_12.txt WA 395 ms 2816 KB
subtask_4_13.txt WA 390 ms 2688 KB
subtask_4_2.txt WA 384 ms 2560 KB
subtask_4_3.txt AC 382 ms 2560 KB
subtask_4_4.txt AC 384 ms 2560 KB
subtask_4_5.txt AC 331 ms 2560 KB
subtask_4_6.txt AC 69 ms 2560 KB
subtask_4_7.txt AC 223 ms 2560 KB
subtask_4_8.txt AC 377 ms 2560 KB
subtask_4_9.txt AC 193 ms 2560 KB