General

# Author Problem Lang Verdict Time Memory Sent Judged
69149165 Practice:
_hikari_
1293D - 28 GNU C++17 Accepted 46 ms 4680 KB 2020-01-19 20:11:12 2020-01-19 20:11:13

→ Source
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <bitset>
#include <cmath>
#define ll long long
#define intinf 0x7f7f7f7f
#define llinf 0x7f7f7f7f7f7f7f7f
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define db double
using std::map;
using std::set;
using std::vector;
using std::bitset;
using std::sqrt;
using std::pair;
const int maxn=2e5+5;
ll x0,asd0,ax,ay,bx,by,xs,ys,t,sx=1e16,k,pre[maxn],ans;
inline ll ABS(ll a) {
return a>0?a:-a;
}
struct Node {
ll x,y;
}n[maxn];
inline ll dis(int id1,int id2) {
return ABS(n[id1].x-n[id2].x)+ABS(n[id2].y-n[id1].y);
}
inline ll duan(int id1,int id2) {
return id2>id1?(pre[id2]-pre[id1]):(pre[id1]-pre[id2]);
}
inline void solve(int id,ll K) {
if(K<0) return;
ll id1=id,id2=k;
ll asd,nans=1;
while(id1>=0) {
asd=duan(id1,id);
if(asd>K) break;
while((asd+duan(id1,id2))>K&&id2>id) id2--;
if((asd+duan(id1,id2))<=K) nans=std::max(nans,id2-id1+1);
id1--;
}
id1=0; id2=id;
while(id2<=k) {
asd=duan(id2,id);
if(asd>K) break;
while((asd+duan(id1,id2))>K&&id1<id) id1++;
if((asd+duan(id1,id2))<=K) nans=std::max(nans,id2-id1+1);
id2++;
}
ans=std::max(ans,nans);
}
int main() {
scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld",&x0,&asd0,&ax,&ay,&bx,&by,&xs,&ys,&t);
n[0].x=x0; n[0].y=asd0;
for(int i=1;;i++) {
if(n[i-1].x>=sx||n[i-1].y>=sx) break;
n[i].x=ax*n[i-1].x+bx;
n[i].y=ay*n[i-1].y+by;
k=i;
}
rep(i,1,k) pre[i]=pre[i-1]+dis(i,i-1);
n[k+1].x=xs; n[k+1].y=ys;
rep(i,0,k) {
solve(i,t-dis(i,k+1));
}
printf("%lld",ans);
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?