akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>	
#include <deque>
#include <set>
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define fore(i,a) for(auto &i:a)
#define INF INT_MAX/2;
#define PI 3.14159265358979323846264338327950L;
const int INF2 = 1001001001;
typedef long long ll;
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
using namespace std;
using Graph = vector<vector<int>>;


int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}


 // 最大公約数計算
 
ll gcd(ll a, ll b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
// 最小公倍数の計算

ll lcm(ll a, ll b)
{
	ll g = gcd(a, b);

	return a / g * b;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


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

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

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (r[x] < r[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if (r[x] == r[y])
			{
				r[x]++;
			}
		}
	}
};

const int MAX_N = 110000;

int memo[MAX_N];

int rec(int n) {
	if (n == 0)return 0;
	if (memo[n] != -1)return memo[n];

	int res = n;

	for (int pow6 = 1; pow6 <= n; pow6 *= 6)res = min(res, rec(n - pow6) + 1);

	for (int pow9 = 1; pow9 <= n; pow9 *= 9)res = min(res, rec(n - pow9) + 1);

	return memo[n] = res;
}

int calc(int x) {
	int ret = 0;
	while (x % 2 == 0) {
		x /= 2;
		ret++;
	}

	return ret;
}

int a[12][12];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);


	int s;
	cin >> s;
	
	if (s < 1200) {
		cout << "ABC" << endl;
		return 0;
	}
	else if (s < 2800) {
		cout << "ARC" << endl;
		return 0;
	}
	else {
		cout << "AGC" << endl;
	}


}
	

Measured memory_bytes: 256
def getNum(li, st):
    cnt = 0
    for l in li:
        if l == st:
            cnt += 1
    return cnt


n = int(input())
bc = []
for x in range(n):
    bc.append(input())

m = int(input())
rc = []
for x in range(m):
    rc.append(input())

bcu = list(set(bc))
rcu = list(set(rc))

brcu = list(set(bcu + rcu))

blist = {}
rlist = {}

for sentence in brcu:
    blist[sentence] = 0
    rlist[sentence] = 0

for srt in bcu:
    blist[srt] = getNum(bc, srt)

for srt in rcu:
    rlist[srt] = getNum(rc, srt)

# print(brcu)
# print(blist)
# print(rlist)

result = []

for sentence in brcu:
    result.append(blist[sentence] - rlist[sentence])

# print(result)
if max(result) < 0:
    print(0)
else:
    print(max(result))


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

int main()
{
    std::string str;
    getline(std::cin, str);

    int arr[26] = {}, strLen = str.length();
    bool flag = 1;

    for(int i = 0; i < strLen; i++)
    {
        arr[str[i] - 'a']++;
    }

    for(int i = 0; i < 26; i++)
    {
        if(arr[i]%2 == 1)
        {
            flag = 0;
        }
    }

    if(flag)
    {
        std::cout << "Yes" << std::endl;
    }
    else
    {
        std::cout << "No" << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

public final class Main {

    public static void main(String[] args) {
        final FastScanner fs = new FastScanner();
        final int n = fs.nextInt();
        final int m = fs.nextInt();
        int res = 0;
        for (int p = 1; p * p <= m; p++) {
            if (m % p == 0) {
                if (p <= m / n) {
                    res = Math.max(res, p);
                }
                if (m / p <= m / n) {
                    res = Math.max(res, m / p);
                }
            }
        }
        System.out.println(res);
    }

    static final class Utils {
        public static void shuffleSort(int[] arr) {
            shuffle(arr);
            Arrays.sort(arr);
        }

        public static void shuffleSort(long[] arr) {
            shuffle(arr);
            Arrays.sort(arr);
        }

        public static void shuffle(int[] arr) {
            final Random r = new Random();

            for (int i = 0; i <= arr.length - 2; i++) {
                final int j = i + r.nextInt(arr.length - i);
                swap(arr, i, j);
            }
        }

        public static void shuffle(long[] arr) {
            final Random r = new Random();

            for (int i = 0; i <= arr.length - 2; i++) {
                final int j = i + r.nextInt(arr.length - i);
                swap(arr, i, j);
            }
        }

        public static void swap(int[] arr, int i, int j) {
            final int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }

        public static void swap(long[] arr, int i, int j) {
            final long t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }

        private Utils() {}
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        private String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    //noinspection CallToPrintStackTrace
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        int[] nextIntArray(int n) {
            final int[] a = new int[n];
            for (int i = 0; i < n; i++) { a[i] = nextInt(); }
            return a;
        }

        long[] nextLongArray(int n) {
            final long[] a = new long[n];
            for (int i = 0; i < n; i++) { a[i] = nextLong(); }
            return a;
        }
    }
}


Measured memory_bytes: 32800
# coding: utf-8
import time
import re
import math
import fractions

def main():
    s=input()
    if 2==len(set(s)):
        print("Yes")
    else:
        print("No")

start=time.time()
main()
#print("処理速度 {}sec".format(time.time()-start))
#A=list(map(int,input().split()))
#A,B,C=map(int,input().split())
#n=int(input())
# global N,A,B,C,D,memo,mx,mn,temp


Measured memory_bytes: 5044
#include <bits/stdc++.h> 
#define ll long long
#define pb push_back
#define mp make_pair
const ll inf = 1e9;
const ll zero = 0;
const ll MOD = 1e9+7;
using namespace std;
map<ll,ll> dp;
ll xorsum(ll n){
	if (dp[n]!=0){
		return dp[n];
	}
	ll ret = 0;
	ret+=xorsum(n/2);
	ret%=MOD;
	ret+=xorsum((n-1)/2);
	ret%=MOD;
	ret+=xorsum((n-2)/2);
	ret%=MOD;
	dp[n]=ret;
	return ret;
}

int main(){
	ll n;
	dp[0]=1;
	dp[1]=2;
	dp[2]=4;
	dp[3]=5;
	cin>> n;
	cout<<xorsum(n);
}

Measured memory_bytes: 256
#include <cstdio>

int main(int argc, char const *argv[]) {
    char S[4];
    scanf("%s", S);
    if (S[0] != S[1] && S[1] != S[2] && S[0] != S[2]) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
const long long MOD = 1e9+7;
using namespace std;
#define ll long long
#define ar array

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

	string S;
	cin >> S;

	if (S.back()=='s') {
		S+="es";
	} else {
		S+="s";	
	}
	cout << S << endl;
	return 0;
}


Measured memory_bytes: 3596
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int house[][][] = new int[4][3][10];
		int n = scan.nextInt();
		int b,f,r,v,k=0;
		
		while(k<n) {
			b = scan.nextInt()-1;
			f = scan.nextInt()-1;
			r = scan.nextInt()-1;
			v = scan.nextInt();
			house[b][f][r] +=  v;
			if(house[b][f][r] < 0) house[b][f][r]=0;
			k++;
		}

		for(int i=0;i<4;i++) {
			for(int j=0;j<3;j++) {
				for(int s=0;s<10;s++) {
					System.out.print(" "+house[i][j][s]);
				}
				System.out.println();
			}
			if(i<3) System.out.println("####################");
		}

		scan.close();
	}

}



Measured memory_bytes: 29540
def main():
    from functools import reduce

    MOD = 10 ** 9 + 7

    def mod_mul(a, b):
        return a * b % MOD

    N = int(input())
    ans = reduce(mod_mul, range(1, N + 1))
    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 3572
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <functional>
using namespace std;
using ll = long long;
int main(){
  int n;
  cin >> n;
  long long t, a;
  long long to=0, ao=0;
  cin >> to >> ao;
  for(int i = 0; i < n - 1; i++){
    cin >> t >> a;
    long long m = max(to / t + (to%t==0 ? 0:1), ao/a + (ao%a==0 ? 0:1)) ;
    to = t*m;
    ao = a*m;
//    cout << to << "," << ao << endl;
  }
  cout << to + ao << endl;
  return 0;
} 


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000


int main() {
	int a[N];
	f(i, N)a[i] = 0;
	vector<int>b;
	int n, k;
	int x, y, z;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%d", &n);
	f(i, n) {
		scanf("%d", &a[i]);
	}
	a[n] = -1;
	f(i, n) {
		k = -1;
		f(j, n - i) {
			if (a[j] == j + 1)k = j;
		}
		if (k == -1) {
			printf("-1\n");
			return 0;
		}
		f(j, n - i) {
			if (j >= k)a[j] = a[j + 1];
		}
		b.push_back(k + 1);
	}

	f(i,n)printf("%d\n", b[n-i-1]);

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define sz(x) ((int)(x).size())
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int main() {
  int N;
  cin >> N;
  int M = 100000;
  vector<int> A(N);
  vector<int> cnt(M);
  rep(i, N) {
    cin >> A[i];
    A[i]--;
    cnt[A[i]]++;
    if (cnt[A[i]] == 3)
      cnt[A[i]] -= 2;
  }

  int ans = 0;
  int dupl = 0;
  rep(i, M) {
    if (cnt[i] > 0)
      ans++;
    if (cnt[i] == 2)
      dupl++;
  }

  if (dupl % 2)
    ans--;

  cout << ans << endl;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  ll ans=n*800-200*(n/15);
  cout<<ans<<endl;
}

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

int main() {
    int N,M;
    cin >> N >> M;
    vector<int> city(2 * M);
    vector<int> sum(N);
    for(int i = 0; i < 2*M; i++ ){
        cin >> city.at(i);
        for (int l = 0; l < N; l++){
           if (l+1 == city.at(i)){
            sum.at(l)++;
           }
        }
    }
    for(int k = 0; k < N; k++){
        cout << sum.at(k) << endl;
    }
}


Measured memory_bytes: 256
n = int(input())
l = list(list(map(str,input().split())) for _ in range(n))
x = input()
bit = 0
su = 0
for j,k in l:
  if j==x:
    bit = 1
    su -= int(k)
  if bit==1:
    su += int(k)
print(su)


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


using namespace std;
int main()
{
	string s;
	int len = 0;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'A') {
			for (int j = i; j < s.size(); j++) {
				if (s[j] == 'Z') {
					len = j - i + 1;
				}
			}
			break;
		}
	}

	cout << len << endl;
	return 0;
}



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

class DICE{
private:
	int D[6];//??????????????????
	
public:
	DICE();
	void set();
	void show();
	void roll(char order);
};


//?????????????????????	??????????????????????????????
DICE::DICE(){
	for(int i = 0; i < 6; ++i){
		D[i] = i+1;
	}
}



//??????????????????????????´=========================================
void DICE::set(){
	
	int number[6];
	
	for(int i = 0; i < 6; ++i){
		cin >> number[i];
	}
	
	D[0] = number[0];//1
	D[1] = number[1];//2
	D[2] = number[2];//3
	D[3] = number[3];//4
	D[4] = number[4];//5
	D[5] = number[5];//6
}



//??????????????????????????¨???========================================-
void DICE::show(){
	cout << D[0] << endl;
}



//?????????????????¢??????==========================================-
void DICE::roll(char order){
	
	int exchange;
		
	if(order == 'N'){//???????????????1????????¢??????
		exchange = D[0];
		D[0] = D[1];
		D[1] = D[5];
		D[5] = D[4];
		D[4] = exchange;
	}
		
	if(order == 'S'){//???????????????1????????¢??????
		exchange = D[0];
		D[0] = D[4];
		D[4] = D[5];
		D[5] = D[1];
		D[1] = exchange;
	}

	if(order == 'E'){//??±????????????1????????¢??????
		exchange = D[0];
		D[0] = D[3];
		D[3] = D[5];
		D[5] = D[2];
		D[2] = exchange;
	}

	if(order == 'W'){//?\?????????????1????????¢??????
		exchange = D[0];
		D[0] = D[2];
		D[2] = D[5];
		D[5] = D[3];
		D[3] = exchange;
	}
}





int main(){
	
	string order;
	DICE dice;
	
	
	dice.set();
	
	cin >>order;
	for(int i = 0; i < order.size(); ++i){
		dice.roll(order[i]);
	}
	
	dice.show();
	
	
	return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

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

using namespace std;
typedef long long ll;

struct Tree {
    string s;
    int index;
    vector<Tree*> v;

    Tree(string _s) {
        s = _s;
        index = 0;
        v.clear();
    }

    Tree(string _s,int id) {
        s = _s;
        index = id;
        v.clear();
    }

    void add(int id,int i,string s) {
        find(i)->v.push_back(new Tree(s,id));
    }

    Tree* find(int id) {
        if(this->index == id) return this;
        
         rep(i,v.size()) {
             Tree *tree = this->v[i]->find(id);
             if(tree != NULL) {
                 return tree;
             }
         }

         return NULL;
    }

    void print(int dep) {
        
        rep(i,dep) {
            cout << ".";
        }
        cout << this->s << endl;
        
        rep(i,this->v.size()) {
            this->v[i]->print(dep+1);
        }

        return;
    }

};

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

    cin >> dist >> s;

    Tree *tree = new Tree(s,dist);

    REP(i,1,n) {
        cin >> dist >> s;
        tree->add(i,dist-1,s);

    }

    tree->print(0);

    return 0;
}

Measured memory_bytes: 1420
import sys
input = sys.stdin.readline

N, A, B = map(int, input().split())
h = [int(input()) for _ in range(N)]


def is_OK(x):
    cnt = 0
    for hi in h:
        hi -= B * x
        if hi > 0:
            if hi % (A - B) == 0:
                cnt += hi // (A - B)
            else:
                cnt += hi // (A - B) + 1
    return cnt <= x


left = 0
right = sum(h) // A + N
while right - left > 1:
    mid = (left + right) // 2
    if is_OK(mid):
        right = mid
    else:
        left = mid
print(right)


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

public class Score
{
    public string tn { get; set; }
    public int s { get; set; }
}

public class Hello
{
    public static void Main()
    {
        var second = false;
        while (true)
        {
            var scores = new List<Score>();
            var n = int.Parse(Console.ReadLine().Trim());
            if (n == 0) break;
            for (int i = 0; i < n; i++)
            {
                string[] line = Console.ReadLine().Trim().Split(' ');
                scores.Add(new Score { tn = line[0], s = 3 * int.Parse(line[1]) + int.Parse(line[3]) });
            }
            if (second) Console.WriteLine();
            else second = true;
            foreach (var x in scores.OrderByDescending(a => a.s))
                Console.WriteLine("{0},{1}", x.tn, x.s);
        }
    }
}

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

using namespace std;

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> M(N);
  for (int i = 0; i < N; i++) cin >> M[i];
  sort(M.begin(), M.end());
  int sum = accumulate(M.begin(), M.begin() + N, 0);
  int remain = X - sum;
  cout << N + remain / M[0];

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int A,B,C;
	cin>>A>>B>>C;
	if(A==5&&B==5&&C==7)
		cout<<"YES";
		else if(A==5&&B==7&&C==5)
			cout<<"YES";
	    else if(A==7&&B==5&&C==5)
		cout<<"YES";
		else
			cout<<"NO"<<endl;
			return 0;
}

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;

const int mod = 1e9 + 7;

vector<int> decode(string s1, string s2) {
  vector<int> v;
  int i = 0;
  while (i < s1.size()) {
    if (s1[i] == s2[i])
      v.push_back(0), i += 1;
    if (i + 1 < s1.size() && s1[i] == s1[i + 1])
      v.push_back(1), i += 2;
  }
  return v;
}

int main() {
  int N;
  cin >> N;
  string s1, s2;
  cin >> s1 >> s2;

  auto v = decode(s1, s2);

  ll ans = 1;
  rep(i, v.size()) {
    if (i == 0) {
      ans *= v[i] == 0 ? 3 : 6;
    } else {
      int p = v[i - 1], n = v[i];
      if (p == 0 && n == 0)
        ans *= 2;
      if (p == 0 && n == 1)
        ans *= 2;
      if (p == 1 && n == 0)
        ans *= 1;
      if (p == 1 && n == 1)
        ans *= 3;
    }
    ans %= mod;
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
s = 0
d = 0
for i in range(len(A)):
    if i == 0:
        continue
    d = A[i - 1] - A[i]
    if d > 0:
        s += d
        A[i] += d
print(s)



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

// #include<cstdio>

int main(){
  int r, c;
  int m[101][101]={};
  cin >> r >> c;
  for (int i=0; i<r; i++){
    for (int j=0; j<c; j++){
      cin >> m[i][j];
      m[i][c]+=m[i][j];
      m[r][j]+=m[i][j];
      m[r][c]+=m[i][j];
    }
  }
  

  for (int i=0; i<=r; i++){
    for (int j=0; j<=c; j++){
      cout << m[i][j];
      if (j==c) continue;
      cout << ' ';
    }
    cout << "\n";
  }

  return 0;
}

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

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	string s,t;
	cin>>n>>s>>t;
	if(s==t){
		cout<<0<<endl;
		return 0;
	}
	int sp=n-1,tp=n-1,ans=0;
	queue<int> q;
	while(tp>=0){
		while(tp-1>=0&&t[tp]==t[tp-1])	tp--;
		while(sp>=0&&(sp>tp||s[sp]!=t[tp]))	sp--;
		if(sp<0){
			cout<<-1<<endl;
			return 0;
		}
		while(!q.empty()&&q.front()-q.size()>=tp)
			q.pop();
		if(tp!=sp)
			q.emplace(sp);
		ans=max(ans,(int)q.size()+1);
		tp--;
	}
	cout<<ans<<endl;
}


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

ans = 0
for i in range(n):
  s = sum([a[i][j]*b[j] for j in range(m)])
  if s+c > 0:
    ans += 1
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
int main(){
  ios::sync_with_stdio(0);  cin.tie(0); cout<<setprecision(3); cout<<fixed;
  #ifdef DEBUG
  freopen("ip.txt","r",stdin);
  clock_t tStart = clock();
  #endif
  ull n; cin>>n; n=floor(sqrt(n));
  cout<<n*n<<'\n';


  #ifdef DEBUG
	cout<<"\nExecution time: "<<(((double)clock() - tStart)/CLOCKS_PER_SEC)<<"s.\n";
	#endif
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int n, t, a, min, min_i, diff;
  static int h[1024];

  cin >> n >> t >> a;
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }

  min = 0x7FFFFFFF;
  min_i = 1001;

  for (int i = 0; i < n; i++) {
    //cout << h[i] << endl;
    //cout << h[i];
    diff = (1000*t - h[i]*6) - 1000*a;
    if (diff < 0) {
      diff = -diff;
    }
    if (diff < min) {
      min_i = i;
      min   = diff;
    }
    //cout << " " << diff << endl;
  }

  cout << min_i + 1 << endl;

  return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
a = list( map(int, input().split()))
p = 10**9+7
ans = 0

suma = sum(a)
sumaa1 = (suma**2//2)%p

sumaa2 = 0
for i in range(n):
    sumaa2 += (a[i]**2)
sumaa2 = sumaa2//2

ans = (sumaa1-sumaa2)%p

print(ans)

Measured memory_bytes: 92124
A,B=map(int, input().split()) 
from fractions import gcd

yakusu=[]
ans=[]
bigger_val=max(A,B)
gcd_AB=gcd(A,B)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

yakusu=sorted(make_divisors(gcd_AB))

for i in yakusu:
  if i==1:
    ans.append(i)
  else:
    if len(ans)==1:
      ans.append(i)
      #print(i,"追加")
    else:
      flag=True
      for j in ans:
        if j>1:
          if gcd(i,j)==1:
            pass
          else:
            #print(i,"は",j,"で割れる")
            flag=False
      else:
        if flag==True:
          ans.append(i)
          #print(i,"追加。",j,"までで割り切れないので。")
        
#          if i%j==0:
#            print(i,"は",j,"で割り切れるので除外")
#            break
#          ans.append(i)
#          print(i,"追加。",j,"までで割り切れないので。")           
#        else:
#          pass
      
#print(yakusu)
#print(ans)
print(len(ans))

Measured memory_bytes: 5304
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <tuple>
#include <stack>
#include <bitset>

using namespace std;
typedef long long ll;
const int MAX_N = 100002;
vector<int> G[MAX_N];
int color[MAX_N]; // 1 or -1

bool dfs (int v, int c) {
  color[v] = c;
  for(int i = 0; i < G[v].size(); i++) {
    int v_adj = G[v][i];
    if (color[v_adj] == c) return false;
    if (color[v_adj] == 0) {
      if (!dfs(v_adj, -c)) return false;
    }
  }
  return true;
}

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

  // 0-based index
  ll N, M, A, B;
  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    cin >> A >> B;
    A--; B--;
    G[A].push_back(B);
    G[B].push_back(A);
  }
  fill(color, color + MAX_N, 0);

  ll ans;
  if ( dfs(0, 1) ) {
    ll cnt = 0;
    for(int i = 0; i < N; i++) {
      if(color[i] == 1) cnt++;
    }
    ans = cnt * (N - cnt) - M;
  }
  else ans = N*(N-1)/2 - M;

  cout << ans << endl;
  return 0;
}


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

int main(){
  string s; cin >> s;
  int q; cin >> q;
  bool flag = false;
  deque<char> d;
  for(char i: s) d.push_back(i);
  
  for(int i = 0; i < q; i++){
  	int ty; cin >> ty;
  	if(ty == 1) flag = !flag;
  
  	else{
    	int f; char c; cin >> f >> c;
    	if(flag) f = 3-f;
    	if(f == 1) d.push_front(c);
    	else d.push_back(c);
    }
  }
  string ans;
  for(char i: d) ans += i;
  if(flag) reverse(ans.begin(), ans.end());
  cout << ans << endl;
    
}

Measured memory_bytes: 1412
# -*- coding: utf-8 -*-

w,h,x,y = map(float, input().split())



mino = "{0:.6f}".format(w*h/2)
if w==x*2 and h==y*2:
  out = 1
else:
  out = 0

print(str(mino) + " " + str(out))

Measured memory_bytes: 2940
import math
N = int(input())
inf = pow(10, 7)

def sum_digits(n):
    answer = 0
    for d in reversed(range(7)):
        shou, amari = divmod(n, pow(10, d))
        if shou == 0:
            continue
        answer += shou
        n = amari
    return answer

answer = inf
answer_v = (0,0)
for a in range(1, math.ceil(N/2)+1):
    b = N-a
    if sum_digits(a) + sum_digits(b) < answer:
        answer = sum_digits(a) + sum_digits(b)
        answer_v = (a, b)

print(str(answer))
# print(str(answer_v))

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
char S[10];
int main(){
    scanf("%s", S);
    ll ans = 0;
    if(S[0]=='M'){
        ans = 6;
    }
    if(S[0]=='T'){
        if(S[1]=='U')
            ans = 5;
        else
        {
            ans = 3;
        }
    }
    if(S[0]=='W'){
        ans = 4;
    }
    if(S[0]=='F'){
        ans = 2;
    }
    if(S[0]=='S'){
        if(S[1]=='A')
            ans = 1;
        else
        {
            ans = 7;
        }
        
    }
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
	int num, n1, n2, a, b;
	cin >> num >> a >> b;
	for (int i = 0; i < num - 2; i++)
		scanf("%d", &a);
	cin >> n1;
	if (num == 1)
		a = abs(n1 - b);
	else {
		cin >> n2;
		a = max(abs(n2 - b), abs(n1 - n2));
	}
	printf("%d\n", a);
	return 0;
}

Measured memory_bytes: 256
//it was hard to write
//so it should be hard to read
#include <bits/stdc++.h>
#define sz size
#define pb push_back
#define ll long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define last(x) (x).size() - 1
#define mp make_pair

using namespace std;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef double ld;

const int MAXN = 1e6 + 5;
const ll INF = 1e18 + 7;
const int inf = 1e9 + 7;
const double EPS = 1e-9;

int n;
double t, a;
int res;
double mn = double(inf);

int main() {
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(9);
    cout << fixed;
	cin >> n >> t >> a;
	for (int i = 1; i <= n; i++) {
		double h;
		cin >> h;
		double cur = t - h * 0.006;
		cur = abs(a - cur);
		if (mn - cur > 0.00000) {
			mn = cur;
			res = i;
		}
	}
	cout << res;
	return 0;
}


Measured memory_bytes: 256
n, k = gets.split.map(&:to_i)

cnt = 0
1.upto(n) do |a|
  b = (n * k - a) % k
  comb_b = (n + b) / k

  c = (n * k - b) % k
  comb_c = (n + c) / k

  if (a + c) % k == 0
    cnt += comb_b * comb_c
  end
end

p cnt



Measured memory_bytes: 1788
using System;
using System.Linq;

namespace B.String_Rotation
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Console.ReadLine();
            var T = Console.ReadLine();
            bool ans = false;

            for (int i = 0; i < S.Length; i++)
            {
                S = string.Concat(S.Last(), S);
                S = S.Remove(S.Length - 1);

                if (S==T)
                {
                    ans = true;
                    break;
                }
            }

            Console.WriteLine(ans ? "Yes" : "No");
        }
    }
}


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

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

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cerr << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#define debug(...) CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) (__VA_ARGS__)

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

const int INF = 1e8;

void Main() {
  int n, m;
  cin >> n >> m;
  vector<int> x(m);
  rep(i, m) cin >> x[i];
  sort(x.begin(), x.end());
  vector<int> diff(m-1);
  rep(i, m-1) diff[i] = x[i+1] - x[i];
  sort(diff.begin(), diff.end());
  int ans = 0;
  rep(i, m - n) ans += diff[i];
  cout << ans << endl;
}

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


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

using namespace std;

#define int long long

signed main(){

  int N, H;
  int res = 0;
  int ans = 0;
  int ma = 0;
  vector<int> b;

  cin>>N>>H;

  for(int i = 0; i < N; i++){
    int A, B;

    cin>>A>>B;

    b.push_back(B);

    ma = max(A, ma);
  }

  sort(b.begin(), b.end(), greater<int>());

  for(int i = 0; i < N; i++){
    if(H <= 0) break;
    if(b[i] > ma) {
      H -= b[i];
      ans++;
    } else break;
  }

  if(H <= 0) H = 0;

   ans += (H + ma - 1) / ma;


  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 1400
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include <algorithm>
#include<math.h>
#include<set>
#include<map>
#include <sstream>
#include<iomanip>
#include <ctype.h>

//#include<bits/stdc++.h>





using namespace std;
int main() {
	
	int  a, b;
	cin >> a >> b;
	
	int t = 0;
	int ans = 1;
	for (int i = 0; i < a; i++) {
		int x;
		cin >> x;
		t += x;
		if (t <= b)ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
a, b, k = map(int, input().split())

if k <= a:
    a_c = a - k
    b_c = b
else:
    a_c = 0
    k = k-a
    b_c = b-k
    if b_c < 0:
        b_c = 0

print(a_c, b_c)

Measured memory_bytes: 2940
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)

	for scanner.Scan() {
		count := 0
		for i := 9; i >= 0; i-- {
			numCpy, _ := strconv.Atoi(scanner.Text())
			if numCpy-i >= 0 {
				for j := 9; j >= 0; j-- {
					numCpyi := numCpy - i
					if numCpyi-j >= 0 {
						for k := 9; k >= 0; k-- {
							numCpyj := numCpyi - j
							if numCpyj-k >= 0 {
								for l := 9; l >= 0; l-- {
									numCpyk := numCpyj - k
									if numCpyk-l == 0 {
										count++
										break
									}
								}
							}
						}
					}
				}
			}
		}
		fmt.Println(count)
	}

}



Measured memory_bytes: 1056
N = int(input())
L = list(map(int,input().split()))
ans = 0

for i in range(N):
    for j in range(i + 1,N):
        for k in range(j + 1,N):
            if L[i] + L[j] > L[k] and L[j] + L[k] > L[i] and L[k] + L[i] > L[j] and L[i] != L[j] and L[i] != L[k] and L[j] != L[k]: ans += 1

print(ans)


Measured memory_bytes: 68176
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC097A
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int x = Math.Abs(line[1] - line[0]);
            int y = Math.Abs(line[2] - line[1]);
            int d = line[3];
            if (x <= d && y <= d) Console.WriteLine("Yes");
            else if (Math.Abs(line[2] - line[0]) <= d) Console.WriteLine("Yes");
            else Console.WriteLine("No");

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 13268
get_number(Number) :-
    get_string(String),
    number_string(Number, String).

get_number(A, B) :-
    get_number(A),
    get_number(B).

get_number(A, B, C) :-
    get_number(A, B),
    get_number(C).

get_string(String) :-
    current_input(Input),
    read_string(Input, ' \n', '', _, String).

/* memo
    code(int)
    string_code(1, S, C), (C: code)
    char_code(X, Y) (X: char, Y: code)
    string_chars(S, S2) (S: string, S2: [char])
    to_lower(C, C2) (C: char? C2: code?)

    f(0, [], []).
    f(Z, [X|Xs], [Y|Ys]) :- X = Y, f(Z1, Xs, Ys), Z is Z1 + 1.
    f(Z, [_|Xs], [_|Ys]) :- f(Z, Xs, Ys).

    match: =, \=

    numeric: <,=<, >, >= (eval)
    lexicographically: @<. @=<, @>, @>=
    value?: =:=, =\= (eval)
    identical: ==, \==
*/

f(N, A) :- N mod 500 =< A.

main :-
    get_number(N, A),
    f(N, A) -> writeln("Yes") ; writeln("No").


Measured memory_bytes: 8084
L, R = map(int,input().split())

a = 100000000000
for i in range(L,R + 1):
  if a == 0:
    break
  for j in range(i + 1,R + 1):
    if a >= i * j % 2019:
      a = i * j % 2019
      if a == 0:
        break
  

print(a)

Measured memory_bytes: 2940
#include<iostream>

using namespace std;

int main(){
	int d;
	int i, I = 0;

	while(cin >> d){
		for(i=d;i<600;i+=d){
			I += (i * i) * d;
		}
		cout << I << endl;
		I = 0;
	}

	return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define pb push_back
#define maxheap priority_queue<int>
#define minheap priority_queue<int, vector<int>, greater<int> >
const int INF = 1e9+7;
const int MAXN = 3e5 + 200;
const  long double eps = 1e-16;
const long double pi = acos(-1.0);
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

long long h;
void solve(){
    cin >> h;
    long long kol = 1;
    long long ans = 0;
    while (true){
        ans += kol;
        h /= 2;
        if (h == 0) break;
        kol *= 2;
    }
    cout << ans << endl;
}



int main() {
ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
cout.setf(ios::fixed), cout.precision(7);
 //freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
 int step;
 step = 1;
  for (int i = 1; i <= step; i++){
         solve();
    }
}


Measured memory_bytes: 256
S = input()

flag = 0
if S[0] != "A":
    flag = 1
    
count = 0
for i in range(2,len(S)-1):
    if S[i] == "C":
        count += 1
if count != 1:
    flag = 1

count2 = 0
for i in S:
    if i == i.upper():
        count2 += 1
if count2 != 2:
    flag = 1
    
if flag == 0:
    print("AC")
else:
    print("WA")

Measured memory_bytes: 38512
import java.util.*;

public class Main{
  static final char MINUS = 'M';
  static HashSet<Integer> set;

  static boolean isdigit(char ch){
    return '0' <= ch && ch <= '9' || ch == MINUS;
  }

  static String replace(String s){
    int before = s.length();

    while(true){
      for(int i=0;i<s.length();i++){
        if(s.charAt(i) == '('){
          int j = i+1;
          while(isdigit(s.charAt(j)))j++;
          if(s.charAt(j) == ')'){
            s = s.substring(0,i) + s.substring(i+1,j) + s.substring(j+1);
            break;
          }
        }
      }

      if(before == s.length()) return s;
      before = s.length();
    }
  }

  static boolean check(String s){
    for(int i=0;i<s.length();i++){
      if(!isdigit(s.charAt(i))){
        return false;
      }
    }
    return true;
  }

  static int toInt(String s){
    if(s.charAt(0) == MINUS){
      return -1 * Integer.parseInt(s.substring(1));
    }
    else{
      return Integer.parseInt(s);
    }
  }

  static void solve(String s){
    if(check(s)){
      set.add(toInt(s));
      return;
    }

    for(int i=0;i<s.length();i++){
      char op = s.charAt(i);
      if(op != '+' && op != '-' && op != '*' && op != '/') continue;
      if(!isdigit(s.charAt(i-1)) || !isdigit(s.charAt(i+1))) continue;

      int l = i-1;
      int r = i+1;
      while(l>=0 && isdigit(s.charAt(l))) l--;
      while(r<s.length() && isdigit(s.charAt(r))) r++;

      int left = toInt(s.substring(l+1,i));
      int right = toInt(s.substring(i+1,r));
      int cal = 0;

      switch(op){
      case '+': cal = left + right; break;
      case '-': cal = left - right; break;
      case '*': cal = left * right; break;
      case '/':
        if(right == 0) continue;
        cal = left / right;
      }

      String next = "" + Math.abs(cal);
      if(cal < 0) next = MINUS + next;

      solve(replace( s.substring(0,l+1) + next + s.substring(r) ));
    }
  }

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

    while(true){
      String s = sc.next();
      if(s.equals("#")) break;
      set = new HashSet<Integer>();
      solve(replace(s));
      System.out.println(set.size());
    }
  }
}

Measured memory_bytes: 13000
#include <iostream>
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;
 }

}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
#define M 100005
int a[M];
multiset<int>q;
multiset<int>::iterator it;
int main(){
	int n,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i){
		if(!q.size())ans++,q.insert(a[i]);
		else{
			if(*q.begin()>=a[i]){
				q.insert(a[i]);
				ans++;
			}
			else{
				it=q.lower_bound(a[i]);
				it--;q.erase(q.find(*it));
				q.insert(a[i]);
			}
		}
	}
	printf("%d",ans);
}

Measured memory_bytes: 5376
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double, char*, const char*>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
template<typename T> inline void debug(const vector<T> &xs){
#ifdef DEBUG
	pr(xs);
#endif
}

// list all divisors of n. O(sqrt(n))
std::vector<ll> get_divisors(ll n){
	std::vector<ll> div(1, 1);
	for(int i=2; (ll)i*i<=n; i++){
		if(n%i==0) div.push_back(i);
	}
	for(int i=div.size()-1; i>=0; i--){
		if(div[i]*div[i]==n) continue;
		div.push_back(n/div[i]);
	}
	return div;
}

int main(){
	ll N, S;
	cin >> N >> S;
	if(N==S){
		cout << N+1 << endl;
		return 0;
	}
	if(N<S){
		cout << -1 << endl;
		return 0;
	}

	vector<ll> divs = get_divisors(N-S);
	sort(divs.begin(), divs.end());
	ll ans = 1e18;
	for(ll x: divs){
		ll b = x+1;
		ll n = N;
		ll s = 0;
		while(n>0){
			s += n%b;
			n /= b;
		}
		if(s == S){
			ans = min(ans, b);
		}
	}
	if(ans < 1e18) cout << ans << endl;
	else cout << -1 << endl;

	return 0;
}


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

using namespace std;

long long int GCD(long long int a, long long int b) {
    if(a<b) {
        long long int tmp=a;
        a=b;
        b=tmp;
    }
    
    if(b==0) {
        return a;
    }
    
    return GCD(b, a%b);
}

int main() {
    long long int N, M;
    cin >> N >> M;
    string S, T;
    cin >> S >> T;
    
    long long int gcd=GCD(N, M);
    long long int ans=N/gcd*M;
    for(long long int i=0; i<gcd; i++) {
        if(S[N/gcd*i]!=T[M/gcd*i]) {
            ans = -1;
            break;
        }
    }
    
    cout << ans << endl;


    return 0;
    
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 3005;
string s, t;

int dp[maxn][maxn];
int f(int i, int j) {
    if (i == s.size() || j == t.size()) return 0;
    if (dp[i][j] != -1) return dp[i][j];
    dp[i][j] = max(dp[i][j],max(f(i+1,j),f(i,j+1)));
    if (s[i] == t[j]) dp[i][j] = max(dp[i][j],1+f(i+1,j+1));
    return dp[i][j];
}

void retrieve(int i, int j) {
    if (i == s.size() || j == t.size()) return;
    if (dp[i][j] == 0) return;
    if (dp[i+1][j] == dp[i][j]) {
        retrieve(i+1,j);
        return;
    }   
    if (dp[i][j+1] == dp[i][j]) {
        retrieve(i,j+1);
        return;
    }
    cout << s[i];
    retrieve(i+1,j+1);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> s >> t;
    memset(dp,-1,sizeof dp);
    f(0,0);
    /*
    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < t.size(); j++) {
            cout << f(i,j) << ' ';
        }
        cout << '\n';
    }
    */
    retrieve(0,0);
    cout << '\n';

    return 0;
}



Measured memory_bytes: 35968
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let a = read_vec::<i64>();
    if *a.iter().min().unwrap() >= 0 || *a.iter().max().unwrap() <= 0 {
        let mut min_idx = 0;
        let mut min_elem = std::i64::MAX;
        for i in 0..n {
            if a[i].abs() < min_elem {
                min_idx = i;
                min_elem = a[i].abs();
            }
        }

        println!(
            "{}",
            a.iter().map(|x| x.abs()).sum::<i64>() - min_elem.abs() * 2
        );
        debug!(min_elem);

        let mut cur = a[min_idx];
        for i in 0..n - 1 {
            if i == min_idx {
                continue;
            }
            println!("{} {}", cur, a[i]);
            cur -= a[i];
        }
        if *a.iter().min().unwrap() >= 0 {
            println!("{} {}", a[n - 1], cur);
        } else {
            println!("{} {}", cur, a[n - 1]);
        }
        return;
    }
    // both sign exist.
    let mut plus_idxs = vec![];
    let mut minus_idxs = vec![];
    for i in 0..n {
        if a[i] > 0 {
            plus_idxs.push(i);
        } else {
            minus_idxs.push(i);
        }
    }

    println!("{}", a.iter().map(|x| x.abs()).sum::<i64>());
    // consume plus
    let mut cur1 = a[minus_idxs[0]];
    for i in 1..plus_idxs.len() {
        println!("{} {}", cur1, a[plus_idxs[i]]);
        cur1 -= a[plus_idxs[i]];
    }
    let mut cur2 = a[plus_idxs[0]];
    for i in 1..minus_idxs.len() {
        println!("{} {}", cur2, a[minus_idxs[i]]);
        cur2 -= a[minus_idxs[i]];
    }
    println!("{} {}", cur2, cur1);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 11128
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
int merge(vector<int>&a, int l, int r) {
	int mid = (l + r) / 2;
	int n1 = mid - l, n2 = r - mid;
	vector<int>L(n1 + 1), R(n2 + 1);
	rep(i, 0, n1)L[i] = a[l + i];
	L[n1] = INF;
	rep(i, 0, n2)R[i] = a[mid + i];
	R[n2] = INF;
	int ret(0);
	int i(0), j(0);
	rep(k, l, r) {
		if (L[i] <= R[j])a[k] = L[i++];
		else {
			a[k] = R[j++];
			ret += n1 - i;
		}
	}
	return ret;
}
int mergesort(vector<int>&a, int l, int r) {
	if (r - l > 1) {
		return mergesort(a, l, (l + r) / 2)
			+ mergesort(a, (l + r) / 2, r)
			+ merge(a, l, r);
	}
	return 0;
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> a(N); rep(i, 0, N) { cin >> a[i]; }
	int ans = mergesort(a, 0, N);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5944
#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#define rep(i,s,n)for(int i = s;i<n;i++)
#define repe(i,s,n)for(int i = s;i<=n;i++)
using namespace std;
typedef long long ll;
static const ll MOD = 1e9 + 7;

int main() {
	ll p, q, r; cin >> p >> q >> r;
	cout << min(min(p + q, q + r),(p + r)) << endl;
	return 0;
}

Measured memory_bytes: 256
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def ccc(v, k):
	while v >= k:
		if v % k == 0:
			v = v // k
		else:
			v = v % k
	return v

def cccc(v,k):
	while v >= k:
		if v % k == 0:
			v = v //k
		else:
			v = v-k
	return v


def main_p(n):
	s = n#int(input())
	#b , c = tin()
	#s = input()
	if s == 2:
		return 1
	elif s == 3:
		return 2
	
	ret = 1  #s-1, 1は範囲外なので。
	for i in range(2, s-1):
		if i*i > s+1:
			break
		if (s-1) % i == 0:
			ret += 1 if i*i == s-1 else 2
			
	ret += 1 #s
	for i in range(2, s):
		if i*i > s+1:
			break
			
		if s % i == 0:
			if ccc(s, i) == 1:
				ret += 1
			oi = s // i
			if oi != i and ccc(s, oi) == 1:
				ret += 1
			
	return ret#print(ret)
	
		
def main():
	n = int(input())
	return main_p(n)

def main_g(n):
	ret = 0
	for i in range(2, n+1):
		if cccc(n, i) == 1:
			ret += 1
	return ret


def maint():
	i=2
	p=0
	g=0
	while p == g:
		p=main_p(i)
		g=main_g(i)
		i+=1
		if p==g:
			print('ok', i-1)
	print(i-1,p,g)
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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

long long n, p[5]; string S;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> S;
		if (S[0] == 'M') p[0]++;
		if (S[0] == 'A') p[1]++;
		if (S[0] == 'R') p[2]++;
		if (S[0] == 'C') p[3]++;
		if (S[0] == 'H') p[4]++;
	}
	long long ans = 0;
	for (int i = 0; i < 5; i++) {
		for (int j = i + 1; j < 5; j++) {
			for (int k = j + 1; k < 5; k++) ans += p[i] * p[j] * p[k];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256