akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
namespace FAST_IO
{
	template<typename T> void read(T &a)
	{
		a=0;
		int f=1;
		char c=getchar();
		while(!isdigit(c))
		{
			if(c=='-')
			{
				f=-1;
			}
			c=getchar();
		}
		while(isdigit(c))
		{
			a=a*10+c-'0';
			c=getchar();
		}
		a=a*f;
	}
	template <typename T> void write(T a)
	{
		if(a<0)
		{
			a=-a;
			putchar('-');
		}
		if(a>9)
		{
			write(a/10);
		}
		putchar(a%10+'0');
	}
	template <typename T> void writeln(T a)
	{
		write(a);
		puts("");
	}
}
int n,x;
int zb[100002],dis[100002];
int ans;
int main()
{
    cin>>n>>x;
    for(int i=0;i<n;i++)
	{
        cin>>zb[i];
        dis[i]=abs(x-zb[i]);
    }
    int d=dis[0];
    for(int i=1;i<n;i++)
	{
        d=__gcd(max(dis[i],d),min(dis[i],d));
    }  
    cout<<d;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 11451419194545;
//コンテスト中はBIT26個使えば行けそうとか思ってたけど，setでやると簡単だった(ほんまか？)
int main() { 

    ll N, Q;
    string S;
    cin >> N >> S >> Q;
    S = S;
    //cout << S << endl;
    //26文字分Setを用意してアルファベットの現れる位置を管理する
    //初期化->番兵追加
    vector<set<ll > > D(26, set<ll >({-1, INF}));
    //setに追加
    for(ll i = 0; i < N; i++){
        D[S[i]-'a'].insert(i);
    }

    vector<ll > ans;
    for(ll i = 0; i < Q; i++){
        ll t; cin >> t;
        if(t == 1){
            ll idx;
            char to_ch;
            cin >> idx >> to_ch;
            idx--;
            //検索
            D[S[idx] - 'a'].erase(idx);
            D[to_ch - 'a'].insert(idx);
            S[idx] = to_ch;
            //cout << S << endl;
        }else{
            //cout << S << endl;
            ll s, e; cin >> s >> e;
            ll cn = 0;
            //ピッタリ-ピッタリで区間を調べるとs==eの時ダメ
            --s;
            for(ll j = 0; j < 26; j++){
                if(D[j].empty()) continue;
                //sからeの区間にアルファベットjは存在するか？を調べる.
                ll st = *D[j].lower_bound(s);
                ll et = *D[j].lower_bound(e);
                if(et > st){
                    cn++;
                }
                //cout << st << " " << et << endl;
            }
            ans.push_back(cn);
            //cout << cn << endl;
        }
    }

    for(ll i = 0; i < ans.size(); i++){
        cout << ans[i] << endl;
    }

}

Measured memory_bytes: 24708
#include<iostream>


using namespace std;
#define ll long long 


bool ke(ll x,ll y){


    if((x&(1ll<<y)))return 1;
    return 0;
}

template <class T> inline T BM(T p, T e, T M) {
    ll ret = 0;
    for(; e > 0; e >>= 1) {
        if(e & 1) ret = (ret + p) % M;
        p = (p + p) % M;
    }
    return (T)ret;
}

ll br[62];
int main(){

    int n;

    scanf("%d",&n);

    ll ar[n+2];

    
    ll res=0;
    for(int i=1;i<=n;i++){


        scanf("%lld",&ar[i]);


        for(ll j=0;j<=60;j++){

            if((ar[i]&(1ll<<j))>0){
                ll k= BM((1ll<<j) ,(i-1-br[j]), 1000000007ll);
                res+=k;
            }
            else 
            {
                ll k=  BM((1ll<<j) ,br[j], 1000000007ll);
                res+=k;
            }
            res %=1000000007ll;
            ll ko = ke(ar[i],j);
            if(ko)br[j]++;
        }
    }
cout<<res<<endl;

    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<int> C;
vector<int> R;

void bfs() {
    R[0] = C[C.size()-1];
    C.pop_back();

    queue<int> Q;
    Q.push(0);

    while(!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        for(auto v : G[cur]) {
            if(R[v] != -1) continue;
            R[v] = C[C.size() - 1];
            C.pop_back();
            Q.push(v);
        }
    }
}

int main() {
    int N;
    cin >> N;
    G.resize(N);
    C.resize(N);
    R.resize(N, -1);
    for(int i=0; i<N-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=0; i<N; ++i) cin >> C[i];

    sort(begin(C), end(C));
    int res = accumulate(begin(C), end(C), 0) - C[N - 1];
    cout << res << endl;

    bfs();
    for(int i=0; i<N; ++i) cout << R[i] << (i + 1 == N ? '\n' : ' ');
}

Measured memory_bytes: 1024
#include  <stdio.h>
/* Aizu Online Judge Problem 	*/
/* Volume0 0004:Simultaneous Equation	*/
/* ax + by = c
   dx + ey = f */

int main(void)
{
  double x, y;
  double a, b, c, d, e, f;
  while(scanf("%lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f) != EOF)
  {
    x = (b * f - c * e)/(b * d - a * e);
    y = (a * f - c * d)/(a * e - b * d);

    x = (x > -0.0005 && x <= 0) ? 0: x;
    y = (y > -0.0005 && y <= 0) ? 0: y;

    printf("%.3f %.3f\n", x, y);
    //printf("%f %f\n", x, y);
  }
  return 0;
}

Measured memory_bytes: 652
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
const ll INF = 1LL<<60;
const int INT_INF = 1e9;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

int main() {
    int n; cin >> n;
    map<int, int> m;
    rep(i, n) {
        int a; cin >> a;
        m[a] += 1;
    }

    int ans = 0;
    for (int x = 1; x <= 100000; x++) {
        int tmp = m[x-1] + m[x] + m[x+1];
        if (tmp > ans) ans = tmp;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

bool ok(int i, set<int> s) {
  while (i > 0) {
    int n = i % 10;
    i /= 10;
    if (s.find(n) != s.end())
      return false;
  }
  return true;
}

int main() {
  int N, K;
  cin >> N >> K;

  set<int> D;
  rep(i, K) {
    int d;
    cin >> d;
    D.insert(d);
  }

  int i = N;
  while (true) {
    if (ok(i, D)) {
      cout << i << endl;
      return 0;
    }
    i++;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
char t[1010];
int main(){
    int i;
    int n;
    int ans;
    while(scanf("%s",&t)){
        n=strlen(t);
        ans=0;
        if(n==1&&t[0]=='0') break;
        for(i=0;i<n;i++){
            ans+=t[i]-'0';
        }
        printf("%d\n",ans);
    }
    return 0;
}


Measured memory_bytes: 2040
#include <bits/stdc++.h>

using namespace std;

int main()
{  string s1,s2; int count=0;
  cin>>s1>>s2;
    for(int i=0;i<s1.size();i++)
    {
        if(s1[i]!=s2[i])
        {
            count++;
        }
    }
 cout<<count<<"\n";
    return 0;
}


Measured memory_bytes: 3848
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;
long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }

int main(){
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;
    for(int i=0; i<N-2; ++i){
        if(S[i]=='A'&&S[i+1]=='B'&&S[i+2]=='C') ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long i = 0; i < n; i++)
#define erep(i, n) for(long i = 1; i <= n; i++)


int main(){long N; string S;
cin >> N >> S;
long r = 0; long l = 0;
rep(i, N){
    if(S.at(i) == ')'){
        if(l == 0) r++;
        else l--;
    }
    else l++;
}
rep(i, r) S = '(' + S;
rep(i, l) S = S + ')';





cout << S << endl;
return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define mp make_pair
#define endl "\n"
#define pii pair<int,int> 
#define ff first
#define ss second
#define mii map<int,int>
#define si set<int>
#define sti stack<int>
#define qi queue<int>
#define vi vector<int>
#define pq priority_queue<int>
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int M=1e9+7;

int32_t main(){
    IOS;
    int n,m;
    cin>>n>>m;
    int h[n];
    vector<vi> v;
    v.resize(n);
    for(int i=0;i<n;i++) cin>>h[i];
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        v[x].pb(y);
        v[y].pb(x);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        bool ok=1;
        for(auto x:v[i]){
            if(h[x]>=h[i]) ok=0;
        }
        if(ok==1){
            ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 9772
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<int, int> P;


ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

ll N;

/******************************************
** A main function is start from here  ****
*******************************************/
int main(){
  cin >> N;
  int ans = 1000;
  for(int i= 1; i<=sqrt(N);i++){
    if(N%i==0){
      int a = i;
      int b = N/i;
      string str = to_string(b);
      ans = min((int)str.size(), ans);
    }
  }

  cout << ans;
  return 0;
}


Measured memory_bytes: 256
//




#include <bits/stdc++.h>
using namespace std;


#define spdio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define pp pop_back()
#define pf push_front
#define ppf pop_front()
#define ff first
#define ss second
#define mp make_pair
#define fr(i,j,n) for(ll i=j; i<n; i++)
#define rfr(i,j,n) for(ll i=n-1; i>=j; i--)
#define pll pair<ll,ll>
#define plb pair<ll,bool>
#define psl pair<string,ll>
#define psb pair<string,bool>
#define srt(v) sort((v).begin(),(v).end())
#define ub(v,val) upper_bound((v).begin(),(v).end(),(val))-(v).begin()
#define lb(v,val) lower_bound((v).begin(),(v).end(),(val))-(v).begin()


typedef long double ld;
typedef long long int ll;


//getline(cin,string);
const ll inf = (ll) 1e18 + 19;
const ll mod = (ll) 1e9  +  7;




ll calc(ll n,ll k) {
    ll val=1;
    fr(i,0,k) val*=n;
    return val;
}




void cazz() {
    ll t=1,i=0,j,n;
    //cin>>t;
    while(t--) {
        ll a,b,c,d;
        ll mx;
        cin>>a>>b>>c>>d;
        mx=max(a*c,max(b*c,max(a*d,b*d)));
        cout<<mx<<"\n";
    }
}




int main() {
    spdio;
	cazz();
	return 0;
}


Measured memory_bytes: 3624
#!/usr/bin/env python3
import sys

NO = "IMPOSSIBLE"  # type: str

def solve(A: int, B: int):
    if (A+B) % 2 == 0:
        print((A+B)//2)
    else:
        print(NO)


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int i,j,n,m;
	char tab[1010][1010];
	cin>>n>>m;
	for (i=0;i<=n+1;i++)
	{
		
		tab[i][0]='#';
		tab[i][m+1]='#';
	}
	for (i=0;i<=m+1;i++)
	{
		
		tab[0][i]='#';
		tab[n+1][i]='#';
	}
	for (i=1;i<=n;i++)
	 for (j=1;j<=m;j++)
	  cin>>tab[i][j];
	for (i=0;i<=n+1;i++)
	 for (j=0;j<=m+1;j++)
	  {
	  	if (j==m+1)
	  	 cout<<tab[i][j]<<"\n";
	  	else
	  	 cout<<tab[i][j];
	  }
	return 0;
}

Measured memory_bytes: 384
import math

n = int(input())
prime_count = 0
for _ in range(n):
    num = int(input())
    num_sqrt = math.floor(math.sqrt(num))
    is_prime = True
    for d in range(2, num_sqrt+1):
        if num % d == 0:
            is_prime = False
            break
    if is_prime:
        prime_count += 1
print(prime_count)


Measured memory_bytes: 5676
import java.util.*;
public class Main {
	public static void main(String[] args){
      	long MOD = 1000000007;
		Scanner sc = new Scanner(System.in);
      	int n = sc.nextInt();
      	long[] a = new long[n];
      	long[] sum = new long[n];
      	long ans = 0;
      	for(int i=0;i<n;i++){
          a[i] = sc.nextLong();
        }
      	sum[n-1] = a[n-1];
      	//System.out.println(sum[n-1]+" ");
      	for(int i=n-2;i>0;i--){
          sum[i] = ( a[i]+sum[i+1] ) % MOD ;
          //System.out.println(sum[i]+" ");
        }
      	for(int i=0;i<n-1;i++){
          ans = ( ans + a[i] * sum[i+1] ) % MOD;
        }
      	System.out.println(ans);
      
	}
}

Measured memory_bytes: 52856
import numpy as np

A = int(input())
B = int(input())
C = int(input())
X = int(input())

# A = 2
# B = 2
# C = 2
# X = 100

count = 0

for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if (a + b + c == 0):
                continue
            if (X == a*500 + b*100 + c*50):
                count = count + 1
print(count)


Measured memory_bytes: 14660
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
  int N; cin >> N;
  int A[100010];
  long long q = 0;
  for(int i = 1; i <= N; ++i) {
    cin >> A[i];
    q += A[i];
  }
  A[N+1] = A[1];
  int x = q;
  for(int i = 2; i <= N-1; i += 2) {
    x -= 2 * A[i];
  }
  cout << x << ' ';
  int xi = x;
  for(int i = 1; i < N; ++i) {
    xi = 2 * A[i] - xi;
    cout << xi;
    if(i != N-1) cout << ' ';
    else cout << endl;
  }

  return 0;
}


Measured memory_bytes: 1664
//>> OI Solution Info <<//
// Version: 2
// State: Progress
// Problem: Moderate Differences
// ID: AGC017B
// Timeline:
//   09/07/17 22:30 ~ --- Initialize
// Review:
//   Mathematical problem: LESS or LEQUAL?!
//>> End <<//
#include <iostream>
#include <stdio.h>
using namespace std;
long long n,a,b,c,d;

int main(){
    scanf("%lld %lld %lld %lld %lld",&n,&a,&b,&c,&d);
    b-=a;n--;
    if(b>n*d || b<-n*d){
        printf("NO\n");
        return 0;
    }
    b+=n*d;
    long long spacing=(1+n)*c+(1-n)*d,span=n*(d-c);
    long long m=span+spacing;
    //printf("%lld %lld %lld\n",span,spacing,b%m);
    if(spacing<=0 || b%m<=span)printf("YES\n");
    else printf("NO\n");
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n, m, c; cin >> n >> m >> c;
    int ans = 0;
    int b[m], a[n][m];
    for (int i = 0; i < m; i++) cin >> b[i];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < n; i++){
        int sum = 0;
        for (int j = 0; j < m; j++){
            sum += a[i][j] * b[j];
        }
        sum += c;
        if (sum > 0) ans++;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
A.insert(N+1,0)
S = 0
for i in range(N+1):
  S += abs(A[i]-A[i+1])
for i in range(1,N+1):
  print(S-abs(A[i-1]-A[i])-abs(A[i]-A[i+1])+abs(A[i-1]-A[i+1]))

Measured memory_bytes: 14048
#include <iostream>
#include <iterator>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

int main()
{
    while (true) {
        int n;
        int m;
        cin >> n >> m;

        if (n == 0 && m == 0) {
            break;
        }

        vector<int> sn;
        for (int i = 0; i < n; ++i) {
            int s;
            cin >> s;
            sn.push_back(s);
        }
        vector<int> sm;
        for (int i = 0; i < m; ++i) {
            int s;
            cin >> s;
            sm.push_back(s);
        }
        constexpr auto MAX_VALUE = 999999999;
        auto changeMin = make_tuple(0, 0, MAX_VALUE);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                auto a = sn;
                auto b = sm;
                swap(a[i], b[j]);
                auto sa = accumulate(begin(a), end(a), 0);
                auto sb = accumulate(begin(b), end(b), 0);
                if (sa == sb) {
                    auto sv = a[i] + b[j];
                    if (sv < get<2>(changeMin)) {
                        changeMin = make_tuple(b[j], a[i], sv);
                    }
                }
            }
        }
        if (get<2>(changeMin) == MAX_VALUE) {
            cout << -1 << endl;
        }
        else {
            int i;
            int j;
            tie(i, j, ignore) = changeMin;
            cout << i << ' ' << j << endl;
        }
    }
}

Measured memory_bytes: 3144
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair< ll, ll > pll;
typedef pair< int, int > pii;

const double pi = 3.14159265358979323846;

#define MOD 1000000007LL
#define PS(p) cout << setprecision(15) << fixed << p << endl;
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
#define ALL(c) c.begin(), c.end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define TG0 get< 0 >
#define TG1 get< 1 >
#define TG2 get< 2 >
#define F first
#define S second
#define VL vector< ll >

// to_string(123)
// atoi("123"); atoi(s.c_str());
// "abc".size()
// s.find('+') == string::npos

using namespace std;

ll maxv = 1e5 + 5;
ll w[105];
ll v[105];

ll dp[105][100005];

int main() {

  ll N, W;
  cin >> N >> W;

  ll sum = 0;
  for (ll i = 1; i <= N; i++) {
    cin >> w[i] >> v[i];
    sum += v[i];
  }

  for (ll i = 0; i <= N; i++) {
    for (ll j = 0; j <= sum; j++) {
      dp[i][j] = 1e11;
    }
  }
  dp[0][0] = 0;

  for (ll i = 1; i <= N; i++) {
    for (ll j = 0; j <= sum; j++) {
      dp[i][j] = dp[i - 1][j];

      if (v[i] <= j) {
        dp[i][j] = min(
            dp[i - 1][j],
            dp[i - 1][j - v[i]] + w[i]);
      }
    }
  }

  ll c = 0;
  for (ll i = 0; i <= sum; i++) {
    if (dp[N][i] <= W) {
      c = max(c, i);
    }
  }

  cout << c << endl;

  return 0;
}


Measured memory_bytes: 80128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int A,B,N,ans=0;
  cin>>A>>B;
  N=B-A+1;
  rep(i,N){
    int x;
    x=A+i;
    if (x/10000==x%10) {
      int y;
      y=x%100;
      y/=10;
      x/=1000;
      x%=10;
      if (x==y) {
        ans+=1;
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
import math
while True :
    d, w, h = map(int, input().split())
    if d == 0 and w == 0 and h == 0 :
        break
    
    length = [d, w, h]
    len_1 = sorted([d, w, h])[0]
    len_2 = sorted([d, w, h])[1]
    max_d = math.sqrt(len_1**2 + len_2**2)
    
    n = int(input())
    for i in range(n) :
        r = int(input())
        if 2 * r > max_d :
            print("OK")
        else :
            print("NA")


Measured memory_bytes: 5660
#include<bits/stdc++.h>
#define int int64_t
using namespace std;

int solve(int h) {
	if(h == 1) return 1;
	else if(h > 1) {
		int ans = 1 + 2 * solve(h/2);
		return ans;
	}
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

	int h;
	cin >> h;
	cout << solve(h) << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(ll x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
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(b<a) { a=b; return 1; } return 0; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

inline void pr(ll n){
    cout << n << endl;
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n;
    cin >> n;
    vll a(n);
    rep(i, n){
        cin >> a[i];
    }
    vll norm(n+1);
    norm[0] = abs(a[0]);
    norm[n] = abs(a[n-1]);
    repr(i, 1, n){
        norm[i] = abs(a[i]-a[i-1]);
    }
    vll cs(n+1, norm[0]);
    vll csr(n+1);
    repr(i, 1, n+1){
        cs[i] = cs[i-1] + norm[i];
    }
    rep(i, n+1){
        csr[i] = cs[n] - cs[i] + norm[i];
    }
    vll norm2(n);
    norm2[0] = abs(a[1]);
    norm2[n-1] = abs(a[n-2]);
    repr(i, 1, n-1){
        norm2[i] = abs(a[i+1]-a[i-1]);
    }
    rep(i, n){
        if(i == 0) pr(norm2[i]+csr[i+2]);
        else if(i == n-1) pr(cs[i-1]+norm2[i]);
        else pr(cs[i-1]+norm2[i]+csr[i+2]);
    }
    dump(a);
    dump(norm);
    dump(cs);
    dump(csr);
    dump(norm2);
    return 0;
}

Measured memory_bytes: 5120
#include<iostream>
using namespace std;

int main() {
    int N;
    cin>>N;
    long A[N];
    for(int i=0;i<N;++i){
        cin>>A[i];
    }
    long ans = 0;
    int r = 0;
    int sum = 0;
    for(int l=0;l<N;++l){
        while(r<N & (sum ^ A[r])==(sum + A[r])){
            sum += A[r];
            r++;
        }
        ans += r - l;
        if(l==r)ans++;
        else {
            sum -= A[l];
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n,ans=0;
    cin>>n;
    ll c[n];
    for(int i=0;i<n;i++)cin>>c[i];
    sort(c,c+n);
    reverse(c,c+n);
    for(int i=0;i<n;i++){
        ans+=(c[i]*(i+2));
        ans%=mod;
    }
    ans*=modpow(2,2*n-2);
    cout<<ans%mod<<endl;
    return 0;
}


Measured memory_bytes: 1792
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def yes():
    print("Yes")  # type: str


def no():
    print("No")  # type: str


def solve(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    if A[M-1] >= sum(A)/(4*M):
        yes()
    else:
        no()
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<cmath>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>
    #include <cassert>
    #include <cmath>

    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    using namespace std;
    using ll = long long;
    using Graph = vector<vector<int>>;
    using P = pair<int,int>;


    
    
    int main(){
        string s,t;cin>>s;
        t = s;
        reverse(s.begin(),s.end());
        int cnt = 0;
        rep(i,s.size()/2){
            if(s[i] == t[i])continue;
            cnt++;
        }
        cout<<cnt;
    }
    


Measured memory_bytes: 256
import java.io.IOException;
import java.math.BigDecimal;
import java.math.BigInteger;

public class Main {
    private static final StringBuilder builder = new StringBuilder();
    public static void main(String[] args) {
        int x = readInt(), n = 1;
        while ((x * n) % 360 != 0) {
            n++;
        }
        System.out.print(n);
    }

    private static void read() {
        builder.setLength(0);
        while (true) {
            try {
                int b = System.in.read();
                if (b == ' ' || b == '\n' || b == -1) {
                    break;
                } else {
                    builder.appendCodePoint(b);
                }
            } catch (IOException e) {
                break;
            }
        }
    }

    private static int readInt() {
        read();
        return Integer.parseInt(builder.toString());
    }

    private static int readInt(int radix) {
        read();
        return Integer.parseInt(builder.toString(), radix);
    }

    private static long readLong() {
        read();
        return Long.parseLong(builder.toString());
    }

    private static long readLong(int radix) {
        read();
        return Long.parseLong(builder.toString(), radix);
    }

    private static BigInteger readBigInteger() {
        read();
        return new BigInteger(builder.toString());
    }

    private static BigInteger readBigInteger(int radix) {
        read();
        return new BigInteger(builder.toString(), radix);
    }

    private static double readDouble() {
        read();
        return Double.parseDouble(builder.toString());
    }

    private static BigDecimal readBigDecimal() {
        read();
        return new BigDecimal(builder.toString());
    }

    private static float readFloat() {
        read();
        return Float.parseFloat(builder.toString());
    }

    private static void skipLine() {
        while (true) {
            try {
                int b = System.in.read();
                if (b == '\n' || b == -1) {
                    break;
                }
            } catch (IOException e) {
                break;
            }
        }
    }

    private static void skip() {
        while (true) {
            try {
                int b = System.in.read();
                if (b == ' ' || b == '\n' || b == -1) break;
            } catch (IOException e) {
                break;
            }
        }
    }

}


Measured memory_bytes: 32348
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long int
#define double /*long*/ double
#define endl '\n'
#define vll vector<ll>
#define vvl vector<vll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vppll vector<pll,pll>
#define mp make_pair
#define pb push_back
#define mapll map<ll,ll>
#define fir first
#define sec second
#define _cin ios_base::sync_with_stdio(0);  cin.tie(0);
#define fo(i,b) for(i=0;i<b;i++)
#define repa(i,a,b) for(i=a;i<b;i++)
#define repb(i,a,b) for(i=a;i>=b;i--)
#define all(x) (x).begin(), (x).end()
#define s(v) (ll)v.size()
#define watch(x) cerr << (#x) << " is " << (x) << endl
#define Time cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n"
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
const long long int MAX = (ll)(1e18+1);
const long long int MIN = (ll)(-1e18-1);
const long long int mod = (ll)(1e9+7);
using namespace std;  // order_of_key(k) -> Number of elements strictly smaller than k
using namespace __gnu_pbds; // order_of_key() ; *( find_by_order() ) -> kth element in set;

ll max(ll a,ll b,ll c) {return max(max(a, b), c);}
ll min( ll a, ll b, ll c) { return min(min(a, b), c);}
ll max(ll a,ll b) {return (a>b) ? a : b;}
ll min(ll a,ll b) {return (a<b) ? a : b;}
ll power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll power_mod(ll a, ll n, ll mod_){ ll p=1; while(n){ if(n%2){ p=(p*a)%mod_;} n/=2; a=(a*a)%mod_;} return p%mod_;}                 
                          /*Code Begins*/




int main(){
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    _cin;
    // cout << setprecision(15);
    ll mn = MAX, mx = MIN;
    ll n, m, t,  k, i, j,  sum=0,  prev, flag=0, cnt=0;
    ll x=0, y=0, fx, diff, tot=0, l , r;
    int TC=1;
    // cin >> TC;
while(TC--){
    cin >> n >> k;
    x=0;
    while(k<=n+1){
        mn = (k)*(k-1)/2;
        mx = n*(n+1)/2 - (n-k)*(n-k+1)/2;
        x +=  mx-mn +1;
        x%=mod;
    ++k;
    }
    
    
    cout << x;

}

    Time;
    return 0;
}


Measured memory_bytes: 3800
#include <bits/stdc++.h>
using namespace std;

const int64_t MOD = 1000000007;
typedef int64_t ll;
typedef uint64_t ull;

#define INF LLONG_MAX

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

signed main() {
  ll n, m;
  cin >> n >> m;
  
  vector< vector<pair<ll,ll>> > graph(n);
  
  ll l,r,d;
  for(ll i=0;i<m;i++){
    cin >> l >> r >> d; l--;r--;
    graph[l].emplace_back(r,d);
    graph[r].emplace_back(l,-d);
  }
  
  vector<ll> pos(n,INF);
  
  char flag[n] = {};
  queue<int> q;
  for(int i=0;i<n;i++){
    if(flag[i]!=0) continue;
  	q.push(i); 
    pos[i] = 0;
    flag[i] = 1;
  	while(!q.empty())
  	{
      auto node = q.front(); q.pop();
      for(auto next: graph[node]) {
        ll expectedPos = pos[node]+next.second;
        if(flag[next.first]!=0){
          // 矛盾がないかチェックが必要
          if(pos[next.first] != expectedPos){
            cout << "No" << endl;
            return 0;
          }
          continue;
        }
        q.push(next.first);
        pos[next.first] = expectedPos;
        flag[next.first] = 1;
      }
  	}
  }
  cout << "Yes" << endl;
  return 0;
}



Measured memory_bytes: 17192
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define int long long
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define inf 1000000000000000007
#define f first
#define s second
#define mini(c,a,b) *min_element(c+a,c+b)
#define maxi(c,a,b) *max_element(c+a,c+b)
//printf("%.12Lf\n",c);
int keta(int x){
	rep(0,i,30){
		if(x<10){
			return i+1;
		}
		x=x/10;
	}
}
int gcd(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return bb;
		}	
		bb=bb%aa;
		if(bb==0){
			return aa;
		}
	}
}	
int lcm(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return x/bb*y;
		}	
		bb=bb%aa;
		if(bb==0){
			return x/aa*y;
		}
	}
}
bool p(int x){
	if(x==1)return false;
	rep(2,i,sqrt(x)+1){
		if(x%i==0&&x!=i){
			return false;
		}
	}	
	return true;
}
int primes[200];
int prime[1000000];
int pr[100000];
int el[314514],wl[314514];
int er[314514],wr[314514];
int a[1114514];
string s[214514];
int ans[214514];
int sa[214514];
signed main(){
	sc(s)
	int n=s.size();
	rep(0,i,n+1)a[i+1]=s[i]-48;
	a[0]=0;
	int ans=0;
	for(int i=n;i>=0;i-=1){
		if(a[i]<5){
			ans+=a[i];
		}
		else if(a[i]==5){
			if(a[i-1]>=5){
				ans+=10-a[i];
				a[i-1]++;
			}
			else ans+=a[i];
		}		
		else{
			ans+=10-a[i];
			a[i-1]++;	
		}
	}
	c(ans)
}		


Measured memory_bytes: 13700
#include <iostream>


using namespace std;


int main(void){
    int n;
    cin>>n;
    int ans=0;
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        ans+=r-l+1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define MAXN (int)1e5
int x[MAXN+10];
int main(void){
  long long int n,a,b;
  int i;
  long long int res;
  cin>>n>>a>>b;
  for(i=1;i<=n;i++){
    cin>>x[i];
  }
  res=0;
  for(i=1;i<n;i++){
    if((x[i+1]-x[i])*a<b) res+=(x[i+1]-x[i])*a;
    else res+=b;
  }
  cout<<res<<endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
 
 
using namespace std;
 
typedef long long ll;
 
#define MOD 998244353
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>b;--i)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
ll newmod(ll a,ll b)
 {
  return ((a%b)+b)%b;
}
 
 
ll powM(ll a,ll b,ll m )
{ 
  a%=m;
  ll ans=1;
  while(b)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }
 
return ans;
}
 
ll pow(ll a,ll b)
{ 
  
  ll ans=1;
  while(b)
  {
    if(b&1)ans=ans*a;
    a=a*a;
    b>>=1;
  }
 
return ans;
}

ll arr[55];
int main()
{ 
  IOS;

for(int i=1;i<=5;i++){
  ll x;cin>>x;
  if(!x){
    cout<<i<<endl;
    return 0;
  }
}



 return 0;

 
 
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define F first
#define S second
#define mod 1000000007

int main()
{
  ll h,w;
  cin>>h>>w;
  vector<vector<char>>mat(h,vector<char>(w,'.'));

  for(int i=0;i<h;i++)
  {
    for(int j=0;j<w;j++)
      cin>>mat[i][j];
  }

  vector<vector<ll>>dp(h,vector<ll>(w,0));
  dp[h-1][w-1]=0;
  for(int i=w-2;i>=0;i--)
  {
    if(mat[h-1][i]=='.')
      dp[h-1][i]=1;
    else
        break;
  }
  for(int i=h-2;i>=0;i--)
  {
    if(mat[i][w-1]=='.')
      dp[i][w-1]=1;
    else
        break;
  }

  for(int i=h-2;i>=0;i--)
  {
    for(int j=w-2;j>=0;j--)
    {
      if(mat[i][j]=='.')
      {
        if(dp[i+1][j]>0&&dp[i][j+1]>0)
          dp[i][j]=(dp[i+1][j]+dp[i][j+1])%mod;
        else
          dp[i][j]=(max(dp[i+1][j],dp[i][j+1]))%mod;
      }
    }
  }
  cout<<dp[0][0]<<endl;
}


Measured memory_bytes: 12236
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#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<(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define VSORT(v) sort(v.begin(), v.end())
#define SORT(v, n) sort(v, v+n)
#define VREV(v,n) reverse(v,v+n)
#define REV(v,n) reverse(v,v+n)
#define vi vector<int>
#define pf push_front
#define pb push_back
#define P pair<int,int>
#define Pll pair<ll,ll>

template<class T, size_t N> size_t countof(const T (&array)[N]) { return N; }
template <class T> void chmin(T&a,const T&b) { a = min(a,b); }
template <class T> void chmax(T&a,const T&b) { a = max(a,b); }
 
void print(){cout<<"\n";}
template <class Head, class... Tail>
void print(Head&& h,Tail&&... t){ 
	if(sizeof...(t)==0)
		cout<<h;
	else
		cout<<h<<' ';
	print(move(t)...);
}

void mprint(auto *matrix,auto N){
	REP(i,N) cout<<matrix[i]<<(i!=N-1?' ':'\n');
	return;
}

const double EPS =1e-9;
const int INF =2e+9;
const ll INFL =9e+18;
const long MOD =1e+9+7;
#define PI 3.14159265258979

#define iP pair<int,P>
int dy[]={0, 0, 1, -1, 1, 1, -1, -1};
int dx[]={1, -1, 0, 0, 1, -1, -1, 1};

inline int in(){int x; cin>>x; return x;}


int main(void){
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	ll N,A,dp[200001],result=0;
	map<ll,ll> mp;

	cin>>N;
	dp[0]=0; mp[0]++;
	FOR(i,1,N+1){
		cin>>A;
		dp[i]=dp[i-1]+A;
		mp[dp[i]]++;;
	}
		
	for(const auto pr:mp){
		ll tem=get<1>(pr);
		if(tem>=2) result+=((tem*(tem-1))/2);
	}
	print(result);
	
	
	return 0;
}


Measured memory_bytes: 14336
n = int(input())
a = []
b = []
c = []
work = 0
total = 0
i = 0
test = 100
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
while(i < n):
  work = a[i]
  total = total + b[work - 1]
  if(test == a[i] - 1):
    total = total + c[test - 1]
  test = a[i]
  i = i + 1
print(total)

Measured memory_bytes: 3064
n, m = map(int, input().split())
rank = []
ind = [0 for i in range(n)]
for i in range(n):
    rank.append(list(map(int, input().split())))
sports = set(range(1, m + 1))
best = n
while len(sports) > 0:
    kol = [0 for i in range(m + 1)]
    for i in range(n):
        while rank[i][ind[i]] not in sports:
            ind[i] += 1
        kol[rank[i][ind[i]]] += 1
    best = min(best, max(kol))
    new_sports = []
    for s in sports:
        if kol[s] < best:
            new_sports.append(s)
    sports = set(new_sports)
print(best)

Measured memory_bytes: 4312
#include <bits/stdc++.h>
using namespace std;

int main() {
  int A,B,K,i,c=0;
  cin >> A >> B >> K;
  
  for(i=A; i>0; i--) {
    if(A%(i+1)==0 && B%(i+1)==0)
      c++;
    if(c==K)
      break;
  }
  
  cout << i+1 << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int d = sc.nextInt();
        int x = sc.nextInt();
        int ans = x;
        for (int i = 0; i < 10; i++) {
            ans = ans * r - d;
            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 35644
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#define MOD 1000000007
#define mkp make_pair
typedef long long ll;
using namespace std;


string S,T;


typedef pair<ll,ll> Hash;

struct RollingHash {

    ll base1,base2;
    ll mod1,mod2;
    vector<ll> hash1,hash2;
    vector<ll> pow1,pow2;

    RollingHash() : base1(1009), base2(1007), mod1(1000000007), mod2(1000000009) {}

    void init(const string &s) {
        int n = s.size();
        hash1.assign(n+1,0);
        hash2.assign(n+1,0);
        pow1.assign(n+1,1);
        pow2.assign(n+1,1);

        for(int i=0;i<n;i++) {
            hash1[i+1] = (hash1[i]+s[i]) * base1 % mod1;
            hash2[i+1] = (hash2[i]+s[i]) * base2 % mod2;
            pow1[i+1] = pow1[i] * base1 % mod1;
            pow2[i+1] = pow2[i] * base2 % mod2;
        }
    }

    Hash get(int l,int r) {//[l,r)
        ll t1 = ((hash1[r] - hash1[l] * pow1[r-l]) % mod1 + mod1) % mod1;
        ll t2 = ((hash2[r] - hash2[l] * pow2[r-l]) % mod2 + mod2) % mod2;
        return make_pair(t1, t2);
    }
};


bool ok[2000020];

int num[2000020];

int m;
vector<int> p;

int dfs(int now,int d){
    if(num[now]>0) return num[now];
    if(d>m){
        cout<<-1<<endl;
        exit(0);
    }
    if(ok[now]==false) return 0;

    p.push_back(now);
    int nex=(now+T.size())%m;
    int res=dfs(nex,d+1)+1;
    return num[now]=res;
}

int main(){
  cin>>S;
  cin>>T;

  string A=S;
  while(A.size()<T.size()) A+=S;


  m=A.size();
  A+=A;
  RollingHash p;
  RollingHash q;
  p.init(A);
  q.init(T);

  Hash targ=q.get(0,T.size());

  for(int i=0;i<m;i++){
      Hash a=p.get(i,i+T.size());
      if(a==targ){
          ok[i]=true;
      }
  }

  int ans=0;

  for(int i=0;i<m;i++){
      ans=max(ans,dfs(i,1));
  }

  cout<<ans<<endl;


  return 0;
}


Measured memory_bytes: 120108
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, p;
    string s;
    cin>> n>> m;
    vector <int> v(n+1, 0);
    vector <int> pen(n+1, 0);
    int ac = 0;
    for(int i = 1; i <= m; ++i){
        cin>> p>> s;
        if(s=="WA"){
            if(v[p] == 0){
                pen[p]++;
            }
        }else{
            v[p]++;
        }
    }
    int neg = 0;
    for(int i = 1; i <= n; ++i){
        if(v[i]){
            ac++;
            neg += pen[i];
        }
    }
    cout << ac << " " << neg << "\n";
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pllll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int, int> > vii;
typedef vector< pair<long long, long long> > vllll;
typedef map<int, int> mii;
typedef map<long long, long long> mllll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0ll)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
#define bitsum(x) __builtin_popcount(x)
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a / gcd(a, b) * b;
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll ans = 0;
  ll n;
  cin >> n;
  // ll n, m;
  // cin >> n >> m;
  // ll n, m, k;
  // cin >> n >> m >> k;
  unordered_set<string> st;
  string s;
  fi(0, n) {
    cin >> s;
    st.insert(s);
  }
  cout << st.size() << endl;
  return 0;
}



Measured memory_bytes: 17788
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main()
{
    int N;
    cin >> N;

    int val_one=N%10;
    if(val_one==0||val_one==1||val_one==6||val_one==8){
        cout <<"pon" << endl;
    }else if(val_one==3){
        cout << "bon" << endl;
    }else{
        cout << "hon" << endl;
    }
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>

using namespace std;

int
main(void){
	vector<int> vec(3);
	for(int i = 0; i < 3; i++) cin >> vec[i];
	int k; cin >> k;
	int rem = k;
	int ans = 0;
	for(int i = 0; i < 3; i++){
		int val;
		if(i == 0) val = 1;
		else if(i == 1) val = 0;
		else val = -1;
		if(rem >= vec[i]){
			ans += val*vec[i];
			rem = rem - vec[i];
		}
		else{
			ans += val*rem;
			rem = 0;
		}
	}	
	cout << ans;
}

Measured memory_bytes: 3560
H,W,K = list(map(int,input().split()))
mod = 1000000007

f = [0]*(W+1)
f[0] = 1
f[1] = 2
for i in range(2,W+1):
    f[i] = f[i-1] + f[i-2]

dp = [[0]*(W+2) for _ in range(H+1)]
dp[0][K] = 1
for i in range(1,H+1):
    for j in range(1,W+1):
        dp[i][j] += (dp[i-1][j] * f[max(0,j-2)] * f[max(0,W-j-1)]
                     + dp[i-1][j-1] * f[max(0,j-3)] * f[max(0,W-j-1)]
                     + dp[i-1][j+1] * f[max(0,j-2)] * f[max(0,W-j-2)] )
        dp[i][j] %= mod
print(dp[-1][1])

Measured memory_bytes: 3064