Submission #994263
Source Code Expand
// need #include <iostream> #include <algorithm> // data structure //#include <bitset> //#include <list> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> //#include <array> //#include <tuple> //#include <unordered_map> //#include <unordered_set> //#include <complex> //#include <deque> // stream //#include <istream> //#include <sstream> //#include <ostream> // etc #include <cassert> #include <functional> #include <iomanip> //#include <typeinfo> //#include <chrono> //#include <random> #define INIT std::ios::sync_with_stdio(false);std::cin.tie(0); #define VAR(type, ...)type __VA_ARGS__;Scan(__VA_ARGS__); template<typename T> void Scan(T& t) { std::cin >> t; } template<typename First, typename...Rest>void Scan(First& first, Rest&...rest) { std::cin >> first; Scan(rest...); } #define OUT(d) std::cout<<d; #define FOUT(n, d) std::cout<<std::fixed<<std::setprecision(n)<<d; #define SOUT(n, c, d) std::cout<<std::setw(n)<<std::setfill(c)<<d; #define SP std::cout<<" "; #define TAB std::cout<<"\t"; #define BR std::cout<<"\n"; #define ENDL std::cout<<std::endl; #define FLUSH std::cout<<std::flush; #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i; #define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& r:c)for(auto& i:r)std::cin>>i; #define ALL(a) (a).begin(),(a).end() #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i) #define REP(i, n) for(int i=0;i<int(n);++i) #define RREP(i, n) for(int i=(n)-1;i>=0;--i) #define FORLL(i, a, b) for(ll i=ll(a);i<ll(b);++i) #define RFORLL(i, a, b) for(ll i=ll(b)-1;i>=ll(a);--i) #define REPLL(i, n) for(ll i=0;i<ll(n);++i) #define RREPLL(i, n) for(ll i=ll(n)-1;i>=0;--i) #define PAIR std::pair<int, int> #define PAIRLL std::pair<ll, ll> #define IN(a, x, b) (a<=x && x<b) #define SHOW(d) {std::cerr << #d << "\t:" << d << "\n";} #define SHOWVECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";} #define SHOWVECTOR2(v) {std::cerr << #v << "\t:\n";for(const auto& xxx : v){for(const auto& yyy : xxx){std::cerr << yyy << " ";}std::cerr << "\n";}} #define SHOWPAIR(p) {std::cerr << #p << "\t:(" << p.first << ",\t" << p.second << ")\n";} #define SHOWPAIRVECTOR2(v) {std::cerr << #v << "\t:\n";for(const auto& xxx : v){for(const auto& yyy : xxx){std::cerr<<'('<<yyy.first<<", "<<yyy.second<<") ";}std::cerr << "\n";}} #define SHOWPAIRVECTOR(v) {for(const auto& xxx:v){std::cerr<<'('<<xxx.first<<", "<<xxx.second<<") ";}std::cerr<<"\n";} #define SHOWQUEUE(a) {std::queue<decltype(a.front())> tmp(a);std::cerr << #a << "\t:";for(int i=0; i<static_cast<int>(a.size()); ++i){std::cerr << tmp.front() << "\n";tmp.pop();}std::cerr << "\n";} //#define CHMAX(a, b) a = (((a)<(b)) ? (b) : (a)) //#define CHMIN(a, b) a = (((a)>(b)) ? (b) : (a)) template<typename T> T CHMAX(T& a, const T b) { return a = (a < b) ? b : a; } template<typename T> T CHMIN(T& a, const T b) { return a = (a > b) ? b : a; } #define EXCEPTION(msg) throw std::string("Exception : " msg " [ in ") + __func__ + " : " + std::to_string(__LINE__) + " lines ]" #define TRY(cond, msg) try {if (cond) EXCEPTION(msg);}catch (std::string s) {std::cerr << s << std::endl;} //void CHECKTIME(std::function<void()> f) { auto start = std::chrono::system_clock::now(); f(); auto end = std::chrono::system_clock::now(); auto res = std::chrono::duration_cast<std::chrono::nanoseconds>((end - start)).count(); std::cerr << "[Time:" << res << "ns (" << res / (1.0e9) << "s)]\n"; } #define int ll using ll = long long; using ull = unsigned long long; constexpr int INFINT = 1 << 30; // 1.07x10^ 9 constexpr int INFINT_LIM = (1LL << 31) - 1; // 2.15x10^ 9 constexpr ll INFLL = 1LL << 60; // 1.15x10^18 constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62); // 9.22x10^19 constexpr double EPS = 1e-9; constexpr int MOD = 1000000007; constexpr double PI = 3.141592653589793238; std::set<PAIR> dp[2000006]; // 時刻i: // 1. そのまま続けて焼く // 焼く速度vのとき // → dp[i + v] = dp[i] + 1; // 2. 食べてから焼く // → dp[i*2] = dp[i] + a + 2 signed main() { INIT; VAR(int, n, a); if (n <= a) { OUT(n)BR; return 0; } assert(n <= 1000000 && a <= 1000000); REP(i, 2000006) { dp[i].insert(PAIR(i, 1)); } FOR(i, 1, n + 1) { for (auto& p : dp[i]) { dp[i + p.second].insert(PAIR(p.first + 1, p.second)); } dp[i * 2].insert(PAIR((*dp[i].begin()).first + a + 2, i)); } ll min = INFLL; /*RREP(i, n + 1) { CHMIN(min, dp[i]); CHMIN(dp[i], min); }*/ /*REP(i, n + 2) { OUT(dp[i])TAB; }BR;*/ /*REP(i, n + 2) { OUT(v[i])TAB; }BR;*/ int ans = INFLL; FOR(i, n, 2000006) { if(!dp[i].empty()) CHMIN(ans, (*dp[i].begin()).first); } OUT(ans)BR; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Cookies |
User | satanic0258 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 5026 Byte |
Status | MLE |
Exec Time | 2137 ms |
Memory | 704256 KB |
Judge Result
Set Name | sample | dataset1 | dataset2 | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 500 | 0 / 500 | ||||||||||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
dataset1 | sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt |
dataset2 | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt, 02-25.txt, 02-26.txt, 02-27.txt, 02-28.txt, 02-29.txt, 02-30.txt, 02-31.txt, 02-32.txt, 02-33.txt, 02-34.txt, 02-35.txt, 02-36.txt, 02-37.txt, 02-38.txt, 02-39.txt, 02-40.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | TLE | 2135 ms | 651520 KB |
01-02.txt | TLE | 2137 ms | 702208 KB |
01-03.txt | TLE | 2137 ms | 701568 KB |
01-04.txt | TLE | 2137 ms | 703232 KB |
01-05.txt | TLE | 2137 ms | 704256 KB |
01-06.txt | TLE | 2137 ms | 699520 KB |
01-07.txt | TLE | 2137 ms | 700800 KB |
01-08.txt | TLE | 2137 ms | 695168 KB |
01-09.txt | TLE | 2137 ms | 691840 KB |
01-10.txt | TLE | 2137 ms | 698624 KB |
01-11.txt | TLE | 2137 ms | 703232 KB |
01-12.txt | TLE | 2136 ms | 681728 KB |
01-13.txt | AC | 88 ms | 93952 KB |
01-14.txt | MLE | 444 ms | 258944 KB |
01-15.txt | TLE | 2135 ms | 655616 KB |
01-16.txt | TLE | 2135 ms | 655616 KB |
01-17.txt | TLE | 2137 ms | 702592 KB |
01-18.txt | AC | 294 ms | 219008 KB |
01-19.txt | AC | 292 ms | 219008 KB |
01-20.txt | AC | 293 ms | 219008 KB |
01-21.txt | AC | 88 ms | 93952 KB |
01-22.txt | AC | 292 ms | 219008 KB |
01-23.txt | AC | 292 ms | 219008 KB |
01-24.txt | AC | 292 ms | 219008 KB |
01-25.txt | AC | 292 ms | 219008 KB |
01-26.txt | AC | 294 ms | 219008 KB |
02-01.txt | AC | 88 ms | 93952 KB |
02-02.txt | RE | 188 ms | 93952 KB |
02-03.txt | RE | 188 ms | 93952 KB |
02-04.txt | RE | 187 ms | 93952 KB |
02-05.txt | RE | 187 ms | 93952 KB |
02-06.txt | RE | 187 ms | 93952 KB |
02-07.txt | RE | 186 ms | 93952 KB |
02-08.txt | RE | 189 ms | 93952 KB |
02-09.txt | RE | 188 ms | 93952 KB |
02-10.txt | RE | 187 ms | 93952 KB |
02-11.txt | RE | 187 ms | 93952 KB |
02-12.txt | RE | 186 ms | 93952 KB |
02-13.txt | RE | 188 ms | 93952 KB |
02-14.txt | RE | 186 ms | 93952 KB |
02-15.txt | RE | 186 ms | 93952 KB |
02-16.txt | RE | 187 ms | 93952 KB |
02-17.txt | RE | 186 ms | 93952 KB |
02-18.txt | RE | 187 ms | 93952 KB |
02-19.txt | RE | 188 ms | 93952 KB |
02-20.txt | RE | 187 ms | 93952 KB |
02-21.txt | RE | 187 ms | 93952 KB |
02-22.txt | RE | 188 ms | 93952 KB |
02-23.txt | RE | 187 ms | 93952 KB |
02-24.txt | RE | 186 ms | 93952 KB |
02-25.txt | RE | 187 ms | 93952 KB |
02-26.txt | RE | 188 ms | 93952 KB |
02-27.txt | RE | 187 ms | 93952 KB |
02-28.txt | RE | 187 ms | 93952 KB |
02-29.txt | RE | 186 ms | 93952 KB |
02-30.txt | RE | 186 ms | 93952 KB |
02-31.txt | RE | 189 ms | 93952 KB |
02-32.txt | RE | 188 ms | 94080 KB |
02-33.txt | RE | 187 ms | 93952 KB |
02-34.txt | RE | 188 ms | 93952 KB |
02-35.txt | RE | 188 ms | 93952 KB |
02-36.txt | RE | 187 ms | 93952 KB |
02-37.txt | RE | 188 ms | 93952 KB |
02-38.txt | RE | 187 ms | 93952 KB |
02-39.txt | RE | 188 ms | 93952 KB |
02-40.txt | RE | 188 ms | 93952 KB |
sample-01.txt | AC | 294 ms | 219008 KB |
sample-02.txt | AC | 89 ms | 93952 KB |
sample-03.txt | MLE | 677 ms | 310656 KB |