結果
問題 | No.2078 魔抜けなパープル |
ユーザー | ganmodokix |
提出日時 | 2022-09-25 22:16:08 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 651 ms / 2,000 ms |
コード長 | 5,272 bytes |
コンパイル時間 | 1,887 ms |
コンパイル使用メモリ | 203,840 KB |
実行使用メモリ | 6,940 KB |
最終ジャッジ日時 | 2024-06-01 23:36:27 |
合計ジャッジ時間 | 4,814 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 50 ms
6,812 KB |
testcase_01 | AC | 474 ms
6,816 KB |
testcase_02 | AC | 309 ms
6,940 KB |
testcase_03 | AC | 374 ms
6,940 KB |
testcase_04 | AC | 277 ms
6,940 KB |
testcase_05 | AC | 290 ms
6,940 KB |
testcase_06 | AC | 651 ms
6,940 KB |
testcase_07 | AC | 21 ms
6,940 KB |
ソースコード
// モジュール // #REQ: base_template.cpp // <!-- GENERATED BEGIN --> // <!-- base_template/ll.cpp --> using ll = long signed long; using ull = long unsigned long; using ld = long double; // <!-- base_template/575.cpp --> #include <bits/stdc++.h> using namespace std; // <!-- base_template/macro.cpp --> // #REQ: base_template/575 base_template/ll // 汎用マクロ #define ALL(x) (begin(x)), (end(x)) #define ALLOF(x) (begin(x)), (end(x)) #define RALL(x) (rbegin(x)), (rend(x)) #define RALLOF(x) (rbegin(x)), (rend(x)) #define RPE REP #define ERP REP #define EPR REP #define PER REP #define PRE REP #define REP(i,n) for (ll i=0, i##_len=(n); i<i##_len; i++) #define RANGE(i,is,ie) for (ll i=(is), i##_end=(ie); i<=i##_end; i++) #define DSRNG(i,is,ie) for (ll i=(is), i##_end=(ie); i>=i##_end; i--) #define STEP(i, is, ie, step) for (ll i=(is), i##_end=(ie), i##_step = (step); i<=i##_end; i+=i##_step) #define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false) #define FOREACH(i,q) for (auto &i : q) template<typename T, typename U> bool chmax(T &a, const U b) { if (a < b) {a = b; return true;} return false; } template<typename T, typename U> bool chmin(T &a, const U b) { if (a > b) {a = b; return true;} return false; } constexpr int INF = numeric_limits<int>::max(); constexpr ll LINF = numeric_limits<ll>::max(); #define Yes(q) ((q) ? "Yes" : "No") #define YES(q) ((q) ? "YES" : "NO") #define Possible(q) ((q) ? "Possible" : "Impossible") #define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE") #define IIF(q,t,f) ((q) ? (t) : (f)) // <!-- base_template/debug_mode.cpp --> // AtCoder/Codeforces 用 デバッグ検知 #ifdef ONLINE_JUDGE constexpr bool DEBUG_MODE = false; #else constexpr bool DEBUG_MODE = true; #endif // <!-- base_template/qin.cpp --> // #REQ: base_template/575 base_template/ll base_template/macro // 標準入出力 struct qin { // query input size_t sz; qin(size_t _sz = 1) : sz(_sz) {} template <typename T> operator T () const { T a; cin >> a; return a; } template <typename T> operator vector<T> () const { vector<T> a(sz); for (size_t i = 0; i < sz; i++) cin >> a[i]; return a; } template <typename T, typename U> operator pair<T, U> () const { T f; U s; cin >> f >> s; return pair<T, U>(f, s); } }; qin in1; // input one template <typename T> void say(const T x, const char* end = "\n") { cout << x << end; } void say(const ld x, const char* end = "\n") { cout << setprecision(30) << x << end; } template <typename T> void say(const vector<T> x, const char* sep = " ", const char* end = "\n") { REP(i, x.size()) { cout << x[i] << (i+1 == i_len ? end : sep); } } template <typename T> void say(const vector<vector<T>> x, const char* sep = " ", const char* end = "\n") { REP(i, x.size()) { say(x[i], sep, end); } } // <!-- base_template/dump.cpp --> // #REQ: base_template/575 base_template/debug_mode #define DUMP(q) DUMP_FUNC(q, #q, __FILE__, __LINE__) template <typename T> void DUMP_PROC(T x) { if (is_integral<T>() || is_floating_point<T>()) cerr << "\e[32m" << x << "\e[m"; else cerr << x; } template<> void DUMP_PROC<char>(char x) { cerr << "\e[36m\'" << x << "\'\e[m"; } template<> void DUMP_PROC<string>(string x) { cerr << "\e[33m\"" << x << "\"\e[m"; } template <typename T, typename U> void DUMP_PROC(pair<T, U> x) { cerr << "{"; DUMP_PROC(x.first); cerr << ", "; DUMP_PROC(x.second); cerr << "}"; } template <typename ...T, typename U, U... Seq> void DUMP_PROC(tuple<T...> &x, integer_sequence<U, Seq...>) { (void)(int[]){(cerr << ((const char*[]){"", ", "})[!!Seq] << (DUMP_PROC(get<Seq>(x)), ""), 0)...}; } template <typename ...T> void DUMP_PROC(tuple<T...> x) {cerr << "{"; DUMP_PROC(x, index_sequence_for<T...>()); cerr << "}";} template <typename T> void DUMP_PROC(vector<T> x) { cerr << "["; for (auto &xi : x) { DUMP_PROC(xi); cerr << (&xi != &*x.rbegin()?", ":""); } cerr << "]"; } template <typename T> void DUMP_FUNC(T x, const char* name, const char* fn, int ln) { if (!DEBUG_MODE) return; cerr << "\e[32m[DEBUG]\e[m " << name << ": "; DUMP_PROC(x); cerr << " @ " << fn << "(" << ln << ")" << endl; } #define DUMPT(...) DUMP(tuple(__VA_ARGS__)) // <!-- base_template/gcc.cpp --> // gcc拡張マクロ #define popcount __builtin_popcount #define popcountll __builtin_popcountll // <!-- base_template.cpp --> // #REQ: base_template/575 base_template/ll base_template/debug_mode base_template/gcc base_template/macro base_template/dump base_template/qin // base template set // <!-- GENERATED END --> // #END void solve() { ll x, a; cin >> x >> a; ll w = ceil(sqrt(x)) + 10; vector dp(a+1, LINF); dp[0] = 0; REP(i, a+1) { RANGE(k, 1, min<ll>(i, w)) { if (dp[i-k] < LINF) { chmin(dp[i], dp[i-k] + k * k + x); } } } RANGE(k, 1, a) { if (dp[a-k] < LINF) { chmin(dp[a], dp[a-k] + k * k + x); } } say(dp[a]); } // 処理内容 int main() { ios::sync_with_stdio(false); // stdioを使うときはコメントアウトすること cin.tie(nullptr); // インタラクティブ問題ではコメントアウトすること // code here ll t = in1; RPE(i, t) solve(); }