test/yukicoder/1211.test.cpp

• View this file on GitHub
• Last update: 2026-02-17 02:03:35+09:00
• Problem: https://yukicoder.me/problems/no/1211

Depends on

• functional graph (lib/graph/functional_graph.hpp)
• 重み付きグラフ (lib/graph/graph.hpp)
• lib/internal/internal_csr.hpp
• HL分解 (lib/tree/hld.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/1211
#include <cstdint>
#include <iostream>
#include <vector>
#include "graph/functional_graph.hpp"

int main(void) {
    int n, k;
    std::cin >> n >> k;
    std::vector<std::int64_t> a(n);
    for (auto &e : a) std::cin >> e;
    auto b = a;
    b.insert(b.begin(), 0);
    b.insert(b.end(), a.begin(), a.end());
    for (int i = 0; i < n * 2; ++i) b[i + 1] += b[i];
    std::int64_t l = 1, r = b[n] / k + 1;
    std::vector<int> to(n * 2 + 2, n * 2 + 1);
    while (r - l > 1) {
        std::int64_t m = (l + r) / 2;
        int idx = 0;
        for (int i = 0; i < n * 2; ++i) {
            while (idx < (int)b.size() && b[idx] - b[i] < m) ++idx;
            to[i] = idx;
        }
        functional_graph fg(to);
        auto v = fg.jump_all(k);
        bool f = false;
        for (int i = 0; i < n; ++i) {
            if (v[i] - i <= n) {
                f = true;
                break;
            }
        }
        (f ? l : r) = m;
    }
    std::cout << l << '\n';

    return 0;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/functional_graph.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	1	AC	2 ms	4 MB
g++	10	AC	2 ms	4 MB
g++	11	AC	2 ms	4 MB
g++	12	AC	2 ms	4 MB
g++	13	AC	2 ms	3 MB
g++	14	AC	239 ms	24 MB
g++	15	AC	534 ms	16 MB
g++	16	AC	365 ms	24 MB
g++	17	AC	476 ms	44 MB
g++	18	AC	48 ms	6 MB
g++	19	AC	319 ms	21 MB
g++	2	AC	3 ms	3 MB
g++	20	AC	40 ms	7 MB
g++	21	AC	65 ms	6 MB
g++	22	AC	51 ms	8 MB
g++	23	AC	250 ms	25 MB
g++	24	AC	280 ms	29 MB
g++	25	AC	153 ms	20 MB
g++	26	AC	14 ms	5 MB
g++	27	AC	377 ms	29 MB
g++	28	AC	155 ms	20 MB
g++	29	AC	400 ms	29 MB
g++	3	AC	2 ms	3 MB
g++	30	AC	257 ms	27 MB
g++	31	AC	359 ms	38 MB
g++	32	AC	146 ms	16 MB
g++	33	AC	419 ms	43 MB
g++	34	AC	477 ms	48 MB
g++	35	AC	471 ms	48 MB
g++	36	AC	459 ms	48 MB
g++	37	AC	471 ms	48 MB
g++	38	AC	466 ms	48 MB
g++	39	AC	508 ms	49 MB
g++	4	AC	3 ms	3 MB
g++	40	AC	509 ms	49 MB
g++	5	AC	3 ms	4 MB
g++	6	AC	2 ms	3 MB
g++	7	AC	2 ms	3 MB
g++	8	AC	2 ms	3 MB
g++	9	AC	2 ms	4 MB
g++	98_challenge01	AC	526 ms	21 MB
g++	sample1	AC	3 ms	3 MB
g++	sample2	AC	2 ms	3 MB

Back to top page