akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define maxn 102
int a[maxn][maxn];
int f[maxn][maxn];
int n, m;
int main()
{
    cin >> n >> m;
    char c;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            scanf(" %c", &c);
            if (c == '#')
                a[i][j] = 1;
            else
                a[i][j] = 0;
        }
    memset(f, 0x3f, sizeof(f));
    f[1][1] = a[1][1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i + 1][j] = min(f[i + 1][j], f[i][j] + (a[i + 1][j] - a[i][j] == 1));
            f[i][j + 1] = min(f[i][j + 1], f[i][j] + (a[i][j + 1] - a[i][j] == 1));
        }
    cout << f[n][m] << endl;
    return 0;
}

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

int main(){
  int A,B,C,D,E,F;
  cin>>A >>B >>C >>D >>E >>F;
  set<int> G,H;
  for(int i=0;i<=F;i++){
    for(int j=0;j<=F;j++){
      int I = 100*A*i + 100*B*j;
      int J = C*i + D*j;
      if(I<=F)G.insert(I);
      if(J<=F)H.insert(J);
    }
  }
  
  int K=1,L=0;
  for(int g:G){
    for(int h:H){
      if(g+h>F||100*h>g*E)continue;
      if(L*g<=K*h){
        K=g;
        L=h;
      }
    }
  }
  cout<<K+L<<" "<<L<<endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

const int INF = 1000000000;

inline void update(int& x, int y){
    if(x > y) x = y;
}

int main(){
    int n, m, l, s, t;
    while(cin >> n >> m >> l >> s >> t && n > 0){
        s--;
        int dist[300][300];
        REP(i, n) REP(j, n) dist[i][j] = (i == j ? 0 : INF);

        REP(i, m) {
            int a, b, c;
            cin >> a >> b >> c;
            a--; b--;
            dist[a][b] = dist[b][a] = c;
        }

        REP(k, n) REP(i, n) REP(j, n) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

        vector<int> p(l);
        vector<int> c(l);
        REP(i, l) cin >> p[i] >> c[i];
        REP(i, l) p[i]--;

        int dp[1 << 16][16] = {};
        REP(S, 1 << l) REP(i, l) dp[S][i] = INF;
        REP(i, l) dp[1 << i][i] = c[i] + dist[s][p[i]];

        REP(S, 1 << l) REP(i, l) if(S >> i & 1) {
            REP(j, l) if(!(S >> j & 1)) {
                update(dp[S | (1 << j)][j], dp[S][i] + dist[p[i]][p[j]] + c[j]);
            }
        }

        int ans = 0;
        REP(S, 1 << l) REP(i, l) {
            if(dp[S][i] + dist[p[i]][s] <= t){
                ans = max(ans, __builtin_popcount(S));
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 5652
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>

using namespace std;

int main(void){
	
	int i, j, n, count = 0;
	bool arr[999999] = {false};

	while (cin >> n) {

		for (i = 2; i <= n; i++) {
			arr[i] = true;
		}

		for (i = 2; i <= sqrt(n); i++) {
			if(arr[i])
				for (j = 0; i*(j + 2) <= n; j++) {
					arr[i*(j + 2)] = false;
				}
		}

		for (i = 2; i <= n; i++) {
			if (arr[i] == true)
				count++;
		}

		cout << count << endl;
		count = 0;

	}

	return 0;
}

Measured memory_bytes: 4024
import math

a,b,k=map(int, input().split())

kr=math.radians(k)

c2=a**2+b**2-2*a*b*math.cos(kr)
c=c2**(1/2)

S=1/2*a*b*math.sin(kr)
L=a+b+c
h=b*math.sin(kr)

print(S)
print(L)
print(h)


Measured memory_bytes: 5716
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<complex>
#include<iomanip>

#define EPS (1e-10)
using namespace std;
#define PI (3.1415926535)

int main(){
	int m, n;
	double x = 0, y = 0;
	double rad = PI/2;
	char in[10];
	const char *delim = ",";

	while(cin >> in){
		m = atoi(strtok(in, delim));
		n = atoi(strtok(NULL, delim));
		if( m == 0 && n == 0){
			break;
		}
		x += m * cos(rad);
		y += m * sin(rad);
		rad -= PI/180 * n;
	}

	cout << (int)x << "\n" << (int)y << endl;

	return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
typedef long long int ll;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T>
bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false;}
template<typename T>
bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false;}
// clang-format on

#include <functional>
template<typename T>
class SegmentTreeAllOne {
    using Func = function<T(T, T)>;

public:
    vector<T> data;
    int n;
    T init;
    Func update_func;
    SegmentTreeAllOne(int _n, T _init, Func up) {
        init = _init;
        update_func = up;
        for (n = 1; n < _n; n *= 2)
            ;
        data.resize(2 * n - 1, init);
    }
    void update(int l, int r, T val) {
        for (l += n - 1, r += n - 1; l < r; l = l / 2, r = (r - 1) / 2) {
            if (!(l & 1)) {
                data[l] = update_func(data[l], val);
            }
            if (!(r & 1)) {
                data[r - 1] = update_func(data[r - 1], val);
            }
        }
    }
    T query(int pos) {
        pos += n - 1;
        T res = data[pos];
        while (pos > 0) {
            pos = (pos - 1) / 2;
            res = update_func(res, data[pos]);
        }
        return res;
    }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n, d, a;
    cin >> n >> d >> a;
    vector<ll> x(n), h(n);
    REP(i, 0, n) {
        cin >> x[i] >> h[i];
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int t, int s) {
        if (x[t] != x[s])
            return x[t] < x[s];
        else
            return h[t] < h[s];
    });
    auto sum = [](ll t, ll s) {
        return t + s;
    };
    SegmentTreeAllOne<ll> segtree(n, 0LL, sum);

    ll cnt = 0;
    int p = 0;
    REP(i, 0, n) {
        ll res = h[ord[i]] - segtree.query(i);
        if (res <= 0) continue;
        while (p < n && x[ord[p]] - 2 * d <= x[ord[i]]) {
            p++;
        }
        ll cn = (res + a - 1) / a;
        segtree.update(i, p, cn * a);
        cnt += cn;
    }

    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 8320
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define error(x) cerr << #x << " = " << x << endl
#define sz(x) (int)(x).size()
#define eb emplace_back
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

const int MOD = 1e9 + 7;

int N, A, B;
int main(void) {
    ll C[55][55] = {0};
    C[0][0] = 1;
    for (int i = 1; i <= 50; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }
    cin >> N >> A >> B;
    vector<ld> arr(N);
    for (int i = 0; i < N; ++i) cin >> arr[i];
    sort(arr.begin(), arr.end(), greater<ld>());
    ld mean = 0;
    for (int i = A; i <= B; ++i) {
        ld sum = 0;
        for (int j = 0; j < i; ++j) sum += arr[j];
        mean = max(mean, sum/i);
    }
    ll ways = 0;
    for (int i = A; i <= B; ++i) {
        ld sum = 0;
        for (int j = 0; j < i; ++j) sum += arr[j];
        if (sum != (ld)round(mean*i)) continue;

        ll last = arr[i-1];
        int more = 0, same = 0;
        for (int j = 0; j < N; ++j) {
            if (arr[j] == last) ++same;
            if (arr[j] > last) ++more;
        }
        int rest = i - more;
        ways += C[same][rest];
    }
    printf("%7Lf\n", mean);
    printf("%lld\n", ways);
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm> // sort
#include <map> // sort

#define REP(i, n) for (long long i = 0; i < (n); i++) 
typedef long long ll;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;

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

    string sei = "CF";
    string res;
    ll cnt = 0;
    REP(i,s.size())
    {
        if(cnt == 2)break;
        if(s[i] == sei[cnt])
        {
            ++cnt;
        }
    }
    if(cnt == 2)
    {
        res = "Yes";
    }
    else
    {
        res = "No";
    }
    

    cout << res << endl;
    return 0;    
}



Measured memory_bytes: 256
def examC():
    N = I()
    A = LI()
    multi2 = 0; multi4 = 0
    for i in A:
        if i%4==0:
            multi4 +=1
        elif i%2==0:
            multi2 +=1
    if multi4>=(N//2):
        ans = "Yes"
    elif (multi4*2 + multi2)>=N:
        ans = "Yes"
    else:
        ans = "No"
    print(ans)



import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()


Measured memory_bytes: 14556
N = int(input())

Ls = set()
for i in range(1, N + 1):
    for j in range(i + 1, N + 1):
        Ls.add((i, j))

K = N - (N % 2)
for i in range(1, K // 2 + 1):
    Ls.remove((i, K - i + 1))

print(len(Ls))
for l in Ls:
    print("%d %d" % l)

Measured memory_bytes: 41456
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }
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; }

#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

#define PB push_back
#define INF 1e9
#define MOD 1e9+7
#define EPS 1e-9

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

// 入力
int N;
long long h[100010];

// DP テーブル
long long dp[100010];

int main() {

    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> h[i];

    // 初期化 (最小化問題なので INF に初期化)
    for (int i = 0; i < 100010; ++i) dp[i] = (ll)INF;

    // 初期条件
    dp[0] = 0;

    // ループ
    for (int i = 1; i < N; ++i) {
        chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
        if (i > 1) chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
    }

    // 答え
    cout << dp[N - 1] << endl;
}

Measured memory_bytes: 1792
/*解説確認*/
#include <iostream>

using namespace std;

int main(void){
    int x=0;
    int y=0;
    int a[]={0,1,3,1,2,1,2,1,1,2,1,2,1};

    cin >> x >> y;

    cout << (a[x]==a[y]?"Yes":"No") << endl;
    
    return 0;
}

Measured memory_bytes: 256
import bisect
import sys
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
L = A[:]
R = A[:]
# print(len(A))
for i in range(N-1):
    # print(i)
    L[i+1] += L[i]
    R[-i-2] += R[-i-1]

def func(l,r):
    if r-l == 1:
        return l
    m = (l+r)//2
    count = 0
    for i in A:
        count += N-bisect.bisect_left(A,m-i)
    if count >= M:
        return func(m,r)
    return func(l,m)

f = func(0,10**6)
ans = 0
count = 0
for p in range(N):
    x = N-bisect.bisect_left(A,f-A[p])
    if x == 0:
        continue
    ans += A[p]*x + R[-x]
    count += x
ans -= (count-M)*f
print(ans)




Measured memory_bytes: 18484
#include<stdio.h>
 int main(){
   int n,i,s[1000];

   scanf("%d",&n);
   for(i=0;i<n;i++){
     scanf("%d",&s[i]);
   }

   for(i=n-1;i>0;i--){
     printf("%d ",s[i]);
   }
   printf("%d\n",s[0]);
   return 0;
 }



Measured memory_bytes: 2088
use proconio::input;

fn main() {
  input! {
    A: f64,
    B: f64,
    N: f64
  }

  if B - 1f64 < N {
    println!("{}", (A * (B - 1f64) / B).floor());
  } else {
    println!("{}", (A * N / B).floor());
  }
}


Measured memory_bytes: 2672
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for (int i = s; i < (int)(n); i++)
#define out(x) cout << x << endl
#define INF 1000000;
#include <map>
#include <math.h>
 
using ll = long long;
using namespace std;

ll n, k;
const ll mod = 1000000007;



int main(){
    int n, k;
    string s;

    cin >> n >> k >> s;
    s[k-1] = s[k-1] + ('a' - 'A');
    rep(i, n) cout << s[i];
    cout << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			var cin = new Scanner2();
			int n = cin.Int();
			int r = cin.Int();
			if (n >= 10) {
				Console.WriteLine(r);
			} else {
				int v = r + 100 * (10 - n);
				Console.WriteLine(v);
			}
		}
	}


	public class Scanner2
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private readonly string filePath_;
		private readonly Func<string> reader_;
		private string[] buf_;
		private int index_;

		public Scanner2(string file = "")
		{
			if (string.IsNullOrWhiteSpace(file)) {
				reader_ = Console.ReadLine;
			} else {
				filePath_ = file;
				var fs = new StreamReader(file);
				reader_ = fs.ReadLine;
			}
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = reader_();
			while (st == "") {
				st = reader_();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}

		public void Save(string text)
		{
			if (string.IsNullOrWhiteSpace(filePath_)) {
				return;
			}

			File.WriteAllText(filePath_ + "_output.txt", text);
		}
	}
}

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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    static void solve(InputReader in, PrintWriter out){
        int k = in.ni();
        int a = in.ni(), b = in.ni();
        out.println(((a-1)/k<b/k)?"OK":"NG");
    }

    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

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

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
typedef pair<int,int> P;

//-----------------------------------------------------------------------

int n,m;
double L[20],a[20],b[20];

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

    cin>>n>>m;
    REP(i,n) cin>>L[i]>>a[i]>>b[i];

    double ret=0;
    REP(bt,1<<n){
        if(__builtin_popcount(bt)!=m) continue;
        double sum=0;
        REP(i,n-1) for(int j=i+1;j<n;j++){
            if(bt>>i&1 && bt>>j&1){
                sum+=(L[i]-L[j])*(L[i]-L[j])+
                     (a[i]-a[j])*(a[i]-a[j])+
                     (b[i]-b[j])*(b[i]-b[j]);
            }
        }
        ret=max(ret,sum);
    }
    printf("%.20lf\n",ret);

}



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

int main() {
  string s;
  cin>>s;
  string t;
  cin >>t;
  
  bool alle_buchstaben_gleich = true;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] != t[i]) {
      alle_buchstaben_gleich = false;
    }
  }
  
  if(alle_buchstaben_gleich == true) {
    cout <<"Yes";
  } else {
    cout<<"No";
  }
	return 0;
}

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

int n,m,q,s0[2010][2010],s1[2010][2010],s2[2010][2010];

int main()
{
#ifdef h10
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
#endif
	int i,j,a,b,c,d;
	scanf("%d%d%d",&n,&m,&q);
	for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
	{
		char c=getchar();
		while (c!='0'&&c!='1') c=getchar();
		s0[i][j]=c=='1';
	}
	for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
	{
		s1[i][j]=s0[i][j]&&s0[i][j+1];
		s2[i][j]=s0[i][j]&&s0[i+1][j];
	}
	for (i=1;i<=n;i++)
	for (j=1;j<=m;j++)
	{
		s0[i][j]+=s0[i-1][j]+s0[i][j-1]-s0[i-1][j-1];
		s1[i][j]+=s1[i-1][j]+s1[i][j-1]-s1[i-1][j-1];
		s2[i][j]+=s2[i-1][j]+s2[i][j-1]-s2[i-1][j-1];
	}
	while (q--)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int A=s0[c][d]-s0[c][b-1]-s0[a-1][d]+s0[a-1][b-1];
		int B=s1[c][d-1]-s1[c][b-1]-s1[a-1][d-1]+s1[a-1][b-1];
		int C=s2[c-1][d]-s2[c-1][b-1]-s2[a-1][d]+s2[a-1][b-1];
		printf("%d\n",A-B-C);
	}
}


Measured memory_bytes: 49024
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(int)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll xs, ys, xt, yt;
	cin >> xs >> ys >> xt >> yt;
	int n;
	cin >> n;
	vector<pair<pll, ll>> b(n + 2);
	b[0] = {pll(xs, ys), 0};
	b[n + 1] = {pll(xt, yt), 0};
	REP(i, n) {
		ll x, y, r;
		cin >> x >> y >> r;
		b[i + 1] = {pll(x, y), r};
	}
	n += 2;
	vector<vector<ld>> g(n, vector<ld>(n, 0));
	REP(i, n) FOR(j, i + 1, n) {
		g[i][j] = g[j][i] = max((ld)0,
					  (ld)sqrt(pow((b[i].first.first - b[j].first.first), 2)
						  +pow((b[i].first.second - b[j].first.second), 2))
					  - b[i].second - b[j].second);
	}
	vector<ld> dir(n, INF * INF + 10);
	priority_queue<pair<int, ld>, vector<pair<int, ld>>, greater<pair<int, ld>>> Q;
	Q.push({0, 0});
	while(!Q.empty()) {
		int p = Q.top().first;
		ld d = Q.top().second;
		Q.pop();
		REP(i, n) {
			if(i == p) continue;
			if(dir[i] > d + g[p][i]) {
				dir[i] = d + g[p][i];
				Q.push({i, dir[i]});
			}
		}
	}
	cout << fixed << setprecision(39) << dir[n - 1] << endl;
	return 0;
}
/* --------------------------------------- */


Measured memory_bytes: 21488
S = input()

alphabet = set(chr(ord('a')+x) for x in range(26))

def F_short(S):
    se = alphabet -set(S)
    x = min(se)
    return S + x
    
def F_long(S):
    if S == ''.join(sorted(alphabet, reverse=True)):
        return '-1'
        
    cand = []
    S = list(S)
    while True:
        x = S[-1]
        if not cand or (x > max(cand)):
            cand.append(S.pop())
            continue
        y = min(ch for ch in cand if ch > x)
        return ''.join(S[:-1]) + y
        
L = len(S)
answer = F_short(S) if L < 26 else F_long(S)
print(answer)

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

int main() {
  int count=0;
  string s;
  cin >> s;
  r(i,s.size()){
    if(s[i]=='p')count++;
  }
  cout << s.size()/2-count<<endl;
}

Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException,
			IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(
				System.in));
		StringBuilder builder = new StringBuilder();
		StringTokenizer to;
		String s;
		while ((s = reader.readLine()) != null) {
			to = new StringTokenizer(s);
			int a = Integer.parseInt(to.nextToken());
			int b = Integer.parseInt(to.nextToken());
			int GCD = getGCD(a, b);
			int LCM = getLCM(a, b, GCD);
			builder.append(GCD).append(' ').append(LCM).append('\n');

		}
		System.out.print(builder);
	}

	public static int getGCD(int a, int b) {
		int tmp;
		if (a > b) {
			tmp = a;
			a = b;
			b = tmp;
		}
		while (a != 0) {
			tmp = a;
			a = b % a;
			b = tmp;
		}
		return b;
	}

	public static int getLCM(int a, int b, int GCD) {
		return a / GCD * b;
	}
}

Measured memory_bytes: 17068
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <iomanip>
#include <random>

#include <fstream>
#include <vector>
#include <algorithm>

#define ll long long int

using namespace std;

bool isPrime(ll n)
{
    if(n == 1)
    {
        return false;
    }
    for(ll i = 2; i*i <= n; i++)
    {
        if(n % i == 0)
        {
            return false;
        }
    }
    
    return true;
}

int main(void)
{

    
    ll d, tmp;
    deque<ll> c, s, res, typ(26, 0);
    
    cin >> d;
    
    for(int i = 0; i < 26; i++)
    {
        cin >> tmp;
        c.push_back(tmp);
    }
    
    for(ll i = 0; i < d; i++)
    {
        for(ll j = 0; j < 26; j++)
        {
            cin >> tmp;
            s.push_back(tmp);
        }
    }
    
    for(ll i = 0; i < d; i++)
    {
        cin >> tmp;
        if(i == 0)
        {
            res.push_back(s[26*i+tmp-1]);
        }
        else
        {
            res.push_back(s[26*i+tmp-1] + res[i - 1]);
        }
        
        for(ll j = 0; j < 26; j++)
        {
            if(j+1==tmp)
            {
                typ[j] = 0;
            }
            else
            {
                typ[j]++;
                res[i] -= c[j]*typ[j];
            }
        }
    }
    
    for(ll i = 0; i < d; i++)
    {
        cout << res[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3688
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, s, n) for(int i = s; i < n; i++)
#define rRep(i, n) for(int i = n - 1; i >= 0; i--)
#define pi pair<int, int>
#define vi vector<int>
#define endl "\n"


int32_t main() {
    FAST
    int n;
    cin >> n;
    vi vec(n);
    map<int, int> ma;
    REP(i, 0, n)
        ma[i + 1] = 0;
    REP(i, 1, n) {
        cin >> vec[i];
        ma[vec[i]]++;
    }

    REP(i, 0, n)
        cout << ma[i + 1] << endl;


}

Measured memory_bytes: 17192
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <climits>
#define bogo_sort   std::sort
#define bozo_sort   std::stable_sort
#define alles(obj)  obj.begin(), obj.end()
#define elif        else if
#define unless(flg) if(!(flg))
#define elless(flg) else if(!(flg))
#define echo        std::cout <<
#define read        std::cin >>
#define endl        std::endl
#define fin         << '\n'
#define bash        push_back
#define makePair    std::make_pair
#define _           << ' ' <<
// type-define
#define Stack       std::stack
#define Queue       std::queue
#define Set         std::set
#define PQueue      std::priority_queue
#define Vector      std::vector
#define Pair        std::pair
#define Map         std::map
#define HashMap     std::unordered_map
#define Greater     std::greater
using String  =     std::string;
using llong   =     long long;
using boolean =     bool;
using Pii     =     Pair<int, int>;
using Vi      =     Vector<int>;
using Vii     =     Vector<Pii>;
// utils
constexpr int   dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int   dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
constexpr int   INF  = 0x3f3f3f3f;
constexpr llong LINF = 0x3f3f3f3f3f3f3f3fLL;

namespace {
    template<class A, class B> A power ( llong x, llong n, llong mod ) {
        llong ans = 1;
        while ( n > 0 ) {
            if ( n & 1 ) ans = ( ans * x ) % mod;
            x = ( x * x ) % mod;
            n >>= 1;
        }
        return ans;
    }
    template<class A, class B> A power ( A x, B n ) { return power( x, n, 1000000007 ); }
    template<class A> A gcd ( A x, A y ) { return x % y ? gcd( y, x % y ) : y; }
    template<class A, class B> A lcm   ( A x,  B y ) { return ( x / gcd(x, y) * y ); }
    template<class A> inline A abs ( A n ) { return ( n < 0 ) ? -n : n; }
    template<class A, class B> inline bool chmax ( A &a, const B &b ) { return b > a ? a = b, true : false; }
    template<class A, class B> inline bool chmin ( A &a, const B &b ) { return b < a ? a = b, true : false; }
    boolean isMovable ( int x, int y, int w, int h ) {
        return ( x >= 0 && y >= 0 && x < w && y < h );
    }
}

namespace Rlyeh {

    int mas[2][128];

    signed call_of_Cthulhu( signed datum ) {

        int n;
        read n;
        for ( int i = 1; i <= 2; i++ ) {
            for ( int j = 1; j <= n; j++ ) {
                read mas[i][j];
                mas[i][j] += std::max ( mas[i][j-1], mas[i-1][j] );
            }
        }

        echo mas[2][n] fin;

        return 0;
    }
}

signed main(){std::cin.tie(0); std::ios::sync_with_stdio(false); int main_result = Rlyeh::call_of_Cthulhu(114514); return 0;}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        var sc = new Scanner(System.in);
    
        String n = sc.next();
        
        int a = 0;
        for(int i = 0; i < n.length(); i++){
            a += Integer.parseInt(n.substring(i, i+1));
        }
        if(a%9 == 0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 49904
def solve():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))
    
    ans = 0
    for i in range(N):
        if V[i] - C[i] > 0:
            ans += V[i] - C[i]
    print(ans)


if __name__ == '__main__':
    solve()

Measured memory_bytes: 3064
N,M = map(int, input().split(" "))
AB=["" for i in range(N)]
for i in range(N):
    A,B = map(int, input().split(" "))
    AB[i] = [A,B]
total_num=0
total_mon=0
AB = sorted(AB)
for i,t in enumerate(AB):
    add = t[1]
    total_num+=add
    if total_num>=M:
        add = add - (total_num-M)
        total_mon+=add*t[0]
        break
    total_mon+=add*t[0]
print(total_mon)


Measured memory_bytes: 20868
<?php
function gcm($num1,$num2)
{
    $s=max($num1,$num2);
    $t=min($num1,$num2);
    $u=$s%$t;
    while($u!=0)
    {
        $s=$t;
        $t=$u;
        $u=$s%$t;
    }
    return $t;
}

fscanf(STDIN,"%d %d",$n,$x);
$a = explode(" ", rtrim(fgets(STDIN)));
for($i=0;$i<$n;$i++)
    $a[$i]=abs($a[$i]-$x);
$result=$a[0];
for($i=0;$i<$n-1;$i++)
    $result=gcm($result,$a[$i+1]);
echo($result);

Measured memory_bytes: 22056
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
int32_t main()
{
	int v,w,t;
	int a,b;
	cin>>a>>v;
	cin>>b>>w>>t;
	int dist=abs(a-b);
	int rel=v-w;
	if(rel<0){puts("NO");}
	else
	{
		int cover=rel*t;
		if(cover<dist)
		{puts("NO");}
		else puts("YES");
		
		
	}
	
}

Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)

const lint MOD = pow(10, 9) + 7;

/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/


int main() {
	int N, H, W;
	cin >> N >> H >> W;
	cout << (N - H + 1) * (N - W + 1) << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-

A, B, C = map(int, input().split())

# A=max, B=current, C=2のcurrent
#容器2に残る量を出力する

occ_1 = A - B
if occ_1 >= C:
    print(0)
else:
    print(C - occ_1)



Measured memory_bytes: 2940
// 忌み数
import java.util.Scanner;

public class Main{
	
	long change(long n) {
		int[] digit = {0,1,2,3,5,7,8,9};
		long x = n;
		long temp = 0;
		long d = 1;
		while(x>=1) {
			temp += (digit[(int)(x%8)] * d);
			x /= 8;
			d *= 10;
		}
		return temp;
	}

    void main() {
       Scanner sc = new Scanner(System.in);
       
       while(true) {
    	   long n = sc.nextInt();
    	   if(n==0) break;
    	   System.out.println(change(n));
       }
    }

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


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

using namespace std;

int main(void)
{

  long long A, B, C, K;
  cin >> A >> B >> C >> K;

  long long count = 0;
  long long max = 0;

  if ( K <= A) {
    max += K;
    cout << max << endl;
    return 0;
  } else {
    max += A;
    count += A;
  }

  if ( K <= count + B) {
    cout << max << endl;
    return 0;
  } else {
    count += B;
  }

  if ( K <= count + C) {
    max -= K-count;
    cout << max << endl;
    return 0;
  } else {
    max -= C;
    cout << max << endl;
    return 0;
  }
  
}

Measured memory_bytes: 3636
a, b, q = gets.strip.split.map(&:to_i)
ss = a.times.map { gets.strip.to_i }
tt = b.times.map { gets.strip.to_i }
xx = q.times.map { gets.strip.to_i }

# xの位置を二分探索で見つける
# 右、左、右左*2、左右*2の6パターンを探索
# 6パターンのうち最短を出力

INF = 10**12
xx.each do |x|
  s_right_index = ss.bsearch_index {|e| e>=x } || a
  s_left_index = s_right_index-1

  t_right_index = tt.bsearch_index{|e| e>=x } || b
  t_left_index = t_right_index-1

  r_s = (s_right_index != a) ? ss[s_right_index]-x : INF
  l_s = (s_left_index != -1) ? x-ss[s_left_index] : INF
  l_s = r_s = 0 if r_s.zero? || l_s.zero?

  r_t = (t_right_index != b) ? tt[t_right_index]-x : INF
  l_t = (t_left_index != -1) ? x-tt[t_left_index] : INF
  l_t = r_t = 0 if r_t.zero? || l_t.zero?

  r = [r_s, r_t].max
  l = [l_s, l_t].max
  rt_ls = r_t*2+l_s
  rs_lt = r_s*2+l_t
  lt_rs = l_t*2+r_s
  ls_rt = l_s*2+r_t
  #p [r, l, rt_ls, rs_lt, lt_rs, ls_rt]
  p [r, l, rt_ls, rs_lt, lt_rs, ls_rt].min
end



Measured memory_bytes: 5752
#include<bits/stdc++.h>
typedef long long i64;
i64 H, W;

i64 calc(i64 H,i64 W) {
  i64 ans = H <= 2 ? 1e15 : W * (H % 3 ? 1 : 0);
  if(H > 1) {
    for(i64 i = 1;i < W; ++i) {
      i64 max = std::max(i * H, std::max(H/2, H - H/2) * (W - i));
      i64 min = std::min(i * H, std::min(H/2, H - H/2) * (W - i));
      ans = std::min(max - min, ans);
    }
  }
  return ans;
}

int main() {
  if(fopen("input.txt","r")) {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
  }
  scanf("%lld%lld", &H, &W);
  printf("%lld", std::min(calc(H, W), calc(W, H)));
  return 0;
}


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


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


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney, tree, chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun

#define REP(i,a,b) for(ll i = a; i < b; ++i)
#define PRI(s) cout << s << endl
#define PRIF(v, n) printf("%."#n"f\n", v)
#define PRIY PRI("Yes")
#define PRIN PRI("No")
#define MINS(a,b) a = min(a,(decltype(a))(b))
#define MAXS(a,b) a = max(a,(decltype(a))(b))



ll mod = 1e9 + 7;

ll modpow(ll r, ll n) {
	ll ans = 1;
	ll tmp = r;
	while (n > 0) {
		if ((n & 1) > 0) ans = ans * tmp % mod;
		tmp = tmp * tmp % mod;
		n >>= 1;
	}
	return ans;
}

int main() {
	ll N;
	cin >> N;
	ll ans = modpow(10, N) + modpow(8, N) - 2 * modpow(9, N);
	ans = (ans % mod + mod) % mod;
	PRI(ans);
	return 0;
}

Measured memory_bytes: 3628
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;

struct Node{
  int key;
  Node *right,*left,*parent;
};


Node *root, *NIL;

Node * find(Node *u,int k){
  while(u!=NIL && k!=u->key){
    if(k<u->key) u=u->left;
    else u = u->right;
  }
  return u;
}

void insert(int k){
  Node *y = NIL;
  Node *x = root;
  Node *z;

  z = (Node *)malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key){
      x = x->left;
    }else{
      x = x->right;
    }
  }
  z->parent = y;
  if(y==NIL){
    root = z;
  }else{
    if(z->key < y->key){
      y->left = z;
    }else{
      y->right = z;
    }
  }
}

void inorder(Node *u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node *u){
  if(u==NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int n,i,x;
  string com;

  scanf("%d",&n);

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

    if(com[0] == 'f'){
      scanf("%d",&x);
      Node *t = find(root,x);
      if(t != NIL) printf("yes\n");
      else printf("no\n");
    }else if(com == "insert"){
      scanf("%d",&x);
      insert(x);
    }else if(com == "print"){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}



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

class Program
{
    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());

        int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int[] b = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int[] c = Console.ReadLine().Split().Select(int.Parse).ToArray();

        int m = 0;
        int beforeM = -1;

        for(int i = 0; i < n; i++)
        {
            m += b[a[i] - 1];
            if(beforeM == a[i] - 1)
            {
                m += c[beforeM - 1];
            }

            beforeM = a[i];
        }

        Console.WriteLine(m);
    }
}


Measured memory_bytes: 13268
local n,k=io.read("n","n")
local t={}
for i=0,k-1 do
    t[i]=0
end
for i=1,n do
    t[i%k]=t[i%k]+1
end

local counter=0
for a=0,k-1 do
    local b=(k-a)%k
    local c=(k-a)%k
    if (b+c)%k==0 then
        counter=counter+t[a]*t[b]*t[c]
    end
end
print(counter)

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

int main()
{
    long long x;
    cin >> x;
    long long count=0;
    count += (x / 11) * 2;
    x = x % 11;
    count += x / 6;
    x = x % 6;
    if (x == 0)
    {
        cout << count << endl;
    }
    else
    {
        cout << count + 1 << endl;
    }
}


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

using namespace std;

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

    int n = s.length();
    int ans = 0;
    for(int i=0;i<n;i++)
    {
        char c;
        if(i&1)
            c = 'p';
        else
            c = 'g';
        if(c>s[i])
            ans++;
        else if(c<s[i])
            ans--;
    }
    cout<<ans;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,d,ans=0;
  cin>>n>>d;
  ans=(n-d-1)*(n-d-2)/2+d+min(d+1,3LL)*(n-d-1);
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3096
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		long n = sc.nextLong();
		if (n == 1) {
			System.out.println(0);
			System.exit(0);
		}

		long sqrt = (long) Math.sqrt(n) + 1;
		long tmp = n;
		ArrayList<Long> primeFactorCount = new ArrayList<Long>();

		// prime factorization
		for (long i = 2; i < sqrt; i++) {
			if (tmp % i == 0) {
				long count = 0;
				while (tmp % i == 0) {
					count++;
					tmp /= i;
				}
				primeFactorCount.add(count); // only need exponent.
			}
		}
		// if tmp != 1, it's last prime factor.
		// if there is no prime factor, n is prime number.
		if (tmp != 1 || primeFactorCount.size() == 0)
			primeFactorCount.add((long) 1);

		int ansCount = 0;
		for (long exp : primeFactorCount) {
			long used = 0;
			while (exp > used) { // exponent > (1+2+3+...)
				ansCount++;
				used++;
				exp -= used;
			}
		}
		System.out.println(ansCount);
	}
}


Measured memory_bytes: 35832
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define FOR(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
using namespace std;

void _main() {
    int N, R;
    cin >> N >> R;
    if (N >= 10) cout << R << endl;
    else cout << R + 100 * (10 - N) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    _main();
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		char[] inS = sc.next().toCharArray();
		char[] inT = sc.next().toCharArray();
		
		char[] s = new char[inS.length + 1];
		System.arraycopy(inS, 0, s, 1, inS.length);
		char[] t = new char[inT.length + 1];
		System.arraycopy(inT, 0, t, 1, inT.length);
		
//		System.out.println(Arrays.toString(s));
//		System.out.println(Arrays.toString(t));
		             
		
		int[][] dp = new int[s.length][t.length];
		for (int i = 1; i < s.length; i++) {
			for (int j = 1; j < t.length; j++) {
				if (s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
				else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
		
		char[] ans = new char[dp[s.length - 1][t.length - 1]];
		int idx = ans.length - 1;
		
		int i = s.length - 1;
		int j = t.length - 1;
		while (idx >= 0) {
			if (s[i] == t[j]) {
				ans[idx] = s[i];
				idx--;
				i--;
				j--;
			} else if (dp[i - 1][j] >= dp[i][j - 1]) {
				i--;
			} else {
				j--;
			}
		}
		
//		for (int[] arr : dp)
//			System.out.println(Arrays.toString(arr));
//		System.out.println(Arrays.toString(ans));
		
		for (char c : ans)
			System.out.print(c);
		System.out.println();
		
		sc.close();
	}
}



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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int l,n;
int x[252521];
ll ans;

ll sum[252521];
ll rval[252521], lval[252521];

void solve(){
  sum[0] = 0;
  REP(i,n)sum[i+1] = x[i];
  sum[n+1] = l;
  rval[1] = 2ll * (sum[n+1] - sum[2]);
  FOR(i,2,n+1){
    rval[i] = rval[i-1];
    rval[i] -= 2ll * (sum[min(n+1,2*i-1)] - sum[i]);
    rval[i] += 2ll * (sum[n+1] - sum[min(n+1,2*i)]);
  }
  lval[n] = 1ll * sum[n];
  FORR(i,1,n){
    lval[i] = lval[i+1];
    int j = n+1-i;
    lval[i] -= 1ll * (sum[i+1] - sum[i]);
    lval[i] -= 2ll * (sum[i] - sum[max(0,i-(j-2))]);
    lval[i] += 2ll * (sum[max(0,i-(j-2)-1)] - sum[0]);
  }
  FOR(i,1,n+1)CHMAX(ans, lval[i]+rval[i]);
  // FOR(i,1,n+1)DEBUG(lval[i]);
  // FOR(i,1,n+1)DEBUG(rval[i]);
}

int main(){
  scanf("%d%d",&l,&n);
  REP(i,n)scanf("%d",x+i);
  ans = 0;
  solve();
  reverse(x,x+n);
  REP(i,n)x[i] = l - x[i];
  solve();
  printf("%lld\n",ans);
  return 0;
}


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

int main()
{
    int a,b;
    cin >> a >> b;
    if(a < b){
        cout << "a < b" << endl;
    }else if(a > b){
        cout << "a > b" << endl;
    }else{
        cout << "a == b" << endl; 
    }
    return 0;
}



Measured memory_bytes: 3080
#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << " _ " <<

using namespace std;

const int N = 1e5 + 7;

int n, k;
int a[N], dp[N];

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

	if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) 
		dp[i] = INT_MAX;
	dp[1] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= k; j++)
			if (i - j > 0)
				dp[i] = min(dp[i], dp[i - j] + abs(a[i] - a[i - j]));
	cout << dp[n];
}

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

using namespace std;

typedef long long ll;

ll A[5];

ll cal ( void )
{

  ll sum = 0;

  for ( int i = 0; i < 3; ++i ) {
    for ( int j = i+1; j < 4; ++j ) {
      for ( int k = j+1; k < 5; ++k ) {
        sum += A[i]*A[j]*A[k];
      }
    }
  }

  return sum;
}

int main()
{
  string s;
  int N;

  cin >> N;
  while(N--) {
    cin >> s;
    if ( s[0] == 'M' ) ++A[0];
    if ( s[0] == 'A' ) ++A[1];
    if ( s[0] == 'R' ) ++A[2];
    if ( s[0] == 'C' ) ++A[3];
    if ( s[0] == 'H' ) ++A[4];
  }

  cout << cal() << "\n";

}


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

int main(){
  int n,cnt=0;
  cin >> n;
  int a[n],b[n],c[n-1];
  for(int i=0;i<n;i++)
    cin >> a[i];
  for(int i=0;i<n;i++){
    cin >> b[i];
    cnt += b[i];
  }
  for(int i=0;i<n-1;i++)
    cin >> c[i];
  for(int i=0;i<n-1;i++){
    if(a[i+1]-a[i]==1)
      cnt += c[a[i]-1];
  }
  cout << cnt << endl;
}

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


int main() {
  string s;
  cin >> s;
  if(s[2]==s[3] && s[4]==s[5]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
#define int ll
ll p[maxn],q[maxn],r[maxn];
multiset<ll>s1,s2;
int32_t main(){
	int x,y,a,b,c;
	cin>>x>>y>>a>>b>>c;
	for(int i=1;i<=a;i++)cin>>p[i];
	for(int i=1;i<=b;i++)cin>>q[i];
	for(int i=1;i<=c;i++)cin>>r[i];
	sort(p+1,p+1+a,[](ll a,ll b){
		return a>b;
	});
	sort(q+1,q+1+b,[](ll a,ll b){
		return a>b;
	});
	sort(r+1,r+1+c,[](ll a,ll b){
		return a>b;
	});	
	
	for(int i=1;i<=x;i++)s1.insert(p[i]);
	for(int i=1;i<=y;i++)s2.insert(q[i]);
	for(int i=c;i>=1;i--){
		ll tmp1=-1;
		auto it1=s1.lower_bound(r[i]);
		if(it1!=s1.begin()){
			tmp1=max(r[i]-*s1.begin(),tmp1);
		}
		ll tmp2=-1;
		auto it2=s2.lower_bound(r[i]);
		if(it2!=s2.begin()){
			tmp2=max(r[i]-*s2.begin(),tmp2);
		}
		if(tmp1<0&&tmp2<0)continue;
		if(tmp1>tmp2){
			s1.erase(s1.begin());
			s1.insert(r[i]);
		}
		else {
			s2.erase(s2.begin());
			s2.insert(r[i]);
		}
	}
	ll ans=0;
	for(auto p:s1)ans+=p;
	for(auto p:s2)ans+=p;
	cout<<ans<<endl;
	return 0;
}

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

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

int main(){
  int n,m;
  cin>>n>>m;
  ll a[100005];
  rep(i,n){
    cin>>a[i];
    a[i]/=2;
  }
  ll l=a[0];
  rep(i,n-1){
    ll g=gcd(l,a[i+1]);
    if(l/g%2==0||a[i+1]/g%2==0){
      cout<<0<<endl;
      return 0;
    }
    l=l*a[i+1]/g;
  }
  cout<<(m/l+1)/2<<endl;
  return 0;
}

Measured memory_bytes: 1024
f=lambda:map(int,input().split())
n,m,x=f()
lc,ll=[],[]
for _ in range(n):
  c,*l=f()
  lc.append(c)
  ll.append(l)
a=10**9
for i in range(2**n):
  lm=[0]*m
  t=0
  for j in range(n):
    if i>>j&1:
      for k in range(m):
        lm[k]+=ll[j][k]
      t+=lc[j]
  if all(s>=x for s in lm):
    a=min(a,t)
print(a if a<10**9 else -1)

Measured memory_bytes: 9224
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
from collections import defaultdict
s = defaultdict(int)
f = {}
ans = 0
for i in a:
  s[i] += 1
  f[i] = None
  ans += i

for _ in range(q):
  b, c = map(int, input().split())
  ans = ans + (c - b) * s[b]
  s[c] += s[b]
  s[b] = 0
  print(ans)

Measured memory_bytes: 25956