akhauriyash/Code-Regression huggingface dataset:
from collections import deque
S = deque(input())
Q = int(input())
 
p = 0
 
for i in range(Q):
    query = input().split()
    if query[0]=='1':
        p ^= 1
    else:
        f = int(query[1])-1
        c = query[2]
        if p:
            f ^= 1
        if f:
            S.append(c)
        else:
            S.appendleft(c)
 
if p:
    print(*reversed(S), sep='')
else:
    print(*S, sep='')

Measured memory_bytes: 81584
n = int(input())
mod = 10**9+7

"""約数の個数"""
#参考：青チャp280
#注意：1も約数としてカウントされる
def factrize(n):
    b = 2
    fct = []
    for i in range(n+1):
        while b*b <= i:
            while i % b == 0:
                i //= b
                fct.append(b)
            b = b+1
        if i > 1:
            fct.append(i)
        b = 2
    
    divisor = dict()
    for i in fct:
        if not i in divisor:
            divisor[i] = 1
        else:
            divisor[i] += 1
    ans = 1
    for i in divisor.values():
        ans *= (i+1)
    return ans

print(factrize(n)%mod)

Measured memory_bytes: 39920
#include <iostream>

const long long MOD = 1000000007;

int main()
{
	int n, k;
	using std::cin;
	cin.sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> k;
	long long ans = 0LL;
	long long presum = (long long)k * (k - 1) / 2, 
		postsum = (2 * n - k + 1) * (long long)k / 2;
	for (int i = k; i <= n + 1; i++) //length
	{
		ans += postsum - presum + 1;
		ans %= MOD;
		presum += i;
		postsum += n - i;
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 3600
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func main() {
	A := float64(nextInt())
	B := nextInt()
	T := float64(nextInt())
	fmt.Println(int((T+0.5)/A) * B)
}

// Input. ----------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}

	return i
}

func nextFloat() float64 {
	sc.Scan()
	f64, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}

	return f64
}

func nextString() string {
	sc.Scan()
	if err := sc.Err(); err != nil {
		panic(err)
	}

	return sc.Text()
}

// ---------- Input.

// Util. ----------

func abs(x int) int {
	return int(math.Abs(float64(x)))
}

func min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

// ---------- Util.


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
// using Graph = vector<vector<int>>;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ll LINF = 1LL << 60;

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 main() {
  int n, w;
  cin >> n >> w;
  ll a[2][n];
  rep(i, n) cin >> a[0][i] >> a[1][i];
  ll dp[n + 1][w + 1];
  rep(i, n + 1) rep(j, w + 1) dp[i][j] = 0;
  repi(i, 1, n + 1) rep(j, w + 1) {
    if (j - a[0][i - 1] < 0)
      dp[i][j] = dp[i - 1][j];
    else
      dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[0][i - 1]] + a[1][i - 1]);
  }
  cout << dp[n][w] << endl;
  return 0;
}


Measured memory_bytes: 79104
# include "bits/stdc++.h"
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const double PI = acos(-1);
template<class T>constexpr T INF() { return ::std::numeric_limits<T>::max(); }
template<class T>constexpr T HINF() { return INF<T>() / 2; }
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
const char dir[4] = { 'u','l','d','r' };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
int d_sum(LL n) { int ret = 0; while (n > 0) { ret += n % 10; n /= 10; }return ret; }
int d_cnt(LL n) { int ret = 0; while (n > 0) { ret++; n /= 10; }return ret; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define UNIQUE(wpwpw)        (wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)
# pragma warning(disable:4996)

int n, k;

int main() {
	cin >> n >> k;
	cout << (n%k == 0 ? 0 : 1) << endl;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
   ll a,b;cin >>a>>b;
   if((a*b)%2==1)puts("Yes");
   else puts("No");
   return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<string>
#include<sstream>
#include<cmath>
#include<climits>
#include<algorithm>
#include<bitset>
#include<set>
#include<stack>
#include<queue>
#include<iomanip>
#include<memory.h>
#include<complex>
#include<unordered_map>
using namespace std;  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tuple<int,int> tii;
#define rep(i,n) for(int i=0;i<(n);i++)  
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second  
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
const double PI = M_PI;  
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define SHOWARRAY(ar,i,j) REP(a,i)REP(b,j)cerr<<ar[a][b]<<((b==j-1)?((a==i-1)?("\n\n"):("\n")):(" "))
#define DIV int(1e9+7)
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}
/* Coding Space*/
ll memo[100];
ll L(int x){
  if(memo[x] != 0) return memo[x];
  ll ret = L(x-1)+L(x-2);
  memo[x] = ret;
  return ret;
}
int main(){
  int n; cin >> n;
  memo[0] = 2;
  memo[1] = 1;
  cout << L(n) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+5;

map<long long,int> mp;

int main()
{
    int n;
    scanf("%d",&n);
    mp[0]=1;
    long long sum=0;
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        sum+=a;
    //    printf("%lld\n",sum);
        ans+=mp[sum];
        mp[sum]++;
      //  printf("%lld\n",ans);
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 12800
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<string>
#include<cstring>
#include<time.h>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;

#define repi(i,a,b) for(ll i = (a); i < (b); i++)
#define rep(i, n) for(ll i = 0; i < (n); ++i)



int ctoi(char c) {
	switch (c)
	{
	case '0': return 0;
	case '1': return 1;
	case '2': return 2;
	case '3': return 3;
	case '4': return 4;
	case '5': return 5;
	case '6': return 6;
	case '7': return 7;
	case '8': return 8;
	case '9': return 9;
	default: return -1;
	}
}

int main() {
    int N;
    cin >> N;
    string s;
    cin >> s;
    unordered_set<int> koho;
	unordered_set<int> fketa;
	unordered_set<int> sketa[10];
	rep(i, s.size() - 2) {
		int k3 = ctoi(s[i]);
		if (fketa.count(k3) != 0) continue;
		fketa.insert(k3);
		repi(j, i + 1, s.size() - 1) {
			int k2 = ctoi(s[j]);
			if (sketa[k3].count(k2) != 0) continue;
			sketa[k3].insert(k2);
			int c = 0;
			repi(k, j + 1, s.size()) {
				int k1 = ctoi(s[k]);
				int v = (k3 * 100) + (k2 * 10) + k1;
				if (koho.count(v) == 0) {
					koho.insert(v);
					c++;
					if (c == 10) break;
				}
			}
			if (sketa[k3].size() == 10) break;
		}
		if (fketa.size() == 10) break;
	}
	cout << koho.size() << endl;
    return 0;
}



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

using namespace std;

int main(){
    int n, a[100];
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    string com = "APPROVED";
    for (int i = 0; i < n; i++){
        if (a[i] % 2 == 0){
            if (a[i] % 3 != 0 and a[i] % 5 != 0)
                com = "DENIED";
        }
    }
    cout << com;
    return 0;
}


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

ll maxdiv(ll n) {
  ll tmp = sqrt(n);
  while (n % tmp != 0) --tmp;
  return tmp;
}

int main() {
  ll n; cin >> n;
  ll m = maxdiv(n);
  cout << m + n / m - 2 << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

//#include <tuple>

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

int main() {
  int N;
  cin >> N;
  vector<int> x(N);
  rep(i, N){
    cin >> x[i];
  }
  sort(x.begin(), x.end());
  
  ll ans;
  ll tmp = 0;

  rep(i, N){
    tmp += pow(abs(x[i]-1), 2);
  }
  ans = tmp;
  // cout << ans << endl;

  for(int p = 2; p <= 100; p++){
    tmp = 0;
    rep(i, N){
      tmp += pow(abs(x[i]-p), 2);
    // cout << pow(x[i] - p, 2) << endl;
    }
    ans = min(ans, tmp);
  }
  
  cout << ans << endl;

}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
#define pb push_back
 const ll mod = 1000000007;

int main() {
	ll N, K;
	cin >> N >> K;

	ll maxK = (N - 1) * (N - 2) / 2;
	if (K > maxK) {
		cout << -1 << endl;
		return 0;
	}

	ll M = (N - 1) + (maxK - K);
	cout << M << endl;
	for (int i = 2; i <= N; i++) {
		cout << 1 << " " << i << endl;
	}
	ll m = N-1;
	for (int i = 2; i <= N-1; i++) {
		for (int j = i + 1; j <= N; j++) {
			if (m == M) {
				return 0;
			}
			cout << i << " " << j << endl;
			m++;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;

int main() {

	string S;
	cin >> S;

	if (S[1] == S[0]) {
		if (S[3] == S[2]) {
			if (S[1] == S[3]) {
				cout << "No" << endl;
			}
			else {
				cout << "Yes" << endl;
			}
		}
		else {
			cout << "No" << endl;
		}
	}
	else if (S[0] == S[2]) {
		if (S[1] == S[3]) {
			if (S[0] == S[1]) {
				cout << "No" << endl;
			}
			else {
				cout << "Yes" << endl;
			}
		}
		else {
			cout << "No" << endl;
		}
	}
	else if (S[0] == S[3]) {
		if (S[1] == S[2]) {
			if (S[0] == S[1]) {
				cout << "No" << endl;
			}
			else {
				cout << "Yes" << endl;
			}
		}
		else {
			cout << "No" << endl;
		}
	}
	else {
		cout << "No" << endl;
	}

	return 0;

}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;
using TextReader = System.IO.TextReader;
using System.Text;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            return consoleReader.String.Replace("2017","2018");
        }

        #region いつもの
#pragma warning disable
        private ConsoleReader consoleReader;
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program(new ConsoleReader(Console.In)).Calc()); static string AllLines<T>(IEnumerable<T> source) => string.Join("\n", source);
    }
    public class ConsoleReader
    {
        private string[] ReadLineSplit() => textReader.ReadLine().Split(Array.Empty<char>(), StringSplitOptions.RemoveEmptyEntries);
        private string[] line = Array.Empty<string>();
        private int linePosition;
        private TextReader textReader;
        public ConsoleReader(TextReader tr) { textReader = tr; }
        public int Int => int.Parse(String);
        public long Long => long.Parse(String);
        public double Double => double.Parse(String);
        public string String
        {
            get
            {
                if (linePosition >= line.Length)
                {
                    linePosition = 0;
                    line = ReadLineSplit();
                }
                return line[linePosition++];
            }
        }
        public class SplitLine
        {
            private string[] splited;
            public SplitLine(ConsoleReader cr) { splited = cr.ReadLineSplit(); cr.line = Array.Empty<string>(); }
            public int[] Int => String.Select(x => int.Parse(x)).ToArray();
            public int[] Int0 => String.Select(x => int.Parse(x) - 1).ToArray();
            public long[] Long => String.Select(x => long.Parse(x)).ToArray();
            public double[] Double => String.Select(x => double.Parse(x)).ToArray();
            public string[] String => splited;
        }
        public SplitLine Split => new SplitLine(this);
        public class RepeatReader : IEnumerable<ConsoleReader>
        {
            ConsoleReader cr; int count;
            public RepeatReader(ConsoleReader cr, int count) { this.cr = cr; this.count = count; }
            public IEnumerator<ConsoleReader> GetEnumerator() => Enumerable.Repeat(cr, count).GetEnumerator();
            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();

            public IEnumerable<string> String => this.Select(cr => cr.String);
            public IEnumerable<int> Int => this.Select(cr => cr.Int);
            public IEnumerable<int> Int0 => this.Select(cr => cr.Int - 1);
            public IEnumerable<long> Long => this.Select(cr => cr.Long);
            public IEnumerable<double> Double => this.Select(cr => cr.Double);
        }
        public RepeatReader Repeat(int count) => new RepeatReader(this, count);
    }
    #endregion
}

Measured memory_bytes: 13140
S = input()
S1 = S[0::2]
S2 = S[1::2]

S_count = S1.count('R') + S1.count('U') + S1.count('D')+ S2.count('L') + S2.count('U') + S2.count('D')

if len(S) == S_count:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 2940
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
int mx2[] = {1,0};
int my2[] = {0,1};

class BLucasNumber {
public:
	void solve(istream& in, ostream& out) {
        vector<ll> l(100);
        l[0] = 2;
        l[1] = 1;
        for(int i=2;i<87;i++){
            l[i] = l[i-1] + l[i-2];
        }
        int n;
        in >> n;
        out << l[n] << endl;
	}
};

int main() {
	BLucasNumber solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Measured memory_bytes: 256
import Foundation

func main() {
    let input1 = readLine()!.split(separator: " ")
    let n = Int(input1[0])!
    let d = Double(input1[1])!
    
    var count = 0
    for _ in 1...n {
        let input = readLine()!.split(separator: " ")
        let x = Double(input[0])!
        let y = Double(input[1])!
        let distance = sqrt(pow(x, 2) + pow(y, 2))
        if distance <= d {
            count += 1
        }
    }
    print(count)
}
 
main()

Measured memory_bytes: 13784
function main(input) {
    let [X, Y] = input.trim().split(/[\s\n]/).map(Number)
    const result = 0

    for(let i = 0; i <= X; i++) {
        const j = X - i
        const legs = i * 2 + j * 4
        if(legs === Y) {
            console.log('Yes')
            return
        }
    }

    console.log('No')
}

main(require("fs").readFileSync("/dev/stdin", "utf8"))


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

int main() {
	string s;
	cin >> s;
	
	int sN = 0;
	int tN = 0;
	
	for(int i = s.length() - 1; i >= 0; i--){
		if(s[i] == 'S'){
			if(tN > 0){
				tN--;
			}else{
				sN++;
			}
		}else{
			tN++;
		}
	}
	
	cout << sN * 2 << endl;
	
	return 0;
}

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

struct UnionFind {
    vector<int> par;

    UnionFind(int N) : par(N) {
        for (int i = 0; i < N; i++) {
            par[i] = i;
        }
    }

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

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

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

int main()
{
    int N, M;
    cin >> N >> M;
    int p[N];
    rep(i, N) cin >> p[i];

    UnionFind tree(N);

    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        tree.unite(x-1, y-1);
    }

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (tree.same(i, p[i] - 1)) {
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define MOD1 1000000007
#define MOD2 1000000009
#define ll long long int
#define li long int
#define fi first
#define se second
#define ffl fflush(stdout);
#define whT int t; cin>>t; while(t--)
int main() 
{
	int x,y;
	cin>>x>>y;
	if(y%2!=0) {
		cout<<"No";
	} else if(x*4==y||x*2==y) {
		cout<<"Yes";
	} else {
		int b=((y-(2*x))/2);
		if(b>=0 && b<=x) cout<<"Yes";
		else cout<<"No";
	}
	return 0;
}


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

int main() {
  int d;
  cin >>d;
 if (d==25) cout << "Christmas" << endl;
  else if(d == 24) cout << "Christmas Eve" << endl;
  else if(d == 23) cout << "Christmas Eve Eve" << endl;
  else cout << "Christmas Eve Eve Eve" << endl;
   
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
str s;
int y,m,d;
int main(){
    cin>>s;
    y = int(s[0]-48)*1000+int(s[1]-48)*100+int(s[2]-48)*10+int(s[3]-48);
    m = int(s[5]-48)*10+int(s[6]-48);
    d = int(s[8]-48)*10+int(s[9]-48);
    if(y>2019){cout<<"TBD\n";}
    if(y==2019 && m > 4){cout<<"TBD\n";}
    else cout<<"Heisei\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <random>
#include <cstdint>
#include <bitset>
#include <iomanip>
#include <utility>
#include<map>
#include<functional>
#include<climits>
using namespace std;
typedef long long ll;
const int mod = 1000000007;

int main() {
	ll n, m,ans=0;
	vector<pair<ll, ll>> ab;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		ll a, b;
		cin >> a >> b;
		ab.push_back(make_pair(a, b));
	}
	sort(ab.begin(), ab.end());
	for (int i = 0; i < ab.size(); i++) {
		if (m <= ab[i].second) {
			ans += m * ab[i].first;
			break;
		}
		ans += ab[i].first*ab[i].second;
		m -= ab[i].second;
	}
	cout << ans << endl;
}



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

int main(){
   int N;
   std::cin >> N;
   std::vector<int> a(N);
   for(int i=0; i<N; ++i)
      std::cin >> a[i];

   std::sort(a.begin(),a.end());

   int A = 0;
   int B = 0;
   for(int i=0; i<N; ++i){
      if(i%2==0) A += a[N-i-1];
      else B += a[N-i-1];
   }
   std::cout << A - B << std::endl;

   return 0;

}


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

typedef long long ll;
typedef int64_t i6;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define Sort(x) sort(x.begin(), x.end())
#define Sort_rev(x) sort(x.begin(), x.end(), greater<int>())
#define ALL(v) (v).begin(), (v).end()

//π M_PI
//deg = rad*180/M_PI

int main() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = 0;
    rep(i, n) {
        if ( s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C' ) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

//#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) rep(i,(n)+1)
#define repst(i,s,n) reps(i,s,(n)+1)
#define reprt(i,n,t) for(int (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(itr,v) for(auto &(itr):(v))
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define bln(i,n) (((i)==(n)-1)?'\n':' ')
#define dbg(x) cout<<#x" = "<<(x)<<ln<<flush
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ')<<flush;}}
#define zero(a) memset(a,0,sizeof(a))
#define unq(a) sort(all(a)),a.erase(unique(all(a)),a.end())

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vst;
typedef vector<bool> vb;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

ll mop(ll a,ll b,ll m=mod) {ll r=1;a%=m; assert(b>=0); for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a*b/gcd(a,b);}

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

int h, w, a[10][10];

signed main() {
	while (1) {
		cin >> h >> w;
		if (h==0) break;
		rep(i,h) rep(j,w) cin >> a[i][j];
		int res = 0;
		rep(li,h) rep(lj,w) reps(ri,li+2,h) reps(rj,lj+2,w) {
			int mn = inf, mx = 0, m = 0, s = 0;
			repst(i,li,ri) repst(j,lj,rj) {
				if (i==li || i==ri || j==lj || j==rj) chmin(mn, a[i][j]);
				else chmax(mx, a[i][j]), m++, s += a[i][j];
			}
			if (mx<mn) chmax(res, mn*m - s);
		}
		cout << res << ln;
	}
}


Measured memory_bytes: 3140
//****************************//
/**********  main *************/
//****************************//
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define REP(i, n) for(i = 0; i < n; i++)
#define FOR(i, a, b) for(i = a; i < b; i++)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())

double pi = 3.141592653589793;

int gcd(int a, int b) {
    if(a % b == 0) {
        return (b);
    } else {
        return (gcd(b, a % b));
    }
}

int main() {

    std::cin.tie(0);

    int i, j, k; // preset
    int res;
    int count = 0;
    int a;

    int n;
    cin >> n;

    for(i = 0; i < n; i++) {
        cin >> a;
        if(i%2==0 && a%2==1){
            count++;
        }
    }

    cout << count << endl;

    return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<string>
#include<cmath>

using namespace std;

int main(void){
	int N,D;
	long ans;
	cin >> D >> N;
	long tmp = pow(100,D);
	ans = tmp * N;
	if(N == 100){
		ans += tmp;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
a0,a1,a2=map(int,input().split())
a3,a4,a5=map(int,input().split())
a6,a7,a8=map(int,input().split())
N=int(input())
b=[int(input()) for _ in range(N)]
A=[a0,a1,a2,a3,a4,a5,a6,a7,a8]

for i in range(N):
  for p in range(9):
    if b[i]==A[p]:
      A[p]=0
  
if A[0]==A[1]==A[2]==0 or A[3]==A[4]==A[5]==0 or A[6]==A[7]==A[8]==0 or A[0]==A[3]==A[6]==0 or A[1]==A[4]==A[7]==0 or A[2]==A[5]==A[8]==0 or A[0]==A[4]==A[8]==0 or A[2]==A[4]==A[6]==0:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 3192
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cmath>
#include <time.h>
#include <tuple>
#define all(c) ((c).begin(),(c).end())
#define rall(c) ((c).rbegin(),(c).rend())
//#define sort(v,n) sort(v,v+n)
#define ll long long
#define fi first
#define se second
#define inf 999999999
using namespace std;
const ll MOD = 1e9 + 7;
const double PI = acos(-1.0);
//---------------------------------------------------------------------------------------------//
ll n,a,b;
ll c[100001];
bool taosu(ll t) {
	ll cont = 0;
	ll d = a - b;
	for (int i = 0; i < n; i++) {
		ll h = c[i] - t*b;
		if (h > 0) {
			cont += (h + d - 1) /d;
		}
	}
	return cont <= t;
}

int main() {
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
	ll l = 0, r = 1000000000;
	while (l+1 < r) {
		ll mid = (r + l)/2;
		if (taosu(mid)) {
			r = mid;
		}
		else {
			l = mid;
		}
	}
	cout << r << endl;
	return 0;
}

Measured memory_bytes: 1024
k = int(input())

a = [str(i) for i in range(1,10)]

for i in range(40000):
    if a[i][-1] == '0':
        a.append(str(a[i])+'0')
        a.append(str(a[i])+'1')
    elif a[i][-1] == '9':
        a.append(str(a[i])+'8')
        a.append(str(a[i])+'9')
    elif a[i][-1] != '0' and a[i][-1] != '9':
        a.append(str(a[i]) + str(int(a[i][-1])-1))
        a.append(str(a[i]) + str(int(a[i][-1])))
        a.append(str(a[i]) + str(int(a[i][-1])+1))

print(a[k-1])

Measured memory_bytes: 51160
#include<iostream>
using namespace std;
int H[1000000], W[1000000];
int main(){

	for (int a = 0; a < 1000000; a++){

		cin >> H[a] >> W[a];
		
		if (H[a] == 0 && W[a] == 0)break;

		for (int b = 0; b < W[a]; b++){

			cout << "#";
		}
		cout << endl;


		for (int c = 2; c < H[a]; c++){

			cout << "#";

			for (int d = 0; d < W[a] - 2; d++){

				cout << ".";

			}
			cout << "#" << endl;
		}
		for (int b = 0; b < W[a]&&1<H[a]; b++){
			
			cout << "#";
		}
		
		cout << endl<<endl;
		
	}
	return 0;
}



Measured memory_bytes: 3072
//A,Elebereth Gilthoniel mantae!
//For Temeria!
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<cstdio>
#include<map>
#include<stack>
#include<queue>
#include<cstring> 
using namespace std;
int h,w,n,a[10008];int d[105][105];
int main()
{
 	//freopen("","r",stdin);
	//freopen("","w",stdout);
	cin>>h>>w>>n;for(int i=0;i<n;i++) cin>>a[i];
	bool flag=0;int id=0;
	for(int i=0;i<h;i++)
	{flag=!flag;
		for(int j=0;j<w;j++)
		{
			int k=0;
			if(flag) k=j;else k=w-j-1;
			while(a[id]==0) id++;
			if(a[id]>0)
			{
				a[id]--;
			}
			d[i][k]=id+1;
		}
	}
	for(int i=0;i<h;i++) 
	{
		for(int j=0;j<w;j++) cout<<d[i][j]<<" ";cout<<"\n";
	}
	return 0;
}

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

#define ll long long

#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (ll i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (ll i = n - 1; i >= 0; i--)
#define fill(ar,val) memset(ar, val, sizeof(ar))
#define fill0(ar) fill((ar), 0)
#define debug(x) cout<<#x<<": "<<x<<endl

#define ld double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define INF 1000000000000000000
ll dp[100007];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long double pi= 3.14159265358979323846;
    ll n,w;
    cin>>n>>w;
    ll ma=0;
    rep(j,n)
    {
        // debug(j);
        ll x,y;
        cin>>x>>y;

        for(ll i=w-x;i>=0;i--)
        {
            

            if(dp[i])
            { 
                dp[i+x]=max(y+dp[i],dp[i+x]);
                // debug(i+x);
                ma=max(dp[i+x],ma);
                // debug(ma);
            }
        }dp[x]=max(y,dp[x]);
        ma=max(dp[x],ma);
    }
    cout<<ma<<endl;
}

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

int main() {
    int n;
    string s;
    cin >> n >> s;
    long long ret = 0;
    int nr = 0, ng = 0, nb = 0;
    for (auto c : s) {
        if (c == 'R') nr++;
        if (c == 'G') ng++;
        if (c == 'B') nb++;
    }
    ret = 1LL * nr * ng * nb;

    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            int k = i * 2 - j;
            if (j < k && k < n) {
                if (s[i] != s[j] and s[j] != s[k] and s[i] != s[k]) {
                    ret--;
                }
            }
        }
    }
    cout << ret << "\n";
}

Measured memory_bytes: 3632
d={}
for i in range(int(input())):
    d[i]={}
    a,b,c=map(int,input().split())
    if i==0:
        d[i][0]=a
        d[i][1]=b
        d[i][2]=c
    else:
        d[i][0]=max(d[i-1][1],d[i-1][2])+a
        d[i][1]=max(d[i-1][0],d[i-1][2])+b
        d[i][2]=max(d[i-1][1],d[i-1][0])+c
print(max(d[i][0],d[i][1],d[i][2]))

Measured memory_bytes: 117504
/*

    author : s@if

*/

#include<bits/stdc++.h>
using namespace std;

#define 		NIL 			-1
#define		 	fi	 		    first
#define 		sec 			second
#define 		MAX 			INT_MAX
#define			INF 			99999999
#define 		ll 			    long long
#define 		PI 			    acos(-1.0)
#define			MOD 			1000000007
#define 		PLL 			pair<ll,ll>
#define 		PII			    pair<int,int>
#define 		ull 			unsigned long long
#define 		For(i,a,b) 		for(int i=a;i<=(int)b;i++)


bool Check(int N , int pos)	{	return (bool) (N & (1<<pos));}
int Set(int N, int pos) {	return N = N | (1<<pos);}

int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};
int hr[]={-2,-2,-1,+1,+2,+2,-1,+1};
int hc[]={+1,-1,+2,+2,-1,+1,-2,-2};
int dx[]={+1,-1,+0,+0};
int dy[]={+0,+0,+1,-1};

const int MAXN = (int)1e5+9;

ll ara[MAXN] ;
bool mark[MAXN];

int main()
{
/*	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);  */

    ll i,j,k,l,m,n,p,q,x,y,u,v,r,tc,t;

    cin>>n>>m;
    memset(ara,0,sizeof(ara));
    memset(mark,true,sizeof(mark));

    For(i,1,m)
    {
        cin>>p;

        mark[p] = false;
    }

    ara[0] = 1;

    for(i=0; i<=n; i++)
    {
        if(mark[i+1]==true){
            ara[i+1]+=ara[i];
            ara[i+1]%=MOD;
        }
        if(mark[i+2]==true){
            ara[i+2]+=ara[i];
            ara[i+2]%=MOD;
        }
    }

   // for(i=0; i<=n; i++)
     //   cout<<ara[i]<<" ";

    cout<<(ara[n-1]+ara[n-2])%MOD<<endl;

   // main();

    return 0;
}


Measured memory_bytes: 1152
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

use std::collections::VecDeque;

fn main() {
    input! {
        n: usize,
        a: [u64;n],
    }
    let mut q: VecDeque<u64> = VecDeque::with_capacity(n);
    let mut front = if n % 2 == 0 {false} else {true};
    for i in 0..n {
        if front {
            q.push_front(a[i]);
        } else {
            q.push_back(a[i]);
        }
        front = !front;
    }
    for v in q {
        print!("{} ", v);
    }
}


Measured memory_bytes: 12412
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ll a, b, k;
  cin >> a >> b >> k;
  if (a >= k) {
    cout << a-k << ' ' << b << endl;
  }
  else {
    cout << 0 << ' ' << max((ll)0, b-k+a) << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int k,l,m;
  scanf("%d%d%d",&k,&l,&m);
  int min = k + l;
  if(min > (l + m)){
    min = l + m;
  }
  if(min > k + m){
    min = k + m;
  }
  printf("%d",min);
  return 0;
}

Measured memory_bytes: 128
K = int(input())
count = 0
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b
for i in range(1, K+1):
    for j in range(1, K+1):
        ijgcd = gcd(i, j)
        for k in range(1, K+1):
            count += gcd(ijgcd,k)
print(count)

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

#include <boost/algorithm/string/classification.hpp>  // is_any_of
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/math/tools/minima.hpp>
#include <boost/multi_array.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/optional.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/irange.hpp>

const int MOD = 1e9 + 7;
#define rep(i, n) for (int i = 0; i < (n); ++i)

namespace adaptor = boost::adaptors;
using namespace std;
using boost::irange;
using boost::algorithm::join;
using boost::algorithm::replace_all;
using boost::algorithm::split;
using boost::math::tools::brent_find_minima;
using boost::multiprecision::cpp_int;
using ll = long long;
using P = pair<int, int>;

// TOP
void Main()
{
	ll n, k;
	cin >> n >> k;
	cout << (ll)(k * pow(k - 1, n - 1)) << endl;
}
// END

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 384
//2:21 start

#include<stdio.h>

int main(){
  int a,b;
  scanf("%d", &a);
  scanf("%d", &b);

  int A[3];
  A[0] = a+b;
  A[1] = a-b;
  A[2] = a*b;
  
  int max = A[0];
  for(int i=0; i<3; i++){
    if(max<A[i])max = A[i];
  }

  printf("%d\n", max);

  return 0;
}


Measured memory_bytes: 128
#include <iostream>

using namespace std;

int N;
long long int T, t[200006];

int main(void) {

	cin >> N >> T;

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

	long long int init = t[1];
	long long int fin = t[1] + T;
	long long int X = 0;

	for (int i = 2; i <= N; i++) {
		if (t[i] <= fin) { fin = t[i] + T; }
		else { X += fin - init; init = t[i]; fin = init + T; }
	}

	X += fin - init;

	cout << X << endl;


	//system("pause");
	return 0;
}

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

int A[100002], B[100001];

int main(void) {
	int N;
	cin >> N;
	for (int i = 0; i <= N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];

	long long ans = 0;
	for (int i = N; i >= 0; i--) {
		int kill = min(A[i+1], B[i]);
		ans += kill;
		B[i] -= kill;
		kill = min(A[i], B[i]);
		ans += kill;
		A[i] -= kill;
	}
	cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
// A - Darker and Darker

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;


char field[1000][1000];
bool visited[1000][1000];

struct Loc {
	int r;
	int c;
	int step;
};

// 四方向への移動ベクトル
const int dr[4] = {1, 0, -1, 0};
const int dc[4] = {0, 1, 0, -1};

int bfs(int H, int W) {

	queue<Loc> search_queue;

	for (int r=0; r<H; r++) {
		for (int c=0; c<W; c++) {
			if (field[r][c] == '#') {
				search_queue.push(Loc{r, c, 0});
				visited[r][c] = true;
			}
		}
	}

	int max_step = 0;

	while(!search_queue.empty()) {
		// キューから探索対象の位置情報を取り出す
		Loc loc = search_queue.front();
		search_queue.pop();

		int r = loc.r;
		int c = loc.c;
		int step = loc.step;
		max_step = max(max_step, step);
		//cout << r << ' ' << c << " (" << s << ")" << endl; // **** debug ****

		// 四方向の探索を予約
		for (int dir = 0; dir < 4; dir++) {
			int next_r = r + dr[dir];
			int next_c = c + dc[dir];

			if (next_r < 0 || next_r >= H || next_c < 0 || next_c >= W) continue;
			if (visited[next_r][next_c]) continue;
			search_queue.push(Loc{next_r, next_c, step + 1});
			visited[next_r][next_c] = true;
		}
	}

	return max_step;
}

int main(){
	int H, W;
	cin >> H >> W;

	for (int r=0; r<H; r++) {
		for (int c=0; c<W; c++) {
			cin >> field[r][c];
		}
	}

	int ans = bfs(H, W);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 17236
#include <iostream>

int main(void) {
    int A, B;
    std::string s;
    std::cin >> A >> B;
    std::cin >> s;

    bool post_number = true;
    for (int i=0;i<A;i++) {
        if (s[i] == '-') post_number = false;
    }
    if (s[A] != '-') post_number = false;
    for (int i=A+1; i<=B+A;i++) {
        if (s[i] == '-') post_number = false;
    }

    if (post_number) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string s, t;
int dp[3030][3030];

int main() {
    cin >> s >> t;
    int slen = s.length();
    int tlen = t.length();
    for(int i = 0; i < 3030; ++i) {
        for(int j = 0; j < 3030; ++j) {
            dp[i][j] = 0;
        }
    }

    for(int i = 0; i < slen; ++i) {
        for(int j = 0; j < tlen; ++j) {
            if(s.at(i) == t.at(j)) {
                dp[i+1][j+1] = dp[i][j] + 1;
            }else {
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
        }
    }

    int len = dp[slen][tlen];
    string ans;
    int si = slen;
    int tj = tlen;

    while(len > 0) {
        if(s.at(si-1) == t.at(tj-1)) {
            ans.push_back(s.at(si-1));
            si--;
            tj--;
            len--;
        }else if(dp[si][tj] == dp[si-1][tj]){
            si--;
        }else {
            tj--;
        }
    }

    reverse(ans.begin(), ans.end());

    cout << ans << endl;

}

Measured memory_bytes: 36096
#include<bits/stdc++.h> 
using namespace std;
#define ll long long 
#define pb push_back 

ll po(ll a,ll b) 
{ 
  ll res=1; 
  while(b--) 
  { 
    res=(res*a)%1000000007;
  } 
    return res;
 } 
int main()
{ 
   ios_base::sync_with_stdio(false);
   cin.tie(NULL); 
   ll i,n,t,ans; 
    
   cin>>n; 
   ans=po(10,n)-2*po(9,n)+po(8,n);
   while(ans<0) ans+=1000000007;
    
   cout<<ans<<endl;
}


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

template <typename T>
class BinaryIndexedTree
{
    std::vector<T> arr;
    const size_t size;
    const std::function<T(const T, const T)> operation;
    const T initial_value;

    void initialize_array()
    {
        this->arr = vector<T>(this->size, this->initial_value);
    }

public:
    BinaryIndexedTree(const size_t N, function<T(const T, const T)> func, T init) : size(N + 1), operation(func), initial_value(init)
    {
        initialize_array();
    }

    void update(const size_t idx, const T value)
    {
        long long idxll = (long long)idx;
        while (idxll <= (long long)this->size)
        {
            this->arr[idxll] = this->operation(this->arr[idxll], value);
            idxll += (idxll & -idxll);
        }
    }

    T query(const size_t idx)
    {
        T ret = this->initial_value;
        long long idxll = (long long)idx;
        while (idxll > 0)
        {
            ret = this->operation(ret, this->arr[idxll]);
            idxll -= (idxll & -idxll);
        }
        return ret;
    }
};

int main()
{
    size_t N, Q;
    cin >> N >> Q;

    vector<size_t> prev(N + 1, 0);
    vector<vector<size_t>> point(N + 1);
    size_t c;
    for (size_t i = 1; i <= N; i++)
    {
        cin >> c;
        point[prev[c]].push_back(i);
        prev[c] = i;
    }

    vector<vector<pair<size_t, size_t>>> query(N + 1);
    size_t l, r;
    for (size_t i = 0; i < Q; i++)
    {
        cin >> l >> r;
        query[l].push_back(make_pair(r, i));
    }

    BinaryIndexedTree<size_t> bit(
        5e5 + 5, [](size_t a, size_t b) { return a + b; }, 0);

    vector<size_t> ans(Q);

    for (size_t l = N; l <= N; l--)
    {
        for (size_t r : point[l])
        {
            bit.update(r, 1);
        }
        for (pair<size_t, size_t> q : query[l])
        {
            size_t r = q.first;
            size_t i = q.second;
            ans[i] = r - l + 1 - bit.query(r);
        }
    }
    for (size_t a : ans)
    {
        cout << a << endl;
    }
}


Measured memory_bytes: 66900
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <ctime>
#include <cstdlib>
using namespace std;

typedef long long LL;
const int MAX_N = 2e5 + 6;

LL a[MAX_N];

struct Treap {
    Treap *lc,*rc;
    LL key,pri;
    int sz;
    Treap(LL _key) {
        lc=rc=NULL;
        sz=1;
        pri=rand();
        key = _key;
    }
};

int Sz(Treap* t) {
    return t?t->sz:0;
}

void pull(Treap* t) {
    if (!t) return;
    t->sz = Sz(t->lc) + Sz(t->rc) + 1;
}

Treap* merge(Treap* a,Treap* b) {
    if (!a || !b) return a?a:b;
    else if (a->pri > b->pri) {
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else {
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,LL k,Treap* &a,Treap* &b) {
    if (!t) a = b = NULL;
    else if (t->key <= k) {
        a=t;
        split(t->rc,k,a->rc,b);
        pull(a);
    }
    else {
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

Treap* root;

void add(LL val) {
    Treap* tl;
    split(root,val,tl,root);
    root = merge(merge(tl,new Treap(val)),root);
}

void deleted(LL val) {
    Treap *tl,*tr;
    split(root,val-1,tl,root);
    split(root,val,root,tr);
    root=merge(merge(tl,root->lc),merge(root->rc,tr));
}

LL query(LL val) {
    Treap *tl;
    split(root,val-1,tl,root);
    LL ret=Sz(root);
    root=merge(tl,root);
    return ret;
}

LL pre[MAX_N];

int main () {
    root=NULL;
    LL n,k;
    cin >> n >> k;
    for (int i=1;n>=i;i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
        add(pre[i] - i*k);
    }
    LL ans=0;
    LL delta=0;
    for (int i=1;n>=i;i++) {
        ans += query(delta);
        delta -= (k-a[i]);
        deleted(pre[i] - i*k);
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 12800
N = int(input())
S = str(input())
ans = 0
for i in range(0, 1000):
    x = str(i).zfill(3)
    try:
        idx1 = S.index(x[0])
        idx2 = S.index(x[1], idx1+1)
        idx3 = S.index(x[2], idx2+1)
        ans += 1
    except ValueError:
        continue
print(ans)


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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			String input1 = br.readLine();

			if(input1.equals(".")){
				break;
			}

			String input2 = br.readLine();

			if(input1.equals(input2)){
				System.out.println("IDENTICAL");
			}
			//全く同じか少し違う
			else {
				String[] strArray1 = input1.split("\"", -1);
				String[] strArray2 = input2.split("\"", -1);

				if(strArray1.length != strArray2.length){
					System.out.println("DIFFERENT");
					continue;
				}
				int diffStr = 0;
				int diffSentence = 0;

				for(int i = 0; i < strArray1.length; i++){
					if(!strArray1[i].equals(strArray2[i])){
						if(i%2 == 0){
							diffSentence++;
							break;
						}
						else {
							diffStr++;
						}
					}
				}

				if(diffSentence == 0 && diffStr == 1){
					System.out.println("CLOSE");
				}
				else {
					System.out.println("DIFFERENT");
				}
			}

		}
	}

}



Measured memory_bytes: 25164
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll,ll> P;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF=99999999999999;
const ll MOD=1000000007;
ll c,d,e,f,p,t,ans=0;
 
 
ll n,m,r;
vector<P> gragh[3000];
vl A,B,C;
vector<vl> cost(100,vl(100,INF));
 
void input(void){
    cin>>n>>m;
    rep(i,m){
        cin>>c>>d>>e;
        gragh[c].push_back(make_pair(d,e));
    }
}
 
ll solve(void){
    rep(r,n){
    cost[r][r]=0;
    vl renewed(3000,0);
    rep(k,n){
    rep(i,n){
        rep(j,gragh[i].size()){
            cost[r][gragh[i][j].first]=min(cost[r][i]+gragh[i][j].second,cost[r][gragh[i][j].first]);
        }
    }
    }
 
    rep(i,n){
        rep(j,gragh[i].size()){
            if(cost[r][i]+gragh[i][j].second<cost[r][gragh[i][j].first]&&cost[r][i]+gragh[i][j].second<INF/2){
                cout<<"NEGATIVE CYCLE"<<endl;
                return 0;
            }
        }
    }
    }
 
    rep(i,n){
        rep(j,n){
    	if(cost[i][j]>INF/2)cout<<"INF";
        else cout<<cost[i][j];
        if(j!=n-1)cout<<" ";
        else cout<<endl;
        }
    }
    return 0;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    solve();
}


Measured memory_bytes: 3452
//#include <fsociety>
#include <cmath>
#include <deque>
#include <algorithm>
#include <iterator>
#include <list>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <unordered_set>
#include <stack>
#include <string>
#include <vector>
#include <iostream>
//end of libraries ;
#define INF 9999999999
#define N 4000
#define F first
#define S second
#define pb push_back
#define ll long long
#define fcin ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
string s , bg , en;
int f , r;
char ch;
bool flag = 0;
int main(){
fcin;
	cin>>s;
	int q;
	cin>>q;
	while(q--){
		cin>>f;
		if(f==2){
			cin>>r>>ch;
			if(!flag){
				if(r==1) { bg = ch + bg;}
				else if(r==2) { en+=ch; }
			}
			else{
				if(r==1) { en+=ch;}
				else if(r==2) {bg = ch + bg; }
			}
		}
		else flag = !flag;
	}
	s = bg + s  + en;
	if(flag){
		reverse(s.begin(),s.end());
	}
	cout<<s<<endl;

}

Measured memory_bytes: 1316