akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace Atcoder
{
    class aaaa
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] frames = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

            double aAve = frames.Average();

            int ans = 0;double diff=1000; double befordiff=10000;
            for (int i =0;i<N;i++){
                diff = Math.Abs(frames[i]-aAve);
                if(diff<befordiff){
                    befordiff = diff;
                    ans = i;
                }
            }

            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = (n); i >= 0; i--)
#define rloop(i, n, a) for(int i = (n); i >= (a); i--)
#define loop(i, a, n) for(int i = (a); i < (n); i++)
#define dd(x) cout << #x << " : " << x << endl
using namespace std;
using ll = int64_t;

struct Comb {
    const ll mod;
    vector<ll> fact, ifact;
    ll mod_pow(ll x, ll n, const ll mod){
        ll ans = 1;
        while(n){
            if(n & 1) ans = ans*x%mod;
            x = x*x%mod;
            n >>= 1;
        }
        return ans;
    }
    Comb(int n, ll mod) : fact(n+1), ifact(n+1), mod(mod) {
        fact[0] = 1;
        loop(i, 1, n+1) fact[i] = fact[i-1] * i % mod;
        ifact[n] = mod_pow(fact[n], mod-2, mod);
        rloop(i, n, 1) ifact[i-1] = ifact[i] * i % mod;
    }
    ll operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]%mod*ifact[n-k]%mod;
    }
};

ll mod_pow(ll x, ll n, const ll mod){
    ll ans = 1;
    while(n){
        if(n & 1) ans = ans*x%mod;
        x = x*x%mod;
        n >>= 1;
    }
    return ans;
}

ll mod_mul(ll a, ll b, const ll mod){
    return (a%mod * b%mod)%mod;
}
ll mod_add(ll a, ll b, const ll mod){
    return ((a%mod) + (b%mod))%mod;
}

int main(){
    const ll mod = 998244353;
    int n, m, k; cin >> n >> m >> k;

    ll def = m * mod_pow(m-1, n-1, mod);

    Comb comb = Comb(n, mod);

    ll ans = 0;
    ll col = m;
    rrep(i, n-1){
        ll now = col;
        now = mod_mul(now, comb(n-1, i), mod);
        if(i <= k) ans = mod_add(ans, now, mod);
        col = mod_mul(col, m-1, mod);
    }
    cout << ans%mod << endl;

    return 0;
}

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

int n =sc.nextInt();
int m =sc.nextInt();
int a[]=new int[n];
for(int i=0;i<m;i++)
a[i]=sc.nextInt();
int s=0;
for(int i=0;i<m;i++)
s=s+a[i];
if(s>n)
System.out.println(-1);
else
System.out.println(n-s);


}
}


Measured memory_bytes: 43364
#include <iostream>
#include <string>

using namespace std;

int main()
{
	string s;
	cin >> s;

	int n = s.length();

	for (int i = 0; i < n / 2; i++)
	{
		if (s[i] != s[n - i - 1])
		{
			cout << "No" << endl;
			return 0;
		}
	}

	for (int i = 0; i < (n - 1) / 2; i++)
	{
		if (s[i] != s[(n - 1) / 2 - i - 1])
		{
			cout << "No" << endl;
			return 0;
		}
	}

	for (int i = (n + 3) / 2; i < n; i++)
	{
		if (s[i] != s[n - i - 1])
		{
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#define DN 200005
using namespace std;
long long n,a[DN],mi,t,rez;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    mi=n;
    for(int i=n;i>=1;i--)
    {
        mi=min(mi,1LL*i);
        t=i-a[i];
        if(t<1||t>mi)
        {
            cout<<-1;
            return 0;
        }
        if(t<mi)
        {
            rez+=i-t;
            mi=t;
        }
    }
    cout<<rez;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
    using namespace std;
     
    int main(){
        int N;
        long long int Y;
        cin >> N >> Y;
        int sum = Y/1000;
        for(int x=N; x>=0; x--){
            for(int y=N-x; y>=0; y--){
                for(int z=N-(x+y); z>=0; z--){
                    if(x*1+y*5+z*10==sum&&x+y+z==N){
                        cout << z << " " << y << " " << x << endl;
                        goto END;
                    }
                }
            }
        }
        cout << "-1 -1 -1" << endl;
    END:
     
        return 0;
    }

Measured memory_bytes: 256
n,m,l=map(int,input().split())
a=[list(map(int,input().split(" "))) for i in range(n)]
b=[list(map(int,input().split(" "))) for i in range(m)]
c=[[0]*l for i in range(n)]

for i in range(n):
    for j in range(l):
        for k in range(m):
            c[i][j]=c[i][j]+a[i][k]*b[k][j]
for d in range(n):
    print(c[d][0],end="")
    for e in range(1,l):
        print(" %d"%c[d][e],end="")

    print()
    
        

            
    


Measured memory_bytes: 7052
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

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

    int n;cin>>n;
    vector<ll> A(n),B(n);
    rep(i,n) cin>>A[i];
    rep(i,n) cin>>B[i];

    ll ans=0;
    rep(k,30){
        vector<ll> a(n),b(n);
        rep(i,n) a[i]=A[i]%(1ll<<(k+1));
        rep(i,n) b[i]=B[i]%(1ll<<(k+1));

        sort(ALL(b));
        ll cnt=0;

        for(ll t=(1ll<<k),y=0;y<4;t+=(1ll<<k),y++){
            // 和がt以上の部分
            rep(i,n){
                ll res=(ll)(b.end()-lower_bound(ALL(b),t-a[i]));
                if(y%2) cnt-=res;
                else    cnt+=res;
            }
        }
        if(cnt%2) ans+=(1ll<<k);
    }
    cout<<ans<<endl;
    return 0;
}


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


int main()
{
    long long int x,y,i;
    cin>>x;
    if(x/500>=1){
        y=(x/500)*1000;
        i=x%500;
        i=(i/5)*5;
        y=y+i;
        cout<<y<<endl;
    }
    else{
        y=(x/5)*5;
        i=x%5;
        i=(i/5)*5;
        y=y+i;
        cout<<y<<endl;
    }

}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
const int MAXN = 2e5 + 1;
int n, m, i, j, k, z;
long long a[MAXN], b[MAXN];
int main()
{
	ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m >> k;
	for (i = 1; i <= n; ++i)
		cin >> a[i], a[i] += a[i - 1];
	for (i = 1; i <= m; ++i)
		cin >> b[i], b[i] += b[i - 1];
	z = 0, i = 0, j = m;
	while (a[i] <= k && i <= n)
	{
		while (b[j] > k - a[i])
			--j;
		z = max(z, i + j);
		++i;
	}
	cout << z;
    return 0;
}

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

int main(void) {
	int count[26] = {};
	string s;
	cin >> s;
	for (int t = 0; t < s.size(); t++) {
		for (int i = 0; i < 26; i++) {
			if (s[t] == 'a' + i) {
				count[i]++;
				break;
			}
		}
	}
	for (int i = 0; i < 26; i++) {
		if (count[i] % 2 == 0) {
			if (i == 25) {
				cout << "Yes" << endl;
			}
		}
		else {
			cout << "No" << endl;
			break;
		}
		
	}
	return 0;
}

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

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>istream &operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
//template <typename T, typename S>ostream &operator<<(ostream &os, pair<T, S> &p) {os << p.first << " " << p.second;return os;}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T, class U>bool chmin(T& a, U b) { if (a > b) { a = b; return true; }return false; }
template <class T, class U>bool chmax(T& a, U b) { if (a < b) { a = b; return true; }return false; }

signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int N, D; cin >> N >> D;
	vector<vector<int>>v(N, vector<int>(D));
	rep(i, 0, N)rep(j, 0, D) { cin >> v[i][j]; }

	auto f = [&](vector<int>a, vector<int>b) {
		int s = 0;
		rep(i, 0, a.size()) {
			s += abs(a[i] - b[i])*abs(a[i] - b[i]);
		}

		int c;
		for (c = 0; c*c < s; c++);
		return c * c == s;
	};

	int ans = 0;
	rep(i, 0, N) {
		rep(j, i + 1, N) {
			ans += f(v[i], v[j]);
		}

	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
import sys
N,M = list(map(int, sys.stdin.readline().rstrip().split())) 
A = list(map(int, sys.stdin.readline().rstrip().split())) 

s = 0
for n in range(M):
  s += A[n]
  
s = N - s
if s < 0:
  print(-1)
else:
  print(s)


Measured memory_bytes: 10036
lis = [list(map(int, input().split())) for _ in range(3)]

n = [0]*4

for i in lis:
    n[i[0]-1] += 1
    n[i[1]-1] += 1

for j in n:
    if j >=3 or j ==0:
        print('NO')
        exit()
print('YES')

Measured memory_bytes: 8944
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder_C
{
    class Program
    {
        /// <summary>
        /// 
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            var input = Enumerable.Range(0, 6).Select(i => Console.ReadLine()).Select(x => long.Parse(x)).ToArray();
            var abcde = input.Skip(1);
            var n = input.First();

            var bottle = Math.Ceiling((decimal)n / abcde.Min());
            Console.WriteLine(bottle + 4);
        }
    }
}


Measured memory_bytes: 13524
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <functional>
#include <stack>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <array>
#include <climits>

using namespace std;

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

const ll MOD = 10e9 + 7;
const ll INF = LLONG_MAX;
const ll MAX_V = 10e3;
const double EPS = 10e-6;
const double PI = 3.14159265359;

//int dx[] = { 0,1,0,-1 }, dy[] = { 1,0,-1,0 };
//int d[] = {0,1,0,-1};
//int nx = x + d[i];
//int ny = y + d[(i+1)%4]

int ipow(int a, int x) {
	int res = 1;
	for (int i = 0; i < x; i++)res *= a;
	return res;
}

int main() {
	string s;
	cin >> s;
	s.pop_back();
	while (1) {
		if (s.size() % 2) {
			s.pop_back();
			continue;
		}
		int l = s.size() / 2;
		bool flag = false;
		for (int i = 0; i < l; i++) {
			if (s[i] != s[i + l])flag = true;
		}
		if (!flag) {
			cout << l*2 << endl;
			break;
		}
		s.pop_back();
	}
	return 0;
}

Measured memory_bytes: 256
# https://abc100.contest.atcoder.jp/tasks/abc100_d
# NOTE: TLE

import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def calc1(tup):
    return tup[0] + tup[1] + tup[2]

def calc2(tup):
    return tup[0] + tup[1] - tup[2]

def calc3(tup):
    return tup[0] - tup[1] + tup[2]

def calc4(tup):
    return tup[0] - tup[1] - tup[2]

def calc5(tup):
    return -tup[0] + tup[1] + tup[2]

def calc6(tup):
    return -tup[0] + tup[1] - tup[2]

def calc7(tup):
    return -tup[0] - tup[1] + tup[2]

def calc8(tup):
    return -tup[0] - tup[1] - tup[2]
def calc1(tup):
    return tup[0] + tup[1] + tup[2]

def calc2(tup):
    return tup[0] + tup[1] - tup[2]

def calc3(tup):
    return tup[0] - tup[1] + tup[2]

def calc4(tup):
    return tup[0] - tup[1] - tup[2]

def calc5(tup):
    return -tup[0] + tup[1] + tup[2]

def calc6(tup):
    return -tup[0] + tup[1] - tup[2]

def calc7(tup):
    return -tup[0] - tup[1] + tup[2]

def calc8(tup):
    return -tup[0] - tup[1] - tup[2]


def main():
    n, m = map(int, input().split())
    xyzl = []
    for _ in range(n):
        x, y, z = map(int, input().split())
        xyzl.append((x,y,z))

    ans = 0
    xyzl.sort(key=lambda xyz: -calc1(xyz))
    ans = max(ans, sum([calc1(xyz) for xyz in xyzl[:m]]))
    xyzl.sort(key=lambda xyz: -calc2(xyz))
    ans = max(ans, sum([calc2(xyz) for xyz in xyzl[:m]]))
    xyzl.sort(key=lambda xyz: -calc3(xyz))
    ans = max(ans, sum([calc3(xyz) for xyz in xyzl[:m]]))
    xyzl.sort(key=lambda xyz: -calc4(xyz))
    ans = max(ans, sum([calc4(xyz) for xyz in xyzl[:m]]))

    xyzl.sort(key=lambda xyz: -calc5(xyz))
    ans = max(ans, sum([calc5(xyz) for xyz in xyzl[:m]]))
    xyzl.sort(key=lambda xyz: -calc6(xyz))
    ans = max(ans, sum([calc6(xyz) for xyz in xyzl[:m]]))
    xyzl.sort(key=lambda xyz: -calc7(xyz))
    ans = max(ans, sum([calc7(xyz) for xyz in xyzl[:m]]))
    xyzl.sort(key=lambda xyz: -calc8(xyz))
    ans = max(ans, sum([calc8(xyz) for xyz in xyzl[:m]]))

    print(ans)


if __name__ == '__main__':
    main()



Measured memory_bytes: 40176
#include<stdio.h>
#include<string.h>
using namespace std;

int a[20], n, cnt;
int b[3] = {3, 5, 7};
int ok(int x)
{
    if (x > 0) return x;
    return -x;
}


void dfs(int x, int y)
{
    int i;
    if (x == 0)
    {
        if (a[3] && a[5] && a[7] && y <= n) 
            {
                ++cnt;
          //      printf("%d\n", y);
            }
        return;
    }
    for (i = 0; i < 3; ++i)
    {
        ++a[b[i]];
        dfs(x - 1, y * 10 + b[i]);
        --a[b[i]];
    }
}
int main()
{
    int i, l, len = 0;
    scanf("%d", &n);
    l = n;
    while (l)
    {
        ++len;
        l /= 10;
    }

    for (i = 3; i <= len; ++i) 
        {
            dfs(i, 0);
          //  printf("%d %d %d\n", a[3], a[5], a[7]);
        }
    printf("%d", cnt);
    return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;
class Main{
    int n,x,y,c;
    public void solve(){
        Scanner sc = new Scanner(System.in);
        sc.useDelimiter("\\s");
        n = sc.nextInt();
        int a[][] = new int [12][10];
        for(x = 0; x < 12; x++){
            for(y = 0; y < 10; y++){
                a[x][y] = 0;
            }
        }
        
        for(x = 0; x < n; x++){
            int b = sc.nextInt();
            int f = sc.nextInt();
            int r = sc.nextInt();
            int v = sc.nextInt();
            if(b == 1){
                a[f-1][r-1] += v;
            }else if(b == 2){
                a[f+2][r-1] += v;
            }else if(b == 3){
                a[f+5][r-1] += v;
            }else if(b == 4){
                a[f+8][r-1] += v;
            }else{
                continue;
            }
        }
        for(y = 0; y < 12; y++){
            for(c = 0; c < 10; c++){
                System.out.printf(" %d",a[y][c]);
            }
            System.out.println();      
            if(y % 3 == 2 && y != 11){
                System.out.println("####################");
            }
        }
    }
    public static void main(String[] args){
        new Main().solve();
    }
}

Measured memory_bytes: 23188
#include <iostream>
#include <string>

using namespace std;

int main(){
    int n,x=0;
    string s;
    
    int ans=0;

    cin>>n>>s;

    for(int i=0;i<n;i++){
        if(s[i]=='I')x++;
        else if(s[i]=='D')x--;

        if(x>ans){
            ans=x;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n;
    int num=0, num_even=0;
    cin >> n;
    int a[n];
    for (int i=0; i<n;i++){
        cin >> a[i];
    }
    for (int i =0; i<n;i++){
        if (a[i]%2==0)
        {
            if(a[i]%3==0 || a[i]%5==0){
                num++;
            }
            num_even++;

        }

    }
    if(num==num_even){
        cout << "APPROVED";
    }
    else
        cout << "DENIED";

    return 0;
}


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

int main(){
  int k; cin>>k;
  int a[1001001];
  int ans=0;
  bool flag = 0;
  rep(i,k){
    if(i==0) a[i] = 7 % k;
    else a[i] = (10 * a[i-1] + 7) % k;
    ans++;
    if(a[i]==0){flag=1; break;}
  }
  if(flag) cout<<ans<<endl;
  else cout<<-1<<endl;
}



Measured memory_bytes: 7528
// VSのおまじない
#define _CRT_SECURE_NO_WARNINGS 0

#include<stdio.h>

void problem_a(void);

// メイン関数
int main(void) {
	
	problem_a();

	return 0;
}


void problem_a(void) {
	int a, b;

	//入力
	scanf("%d %d",&a,&b);
	
	// 3匹のヤギが同じ枚数食べられるか？
	if ((a + b) % 3 == 0 || a%3 ==0 || b%3==0) {
		printf("Possible");
	}
	else {
		printf("Impossible");
	}

	return;
}

Measured memory_bytes: 128
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n,k,q=MI()
aa=LI()
pp=list(sorted(set(aa)))

# 最大-最小を返す
def diff(p):
    can=[]
    cur=[]
    for a in aa+[-1]:
        if a<p:
            if len(cur)==n:
                can=cur
                break
            if len(cur)>=k:
                cur.sort()
                if k==1:can+=cur
                else:can+=cur[:-(k-1)]
            cur=[]
        else:
            cur.append(a)
    if len(can)<q:
        return -1
    can.sort()
    res=can[q-1]-can[0]
    return res

#print(pp)
ans=10**16
for p in pp:
    ret=diff(p)
    if ret==-1:break
    #print(p,ret)
    ans=min(ans,ret)

print(ans)


Measured memory_bytes: 69472
/*
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#ifdef LOCAL
#include "debug.h"
#else
#include<bits/stdc++.h>
using namespace std;
#define debug(x...)
#endif
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> 
using ordered_set= tree<T, null_type, 
		less<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
template<class T> 		
using ordered_mset= tree<T, null_type, 
		less_equal<T>, 
		rb_tree_tag, tree_order_statistics_node_update> ;
		
*/
 
/*
 
PBDS
-------------------------------------------------
			0 based indexing
-------------------------------------------------			 
1) insert(value)
2) erase(value)
3) order_of_key(value) // Number of items strictly smaller than value
4) *find_by_order(k) : K-th element in a set (counting from zero)
 
*/
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());	

void solve()
{
	int n,x,t;
	cin>>n>>x>>t;
	
	cout<<t*(1+(n-1)/x);
}		

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int testcase=1;
	//cin>>testcase;
	
	for(int i=1;i<=testcase;i++)
	{
		//cout<<"Case "<<i<<": ";
		solve();
	}
	
	#ifdef LOCAL
	cerr<<"\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms\n";
	#endif
	
	
	return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
const char nl = '\n';
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 3010;

string s, t;
int dp[N][N];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> s >> t;
  int n = s.size(), m = t.size();
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
      if (s[i-1] == t[j-1]) {
        dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
      }
    }
  }
  string ans;
  int ci = n, cj = m;
  while (ci && cj) {
    if (dp[ci-1][cj] == dp[ci][cj]) {
      ci--;
    } else if (dp[ci][cj-1] == dp[ci][cj]) {
      cj--;
    } else {
      assert(s[ci-1] == t[cj-1] && dp[ci-1][cj-1] + 1 == dp[ci][cj]);
      ans.push_back(s[ci-1]);
      ci--;
      cj--;
    }
  }
  reverse(ans.begin(), ans.end());
  cout << ans << nl;
  return 0;
}


Measured memory_bytes: 35584
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
#include <boost/range/adaptors.hpp>

using namespace std;
using boost::adaptors::reversed;
using boost::irange;
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long int;

int main() {
    array<ll, 3> a;
    for (auto &&i: irange(0LL, 3LL)){
        cin >> a.at(i);
    }
    auto m = max_element(a.begin(), a.end());
    ll K;
    cin >> K;
    for (auto &&i: irange(0LL, K)){
        *m *= 2;
    }
    cout << accumulate(a.begin(), a.end(), 0LL) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long int lo;
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define inf (lo)1e10 + 7
#define FOR for(lo i = 0 ; i < n ; i++)
#define FORV for(lo i = 0 ; i < (lo)v.size() ; i++)
#define ii pair<lo,lo>
#define iii pair<lo, pair<lo,lo> >
#define si pair<string,lo>
lo a,b,c,d,e,n,m,k,t,h,x,y,a1[100005],a2[100005];
char c1,c2,c3,c4;
string s1,s2,s3,s4;
double d1,d2,d3;
vector <lo> v;
map <lo,lo> mp1;
map <lo,lo> mp2;
set <lo> stt;
queue <lo> q;
priority_queue <lo> pq;
lo vis [10000];
int main() {
    // freopen("gir.gir", "r", stdin);
    // freopen("cik.cik", "w", stdout);
    cin >> n >> a >> b;
    cout << min(n * a, b) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<double> x(N);
  vector<double> y(N);
  
  for(int i = 0;i < N;i++)cin >> x[i] >> y[i];

  vector<int> num;
  for(int i = 0;i < N;i++)num.push_back(i);

  double ans = 0;

  do{
    for(int i = 0;i < N-1;i++){
      double xx = x[num[i]] - x[num[i+1]];
      double yy = y[num[i]] - y[num[i+1]];
      ans += sqrt(xx*xx + yy*yy);
    }
  }while(next_permutation(num.begin(),num.end()));

  double n_c = 1;
  for(int i = N;i >= 2;i--)n_c *= i;

  printf("%.10lf\n",ans/n_c);

}

Measured memory_bytes: 256
#include<cstdio>

int main(){
    int a,b,d,r;
    double f;
    scanf("%d %d", &a, &b);
    d = a / b;
    r = a % b;
    f = double(a) / double(b);
    
   printf("%d %d %.5lf\n", d, r, f );
    
    return 0;
}


Measured memory_bytes: 2764
#include<stdio.h>
int main(){
  long long a,num=26;
  scanf("%lld",&a);
  int count=0;
  while(a>num){
    a-=num;
    num*=26;
    count++;
  }
  char s[count+1];
  int i;
  for(i=0;i<count+1;i++){
    num/=26;
    long long b=(a-1)/num;
    s[i]='a'+b;
    a-=b*num;
    printf("%c",s[i]);
  }
  puts("");
  return 0;
}


Measured memory_bytes: 1656
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;
typedef long long int ll;

int N;
set<int> st[100005];
queue<int> que;

int main() {
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    st[a].insert(b);
    st[b].insert(a);
  }

  for (int i = 0; i < N; i++) {
    if (st[i].size() == 1) {
      que.push(i);
    }
  }

  while (!que.empty()) {
    int p = que.front();
    que.pop();

    if (st[p].empty()) {
      cout << "First" << endl;
      return 0;
    }

    int q = *st[p].begin();
    for (auto i : st[q]) {
      st[i].erase(q);
      if (st[i].size() == 1) {
        que.push(i);
      }
    }
  }

  cout << "Second" << endl;

  return 0;
}


Measured memory_bytes: 14464
m;n="Thurs\0Fri\0__Satur\0Sun\0__Mon\0__Tues\0_Wednes";main(d){for(;scanf("%d%d",&m,&d),m;printf("%sday\n",n+(d-13*~m/5)%7*6))m<3?d-=2,m+=12:0;}

Measured memory_bytes: 0
# https://img.atcoder.jp/abc054/editorial.pdf

N, M = map(int, input().split())

graph = [[False for _ in range(N)] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  graph[a-1][b-1] = graph[b-1][a-1] = True

def dfs(v, visited):
  all_visited = True
  for i in range(N):
    if not visited[i]:
      all_visited = False
      
  if all_visited:
    return 1
  
  ret = 0
  for i in range(N):
    if not graph[v][i]: continue
    if visited[i]: continue
    
    visited[i] = True
    ret += dfs(i, visited)
    visited[i] = False
  
  return ret

visited = [False] * N
visited[0] = True
ans = dfs(0, visited)
print(ans)


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

signed main()
{
   int N; cin>>N;
   vector<double> t(N+1);
   vector<double> v(N+1);
   for(int i=0;i<N;i++) cin>>t[i+1];
   for(int i=0;i<N;i++) cin>>v[i];

   for(int i=0;i<N;i++){
      t[i+1]+=t[i];
   }
   v[N]=0;

   double curT=1;
   double preV=0.0;

   double ans=0.0;
   for(int i=0;i<N;i++){
      while(curT<=2*t[i+1]){
         double curV=preV+0.5;
         curV=min(curV,v[i]);
         for(int j=i+1;j<=N;j++){
            curV=min(curV,v[j]+(2*t[j]-curT)*0.5);
         }
         ans+=(preV+curV)*0.25;
         curT++;
         preV=curV;
      }
   }
   cout<<fixed<<setprecision(10)<<ans<<endl;
}


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

typedef long long ll;
typedef pair<ll, ll> P;


#define rep(i,n) for(ll (i)=0; (i)<(ll)(n); (i)++)
#define frep(i,m,n) for(ll (i)=(m); (i)<=(ll)(n); (i)++)
#define rrep(i,n) for(ll (i)=(n)-1; (i)>-1; (i)--)
#define frrep(i,m,n) for(ll (i)=(n); (i)>(ll)(m); (i)--)
#define ALL(x) (x).begin(), (x).end()

const ll INF = 100100100100100100;
const ll MOD = 1000000007;

// get abs
ll my_abs(ll a);
// a^n
ll a_n(ll a, ll n);
// get gcd
ll my_gcd(ll a, ll b);
// a^(-1) % MOD 
ll inv(ll a);
// (a+b+c)%MOD
ll madd(ll a, ll b, ll c);
// (a-b)%MOD
ll msub(ll a, ll b);
// (a*b*c)%MOD
ll mtime(ll a, ll b, ll c);

ll my_min(ll a, ll b, ll c) {
    ll ret = min(a, b);
    ret = min(ret, c);
    return ret;
}
ll my_max(ll a, ll b, ll c) {
    ll ret = max(a, b);
    ret = max(ret, c);
    return ret;
}


int main() {
    ll h, w, ans = INF; cin >> h >> w;
    if((h%3) == 0 || (w%3) == 0) {
        ans = 0;
    }
    else {
        // 横一直線と縦半分
        frep(i, 1, h-1) {
            ll a = w*i, b, c;
            if(w%2 == 0) {
                b = (w/2)*(h-i);
                c = (w/2)*(h-i);
            }
            else {
                b = (w/2)*(h-i);
                c = ((w+1)/2)*(h-i);
            }
            if(ans > my_max(a, b, c)-my_min(a, b, c)) {
                ans = my_max(a, b, c)-my_min(a, b, c);
            }
        }
        // 縦一直線と横半分
        frep(i, 1, w-1) {
            ll a = h*i, b, c;
            if(h%2 == 0) {
                b = (h/2)*(w-i);
                c = (h/2)*(w-i);
            }
            else {
                b = (h/2)*(w-i);
                c = ((h+1)/2)*(w-i);
            }
            if(ans > my_max(a, b, c)-my_min(a, b, c)) {
                ans = my_max(a, b, c)-my_min(a, b, c);
            }
        }
        // 横に2回切る
        if(h >= 3) {
            ll a = ((h+2)/3)*w, b = (h/3)*w;
            if(ans > a-b) ans = a-b;
        }
        // 縦に2回切る
        if(w >= 3) {
            ll a = ((w+2)/3)*h, b = (w/3)*h;
            if(ans > a-b) ans = a-b;
        }
    }
    cout << ans << endl;
    return 0;
}

ll my_abs(ll a) {
    if(a >= 0) return a;
    else return -1 *a;
}

ll a_n(ll a, ll n) { 
    if(n == 0) return 1;
    
    ll ret = a, count = 1;
    while(count * 2 < n) {
        ret *= ret;
        count *= 2;
    }
    if(count == n) return ret;
    else return (ret * a_n(a, n-count));
}

ll my_gcd(ll a, ll b) {
    if(b == 0) return a;
    return my_gcd(b, a%b);
}

ll inv(ll a) {
    return a_n(a, MOD-2);
}

ll madd(ll a, ll b, ll c) {
    ll ret = (a+b) % MOD;
    return (ret+c) % MOD;
}

ll msub(ll a, ll b) {
    if(a < b) return (a-b+MOD) % MOD;
    else return (a-b) % MOD;
}

ll mtime(ll a, ll b, ll c) {
    ll ret = (a*b) % MOD;
    return (ret*c) % MOD;
}


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

using namespace std;

int n;
int a[2][110];
int ans;

int main()
{
	cin>>n;
	int i,j;
	for (i=1;i<=n;i++)cin>>a[0][i];
	for (i=1;i<=n;i++)a[0][i]+=a[0][i-1];
	
	for (i=1;i<=n;i++)cin>>a[1][i];
	for (i=n;i>=1;i--)a[1][i]+=a[1][i+1];
	
	for (i=1;i<=n;i++)ans=max(ans,a[0][i]+a[1][i]);
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 256
/*
  The Island Was Silent before.
  .....
  And One day again it became Silent.
*/
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ll  long long
#define modd(a,b) ((a+2*b)%b)
#define debug(a) cout << #a << ": " << (a) << "\n"
#define ioso ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define rtt cerr << "Time: " << clock()*1.0 / CLOCKS_PER_SEC << endl;
#define ffe freopen("input.txt","r",stdin), freopen("output.txt","w",stdout);

int main() {
  #ifndef ONLINE_JUDGE
  ioso ffe
  #endif
  int k; string s; cin >> k >> s;

  for(int i=0;i<min(k,(int)s.length());i++) {
    cout << s[i];
  }

  if(s.length()>k) {
    cout << "..." << endl;
  }
  
}

Measured memory_bytes: 3628
N=int(input())
A=list(map(int,input().split()))

if N==0:
    if A[0]==1:
        print(1)
        exit()
    else:
        print(-1)
        exit()

bunki=sum(A)-1

ans=[0]*(N+1)
ans[0]=1

for i in range(N):
    if bunki>0:
        bunki_use=min(bunki,ans[i]-A[i])
        bunki-=bunki_use
        ans[i+1]=ans[i]+bunki_use-A[i]
    else:
        ans[i+1]=ans[i]-A[i]

    if ans[i+1]<1:
        print(-1)
        exit()

if ans[N]!=A[N]:
    print(-1)
    exit()

print(sum(ans))

Measured memory_bytes: 20148
#include <iostream>

using namespace std;

int main() {

    int num;
    cin >> num;

    int min;
    cin >> min;

    int max;
    cin >> max;

    if ((max - min) > num) {
        cout << "OK";
        return 0;
    }

    for (int i=min; i<=max; i++) {
        if (i%num == 0) {
            cout << "OK";
            return 0;
        }
    }

    cout << "NG";
    
    return 0;
}

Measured memory_bytes: 3632
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var A, B int
	fmt.Scan(&A)
	fmt.Scan(&B)

	c := 0
	for num := A; num <= B; num++ {
		if isPalindrome(num) {
			c++
		}
	}

	fmt.Println(c)
}

func isPalindrome(num int) bool {
	s := strconv.Itoa(num)

	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i:i+1] != s[j:j+1] {
			return false
		}
	}

	return true
}

Measured memory_bytes: 1024
/**
	Language: C++ 11
	Author  : ebby21
**/

#include <bits/stdc++.h>

using namespace std;

#define FASTIO() ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define DEBUG(var) cerr << '\n' << #var << "\t:\t" << var << '\n'
#define FORF(i, L, U) for (ll i = (L); i <= (U); ++i)
#define FORR(i, U, L) for (ll i = (U); i >= (L); --i)
#define FORE(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef unsigned int ui;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;

int main() {
	FASTIO();
	int L;
	cin >> L;
	cout << fixed << setprecision(12) << L*L*L/27.0 << "\n";
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 100010
typedef long long ll;
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,k,a[N];
int main(){
	n=read();
	k=1;
	while((k<<1)<=n)k<<=1;
	if(k==n)return !printf("No\n");
	if((k<<1)==n+1)k<<=1;
	printf("Yes\n");
	for(int i=1;i<=k;++i){
		a[i]=i;
	}
	if(!(n&1)){
		int t=n^k^1;
		for(int i=t;i>2;--i){
			swap(a[i],a[i-1]);
		}
		printf("%d %d\n",n,k);
		printf("%d %d\n",2*n,a[2]);
	}
	for(int i=1;i<k-1;++i){
		printf("%d %d\n",a[i],a[i+1]);
		printf("%d %d\n",a[i]+n,a[i+1]+n);
	}
	printf("%d %d\n",a[1],a[k-1]+n);
	for(int i=k;i<n;i+=2){
		printf("%d %d\n",i,i+1);
		printf("%d %d\n",i,1);
		printf("%d %d\n",i+1+n,1);
		printf("%d %d\n",i+n,i+1+n);
	}
	return 0;
}




Measured memory_bytes: 3920
from collections import Counter
n = int(input())
d = [input() for _ in range(n)]
c = Counter(d).most_common()
now = c[0][1]

data = []
for x in c:
    if x[1] < now:
        break
    data.append(x[0])
data.sort()
for x in data:print(x)

Measured memory_bytes: 121680
from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
m = [0]*n

l, r = [0]*n, [0]*n
for i in range(1, n):
    l[i] = gcd(a[i-1], l[i-1])
    r[n-1-i] = gcd(r[n-i], a[n-i])

ans = 1
for a, b in zip(l, r):
    x = gcd(a, b)
    if ans < x:
        ans = x

print(ans)

Measured memory_bytes: 89580
#include<bits/stdc++.h>
using namespace std;
int main(){
  int d,e;
  while(cin>>d>>e,d){
    double ans=1e9;
    for(int i=0;i<=d;++i){
      ans=min(ans,abs(sqrt(i*i+(d-i)*(d-i))-e));
    }
    cout<<ans<<endl;
  }
  return 0;
}

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

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

using namespace std;

template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

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

    int H, N;
    cin >> H >> N;
    vector<int> A(N), B(N);
    REP(i, N) cin >> A[i] >> B[i];

    vector<int> dp(H + 1, INT_MAX);
    dp[0] = 0;
    FOR(h, 1, H + 1) {
        REP(i, N) {
            amin(dp[h], dp[max(h - A[i], 0)] + B[i]);
        }
    }

    cout << dp[H] << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cassert>
using namespace std;
#define N 200
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,a[N],ans[N],t[N];
namespace grader{
	char s[N];
	int Ask(int *a){
		int cnt0=0,cnt1=0;
		for(int i=1;i<=n;++i){
			if(s[a[i]]=='R')++cnt1;
			else ++cnt0;
		}
		return cnt1>cnt0;
	}
}
int Query(int *a){
	printf("? ");
	for(int i=1;i<=n;++i){
		printf("%d ",a[i]);
	}
	printf("\n");
	fflush(stdout);
	//return grader::Ask(a);
	static char qwq[10];
	scanf("%s",qwq+1);
	assert(qwq[1]^'-');
	return qwq[1]=='R';
}
int main(){
	n=read();
	//scanf("%s",grader::s+1);
	memset(ans,-1,sizeof(ans));
	for(int i=1;i<=n;++i){
		a[i]=i;
	}
	t[1]=Query(a);
	t[n+1]=t[1]^1;
	int l=1,r=n+1;
	while(r-l>1){
		int mid=(l+r)>>1;
		for(int i=1;i<=n;++i){
			a[i]=mid+i-1;
		}
		t[mid]=Query(a);
		if(t[mid]==t[1]){
			l=mid;
		}
		else{
			r=mid;
		}
	}
	int pos=l;
	ans[pos]=t[1],ans[pos+n]=t[n+1];
	for(int i=1;i<n;++i){
		a[i]=pos+i;
	}
	for(int i=1;i<pos;++i){
		a[n]=i;
		ans[i]=Query(a);
	}
	for(int i=pos+n+1;i<=(n<<1);++i){
		a[n]=i;
		ans[i]=Query(a);
	}
	for(int i=pos+1;i<pos+n;++i){
		int u=0;
		for(int j=pos;j<=pos+n;++j){
			if(j==i)continue;
			a[++u]=j;
		}
		assert(u==n);
		ans[i]=Query(a)^1;
	}
	printf("! ");
	for(int i=1;i<=(n<<1);++i){
		assert(~ans[i]);
		putchar(ans[i]?'R':'B');
	}
	putchar('\n');
	fflush(stdout);
	return 0;
}



Measured memory_bytes: 3836
#include <stdio.h>
int main(void)
{
	double a,b,c,d,e,f,x,y;
	while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f) != EOF)
		{
			y = (c*d - a*f)/(b*d - a*e);
			x = (c - b*y)/a;
			printf("%.3lf %.3lf\n",x,y);
		}

						
	
	return 0;
}

Measured memory_bytes: 652
import cmath
pi = cmath.pi
exp = cmath.exp

import sys
readline = sys.stdin.readline
write = sys.stdout.write

def make_exp_t(N, base):
    exp_t = {0: 1}
    temp = N
    while temp:
        exp_t[temp] = exp(base / temp)
        temp >>= 1
    return exp_t

def fft_dfs(f, s, N, st, exp_t):
    if N==2:
        a = f[s]; b = f[s+st]
        return [a+b, a-b]
    N2 = N//2; st2 = st*2
    F0 = fft_dfs(f, s   , N2, st2, exp_t)
    F1 = fft_dfs(f, s+st, N2, st2, exp_t)
    w = exp_t[N]; wk = 1.0
    for k in range(N2):
        U = F0[k]; V = wk * F1[k]
        F0[k] = U + V
        F1[k] = U - V
        wk *= w
    F0.extend(F1)
    return F0

def fft(f, N):
    if N==1:
        return f
    return fft_dfs(f, 0, N, 1, fft_exp_t)

def ifft(F, N):
    if N==1:
        return F
    f = fft_dfs(F, 0, N, 1, ifft_exp_t)
    for i in range(N):
        f[i] /= N
    return f

N,M = map(int,input().split())

l = 10**5+1
L = 2**(2*l-1).bit_length()

power = list(map(int,input().split()))
count = [0.0 for _ in range(l)]

for p in power:
    count[p] += 1

fft_exp_t = make_exp_t(L, -2j*pi)
ifft_exp_t = make_exp_t(L, 2j*pi)

count.extend([0]*(L-l))

C = fft(count, L)

CC =[C[i]*C[i] for i in range(L)]

cc = ifft(CC,L)

shake = 0
ans = 0

for i in reversed(range(len(cc))):
    if shake+int(cc[i].real+0.5)<=M:
        ans += i*int(cc[i].real+0.5)
        shake += int(cc[i].real+0.5)
    else:
        ans += i*(M-shake)
        break
        
print(ans)

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

int main()
{
  int n,x,y;
  cin>>n;
  y=0;

  for(int i=0;i<n;i++)
  {
    int l,r;
    cin>>l>>r;
    x=r-l+1;
    y+=x;
  }
  cout<<y<<endl;
}


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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7, inf = 1e9, MAXN = 1e5 + 5, off = 1 << 17;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

struct Tournament{
  ll t[2 * off], p1[2 * off], p2[2 * off];
  Tournament(){ REP(i, 2 * off) t[i] = p1[i] = p2[i] = 0; }
  ll sum(ll x){
    return x * (x + 1) / 2;
  }
  void prop(int x, int lo, int hi){
    if(p1[x] == 0 && p2[x] == 0) return;
    t[x] += (hi - lo) * p2[x];
    t[x] += sum(hi - lo) * p1[x];

    if(x < off){
      p1[x * 2] += p1[x];
      p1[x * 2 + 1] += p1[x];
      p2[x * 2] += p2[x];
      p2[x * 2 + 1] += p2[x] + p1[x] * (hi - lo) / 2;
    }
    p1[x] = p2[x] = 0;
  }
  void construct(int x, int lo, int hi){
    prop(x, lo, hi);
    if(x >= off) return;
    int mid = (lo + hi) >> 1;
    construct(x * 2, lo, mid); construct(x * 2 + 1, mid, hi);
  }
  void update(int x, int lo, int hi, int a, int b, int tip, int val){
    if(lo >= hi) return;
    prop(x, lo, hi);
    if(lo >= b || hi <= a) return;
    if(lo >= a && hi <= b){
      if(tip == 0){
        p2[x] += val;
      }
      else{
        p1[x] --;
        p2[x] -= (lo - a);
        p2[x] += val;
      }
      prop(x, lo, hi);
      return;
    }
    int mid = (lo + hi) >> 1;
    update(x * 2, lo, mid, a, b, tip, val); update(x * 2 + 1, mid, hi, a, b, tip, val);
  }
} T;

int n, m;
int a[MAXN];

int dist(int x, int y){
  if(x <= y) return y - x;
  return ( m - (x - y) );
}

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

  cin >> n >> m;
  REP(i, n) cin >> a[i];
  FOR(i, 1, n){
    int d = dist(a[i - 1], a[i]);
    //TRACE(d);
    if(a[i - 1] <= a[i]){
      T.update(1, 0, off, a[i - 1] + 1, a[i] + 1, 1, d + 1);
      //cout << a[i - 1] + 1 _ a[i] + 1 _ d << "\n";
      T.update(1, 0, off, a[i] + 1, m + 1, 0, d);
      T.update(1, 0, off, 1, a[i - 1] + 1, 0, d);
    }
    else{
      T.update(1, 0, off, a[i - 1] + 1, m + 1, 1, d + 1);
      T.update(1, 0, off, 1, a[i] + 1, 1, dist(0, a[i]) + 1);
      T.update(1, 0, off, a[i] + 1, a[i - 1] + 1, 0, d);
    }
    //T.construct(1, 0, off);
    //FOR(i, 1, m + 1) cout << T.t[i + off] << " ";
    //cout << "\n";
  }
  T.construct(1, 0, off);
  ll sol = 1e18;
  FOR(i, 1, m + 1) sol = min(sol, T.t[i + off]);
  cout << sol;
}


Measured memory_bytes: 6784
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <cstdio>
#include <cstdint>
using namespace std;

int_fast8_t d;
uint_fast32_t M = 0;
uint_fast64_t c, sd = -1, sc = -1;
constexpr int buff_size = 1 << 17;
char buff[buff_size], *ci = buff + buff_size, *ce = ci, ct;

inline char read_input() {
    if (ci == ce) { fread_unlocked(buff, 1, buff_size, stdin); ci = buff; }
	return *ci++;
}

int main() {
    while((ct=read_input()) > 47) M = (M<<1) + (M<<3) + ct - 48;
    while(M--) {
        if(ci + 18 > ce) {
            d = read_input() - 48;
            read_input();
            for(c=0; (ct=read_input()) > 47;) c = (c<<1) + (c<<3) + ct - 48;
        } else {
            d = *ci - 48;
            ci += 2;
            for(c=0; *ci > 47;) c = (c<<1) + (c<<3) + *ci++ - 48;
            ci++;
        }
        sc += c;
        sd += c * d;
    }
    printf("%lld", sc + sd / 9);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long int li;
typedef long long ll;
typedef long double ld;

void solve()
{
	int n, s = 0;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++)
	{
        cin >> a[i];
        if ((i + 1) % 2 && a[i] % 2)
			s++;
	}
	cout << s << "\n";
}

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


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

int main(void)
{
  int n, c, i, sum = 0;
  scanf("%d", &n);
  int d[n];
  for(i = 0; i < n; ++i) {
    scanf("%d", &d[i]);
  }
  for(i = 0; i < n; ++i) {
    scanf("%d", &c); d[i] -= c;
  }
  for(i = 0; i < n; ++i) {
	if(d[i] > 0) { sum += d[i]; }
  }
  printf("%d\n", sum);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;
#define int              long long

#define pb              push_back
#define mp              make_pair
#define vi              vector<int>
void ash()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
int32_t main()
{
ash();
int N,sum=0,t;
int M;
cin>>N;
cin>>M;
vi a(M);
for(int i=0;i<M;i++)
{
cin>>t;
a.emplace_back(t);
sum=sum+t;
}
if(sum>N)
cout<<"-1";
else cout<<N-sum;
    
}
 

Measured memory_bytes: 3736
#include <iostream>
#include <stack>
#include <sstream>

using namespace std;

int main() {
  string line;
  getline(cin, line);
  
  stack<int> stack;

  stringstream ss(line);
  string word;
  while (ss >> word) {
    if (word == "+") {
      int v1 = stack.top();
      stack.pop();
      int v2 = stack.top();
      stack.pop();

      stack.push(v2 + v1);
    } else if (word == "-") {
      int v1 = stack.top();
      stack.pop();
      int v2 = stack.top();
      stack.pop();

      stack.push(v2 - v1);
    } else if (word == "*") {
      int v1 = stack.top();
      stack.pop();
      int v2 = stack.top();
      stack.pop();

      stack.push(v2 * v1);
    } else {
      // operand
      stringstream ss2(word);
      int val = 0;
      ss2 >> val;
      stack.push(val);
    }
  }
  
  int v = stack.top();
  cout << v << endl;

  return 0;
}

Measured memory_bytes: 1232
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

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

typedef long long ll;

int main() {
	int n;
	cin >> n;
	
	ll l = 1, r = 1;
	REP(i, n) {
		ll t, a;
		scanf("%lld %lld", &t, &a);
		
		ll x = max(l / t + (l % t > 0), r / a + (r % a > 0));
		l = t * x;
		r = a * x;
	}
	cout << l + r << endl;
	return 0;
}


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

int main(){
	int N,K,Q; cin>>N>>K>>Q;
	vector<int> ans(N+1, K-Q);
	for(int i=0; i<Q; ++i){ int a; cin>>a; ans[a]++; }
	for(int i=1; i<=N; ++i) puts(ans[i]>0? "Yes":"No");
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cmath>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <string>
#include <cstring>
#include <queue>

using namespace std;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define S(x) scanf("%d",&x)
#define S2(x,y) scanf("%d%d",&x,&y)
#define P(x) printf("%d\n",x)
#define all(v) v.begin(),v.end()
#define FF first
#define SS second
#define pb push_back
#define mp make_pair

typedef long long int LL;
typedef pair<int, int > pii;
typedef vector<int > vi;

int main() {
  string s;
  cin >> s;
  LL ans = 0;
  int b = 0;
  rep(i,0,s.size()) {
    if(s[i] == 'B') b++;
    else ans += b;
  }
  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 640
import sys 
import math

#X = int(input())
#a = list(map(int, input().split(" ")))
#a = [0 for i in range(X+1)]
S = input()
T = input()

flag = False

for i in range(len(S)):
    cmp_str = S[len(S)-1] + S[0:len(S)-1]
    S =  S[len(S)-1] + S[0:len(S)-1]
    #print(cmp_str)
    if(cmp_str == T):
        flag = True
        break

if(flag):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
typedef long long ll;

using namespace std;

ll chat_in_a_circle(int n, ll a[]) {
  vector<ll> b;
  for(int i=0;i<n;i++) {
    //cout << a[i];
    b.push_back(a[i]);
  }

  sort(b.begin(), b.end());
  /*
  for(int i=0;i<n;i++) {
    cout << b[i];
  }
  cout << endl;
  */

  ll ans = 0;
  for(int i=0;i<n-1;i++) {
    //cout << b[n - ((int) (i / 2))] << endl;
    //cout << b[(n-1)- ((int) ((i+1)/ 2))] <<endl;
    ans += b[(n-1)- ((int) ((i+1)/ 2))];
  }
  return ans;
}

int main() {
  int n;
  cin >> n;
  ll a[n];
  for(int i=0;i<n;i++) {
    cin >> a[i];
  }
  cout << chat_in_a_circle(n, a);
}

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

int main(){
  int q, query, x, L, R;
  scanf("%d", &q);
  multiset<int> S;
  for(int i = 0; i < q; i++){
    scanf("%d", &query);
    if(query == 3){
      scanf("%d %d", &L,&R);
      auto it = S.lower_bound(L);
      for(auto i = it; i != S.end() && *i <= R; i++){
        printf("%d\n", *i);
      }
    }else{
      scanf("%d", &x);
      if(query == 0){
        S.insert(x);
        printf("%d\n", S.size());
      }else if(query == 1){
        printf("%d\n", S.count(x));
      }else{
        S.erase(x);
      }
    }
  }
  return 0;
}



Measured memory_bytes: 12448
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>

using namespace std;

typedef long long ll;



int main(){
    string s;
    cin>>s;
    int ans=0,real=1000000;
    map<char,int>ma;
    for(int i=0;i<s.length();i++){
        ma[s[i]]++;
    }
    string ts=s;
    for(auto a:ma){
        char max_char=a.first;
        ans=0;
        while(1){
            bool ok=1;
            for(int i=0;i<s.length()-1;i++){
                if(s[i]!=s[i+1]){
                    ok=0;
                }
            }
            if(ok){
                break;
            }
            for(int i=0;i<s.length()-1;i++){
                if(s[i+1]==max_char){
                    s[i]=max_char;
                }
            }
            s.pop_back();
            ans++;
       //     cout<<s<<endl;
        }
        real=min(real,ans);
        s=ts;
       // cout<<endl<<endl;
    }
    cout<<real<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main(){
	priority_queue <float> pq;
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		float x;
		scanf("%f",&x);
		pq.push(-x);
	}
	while(pq.size()>1){
		float a,b;
		a=pq.top();pq.pop();
		b=pq.top();pq.pop();
		pq.push((a+b)/2);
	}
	printf("%f",-pq.top());
	return 0;
}

Measured memory_bytes: 256