akhauriyash/Code-Regression huggingface dataset:
# ACGT
# 0123
# exclude the cases AGC, AXGC, GAC, ACG, AGXC
# AGGC TGAC GAGC AAGC AGTC GGAC AGAC CAGC GACG AGCC CACG CGAC AACG ACGC TAGC ATGC TACG
# 
MOD = 10**9 + 7
n = int(input())
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
for s in range(4):
    for t in range(4):
        for u in range(4):
            dp[3][s][t][u] = 1
dp[3][0][2][1] = 0
dp[3][0][1][2] = 0
dp[3][2][0][1] = 0
for i in range(3, n):
    for s in range(4):
        for t in range(4):
            for u in range(4):
                for v in range(4):
                    dp[i+1][t][u][v] = (dp[i+1][t][u][v] + dp[i][s][t][u]) % MOD
    dp[i+1][2][2][1] -= dp[i][0][2][2]
    dp[i+1][2][0][1] -= dp[i][3][2][0]
    dp[i+1][0][2][1] -= dp[i][2][0][2]
    dp[i+1][0][2][1] -= dp[i][0][0][2]
    dp[i+1][2][3][1] -= dp[i][0][2][3]
    dp[i+1][2][0][1] -= dp[i][2][2][0]
    dp[i+1][2][0][1] -= dp[i][0][2][0]
    dp[i+1][0][2][1] -= dp[i][1][0][2]
    dp[i+1][0][1][2] -= dp[i][2][0][1]
    dp[i+1][2][1][1] -= dp[i][0][2][1]
    dp[i+1][0][1][2] -= dp[i][1][0][1]
    dp[i+1][2][0][1] -= dp[i][1][2][0]
    dp[i+1][0][1][2] -= dp[i][0][0][1]
    dp[i+1][1][2][1] -= dp[i][0][1][2]
    dp[i+1][0][2][1] -= dp[i][3][0][2]
    dp[i+1][3][2][1] -= dp[i][0][3][2]
    dp[i+1][0][1][2] -= dp[i][3][0][1]
print(sum(dp[n][s][t][u] for s in range(4) for t in range(4) for u in range(4)) % MOD)


Measured memory_bytes: 43500
using System;

namespace aoj
{
    public class Program
    {
        public static void Main(string[] args)
        {
            string str = Console.ReadLine();
            string ans = "";
            for (int i = 0; i < str.Length; i++) 
            {
                ans += str[i] == '1' ? "9" : "1";
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 11092
#include <stdio.h>

typedef enum {false, true} bool;


bool trace(long long xy[][2], long long basis, long long xor_basis, int N, int num, int ctr, int index)
{
    int i, j;
    static int record[15];
    static bool flag;
    
    
    if(num == ctr)
    {
        flag = true;
        xor_basis = xor_basis ^ basis;
        
        for(i=0; i<num; i++)
        {
            if((xy[record[i]][1] & basis) != basis || ((xy[record[i]][0] ^ xor_basis) & xor_basis) != xor_basis)
            {
                flag = false;
                
                break;
            }
        }
    }
    else
    {
        for(j=index; j<=N-(num-ctr); j++)
        {
            if(ctr == 0)
                basis = 0;
            
            record[ctr] = j;
            
            if(trace(xy, basis | 1<<(N-j-1), xor_basis, N, num, ctr+1, j+1))
                return true;
        }
    }
    
    if(flag)
        return true;
    else
        return false;
}

int main(void)
{
    char c;
    int N;
    int A, x, y;
    
    long long xy[15][2], temp, temp2;
    
    int i, j;
    
    
    scanf("%d%c", &N, &c);
    
    
    for(i=0; i<N; i++)
    {
        scanf("%d%c", &A, &c);
        
        xy[i][0] = 1<<(N-i-1);
        
        xy[i][1] = 1;
        for(j=1; j<N; j++)
            xy[i][1] = xy[i][1]<<1 | 1;
        
        temp = xy[i][1];
        
        for(j=0; j<A; j++)
        {
            scanf("%d%c%d%c", &x, &c, &y, &c);
            
            if(y == 0)
            {
                temp2 = temp ^ 1<<(N-x);
                xy[i][1] &= temp2;
            }
            if(y == 1)
                xy[i][0] |= 1<<(N-x);
        }
    }
    
    for(i=N; i>0; i--)
    {
        if(trace(xy, 0, temp, N, i, 0, 0))
            break;
    }
    
    
    printf("%d\n", i);
    
    
    //system("pause");
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
    int n,x;
    
    int tim[2000];
    int teb[2000];
    int magic[2000]={};

// int pre(int i){
//     return ( i==0 ) ? n-1 : i-1;
// }
int prepre(int f,int k){
    return f-k<0 ? n+(f-k) : f-k ;
}
// int nex(int i){
//     return ( i==n-1) ? 0 : i+1;
// }
int cost(int i,int magic){
    int ret=min(teb[i],tim[prepre(i,magic)]);
    teb[i]=ret;
    return ret;
    // if(dep>=magic){return min(now,tim[i]);}
    // return cost(pre(i),magic,dep+1,min(now,tim[i]));
    // // cout<<i<<f<<dep<<endl;
    // if( x*dep > tim[f] )return tim[f];
    // //if( )
    // if( tim[i] + x*dep < tim[f]){
    //     // cout<<"faf:"<<tim[i]<<endl;
    //     magic[f]=dep-1;
    //     return tim[i] ;//+ x*(dep-1);
    // }else{
    //     // magic[f]++;
    //     // cout<<"nex:"<<x*dep<<endl;
    //     return cost(pre(i),f,dep+1);
    // }
}
int main(){

    cin>>n>>x;
    long long supersum=0;
    for(int i=0;i<n;i++){
        cin>>tim[i];
        teb[i]=tim[i];
        supersum+=tim[i];
        // cout<<tim[i]<<endl;
    }

    for(int magic=1;magic<n;magic++){
        long long sum=0;
        for(int i=0;i<n;i++){
            // cout<<"se:"<<i<<endl;
            sum+=cost(i,magic);
        }
        if(supersum>sum + (long long)magic*x){
            supersum=sum + (long long)x*magic;
        }
        // cout<<supersum<<endl;
    }


    // // cout<<"ff"<<endl;
    // for(int i=0;i<n;i++){
    //     // cout<<magic[i]<<endl;
    //     mag=max(mag,magic[i]);
    // }
    cout<<supersum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
    int k, s;
    int count = 0;
    int z = 0;

    scanf("%d %d", &k, &s);

    for (int x = 0; x <= k; x++) {
        for (int y = 0; y <= k; y++) {
            z = s - x - y;
            if (z >= 0 && z <= k) {
                count++;
            }
        }
    }
    printf("%d\n", count);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define MOD 1000000007LL

using namespace std;
using llong = long long;


int main()
{
	IOS;

	int n, k;
	set<int> a;
	cin >> n >> k;
	int i, j;
	for (i = 0; i < k; i++)
	{
		int d;
		cin >> d;
		for (j = 0; j < d; j++)
		{
			int tmp;
			cin >> tmp;
			a.insert(tmp);
		}
	}
	cout << n - a.size();


	return 0;
}

Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
	int c[3][3];
	cin >> c[0][0] >> c[0][1] >> c[0][2];
	cin >> c[1][0] >> c[1][1] >> c[1][2];
	cin >> c[2][0] >> c[2][1] >> c[2][2];
	
	if(c[1][0] - c[0][0] == c[1][1] - c[0][1] && c[1][1] - c[0][1] == c[1][2] - c[0][2] && c[2][0] - c[0][0] == c[2][1] - c[0][1] && c[2][1] - c[0][1] == c[2][2] - c[0][2])
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

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

using namespace std;

typedef unsigned long long ull;
#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)
#define all(a) (a).begin(), (a).end()

const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

int main(){
	int n;
	while(cin >> n, n){
		int d[15][15];
		rep(i, 15){
			rep(j, 15) d[i][j] = inf;
			d[i][i] = 0;
		}
		int v = -1;
		for(int i=0; i < n; i++){
			int a, b, c;
			cin >> a >> b >> c;
			d[a][b] = c;
			d[b][a] = c;
			v = max(v, max(a+1, b+1));
		}
		rep(k, v) rep(i, v)rep(j, v) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

		int m = inf, ret = -1;
		for(int i=0; i < v; i++){
			int sum = 0;
			for(int j=0; j< v; j++) if(d[i][j] != inf) sum += d[i][j];
			if(sum < m){m = sum; ret = i;}
		}
		cout << ret << " " << m << endl;
	}
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a, b, k;
    scanf("%d %d %d", &a, &b, &k);
    if (2 * k >= b - a + 1){
        for (int i = a; i <= b; i++)
            printf("%d\n", i);
    }else{
        for (int i = a; i < a + k; i++)
            printf("%d\n", i);
        for (int i = b - k + 1; i <= b; i++)
            printf("%d\n", i);
    }
    return 0;
}


Measured memory_bytes: 256
n, m, v, p = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
total = 0
target = A[p-1]
before_p = p - 1

ans = p-1
for idx in range(p-1, n):
    candidate = A[idx]

    if candidate + m < target:
        break

    later_idx = n - idx - 1
    if before_p + later_idx >= v - 1:
        ans += 1

    else:
        possible = (before_p + later_idx)*m
        possible += (candidate+m)*(idx-p+1) - total

        if possible >= m*(v-1):
            ans += 1
        else:
            break
    total += candidate

print(ans)


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

int main(){
    ll n,l,a[210],sum=0;
    cin>>n>>l;
    rep(i,n){
        a[i]=l+i;
        sum+=a[i];
    }
    if(a[0]<0 && a[n-1]>0){
        cout<<sum<<endl;
    } else if(a[0]<0){
        cout<<sum-a[n-1]<<endl;
    } else {
        cout<<sum-a[0]<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
n=int(input())
l=[[0]*3 for _ in range(n)]
for i in range(n):
  s,c=input().split()
  l[i][0]=s
  l[i][1]=int(c)
  l[i][2]=int(i+1)
A=sorted(l,key=lambda x:(x[0],-x[1]))
for i in range(n):print(A[i][2])

Measured memory_bytes: 38384
#include<stdio.h>
#include<string.h>

int atcg(char b){
	//printf("%c\n",b);
	if(b == 'A') return 1;
	else if(b == 'T') return 1;
	else if (b == 'C') return 1;
	else if (b == 'G') return 1;
	else return 0;
}


int main(){
	char s[10];
	int i ; 
	scanf("%s",s);
	//printf("%s\n",s);
	//printf("%d\n",strlen(s));
	int length = strlen(s);
	int count = 0;
	int flag;
	int max = 0;
	for(i=0;i<length;i++){
		if(atcg(s[i]) > 0){
			flag = 0;
		} else {
			flag = 1;
			if(max < count) max = count;
			count = 0;
		} 
		
		if(flag == 0) count++;
		if(max < count) max = count;
	}
	printf("%d\n",max);
	return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
const int N=1e5+10;
typedef pair<int,int> pr;
map<pr,int> mp;
multiset<int> b[N];
queue<pr> q;
typedef multiset<int>::iterator it;
int f[N];
int find(int x){
    return !f[x]?x:f[x]=find(f[x]);
}
void link(int x,int y){
    b[x].insert(y),b[y].insert(x);
}
pr mkpr(int x,int y){
    if(x>y) swap(x,y);
    return make_pair(x,y);
}
int main()
{
    int n;
    scanf("%d",&n);
    fo(i,1,n*2-2){
        int x,y;
        scanf("%d %d",&x,&y);
        link(x,y);
        pr t=mkpr(x,y);
        ++mp[t];
        if(mp[t]==2) q.push(t);
        if(mp[t]>2) return printf("NO"),0;
    }
    fo(ch,2,n){
        if(q.empty()) return printf("NO"),0;
        int x=0,y=0;
        for(;x==y;x=find(q.front().first),y=find(q.front().second),q.pop());
        if(b[x].size()>b[y].size()) swap(x,y);
        f[x]=y;
        for(it i=b[x].begin();i!=b[x].end();i++){
            int v=find(*i);
            b[v].erase(b[v].find(x));
            if(v==y) continue;
            link(v,y);
            pr t=mkpr(v,y);
            ++mp[t];
            if(mp[t]==2) q.push(t);
        }
        b[x].clear();
    }
    printf("YES");
}


Measured memory_bytes: 40960
#include<cstdio>
#include<cstring>
using namespace std;
int main(void)
{
	char s[27];
	int i,cnt[26],flg,len,x;
	scanf("%s",s);
	len=strlen(s);
	for(i=0;i<26;i++)	cnt[i]=0;
	flg=1;
	for(i=0;i<len;i++)	{
		x=s[i]-'a';
//		printf("x=%d\n",x);
		if(cnt[x]!=0)	{
			flg=0;
			break;
		}
		cnt[x]=1;
	}
	if(flg==1)	printf("yes\n");
	else printf("no\n");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for(int i = (int)(n); i>=0; --i)
struct fast_ios { fast_ios(){cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast_ios_;

int main()
{
    string S;
    cin >> S;
    S[1] = S[1]=='R'?'B':'R';
    cout << S << endl;
    return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define forN(i, n) for(int i = 0; i <n ; ++i)
#define endl "\n"
typedef long long ll;
using namespace  std;
const ll INF = 1e18;
const ll MOD = 1e6 + 3;
const int N = 1e5 +5;

int main() {
    fastIO;
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ac = a*c;
    ll ad = a*d;
    ll bc = b*c;
    ll bd = b*d;
    cout<<max({ac,ad,bc,bd});
}

Measured memory_bytes: 3648
#include <iostream>
#define N 101
#define W 10001
#define DIAGONAL 1
#define TOP 0
using namespace std;
void knapsack();
struct I{
  int v,inw;
};
int n,w,C[N][W],G[N][W];
struct I items[N];
int main(){
  int i,j;
  cin >> n >> w;
  for(i=1;i<=n;i++) cin >> items[i].v >> items[i].inw;
  knapsack();
  return 0;
}
void knapsack(){
  int i,j;
  for(i=0;i<=n;i++) C[i][0]=0;
  for(i=0;i<=w;i++) C[0][i]=0;
  for(i=1;i<=n;i++){
    for(j=1;j<=w;j++){
      if(items[i].inw<=j){
	if(items[i].v+C[i-1][j-items[i].inw]>C[i-1][j]){
	  C[i][j]=items[i].v+C[i-1][j-items[i].inw];
	  G[i][j]=DIAGONAL;
	}else{
	  C[i][j]=C[i-1][j];
	  G[i][j]=TOP;
	}
      }else{
	C[i][j]=C[i-1][j];
	G[i][j]=TOP;
      }
    }
  }
  cout << C[n][w] << endl;
}

Measured memory_bytes: 9016
n=int(raw_input())
a=map(int,raw_input().split())
maxa=max(a)
cmaxa=a.count(maxa)
ca=[0]*(maxa+1)
for i in xrange(n):
    ca[a[i]]+=1
if maxa%2==1:
    l=maxa/2+1
    if a.count(l)==2:
        for i in xrange(n):
            if a[i]<l:
                print("Impossible")
                exit()
        for i in xrange(l+1,maxa+1):
            if ca[i]<2:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")
else:
    l=maxa/2
    if a.count(l)==1:
        for i in xrange(n):
            if a[i]<l:
                print("Impossible")
                exit()
        for i in xrange(l+1,maxa+1):
            if ca[i]<2:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")

Measured memory_bytes: 2696
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using ll = long long;
using ull = unsigned long long;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ull> vul;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<ll>> vvl;
typedef vector<vector<string>> vvs;
typedef vector<vector<ull>> vvul;
typedef vector<bool> vb;
const ll md = 998244353;

ll add(ll a, ll b, ll mod = md) {
    return (a%mod + b%mod + mod)%mod;
}

ll mul(ll a, ll b, ll mod = md) {
    return ((a%mod) * (b%mod))%mod;
}

ll C(vl &fact, vl &invfact, ll n, ll r, ll mod = md) {
    if(r == 0) return 1;
    return mul(fact[n], mul(invfact[r], invfact[n-r], mod), mod);
}

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

void cachefact(vector<ll>& fac, vector<ll> &ifac, ll bound, ll mod = md) {
	fac[0] = 1;
	ifac[0] = power(1, mod-2)%mod;
	for(ll i = 1; i <= bound; i++) {
		fac[i] = (fac[i-1] % mod * i % mod)%mod;
		ifac[i] = power(fac[i], mod-2)%mod;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	vl fac(5e5+1), ifac(5e5+1);
	cachefact(fac, ifac, 5e5);
	int n, m, k;
	cin >> n >> m >> k;
	ll res = 0;
	for(int i = 0; i <= k; i++) {
		res = add(res, mul(mul(m, C(fac, ifac, n-1, i)), power(m-1, n-i-1)));
	}
	cout << res << "\n";
	return 0;
}

Measured memory_bytes: 11056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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 INF = 1LL << 60;

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    int cur = A[0]; int cnt = 1; int sum = 0;
    for (int i = 1; i < N; i++) {
        if (A[i] == cur) {
            cnt++;
        } else {
            if (cur < cnt) {
                sum += cnt - cur;
            } else if (cur > cnt){
                sum += cnt;
            }
            cur = A[i];
            cnt = 1;
        }
    }
    if (cur < cnt) {
        sum += cnt - cur;
    } else if (cur > cnt) {
        sum += cnt;
    }

    cout << sum << endl;
    return 0;
}

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

#define rep_0(i, end) for(int i = 0; i < (end); ++i)
#define rep_1(i, fr, ba) for(int i = (fr); i <= (ba); ++i)
#define rep(...) overload_rep(__VA_ARGS__, rep_1, rep_0)(__VA_ARGS__)
#define overload_rep(arg_0, arg_1, arg_2, name, ...) name
#define all(vec) vec.begin(), vec.end()

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; }

int N;
unordered_set<int> graph[100000];

int main() {

    cin >> N;
    rep(i, N - 1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].insert(b);
        graph[b].insert(a);
    }

    unordered_set<int> que;
    rep(i, N)if(graph[i].size() == 1)que.insert(i);

    cout << ([&]{
        while(!que.empty()){
            int v = *que.begin();
            if(graph[v].size() == 0)return false;
            int u = *graph[v].begin();
            for(const int& x : graph[u]){
                graph[x].erase(u);
                if(graph[x].size() <= 1)que.insert(x);
            }
            que.erase(v);
            que.erase(u);
        }
        return true;
    }() ? "Second" : "First") << '\n';

}


Measured memory_bytes: 18188
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string S;
	cin >> S;
	int ans = SZ(S);
	bool b = true;
	int fi = S[0];
	FOR(i,1, SZ(S)) {
		if (S[i] != fi) {
			b = false;
			break;
		}
	}
	if (b) {
		cout << 0 << endl;
		PAU;
		return 0;
	}
	REP(i, 26) {
		char target = 'a' + i;
		string now = S;
		bool clear;
		int cnt = 0;
		while (SZ(now) > 1) {
			clear = true;
			string news = "";
			cnt++;
			REP(j,SZ(now) - 1) {
				if (now[j] == target || now[j + 1] == target) {
					news += target;
				}
				else {
					news += now[j];
					clear = false;
				}
			}
			if (clear)break;
			now = news;
		}
		cerr << target << ":" << cnt << endl;
		if (clear)ans = min(ans, cnt);
	}
	cout << ans << endl;
	PAU;
	return 0;
}


Measured memory_bytes: 504
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main(){ 
  long long a,b,c;
  long long d;
  d=LLONG_MAX;
  cin>>a>>b;
  vector<int>e(a);
  rep(i,a)cin>>e[i];
  sort(e.begin(),e.end());
  rep(i,a-b+1){
    c=e[i+b-1]-e[i];
    d=min(d,c);
  }
  cout<<d;
}


Measured memory_bytes: 640
class Dice:
    def __init__(self):
        self.dice=[1,2,3,4,5,6] # up,front,right,left,back,front
    def set(self,l):
        self.dice=l
    def roll(self, s):
        import copy
        mat=((1,4,3,2),(5,0,1,1),(2,2,0,5),(3,3,5,0),(0,5,4,4),(4,1,2,3))
        l=copy.deepcopy(self.dice)
        if s == 'N': c = 0
        if s == 'S': c = 1
        if s == 'E': c = 2
        if s == 'W': c = 3
        for i in range(6):
            self.dice[i]=l[mat[i][c]]
    def get(self):
        return self.dice

import random
d=Dice()
d.set(list(map(int,input().split())))
for i in range(int(input())):
    u,f=map(int,input().split())
    while True:
        d.roll('NSEW'[random.randrange(4)])
        if d.get()[0]==u and d.get()[1]==f:
            print(d.get()[2])
            break

Measured memory_bytes: 11704
using System;
using System.Collections.Generic;
using System.Linq;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayInt();
            var W = input[0];
            var H = input[1];
            var x = input[2];
            var y = input[3];
            var ans = (double)W * H / 2;
            var can = 2 * x == W && 2 * y == H ? 1 : 0;

            Console.WriteLine(ans + " " + can);
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 11348
import java.util.Scanner;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    while(sc.hasNext()) {
      String str = sc.nextLine();
      for (int i = 0; i < str.length(); i++) {
        System.out.print(str.charAt(str.length()-i-1));
      }
      System.out.println("");
    }
  }
}

Measured memory_bytes: 12000
#include <iostream>
#include <vector>
#include <atcoder/modint>
#include <atcoder/lazysegtree>

namespace ac = atcoder;

using mint = ac::modint998244353;

// ノードに持たせる値
struct S {
    mint val;
    int len;

    S(mint _val, int _len) : val(_val), len(_len) {}

    static S op(S a, S b) {
        return S(a.val * mint(10).pow(b.len) + b.val,
                 a.len + b.len);
    }
    static S id() { return S(0, 0); }
};

// 作用素(更新する値)
using F = int;
// fが新しい方、0が単位元であることに注意
F f_op(F f, F g) { return f == 0 ? g : f; }
F f_id() { return 0; }

// 作用素の適用
S mapping(F f, S a) {
    if (f == 0) return a;
    return S((mint(10).pow(a.len) - 1) / 9 * f, a.len);
}

void solve() {
    int n;
    std::cin >> n;

    // 初期配列
    std::vector<S> init(n, S(1, 1));

    ac::lazy_segtree<S, S::op, S::id, F, mapping, f_op, f_id> seg(init);

    int q;
    std::cin >> q;
    while (q--) {
        int l, r, d;
        std::cin >> l >> r >> d;
        --l;  // [l, r)

        seg.apply(l, r, d);
        std::cout << seg.all_prod().val.val() << "\n";
    }
}

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

    solve();

    return 0;
}


Measured memory_bytes: 10108
n,x=map(int,input().split())

A=list(map(int,input().split()))

B=[a for a in A]

if B[0]>x:
    B[0]=x

for i in range(n-1):
    if B[i]+B[i+1]>x:
        B[i+1]=x-B[i]

ans=0
for a,b in zip(A,B):
    ans+=(a-b)

print(ans)

Measured memory_bytes: 14540
{-# LANGUAGE
    BangPatterns, MultiWayIf, TupleSections #-}
{-# OPTIONS_GHC -O2 #-}


import Control.Arrow
import Control.Concurrent
import Control.Monad
import Data.Bits
import qualified Data.ByteString.Builder as B
import qualified Data.ByteString.Char8 as C
import Data.Char
import Data.Complex
import Data.Function
import Data.Function.HT
import qualified Data.IntMap.Strict as IM
import qualified Data.IntSet as IS
import Data.List
import Data.Maybe
import Data.Monoid
import Data.Ord
import qualified Data.Sequence as Sq
import Data.Vector.Algorithms.Search
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import Debug.Trace
import System.IO


r :: Int -> IO (U.Vector Int)
r n = U.unfoldrN n (C.readInt . C.dropWhile (==' ')) <$> C.getLine

r' :: IO [Int]
r'  =   unfoldr    (C.readInt . C.dropWhile (==' ')) <$> C.getLine


main :: IO ()
main = do
    [h,w,k] <- r'
    cs <- (V.fromList . concat) <$> replicateM h getLine
    let choices = forM (V.replicate (h + w) (0 :: Int)) (\_ -> [1,0])
    print $ length $ filter (solve cs (h,w,k)) choices

solve :: V.Vector Char -> (Int, Int, Int) -> V.Vector Int -> Bool
solve board (h,w,k) choice =
    k == (V.sum $ V.imap (\i c -> let (h',w') = quotRem i w
        in if c == '#' && (choice V.! h') == 0 && choice V.! (h + w') == 0 then 1 else 0) board)


Measured memory_bytes: 5316
N = int(input())
# 問題文では駅は1-indexだが以下では0-indexにして考えている
CSF = [list(map(int, input().split())) for _ in range(N - 1)]
for i in range(N):
    ans = 0
    for j in range(i, N - 1):
        # i,i+1,...,N-1番の駅からの電車について考える
        c, s, f = CSF[j][0], CSF[j][1], CSF[j][2]

        # ans = 今いる駅に着いた時刻

        # 以下、まず待ち時間に着いて考える

        # 開通前に着いてしまったら開通まで待つしかない
        # 発射時刻はs
        if ans < s:
            ans = s
        else:
            # 待ち時間無しで次に乗れる場合
            if ans % f == 0:
                ans += 0
            # 待ち時間が発生する場合
            # ex. F=5でt=7に到着する場合、待ち時間は5-7%5=3
            else:
                ans += f - ans % f

        # 次の駅までc秒かかる
        ans += c
    # i=0,1,2,...,n-1の全てについて、i駅からかかった時間
    print(ans)


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

int ya(int a){
	if(a>0){
		return a;
	}
	else{
		return -a;
	}
}
int main()
{
	int n,i,a,b;
	cin>>n;
	int h[n],dp[n]={};
	for(i=0;i<=n-1;i++){
		cin>>h[i];
	}
	dp[0]=0;
	dp[1]=ya(h[1]-h[0]);
	for(i=2;i<=n-1;i++){
		a=dp[i-2]+ya(h[i]-h[i-2]);
		b=dp[i-1]+ya(h[i]-h[i-1]);
		if(a<b){
			dp[i]=a;
		}
		else{
			dp[i]=b;
		}
	}
	cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 4364
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

int main(){
    int N,M;cin>>N>>M;
    vector<int> num(N);
    vector<bool> a(N);
    REP(i,M){
        int p;string s;
        cin>>p>>s;
        p--;
        if(s=="AC") a[p]=true;
        else if(!a[p]) num[p]++;
    }
    int ans=0,pen=0;
    REP(i,N){
        if(a[i]){
            ans++;
            pen+=num[i];
        }
    }
    cout<<ans<<" "<<pen<<endl;
}

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

using namespace std;
using ll = long long;

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

    int n;
    cin>>n;
    string s;
    cin>>s;
    int totr=0;
    int totw=0;
    for(int i=0;i<n;i++){
        if(s[i]=='R')totr++;
        else totw++;
    }
    int curr=0;
    int curw=0;
    int ans = INT_MAX;
    for(int i=0;i<=n;i++){
        if(i!=0){
            if(s[i-1] == 'R') curr++;
            else curw++;
        }
        //왼쪽은 R로
        int to_R = curw;
        int to_W = totr-curr;
        ans = min(ans, to_R + to_W - min(to_R, to_W));
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3756
import std.stdio;
import std.string : chomp;
import std.conv : to;
import std.math : round;



void main() {
    string input;
    double highest=0, lowest=1000000;

    while ((input = readln.chomp).length != 0) {
        double temp = input.to!double;

        if (temp > highest) highest = temp;
        if (temp < lowest)  lowest  = temp;
    }

    writeln(((highest - lowest) * 100).round / 100);
}

Measured memory_bytes: 1132
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int test_cases = 1;
        Solver s = new Solver();
        for (int i = 1; i <= test_cases; i++) {
            s.solve(i, in, out);
        }
        out.close();
    }
}

class Solver {
    void solve(int test_number, InputReader in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        HashSet<Integer> s = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int a = in.nextInt();
            if (s.contains(a)) s.remove(a);
            else s.add(a);
        }
        out.println(s.size());
    }
}


class InputReader {
    BufferedReader br;
    StringTokenizer st;

    public InputReader()
    {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }

    String next()
    {
        while (st == null || !st.hasMoreElements())
        {
            try
            {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException  e)
            {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt()
    {
        return Integer.parseInt(next());
    }

    long nextLong()
    {
        return Long.parseLong(next());
    }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}

Measured memory_bytes: 45192
import java.util.*; import java.io.*; import java.math.*;
public class Main{
	static void solve(){//Here is the main function
		String s = next();
		if(s.matches("A?KIHA?BA?RA?")){
			myout("YES");
		}else{
			myout("NO");
		}
	}
	//Method addition frame start



	//Method addition frame end

	//Don't have to see. start------------------------------------------
	static class InputIterator{
		ArrayList<String> inputLine = new ArrayList<String>(1024);
		int index = 0; int max; String read;
		InputIterator(){
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try{
				while((read = br.readLine()) != null){
					inputLine.add(read);
				}
			}catch(IOException e){}
			max = inputLine.size();
		}
		boolean hasNext(){return (index < max);}
		String next(){
			if(hasNext()){
				return inputLine.get(index++);
			}else{
				throw new IndexOutOfBoundsException("There is no more input");
			}
		}
	}
	static HashMap<Integer, String> CONVSTR = new HashMap<Integer, String>();
	static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
	static PrintWriter out = new PrintWriter(System.out);
	static void flush(){out.flush();}
	static void myout(Object t){out.println(t);}
	static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
	static String next(){return ii.next();}
	static boolean hasNext(){return ii.hasNext();}
	static int nextInt(){return Integer.parseInt(next());}
	static long nextLong(){return Long.parseLong(next());}
	static double nextDouble(){return Double.parseDouble(next());}
	static ArrayList<String> nextStrArray(){return myconv(next(), 8);}
	static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
	static ArrayList<Integer> nextIntArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Integer> ret = new ArrayList<Integer>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Integer.parseInt(input.get(i)));
		}
		return ret;
	}
	static ArrayList<Long> nextLongArray(){
		ArrayList<String> input = nextStrArray(); ArrayList<Long> ret = new ArrayList<Long>(input.size());
		for(int i = 0; i < input.size(); i++){
			ret.add(Long.parseLong(input.get(i)));
		}
		return ret;
	}
	static String myconv(Object list, int no){//only join
		String joinString = CONVSTR.get(no);
		if(list instanceof String[]){
			return String.join(joinString, (String[])list);
		}else if(list instanceof ArrayList){
			return String.join(joinString, (ArrayList)list);
		}else{
			throw new ClassCastException("Don't join");
		}
	}
	static ArrayList<String> myconv(String str, int no){//only split
		String splitString = CONVSTR.get(no);
		return new ArrayList<String>(Arrays.asList(str.split(splitString)));
	}
	public static void main(String[] args){
		CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
		solve();flush();
	}
	//Don't have to see. end------------------------------------------
}


Measured memory_bytes: 34036
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<string.h>
#include<complex>
#include<math.h>
using namespace std;
typedef long long int llint;
#define rep(i,n) for(int i=0;i<n;i++)

bool check(char a, char b) {
	return a > b;
}

int kuraiwa(int n) {
	int ans = 0;
	while (n > 0) {
		ans += n % 10;
		n /= 10;
	}
	return ans;
}

bool kaibun(int n) {
	int a[5];
	for (int i = 0; i < 5; i++) {
		a[i] = n % 10;
		n /= 10;
	}
	if (a[0] == a[4] && a[1] == a[3]) {
		return true;
	}
	else {
		return false;
	}
}

int main() {
	char s[220], t[110];
	cin >> s >> t;
	char s1[220];
	strcpy(s1, s);
	strcat(s1, s);
	if (strstr(s1, t) != '\0'){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, k; cin >> n >> k;
  string s; cin >> s;
  int ans = 0;
  rep(i, n) {
    if(i == 0 && s[i] == 'L') continue;
    if(i == n-1 && s[n-1] == 'R') continue;
    ans += (s[i]=='L' ? s[i]==s[i-1] : s[i]==s[i+1]);
  }
  cout << min(n-1, ans+2*k) << "\n";
  return 0;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)

vi calc(string &S){
	int N = S.size();
	vi V(N);
	int pre = 0;
	int back = N-1;
	rp(now, 1, N){
		// forward
		if(S[pre] != S[now]){
			if(S[pre] == S[0]){
				int n = now - pre;
				int a = n/2;
				int b = n-a;
				V[now-1] += b;
				V[now] += a;
			}
			pre = now;
		}

		// backward
		if(S[back] != S[N-1-now]){
			if(S[back] == S[N-1]){
				int n = back - (N-1-now);
				int a = n/2;
				int b = n-a;
				V[N-1-now+1] += b;
				V[N-1-now] += a;
			}
			back = N-1-now;
		}

	}
	return V;
}

int main(){
	string S; cin>>S;
	vi V = calc(S);
	rp(i, 0, S.size()) cout<<V[i]<<(i+1<S.size()?" ":"\n");
}


Measured memory_bytes: 1024
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	private static final int BIG_NUM  = 2000000000;
	private static final int MOD  = 1000000007;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		PriorityQueue<Integer> Q = new PriorityQueue<Integer>(1,Collections.reverseOrder());

		String order;
		StringBuilder ans = new StringBuilder();
		int value;

		while(true){

			order = scanner.next();

			if(order.equals("end")){
				break;
			}else if(order.equals("insert")){
				value = scanner.nextInt();
				Q.add(value);
			}else{ //extract
				ans.append(Integer.toString(Q.peek())).append("\n");
				Q.remove();
			}
		}
		System.out.printf(ans.toString());
	}
}




Measured memory_bytes: 479472
n, m = list(map(int, input().split()))
cl = list(map(int, input().split()))
cl.sort()
ql=[]
for _ in range(m):
    b, c = list(map(int, input().split()))
    ql.append([b,c])
ql.sort(key=lambda x: x[1],reverse=True)
i, j = 0,0
while i < len(cl) and j < len(ql):
    if cl[i] < ql[j][1]:
        cl[i] = ql[j][1]
        ql[j][0] -=1
        if ql[j][0] == 0:
            j+=1
    i+=1
print(sum(cl))

Measured memory_bytes: 25976
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main(){
    int a[3];
    for(int i = 0; i < 3; i++){
        cin >> a[i];
    }
    sort(a, a+3);
    cout << a[0] + a[1];
    
}

Measured memory_bytes: 256
MAX = 10 ** 8
n = int(input())
M = [list(map(int,input().split())) for _ in range(n)]
dp = [[MAX for _ in range(n)] for _ in range(n)]
r = [0 for _ in range(n)] 
c = [0 for _ in range(n)] 

for i in range(n):
    r[i] = M[i][0]
    c[i] = M[i][1]
    dp[i][i] = 0

for d in range(1,n):
    for i in range(n-d):
        j = i + d
        min_v = MAX
        for k in range(i,j):
            v = r[i] * c[k] * c[j] + dp[i][k] + dp[k+1][j]
            min_v = min(min_v,v)

        dp[i][j] = min(dp[i][j], min_v)

print (dp[0][n-1])



Measured memory_bytes: 5776
#include <iostream>
using namespace std;
int main()
{
    long long n,w;
    cin>>n>>w;
    long long dp[n][w+1];
    long long we[n];
    long long v[n];
    for(long long i=0;i<n;i++) cin>>we[i]>>v[i];
    
    for(int i=0;i<n;i++)
    for(int j=0;j<=w;j++) dp[i][j]=0;
    for(long long i=0;i<n;i++) dp[i][0]=0;
    for(long long i=0;i<=w;i++) 
    if(i>=we[0]) dp[0][i]=v[0];
    
    for(long long i=1;i<n;i++)
    for(long long j=1;j<=w;j++)
    if(j>=we[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-we[i]]+v[i]);
    else dp[i][j]=dp[i-1][j];
    cout<<dp[n-1][w];
    return 0;
}


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

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define st first
#define nd second
#define endl '\n'
#define what_is(x) cerr << #x << " is " << x << endl;
#define what_is_v(x) cerr << #x << " is "; for(auto&e: (x)) cerr << e << ' '; cerr << '\n'; //vector, set
#define what_is_a(x, n) cerr << #x << " is "; for(int i=0;i<n;i++) cerr << x[i] << ' '; cerr <<  '\n'; //n first element of array
#define cerr_pair(x) '{' << x.st << ", " << x.nd << '}'
#define pwhat_is(x) cerr << #x << " is " << cerr_pair(x) << endl;
#define pwhat_is_v(x) cerr << #x << " is "; for(auto&e: (x)) cerr << cerr_pair(e) << ' '; cerr << '\n'; //vector, set
#define pwhat_is_a(x, n) cerr << #x << " is "; for(int i=0;i<n;i++) cerr << cerr_pair(x[i]) << ' '; cerr <<  '\n'; //n first element of array
#define int long long
// #define pow mypow

typedef pair<int,int> pii;
const int N = 2e5+5;
const int INF = 1e9+5;
const int MOD = 1e9+7;

int n, k, a[N];
int solve(){
	sort(a, a+n);
	int l = 0, r = n-1;
	int res = 1;
	if (k&1) {
		if (a[n-1] == 0) return 0;
		if (a[n-1] < 0) {
			for(int i=0; i<k; i++) {
				res = (res * a[n-1-i] + MOD*MOD) % MOD;
			}
			return res;
		}
		k -= 1; //now k become even
		res = a[n-1];
		r--;
	}
	k /= 2;
	for(int i=0; i<k; i++){
		int left = a[l] * a[l+1];
		int right = a[r] * a[r-1];
		if (left > right) {
			left = (left + MOD*MOD) % MOD;
			res = (res*left) %MOD;
			l += 2;
		}
		else {
			right = (right + MOD*MOD) % MOD;
			res = (res*right) %MOD;
			r -= 2;
		}
	}
	return res;
}
int32_t main()
{
	IOS
	// freopen("input.txt", "r", stdin);
	cin >> n >> k;
	for(int i=0; i<n; i++) cin >> a[i];
	cout << solve() << endl;
	return 0;
}


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

typedef long long ll;
const int MAX_N = 100001;
int par[MAX_N], uniteRank[MAX_N];

void uniteInit(int n){
    for (int i = 0; i < n; i++) {
        par[i] = i;
        uniteRank[i] = 0;
    }
}

int root(int x){
    return par[x] == x ? x : par[x] = root(par[x]);
}

bool same(int x, int y){
    return root(x) == root(y);
}

void unite(int x, int y){
    x = root(x);
    y = root(y);
    if(x == y) return;
    if(uniteRank[x] < uniteRank[y]){
        par[x] = y;
    } else {
        par[y] = x;
        if(uniteRank[x] == uniteRank[y]){
            uniteRank[x]++;
        }
    }
}

int main()
{
    int N, M;
    cin >> N >> M;
    uniteInit(N + 1);
    for(int i = 0; i < M; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        unite(x, y);
    }
    int answer = 0;
    for(int i = 1; i <= N; i++)
    {
        if(par[i] == i)
        {
            answer++;
        }
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <tuple>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxs = 4000000 + 1;
bitset<maxs> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    int n;
    cin >> n;
    s[0] = 1;
    i64 sum = 0;
    forn(i, n) {
        int x;
        cin >> x;
        sum += x;
        s |= s << x;
    }
    int z = (sum + 1) / 2;
    while (!s[z]) ++z;
    cout << z << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>

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

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

int main(int argc, const char * argv[]) {
    
    ll N;
    cin >> N;
    
    ll Ans = 0;
    for(ll A=1; A<N; A++){
        for(ll B=1; A*B<N; B++){
            ll C = N - (A * B);
            if(C > 0) Ans++;
        }
    }
    
    cout << Ans << endl;
    
    return 0;
}


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

int main()
{
	int N, T,t[200001];
	long long ans = 0;

	cin >> N >> T;

	for (int i = 0; i < N; i++) {
		scanf("%d", &t[i]);
	}

	for (int i = 0; i < N-1; i++) {
		ans += min(t[i + 1] - t[i], T);
	}
	ans += T;

	cout << ans << endl;

	return 0;
}

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

double distance(double x,double y){
	return sqrt(x*x + y*y);
}

int32_t main(){
	
	int n,d,count=0;
	cin >> n >> d;
	
	for (int i=0;i<n;i++){
		
		double x,y;
		cin >> x >> y;
		
		if (distance(x,y)<=(double)d) count++;
		
	}
	
	cout<<count<<'\n';
	
	
	return 0;
}


Measured memory_bytes: 3840
// AOJ 1313
#include<cstdio>
#include<algorithm>
#include<vector>
#define rep(i,a) for( int i = 0; i != (a); ++i )
#define all(a) (a).begin(), (a).end()

const int INF = 1 << 30;

int M, N;
int X1[100], Y1[100];
int X2[100], Z2[100];

double width( int *X, int *Y, int n, double x )
{
	double lb = INF, ub = -INF;
	
	rep( i, n )
	{
		double x1 = X[i], y1 = Y[i], x2 = X[(i+1)%n], y2 = Y[(i+1)%n];

		if( (x1-x)*(x2-x) <= 0 && x1 != x2 )
		{
			double y = y1+(y2-y1)*(x-x1)/(x2-x1);
			lb = std::min( lb, y );
			ub = std::max( ub, y );
		}
	}

	return std::max( 0.0, ub-lb );
}

int main()
{
	while( scanf( "%d%d", &M, &N ), M|N )
	{
		rep( i, M )
			scanf( "%d%d", X1+i, Y1+i );
		rep( i, N )
			scanf( "%d%d", X2+i, Z2+i );

		int min1 = *std::min_element( X1, X1+M ), max1 = *std::max_element( X1, X1+M ),
			min2 = *std::min_element( X2, X2+N ), max2 = *std::max_element( X2, X2+N );
	
		std::vector<int> xs;
		rep( i, M )
			xs.push_back( X1[i] );
		rep( i, N )
			xs.push_back( X2[i] );

		std::sort( all( xs ) );

		double ans = 0.0;
		rep( i, xs.size()-1 )
		{
			double a = xs[i], b = xs[i+1], c = (a+b)/2;

			if( min1 <= c && c <= max1 && min2 <= c && c <= max2 )
			{
				double fa = width( X1, Y1, M, a ) * width( X2, Z2, N, a );
				double fb = width( X1, Y1, M, b ) * width( X2, Z2, N, b );
				double fc = width( X1, Y1, M, c ) * width( X2, Z2, N, c );

				ans += (b-a)/6*(fa+4*fc+fb);
			}
		}

		printf( "%.10f\n", ans );
	}

	return 0;
}

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

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

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
  int x;

  VI array;
  VI oddArray;

  FOR(i,1,200){
    if(i*(i+1)*(i+2)/6 <= 1e6){
      array.push_back(i*(i+1)*(i+2)/6);
      if((i*(i+1)*(i+2)/6) % 2 == 1) oddArray.push_back(i*(i+1)*(i+2)/6);
    }


    else break;
  }
  VI dp(1000010,0);
  VI dpOdd(1000010,0);
  rep(i,array.size()){
    dp[array[i]] ++;
  }
  rep(i,oddArray.size()){
    dpOdd[oddArray[i]] ++;
  }
  rep(j,array.size()){
    rep(k,1e6+1){
      if(dp[k] == 0) continue;
      if(array[j]+k >= 1e6) continue;
      if(dp[array[j]+k] >= 1) dp[array[j]+k] = min(dp[k] + 1,dp[array[j]+k]);
      else dp[array[j]+k] = dp[k] + 1;
    }
  }
  rep(j,oddArray.size()){
    rep(k,1e6+1){
      if(dpOdd[k] == 0) continue;
      if(oddArray[j]+k >= 1e6) continue;
      if(dpOdd[oddArray[j]+k] >= 1) dpOdd[oddArray[j]+k] = min(dpOdd[k] + 1,dpOdd[oddArray[j]+k]);
      else dpOdd[oddArray[j]+k] = dpOdd[k] + 1;
    }
  }

  // rep(i,10){
  //   rep(j,array.size()){
  //     int cnt = 0;
  //     if(array[j] % 2 == 0) continue;
  //     FOR(k,1,1e6+1){
  //       if(dp[k].second == 0) continue;
  //       cnt++;
  //       if(array[j]+k >= 1e6) continue;
  //       if(dp[array[j]].first == 0) continue;
  //       if(dp[array[j]+k].first >= 1) continue;
  //       dp[array[j]+k].first += dp[array[j]].first + 1;
  //     }
  //   }
  //}
  while(true){
    cin >> x;
    if(x == 0) return 0;
    cout << dp[x] << ' ' << dpOdd[x] << endl;
    //printf("%d %d\n",dp[x].first,dp[x].second);
  }
  return 0;
}



Measured memory_bytes: 10568