結果

問題 No.2566 美しい整数列
ユーザー uetaueta
提出日時 2023-12-02 15:54:56
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 180 ms / 2,000 ms
コード長 8,478 bytes
コンパイル時間 2,483 ms
コンパイル使用メモリ 165,392 KB
実行使用メモリ 30,292 KB
最終ジャッジ日時 2024-09-26 19:30:39
合計ジャッジ時間 6,939 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
11,768 KB
testcase_01 AC 4 ms
11,648 KB
testcase_02 AC 4 ms
11,648 KB
testcase_03 AC 4 ms
11,648 KB
testcase_04 AC 179 ms
30,164 KB
testcase_05 AC 180 ms
30,292 KB
testcase_06 AC 69 ms
17,792 KB
testcase_07 AC 69 ms
17,664 KB
testcase_08 AC 67 ms
17,708 KB
testcase_09 AC 69 ms
17,652 KB
testcase_10 AC 72 ms
17,664 KB
testcase_11 AC 97 ms
20,848 KB
testcase_12 AC 97 ms
20,856 KB
testcase_13 AC 103 ms
20,772 KB
testcase_14 AC 97 ms
20,824 KB
testcase_15 AC 102 ms
20,864 KB
testcase_16 AC 132 ms
29,312 KB
testcase_17 AC 136 ms
29,568 KB
testcase_18 AC 152 ms
29,696 KB
testcase_19 AC 92 ms
23,552 KB
testcase_20 AC 129 ms
28,272 KB
testcase_21 AC 136 ms
28,796 KB
testcase_22 AC 87 ms
22,476 KB
testcase_23 AC 113 ms
26,744 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cstdint>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define fore(i, a) for(auto &&i : a)
#define foreP(a, b, v) for(auto &&[a, b] : v)
#define foreP3(a, b, c, v) for(auto &&[a, b, c] : v)
#define fitr(itr, m) for(auto &&itr=m.begin();itr!=m.end();itr++)
#define ALL(v) (v).begin(),(v).end()
#define SUM(a) accumulate(ALL(a),0LL)
#define VC vector
#define TP tuple

using namespace std;
mt19937 engine(time(0));

using ll = long long;
using ld = long double;
constexpr long long mod = 998244353;
// constexpr long long mod = 1000000007;
// constexpr long long mod = 100000000000000003;
constexpr double PI=3.1415926535897932384626433832795028841971;
constexpr long long inf = INT_MAX;
constexpr long long infll = LONG_MAX;

int dx[8] = {1, 0,-1, 0, 1, 1,-1,-1};
int dy[8] = {0, 1, 0,-1, 1,-1, 1,-1 };

using Si =set<int>;using Sll =set<long long>;using Sc =set<char>;using Ss =set<string>;
using Mii = map<int,int>;using Msi = map<string,int>;using Mci = map<char,int>;using Mlli = map<long long,int>;
using P = pair<int, int>;using PL = pair<long long, long long>;
using V = vector<int>;using VL = vector<long long>;using Vc = vector<char>;using Vs = vector<string>;
using VP = vector<P>;using VPL = vector<P>;
using VV = vector<vector<int>>;using VVL = vector<vector<long long>>;
using VVc = vector<vector<char>>;using VVs = vector<vector<string>>;
using VVP = vector<vector<P>>;using VVPL = vector<vector<PL>>;
using VVV = vector<vector<vector<int>>>;using VVVL = vector<vector<vector<ll>>>;using VVVP = vector<vector<vector<P>>>;

template<class T,class S>bool chmin(T& a, S b) {if(a<=b)return false;a = b;return true;};
template<class T,class S>bool chmax(T& a, S b) {if(a>=b)return false;a = b;return true;};

ll modpow(ll x, ll n, ll m = mod) {
    if (n < 0) {ll res = modpow(x, -n, m);return modpow(res, m - 2, m);}
	if (abs(x) >= m)x %= m;if (x < 0)x += m;//if (x == 0)return 0;
	ll res = 1;
	while (n) {if (n & 1)res = res * x % m;x = x * x % m; n >>= 1;}
	return res;
}

class modint {
public:
    int val;
    modint() :val(0) {}
    template<typename T>modint(T x=0): val(x%mod){if(val<0)val+=mod;}
    modint(const modint &r){val=r.val;}
    modint& operator=(const modint& other) {val = other.val;return *this;}
    modint& operator=(const int& other) {val = other;return *this;}
    modint& operator=(const long long& other) {val = other;return *this;}
    //算術演算子
    modint operator +(){return (*this);} //単項
    modint operator -(){return (val%mod+mod)%mod;} //単項
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    modint operator %(const modint &r){return modint(*this)%=r;}
    modint operator ^(long long r){modint ans = 1, x = val;while (r > 0) {if (r & 1) ans *= x;x *= x;r >>= 1;}return ans;}
    modint operator ++(int){val+=1;val%=mod; return *this;}
    modint operator --(int){(val==0)?val=mod-1:val-=1; return *this;}
    //代入演算子
    modint &operator +=(const modint &r){val+=r.val;if(val>=mod)val-=mod;return *this;}
    modint &operator -=(const modint &r){if(val<r.val)val+=mod;val-=r.val;return *this;}
    modint &operator *=(const modint &r){val=(ll)val*r.val%mod;return *this;}
    modint &operator /=(const modint &r){ll a=r.val,b=mod,u=1,v=0;while(b){ll t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}val=val*u%mod;if(val<0)val+=mod;return *this;}
    modint &operator %=(const modint &r){val=val%r.val; return *this;}
    modint &operator ^=(const long long &r){(*this)=(*this)^r; return (*this);}
    //等価比較演算子
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator >(const modint& r){return this->val>r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
    // 他のクラスとの計算
    template <typename T>friend modint operator+(T t, const modint& o) {return modint(t) + o;}
    template <typename T>friend modint operator-(T t, const modint& o) {return modint(t) - o;}
    template <typename T>friend modint operator*(T t, const modint& o) {return modint(t) * o;}
    template <typename T>friend modint operator/(T t, const modint& o) {return modint(t) / o;}
};
istream &operator >>(istream &is,modint& x){ long long t; is >> t; x=modint(t); return is;}
ostream &operator <<(ostream &os,const modint& x){return os<<x.val;}

const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = (1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * (i + 1);
	}
	factinv[max_n - 1] = (1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] *(i + 1);
	}
}

modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[a - b];
}

template<typename T>
T gcd(T a, T b) {
	a = abs(a); b = abs(b);
	if (a < b)swap(a, b);
	while(b){ll r = a % b; a = b; b = r;}
	return a;
}

template <class T,class S> istream &operator>>(istream &is, pair<T,S> &pir) {is >> pir.first >> pir.second; return is;}
template <class T> istream &operator>>(istream &is, vector<T> &vec) {for(T &i: vec) is >> i; return is;}
template <class... T> istream &operator>>(istream &is, tuple<T...> &tpl) {apply([&is](auto &&...args) { ((is >> args), ...); }, tpl);return is;}

template <class OStream, class T> OStream &operator<<(OStream &os, const vector<T> &vec) {auto itr = vec.begin();while (itr != vec.end()){os << *itr; itr++;if(itr!=vec.end())os <<" ";}return os;}
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const array<T, sz> &arr) {auto itr = arr.begin();while (itr != arr.end()){os << *itr; itr++;if(itr!=arr.end())os <<" ";}return os;}
template <class OStream, class... T> OStream &operator<<(OStream &os, const tuple<T...> &tpl) {apply([&os](auto &&...args) {int count = 0;((os << args << (++count != sizeof...(args) ? " " : "")), ...);}, tpl);return os;}
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa) {return os  << pa.first << ' ' << pa.second;}
template <class OStream, class T> OStream &operator<<(OStream &os, const set<T> &vec) {auto itr = vec.begin();while (itr != vec.end()){os << *itr; itr++;if(itr!=vec.end())os <<" ";}return os;}

template <class OStream, class T> OStream &operator<<(OStream &os, const deque<T> &vec) {os << "deq[";for (auto v : vec) os << v << ',';os << ']';return os;}
template <class OStream, class T> OStream &operator<<(OStream &os, const queue<T> &vec) {os << "que[";for (auto v : vec) os << v << ',';os << ']';return os;}
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const map<TK, TV> &mp) {os << '{';for (auto v : mp) os << v.first << "=>" << v.second << ','<< endl;os << '}';return os;}
template<typename T>void out(T a){ cout << a << endl;}
template<typename T,typename S>void out(T a,S b){ cout << a <<" " << b << endl;}
template<typename T,typename S,typename U>void out(T a,S b,U c){ cout << a <<" " << b <<" " << c << endl;}
void yes(bool f=1,string yes="Yes",string no="No"){if(f){cout << yes << endl;}else{cout << no << endl;}}

struct  S
{
	int x;
	int y;
	S(int x, int y) : x(x),y(y){}
	bool operator<(const struct S& other) const
	{
		return x < other.x;
	}
	void debug(){
		cerr <<"debug " << x <<"-" << y << endl;
	}
};

void solve(){
    int N,M;
    cin >> N >> M;
    VL A(N),B(M),C(N);
    cin >> A >> B >> C;
    VL BD(N - 1,0);
    rep(i,N-1){
        BD[i + 1] = B[i%M];
    }
    rep(i,N-1){
        BD[i + 1] += BD[i];
    }
    ll al = 0;
    rep(i,N){
        al += C[i];
    }
    map<ll, ll> m;
    rep(i,N){
        if(m.count(A[i]-BD[i])){
            m[A[i] - BD[i]] -= C[i];
        }else{
            m[A[i] - BD[i]] = al - C[i];
        }
    }
    ll ans = infll;
    for(auto i: m){
        chmin(ans, i.second);
    }
    out(ans);
    return;
}

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<setprecision(20);
    int t=1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}
0