結果
問題 | No.3067 +10 Seconds Clock |
ユーザー |
|
提出日時 | 2025-03-21 22:37:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 7,957 bytes |
コンパイル時間 | 2,181 ms |
コンパイル使用メモリ | 208,180 KB |
実行使用メモリ | 7,936 KB |
最終ジャッジ日時 | 2025-03-21 22:37:14 |
合計ジャッジ時間 | 4,040 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
#ifndef INCLUDED_MAIN #define INCLUDED_MAIN #include __FILE__ int main() { ll n,t; cin>>n>>t; vector<ll> nx(n-1); ll need=0; rep(i,n-1) { cin>>nx[i]; need+=nx[i]; } ll k; cin>>k; vector<ll> tim(k); rep(i,k) { cin>>tim[i]; tim[i]--; } vector<ll> pos_time(n); pos_time[0]=t; ll xidx=0; srep(i,1,n-1) { pos_time[i]=pos_time[i-1]-nx[i-1]; if(pos_time[i]<=0) { cout<<-1<<nl; return 0; } if(tim[xidx]==i) { xidx++; pos_time[i]+=10; } } ll allcatch=pos_time[n-1]; ll red=(allcatch-1)/10; ll ans=k-red; if(ans<0) { ans=0; } cout<<ans<<nl; return 0; } /////// library zone /////// #else #include <bits/stdc++.h> using namespace std; #define rep(i,n) for(ll i=0;i<n;i++) #define srep(i,l,r) for(ll i=l;i<=r;i++) using ll = long long; const ll mod=998244353; #define vout(v) for(auto i :v) cout<<i<<" "; #define INF 9223300000000000000ll #define Winf 5e12 #define nl "\n" #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define vl vector<ll> vector<ll> pfact(ll n) { vector<ll> resp; vector<bool> prefact(sqrtl(n)+10); for(ll i=2;i*i<=n;i++) { while(n%i==0) { n/=i; if(!prefact[i]) resp.push_back(i); prefact[i]=true; } } if(n!=1) resp.push_back(n); return resp; } ll vecmax(vector<ll> &a) { ll ans=-1*INF; rep(i,(ll)a.size()) { ans=max(ans,a[i]); } return ans; } ll vecmin(vector<ll> &a) { ll ans=INF; rep(i,(ll)a.size()) { ans=min(ans,a[i]); } return ans; } ll safemod(ll num,ll rule) { return (num%rule+rule)%rule; } ll modinv(ll a, ll mod) { //拡張Euclidによるmodでの逆元, a*u+mod*v=1を解く ll b=mod,u=1,v=0; while (b) { ll t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); } u%=mod; if (u < 0) u+=mod; return u; } vector<ll> Erasieve(ll n) { vector<bool> is_prime(n+1, true); is_prime[0] = is_prime[1] = false; for (int i=2;i*i<=n;++i) { if (is_prime[i]) { for (int j=i*i;j<=n;j+=i) is_prime[j] = false; } } vector<ll> primes; srep(i,2,n) { if (is_prime[i]) primes.push_back(i); } return primes; } ll divcount(ll n) { ll ans=0; for(int i=1;i*i<=n;i++) { if(n%i==0) ans+=(i*i==n ? 1:2); } return ans; } struct UnionFind { //Potentializedでない vector<int> par; vector<int> rank;//これは各木のsizeに近いものを表す UnionFind(int N) : par(N), rank(N,0) { rep(i,N) { par[i] = i; } } // 経路圧縮 int root(int x) { if (par[x]==x) return x; return par[x]=root(par[x]); } void unite(int x,int y) { int rx=root(x); int ry=root(y); if (rx==ry) return; if (rank[rx]<rank[ry]) { par[rx]=ry; } else { par[ry]=rx; if (rank[rx]==rank[ry]) { rank[rx]++; } } } bool same(int x,int y) { return root(x)==root(y); } }; struct XORPotentialUF {// 0-indexed!!...これABEL群に対応は...厳しいですね... vector<int> par; vector<int> wgt; // 各ノードの根からの XOR 差分 vector<int> rank; // 木の高さ的な XORPotentialUF(int size) : par(size),wgt(size,0),rank(size,0) { rep(i,size) par[i]=i; } pair<int, int> find(int u) { if (par[u]!=u) { int orig_par=par[u]; auto [root,diff]=find(orig_par); par[u]=root; wgt[u]^=diff; return {root,wgt[u]}; } return {u,0}; } bool limitunite(int u,int v,int z) { auto [pu,ru]=find(u); auto [pv,rv]=find(v); if (pu==pv) { return (ru^rv)==z; } if (rank[pu]<rank[pv]) { swap(pu,pv); swap(ru,rv); } par[pv]=pu; wgt[pv]=ru^rv^z; if (rank[pu]==rank[pv]) rank[pu]++; return true; } int weight(int vertex) { find(vertex); return wgt[vertex]; } int diff_ytox(int x,int y) {//使う気はしない return weight(x)^weight(y); } }; template<class ABEL> struct ADDPotentialUF { //0-indexed!! reference: https://qiita.com/drken/items/cce6fc5c579051e64fab super感謝 vector<int> par; vector<int> rank; vector<ABEL> wgt; ADDPotentialUF(int size) : par(size),wgt(size,0),rank(size,0) { rep(i,size) par[i]=i; } pair<int, ABEL> find(int x) { if (par[x]==x) { return {x,0}; } else { auto [r,w]=find(par[x]); par[x]=r; wgt[x]+=w; return {r,wgt[x]}; } } ABEL weight(int x) { find(x); return wgt[x]; } bool issame(int x,int y) { return find(x).first==find(y).first; } bool unite(int x,int y,ABEL w) { w+=weight(x); w-=weight(y); x=find(x).first; y=find(y).first; if (x==y) { return (diff_ytox(x,y)==w); } if (rank[x]<rank[y]) swap(x,y), w*=-1; if (rank[x]==rank[y]) ++rank[x]; par[y]=x; wgt[y]=w; return true; } ABEL diff_ytox(int x,int y) { //同じ成分にいる前提 return weight(y)-weight(x); } }; template <class T> void vecpr(T first,T last) { ll tmp=0; for(auto it=first;it!=last;++it) { if(tmp) cout<<" "; cout<<*it; tmp++; } cout<<endl; } template <class T> void vvpr(vector<vector<T>> a) { for(int i=0;i<(ll)a.size();i++) { for(int j=0;j<(ll)a[i].size();j++) { if(j) cout<<" "; cout<<a[i][j]; } cout<<endl; } } vector<ll> slmax(vector<ll> a, ll limit, ll breadth) {//slidewindowによる幅breadthでの区間最大値評価,limit=a.size() deque<ll> deq; vector<ll> max_numbers(limit, (-1)*INF); rep(i, limit) { while (!deq.empty() && deq.front() <= i - breadth) deq.pop_front(); while (!deq.empty() && a[deq.back()] <= a[i]) deq.pop_back(); deq.push_back(i); max_numbers[i] = a[deq.front()]; } return max_numbers; } vector<ll> slmin(vector<ll> a, ll limit, ll breadth) {//slidewindowによる幅breadthでの区間最小値評価,limit=a.size() deque<ll> deq; vector<ll> min_numbers(limit, INF); rep(i, limit) { while (!deq.empty() && deq.front() <= i - breadth) deq.pop_front(); while (!deq.empty() && a[deq.back()] >= a[i]) deq.pop_back(); deq.push_back(i); min_numbers[i] = a[deq.front()]; } return min_numbers; } ll modpow(ll fl, ll po, ll mode) { // mode: 0=modなし, 1=modあり ll ret=1; if (mode) { while (po>0) { if (po&1) ret=(ret*fl)%mod; fl=(fl*fl)%mod; po>>=1; } } else { while (po>0) { if(po&1) ret*=fl; fl*=fl; po>>=1; } } return ret; } ll gcd(ll a,ll b) { //Euclid if(a<b) return gcd(b,a); if(a%b==0) return b; return gcd(b,a%b); } vector<ll> lis_min(vector<ll> &a) { ll n=(ll)a.size(); vector<ll> dp(n,INF); rep(i,n){ auto itr = lower_bound(dp.begin(),dp.end(), a[i]); *itr = a[i]; } return dp; }//あんま使えない vector<ll> lis_size(vector<ll>& a) { // 最長増加部分列の a index目までみたのがdp[a]; ll n=a.size(); vector<ll> dp(n,1); vector<ll> seq; rep(i,n) { auto it=lower_bound(seq.begin(), seq.end(), a[i]); if (it==seq.end()) seq.push_back(a[i]); else *it=a[i]; dp[i]=distance(seq.begin(), lower_bound(seq.begin(), seq.end(), a[i]))+1; } srep(i,1,n-1) { if(dp[i]<dp[i-1]) dp[i]=dp[i-1]; } return dp; } #endif