(200801) 코드포스

Codeforces materials usage license (v. 0.1) 에 따라 codeforces.com 의 문제임을 알립니다.

Original problem link: Problem - 1389B - Codeforces


Example

Input

4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9

Output

15
19
150
56


Common codes for Codeforces
#include <algorithm>
#include <array>
#include <cmath>
#include <functional> 
#include <iostream>
#include <memory>
#include <queue>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <vector>

namespace predefined {

#ifdef CODEFORCES_DEBUG
  constexpr bool kIsDebug = true;
#else
  constexpr bool kIsDebug = false;
#endif

enum class LogType {
  INFO,
  DEBUG
};

template <LogType Type, bool... Bools>
struct Log;

template <>
struct Log<LogType::INFO> {
  Log() {}
  ~Log() { std::cout << '\n'; }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, true>{
  Log() {}
  ~Log() { std::cout << '\n'; }

  void Open() {
    freopen("input.txt", "r", stdin);
  }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, false> {
  Log() {}
  ~Log() {}

  void Open() {}

  template <typename T>
  Log& operator<< (const T &t) { return *this; }
};

namespace solver {

using SolveFunc = std::function<void()>;

template<typename MultiRunner>
void Run(SolveFunc solve_func);

template<>
void Run<std::true_type>(SolveFunc solve_func) {
  int test_case;
  std::cin >> test_case;

  while (test_case--) {
    solve_func();
  }
}

template<>
void Run<std::false_type>(SolveFunc solve_func) {
  solve_func();
}

} // solver

template <bool MultiTest>
struct Solver {
  constexpr static bool condition = MultiTest | kIsDebug;
  typedef typename std::conditional<condition, std::true_type, std::false_type>::type run_type;

  explicit Solver(solver::SolveFunc solve_func) {
    solver::Run<run_type>(solve_func);
  }
};

template<typename T>
struct BoolMap {
  explicit BoolMap(const T &_true_value, const T &_false_value) 
    : true_value(_true_value),
      false_value(_false_value) {}

  const T true_value;
  const T false_value;

  const T inline GetValue(const bool bool_key) const {
    return bool_key ? true_value : false_value;  
  };
};

}  // predefined;

#define LOG_INFO predefined::Log<predefined::LogType::INFO>()
#define LOG_DEBUG predefined::Log<predefined::LogType::DEBUG, predefined::kIsDebug>()
#define LOG(LEVEL) LOG_##LEVEL
#define LABEL(variable_name) #variable_name << ": " << variable_name << " "

#define INIT_ANSWER(type, true_value, false_value) \
  const predefined::BoolMap<type> predefined_bool_map(true_value, false_value)
#define INIT_STRING_ANSWER(true_string, false_string) \
  INIT_ANSWER(std::string, true_string, false_string)
#define GET_ANSWER(bool_key) \
  predefined_bool_map.GetValue(bool_key)

#define INIT_CODEFORCES() \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(NULL); \
  LOG(DEBUG).Open();

1389B Memory limit exceeded

dp를 while로 바꾸면 통과 될 것 같네요.
문제 조건 중 Also, you can’t perform two or more moves to the left in a row.
이게 in a row 가 한번에란 뜻으로 쓰였는데… row라서 저는 그 position에서 왼쪽으로는 한번밖에 못간다로 봤었네요.

namespace {
using namespace std;

constexpr bool kMultiTestCase = true;
using Solver = predefined::Solver<kMultiTestCase>;

}  // unnamed namespace;

enum LeftMoveState {
  NOT_YET,
  IS_MOVED,
  STATE_MAX
};

void solve() {
  int n, k, z;

  cin >> n >> k >> z;

  vector<int> inputs(n);
  for(auto &input : inputs) cin >> input;

  vector<vector<vector<int>>> memory(
    n, vector<vector<int>>(
      k+1, vector<int>(STATE_MAX, -1)));
  
  auto dp = make_shared<unique_ptr<function<int(int, int, LeftMoveState)>>>();
  *dp = make_unique<function<int(int, int, LeftMoveState)>>(
    [&](int now, int count, LeftMoveState state)->int{
      int &ret = memory[now][count][state];
      if(ret != -1) return ret;

      const int move_count = now + 2 * count;
      if (move_count == k) {
        ret = inputs[now];
        return ret;
      }

      if (state == NOT_YET) {
        if(count < z) {
          ret = inputs[now] + (**dp)(now - 1, count + 1, IS_MOVED);
        }
        ret = max(ret, inputs[now] + (**dp)(now + 1, count, NOT_YET));
      } else if (state == IS_MOVED) {
        ret = inputs[now] + (**dp)(now + 1, count, NOT_YET);
      } else {
        LOG_DEBUG << "exception catched";
      }

      return ret;
    }
  );
  
  LOG_INFO << (**dp)(0, 0, IS_MOVED);
}

int main(int argc, char** argv) {
  INIT_CODEFORCES();

  Solver([](){solve();});

  return 0;
}

1389B

메모리 사용 최소화 하는 방법으로 풀어봤습니다.

namespace {
using namespace std;

constexpr bool kMultiTestCase = true;
using Solver = predefined::Solver<kMultiTestCase>;

}  // unnamed namespace;

void solve() {
  int n, k, z;

  cin >> n >> k >> z;

  vector<int> inputs(n);
  for(auto &input : inputs) cin >> input;

  vector<int> buffer(z + 1);
  int ans = 0;
  buffer[0] = inputs[0];
  for(int count = 1; count < z; ++count) {
    buffer[count] = inputs[0] * (count + 1) + inputs[1] * count;
    if (0 + 2 * count + 0 <= k) {
      ans = max(ans, buffer[count]);
    }
  }

  for (int now = 1; now < n; ++now) {
    buffer[0] = inputs[now] + buffer[0];
    if (now + 2 * 0 + 0 <= k) {
      ans = max(ans, buffer[0]);
    }

    if (0 < z) {
      buffer[1] = max(buffer[1], buffer[0] + inputs[now - 1]);
      if (now + 2 * 0 + 1 <= k) {
        ans = max(ans, buffer[1]);
      }
    }

    for (int count = 1; count <= z; ++count) {
      buffer[count] = max(inputs[now] + buffer[count - 1] + inputs[now - 1],
                          inputs[now] + buffer[count]);
      if (now + 2 * count + 0 <= k) {
        ans = max(ans, buffer[count]);
      }

      if (count < z) {
        buffer[count + 1] = max(buffer[count + 1], buffer[count] + inputs[now - 1]);
        if(now + 2 * count + 1 <= k) {
          ans = max(ans, buffer[count + 1]);
        }
      }
    }
  }
  
  LOG_INFO << ans;
}

int main(int argc, char** argv) {
  INIT_CODEFORCES();

  Solver([](){solve();});

  return 0;
}

Codeforces materials usage license (v. 0.1) 에 따라 codeforces.com 의 문제임을 알립니다.

Original problem link: Problem - 1383A - Codeforces


Example

Input

5
3
aab
bcc
4
cabc
abcb
3
abc
tsr
4
aabd
cccd
5
abcbd
bcdda

Output

2
-1
3
2
-1


Common codes for Codeforces
#include <algorithm>
#include <array>
#include <cmath>
#include <functional> 
#include <iostream>
#include <memory>
#include <queue>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <vector>

namespace predefined {

#ifdef CODEFORCES_DEBUG
  constexpr bool kIsDebug = true;
#else
  constexpr bool kIsDebug = false;
#endif

enum class LogType {
  INFO,
  DEBUG
};

template <LogType Type, bool... Bools>
struct Log;

template <>
struct Log<LogType::INFO> {
  Log() {}
  ~Log() { std::cout << '\n'; }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, true>{
  Log() {}
  ~Log() { std::cout << '\n'; }

  void Open() {
    freopen("input.txt", "r", stdin);
  }

  template <typename T>
  Log& operator<< (const T &t) {
    std::cout << t;
    return *this;
  }
};

template <>
struct Log<LogType::DEBUG, false> {
  Log() {}
  ~Log() {}

  void Open() {}

  template <typename T>
  Log& operator<< (const T &t) { return *this; }
};

namespace solver {

using SolveFunc = std::function<void()>;

template<typename MultiRunner>
void Run(SolveFunc solve_func);

template<>
void Run<std::true_type>(SolveFunc solve_func) {
  int test_case;
  std::cin >> test_case;

  while (test_case--) {
    solve_func();
  }
}

template<>
void Run<std::false_type>(SolveFunc solve_func) {
  solve_func();
}

} // solver

template <bool MultiTest>
struct Solver {
  constexpr static bool condition = MultiTest | kIsDebug;
  typedef typename std::conditional<condition, std::true_type, std::false_type>::type run_type;

  explicit Solver(solver::SolveFunc solve_func) {
    solver::Run<run_type>(solve_func);
  }
};

template<typename T>
struct BoolMap {
  explicit BoolMap(const T &_true_value, const T &_false_value) 
    : true_value(_true_value),
      false_value(_false_value) {}

  const T true_value;
  const T false_value;

  const T inline GetValue(const bool bool_key) const {
    return bool_key ? true_value : false_value;  
  };
};

}  // predefined;

#define LOG_INFO predefined::Log<predefined::LogType::INFO>()
#define LOG_DEBUG predefined::Log<predefined::LogType::DEBUG, predefined::kIsDebug>()
#define LOG(LEVEL) LOG_##LEVEL
#define LABEL(variable_name) #variable_name << ": " << variable_name << " "

#define INIT_ANSWER(type, true_value, false_value) \
  const predefined::BoolMap<type> predefined_bool_map(true_value, false_value)
#define INIT_STRING_ANSWER(true_string, false_string) \
  INIT_ANSWER(std::string, true_string, false_string)
#define GET_ANSWER(bool_key) \
  predefined_bool_map.GetValue(bool_key)

#define INIT_CODEFORCES() \
  std::ios::sync_with_stdio(false); \
  std::cin.tie(NULL); \
  LOG(DEBUG).Open();