akhauriyash/Code-Regression huggingface dataset:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

lim = M+10  # 必要そうな階乗の限界を入れる
fact = [1] * (lim+1)
fact_inv = [1] * (lim+1)
for n in range(1, lim+1):
    fact[n] = (fact[n-1] * n) % mod
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
    fact_inv[n-1] = (n * fact_inv[n]) % mod
def C(n, r):
    return (((fact[n] * fact_inv[r]) % mod) * fact_inv[n-r]) % mod

def P(n, r):
    return fact[n]*fact_inv[n-r]%mod

ans = 0
for k in range(N+1):
    now = C(N, k)
    now *= P(M-k, N-k)
    if k%2 == 1:
        now = -now
    ans += now
    ans %= mod
ans *= P(M, N)
ans %= mod
print(ans)


Measured memory_bytes: 49260
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

int main(){
  double a, b, c, cRad; //radian
  double s, l, h;
  double pi = acos(-1); // pi = 3.1415926535...
  
  cin >> a >> b >> cRad;

  s = a * b * sin(pi / 180 * cRad) / 2;
  c = sqrt( a*a + b*b - 2 * a * b * cos(pi / 180 * cRad) );
  l = a + b + c;
  h = 2 * s / a;
  
  printf("%f\n%f\n%f\n", s, l, h);
  
  return 0;
}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    ll N;
    cin >> N;
    vector<ll> vec(N);
    rep(i,N){
        cin >> vec[i];
    }
    ll all_sum = 0;
    ll sub_sum = 0;
    rep(i,N){
        all_sum += vec[i];
    }
    for (int i = 1; i <= N - 2; i += 2){
        sub_sum += (2 * vec[i]);
    }
    vector<ll> ans(0);
    ans.push_back(all_sum - sub_sum);
    rep(i,N - 1){
        ans.push_back(2 * vec[i] - ans[i]);
    }
    rep(i,N){
        cout << ans[i] << " ";
    }
    cout << endl;
}


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 1000000000
#define LLINF 1000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N,M;
int cnt[100100];
int state[100100];
int main(){
	cin >> N >> M;
	for(int i=0;i<N;i++){
		cnt[i]=1;
		state[i]=0;
	}
	state[0]=2;
	for(int i=0;i<M;i++){
		int a,b;
		cin >> a >> b;
		a--;b--;
		if(state[a]==2){
			if(cnt[b]>0)state[b]=1;
			else state[b]=2;
			state[a]=0;
		}else if(state[a]==1){
			state[b]=1;
		}else{
			if(state[b]==2){
				state[b]=1;
			}
		}
		cnt[a]--;cnt[b]++;
		if(cnt[a]==0)state[a]=0;
	}
	int ans = 0;
	for(int i=0;i<N;i++){
		if(state[i]>0)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    a = inputList()
    
    flg = True
    for i,vol in enumerate(a):
        if i == 0:
            continue
        if vol != a[i-1]:
            flg = False
            break
            
    if flg == True:
        print(0)
        sys.exit()
    
    ans = INF
    for i in range(-100,101):
        cst = 0
        for j,vol in enumerate(a):
            cst += (vol-i)**2
            
        if ans > cst:
            ans = cst
            #print("{} {}".format(cst,ans))
            
    print(ans)
    
if __name__ == "__main__":
	main()


Measured memory_bytes: 40816
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>

int gcd(int a,int b){
	return b ? gcd(b, a % b) : a; 
}

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int>a(n), l(n + 1), r(n + 1);

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

	l[0] = 0;
	r[n] = 0;

	for (int i = 0; i < n; i++) {
		l[i + 1] = gcd(l[i], a[i]);
		r[n - i - 1] = gcd(r[n - i], a[n - i - 1]);
	}

	int ans = 1;

	for (int i = 0; i < n; i++)
		ans = max(ans, gcd(l[i], r[i + 1]));

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int n, k, r, s, p;
	cin >> n >> k >> r >> s >> p;
	string t;
	cin >> t;
	string sub[100001];
	bool visit[100001] = {};
	map<pair<char, char>, int> te;
	te[make_pair(0, 'r')] = 0;
	te[make_pair(0, 's')] = r;
	te[make_pair(0, 'p')] = 0;
	te[make_pair(1, 'r')] = 0;
	te[make_pair(1, 's')] = 0;
	te[make_pair(1, 'p')] = s;
	te[make_pair(2, 'r')] = p;
	te[make_pair(2, 's')] = 0;
	te[make_pair(2, 'p')] = 0;
	int count = 0;
	for (int i = 0; i < t.size(); ++i)
	{
		if(!visit[i])
		{
			++count;
			sub[i] = "";
			for (int j = i; j < t.size(); j += k)
			{
				visit[j] = 1;
				sub[i] += t[j];
			}
		}
	}
	int ans = 0;
	int dp[100001][3] = {};
	for (int i = 0; i < count; ++i)
	{
		for (int j = 0; j < sub[i].size(); ++j)
		{
			for (int kk = 0; kk < 3; ++kk)
			{
				dp[j][kk] = 0;
			}
		}
		dp[0][0] = te[make_pair(0, sub[i][0])];
		dp[0][1] = te[make_pair(1, sub[i][0])];
		dp[0][2] = te[make_pair(2, sub[i][0])];
		for (int j = 1; j < sub[i].size(); ++j)
		{
			dp[j][0] = max(dp[j-1][1], dp[j-1][2]) + te[make_pair(0, sub[i][j])];
			dp[j][1] = max(dp[j-1][2], dp[j-1][0]) + te[make_pair(1, sub[i][j])];
			dp[j][2] = max(dp[j-1][0], dp[j-1][1]) + te[make_pair(2, sub[i][j])];
		}
		ans += max(dp[sub[i].size()-1][0], max(dp[sub[i].size()-1][1], dp[sub[i].size()-1][2]));
	}
	cout << ans << endl;
 
	return 0;
}

Measured memory_bytes: 6528
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)){
			int h = sc.nextInt();
			int w = sc.nextInt();
			int[][] population = new int[h][w];
			int[] hSum = new int[h]; //hの人口総和
			int[] wSum = new int[w]; //wの人口総和
			for (int i=0; i<h; i++) {
				for (int j=0; j<w; j++) {
					population[i][j] = sc.nextInt();
				}
			}
			int min = 10000000;
			for (int i=0; i<h; i++) {
				for (int j=0; j<w; j++) {
					int count = 0;
					for (int k=0; k<h; k++) {
						for (int l=0; l<w; l++) {
							int toh = Math.abs(k-i);
							int tow = Math.abs(j-l);
							count += Math.min(toh, tow) * population[k][l];
						}
					}
					min = Math.min(min, count);
				}
			}
			System.out.println(min);
		}
	}
}


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

int main() 
{
  char number[1100];
  int i;
  int ans = 0;
  while(true){
    cin >> number;
    if(number[0] == '0'){
      return 0;
    }else{
      for(i = 0;number[i] != '\0';++i){
        ans += number[i] - '0';
      }
      cout << ans << endl;
      ans = 0;
    }
  }
}


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

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

    if(a>b){
        cout << a-1 << endl;
        // return 0;
    }
    else{
        cout << a << endl;
        // return 0;
    } 
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String string = sc.nextLine();
		char[] line = string.toCharArray();

		char c = ' ';
		for (int i = 0; i < line.length; i++) {
			if (Character.isUpperCase(line[i])) {
				c = Character.toLowerCase(line[i]);
			} else if (Character.isLowerCase(line[i])) {
				c = Character.toUpperCase(line[i]);
			} else {
				c = line[i];
			}
			System.out.print(c);
		}
		System.out.println();
	}

}

Measured memory_bytes: 26880
#include<bits/stdc++.h>
    using namespace std;
     
    #define int long long
    #define hell 998244353 
    #define endl "\n"
     
    int min(int a, int b){
     
        if(a>b)
            return b;
        return a;
    }
     
    int max(int a, int b){
     
        if(a>b)
            return a;
        return b;
    }
     
     
int32_t main()
{
    int n;
    cin>>n;

    map<string, int> freq; 
    string s;


    for(int i=0;i<n;i++)
    {
        cin>>s;

        sort(s.begin(), s.end());
        freq[s]++;
    }

    int count = 0;
    for(auto x:freq)
        count += (freq[x.first]*(freq[x.first]-1))/2;


    cout<<count;
    

}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define fore(i, a) for (auto &i : a)
#define all(x) (x).begin(), (x).end()
//#pragma GCC optimize ("-O3")
using namespace std;
void _main();
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    _main();
}
typedef long long ll;
const int inf = INT_MAX / 2;
const ll infl = 1LL << 60;
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;
}
int A, B;
void _main()
{
    cin >> A >> B;
    int k = (A + B) / 2;
    if (abs(A - k) == abs(B - k))
        cout << k << endl;
    else
        cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <complex>
#include <cassert>
#include <vector>
#include <iomanip>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef vector<string> vs;
typedef pair<int, int> P;
ll const mod = 1000000007;

bool check(int n, string s){
    rep(i, s.size()){
        if (s[i] == 'X') s[i] = n + '0';
    }
    int pl = s.find('+');
    int eq = s.find('=');
    vs ss(3);
    ss[0] = s.substr(0, pl);
    ss[1] = s.substr(pl + 1, eq - pl - 1);
    ss[2] = s.substr(eq + 1);
    rep(i, 3)if (ss[i].size() != 1 && ss[i][0] == '0') return false;

    rep(i, 3){
        reverse(all(ss[i]));
        ss[i].resize(ss[2].size(), '0');
    }
    int c = 0;
    rep(i, ss[2].size()){
        if ((ss[0][i] + ss[1][i] - 2 * '0' + c) % 10 == ss[2][i] - '0'){
            c = ss[0][i] + ss[1][i] - 2 * '0' + c >= 10;
        }
        else {
            return false;
        }
    }
    return true;
}

int solve(string const& s){
    rep(i, 10)if (check(i, s)){
        return i;
    }
    return -1;
}

int main(){
    string s;
    while (cin >> s){
        int ans = solve(s);
        if (ans == -1) cout << "NA";
        else cout << ans;
        cout << endl;
    }
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MAX 100000
#define INF 1000000000
using ll=long long;

ll modpow(ll a,ll n,ll mod){
  ll res=1;
  while(n>0){
    if(n&1){       //nのbitと...00001を比較  nが2で割り切れるならtrue
      res=(res*a)%mod;
    }
    a=(a*a)%mod;
    n>>=1;
  }
  return res;
}

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

ll fac[MAX],finv[MAX],inv[MAX];

void COMinit(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for(int i=2;i<MAX;i++){
    fac[i]=(fac[i-1]*i)%MOD;
    inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
    finv[i]=finv[i-1]*inv[i]%MOD;
  }
}

ll COM(int n,int k){
  if(n<k){
    return 0;
  }
  if(n<0||k<0){
    return 0;
  }
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

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

  COMinit();
  ll ans=0;
  for(int N=1;N<=S/3;N++){
    int x=S-3*N;
    ans+=COM(x+N-1,N-1);
    ans%=MOD;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 5976
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	class UnionFind {
		int[] par, rank;
		UnionFind(int n) {
			par  = new int[n + 1];
			rank = new int[n + 1];
			init(n);
		}
		void init(int n) {
			for (int i = 0; i <= n; i++) {
				par[i] = i;
				rank[i] = 0;
			}
		}
		
		int find(int x) {
			if (par[x] == x)
				return x;
			else
				return par[x] = find(par[x]);
		}
		
		void unite(int x, int y) {
			x = find(x);
			y = find(y);
			if (x == y)
				return;
			
			if (rank[x] < rank[y]) {
				par[x] = y;
			} else {
				par[y] = x;
				if (rank[x] == rank[y])
					rank[x]++;
			}
		}
		
		boolean same(int x, int y) {
			return find(x) == find(y);
		}
	}

	class Edge {
		int u, v;
		double cost;
		Edge(int u, int v, double cost) {
			this.u = u; this.v = v; this.cost = cost;
		}
	}
	class Pair {
		int y, x;
		Pair(int y, int x) {
			this.y = y; this.x = x;
		}
	}

	void run() {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();

		Pair[] pairs = new Pair[n + 1];
		for (int i = 1; i <= n; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			pairs[i] = new Pair(y, x);
		}

		Edge[] edges = new Edge[m];
		double sum = 0;
		for (int i = 0; i < m; i++) {
			int p = scan.nextInt();
			int q = scan.nextInt();
			int _y = Math.abs(pairs[p].y - pairs[q].y);
			int _x = Math.abs(pairs[p].x - pairs[q].x);
			double cost = Math.sqrt(_y * _y + _x * _x);
			sum += cost;
			edges[i] = new Edge(p, q, cost);
		}
		
		Arrays.sort(edges, new Comparator<Edge>() {
			@Override
			public int compare(Edge e1, Edge e2) {
				return e1.cost - e2.cost > 0 ? -1 :
				       e1.cost - e2.cost < 0 ?  1 :
				    	                        0 ;
			}
		});
		UnionFind uf = new UnionFind(n);
		
		double res = 0;
		for (int i = 0; i < m; i++) {
			Edge e = edges[i];
			if (!uf.same(e.u, e.v)) {
				uf.unite(e.u, e.v);
				res += e.cost;
			}
		}
		System.out.printf("%.4f\n", sum - res);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}


Measured memory_bytes: 68676
# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0)
# define div ghjfghjg
vector < ll > div;
ll get(ll x)
{
    for (auto it : div)
        while (!(x % it))
            x /= it;
    return x;
}
map < ll , int > s;
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n;
    IOS;
    fi>>n;
    auto prim = [&](int x)
    {
        for (int i = 2;1ll * i * i <= x;++i)
            if (!(x % i)) return 0;
        return 1;
    };
    for (int i = 2;i <= 2500;++i)
        if (prim(i))
            div.push_back(1ll * i * i * i);
    int ans = 0;
    int ok = 0;
    set < ll > w;
    while (n --)
    {
        ll cnt;
        fi>>cnt;
        cnt = get(cnt);
        if (cnt == 1)
            ok = 1;
        else
            ++s[cnt],w.insert(cnt);
    }
    ans = ok;
    for (auto it : w)
    {
        ans += max(s[it],s[get(it * it)]);
        s[it] = s[get(it * it)] = 0;
    }
    fo << ans << '\n';
    return 0;
}




Measured memory_bytes: 17408
D = int(input())
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
res = 0
ans = [-1]*D
llst = [0]*26

def calc(d,x):
    day = d+1
    res = s[d][x]
    for i in range(26):
        if x == i: continue
        res -= c[i]*(day-llst[i])
    return res

for i in range(D):
    mx = -1
    mxv = -float("inf")
    for j in range(26):
        v = calc(i,j)
        if v >= mxv:
            mx = j
            mxv = v
    ans[i] = mx+1
    llst[mx] = i+1
for i in range(D): print(ans[i])

Measured memory_bytes: 9420
use v5.18;
use warnings;
use List::Util qw ( sum );
sub read_line { chomp(my $str = <STDIN>); $str }
sub splited_read_line { split / /, read_line }

my $n = read_line;
my @nums = splited_read_line;
my @abss = do {
  my $i = 1;
  map { $_ - $i++ } @nums;
};

# 中央値
my @sorted = sort { $a <=> $b } @abss;
my $median = $sorted[int($n / 2)];

my $i = 1;
say sum map { abs($_ - ($median + $i++)) } @nums;

Measured memory_bytes: 46872
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <string>
#include <cmath>
#include <map>
#include <iomanip>
#include <tuple>
#include <functional>
#include <bitset>
#define INF 1000000009
#define LINF 1000000000000000009
#define double long double
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> PP;
template<class T> bool chmax(T &a, const T&b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T&b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }

int main(){
	ll n, m, v, p;
	cin >> n >> m >> v >> p;
	vector<ll> a(n);
	for (ll i = 0; i < n; i++) cin >> a[i];
	sort(all(a));
	ll ng = -1, ok = n + 1;
	while (ok - ng > 1) {
		int mid = (ok + ng) / 2;
		ll cnt = 0;
		for (ll i = mid + 1; i < n - p + 1; i++) {
			cnt += a[i] - a[mid];
			//if (mid == 1) cout << i << ' ' << cnt << endl;
		}
		if (cnt > m*(n-v) || a[n - p] - a[mid] > m) {
			ng = mid;
		}
		else {
			ok = mid;
		}
		//cout << ng << ' ' << ok << endl;
	}
	cout << n - ok << endl;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {
    public static void main(String[] args) {

        // a[]の作成
        int[] a = new int[101010];
        a[0] = 0;
        a[1] = 0;
        a[2] = 0;
        a[3] = 1;
        a[4] = 0;
        for (int i = 5; i < 101010; i++) {
            if (isLike2017(i)) {
                a[i] = 1;
            } else {
                a[i] = 0;
            }
        }

        // s[]：累積和の作成
        int[] s = new int[101011];
        s[0] = 0;
        for (int i = 1; i < 101011; i++) {
            s[i] = s[i - 1] + a[i - 1];
        }

        Scanner sc = new Scanner(System.in);
        int Q = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < Q; i++) {
            String[] query = sc.nextLine().split(" ");
            int l = Integer.parseInt(query[0]);
            int r = Integer.parseInt(query[1]);
            System.out.println(s[r + 1] - s[l]);
        }

        sc.close();
    }

    // エラストテネスの篩
    public static boolean isPrime(int n) {
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static boolean isLike2017(int n) {
        int val = (n + 1) / 2;
        if (isPrime(n) && isPrime(val)) {
            return true;
        }
        return false;
    }

}


Measured memory_bytes: 119004
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void yn(bool j){cout << (j ? "Yes" : "No") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> long long bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

int main(){
    ll N, K; cin >> N >> K; 
    vector<ll> a(N), d(N, INF);
    rep(i, N){
        cin >> a[i];  
        a[i]--;
    }
    ll node = 0, par = -1;
    ll start = INF, last = INF;
    rep(_, N){
        if (par == -1){
            chmin(d[node], 0);
            par = node;
            node = a[node];
        }else{
            if (!chmin(d[node], d[par] + 1)){
                start = node;
                last = par;
                break;
            }
            par = node;
            node = a[node];
        }
    }
    // debug(d);
    ll dur;
    if (start != INF) dur = d[last] - d[start] + 1;
    else dur = N + N;
    ll now = 0;
    while(0 < K){
        K--;
        now = a[now];
        if (now == start) K = K % dur;
        // pt(now, K);
        if (K == 0){
            pt(now + 1);
            return 0;
        }
    }
}

Measured memory_bytes: 6420
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T> &p){ cout << "[" << p.first << ", " << p.second << "]"; return os; }

#define Sq(x) (x)*(x)
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Unique(a) a.erase(unique(Range(a)), a.end())
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) { for(const auto &e : xs) cout << e << " "; cout << "\n"; }
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")
#define Return(expr) { Cout(expr); return 0; }
#define vc vector
#define Mini(a, x) a = min(a, x)
#define Maxi(a, x) a = max(a, x)

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(int, a, b, c, d);
    Cout(a+a*a+a*a*a);
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n+1;i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end())
typedef long long ll;

int main(){
  int n,k;
  cin >> n >> k;
  string s;
  cin >> s;
  vector<char> ini(0);//initials
  vector<int> r(0);//runlength
  
  int seek = 0;
  while(seek < n){
    int start = seek;
    int freq = 0;
    while(s[seek] == s[start]){
      seek ++;
      freq ++;
    }
    ini.push_back(s[start]);
    r.push_back(freq);
  }
  
  int m = r.size();//length of r;
  vector<int> c(m);//cumlative sum
  
  rep(i,m) c[i] = c[i-1] + r[i];
  
  int ans = 0;
  seek = 0;
  
  //corner
  if(m == 1){
    cout << n << endl;
    return 0;
  }
  
  while(seek < m){
    //skip処理
    if(ini[seek] == '1'){
      seek ++;
      continue;
    }
    
    //本処理
    int rightend = min(seek + 2*k - 1, m-1);
    int leftend = max(seek - 2, -1);
    ans = max(ans,c[rightend] - c[leftend]);
    seek ++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1400
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      
      String[] input = sc.nextLine().split(" ");
      int m = Integer.parseInt(input[0]);
      int f = Integer.parseInt(input[1]);
      int b = Integer.parseInt(input[2]);
      
      if(b > m + f) {
         System.out.println("NA"); 
      } else if (b > m){
         System.out.println(b - m);
      } else {
         System.out.println("0");
      }
   }
}


Measured memory_bytes: 26208
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int n,f[N],dep[N];
vector<int>G[N];
void dfs(int u,int fa)
{
	for(int i=0;i<G[u].size();i++)
	if(G[u][i]!=fa)dep[G[u][i]]=dep[u]+1,dfs(G[u][i],u);
}
int main()
{
	scanf("%d",&n);
	f[0]=1,f[1]=0;
	for(int i=2;i<=n;i++)if(f[i-1]&&f[i-2])f[i]=0;else f[i]=1;
	for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);
	dfs(1,0);
	int t=1;
	for(int i=2;i<=n;i++)if(dep[i]>dep[t])t=i;
	for(int i=1;i<=n;i++)dep[i]=0;
	dfs(t,0);
	t=0;
	for(int i=1;i<=n;i++)t=max(t,dep[i]);
	if(f[t])puts("First");else puts("Second");
}

Measured memory_bytes: 25216
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define LINT long long

int main(){
  int N, T, A;
  cin>>N>>T>>A;
  int ans;
  double temp=1000;
  int H[N];
  double work;
  REP(i, N){
    cin>>H[i];
    work = (double)T-0.006*(double)H[i]-(double)A;
    if(abs(temp) > abs(work)){
      temp = (double)T-0.006*(double)H[i]-(double)A;
      ans = i+1;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
object Main extends App{
  import scala.io.StdIn.readLine
  import scala.io.StdIn.readInt
  
  val n = readInt
  val a = readLine.split(" ").map(_.toInt).toList
  val b = readLine.split(" ").map(_.toInt).toList
  
  def dicNum(x:List[Int]):Long ={
    def dicNumRe(acc:Long,x:List[Int]):Long =
    x match{
      case Nil => acc
      case _ => dicNumRe(acc + (x.filter(_ < x.head).length)*((1 to (x.length - 1)).product) , x.tail)
    }
    dicNumRe(0,x)
  }
  
  println(math.abs(dicNum(a)-dicNum(b)).toString)
}


Measured memory_bytes: 54932
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define INTINF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 
 
int main() {
	int ans = 0;
	int tmp;
	int n;
	cin >> n;
	vector<int> a;
	REP(i, n){
		cin >> tmp;
		auto it = upper_bound(a.begin(), a.end(), -tmp);
		if(it == a.end()){
			ans++;
			a.push_back(-tmp);
		}
		else {
			*it = -tmp;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < n; i++)
using ll = long long;
using namespace std;
const int INF = 1e9;

int main() {

    ll N, A, B;
    cin >> N >> A >> B;

    cout << max((ll)0, ((B * (N - 1)) + A) - (A * (N - 1) + B) + 1) << endl;

    return 0;
}

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

int main() {
  vector<vector<int>> a(3, vector<int>(3));
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      cin>>a.at(i).at(j);
    }
  }
  int n; cin >> n;
  vector<vector<int>> h(3, vector<int>(3, 0));
  for(int i = 0; i < n; i++){
    int b; cin >> b;
    for(int j = 0; j < 3; j++){
      for(int k = 0; k < 3; k++){
        if(a.at(j).at(k) == b) h.at(j).at(k) = 1;
      }
    }
  }
  string out = "No";
  if(h.at(0).at(0) == 1 & h.at(1).at(1) == 1 & h.at(2).at(2) == 1) out = "Yes";
  if(h.at(0).at(2) == 1 & h.at(1).at(1) == 1 & h.at(2).at(0) == 1) out = "Yes";
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
      if(h.at(i).at(j) == 1){
        if(h.at(i).at((j+1)%3) == 1 & h.at(i).at((j+2)%3) == 1){
          out = "Yes";
        }
        if(h.at((i+1)%3).at(j) == 1 & h.at((i+2)%3).at(j) == 1){
          out = "Yes";
        }
      }
    }
  }
  cout << out;
}

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

int main() {
	double weight;
	while(cin >> weight){
		if(weight <= 48.00) cout << "light fly" << endl;
		if(weight > 48.00 && weight <=51.00) cout << "fly" << endl;
		if(weight > 51.00 && weight <=54.00) cout << "bantam" << endl;
		if(weight > 54.00 && weight <=57.00) cout << "feather" << endl;
		if(weight > 57.00 && weight <=60.00) cout << "light" << endl;
		if(weight > 60.00 && weight <=64.00) cout << "light welter" << endl;
		if(weight > 64.00 && weight <=69.00) cout << "welter" << endl;
		if(weight > 69.00 && weight <=75.00) cout << "light middle" << endl;
		if(weight > 75.00 && weight <=81.00) cout << "middle" << endl;
		if(weight > 81.00 && weight <=91.00) cout << "light heavy" << endl;
		if(weight > 91.00) cout << "heavy" << endl;
	}
	return 0;
}


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

const int MAXN = 1010;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
int H, W;
char A[MAXN][MAXN];
int dist[MAXN][MAXN];

int main() {
	scanf("%d %d", &H, &W);
	for (int i = 0; i < H; i++) {
		scanf("%s", A[i]);
	}

	vector<pair<int, int>> que;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (A[i][j] == '#') {
				que.emplace_back(i, j);
				dist[i][j] = 0;
			} else {
				dist[i][j] = -1;
			}
		}
	}

	for (size_t i = 0; i < que.size(); i++) {
		int a, b; tie(a, b) = que[i];
		for (int d = 0; d < 4; d++) {
			int newa, newb; tie(newa, newb) = make_pair(a+dx[d], b+dy[d]);
			if (newa < 0 || newa >= H || newb < 0 || newb >= W || dist[newa][newb] != -1) continue;
			dist[newa][newb] = dist[a][b]+1;
			que.emplace_back(newa, newb);
		}
	}

	int a, b; tie(a, b) = que.back();
	printf("%d\n", dist[a][b]);

	return 0;
}

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    string s; cin >> s;
    vector<int> vs;
    for(char ch: s){
        vs.push_back(ch - 'a');
    }
    int l = vs.size();
    // cout << l << endl;
    int maxl = 0; 
    // 'a' - 'z'
    for(int i=0;i<26;i++){
        vector<int> vsc = vs;
        int lc = l;
        while(lc > 0){
            bool same = true;
            for(int j=0;j<lc;j++){
                if(vsc[j] != i){
                    same = false;
                    break;
                }
            }
            if(same){
                // cout << "same" << endl;
                break;
            }

            for(int j=0;j<lc;j++){
                if(vsc[j] == i){
                    if(j - 1 >= 0) vsc[j-1] = i;
                }
            }
            lc--;
        }
        maxl = max(lc, maxl);
    }
    cout << l - maxl << endl;
}

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

using namespace std;

void solve() {
    int N;
    cin >> N;
    double c_log;
    c_log = 0;
    long long ans;
    vector<long long> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
        c_log += log10(A[i]);
        if (A[i] == 0)
        {
            cout << 0 << endl;
            return;
        }
    }
    if (c_log > 18)
    {
        cout << -1 << endl;
        return;
    }
    
    ans = 1;
    for (int i = 0; i < N; i++)
    {
        ans = ans * A[i];
    }
    if (ans > (long long)1e18)
    {
        cout << -1 << endl;
        return;
    }
    
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 4048
#include <bits/stdc++.h>
#include <set>
#include <numeric>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);
// int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
// int a[12][12];



void solve() {
  int k; cin >> k;
  int even=0,odd=0;
  for (int i=1; i <=k; i++) {
    if (i%2 == 0) odd++;
    else even++;
  }
  cout << even*odd << endl;

}

int main() {
  solve();
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	//	"strings"
)

// gcd ...
func gcd(a, b int) int {
	if b > a {
		a, b = b, a
	}
	if a%b == 0 {
		return b
	}
	return gcd(b, a%b)
}

// lcm ...
func lcm(a, b int) int {
	g := gcd(a, b)
	return (a / g) * b
}

func main() {
	sc := NewScanner()

	n := sc.NextInt()
	tmp := sc.NextInt()
	for i := 1; i < n; i++ {
		tmp = gcd(tmp, sc.NextInt())
	}
	fmt.Printf("%v\n", tmp)

}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
    int n,x,g;
    cin >> n >> x;
    cin >> g;
    g = abs(g-x);
    rep(i,n-1){
        int a;
        cin >> a;
        g = gcd(g,abs(a-x));
    }
    cout << g << endl;
}


Measured memory_bytes: 3608
#include<stdio.h>
#include<stdlib.h>

void run(void){
  int s;
  scanf("%d",&s);
  char *used=(char *)calloc(1000000+1,sizeof(char));
  int m;
  for(m=1;!used[s];m++){
    used[s]=1;
    s=s%2==0?s/2:3*s+1;
  }
  printf("%d\n",m);
}

int main(void){
  run();
  return 0;
}

Measured memory_bytes: 1152
import math

def gcd(*numbers):
    return math.gcd( math.gcd(a, b), c)

k = int(input())

ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, b, c)

print(ans)
            

Measured memory_bytes: 68312
while True:
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    else:
        if x<y:
            x,y=y,x
        i=0
        while True:
            if y==0:
                break
            else:
                i+=1
                d=x%y
                x=d
                x,y=y,x
    print(x,i)


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

int main() {
  string S(4, '0');
  cin >> S;
  int digit = (int)S.size() - 1;

  for (int bit = 0; bit < (1 << digit); ++bit) {
    int ans = S.at(0) - '0';
    string f = "";
    f += S.at(0);

    for (int i = 0; i < digit; ++i) {
      int n = S.at(i + 1) - '0';

      if (bit & (1 << i)) {
        ans += n;
        f += '+';
      } else {
        ans -= n;
        f += '-';
      }

      f += S.at(i + 1);
    }

    if (ans == 7) {
      cout << f + '=' + to_string(ans) << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include <stdio.h>


int main(void)
{
	int			i,j, money=100000, debt, week, surplus;
	
	scanf("%d",&week);
	for(i=0; i<week; i++){
		debt = money*1.05;
		surplus = debt % 1000;

		if(surplus){

			money = debt + 1000 -surplus;
		}
		else{
			money = debt;
		}

	}
	
	printf("%d\r\n", money);
	return 0;
}

Measured memory_bytes: 592
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

char cor[4]="RGB";
int main(){
    int T;
    scanf("%d\n",&T);
    int ns[9];
    char c;
    for(int ix=0;ix<T;ix++){
        vector<int> cs[3];
        for(int i=0;i<9;i++){
            scanf("%d",ns+i);
        }
        for(int i=0;i<9;i++){
            scanf(" %c",&c);
            for(int j=0;j<3;j++){
                if(c==cor[j]) cs[j].push_back(ns[i]);
            }
        }
        bool is=true;
        for(auto ar : cs) if(ar.size()%3>0) is=false;
        if(!is){
            printf("0\n");
            continue;
        }
        for(auto ar : cs){
            sort(begin(ar),end(ar));
            bool isex=false;
            if(ar.size()==0) isex=true;
            do{
                bool is2=true;
                for(int i=0;i<ar.size()/3;i++){
                    if(!((ar[i*3]==ar[i*3+1] && ar[i*3]==ar[i*3+2]) || (ar[i*3]+1==ar[i*3+1] && ar[i*3]+2==ar[i*3+2]))) is2=false;
                }
                if(is2) isex=true;
            }while(next_permutation(begin(ar),end(ar)));
            if(!isex) is=false;
        }
        if(is) printf("1\n");
        else printf("0\n");
    }
}

Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
typedef long long int llint;

int main(){
	int n, i;
	llint sum;
	llint a[110000];
	cin>>n;
	a[0]=0;
	a[n+1]=0;
	for(i=1; i<=n; i++) cin>>a[i];
	for(i=0; i<=n; i++) sum+=abs(a[i+1]-a[i]);
	for(i=1; i<=n; i++){
		// 0, 1, 2, or, 2, 1, 0
		if((a[i-1]<=a[i] && a[i]<=a[i+1]) || (a[i-1]>=a[i] && a[i]>=a[i+1])){
			// cout<<i<<endl;
			cout<<sum<<endl;
		}
		// 0, 2, 1, or, 1, 2, 0
		else if((a[i-1]<=a[i+1] && a[i]>=a[i+1]) || (a[i-1]>=a[i+1] && a[i]<=a[i+1])){
			// cout<<i<<endl;
			cout<<sum-2*(abs(a[i]-a[i+1]))<<endl;
		}
		// 2, 0, 1, or, 1, 0, 2
		else if((a[i-1]>=a[i+1] && a[i-1]<=a[i]) || (a[i-1]>=a[i] && a[i-1]<=a[i+1])){
			// cout<<i<<endl;
			cout<<sum-2*(abs(a[i-1]-a[i]))<<endl;
		}
	}
	return 0;
}

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

int main( void ){
    long int k, a, b;
    cin >> k >> a >> b;
    if(b-a <= 2 || k < a-1) cout << k+1 << endl;
    else cout << a + (b-a) * ((k-(a-1)) / 2) + (k-(a-1)) % 2 << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        string s = ReadLine();
        string t = ReadLine();

        string S = s + s;
        var next = new long[26][];
        for (int i = 0; i < 26; i++)
        {
            next[i] = new long[s.Length];
            int point = -1;
            for (int now = S.Length - 1; now >= 0; now--)
            {
                if (S[now] == 'a' + i) point = now;
                if (now < s.Length)
                {
                    next[i][now] = point - now;
                }
            }
        }
        long ans = 0;
        long sindex = 0;
        for (int i = 0; i < t.Length; i++)
        {
            var v = next[t[i] - 'a'][sindex];
            if (v < 0)
            {
                WriteLine(-1);return;
            }
            else
            {
                ans += v + 1;
                sindex += v + 1;
                sindex %= s.Length;
            }
        }
        WriteLine(ans);
    }
}


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

typedef long long ll;

int main() {
    bitset<64> bs(0);
    
    int n; cin >> n;
    vector<bitset<64> > mask(n);
    for(int i=0; i<n; i++){
        int k; cin >> k;
        vector<int> b(k);
        for(int j=0; j<k; j++){
            cin >> b[j];
            mask[i].set(b[j]);
        }
    }
    
    int q;
    cin >> q;
    for(int i=0; i<q; i++){
        int query; cin >> query;
        
        if(query==0){
            int i; cin >> i;
            cout << bs.test(i) << endl;
        }
        else if(query==1){
            int i; cin >> i;
            bs |= mask[i];
        }
        else if(query==2){
            int i; cin >> i;
            bs &= ~mask[i];
        }
        else if(query==3){
            int i; cin >> i;
            bs ^= mask[i];
        }
        else if(query==4){
            int i; cin >> i;
            cout << ((bs&mask[i])==mask[i]) << endl;
        }
        else if(query==5){
            int i; cin >> i;
            cout << (bs&mask[i]).any() << endl;
        }
        else if(query==6){
            int i; cin >> i;
            cout << (bs&mask[i]).none() << endl;
        }
        else if(query==7){
            int i; cin >> i;
            cout << (bs&mask[i]).count() << endl;
        }
        else if(query==8){
            int i; cin >> i;
            cout << (bs&mask[i]).to_ullong() << endl;
        }
    }

}



Measured memory_bytes: 3068
import java.util.*;


public class Main {
    public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);
        
   int N = sc.nextInt();
   int X = sc.nextInt();
   int[] L = new int[N];
   
   for(int i =0; i<N;i++){
       L[i] = sc.nextInt();
   }
   
   int ans = 1;
   int D = 0;
   for(int n = 0; n < L.length; n++){
       D = D + L[n];
       if(D <= X){
           ans++;
       }
   }
   
   System.out.println(ans);
    }  
}

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


using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 1010;
const ll INF = 1LL << 60;

template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}



// Main Code

vector<pair<ll, ll>> vp;

int main()
{
	ll n, c;
	cin>>n>>c;
	rep(i, 0, n)
	{
		ll x, y;
		cin>>x>>y;
		vp.pb({x, y});
	}
	ll ans = 0;
	ll tmp = 0;
	ll curr = 0;
	ll opr[n+1], opl[n+1];
	ll rd[n+1], ld[n+1];
	opr[0] = 0;
	int i = 1;
	ld[0] = rd[0] = 0;
	for(auto x: vp)
	{
		tmp += x.s - x.f + curr;
		if(opr[i-1] >= tmp)
		{
			rd[i] = rd[i-1];
		}
		else
		{
			rd[i] = x.f;
		}
		opr[i] = max(opr[i-1], tmp);
		i++;
		curr = x.f;
	}
	opl[0] = 0;
	curr = c;
	i = 1;
	tmp = 0;
	for(auto j = vp.rbegin(); j != vp.rend(); j++)
	{
		tmp += (*j).s-curr+(*j).f;
		if(opl[i-1] >= tmp)
		{
			ld[i] = ld[i-1];
		}
		else
		{
			ld[i] = c - (*j).f;
		}
		opl[i] = max(opl[i-1], tmp);
		curr = (*j).f;
		i++;
	}
	repn(i, 0, n)
	{
		chmax(ans, (opr[i] + opl[n - i] - rd[i]));
		chmax(ans, (opr[n-i] + opl[i] - ld[i]));
	}
	cout<<ans<<endl;
}


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

using namespace std;

int h[200005], que[400005], l, r;
long long dp[200005];

long long x(int id) {
	return dp[id] + 1LL * h[id] * h[id];
}

int main() {
	int n;
	long long C;
	
	scanf("%d%lld", &n, &C);
	
	for (int i = 0; i < n; i++) scanf("%d", &h[i]);
	
	for (int i = 1; i < n; i++) {
		while (r - l >= 2 && (x(que[r - 1]) - x(que[r - 2])) * (h[i - 1] - h[que[r - 1]]) > (x(i - 1) - x(que[r - 1])) * (h[que[r - 1]] - h[que[r - 2]])) r--;
		que[r++] = i - 1;
		while (r - l >= 2 && (x(que[l + 1]) - x(que[l])) < 2LL * h[i] * (h[que[l + 1]] - h[que[l]])) l++;
		
		dp[i] = dp[que[l]] + 1LL * (h[i] - h[que[l]]) * (h[i] - h[que[l]]) + C;
	}
	
	printf("%lld\n", dp[n - 1]);
}


Measured memory_bytes: 3328
n = int(input())

al = [0 for _ in range(n)]
for i in range(n):
    al[i] = int(input())

ans = 1
i = 0
while True:
    if al[i] == 2:
        print(ans)
        break
    elif al[i] == -1:
        print(-1)
        break
    tmp = i
    i = al[i]-1
    al[tmp] = -1
    ans += 1


Measured memory_bytes: 7080
#include<stdio.h>

int main(void)
{
  int i, N, a, b, c;

  scanf("%d",&N);
  for(i=0;i<N;i++)
    {
      scanf("%d %d %d", &a, &b, &c);
      if(a>b)
	{
	  if(a>c)
	    {
	      if(a*a == b*b + c*c)
		printf("YES\n");
	      else
		printf("NO\n");
	    }
	  else
	    {
	      if(c*c == a*a + b*b)
		printf("YES\n");
	      else
		printf("NO\n");
	    }
	}
      else
	{
	  if(b>c)
	    {
	      if(b*b == a*a + c*c)
		printf("YES\n");
	      else
		printf("NO\n");
	    }
	  else
	    {
	      if(c*c == a*a + b*b)
		printf("YES\n");
	      else
		printf("NO\n");
	    }
	}
    }
  return 0;
}

Measured memory_bytes: 580
#include <iostream>
#include <vector>
#include <algorithm>

#define rep(i,N) for(int i=0; i<(int)(N); i++)
using namespace std;


int levenshtein(string str1, string str2);

int main(){
        string s1,s2;
        cin >> s1 >> s2;
        cout << levenshtein(s1, s2) << endl;
        return 0;
}

int d[1010][1010];
int levenshtein(string str1, string str2){
        rep(i,str1.size()+1){
                rep(j,str2.size()+1){
                        if(i==0) {
                                d[i][j]=j;
                        }else{
                                if(j==0) {
                                        d[i][j]=i;
                                }else{
                                        if(str1[i-1]==str2[j-1]) {
                                                d[i][j]=min(d[i-1][j-1],min(d[i][j-1]+1,d[i-1][j]+1));
                                        }
                                        else{
                                                d[i][j]=min(d[i-1][j-1]+1,min(d[i][j-1]+1,d[i-1][j]+1));
                                        }
                                }
                        }

                }
        }

        return d[str1.size()][str2.size()];
}



Measured memory_bytes: 7124
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<cmath>
#include<stack>
#include <algorithm>
#include <functional>
//#include<stdlib.h>
using namespace std;


int main() {
	int a, b, c;
	cin >> c >> a >> b;
	a *= c;
	cout << ((a > b) ? b : a);
	return 0;
}

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

using namespace std;
map<ll, int> mp;
int n;

int main()
{
    cin >> n;
    mp[0]++;
    ll s = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        s += x;
        ans += mp[s];
        mp[s]++;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 12800