akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n;
    cin>>n;
    vector<int> p(n);
    rep(i,n) cin>>p[i];
    int a=1;
    rep(i,n){
        if(p[i]==a) a++;
    }
    if(a==1){
        cout<<-1<<endl;
        return 0;
    }
    int ans=n-a+1;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
const double EPS = 1e-10;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define LCIN(n) LL(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<LL,LL>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    LL from,to,value;
    Edge(LL a,LL b,LL c){
        from = a;
        to = b;
        value = c;
    }
    Edge(LL a,LL b){
        from = a;
        to = b;
    }
};
int main(){
    CIN(N);CIN(K);
    I vec;
    REP(a,N){
        CIN(b);
        vec.pb(b);
    }
    LL ans = LINF;
    vec.pb(0);
    sort(ALL(vec));
    for(int a = 0;a < N-K+1;a++){
        int hoge = vec.at(a);
        int huge = vec.at(a+K);
        LL ins = abs(hoge)+abs(huge)+min(abs(hoge),abs(huge));
        ans = min(ans,ins);
    }
    COUT(ans);
    return 0;
}



Measured memory_bytes: 892
s=list(str(input()))
for i in range(len(s)):
    if s[i]=='A':
        s[i]='X'
    elif s[i]=='B':
        s[i]='Y'
    elif s[i]=='C':
        s[i]='Z'
    else:
        s[i]=chr(ord(s[i])-3)
print(''.join(s))


Measured memory_bytes: 5564
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int ar[n];
    for(int i=0;i<n;++i)
    cin>>ar[i];
    
    int sum=0;
    sum+=accumulate(ar,ar+n,0);
    sort(ar,ar+n,greater<int> ());
    
    bool flag=true;
    double req=(double)sum/(4*m);
    
    if(ar[m-1]>=req)
    cout<<"Yes";
    else
    cout<<"No";
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		Integer[] A = new Integer[N];
		Integer[] B = new Integer[N];
		Integer[] C = new Integer[N];

		for(int i=0; i<N; i++) {
			A[i] = sc.nextInt();
		}

		for(int i=0; i<N; i++) {
			B[i] = sc.nextInt();
		}

		for(int i=0; i<N; i++) {
			C[i] = sc.nextInt();
		}

		Arrays.sort(A);
		Arrays.sort(B);
		Arrays.sort(C);

		long ans = 0;
		for(int i=0; i<N; i++) {
			int key = B[i];
			int a_n = binary_search(A, key, 0, A.length);
			if(a_n <= 0 || a_n > A.length)
				continue;

			key++;
			int c_n = binary_search(C, key, 0, C.length);
			if(c_n < 0 || c_n >= C.length)
				continue;

			ans += (long)a_n * (N-c_n);
		}

		System.out.println(ans);

	}

	//okの条件（ここを問題ごとに変える）(int)
	public static boolean isOK(Integer[] a, int index, int key) {
		if(a[index] >= key)
			return true;
		else
			return false;
	}

	//okの条件（ここを問題ごとに変える）(long)
	public static boolean isOK(Long[] a, int index, long key) {
		if(a[index].longValue() >= key)
			return true;
		else
			return false;
	}

	//めぐる式二分探索(デフォルトはkey以上を満たす最小のindexを返す)(int)
	public static int binary_search(Integer[] a, int key, int ng, int ok) {
//		int ng = -1;
//		int ok = a.length;
		if(ng < ok)
			ng--;
		else
			ok--;

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

			if(isOK(a, mid, key))
				ok = mid;
			else
				ng = mid;
		}

		return ok;
	}

	//めぐる式二分探索(デフォルトはkey以上を満たす最小のindexを返す)(long)
	public static int binary_search(Long[] a, long key, int ng, int ok) {
//		int ng = -1;
//		int ok = a.length;
		if(ng < ok)
			ng--;
		else
			ok--;

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

			if(isOK(a, mid, key))
				ok = mid;
			else
				ng = mid;
		}

		return ok;
	}

	//keyが含まれているか(int)
	public static boolean containsValue(Integer[] a, int key) {
		int index = binary_search(a, key, 0, a.length);

		if(index < 0 || index >= a.length || a[index] != key)
			return false;
		else
			return true;
	}

	//keyが含まれている個数(int)
	public static int countValue(Integer[] a, int key) {
		int index1 = binary_search(a, key, 0, a.length);
		int index2 = binary_search(a, key+1, 0, a.length);

		if(index1 < 0 || index1 >= a.length || a[index1] != key)
			return 0;

		return index2 - index1;
	}

	//keyが含まれているか(long)
	public static boolean containsValue(Long[] a, long key) {
		int index = binary_search(a, key, 0, a.length);

		if(index < 0 || index >= a.length || a[index] != key)
			return false;
		else
			return true;
	}

	//keyが含まれている個数(long)
	public static int countValue(Long[] a, long key) {
		int index1 = binary_search(a, key, 0, a.length);
		int index2 = binary_search(a, key+1, 0, a.length);

		if(index1 < 0 || index1 >= a.length || a[index1] != key)
			return 0;

		return index2 - index1;
	}

}


Measured memory_bytes: 103180
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e+9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main(){
    double n; cin >> n;
    n = (int)ceil(n / 2.0);
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef  long long  ll;
const int maxn = 2e5 + 5;
int n, q;
ll a, t[maxn], ans[maxn];
vector<ll> v;
int main() {
    scanf("%d %d",&n,&q);
    v.push_back(n);//!!!
    for (int i=0; i<q; i++) {
        scanf("%lld",&a);
        while (v.size() && v.back() >= a)
            v.pop_back();
        v.push_back(a);
    }
    t[v.size() - 1] = 1;
    for (int i=v.size()-1; i>=0; i--) {
        ll k = v[i];
        while (k>v[0]) {
            int j = lower_bound(v.begin(), v.end(), k) - (v.begin() + 1);
            t[j] += k / v[j] * t[i];
            k %= v[j];
        }
        ans[k] += t[i];
    }
    for (int i=n-1; i>=1; i--) ans[i] += ans[i+1];
    for (int i=1; i<=n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

Measured memory_bytes: 4212
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long[] a = new long[N];
		for (int i = 0; i < N; i++)
			a[i] = sc.nextLong() - i - 1;
		Arrays.sort(a);
		long[] s = new long[N + 1];
		for (int i = 0; i < N; i++)
			s[i] = i == 0 ? a[i] : s[i - 1] + a[i];
		long total = s[N - 1];
		long min = Long.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			if (i > 0 && a[i] == a[i - 1])
				continue;
			long l = a[i] * (i + 1) - s[i];
			long h = (total - s[i]) - a[i] * (N - i - 1);
			min = Math.min(min, l + h);
		}
		System.out.println(min);
	}
}


Measured memory_bytes: 85816
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>

#include <map>
#include <vector>
#include <algorithm>
#include <functional>

#include <sstream>
#include <iostream>

using namespace std;
typedef long long llint;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

#define TRACE(x) cerr << #x << " = " << x << endl
#define _ << " _ " <<

const int MAXN = 1005;
const int MAX = 5005;
const int inf = 1e9;

int N;
vector<int> T[MAXN];
int X[MAXN];
int Y[MAXN];

bool dfs(int i) {
  static int dp[MAXN][MAX];
  if (T[i].empty()) 
    return true;

  for (int j : T[i])
    if (!dfs(j)) return false;

  int m = T[i].size();
  REP(sum, X[i] + 1) dp[m][sum] = 0;

  for (int j = m - 1; j >= 0; --j) {
    int J = T[i][j];
    for (int sum = 0; sum <= X[i]; ++sum) {
      dp[j][sum] = inf;
      if (sum + X[J] <= X[i])
	dp[j][sum] = min(dp[j][sum], dp[j+1][sum+X[J]] + Y[J]);
      if (sum + Y[J] <= X[i])
	dp[j][sum] = min(dp[j][sum], dp[j+1][sum+Y[J]] + X[J]);
    }
  }

  if (dp[0][0] == inf)
    return false;

  Y[i] = dp[0][0];
  return true;
}

int main(void) 
{
  scanf("%d", &N);
  FOR(i, 2, N + 1) {
    int p;
    scanf("%d", &p);
    T[p].push_back(i);
  }

  FOR(i, 1, N + 1)
    scanf("%d", &X[i]);

  puts(dfs(1) ? "POSSIBLE" : "IMPOSSIBLE");

  return 0;
}




Measured memory_bytes: 17280
#include <iostream>
using namespace std;
int main(){
    int n,m,l;
    cin>>n>>m>>l;
    long int matrix1[n*m];
    long int matrix2[m*l];
    long int output[n*l]={0};

    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    {
            cin >> matrix1[i*m+j];
    }
    for(int i=0;i<m;i++)
        for(int j=0;j<l;j++)
        {
            cin >> matrix2[i*l+j];
        }

     for(int i=0;i<n;i++)
         for(int j=0;j<l;j++) {
             for (int k = 0; k < m; k++)
                 output[i * l + j] += matrix1[i * m + k] * matrix2[k * l + j];
             if(j<l-1)
            cout<<output[i*l+j]<<" ";
             else
                 cout<<output[i*l+j]<<endl;
    }

    return 0;
}


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

#define ll long long
#define Fi first
#define Se second
#define Pb push_back
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
#define vvp vector<vector<pair<int,int>>>

const int INF = 1e9;
const int MOD = 1e9+7;

#define all(v) v.begin(),v.end()
#define output_s(a) printf("%s\n",(a).c_str())

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m) for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m) for(int i=(int)(n);i>=(int)(m);i--)
#define RepA(x) for(auto &item:(x))

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

template<typename TypeInt> //最大公約数
TypeInt GCD(TypeInt a,TypeInt b){
    if(a%b==0) return b;
    else return GCD(b,a%b);
}
template<typename TypeInt> //最小公倍数
TypeInt LCM(TypeInt a,TypeInt b){
    return a*b/GCD(a,b);
}

int IN_int(){
    int x;
    scanf("%d",&x);
    return x;
}

//library----------------------------------------------

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

const int NMAX = 25;
bool flag;

int main(){
    CIN(K,N);
    vi dis(N);
    vi A(N);
    int ans=0;
    rep(i,N){
        cin>>A[i];
    }
    rep(i,N-1){
        dis.Pb(A[i+1]-A[i]);
    }
    dis.Pb(A[0]+(K-A[N-1]));
    sort(all(dis));
    rep(i,dis.size()-1) ans+=dis[i];
    printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 2560
def main():
    N = int(input())
    x_line = list(map(int, input().split(' ')))
    max_x = max(x_line)
    min_x = min(x_line)
    result = sum(x_line) ** 2
    for i in range(min_x, max_x + 1):
        hash_result = 0
        for x in x_line:
            hash_result += (x - i) ** 2
        if hash_result < result:
            result = hash_result
    print(result)


if __name__ == '__main__':
    main()


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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

LL t,n,n2,x,y,z,datmin[800010],datmax[800010],ans;
vector <pair <LL,pii> > v,v2;

bool cmp(pair <LL,pii> a,pair <LL,pii> b)
{
	return abs(a.se.fi-a.se.se)>abs(b.se.fi-b.se.se);
}

void build(LL k,LL lb,LL ub)
{
	if(lb==ub)
	{
		if(lb<n) datmin[k]=datmax[k]=lb;
		else
		{
			datmin[k]=1e9;
			datmax[k]=-1e9;
		}
		return;
	}
	build(k*2+1,lb,(lb+ub)/2);
	build(k*2+2,(lb+ub)/2+1,ub);
	datmax[k]=max(datmax[k*2+1],datmax[k*2+2]);
	datmin[k]=min(datmin[k*2+1],datmin[k*2+2]);
}

void updmax(LL k)
{
	datmax[k]=-1e9;
	while(k>0)
	{
		k=(k-1)/2;
		datmax[k]=max(datmax[k*2+1],datmax[k*2+2]);
	}
}

void updmin(LL k)
{
	datmin[k]=1e9;
	while(k>0)
	{
		k=(k-1)/2;
		datmin[k]=min(datmin[k*2+1],datmin[k*2+2]);
	}
}

LL querymax(LL k,LL lb,LL ub,LL tlb,LL tub)
{
	if(ub<tlb||tub<lb) return -1e9;
	if(tlb<=lb&&ub<=tub) return datmax[k];
	return max(querymax(k*2+1,lb,(lb+ub)/2,tlb,tub),querymax(k*2+2,(lb+ub)/2+1,ub,tlb,tub));
}

LL querymin(LL k,LL lb,LL ub,LL tlb,LL tub)
{
	if(ub<tlb||tub<lb) return 1e9;
	if(tlb<=lb&&ub<=tub) return datmin[k];
	return min(querymin(k*2+1,lb,(lb+ub)/2,tlb,tub),querymin(k*2+2,(lb+ub)/2+1,ub,tlb,tub));
}

int main()
{
	cin>>t;
	rep(tn,t)
	{
		cin>>n;
		n2=1;
		while(n2<n) n2*=2;
		v.clear();
		v2.clear();
		rep(i,n)
		{
			scanf("%lld%lld%lld",&x,&y,&z);
			if(y>z) v.pb(mpr(x-1,mpr(y,z)));
			else v2.pb(mpr(x,mpr(z,y)));
		}
		sort(v.begin(),v.end(),cmp);
		sort(v2.begin(),v2.end(),cmp);
		build(0,0,n2-1);
		ans=0;
		rep(i,v.size())
		{
			LL tmp=querymax(0,0,n2-1,0,v[i].fi);
			//cout<<tmp<<' '<<v[i].fi<<' '<<v[i].se.fi<<' '<<v[i].se.se<<endl;
			if(tmp==-1e9)
			{
				//cout<<i<<' '<<ans<<endl;
				ans+=v[i].se.se;
				continue;
			}
			ans+=v[i].se.fi;
			updmax(tmp+n2-1);
		}
		//cout<<ans<<endl;
		rep(i,v2.size())
		{
			LL tmp=querymin(0,0,n2-1,v2[i].fi,n-1);
			if(tmp==1e9)
			{
				ans+=v2[i].se.se;
				continue;
			}
			ans+=v2[i].se.fi;
			updmin(tmp+n2-1);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
/*
10
5
4 5 1
4 3 1
2 8 1
1 7 1
4 5 1
*/

Measured memory_bytes: 16716
#include <stdio.h>

int main(){
    int a,b;
    char op;
    
    while (1) {
        scanf("%d %c %d",&a,&op,&b);
    
    if (op=='+') {
        printf("%d\n",a+b);
    }
    else if(op=='-'){
        printf("%d\n",a-b);
    }
    else if(op=='*'){
        printf("%d\n",a*b);
    }
    else if(op=='/'){
        printf("%d\n",a/b);
    }
    else break;
    }
    return(0);
}

Measured memory_bytes: 600
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

int main() {
    int N; long long T; cin >> N >> T;
    vector<long long> ts(N);
    rep(i, N) cin >> ts[i];

    long long prev_time = 0;
    long long acc = 0;
    for (const auto t: ts) {
        long long diff = t - prev_time;
        if (diff <= T) {
            acc += diff;
        } else {
            acc += T;
        }
        prev_time = t;
    }
    acc += T;
    cout << acc << endl;
}


Measured memory_bytes: 1792
n=gets
a=gets.split.map(&:to_i)
minus=true
m_l=[]
a_1=[]
a.each{|i|
  if i<0
    i=i*(-1)
    m_l<< i
  end
  a_1<< i
}
a_1.sort!
a_0=a_1.shift
minus=false if a.include?(0)||m_l.size%2==0
p minus ? a_1.inject(:+)-a_0:a_1.inject(:+)+a_0

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

using ll = long long int;
using P = std::pair<int, int>;

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

std::vector<std::vector<int>> dat;

int k;

int dx[] = {0, -1, -1, 1, 1, 0, 2, 0, -2, 2, -2, 2, -2};

int dy[] = {0, -1, 1, -1, 1, 2, 0, -2, 0, 2, 2, -2, -2};

void cut(int &a)
{
    if (a < 0)
        a = 0;
    else if (a > 2 * k)
        a = 2 * k;
}

void fill(int x, int y)
{
    rep(i, 13)
    {
        int gx = x + dx[i] * k + 1, gy = y + dy[i] * k + 1;
        int sx = gx - k, sy = gy - k;

        cut(sx);
        cut(sy);
        cut(gx);
        cut(gy);

        if (gx == sx || gy == sy)
            continue;

        dat[sx][sy]++;
        dat[gx][sy]--;
        dat[sx][gy]--;
        dat[gx][gy]++;
    }
}

int main()
{
    int n;
    std::cin >> n >> k;

    dat.resize(2 * k + 1, std::vector<int>(2 * k + 1, 0));

    rep(i, n)
    {
        int x, y;
        char ch;
        std::cin >> x >> y >> ch;
        if (ch == 'W')
        {
            x += k;
        }
        x %= 2 * k;
        y %= 2 * k;

        fill(x, y);
        std::cerr << i << std::endl;
        /*for (int i = 2 * k - 1; i >= 0; --i)
        {
            rep(j, 2 * k)
            {
                std::cerr << dat[j][i] << ' ';
            }
            std::cerr
                << std::endl;
        }*/
    }

    for (int i = 0; i <= 2 * k - 1; ++i)
    {
        for (int j = 1; j <= 2 * k - 1; ++j)
        {
            dat[i][j] += dat[i][j - 1];
        }
    }

    for (int i = 1; i <= 2 * k - 1; ++i)
    {
        for (int j = 0; j <= 2 * k - 1; ++j)
        {
            dat[i][j] += dat[i - 1][j];
        }
    }

    int ans = 0;

    rep(i, 2 * k)
    {
        rep(j, 2 * k)
            ans = std::max(ans, dat[i][j]);
    }

    std::cout << ans << std::endl;

    /*for (int i = 2 * k - 1; i >= 0; --i)
    {
        rep(j, 2 * k)
        {
            std::cerr << dat[j][i] << ' ';
        }
        std::cerr
            << std::endl;
    }*/

    return 0;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ll long long
long long INF = 1e18;
const int MOD = 1e9 + 7;

using namespace std;

int vpa[300*300+1],vpb[300*300+1],vl[300*300+1],answer[100000];

int main(){
    int h,w,d,q;
    scanf("%d %d %d",&h,&w,&d);
    FOR(i,1,h+1){
        FOR(j,1,w+1){
            int a;
            scanf("%d",&a);
            vpa[a] = i;
            vpb[a] = j;
        }
    }

    scanf("%d",&q);
    FOR(i,1,d+1) vl[i] = 0;
    FOR(i,d+1,h*w+1) vl[i] = vl[i-d] + abs(vpa[i]-vpa[i-d]) + abs(vpb[i]-vpb[i-d]);

    REP(i,q){
        int l,r;
        scanf("%d %d",&l,&r);
        answer[i] = vl[r] - vl[l];
    }
    REP(i,q) printf("%d\n",answer[i]);
    return 0;
}


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

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define INF 1000000009
using namespace std;
typedef long long ll;

int main(){
	//freopen("stl.gir", "r", stdin);
	
	int n, k;
	cin >> n >> k;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) cin >> arr[i];
	vector<int> dp(n);
	dp[0] = 0;
	for (int i = 1; i < n; i++){
		dp[i] = INF;
		for (int j = 1; j <= k; j++){
			if (i-j >= 0) dp[i] = min(dp[i], abs(arr[i]-arr[i-j]) + dp[i-j]);
		}
	}
	cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
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; }
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0, 0,-1,1,-1, 1,-1};
int dy[]={0,1,-1, 0,1,-1,-1, 1};

 

int main(){
    string s;cin >> s;
    cout << (char) (s[0] + 1) << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>

int main(){
	std::string a, b;
	while(std::cin >> a >> b, a != "0"){
		int hit = 0, brow = 0, as[10] = {0}, bs[10] = {0};
		//hitの判定, browの準備
		for(int i=0;i<4;i++){
			if(a[i] == b[i])hit++;
			as[a[i]-'0']++, bs[b[i]-'0']++;
		}
		//仮のbrowを求める
		for(int i=0;i<10;i++){
			if(as[i] > 0 && bs[i] > 0)
				brow++;
		}
		//仮のbrowにはhitも含まれているので引く
		brow -= hit;
		std::cout << hit << " " << brow << std::endl;
	}
}

Measured memory_bytes: 912
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int N,M,H,K;

typedef pair<int,int> cor_t;//height, vertStcik index

struct knot_t{
    int col;
    int score;
    bool turned;//対応する横棒で曲がる得点　ここで曲がったことありますか
    knot_t* parallel;
    knot_t* next;
};

int scores[1005];
cor_t horizontalSticks[100007];
vector<knot_t> vertSticks[1005];

void init(){
    for(int i=1;i<=N;i++) scanf("%d",scores+i);
    for(int i=1;i<=M;i++){
        scanf("%d",&horizontalSticks[i].second);
        scanf("%d",&horizontalSticks[i].first);
        horizontalSticks[i].first=H-horizontalSticks[i].first;
    }
    for(int i=1;i<=N;i++) vertSticks[i].clear(),vertSticks[i].reserve(1005);
}

void search(knot_t& a){
    a.turned=true;
    auto nextptr=a.parallel->next;
    if (nextptr&&!nextptr->turned) search(*nextptr);
}

int main(){

    while(scanf("%d%d%d%d",&N,&M,&H,&K)
        &&
        N&&M&&H&&K){
        init();
        sort(horizontalSticks+1,horizontalSticks+M+1);
        for(int i=1;i<=M;i++){
            auto &cur=horizontalSticks[i];
            int leftIndex=cur.second,rightIndex=leftIndex+1;
            auto &left=vertSticks[leftIndex],&right=vertSticks[rightIndex];
            auto leftTop=left.empty()?nullptr:&left.back(),
                 rightTop=right.empty()?nullptr:&right.back();
            int leftScore=left.empty()?scores[leftIndex]:left.back().score,
                rightScore=right.empty()?scores[rightIndex]:right.back().score;
            //左/右の縦棒から直行する時の得点
            left.push_back(
                {cur.second,rightScore,false,nullptr,leftTop}
                );
            right.push_back(
                {cur.second+1,leftScore,false,nullptr,rightTop}
                );
            left.back().parallel=&right.back();
            right.back().parallel=&left.back();
        }

        for(int i=1;i<=K;i++) if (!vertSticks[i].empty()) search(vertSticks[i].back());

        int sum=0;
        for(int i=1;i<=K;i++) sum+=vertSticks[i].empty()?scores[i]:vertSticks[i].back().score;

        int diff=0;
        for(int i=1;i<=N;i++){
            auto &curCol=vertSticks[i];
            for(auto &a:curCol){
                auto &fst=a,&snd=*a.parallel;
                auto fstCandidate=fst.next?fst.next->score:scores[fst.col];
                auto sndCandidate=snd.next?snd.next->score:scores[snd.col];
                diff=min(diff,fst.turned*(fstCandidate-fst.score)+snd.turned*(sndCandidate-snd.score));
            }
        }
        printf("%d\n",sum+diff);
    }


    return 0;
}


Measured memory_bytes: 13652
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include <set>

#define DIV 1000000007
using namespace std;
using ll = long long;

int main() {
    ll T1, T2;
    cin >> T1 >> T2;

    ll A1, A2;
    cin >> A1 >> A2;

    ll B1, B2;
    cin >> B1 >> B2;

    ll c1 = A1 - B1, c2 = A2 - B2;
    ll ans = 0;

    if (c1 == 0)
        cout << "infinity" << endl;

    else if (c1 > 0) {
        if (c1 * T1 + c2 * T2 > 0)
            cout << 0 << endl;
        else if (c1 * T1 + c2 * T2 == 0)
            cout << "infinity" << endl;
        else {
            ll turn = (-1)*(c1 * T1 + c2 * T2);
            ans = (c1 * T1) / turn;
            if ((c1 * T1) % turn == 0)ans = ans * 2;
            else ans = ans * 2 + 1;
            cout << ans << endl;
        }

    }

    else {
        if (c1 * T1 + c2 * T2 < 0)
            cout << 0 << endl;
        else if (c1 * T1 + c2 * T2 == 0)
            cout << "infinity" << endl;
        else {
            ll turn = c1 * T1 + c2 * T2;
            ans = ((-1)*c1 * T1) / turn;
            if (((-1)*c1 * T1) % turn == 0)ans = ans * 2;
            else ans = ans * 2 + 1;
            cout << ans << endl;
        }

    }
}


Measured memory_bytes: 256
#define N 100005
#include <stdio.h>

int A[N];

void showArray(int A[], int n, int pos) {
    for (int i = 0; i < n; i++) {
        if (i == pos) {
            printf(" [%d]" + !i, A[i]);
        }
        else {
            printf(" %d" + !i, A[i]);
        }
    }
    printf("\n");
}

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int partition(int A[], int p, int r) {
    int x = A[r];
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (A[j] <= x) {
            i = i + 1;
            swap(&A[i], &A[j]);
        }
    }
    swap(&A[i + 1], &A[r]);
    return i + 1;
}

int main() {
    int n = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    int pos = partition(A, 0, n - 1);
    showArray(A, n, pos);
    return 0;
}


Measured memory_bytes: 2120
s=list(input())
l=[]
x=-100
for i in range(len(s)-1):
  if x==i:
    pass
  else:
    if s[i]=='B' and s[i+1]=='C':
      l.append('D')
      x=i+1
    else:
      l.append(s[i])
f=0
ct=0
for i in range(len(l)):
  if l[i]=='A':
    f+=1
  if l[i]=='B' or l[i]=='C':
    f=0
  if l[i]=='D':
    ct+=f
print(ct)

Measured memory_bytes: 6436
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();
		int num = Integer.parseInt(line);
		System.out.println(num * num * num);
	}
}


Measured memory_bytes: 24324
#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double PI=acos(-1.0);
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n;
int a[maxn],b[maxn],c[maxn];
vector<int>vec;
ll ma[maxn*3],mc[maxn*3];
int main(){
    read(n);
    for (int i=1;i<=n;i++) read(a[i]),vec.push_back(a[i]);
    for (int i=1;i<=n;i++) read(b[i]),vec.push_back(b[i]);
    for (int i=1;i<=n;i++) read(c[i]),vec.push_back(c[i]);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for (int i=1;i<=n;i++){
        int pos=lower_bound(vec.begin(),vec.end(),a[i])-vec.begin();
        pos++;
        ma[pos]++;
    }
    for (int i=1;i<=n;i++){
        int pos=lower_bound(vec.begin(),vec.end(),c[i])-vec.begin();
        pos++;
        mc[pos]++;
    }
    for (int i=1;i<=3e5;i++) ma[i]+=ma[i-1],mc[i]+=mc[i-1];
    ll ans=0;
    for (int i=1;i<=n;i++){
        int pos=lower_bound(vec.begin(),vec.end(),b[i])-vec.begin();
        pos++;
        ans+=ma[pos-1]*(mc[300000]-mc[pos]);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 7408
#include <bits/stdc++.h>
using namespace std;
int a[3][3];
int main()
{
	int sum=0,sum1=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			cin>>a[i][j];
			sum+=a[i][j];
			if(i==j) sum1+=a[i][j];
		}
	}
	if(sum-sum1==2*sum1) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;

class DisjointSet{
public:
	vector<int> rank, p;

	DisjointSet() {}
	DisjointSet(int size) {
		rank.resize(size, 0);
		p.resize(size, 0);
		for (int i=0; i<size; i++){
			makeSet(i);
		}
	}

	void makeSet(int x) {
		p[x] = x;
		rank[x] = 0;
	}

	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}

	void link(int x, int y) {
		if (rank[x] > rank[y]) {
			p[y] = x;
		}
		else {
			p[x] = y;
			if (rank[x] == rank[y]) {
				rank[y]++;
			}
		}
	}

	int findSet(int x) {
		if (x != p[x]) {
			p[x] = findSet(p[x]);
		}
		return p[x];
	}
};

int main(){
	int N, M, A, B;
	cin >> N >> M;
	DisjointSet ds = DisjointSet(N);

	for (int i = 0; i < M; i++) {
		cin >> A >> B;
		ds.unite(A-1, B-1);
	}

	set<int> check;
	for (int i = 0; i < N; i++) {
		check.insert(ds.findSet(i));
	}
	cout << check.size() - 1 << endl;

}


Measured memory_bytes: 7912
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
//const ll mod=1e9+7;
const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll n,s;
  cin >> n >> s;
  vec a(n);
  for(ll i=0;i<n;i++) cin >> a[i];
  vector<mat> dp(n+1,mat(s+1,vec(3)));
  dp[0][0][0]=1;
  for(ll i=0;i<n;i++) {
    for(ll j=0;j<=s;j++) {
      for(ll k=0;k<3;k++) {
        (dp[i+1][j][k]+=dp[i][j][k])%=mod;
        if(k==0) {
          if(j+a[i]<s) {
            (dp[i+1][j+a[i]][k+1]+=dp[i][j][k]*(i+1))%=mod;
          }
          if(j+a[i]==s) {
            (dp[i+1][j+a[i]][k+2]+=dp[i][j][k]*(i+1)*(n-i))%=mod;
          }
        }
        else if(k==1) {
          if(j+a[i]<s) {
            (dp[i+1][j+a[i]][k]+=dp[i][j][k])%=mod;
          }
          if(j+a[i]==s) {
            (dp[i+1][j+a[i]][k+1]+=dp[i][j][k]*(n-i))%=mod;
          }
        }
      }
    }
  }
  cout << dp[n][s][2] << endl;
}

Measured memory_bytes: 493056
//#define DEBUG
using namespace std;

bool prime[1000000] = {0};
int a, d, n;

int main(){
	for(int i = 2; i < 1000; i++){
		if(!prime[i]){
			for(int j = i*2; j < 1000000; j+=i){
				prime[j] = true;
			}
		}
	}
	prime[0] = prime [1] = 1;
	#ifdef DEBUG_prime
	for(int i = 2; i < 100; i++)if(!prime[i])cout<<i<<endl;
	#endif
	while(cin>>a>>d>>n, a||d||n){
		int i, c = 0;
		for(i = a; i < 1000000; i += d){
			if(!prime[i]){
				c++;
				if(c == n)break;
			}
		}
		cout<<i<<endl;
	}
	return 0;
}

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

int main(){

    ll K, A, B;
    cin >> K >> A >> B;
    ll tmp = B - A;
    if(tmp < 2 || A > K){
        cout << K + 1 << endl;
        return 0;
    }
    ll ans = A;
    K -= (A-1);
    ll t = K / 2;
    K -= t * 2;
    ans += t * tmp;
    if(K){
        ans++;
        K--;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define Sort(v, n) sort(v, v+n);
#define VSort(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define cY cout<<"Yes";
#define cN cout<<"No";
#define cA(a) cout<<a;
const ll MOD = 1000000007;



int main() {
    int n;
    cin >> n;
    int a[n];
    rep(i,n) {
        cin >> a[i];
    }
    int bai2 = 0,bai4 = 0,nobai = 0;
    rep(i,n) {
        if(a[i] % 4 == 0) {
            bai4++;
        } else if(a[i] % 2 == 0) {
            bai2++;
        }else {
            nobai++;
        }
    }
    if(bai2 > 0) {
        if(bai4 >= nobai) {
            cY
        } else {
            cN
        }
    } else {
        if(bai4 + 1 >= nobai) {
            cY
        } else {
            cN
        }
    }
}



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

int main() {
  string S; cin >> S;
  int size = S.size();
  int num[26]; rep (i,0,26) num[i] = 0;
  bool check = false;
  rep(i,0,size) {
    int a = (int)(S[i] - 'a');
    num[a]++;
  }
  rep(i,0,26) {
    if (num[i] >=2) check = true;
  }
  if (check) cout << "no" << endl;
  else cout << "yes" << endl;
  
}

Measured memory_bytes: 3632
import java.io.*;
import java.util.*;
 
public class Main {
	private static InputStreamReader isr;
	private static BufferedReader br;
	
	public static void main(String args[]){
		isr = new InputStreamReader(System.in);
		br = new BufferedReader(isr);
		
		System.out.println(Levenshtein( getstrp(), getstrp() ));
	}
	
	public static char[] getstrp(){
	    String buf;
		try{
			buf = br.readLine();
		}catch(Exception e){
			buf = "";
		}
		buf=" "+buf;
		return buf.toCharArray();
	}
	
	public static int Levenshtein(char[] a, char[] b){
	    int al=a.length, bl=b.length;
	    int[][] state = new int[al][bl];
	    int v=0, h=0;
	    state[v][h]=0;
	    for(h=1; h<bl; h++){
	        state[v][h]=state[v][h-1]+1;
	    }
	    for(v=1; v<al; v++){
	        h=0;
	        state[v][h]=state[v-1][h]+1;
	        for(h=1; h<bl; h++){
	            if(a[v]==b[h]){
	                state[v][h]=Math.min(Math.min(state[v-1][h],state[v][h-1]),state[v-1][h-1]-1)+1;
	            }else{
	                state[v][h]=Math.min(Math.min(state[v-1][h],state[v][h-1]),state[v-1][h-1])+1;
	            }
	            
	        }
	    }
	    return state[al-1][bl-1];
	}
	
}

Measured memory_bytes: 29248
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <utility>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <climits>
#include <numeric>
#include<stdio.h>
#include <queue>
#include <iomanip>
#include <float.h>
#include <set>
#include<functional>
#include <stack>
#include <time.h>
#include <climits>
#include <bitset>
using namespace std;
signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	string ans="";
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '(')cnt += 1;
		else cnt -= 1;
		if (cnt == -1) {
			ans = "(" + ans;
			cnt += 1;
		}
		ans = ans + s[i];
	}
	while (cnt>0) {
		cnt -= 1;
		ans = ans + ")";
	}
	cout << ans;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include <algorithm> 
using namespace std;

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;

int main()
{
    long long int n;cin >> n;
    map<long long int,long long int> m;

    for(int i=0;i<n;i++){
        long long int tmp;cin >> tmp;
        m[tmp]++;
    }
    long long int res=0;
    for(auto t:m){
        if(t.first>t.second) res += t.second;
        else if(t.first<t.second) res += t.second - t.first;
    }
    p(res)
} 

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

using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, D;
	cin >> N >> D;
	vector<int> d(N);
	for (int i = 0; i < N; i++) cin >> d[i];
	vector<int> a(N + 1);
	a[0] = D;
	int idx = 0;
	for (int i = 1; i <= N; i++) {
		a[i] = min(a[i - 1], abs(a[i - 1] - d[i - 1]));
	}

	vector<int> b(N + 1);
	b[N] = 1;
	for (int i = N - 1; i >= 0; i--) {
		if (b[i + 1] * 2 <= d[i]) b[i] = b[i + 1];
		else b[i] = b[i + 1] + d[i];
	}

	vector<bool> ans(N);
	for (int i = 0; i < N; i++) ans[i] = (a[i] >= b[i + 1]);

	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		int q;
		cin >> q;
		q--;
		cout << (ans[q] ? "YES" : "NO") << endl;
	}
	return 0;
}

Measured memory_bytes: 7936
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <memory>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void __read(T &a) { cin >> a; }
template<typename T, typename ... Args> void __read(T &a, Args &... args) { cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i]
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T> void outv(T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion




int32_t main() {
    make(int, n);
    makev(a, n);
    VVI g(n);
    for(int i = 1; i < n; ++i){
        make(int, v, u);
        v--, u--;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    VI ans(n);
    VI lis(n + 1, M7);
    lis[0] = 0;
    function<void(int, int)> dfs = [&](int v, int p = -1){
        int i = upper_bound(ALL(lis), a[v] - 1) - lis.begin();
        int tmp = lis[i];
        lis[i] = a[v];
        ans[v] = lower_bound(ALL(lis), M7) - lis.begin() - 1;
        for(auto& u : g[v]){
            if (u != p){
                dfs(u, v);
            }
        }
        lis[i] = tmp;
    };
    dfs(0, -1);
    for(auto& val : ans){
        cout << val << '\n';
    }

    return 0;
}

Measured memory_bytes: 39116
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
typedef pair<P,P> PP;
#define N 200001
vector<int> G[N],rG[N],g;
bool u[N];
int n,cmp[N];

void add_edge(int x,int y){G[x].push_back(y);rG[y].push_back(x);}
void dfs(int x){u[x]=1;rep(i,G[x].size())if(!u[G[x][i]])dfs(G[x][i]);g.push_back(x);} 
void rdfs(int x,int k){u[x]=1;cmp[x]=k;rep(i,rG[x].size())if(!u[rG[x][i]])rdfs(rG[x][i],k);}
int scc() {
  mem(u);g.clear();rep(i,n)if(!u[i])dfs(i);mem(u);
  int k=0;rrep(i,g.size())if(!u[g[i]])rdfs(g[i],k++);return k;
}
void init() {
  rep(i,n) G[i].clear(),rG[i].clear();
  g.clear();
}
int rev(int x) {return (x+n/2)%n;}
int two_sat(vector<P> v) {
  init();
  rep(i,v.size()) {
    add_edge(rev(v[i].F),v[i].S);
    add_edge(rev(v[i].S),v[i].F);
  }
  scc();
  rep(i,n/2) {
    if(cmp[i]==cmp[i+n/2]) return 0;
  }
  return 1;
}
void Main() {
  int m;
  cin >> n >> m;
  PP a[m];
  rep(i,m) {
    int x,y;
    string s,t,r;
    cin >> x >> s >> t >> y >> r;
    x--,y--;
    a[i]=PP(P(x,s=="left"?0:1),P(y,r=="left"?0:1));
  }
  int l=0,r=n;
  while(l+1<r) {
    int mid=(l+r)/2;
    n=mid*2;
    vector<P> v;
    rep(i,m) {
      int x=a[i].F.F,y=a[i].S.F;
      if(x>=mid||y>=mid) continue;
      if(a[i].F.S) x=rev(x);
      if(a[i].S.S) y=rev(y);
      v.pb(P(x,y));
    }
    if(two_sat(v)) l=mid;
    else r=mid;
  }
  cout << r << endl;
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 14396
#include <iostream>

int main()
{
    int n,x,cnt;

    while(1)
    {
        std::cin >> n >> x;

        if (n == 0 && x == 0) break;

        cnt = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i+1; j <= n; j++)
                for (int k = j+1; k <= n; k++)
                    if (i+j+k==x && i!=j && j!=k && k!=i) cnt++;
        
        std::cout << cnt << std::endl;
    }
}


Measured memory_bytes: 3092
import functools
import fractions
N = int(input())
A = [int(x) for x in input().split()]
GCD = functools.reduce(fractions.gcd, A)
B = sorted([a // GCD for a in A], reverse=True)
def ggcd(B, cancel):
  gcd = B[0]
  for b in B[1:]:
    _gcd = fractions.gcd(gcd, b)
    if _gcd == 1 and cancel > 0:
      _gcd = gcd
      cancel -= 1
    gcd = _gcd
  return gcd
print(GCD * max(ggcd(B, 1), ggcd(B[1:], 0)))

Measured memory_bytes: 16132
#include <stdio.h>
#include <iostream>
#include <vector>
#include <assert.h>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <memory.h>
#include <time.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100000;
int n, k, a[N], b[N];
int main()
{
	scanf("%d%d", &n, &k);
	ll res = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", a + i, b + i);
		if ((k | a[i]) == k)
			res += b[i];
	}
	int mask = 0;
	for (int i = 30; i >= 0; --i) {
		ll cur = 0;
		if ((k >> i) & 1)
			for (int j = 0; j < n; ++j)
				if ((((k >> i) ^ 1) | (a[j] >> i)) == ((k >> i) ^ 1))
					cur += b[j];
		res = max(res, cur);
		mask |= k &(1 << i);
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
// #include <atcoder/all> // NOTE: AtCoderライブラリ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
// using namespace atcoder; // NOTE: AtCoderライブラリ
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef pair<int, int> pii;
// #define INF __INT32_MAX__
#define INF 1e9
#define LINF __LONG_LONG_MAX__

int main() {
    ll A, B, C, D; cin >> A >> B >> C >> D;

    ll ans = max(A * C, max(A * D, max(B * C, B * D)));

    cout << ans << endl;
}


Measured memory_bytes: 3596
#include <iostream>

const int MAXN = 3001;
const int P = 998244353;

int a[MAXN];
int f[MAXN][MAXN];

int pow(int64_t x, int y) {
  int64_t ans = 1;
  while (y > 0) {
    if (y & 1) ans = ans * x % P;
    x = x * x % P;
    y >>= 1;
  }
  return ans;
}

int solve(int n, int sum) {
  for (int i = 1; i <= n; ++i) {
    f[i][a[i]] = pow(2, i - 1);
    for (int j = 1; j <= sum; ++j) {
      f[i][j] = (f[i][j] +  2LL * f[i - 1][j]) % P;
      if (j - a[i] > 0) {
        f[i][j] = (f[i][j] + f[i - 1][j - a[i]]) % P;
      }
    }
  }
  return f[n][sum];
}

int main() {
  int n, sum;
  std::cin >> n >> sum;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
  }
  std::cout << solve(n, sum) << std::endl;
  return 0;
}


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

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

    vector<int64_t> lucas(87);
    lucas.at(0) = 2LL;
    lucas.at(1) = 1LL;
    for (int i = 2; i < 87; i++) {
        lucas.at(i) = lucas.at(i - 1) + lucas.at(i - 2);
    }

    cout << lucas.at(n) << endl;
}

Measured memory_bytes: 256
import java.io.File;
import java.io.IOException;
import java.util.*;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		//File file = new File("input.txt");
		//Scanner sc = new Scanner(file);
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
			
		int ans = 0;
		
		if(N == 10000) ans += 10000;
		
		for(int i = 1; i <= 9; i++){
			if(i >= A && i <= B){
				ans += i;
				//System.out.println(i);
			}
			
			for(int j = 0; j <= 9; j++){
				int ij = 10 * i + j;
				if(ij > N) continue;
				if(i + j > B) continue;
				if(i + j >= A && i + j <= B){
					ans += ij;
					//System.out.println(ij);
				}
				
				for(int k = 0; k <= 9; k++){
					int ijk = 100 * i + 10 * j + k;
					if(ijk > N) continue;
					if(i + j + k > B) continue;
					if(i + j + k >= A && i + j + k <= B){
						ans += ijk;
						//System.out.println(ijk);
					}
					
					for(int m = 0; m <= 9; m++){
						int ijkm = 1000 * i + 100 * j + 10 * k + m;
						if(ijkm > N) continue;
						if(i + j + k + m >= A && i + j + k + m <= B){
							ans += ijkm;
							//System.out.println(ijkm);
						}
					}
				}
			}
		}
		
		System.out.println(ans);
	}
}

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

const int N = 1e5+5;

int n, A[N];

int main() {
    scanf("%d", &n);
    set<int> S;
    for(int i = 1; i <= n; ++i) scanf("%d", A+i), S.emplace(A[i]);
    int st;
    for(int i = 1; i <= 10000; ++i) if(S.find(i) == S.end()) st = i;
    int cnt = 0;
    for(int i = 2; i <= n; ++i) {
        if(A[i] == A[i-1]) A[i] = st, cnt++;
    }
    printf("%d\n", cnt);
}


Measured memory_bytes: 256
#include <cstdio>
#include <queue>
using namespace std;
#define MAX_N 100

int g[MAX_N+1][MAX_N+1];
int d[MAX_N+1];
bool visited[MAX_N+1];
queue<int> que;

int n;
int t = 1;

void bfs(int id) {
  visited[id]=true;
  que.push(id);
  queue<int> next_que;
  while(!que.empty()) {
    int v = que.front(); que.pop();
    for(int u=1;u<=n;u++) {
      if(g[v][u]!=0 && !visited[u]) {
        visited[u]=true;
        next_que.push(u);
        d[u] = t;
      }
    }
    if(que.empty()){
      que = next_que;
      while(!next_que.empty()) next_que.pop();
      t++;
    }
  }
}

int main() {
  scanf("%d\n",&n);
  int u,k,v;
  for(int i=0;i<n;i++) {
    scanf("%d %d ",&u,&k);
    for(int j=0;j<k;j++) {
      scanf("%d ",&v);
      g[u][v] = 1;
    }
  }
  bfs(1);
  for(int i=1;i<=n;i++) {
    if(visited[i])
      printf("%d %d\n",i,d[i]);
    else
      printf("%d -1\n",i);
  }
}

Measured memory_bytes: 1084
// サンプルは合う
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int main(){
    int n, m;
    cin >> n >> m;
    vector<pii> vp[n+1];
    while(m-- > 0){
        int l, r, c;
        cin >> l >> r >> c;
        vp[l].push_back({r,c});
    }
    vector<ll> dp(n+1, 1ll<<60);
    dp[0] = 0;
    priority_queue<pair<ll,int>> pq;
    for(pii p : vp[1]){
        pq.push({-(dp[1-1]+p.second), p.first});
    }
    for(int i = 1; i <= n; i++){
        while(!pq.empty() && pq.top().second < i)  pq.pop();
        if(pq.empty()){
            cout << -1 << endl;
            return 0;
        }
        dp[i] = -pq.top().first;
        if(i != 1){
            for(pii p : vp[i]){
                pq.push({-(dp[i]+p.second), p.first});
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

Measured memory_bytes: 7160
#include <bits/stdc++.h>
#define r(i,n) for(int i = 0; i<n; i++)
using namespace std;
 
int main() {
  int a, b;
  cin >> a >> b;
  if(a<=8&&b<=8)cout << "Yay!"<< endl;
    else cout << ":(" << endl;
}


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

namespace ac = atcoder;


void solve()
{
    long long n,q,i,temp,a,b,c;
    cin>>n>>q;
    ac::fenwick_tree<long long> fwt(n);
    for(i=0; i<n;i++)
    {
      cin>>temp;
      fwt.add(i, temp);
    }
    while(q--)
    {
      cin>>a>>b>>c;
      if(a==0)
      {
        fwt.add(b, c);  //Add c to a[b]
      }
      else
      {
        cout<<fwt.sum(b,c)<<endl;
      }
      

    }

}
int main() {
    int t=1;
    //cin>>t;
    while(t--)
    {
      solve();
    }
    return 0;
}

Measured memory_bytes: 8220