akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    cout << ((n == m)?"Yes":"No") << endl;
}


Measured memory_bytes: 256
///بِسْمِ الّٰلهِ الرَّحْمٰنِ الرَحِيْمِ
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi acos(-1.0)
int main()
{
     ios_base::sync_with_stdio(false);cin.tie(NULL);
     ll int i,n,t,p=INT_MAX,j=0,x,a=0,b,l=1,r=0,y,k,c,sum=0,m,d;
     cin>>n>>m;
     for(i=0;i<m;i++){
        cin>>p;
        sum+=p;
     }
     if(n<sum){
        cout<<-1<<endl;
     }
     else{
        cout<<n-sum<<endl;
     }

     return EXIT_SUCCESS;
}



Measured memory_bytes: 3612
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl
#define show2(a, n, m) rep(i, n) { rep(j, m) {cout << a[i][j] << ' ';} cout << endl;} 
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef long double ld;

const int INF = 1 << 30;
const long long INFL = 1LL << 60;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

int main() {
//	cout << fixed << setprecision(15);
	ll n, x;
	cin >> n >> x;
	vll w(n), v(n);
	rep(i, n) cin >> w[i] >> v[i];

	vector<vll> dp(n+1, vll(n*1000+1, INFL));
	dp[0][0] = 0;
	rep(i, n) rep(j, n*1000+1) {
		dp[i+1][j] = dp[i][j];
		if(j - v[i] >= 0) chmin(dp[i+1][j], dp[i][j-v[i]] + w[i]);
	}
	ll ans = 0;
	for(int i = n*1000; i >= 0; i--) {
		if(dp[n][i] <= x) {
			ans = i;
			break;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 80256
#ABC096-C
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
G=[["."]*(w+2)]
for i in range(h):
    G.append(["."]+S()+["."])
G.append(["."]*(w+2))
ret=True
#grid周り探索
for i in range(1,h):
    for j in range(1,w):
        if G[i][j]==".":
            continue
        ans=False
        for ti,tj in[[-1,0],[1,0],[0,1],[0,-1]]:
            if G[i+ti][j+tj]=="#":
                ans=True
        if not ans:
            ret=False
if ret:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 40176
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define iter vector<int>::iterator
#define mod 1000000007
#define inf 1e16

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,k;
    cin>>n>>k;

    int a[n];
    for(int i=0;i<n;i++)
    {
    	cin>>a[i];
    }
    int dp[n+1][k+1];
    dp[1][0]=1;
    dp[0][0]=0;
    for(int i=1;i<k+1;i++)
    {
    	if(i<=a[0])
    	    dp[1][i]=dp[1][i-1]+1;
    	else
    		dp[1][i]=dp[1][i-1];
    	dp[0][i]=0;
    }

    for(int i=2;i<n+1;i++)
    {
    	for(int j=0;j<k+1;j++)
    	{
    		if(j-a[i-1]-1>=0)
    		    dp[i][j]=(((dp[i-1][j]%mod)-(dp[i-1][j-a[i-1]-1]%mod))+mod)%mod;
    		else
    			dp[i][j]=dp[i-1][j]%mod;

    		if(j>0)
    		    dp[i][j]=((dp[i][j]%mod)+(dp[i][j-1]%mod))%mod;
    	}
    }
    
    if(k-1>=0)
    	cout<<(((dp[n][k]%mod)-(dp[n][k-1]%mod))+mod)%mod<<"\n";
    else
    	cout<<dp[n][k]%mod<<"\n";

    


}

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

int main() {
	int n, a[10001] = { 0 };
	
	a[0] = 1;
	for (int i = 1; i < 10001; i++) {
		a[i] = a[i - 1] + i;
	}

	while (cin >> n) {
		cout << a[n] << endl;
	}
	return 0;
}

Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


void solve() {
    int i,j,k,l,r,x,y; string s;
    bool exit = false;
    int D,N;
    cin>>D>>N;
    int ret=1;
    FOR(i,D)
        ret*=100;
    if(N != 100)
        cout<< ret*N<<endl;
    else
        cout << ret*101<<endl;
    /*cin>>N;
    vector<ll> V;
    FOR(x,N+1) {
            FOR(y,N+1) {
                    ll ret=1;
                    FOR(i,x) ret*=2;
                    FOR(i,y) ret*=5;
                    V.push_back(ret);
            }
    }
    sort(ALL(V));
    FORR(v,V) cout<<v<<endl;*/
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}



Measured memory_bytes: 256
X = int(input())
 
l = [1 for i in range(1001)]
k = 0
for i in range(1,33):
    for j in range(2,10):
        tmp = i ** j
        if tmp <= 1000:
            l[k] = tmp
            k += 1
        else :
            break
 
l.sort()
for i in range(1001):
    if X < l[i]:
        print(l[i-1])
        break
else :
    print(l[-1])


Measured memory_bytes: 3316
while True:
    N = int(input())
    if N == 0: break
    src = list(input().split())
    ru = lu = both = False
    ans = 0
    for f in src:
       if f == 'ru':   ru = True
       elif f == 'lu': lu = True
       elif f == 'rd': ru = False
       else:           lu = False
       if ru == lu == (not both):
           ans += 1
           both = not both
    print(ans)

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

ll dp[90];


ll lucas(int n){
  dp[0]=2;
  dp[1]=1;
  for(int i=0;i<n-1;i++){
    dp[i+2]=dp[i]+dp[i+1];
  }
  return dp[n];
}

int main() {
  int n;
  cin >> n;
  cout << lucas(n) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s, t, u;
    int a,b;
    cin >> s >> t >> a >> b >> u;
    
    if(u == s){
        a--;
    } else if(u == t){
        b--;
    }
    cout << a << " "<< b << endl;
	return 0;
}

Measured memory_bytes: 256
input_arr = input().split(" ")
A = int(input_arr[0])
B = int(input_arr[1])

# AとBの偶奇が一致する場合 存在する
# AとBの偶奇が一致しない場合 存在しない

if (A % 2 != B % 2):
    print("IMPOSSIBLE")
else:
    k = int((A + B) / 2)
    print(k)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;

int main() {
    vector<int> num(4);
    for (int i = 0; i < 4; i++) {
        char a;
        cin >> a;
        a = a - '0';
        num.at(i) = a;
    }
    for (int i = 0; i < 8; i++) {
        int k = i, sum = num.at(0);
        string S = to_string(num.at(0));
        for (int j = 0; j < 3; j++) {
            int a = num.at(j + 1);
            if (k & 1) {
                S += '-';
                S += to_string(a);
                a *= -1;
            }
            else {
                S += '+';
                S += to_string(a);
            }
            sum += a;
            k >>= 1;
        }
        if (sum == 7) {
            cout << S << "=7" << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int x;
  cin>>x;
  int n;
  cin>>n;
  int a[n];
  unordered_map<int,int>m;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    m[a[i]]++;
  }
  int res=0;
  int i=1;
  if(m[x]==0)
    cout<<x;
  else
  {
  while(1)
  {
    int temp=x-i;
    if(m[temp]==0)
    {
      res=temp;
      break;
    }
    int sec=x+i;
    if(m[sec]==0)
    {
      res=sec;
      break;
    }
    i++;
  }
  cout<<res;
  }
}
  


Measured memory_bytes: 3572
# coding=utf-8
# Date: 2020-01-08
# Author: lee215

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]


# fi = open('sample1.in', 'r')
# raw_input = fi.readline

H, A = gets()
if A == 1:
    print H
else:
    print(H + A - 1) / A


Measured memory_bytes: 2568
n = int(input())
xy = [list(map(int,input().split())) for _ in range(n)]

def func(p,q):
    flag = [0]*n
    for i in range(n):
        for j in range(n):
            if i==j or flag[j-1]==1:
                continue
            if xy[j][0]-xy[i][0]==p and xy[j][1]-xy[i][1]==q:
                flag[j-1]=1
    return n-sum(flag)

ans = n
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        ans = min(ans,func(xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]))
print(ans)

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

typedef long long int ll;

int main() {
    ll n;
    ll a[200000];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    ll ans = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            ans += a[i - 1] - a[i];
            a[i] += a[i - 1] - a[i];
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 5060
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};
use std::collections::HashSet;


fn main() {
  let x = read::<i64>();
  let mut uniq = HashSet::new();
  for _ in 0..x {
    let y = read::<String>();
    uniq.insert(y);
  }

  println!("{}", if uniq.len() == 3 { "Three" } else { "Four" });
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pi acos(-1.0)
#define eps 1e-9
#define ll long long
#define ull unsigned long long
#define sf scanf
#define pf printf
#define nl printf("\n")
#define	inf (ll)1e15
#define mod 998244353
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend() 
#define sz(x) (int)(x).size()
#define test_case int ___t;scanf("%d", &___t);for(int cs=1;cs<=___t;cs++)

using namespace __gnu_pbds;
using namespace std;

inline string str_inp(int n){char ch[n+5];sf(" %s",ch);return string(ch);}
inline string line_inp(int n)
{char ch[n+5];fgets(ch,n+5,stdin);string s=string(ch);s.pop_back();return s;}

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;

const int S=3005;
ll n,sum;
ll dp[S+5][S+5];
ll ara[S+5];

ll Solve(ll i,ll taken)
{
	if(i>n)
	{
		if(taken==sum)return 1LL;
		return 0LL;
	}
	if(dp[i][taken]!=-1)return dp[i][taken];
	ll tot=0;
	tot=2*Solve(i+1,taken);
	if(taken+ara[i]<=sum)tot+=Solve(i+1,taken+ara[i]);
	return dp[i][taken]=tot%mod;
}

int main()
{
    //#ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    //#endif

	while(~sf("%lld %lld",&n,&sum))
	{
		for(int i=1;i<=n;i++)sf("%lld",&ara[i]);
		memset(dp,-1,sizeof dp);
		pf("%lld\n",Solve(1,0));
	}
    return 0;
}




































Measured memory_bytes: 74632
N = int(input())
B = list(map(int, input().split()))
A = [-1] * N
B_sort = sorted(B)
for i in range(N - 1):
    index = B.index(B_sort[i])
    if A[index] == -1:
        A[index] = B[index]
    else:
        A[index] = min(A[index], B[index])
    if A[index + 1] == -1:
        A[index + 1] = B[index]
    else:
        A[index + 1] = min(A[index + 1], B[index])
    B[index] = -1
print(sum(A))


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
using namespace std;
//---------------------------------------
int gcd(int x, int y);  //?????§??¬?´???°???????????¢??°gcd
//---------------------------------------

int main(void)
{
	int x, y;
	
	cin >> x;
	cin >> y;
	
	cout << gcd(x, y) << endl;
	 
	return 0;
}

//------------------------------------------
int gcd(int x, int y)
{
	int max, min;
	
	if(x >= y){
		max = x;
		min = y;
	}else{
		max = y;
		min = x;
	}
	
	
	int amari = max % min;
	if(!amari){
		return min;
	}
	return gcd(amari, min);
}
//--------------------------------------------

Measured memory_bytes: 3048
#include<stdio.h>
#include<stdlib.h> 
int main (int argc, char *argv[]) {
    int p;
    int q;
    int temp;
    while((p<=0||q<=0||(p+q)>16||p>16||q>16)){
      
      scanf("%d",&p);
      
      scanf("%d",&q);
    }

    if(p-q>=0){//pのほうが大きい時
      temp=q;
      q=p;
      p=temp;
    }
    if(8>=q){
      printf("Yay!");
    }else{
      printf(":(");
    }
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

template< typename G >
struct DoublingLowestCommonAncestor {
  const G &g;
  vector< int > dep;
  const int LOG;
  vector< vector< int > > table;

  DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
    table.assign(LOG, vector< int >(g.size(), -1));
  }

  void dfs(int idx, int par, int d) {
    table[0][idx] = par;
    dep[idx] = d;
    for(auto &to : g[idx]) {
      if(to != par) dfs(to, idx, d + 1);
    }
  }

  void build() {
    dfs(0, -1, 0);
    for(int k = 0; k + 1 < LOG; k++) {
      for(int i = 0; i < (int)table[k].size(); i++) {
        if(table[k][i] == -1) table[k + 1][i] = -1;
        else table[k + 1][i] = table[k][table[k][i]];
      }
    }
  }

  int query(int u, int v) {
    if(dep[u] > dep[v]) swap(u, v);
    for(int i = LOG - 1; i >= 0; i--) {
      if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
    }
    if(u == v) return u;
    for(int i = LOG - 1; i >= 0; i--) {
      if(table[i][u] != table[i][v]) {
        u = table[i][u];
        v = table[i][v];
      }
    }
    return table[0][u];
  }
};

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

    ll n;
    cin >> n;
    vector<vector<ll>> G(n);
    REP(i, n){
    	ll k;
    	cin >> k;
    	REP(j, k){
    		ll c;
    		cin >> c;
    		G[i].push_back(c);
    		G[c].push_back(i);
    	}
    }

    DoublingLowestCommonAncestor<vector<vector<ll>>> lca(G);
    lca.build();
    ll Q;
    cin >> Q;
    while(Q--){
    	ll x, y;
    	cin >> x >> y;
    	cout << lca.query(x, y) << endl;
    }
    return 0;
}


Measured memory_bytes: 18956
#include<iostream>
using namespace std;
int size[101],graph[101][100],cnt,times[101],timee[101];

void dfs(int x){
  if(times[x]==0){
    times[x]=++cnt;
    for(int i=0;i<size[x];++i){
      if(times[graph[x][i]]==0) dfs(graph[x][i]);
    }
    timee[x]=++cnt;
  }
}

int main(){
  int n,u,k,v; cin>>n;
  for(int i=0;i<n;++i){
    cin>>u>>k;
    size[u]=k;
    for(int j=0;j<k;++j){
      cin>>v;
      graph[u][j]=v;
    }
  }
  for(int i=1;i<=n;++i) dfs(i);
  for(int i=1;i<=n;++i) cout<<i<<" "<<times[i]<<" "<<timee[i]<<endl;
  return 0;
}



Measured memory_bytes: 3116
import numpy as np

t = np.array(list(input()), dtype='U1')
s = np.array(list(input()), dtype='U1')

ls = len(s)
lt = len(t)

eq = s[:, None] == t[None, :]
dp = [np.zeros(lt+1, dtype=np.int16)]

# solve
for i in range(ls):
    prev = dp[-1].copy()
    np.maximum(prev[1:], prev[:-1] + eq[i], out = prev[1:])
    np.maximum.accumulate(prev, out = prev)
    dp.append(prev)

# print([list(line) for line in dp])

# restore
l = dp[-1][-1]
res = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i-1][j-1]:
        res += s[i-1]
        i, j = i-1, j-1
        continue
    
    if dp[i-1][j] > dp[i][j-1]:
        i -= 1
    else:
        j -= 1

print(res[::-1])


Measured memory_bytes: 39244
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    string s;cin >> s;
    auto pre = s[0];
    auto ans = 0;

    for (auto i = 1; i < s.length(); ++i) {
        if (pre != s[i]){
            ans += 1;
            pre = s[i];
        }
    } 
    cout << ans << endl;

}

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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define ALL(x) x.begin(),x.end()
#define PB push_back
#define LL long long

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {
    _for(i,0,v.size()) os << v[i] << " ";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){
    for(typename set<T>::iterator it = v.begin();it != v.end();it++)
    os << *it <<" ";
    return os;
}

const int maxn = 1e5+5;
LL dp[maxn][2];
LL A[maxn];
int N;

int main()
{
    scanf("%d",&N);
    _for(i,0,N){
        scanf("%lld",&A[i]);
    }
    dp[0][0] = A[0] + A[1];
    dp[0][1] = -dp[0][0];
    _for(i,1,N-1){
        dp[i][0] = max(dp[i-1][0] + A[i+1],dp[i-1][1] + A[i+1]);
        dp[i][1] = max(dp[i-1][0] - 2*A[i] - A[i+1],dp[i-1][1] + 2*A[i] - A[i+1]);
    }
    printf("%lld\n",max(dp[N-2][0],dp[N-2][1]));

    return 0;
}


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

int main(){
     int a,b;
    cin>>a>>b;
     if(a>b){
      cout<<"a > b"<<endl;
     } if (a<b){
     cout<<"a < b"<<endl;
     }if(a==b){
    cout<<"a == b"<<endl;
   }
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(){
    ll N;
    cin >> N;
    ll A[5];
    for(int i=0;i<5;i++)
        cin >> A[i];
    
    ll count, arr1, arr2 = 0, dep1, dep2 = -1;
    for(int i=0;i<5;i++){
        arr1 = i;
        arr2 = dep2 + 1;
        dep1 = arr1;
        count = N / A[i];   // 全員移動するのに必要な台数
        if((N % A[i]) != 0)
            count++;
        dep2 = max(arr1 + count - 1, arr2);
        // cout << arr1 << ", " << dep2 << endl;
    }
    
    cout << dep2 + 1 << endl;

}

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

const int N = 810;

char s[N][N];
int vis[N][N];

int n, m, K, sx, sy;

bool ok(int x, int y){
	if(x==0 || y==0 || x==n-1 || y==m-1)	return 1;
	return 0;
}

typedef pair<int,int> pii;
int xl[4]={-1,1,0,0};
int yl[4]={0,0,-1,1};

int solve(){
    vis[sx][sy] = 0;
    queue<pii> Q;
	Q.push(make_pair(sx, sy));
    while(!Q.empty()){
		pii p = Q.front();	Q.pop();
		if(vis[p.first][p.second] == K){
			continue;
		}
		if(ok(p.first, p.second)){
			return 1;
		}
		for(int i=0; i<4; i++){
			int a = p.first + xl[i];
			int b = p.second + yl[i];
			if(a<0 || a>=n || b<0 || b>=m)	continue;
			if(s[a][b] == '#')	continue;
			if(vis[a][b] != -1)	continue;
			vis[a][b] = vis[p.first][p.second] + 1;
			Q.push(make_pair(a, b));
		}
    }

    for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(vis[i][j] != -1){
				vis[i][j] = K;
				Q.push(make_pair(i, j));
			}
		}
    }

    while(!Q.empty()){
		pii p = Q.front(); Q.pop();
		if(ok(p.first, p.second)){
			int ans = vis[p.first][p.second];
			if(ans % K == 0){
				return ans / K;
			} else {
				return ans / K + 1;
			}
		}
		for(int i=0; i<4; i++){
			int a = p.first + xl[i];
			int b = p.second + yl[i];
			if(a<0 || a>=n || b<0 || b>=m)	continue;
			if(vis[a][b] != -1)	continue;
			vis[a][b] = vis[p.first][p.second] + 1;
			Q.push(make_pair(a, b));
		}
    }
}

int main(){
	while(~scanf("%d %d %d", &n, &m, &K)){
		for(int i=0; i<n; i++){
			scanf("%s", s[i]);
			for(int j=0; j<m; j++){
                if(s[i][j] == 'S'){
					sx = i;
					sy = j;
					s[i][j] = '.';
                }
                vis[i][j] = -1;
			}
		}
        printf("%d\n", solve());
	}
	return 0;
}


Measured memory_bytes: 3712
using System;
using System.Linq;

namespace ALDS1_4_D
{
	class Program
	{
		static int limit;
		static int[] arr;

		static bool IsOK(int key)
		{
			int count = 0; int sum = 0;
			for (int i = 0; i < arr.Length; i++)
			{
				if (sum + arr[i] <= key) sum += arr[i];
				else
				{
					count++;
					sum = arr[i];
				}
			}
			count++;
			return limit >= count;
		}

		static int Binary_search()
		{
			int ng = -1;
			int ok = 1000000000;

			while (Math.Abs(ok - ng) > 1)
			{
				int mid = ng + (ok - ng) / 2;

				if (IsOK(mid)) ok = mid;
				else ng = mid;
			}

			return ok;
		}
		static void Main(string[] args)
		{
			int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
			arr = new int[x[0]]; limit = x[1];
			for (int i = 0; i < x[0]; i++) arr[i] = int.Parse(Console.ReadLine());
			Console.WriteLine(Math.Max(arr.Max(), Binary_search()));
		}
	}
}


Measured memory_bytes: 22880
import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
            B[i] = sc.nextInt();
        }
        long push = 0; 
        for (int i = A.length-1; i > -1; i--) {
            long Ai = A[i]+push;
            long Bi = B[i];
            if (Ai%Bi > 0) {
                push += Bi-(Ai%Bi);
            }           
        }
        System.out.println(push);
    }
    
}


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

int main()
{
    int N;
    cin >> N;
    vector<string> judge(N);
    for (int i=0; i<N; i++) cin >> judge[i];
    int AC=0;
    int WA=0;
    int TLE=0;
    int RE=0;
    for (int i=0; i<N; i++)
    {
        if (judge[i]=="AC") AC++;
        else if (judge[i]=="WA") WA++;
        else if (judge[i]=="TLE") TLE++;
        else RE++;
    }
    cout << "AC x " << AC << endl;
    cout << "WA x " << WA << endl;
    cout << "TLE x " << TLE << endl;
    cout << "RE x " << RE << endl;
}

Measured memory_bytes: 6424
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include<math.h>
#include <vector>
#include<bitset>
#include<map>
using namespace std;

int main() {
	char a; cin >> a;
	if ('a' <= a && a <= 'z')cout << 'a' << endl;
	else cout << 'A' << endl;
}

Measured memory_bytes: 3620
#include <atcoder/math>
#include <cstdio>

using namespace std;
using namespace atcoder;

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        long long n, m, a, b;
        scanf("%lld %lld %lld %lld", &n, &m, &a, &b);
        printf("%lld\n", floor_sum(n, m, a, b));
    }
    return 0;
}

Measured memory_bytes: 1736
#include <stdio.h>
#include <stdlib.h>
 
int partition(int*, int);
 
int main() {
  int i, n, key;
  int *a;
   
  scanf("%d",&n);
  a = (int*)malloc(sizeof(int) * n);
  for(i = 0;i < n;i++) 
    scanf("%d",&a[i]);
  key = partition(a, n);
  for(i = 0;i < n;i++) {
    if(i == key) printf("[%d]",a[i]);
    else printf("%d",a[i]);
    if(i != n-1) printf(" ");
  }
  printf("\n");
  free(a);
  return 0;
}
 
int partition(int* a, int r) {
  int j, change;
  int x = a[r-1];
  int i = -1;
  int k;
  for(j = 0;j < r-1;j++) {
    if(a[j] <= x) {
      i++;
      change = a[i];
      a[i] = a[j];
      a[j] = change;
    }
  }
  change = a[i+1];
  a[i+1] = a[r-1];
  a[r-1] = change;
  return i+1;
}

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

//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (n - 1); i > (a - 1); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define rirep(i, x) for (auto i = (x).rbegin(); i != (x).rend(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
// gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1LL << (n))
#define pcnt(x) __builtin_popcountll(x)
//配列内等要素削除
#define Unique(x) (x).erase(unique((x).begin(), (x).end()), (x).end())
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) (((n) * ((n) + 1)) / 2)
#define updiv(a, b) ((a + b - 1) / b)
#define cauto const auto &
using P = pair<int, int>;
using Graph = vector<vector<P>>;
template <class T>  //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>  //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {  //多次元初期化
  std::fill((T *)array, (T *)(array + N), val);
}
template <class A, class B>
bool chmax(A &a, const B &b) {  //最大値更新 返り値はbool
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class A, class B>
bool chmin(A &a, const B &b) {  //最小値更新 返り値はbool  int a, b;
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, 1, 1, -1, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END

signed main(void) {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int n;
  cin >> n;
  int ans;
  rep(i, 0, n) {
    int a;
    cin >> a;
    if (i == 0)
      ans = a;
    else
      ans = lcm(ans, a);
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 3620
import java.io.PrintWriter;
import java.util.Scanner;


public class Main {

  private static final Scanner in = new Scanner(System.in);
  private static final PrintWriter out = new PrintWriter(System.out);

  private static int[] nextArray(int n) {
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
      arr[i] = in.nextInt();
    }
    return arr;
  }

  public static void main(String[] args) {
    int a = in.nextInt();
    int b = in.nextInt();
    int c = in.nextInt();
    int d = in.nextInt();
    solve(a, b, c, d);
    out.flush();
    out.close();
  }

  private static void solve(int a, int b, int c, int d) {
    if (Math.abs(a - c) <= d) {
      out.println("Yes");
      return;
    }
    if (Math.abs(a - b) <= d && Math.abs(b - c) <= d) {
      out.println("Yes");
      return;
    }
    out.println("No");
  }


}

Measured memory_bytes: 23252
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;

int modd=1e9+7;

int main(){
  int h,w; cin>>h>>w;
  vector<vector<char> > arr(h);
  vector<char> temp(w);
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++) cin>>temp[j];
    arr[i]=temp;
  }

  vector<vector<long long> > tab(h);
  vector<long long> teemp(w);
  for(int i=0; i<h; i++) tab[i]=teemp;

  tab[0][0]=1;
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
            //cout<<arr[i][j];
      if(arr[i][j]=='.'){
        if(i+1<h) if(arr[i+1][j]=='.') tab[i+1][j]=(tab[i+1][j]+tab[i][j])%modd;
        if(j+1<w) if(arr[i][j+1]=='.') tab[i][j+1]=(tab[i][j+1]+tab[i][j])%modd;
      }
    }
    //cout<<endl;
  }

  cout<<tab[h-1][w-1]<<endl;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin >> s;
    int ans=-1,count=0;
    for(int i=0;i<s.size();i++){
        for(int j=i;j<s.size();j++){
            if(s[j]=='A'||s[j]=='C'||s[j]=='G'||s[j]=='T'){
                count++;
            }else{
                ans = max(ans,count);
                count=0;
                break;
            }
        }
        if(count>0){
            ans = max(ans,count);
            count = 0;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>

#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
typedef long long int ll;
const int INF = 1000000000;
const double PI = 3.1415926535;

int main()
{
    int a, b, c, k;
    cin >> a >> b >> c >> k;

    int ans = 0;
    if (k < a) {
        cout << k << endl;
        return 0;
    }
    else if (k < (a + b)) {
        cout << a << endl;
        return 0;
    }
    else {
        cout << a - (k - a - b) << endl;
        return 0;
    }
    return 0;
}

Measured memory_bytes: 3588
#include <iostream>

using namespace std;

int main()
{
    int a, b;

    cin >> a >> b;

    if(a > b) { cout << "a > b" << endl; }

    if(a < b) { cout << "a < b" << endl; }

    if(a == b) { cout << "a == b" << endl; }

    return 0;
}

Measured memory_bytes: 1156
A,B,C,D = map(int,input().split())
if A%D ==0:
  t = A//D
else:
  t = A//D+1
if C%B ==0:
  u = C//B
else:
  u = (C//B)+1
if t < u:
  print('No')
else:
  print('Yes')


Measured memory_bytes: 61780
n =int(input())
a = list(map(int, input().split()))
d = {}
for i in range(n):
  if a[i] in d:
    d[a[i]] += 1
  else:
    d[a[i]] = 1
result = 0
for k in d:
  if d[k] < k:
    result += d[k]
  elif d[k] > k:
    result += d[k] - k
print(result)


Measured memory_bytes: 17780
#include<stdio.h>

bool IsPrime(int a)
{
	for (int i=a-1; i>1; i--){
    	if(a%i == 0 ) return false;
    }
    return true;
}

int main()
{
 	int x;
  	scanf("%d", &x);
  
  	while(1){
		if(IsPrime(x)) break;
      	x++;
    }
  	printf("%d\n", x);
  
  	return 0;
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=201000;
int n,m,u,v,f[N];
int find(int x) { return f[x]==x?x:f[x]=find(f[x]); }
int main() {
	scanf("%d%d",&n,&m);
	rep(i,0,2*n) f[i]=i;
	rep(i,0,m) {
		scanf("%d%d",&u,&v); --u; --v;
		f[find(2*u)]=find(2*v+1);
		f[find(2*v)]=find(2*u+1);
	}
	rep(i,0,n) if (find(2*i)==find(2*i+1)) {
		printf("%lld\n",(ll)n*(n-1)/2-m);
		return 0;
	}
	int cl=0;
	rep(i,0,n) if (find(2*i)==find(0)) cl++;
	printf("%lld\n",(ll)cl*(n-cl)-m);
}


Measured memory_bytes: 896
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
p = LIST()
ans = 0
arr = [inf for _ in range(n)]
arr[0] = p[0]
for i in range(1, n):
    arr[i] = min(p[i], arr[i-1])
#print(arr)
for i in range(n):
    ans += 1 if arr[i] == p[i] else 0
    #print(i+1, arr, sum(arr[p[i] - 1:]), sum(arr[p[i] - 1:]) == i + 1)
print(ans)

Measured memory_bytes: 102092
#include<bits/stdc++.h>
 
using namespace std;
 
using int64 = long long;
 
int main() {
  string S, T;
  cin >> S >> T;
  S += S;
  if(S.find(T) != string::npos) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define REEP(i, N) for(ll i = N - 1; i >= 0; --i)
#define FOR(i,m,n) for(ll i = m; i < n; ++i)
#define RFOR(i,m,n) for(ll i = n - 1; i >= m; --i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define PB push_back
#define KIRIAGE(a, b) a += (b - a % b) % b // a を b の倍数値まで増やす
#define CEIL(c, a, b) if(a % b == 0) { c = a / b;} else { c = a / b + 1;} // a / b 以上の最小整数
#define sp(n) setprecision(n)
#define INF 1000000000
#define MOD 1000000007

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx4[4] = {1, 0, -1, 0};
int dy4[4] = {0, 1, 0, -1};
int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(void) {
	int n, m;
	cin>>n>>m;
	vector<P> hito(n);
	vector<P> point(m);
	REP(i, n) cin>>hito[i].first>>hito[i].second;
	REP(i, m) cin>>point[i].first>>point[i].second;
	REP(i, n) {
		ll max = INF;
		int ans = -1;
		REP(j, m) {
			if(abs(hito[i].first - point[j].first) + abs(hito[i].second - point[j].second) < max) {
				max = abs(hito[i].first - point[j].first) + abs(hito[i].second - point[j].second);
				ans = j + 1;
			}
		}
		cout<<ans<<endl;
	}
}


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

int main() {
  int n, a;
  int remainder;
  cin >> n >> a;
  remainder = n % 500;
  //cout << remainder << endl;
  if (remainder <= a) {
    cout << "Yes" <<endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
int main(){
  int c=0,i=0;
  string s,t;
  cin>>s>>t;
  int x=s.length();
  while(x--){
    if(s[i]!=t[i])
      c++;
 i++;
  }cout<<c;
  return 0;
}

Measured memory_bytes: 3924
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n;
string s, t;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;
  cin >> s >> t;

  REP(i, n) {
    cout << s[i] << t[i];
  }

  cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e9
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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

signed main(){
   int n;
   cin>>n;
   vector<int>l(n);
   REP(i,n) cin>>l[i];
   sort(ALL(l));
   ll ans=0;
   for (int i = 0; i < n; i++)
   {
       for (int j = i+1; j < n; j++)
       {
         //  cerr<<lower_bound(l.begin()+j,l.end(),l[i]+l[j])-(l.begin()+(j+1))<<endl;
           ans+=lower_bound(l.begin()+j,l.end(),l[i]+l[j])-(l.begin()+j+1);
       }
       //cerr<<ans<<endl;
   }
   cout<<ans<<endl;

   
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,ans=0;
    map<string,ll> mp;
    cin>>n;
    rep(i,n){
        string s,t;
        cin>>s;
      t=s;
        vector<char> v;
        rep(i,10){
            v.pb(s[i]);
        }
        sort(all(v));
        rep(i,10){
            t[i]=v[i];
        }
        //cout<<t<<endl;
        auto itr=mp.find(t);
        if(itr!=mp.end()){
            // cout<<i<<" "<<itr->second<<endl;
            ans+=mp[t];
            mp[t]++;
        }
        else{
            mp[t]=1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long long  int i,j,n,x,tp,num=0,m=1;
    cin>>n>>x;
    for(i=0; i<n; i++)
    {
        cin>>tp;
        num+=tp;
        if(num<=x)
            m++;
    }
    cout<<m<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
signed main(){
    int n;cin >> n;
    int a[n];
    rep(i,n){
        cin >> a[i];
        a[i]--;
    }
    vector<int> t;
    t.push_back(0);
    rep(i,n){
        int hoge = t.back();
        int to = a[to];
        if(to == 1){
            cout << i+1 << endl;
            return 0;
        }
        t.push_back(to);

    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 2168
# -*- coding: utf-8 -*-
import random
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline

INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def warshall_floyd(g):
    N = len(g)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    return g


def slv(N, M, L, ABC, Q, ST):
    g = [[INF]*(N) for _ in range(N)]

    for a, b, c in ABC:
        if c > L:
            continue
        g[a-1][b-1] = c
        g[b-1][a-1] = c

    d = warshall_floyd(g)

    gg = [[INF]*(N) for _ in range(N)]
    for u in range(N):
        for v in range(N):
            if d[u][v] <= L:
                gg[u][v] = 1

    d = warshall_floyd(gg)

    for s, t in ST:
        c = d[s-1][t-1]
        if c != INF:
            print(c-1)
        else:
            print(-1)


def main():
    N, M, L = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    Q = read_int()
    ST = [read_int_n() for _ in range(Q)]

    (slv(N, M, L, ABC, Q, ST))


if __name__ == '__main__':
    main()


Measured memory_bytes: 72284
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define N 10000000

int main(void){
	vector<bool> isprime(N+1);
	for(int i=0;i<isprime.size();i++) isprime[i]=true;
	int upto = (int)sqrt(isprime.size());
	isprime[1]=false;
	for(int i=2;i<=upto;++i){
		if(isprime[i]){//消されてなければその倍数を消す
			for(int j=2;i*j<isprime.size();++j) isprime[i*j] = false;
		}
	}
	int n;
	while(cin>>n,n){
		for(int i=n;i>=13;--i)
			if(isprime[i]&&isprime[i-2]&&isprime[i-6]&&isprime[i-8]){cout<<i<<endl;break;}
	}
	return 0;
}

Measured memory_bytes: 2328
use std::io::{stdin, Read};
use std::str::FromStr;

// https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn main() {
    let n = read::<usize>();
    let s = read::<String>().chars().collect::<Vec<_>>();
    let mut west = vec![0; n];
    for i in 1..n {
        west[i] = west[i - 1] + if s[i - 1] == 'W' { 1 } else { 0 }
    }

    let mut east = vec![0; n];
    for i in 1..n {
        east[n - i - 1] = east[n - i] + if s[n - i] == 'E' { 1 } else { 0 }
    }

    let mut ans = usize::max_value();
    for i in 0..n {
        ans = std::cmp::min(ans, west[i] + east[i])
    }

    println!("{}", ans)
}


Measured memory_bytes: 14588
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define vec vector<ll>
#define mat vector<vector<ll> >
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e4+7;

int MAX=1000100;
vector<vector<int> >trie(MAX,vector<int>(26));
vector<int>leaf(MAX);

int sz=1;
void add_string(string s){
    int v=0;
    for(auto c:s){
        if(!trie[v][c-'a']){
            trie[v][c-'a']=sz;
            sz++;
        }
        v=trie[v][c-'a'];
    }
    leaf[v]=1;
}

signed main(){
    int n;cin>>n;
    vector<string>a(n);
    rep(i,n){
        string s;cin>>s;
        reverse(all(s));
        add_string(s);
        a[i]=s;
    }
    int ans=0;
    rep(i,n){
        string s;
        s=a[i];
        vector<int>cnt(26);
        for(auto c:s){
            cnt[c-'a']++;
        }
        int v=0;
        rep(j,s.size()){
            rep(x,26){
                if(cnt[x]&&trie[v][x]){
                    ans+=leaf[trie[v][x]];
                }
            }
            cnt[s[j]-'a']--;
            v=trie[v][s[j]-'a'];
        }
        ans--;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 146184
import numpy as np


def main():
    N, W = list(map(int, input().split(' ')))
    items = np.array([list(map(int, input().split(' '))) for _ in range(N)])
    dp = np.zeros((N, W + 1))
    dp[0, items[0, 0]:] = items[0, 1]
    for n in range(1, N):
        weight, value = items[n, 0], items[n, 1]
        dp[n, :] = dp[n - 1, :]
        dp[n, weight:] = np.fmax(
            dp[n, weight:],
            value + dp[n - 1, :(- weight)]
        )
    print(int(dp[N - 1, W]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 92052
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int sum = 0;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i = 0; i < N; i++) {
            arr.add(sc.nextInt());
            sum += arr.get(i);
        }
        Collections.sort(arr, Collections.reverseOrder());

        if(arr.get(M - 1) * (M * 4) < sum) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}


Measured memory_bytes: 21844
//From Naruto to Hokage
//#include <RJ>
#include<bits/stdc++.h>
using namespace std;

#define ll          long long
#define pb          push_back
#define eb          emplace_back
#define endl        '\n'
#define mii         map<ll,ll>
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define INF         (1ll<<60)
#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 present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
const int N=100005;
void solve(){
    ll n,l;
    cin>>n>>l;
    ll minn=min(l,l+n-1);
    ll maxx=max(l,l+n-1);
    ll temp;
    if(minn<=0 && maxx>=0) temp=0;
    else if(minn>0 && maxx>0) temp=minn;
    else temp=maxx;
    ll ans=n*l+(n*(n-1))/2-temp;
    cout<<ans;
}
signed main()
{
    ios
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--){
        solve();
    }
    time
    return 0;
}

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

using namespace std;

typedef long long ll;
#define mod 1000000007
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define repc(i, a, b, c) for (ll i = a; (c > 0 ? i < b : i > b) and c != 0; i += c)
#define fi first
#define si second
#define pb push_back
#define all(name) (name.begin(), name.end())
#define fact(n) vector<ll> ft(1, 1LL);rep(i, 1, n+1)ft.pb((ft[i-1]*i)%mod);
#define mod_in(a) power(a, mod - 2)
#define ncr(n, r) ((ft[n]*mod_in((ft[r]*ft[(n)-(r)])%mod))%mod)
#define deb(x) cerr << "[" << #x << " " << x << "]\n";
#define int ll

ll power(ll x, ll y) {
     ll res = 1;x %= mod;
    while (y > 0) {
        if (y & 1)res = (res*x) % mod;
        y = y>>1;
        x = (x*x) % mod;
    }
    return res%mod;
}
/*================================================================*/




int arr[100005];
void solve() {
    int n, k, ans = 0;
    cin >> n >> k;
    rep(i, 1, k+1){
        ans = (ans + (power(k/i, n)*arr[i]))%mod;
        // deb
    }
    cout << ans;
}

signed main() {
    int t = 1;
    // cin >> t;
    rep(i, 1, 1e5+1)arr[i] += i;
    rep(i, 1, 1e5+1)repc(j, i*2, 1e5+1, i)arr[j] -= arr[i];
    rep(i, 0, 5)deb(arr[i]);
    while(t--){
        solve();
    }
}


Measured memory_bytes: 4408