結果
| 問題 | No.2386 Udon Coupon (Easy) |
| ユーザー |
 wahr69
|
| 提出日時 | 2023-07-21 22:41:42 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 35 ms / 2,000 ms |
| コード長 | 14,349 bytes |
| コンパイル時間 | 12,737 ms |
| コンパイル使用メモリ | 311,760 KB |
| 最終ジャッジ日時 | 2025-02-15 17:11:29 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
//#define NDEBUG#pragma GCC optimize("O3","unroll-loops","omit-frame-pointer","inline") //Optimization flags//#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX#pragma GCC target("avx") //Enable AVX#ifndef _MSC_VER#include <x86intrin.h> //AVX/SSE Extensions#endif#ifdef _MSC_VER#pragma warning(1:4456)#endif#define _CRT_SECURE_NO_WARNINGS#define _USE_MATH_DEFINES#define ALL(a) (a).begin(),(a).end()#define MEM2LOC(type,name) type name=(this->name);#define MEM2LOC_V(type,name) type name=((this->name).data());#define LOC2MEM(name) (this->name)=(name);#include<iostream>#include<array>#include<vector>#include<list>#include<stack>#include<queue>#include<set>#include<map>#include<unordered_set>#include<unordered_map>#include<algorithm>#include<numeric>#include<iomanip>#include<math.h>#include<fstream>#include<string>#include<sstream>#include<cmath>#include<memory>#include<cassert>#include<functional>#include<chrono>#include<bitset>using namespace std;using namespace chrono;namespace ValLib {constexpr double DIST_INF=1e100;constexpr int DX4[]={0,-1,0,1};constexpr int DY4[]={-1,0,1,0};constexpr int DX8[]={0,-1,-1,-1,0,1,1,1};constexpr int DY8[]={-1,-1,0,1,1,1,0,-1};constexpr int DX5[]={DX4[0],DX4[1],DX4[2],DX4[3],0};constexpr int DY5[]={DY4[0],DY4[1],DY4[2],DY4[3],0};constexpr int DX9[]={DX8[0],DX8[1],DX8[2],DX8[3],DX8[4],DX8[5],DX8[6],DX8[7],0};constexpr int DY9[]={DY8[0],DY8[1],DY8[2],DY8[3],DY8[4],DY8[5],DY8[6],DY8[7],0};typedef unsigned int uint;typedef long long ll;typedef unsigned long long ull;constexpr ll V_MOD = 998244353ll;constexpr int V_INT_MAX = 2147483647;constexpr ll V_LL_MAX = 9223372036854775807ll;constexpr ull V_ULL_MAX = 18446744073709551615ull;template<class T,size_t A>using array1=array<T,A>;template<class T,size_t A,size_t B>using array2=array<array<T,B>,A>;template<class T,size_t A,size_t B,size_t C>using array3=array<array<array<T,C>,B>,A>;template<class T,size_t A,size_t B,size_t C,size_t D>using array4=array<array<array<array<T,D>,C>,B>,A>;template<class T,size_t A,size_t B,size_t C,size_t D,size_t E>using array5=array<array<array<array<array<T,E>,D>,C>,B>,A>;template<class T>using vector1=vector<T>;template<class T>using vector2=vector<vector<T>>;template<class T>using vector3=vector<vector<vector<T>>>;template<class T>using vector4=vector<vector<vector<vector<T>>>>;template<class T>using vector5=vector<vector<vector<vector<vector<T>>>>>;template<typename Key,typename Value>using umap=std::unordered_map<Key,Value>;template<typename T>using uset=std::unordered_set<T>;template<typename T>using sptr=typename std::shared_ptr<T>;template<class _Iter>using iter_cat_type=typename std::iterator_traits<_Iter>::iterator_category;template<class _Ty,class=void>constexpr bool _is_iterator=false;template<class _Ty>constexpr bool _is_iterator<_Ty,std::void_t<iter_cat_type<_Ty>>> = true;template<typename T>void fill(vector<T>&a,const T&v){std::fill(ALL(a),v);}template<typename T>void fill(vector<vector<T>>&a,const T&v){for(vector<T>&t:a)std::fill(ALL(t),v);}template<typename T>void resize(vector<T>&a,int sz1){a.resize(sz1);}template<typename T>void resize(vector<T>&a,int sz1,const T&v){a.resize(sz1,v);}template<typename T>void resize(vector<vector<T>>&a,int sz1,int sz2){a.resize(sz1);for(vector<T>&t:a)t.resize(sz2);}template<typename T>void resize(vector<vector<T>>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(vector<T>&t:a)t.resize(sz2,v);}template<typename T>void assign(vector<T>&a,int sz1,const T&v){a.assign(sz1,v);}template<typename T>void assign(vector<vector<T>>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(vector<T>&t:a)t.assign(sz2,v);}template<typename T,size_t SZ>void fill(array<T,SZ>&a,const T&v){std::fill(ALL(a),v);}template<typename T,size_t SZ1,size_t SZ2>void fill(array2<T,SZ1,SZ2>&a,const T&v){for(array<T,SZ2>&t:a)std::fill(ALL(t),v);}template<typename T,typename U>ostream&operator<<(ostream&os,const pair<T,U>&pr){os<<"{"<<pr.first<<","<<pr.second<<"}";return os;}template<typename T>ostream&operator<<(ostream&os,vector<T>&a){os<<"[";for(int i=0;i<a.size();i++){if(i!=0){os<<",";}os<<a[i];}os<<"]";return os;}template<typename T,size_t SZ>ostream&operator<<(ostream&os,const array<T,SZ>&a){os<<"[";for(int i=0;i<SZ;i++){if(i!=0){os<<",";}os<<a[i];}os<<"]";return os;}template<typename T,typename U>ostream&operator<<(ostream&os,const map<T,U>&m){os<<"{";auto b=m.begin();auto e=m.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<p->first<<":"<<p->second;}os<<"}";return os;}template<typename T>ostream&operator<<(ostream&os,const set<T>&s){os<<"{";auto b=s.begin();auto e=s.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<*p;}os<<"}";return os;}template<typename T,typename U>ostream&operator<<(ostream&os,const unordered_map<T,U>&m){os<<"{";auto b=m.begin();auto e=m.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<p->first<<":"<<p->second;}os<<"}";return os;}template<typename T>ostream&operator<<(ostream&os,const unordered_set<T>&s){os<<"{";auto b=s.begin();auto e=s.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<*p;}os<<"}";return os;}constexpr ll mod_add(ll a,ll b,ll mod){return((a%mod)+(b%mod))%mod;}constexpr ll mod_sub(ll a,ll b,ll mod){return((a%mod)+mod-(b%mod))%mod;} // a>bだとmod-(b-a)が返るconstexpr ll mod_mul(ll a,ll b,ll mod){return((a%mod)*(b%mod))%mod;}constexpr ull mod_add(ull a,ull b,ull mod){return((a%mod)+(b%mod))%mod;}constexpr ull mod_sub(ull a,ull b,ull mod){return((a%mod)+mod-(b%mod))%mod;} // a>bだとmod-(b-a)が返るconstexpr ull mod_mul(ull a,ull b,ull mod){return((a%mod)*(b%mod))%mod;}constexpr int intPow(int x,int n){assert(x>=0);assert(n>=0);if(x==0){if(n==0){return 1;}else{return 0;}}int r=1,z=x;while(n>0){if(n&1){r*=z;}z*=z;n>>=1;}return r;}constexpr ll intPow(ll x,ll n){assert(x>=0ll);assert(n>=0ll);if(x==0ll){if(n==0ll){return 1ll;}else{return 0ll;}}ll r=1ll,z=x;while(n>0ll){if(n&1ll){r*=z;}z*=z;n>>=1ll;}return r;}constexpr ll intPow(ll x,ll n,ll mod){assert(x>=0ll);assert(n>=0ll);if(x==0ll){if(n==0ll){return 1ll;}else{return 0ll;}}ll r=1ll,z=x;while(n>0ll){if(n&1ll){if(mod>0ll){r=mod_mul(r,z,mod);}else{r*=z;}}if(mod>0ll){z=mod_mul(z,z,mod);}else{z*=z;}n>>=1ll;}return r;}constexpr ull intPow(ull x,ull n){if(x==0ull){if(n==0ull){return 1ull;}else{return 0ull;}}ull r=1ull,z=x;while(n>0ull){if(n&1ull){r*=z;}z*=z;n>>=1ull;}return r;}constexpr ull intPow(ull x,ull n,ull mod){if(x==0ull){if(n==0ull){return 1ull;}else{return 0ull;}}ull r=1ull,z=x;while(n>0ull){if(n&1ull){if(mod>0ull){r=mod_mul(r,z,mod);}else{r*=z;}}if(mod>0ull){z=mod_mul(z,z,mod);}else{z*=z;}n>>=1ull;}return r;}constexpr ll mod_inv(ll a,ll mod){return intPow(a%mod,mod-2ll,mod);}constexpr ll mod_div(ll a,ll b,ll mod){return mod_mul(a,mod_inv(b,mod),mod);}constexpr ull mod_inv(ull a,ull mod){return intPow(a%mod,mod-2ull,mod);}constexpr ull mod_div(ull a,ull b,ull mod){return mod_mul(a,mod_inv(b,mod),mod);}typedef pair<int, int> pii;typedef pair<ll, ll> pll;typedef pair<long double, long double> pdd;ll ceilDiv(ll a,ll b){return a/b+(a%b!=0?1:0);}ll isOverflowAdd(ll a,ll b){return a > V_LL_MAX - b;}ll isOverflowMul(ll a,ll b){return a > V_LL_MAX / b;}void debugErrSub();template<class Head,class...Tail>void debugErrSub(Head&&head,Tail&&...tail){cerr<<" "<<head;debugErrSub(std::forward<Tail>(tail)...);}template<class Head,class...Tail>void debugErr(Head&&head,Tail&&...tail){cerr<<head;debugErrSub(std::forward<Tail>(tail)...);}template<typename Key, typename Value>bool containsKey(const umap<Key, Value>& m, const Key& key) {return m.find(key) != m.end();}template<typename Key, typename Value>bool containsValue(const umap<Key, Value>& m, const Value& val) {for (auto it = m.begin(); it != m.end(); ++it)if (it->second == val)return true;return false;}template<typename T>const typename uset<T>::const_iterator find(const uset<T>& s, const T& key) {return s.find(key);}template<typename T>bool contains(const uset<T>& s, const T& key) {return s.find(key) != s.end();}#ifndef __GNUC__int __builtin_popcount(unsigned int n){return(int)bitset<32>(n).count();}int __builtin_popcountll(unsigned long long n){return(int)bitset<64>(n).count();}#endif// 条件を満たす最小の要素のindexを返す// lb: lower bound. 条件式を満たさない// ub: upper bound. 条件式を満たす// check: 条件式// 使い方の例: int result = binarySearch<int>(A, 0, N - 1, [&](int x) { return x >= K; });template<typename T> int binarySearch(const vector<T>& vec, int beginIndex, int endIndex, const function<bool(const T&)>& confilm) {int lb = beginIndex; // lower boundint ub = endIndex; // upper boundwhile (abs(ub - lb) > 1) {int mid = (ub + lb) / 2;if (confilm(vec[mid])) {ub = mid;} else {lb = mid;}}return ub;}// lb: lower bound. 条件式を満たさない// ub: upper bound. 条件式を満たす// check: 条件式ll binarySearch(ll lb, ll ub, const function<bool(ll)>& check) {while (abs(ub - lb) > 1ll) {ll mid = (lb + ub) / 2ll;if (check(mid)) {ub = mid;} else {lb = mid;}}return ub;}// lb: lower bound. 条件式を満たさない// ub: upper bound. 条件式を満たす// check: 条件式ull binarySearch(ull lb, ull ub, const function<bool(ull)>& check) {assert(ub > lb);while (ub - lb > 1ull) {ull mid = (lb + ub) / 2ull;if (check(mid)) {ub = mid;} else {lb = mid;}}return ub;}// 最大公約数（ユーグリッドの互除法）static constexpr ull gcd(ull x, ull y) {assert(x > 0ull);assert(y > 0ull);ull r = 0ull;while ((r = x % y) != 0ull) {x = y;y = r;}return y;}// 最小公倍数static constexpr ull lcm(ull x, ull y) {assert(x > 0ull);assert(y > 0ull);return x / gcd(x, y) * y;}// 文字列の先頭の0を削除するstring cutZeroLeft(const string& str) {for (int i = 0; i < (int)str.length(); ++i) {if (str[i] != '0') {return str.substr(i);}}return "";}// 0以上の整数を0埋めで表記するstring fillZero(ull number, int digit) {int zeroNum = max(0, (int)(digit - to_string(number).length()));return move(move(string(zeroNum, '0')) + move(to_string(number)));}// double型の値を任意の少数桁数で表示する// 指定の桁数まで0で埋める。指数表記にはならない// precision=0を指定したときは小数点は表示しない// 表示桁数＋１桁目を四捨五入するstring sprintDoublePlane(double value, int precision) {assert(precision >= 0);stringstream ss;ss << fixed << setprecision(precision) << value;return move(ss.str());}template<typename A>void in(A&a){cin>>a;cin.ignore();}template<typename A,typename B>void in(A&a,B&b){cin>>a>>b;cin.ignore();}template<typename A,typename B,typename C>void in(A&a,B&b,C&c){cin>>a>>b>>c;cin.ignore();}template<typename A,typename B,typename C,typename D>void in(A&a,B&b,C&c,D&d){cin>>a>>b>>c>>d;cin.ignore();}template<typename A,typename B,typename C,typename D,typename E>void in(A&a,B&b,C&c,D&d,E&e){cin>>a>>b>>c>>d>>e;cin.ignore();}template<typename A,typename B,typename C,typename D,typename E,typename F>void in(A&a,B&b,C&c,D&d,E&e,F&f){cin>>a>>b>>c>>d>>e>>f;cin.ignore();}template<typename A,typename B,typename C,typename D,typename E,typename F,typename G>void in(A&a,B&b,C&c,D&d,E&e,F&f,G&g){cin>>a>>b>>c>>d>>e>>f>>g;cin.ignore();}template<typename A>void inr(vector<A>&a,int size){resize(a,size);for(int i=0;i<size;++i){cin>>a[i];cin.ignore();}}template<typename A,typename B>void inr(vector<A>&a,vector<B>&b,int size){resize(a,size);resize(b,size);for(int i=0;i<size;++i){cin>>a[i]>>b[i];cin.ignore();}}template<typename A,typename B,typename C>void inr(vector<A>&a,vector<B>&b,vector<C>&c,int size){resize(a,size);resize(b,size);resize(c,size);for(int i=0;i<size;++i){cin>>a[i]>>b[i]>>c[i];cin.ignore();}}template<typename A,typename B,typename C,typename D>void inr(vector<A>&a,vector<B>&b,vector<C>&c,vector<D>&d,int size){resize(a,size);resize(b,size);resize(c,size);resize(d,size);for(int i=0;i<size;++i){cin>>a[i]>>b[i]>>c[i]>>d[i];cin.ignore();}}template<typename A,typename B,typename C,typename D,typename E>void inr(vector<A>&a,vector<B>&b,vector<C>&c,vector<D>&d,vector<E>&e,int size){resize(a,size);resize(b,size);resize(c,size);resize(d,size);resize(e,size);for(int i=0;i<size;++i){cin>>a[i]>>b[i]>>c[i]>>d[i]>>e[i];cin.ignore();}}template<typename A>void inrl(vector<A>&a,int size){resize(a,size);for(int i=0;i<size;++i){cin>>a[i];}cin.ignore();}template<typename A>void inr(vector2<A>&a,int h,int wa){resize(a,h,wa);for(int i=0;i<h;++i){for(int j=0;j<wa;++j){cin>>a[i][j];}cin.ignore();}}template<typename A,typename B>void inr(vector2<A>&a,vector2<B>&b,int h,int wa,int wb){resize(a,h,wa);resize(b,h,wb);for(int i=0;i<h;++i){for(intj=0;j<wa;++j){cin>>a[i][j];}for(int j=0;j<wb;++j){cin>>b[i][j];}cin.ignore();}}template<typename A,typename B,typename C>void inr(vector2<A>&a,vector2<B>&b,vector2<C>&c,int h,int wa,int wb,int wc){resize(a,h,wa);resize(b,h,wb);resize(c,h,wc);for(int i=0;i<h;++i){for(int j=0;j<wa;++j){cin>>a[i][j];}for(int j=0;j<wb;++j){cin>>b[i][j];}for(int j=0;j<wc;++j){cin>>c[i][j];}cin.ignore();}}template<typename A,typename B>void inpr(vector<pair<A,B>>&a,int h){resize(a,h);for(int i=0;i<h;++i){cin>>a[i].first>>a[i].second;cin.ignore();}}template<typename T>void out(const T&val){cout<<val<<"\n";}}using namespace ValLib;void solve() {ll N, A, B, C;in(N);in(A, B, C);vector<ll> dp(N + 1, 0);for (int i = 0; i < N; ++i) {if (i + 3 <= N) dp[i + 3] = max(dp[i + 3], dp[i] + A);if (i + 5 <= N) dp[i + 5] = max(dp[i + 5], dp[i] + B);if (i + 10 <= N) dp[i + 10] = max(dp[i + 10], dp[i] + C);}out(*max_element(dp.begin(), dp.end()));}int main() {std::ios::sync_with_stdio(false);//#define INPUT_FROM_FILE//#define OUTPUT_TO_FILE#ifdef INPUT_FROM_FILEifstream ifs("input01.txt");cin.rdbuf(ifs.rdbuf());#endif#ifdef OUTPUT_TO_FILEofstream ofs("output01.txt");cout.rdbuf(ofs.rdbuf());#endifsolve();}