結果

問題 No.1460 Max of Min
コンテスト
ユーザー suzuken_w
提出日時 2021-04-02 00:16:15
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 882 ms / 2,000 ms
コード長 1,762 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,747 ms
コンパイル使用メモリ 219,200 KB
最終ジャッジ日時 2025-01-20 07:27:30
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 91
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
const vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T>void debag(const vector<T> &a){cerr<<"debag :";for(auto v:a)cerr<<v<<" ";cerr<<"\n";}
template<class T>void print(const vector<T> &a){for(auto v:a)cout<<v<<" ";cout<<"\n";}
V<ll> add(V<ll> &x,V<ll> &d){
    int k=d.size();
    V<ll> ans(k);
    ans[0]=min(d[0],x[k-1]);
    for(int i=1;i<k;i++){
         ans[i]=max(x[i-1],min(d[i],x[k-1]));
    }
    return ans;
}
V<ll> mul(V<ll> &x,V<ll> &d){
    int k=d.size();
    V<V<ll>> nxt(k);
    nxt[0]=x;
    for(int i=1;i<k;i++){
       nxt[i]=add(nxt[i-1],d);
    }
    V<ll> ans(k,-2*inf);
    for(int i=0;i<k;i++){
       for(int j=0;j<k;j++){
            chmax(ans[j],min(nxt[i][j],x[i]));
       }
    }
    return ans;
}
int main(){
  ll k,n;
  cin>>k>>n;
  V<ll> a(k),b(k);
  for(int i=0;i<k;i++)cin>>a[i];
  for(int i=0;i<k;i++)cin>>b[i];
  V<ll> c(k,-2*inf);
  c[0]=2*inf;
  for(int i=60;i>=0;i--){
        c=mul(c,b);
        if(n&(1ll<<i)){
            c=add(c,b);
        }
  }
  ll ans=-2*inf;
  for(int i=0;i<k;i++){
       chmax(ans,min(a[i],c[i]));
  }
  cout<<ans<<"\n";
}
0