結果
問題 | No.1486 ロボット |
ユーザー |
|
提出日時 | 2021-05-13 19:14:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 15,691 bytes |
コンパイル時間 | 2,103 ms |
コンパイル使用メモリ | 190,308 KB |
実行使用メモリ | 11,996 KB |
最終ジャッジ日時 | 2024-09-25 07:37:26 |
合計ジャッジ時間 | 3,022 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h>namespace clibrary{using namespace std;namespace macro{using ll=long long;using ld=long double;#define rep(i,n) for(ll i=0;i<n;i++)#define irep(i,n) for(ll i=0;i<=n;i++)#define reps(i,j,n) for(ll i=j;i<n;i++)#define repr(i,n) for(ll i=n-1;i>=0;i--)#define bit(i,n) for(ll i=0;i<(1<<n);i++)#define dbl(i) fixed << setprecision(15) << i << endl#define all(a) a.begin(),a.end()#define gcd __gcd#define Unweightgraph vector<vector<ll>>#define Weightgraph vector<vector<Edge>>#define st(a) sort(a.begin(),a.end())#define rst(a) sort(a.rbegin(),a.rend())#define mp(a,b) make_pair(a,b)#define pb(a) push_back(a)#define fi first#define se secondusing vl =vector<ll>;using vi =vector<int>;using vs =vector<string>;using vpl =vector<pair<ll,ll>>;using P=pair<ll,ll>;const ll mod = 1000000007;const ll mod1=998244353;const ll inf=1e9;const ll linf=1e18;string yn(bool a){if(a)return "Yes";return "No";}string Yn(bool a){if(a)return "YES";return "NO";}template <typename T>bool chmin(T &a, const T &b) {if (a > b) {a = b;return true;}return false;}template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b;return true;}return false;}class mint {ll x;public:mint(ll x=0) : x((x%mod+mod)%mod) {}mint operator-() const {return mint(-x);}mint& operator+=(const mint& a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint& a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint& a) {(x *= a.x) %= mod;return *this;}mint operator+(const mint& a) const {mint res(*this);return res+=a;}mint operator-(const mint& a) const {mint res(*this);return res-=a;}mint operator*(const mint& a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(mod-2);}mint& operator/=(const mint& a) {return (*this) *= a.inv();}mint operator/(const mint& a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& m){os << m.x;return os;}};class UnionFind {public:vector <ll> par; // 各元の親を表す配列vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}void init(ll sz_) {par.resize(sz_);siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかったfor (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}ll root(ll x) { // 根の検索while (par[x] != x) {x = par[x] = par[par[x]]; // x の親の親を x の親とする}return x;}bool unite(ll x, ll y) {x = root(x);y = root(y);if (x == y) return false;// merge technique(データ構造をマージするテク.小を大にくっつける)if (siz[x] < siz[y]) swap(x, y);siz[x] += siz[y];par[y] = x;return true;}bool same(ll x, ll y) { // 連結判定return root(x) == root(y);}ll size(ll x) { // 素集合のサイズreturn siz[root(x)];}};struct Edge {ll to; // 辺の行き先ll weight; // 辺の重みEdge(ll t, ll w) : to(t), weight(w) { }};//バイナリーインデックスツリーtemplate<typename T>class BIT{public:int N;vector<T> data;BIT(T _N):N(_N){data.assign(N+1, 0);};// a is 1-indexedvoid add1(int a, T w){for(int x = a; x <= N; x += x & -x)data[x] += w;}// 1-indexed sum of prefix [0, a]T sum1(int a){T res = 0;for(int x = a; x > 0; x -= x & -x)res += data[x];return res;}// 1-indexed sum of range [l, r]T sum1(int l, int r){return sum1(r) - sum1(l-1);}// 0-indexed addvoid add(int a, T w){add1(a + 1, w);}// 0-indexed sumT sum(int a){return sum1(a + 1);}// 0-indexed sum of rangeT sum(int l, int r){return sum(r) - sum(l-1);}// show the valuevoid debug(){print(data);}};//区間加算BITtemplate <typename T>struct BIT2 {int n; // 要素数vector<T> bit[2]; // データの格納先BIT2(int n_) { init(n_); }void init(int n_) {n = n_ + 1;for (int p = 0; p < 2; p++) bit[p].assign(n, 0);}void add_sub(int p, int i, T x) {for (int idx = i; idx < n; idx += (idx & -idx)) {bit[p][idx] += x;}}void add(int l, int r, T x) { // [l,r) に加算add_sub(0, l, -x * (l - 1));add_sub(0, r, x * (r - 1));add_sub(1, l, x);add_sub(1, r, -x);}T sum_sub(int p, int i) {T s(0);for (int idx = i; idx > 0; idx -= (idx & -idx)) {s += bit[p][idx];}return s;}T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }};struct Edge3 {ll cost, from, to;Edge3() {}Edge3(ll c, ll f, ll t) : from(c), to(f), cost(t) {}friend bool operator < (const Edge3& lhs, const Edge3& rhs) { return lhs.cost < rhs.cost; };friend bool operator > (const Edge3& lhs, const Edge3& rhs) { return rhs < lhs; };friend bool operator <= (const Edge3& lhs, const Edge3& rhs) { return !(lhs > rhs); };friend bool operator >= (const Edge3& lhs, const Edge3& rhs) { return !(lhs < rhs); };};struct kruskal{struct UnionFind uf;uint64_t weight; // 最小全域木の辺の重みの和kruskal(ll V, vector<Edge3> &edges) : uf(V), weight(0) {sort(edges.begin(), edges.end());for (auto e : edges) {if (uf.same(e.from, e.to)) continue;uf.unite(e.from, e.to);weight += e.cost;}}};}using namespace macro;//約数列挙vector<ll> enum_divisors(ll N) {vector<ll> res;for (ll i = 1; i * i <= N; ++i) {if(N % i == 0) {res.push_back(i);if (N/i != i) res.push_back(N/i);}}sort(res.begin(), res.end());return res;}//素数チェックbool prime(ll a){if(a<=1)return false;for(int i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}//最小公倍数ll lcm(ll a,ll b){ll d = gcd(a,b);return a/d*b;}//aのn乗(繰り返し二乗法)template <typename T>T rui(T a, T n){T x = 1;while(n > 0){//全てのbitが捨てられるまで。if(n&1){//1番右のbitが1のとき。x = x*a;}a = a*a;n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。}return x;}//xのn乗(mod)long long mpow(long long x, long long n,ll m) {ll ret=1;while (n > 0) {if (n & 1) ret =ret*x % m; // n の最下位bitが 1 ならば x^(2^i) をかけるx = x * x % m;n >>= 1; // n を1bit 左にずらす}return ret;}//nCrvector<vector<ll>> comblist(int n, int r) {vector<vector<ll>> v(n + 1,vector<ll>(n + 1, 0));for (int i = 0; i < v.size(); i++) {v[i][0] = 1;v[i][i] = 1;}for (int j = 1; j < v.size(); j++) {for (int k = 1; k < j; k++) {v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);}}return v;}//nCr (mod)ll mcomb(ll n,ll x,ll mod){ll res;ll a=1;for(ll i=0;i<x;i++){a=a*n%mod;n--;}ll b=1;for(ll i=1;i<x+1;i++){b=b*i%mod;}res=(a*mpow(b,mod-2,mod))%mod;return res;}//φ関数(1からnまでのうちnと互いな素な個数)ll phi(ll n){ll ret =n;for(ll i = 2; i * i <= n; i++) {if(n % i == 0) {ret -= ret / i;while(n % i == 0) n /= i;}}if(n>1)ret -=ret/n;return ret;}//拡張ユークリッド互助法ll extGCD(ll a, ll b, ll &x, ll &y) {if (b == 0) {x = 1;y = 0;return a;}ll d = extGCD(b, a%b, y, x); // 再帰的に解くy -= a / b * x;return d;}//逆元ll modinv(ll a, ll m) {ll x, y;extGCD(a, m, x, y);return (x % m + m) % m;}//ビット本数ll bcount(ll bits){bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);}//素因数分解vector<pair<long long, long long> > prime_factorize(long long N) {vector<pair<long long, long long> > res;for (long long a = 2; a * a <= N; ++a) {if (N % a != 0) continue;long long ex = 0; // 指数// 割れる限り割り続けるwhile (N % a == 0) {++ex;N /= a;}// その結果を pushres.push_back({a, ex});}// 最後に残った数についてif (N != 1) res.push_back({N, 1});return res;}//ワーシャルフロイド法(iからjに行くまでの最小コスト計算,nは要素数,dはコスト表)void warshall_floyd(int n,vector<vector<ll>> &d){for (int k = 0; k < n; k++){ // 経由する頂点for (int i = 0; i < n; i++) { // 始点for (int j = 0; j < n; j++) { // 終点d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}}//エラトステネスのふるい(n以下の素数列挙)vector<ll> eratosthenes( const ll N ){vector<bool> is_prime( N + 1 );for( ll i = 0; i <= N; i++ ){is_prime[ i ] = true;}vector<ll> P;for( ll i = 2; i <= N; i++ ){if( is_prime[ i ] ){for( ll j = 2 * i; j <= N; j += i ){is_prime[ j ] = false;}P.emplace_back( i );}}return P;}//エラトステネスのふるい(素数チェック)vector<bool> eratosthenescheck( const ll N ){vector<bool> is_prime( N + 1 );for( ll i = 0; i <= N; i++ ){is_prime[ i ] = true;}for( ll i = 2; i <= N; i++ ){if( is_prime[ i ] ){for( ll j = 2 * i; j <= N; j += i ){is_prime[ j ] = false;}}}return is_prime;}//ダイクストラvector<ll> dijkstra(ll s,ll n,vector<vector<Edge>> g){priority_queue<P, vector<P>, greater<P>> q;vector<ll> dist(n,linf);q.push(make_pair(0, s));dist[s] = 0;while (!q.empty()) {ll pos = q.top().second;ll cost=q.top().first;q.pop();if(cost>dist[pos])continue;for (ll i = 0; i < g[pos].size(); i++) {ll to = g[pos][i].to, cost = g[pos][i].weight;if (dist[to] > dist[pos] + cost) {dist[to] = dist[pos] + cost;q.push(make_pair(dist[to], to));}}}return dist;}//区間素数(l=b-a+1)ll sieve(ll a,ll b){ll x=sqrt(b);ll l=b-a+1;vector<bool> pri(x,true);vector<bool> ans(l,true);for(ll i=2;i*i<b;i++){if(pri[i]){for(ll j=2*i;j*j<b;j+=i)pri[j]=false;for(ll j=max(2LL,(a+i-1)/i)*i;j<b;j+=i)ans[j-a]=false;}}ll tmp=0;rep(i,b-a)if(ans[i])tmp++;return tmp;}}using namespace clibrary;int main(){ll a,b,c,d,e;cin >> a >> b >> c>>d>>e;ll time=0;ll ta=a,tb=c;ll sum=0;bool fa=true,fb=true;vector<ll> shuki(1100000,0);while(time<e){time++;ll now=0;if(fa&&fb)sum++;if(time==ta){if(fa){ta+=b;fa=false;}else{ta+=a;fa=true;now++;}}if(time==tb){if(fb){tb+=d;fb=false;}else{tb+=c;fb=true;now++;}}if(now==2){break;}shuki[time]=sum;}if(time==e)cout<<sum<<endl;else{cout << e/time*sum+shuki[e%time]<<endl;}}