結果
問題 | No.2566 美しい整数列 |
ユーザー | tonegawa |
提出日時 | 2023-12-03 13:37:37 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 5,644 bytes |
コンパイル時間 | 1,467 ms |
コンパイル使用メモリ | 148,180 KB |
実行使用メモリ | 22,052 KB |
最終ジャッジ日時 | 2024-09-26 22:09:26 |
合計ジャッジ時間 | 4,969 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 153 ms
22,016 KB |
testcase_05 | AC | 162 ms
22,016 KB |
testcase_06 | AC | 62 ms
9,368 KB |
testcase_07 | AC | 64 ms
9,492 KB |
testcase_08 | AC | 63 ms
9,496 KB |
testcase_09 | AC | 66 ms
9,496 KB |
testcase_10 | AC | 65 ms
9,496 KB |
testcase_11 | AC | 90 ms
12,440 KB |
testcase_12 | AC | 90 ms
12,568 KB |
testcase_13 | AC | 88 ms
12,436 KB |
testcase_14 | AC | 87 ms
12,532 KB |
testcase_15 | AC | 86 ms
12,568 KB |
testcase_16 | AC | 121 ms
21,948 KB |
testcase_17 | AC | 127 ms
22,048 KB |
testcase_18 | AC | 131 ms
22,052 KB |
testcase_19 | AC | 84 ms
15,656 KB |
testcase_20 | AC | 119 ms
20,708 KB |
testcase_21 | AC | 130 ms
21,132 KB |
testcase_22 | AC | 79 ms
14,668 KB |
testcase_23 | AC | 101 ms
19,256 KB |
ソースコード
#include <iostream> #include <string> #include <vector> #include <array> #include <tuple> #include <stack> #include <queue> #include <deque> #include <algorithm> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <bitset> #include <cmath> #include <functional> #include <cassert> #include <climits> #include <iomanip> #include <numeric> #include <memory> #include <random> #include <thread> #include <chrono> #define allof(obj) (obj).begin(), (obj).end() #define range(i, l, r) for(int i=l;i<r;i++) #define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end()) #define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S) #define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit)) #define bit_kth(i, k) ((i >> k)&1) #define bit_highest(i) (i?63-__builtin_clzll(i):-1) #define bit_lowest(i) (i?__builtin_ctzll(i):-1) #define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t)) using ll = long long; using ld = long double; using ul = uint64_t; using pi = std::pair<int, int>; using pl = std::pair<ll, ll>; using namespace std; template<typename F, typename S> std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){ dest << p.first << ' ' << p.second; return dest; } template<typename T> std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i<sz;i++){ int m = v[i].size(); for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' '); } return dest; } template<typename T> std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){ int sz = v.size(); if(sz==0) return dest; for(int i=0;i<sz-1;i++) dest << v[i] << ' '; dest << v[sz-1]; return dest; } template<typename T, size_t sz> std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){ if(sz==0) return dest; for(int i=0;i<sz-1;i++) dest << v[i] << ' '; dest << v[sz-1]; return dest; } template<typename T> std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){ for(auto itr=v.begin();itr!=v.end();){ dest << *itr; itr++; if(itr!=v.end()) dest << ' '; } return dest; } template<typename T, typename E> std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){ for(auto itr=v.begin();itr!=v.end();){ dest << '(' << itr->first << ", " << itr->second << ')'; itr++; if(itr!=v.end()) dest << '\n'; } return dest; } std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } template<typename T> vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);} template<typename T, typename... Tail> auto make_vec(size_t sz, Tail ...tail){ return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...)); } template<typename T> vector<T> read_vec(size_t sz){ std::vector<T> v(sz); for(int i=0;i<(int)sz;i++) std::cin >> v[i]; return v; } template<typename T, typename... Tail> auto read_vec(size_t sz, Tail ...tail){ auto v = std::vector<decltype(read_vec<T>(tail...))>(sz); for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...); return v; } long long max(long long a, int b){return std::max(a, (long long)b);} long long max(int a, long long b){return std::max((long long)a, b);} long long min(long long a, int b){return std::min(a, (long long)b);} long long min(int a, long long b){return std::min((long long)a, b);} long long modulo(long long a, long long m){a %= m; return a < 0 ? a + m : a;} void io_init(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); } template<typename Val> struct accumulate1d{ std::vector<Val> sum; accumulate1d(){} accumulate1d(const std::vector<Val> &v): sum(v){ for(int i = 1; i < v.size(); i++) sum[i] = sum[i - 1] + v[i]; } // [0, r)の和, 範囲外の部分は全て単位元 Val query(int r){ r = std::min(r, (int)sum.size()); if(r <= 0) return 0; return sum[r - 1]; } // [l, r)の和, 範囲外の部分は全て単位元 Val query(int l, int r){ l = std::max(l, 0); r = std::min(r, (int)sum.size()); if(r <= l) return 0; return (l == 0 ? sum[r - 1] : (sum[r - 1] - sum[l - 1])); } // [0, k]がx以上になる最小インデックス, ない場合はn int lower_bound(Val x){ return std::lower_bound(sum.begin(), sum.end(), x) - sum.begin(); } // [0, k]がxより大きくなる最小インデックス, ない場合はn int upper_bound(Val x){ return std::upper_bound(sum.begin(), sum.end(), x) - sum.begin(); } }; int main(){ io_init(); int n, m; std::cin >> n >> m; auto a = read_vec<ll>(n); auto b = read_vec<ll>(m); range(i, 0, n - 1) if(i >= b.size()) b.push_back(b[i % m]); auto c = read_vec<ll>(n); auto ac = accumulate1d<ll>(b); ll S = 0; range(i, 0, n) S += c[i]; map<ll, ll> mp; range(i, 0, n){ ll diff = ac.query(i); auto itr = mp.find(a[i] - diff); if(itr == mp.end()) mp.emplace(a[i] - diff, c[i]); else itr->second += c[i]; } ll ans = S; for(auto [_, s] : mp) ans = min(ans, S - s); std::cout << ans << '\n'; }