akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <set>
#include <map>

using namespace std;

const int maxN = 1000100;
const long long oo = 1000000000000ll;

#define foru(i, l, r) for (int i = l; i <= r; ++i)
#define ford(i, r, l) for (int i = r; i >= l; --i)
#define repu(i, r) for (int i = 0; i < r; ++i)
#define ll long long
#define F first
#define S second
#define mp make_pair
#define pint pair < ll, int >

int s[maxN], f[maxN], n, d, a[maxN], q;

int main() {
    cin >> n >> d;
    foru(i, 1, n) cin >> a[i];
    s[0] = d;
    foru(i, 1, n)
        if (2 * s[i - 1] <= a[i])
            s[i] = s[i - 1];
        else
            s[i] = (s[i - 1] < a[i]) ? a[i] - s[i - 1] : s[i - 1] - a[i];
    f[n] = 1;
    ford(i, n - 1, 1)
        if (a[i + 1] >= 2 * f[i + 1])
            f[i] = f[i + 1];
        else
            f[i] = f[i + 1] + a[i + 1];
    /*foru(i, 1, n) cout << a[i] << " ";
    cout << endl;
    foru(i, 1, n) cout << s[i] << " ";
    cout << endl;
    foru(i, 1, n) cout << f[i] << " ";
    cout << endl;*/
    cin >> q;
    foru(i, 1, q) {
        int x;
        cin >> x;
        if (f[x] <= s[x - 1]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}


Measured memory_bytes: 12032
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>

//using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
template<typename T> void chadd(T& a, T b) { a = a + b; }

namespace {  // 名前なし名前空間
	// gcd, lcm は C++17 でstdに標準入りしたので言語のバージョンに注意
	// 最大公約数
	ll gcd(ll a, ll b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

	// 最小公倍数
	ll lcm(ll a, ll b) {
		return a / gcd(a, b) * b;
	}
}

int main() {

	int n;
	std::cin >> n;

	bool can = false;

	for (int i = 1; i * i <= n; ++i) {
		if (n % i != 0) continue;

		if (i < 10 && n / i < 10) {
			can = true;
			break;
		}
	}

	if (can) std::cout << "Yes" << std::endl;
	else std::cout << "No" << std::endl;


	return 0;
}

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

int main() {
    int N;
    cin >> N;
    bool flag = true;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;

        if (a % 2 == 0) {
            if (a % 3 != 0 && a % 5 != 0) {flag = false; break;}
        }
    }

    if (flag) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
 
int main(){
	int n,y;
	cin>>n>>y;
	y/=1000;
	int a,b,c;
	//9a+4b=t;
	int t=y-n;
		for (int i=0;9*i<=t;i++){
			if ((t-9*i)%4==0){
				c=n-i-(t-9*i)/4;
				if (c>=0)
				{
					cout<<i<<" "<<(t-9*i)/4<<" "<<n-i-(t-9*i)/4;
					return 0;
				}
			}
			
		}
		cout<<"-1 -1 -1";
	
	
}

Measured memory_bytes: 256
n,q = map(int, raw_input().split())
que = [map(str, raw_input().split()) for i in range(n)]
for i in range(n):que[i][1] = int(que[i][1])
mxt = sum([y for x,y in que])
t = 0
i = 0
while t < mxt:
	i %= n
	a,c = que[i][0],que[i][1]
	if c <= q:
		t += c
		que.pop(i)
		n -= 1
		print a,t				
	else:
		t += q
		que[i][1] = c - q
		i += 1

Measured memory_bytes: 14004
//https://atcoder.jp/contests/abc174/tasks/abc174_b
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin>>n;
	double d;
	cin>>d;
	ll cnt=0;
	
	ll i;
	for(i=1;i<=n;i++)
	{
		double ans;
		double p1;
		cin>>p1;
		double p2;
		cin>>p2;
		ans=sqrt((p1*p1)+(p2*p2));
		if(ans<=d)
		{
			cnt=cnt+1;
		}
		else
		{
			cnt=cnt;
		}
	}
	cout<<cnt<<"\n";
	return 0;
}

Measured memory_bytes: 3744
U = input()
S = [0]*len(U)
T = [0]*len(U)
for k in range(len(U)):
    if U[k] == "S":
        S[k] = 1
    else:
        T[k] = 1

for k in range(1,len(U)):
    S[k] += S[k-1]
    T[k] += T[k-1]
ans = 0
for k in range(len(U)):
    ans = max(ans,2*(T[k]-S[k]))
print(ans)


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

struct Benri {
    Benri() {
        std::cin.tie(0); ios::sync_with_stdio(false);
        cout << fixed << setprecision(12);
    }
} benri;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vll = vector<long long>;
using pll = pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define MOD 1000000007
#define MOD2 998244353

typedef complex<double> P;
namespace std {
bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
}
}

int main() {
    int N; cin >> N;
    vector<pair<double, P>> AP(N); // arg, point
    rep(i, N) {
        double x, y; cin >> x >> y;
        AP[i].S = P(x, y);
        AP[i].F = arg(P(x, y));
    }

    sort(all(AP));

    double ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            P tmp(0.0, 0.0);
            for (int k = i ; k <= i + j; k++ ) {
                int l = k % N;
                tmp += AP[l].S;
            }
            
            ans = max(ans, abs(tmp));
        }
    }

    cout << ans << endl;


}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n)-1;(i)>=0;(i)--)
#define all(v) (v).begin(),(v).end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define pb push_back
#define mod 1000000007
#define inf 1000000000
#define llinf 1000000000000000

typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef vector<pint> vpint;



int main(){
    int n;
    cin>>n;
    string str[n];
    rep(i,n)cin>>str[i];

    int count=0;
    int startb=0;
    int enda=0;
    int selfa=0;
    rep(i,n){
        rep(j,str[i].length()-1){
            if(str[i].substr(j,2)=="AB"){
                count++;
            }
        }
        if(str[i].substr(0,1)=="B"){
            startb++;
            if(str[i].substr(str[i].length()-1,1)!="A"){
                selfa=1;
            }
        }
        if(str[i].substr(str[i].length()-1,1)=="A"){
            enda++;
            if(str[i].substr(0,1)!="B"){
                selfa=1;
            }
        }
    }
    int cat;
    cat=min(startb,enda);
    if(cat>=1 && selfa==0)cat--;
    count+=min(n-1,cat);
    cout<<count<<endl;

}

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

namespace IO {
    template <typename Tp> inline Tp input() {
        Tp x = 0, y = 1;
        char c = getchar();
        while ((c < '0' || '9' < c) && c != EOF) {
            if (c == '-')
                y = -1;
            c = getchar();
        }
        if (c == EOF)
            return 0;
        while ('0' <= c && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x *= y;
    }
    template <typename Tp> inline void read(Tp &x) { x = input<Tp>(); }
}; // namespace IO
using namespace IO;

namespace modular {
    const int MOD = 1000000007;
    inline int add(int x, int y) { return (x += y) >= MOD ? x -= MOD : x; }
    inline void inc(int &x, int y) { (x += y) >= MOD ? x -= MOD : 0; }
    inline int mul(int x, int y) { return 1LL * x * y % MOD; }
    inline int qpow(int x, int y) {
        int ans = 1;
        for (; y; y >>= 1, x = mul(x, x))
            if (y & 1)
                ans = mul(ans, x);
        return ans;
    }
}; // namespace modular

#define reg register
#define FIN(s) freopen(s, "r", stdin)
#define FOUT(s) freopen(s, "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define lep(i, l, r) for (int i = l; i < r; ++i)
#define irep(i, r, l) for (int i = r; i >= l; --i)
#define ilep(i, r, l) for (int i = r; i > l; --i)
typedef long long ll;

int L, top;
struct edge {
    int u, v, w;
} e[107];

void add(int u, int v, int w) { e[++top] = (edge){u, v, w}; }

void solve() {
    int S = 1, T = 0, x = 0, y = 0;
    while ((1 << x + 1) - 1 <= L)
        x++;
    T = x + 1;
    lep(i, 1, T) add(i, i + 1, 0);
    lep(i, 1, T) add(i, i + 1, 1 << i - 1);
    int k = L - (1 << x) + 1, now = (1 << x);
    while (now <= L) {
        irep(i, 22, 0) if ((1 << i) <= k) {
            y = i;
            break;
        }
        k -= (1 << y);
        add(y + 1, T, now);
        now += (1 << y);
    }
    printf("%d %d\n", T, top);
    rep(i, 1, top) printf("%d %d %d\n", e[i].u, e[i].v, e[i].w);
}

int main() {
#ifdef LOCAL
    FIN("in");
#endif
    read(L);
    L--;
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>

using namespace std;

int di[4][2] = {{0,1},{-1,0},{0,-1},{1,0}};

int main(void){

  int h,w;

  cin>>h;
  cin>>w;

  char paper[h][w];

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin >> paper[i][j];
    }
  }

  int all=1;
  
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(paper[i][j] != '.'){
	all=0;
	break;
      }
    }
    if(all==0) break;
  }

  if(all==1){
    cout << "Yes" << endl;
    return 0;
  }

  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      //cout << paper[i][j] << endl;
      if(paper[i][j] == '#'){

	if(j+1 < w){
	  if(paper[i][j+1] != '.') continue;
	}
	if(i-1 >= 0){
	  if(paper[i-1][j] != '.') continue;
	}
	if(j-1 >= 0){
	  if(paper[i][j-1] != '.') continue;
	}
	if(i+1 < h){
	  if(paper[i+1][j] != '.') continue;
	  else{
	    cout << "No" << endl;
	    return 0;
	  }	  
	}
	else{
	  cout << "No" << endl;
	  return 0;
	}
	
      }
    }
  }

  cout << "Yes" << endl;
  
  return 0;
}



Measured memory_bytes: 256
import java.io.*;
  
public class Main {
  public static void main(String[] args) {
    try {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String r = br.readLine();
      String[] in = r.split(" ");
      int x = Integer.parseInt(in[0]);
      int y = Integer.parseInt(in[1]);
      System.out.print(x * y);
      System.out.print(" ");
      System.out.println((x + y) * 2);
    } catch(IOException e) {
      System.out.println(e);
    }
  }
}

Measured memory_bytes: 24116
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace _001_FindingMissingCards
{
    /*
     */

    class Program
    {
        static void Main()
        {
            string line1st = Console.ReadLine();
            char[] cs = line1st.ToCharArray();
            for (int i = 0; i < cs.Length; i++)
            {
                if (char.IsUpper(cs[i]))
                {
                    cs[i] = char.ToLower(cs[i]);
                }
                else if (char.IsLower(cs[i]))
                {
                    cs[i] = char.ToUpper(cs[i]);
                }
            }
            string soutput = new string(cs);
            Console.WriteLine(soutput);


            
        }
    }
}

Measured memory_bytes: 9220
#include <iostream>

int main() {
  int A, B, C;
  std::cin >> A >> B >> C;
  
  bool T = false;
  if ((A == B) && (A != C)) {T = true;}
  if ((A == C) && (A != B)) {T = true;}
  if ((B == C) && (B != A)) {T = true;}
  
  if (T) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
}

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

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define mem(x,val) memset((x),(val),sizeof(x))
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define PI acos(-1.0) 
#define N 111111

const int INF = 1 << 30 ;
typedef long long ll ;
typedef pair < int , int > pii ;

bool a[200] ;

int main() {
  int n, m, x, temp, cost1 = 0, cost2 = 0 ;
  cin >> n >> m >> x ;

  for(int i = 0 ;i<m ;i++){
    cin >> temp ;
    a[temp] =true ;
  }

  for(int i = x ;i<=n ;i++)
    if(a[i])cost1++ ;
  for(int i = x ;i>=0 ; i--)
    if(a[i])cost2++ ;

  cout << min(cost1, cost2) << endl ;

  return 0 ;
}

Measured memory_bytes: 256
function main(input){
  var num;
  var inputNK;
  var inputH;
  var inputN;
  var inputK;
  input = input.split('\n');
  inputNK = input[0].split(' ');
  inputH =  input[1].split(' ');
  inputN = parseInt(inputNK[0]);
  inputK = parseInt(inputNK[1]);
  num = 0;
  for(var i=0 ; i<inputN; i++){
    if(parseInt(inputH[i]) >= inputK){
      num++;
    }
  }
  console.log(num);
}

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

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

#define CAPA 500001
#define MID  200000 

void inputAndCalc();
	void checkAndSet();
		void addChar();
void output();

char s[CAPA],				//head - 200K, tailMax + 200K
	 c;
char *pa = &s[MID], *pb;	//points head or tail of s
int  q, t, f;
bool bReverse = false, bHead = true;

int main() {
	inputAndCalc();
	output();
	return 0;
}

void inputAndCalc() {
	scanf("%s", pa);				//put head in the middle
	pb = &pa[strlen(pa) - 1];		//needs -1 to point tail
	scanf("%d", &q);
	checkAndSet();					//check queries and get ans
	return;
}

void checkAndSet() {
	for (int i = 0; i < q; i++) {
		scanf("%d", &t);
		if (t == 1)
			bReverse = !bReverse;	//changes flag
		else {
			scanf("%d %c", &f, &c);
			bHead = f % 2;			// 1 -> head, 2 -> tail
			addChar();				//add char to s
		}
	}
}

void addChar() {
	if (!(!bReverse ^ bHead))		//tip: draw Venn diagram
		*(--pa) = c;				//move -> sustitute
	else
		*(++pb) = c;				//mo(ry
	return;
}

void output() {
	if (!bReverse)
		puts(pa);
	else
		while (pb >= pa) {
			putchar(*pb--);			//put -> move
		}
	putchar('\n');
	return;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

int main() {
	int a, b, t, ans = 0, x = 0;
	cin >> a >> b >> t;
	x = a;
	while(x <= t) {
		ans += b;
		x += a;
	}
	cout << ans << "\n";
	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;
using P = pair<int, int>;
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

string s;
int k;
set<string>st;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>s>>k;
    int n=s.size();
    rep(i,n)for(int j=i+1;j<=n;j++){
        if(j-i<=k)st.insert(s.substr(i,j-i));
        if(st.size()>k)st.erase(--st.end());
    }
    cout<<*prev(st.end())<<endl;
    return 0;
}

Measured memory_bytes: 256
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[8][2] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}, {1, 1}, {1, -1}, { -1, -1}, { -1, 1}};
const int mod = 1e9 + 7, gakki = 5 + 2 + 1 + 19880611 + 1e9;
const int MAXN = 2e5 + 5, MAXM = 2e5 + 5, N = 2e5 + 5;
const int MAXQ = 100010;
/*int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], tot = 1;
inline void addedge(int u, int v)
{
        to[++tot] = v;
        nxt[tot] = Head[u];
        Head[u] = tot;
}*/
inline void read(int &v)
{
        v = 0;
        char c = 0;
        int p = 1;
        while (c < '0' || c > '9')
        {
                if (c == '-')
                {
                        p = -1;
                }
                c = getchar();
        }
        while (c >= '0' && c <= '9')
        {
                v = (v << 3) + (v << 1) + c - '0';
                c = getchar();
        }
        v *= p;
}
int num[100005];
int main()
{
        int n;
        int k;
        int minn = INT_MAX;
        int aim;
        read(n), read(k);
        for (int i = 1; i <= n; i++)
        {
                read(num[i]);
                if (num[i] < minn)
                {
                        minn = num[i];
                        aim = i;
                }
        }
        int ans = 0;
        ans = INT_MAX;
        int anser = 0;
        for (int laim = max(1, aim - k + 1); laim <= aim; laim++)
        {
                int raim = min(n, laim + k - 1);
                anser = 1;
                if ((laim - 1) % (k - 1))
                {
                        anser++;
                }
                anser += (laim - 1) / (k - 1);
                if ((n - raim) % (k - 1))
                {
                        anser++;
                }
                anser += (n - raim) / (k - 1);
                ans = min(ans, anser);
        }
        cout << ans << endl;
        return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,k;
    cin >> n >> k;
    long long a[n];
    long long suma = 0LL;
    for(int i = 0;i<n;i++){
        cin >> a[i];
    }
    sort(a,a+n);
    if(n>k){
        for(int i = 0;i<(n-k);i++){
            suma += a[i];
        }
    }
    cout << suma;
}

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


int main (){
    int N;
    cin>>N;
    vector<int> Vec(N);
    for(int i=0; i<N; i++){
        cin>>Vec.at(i);
    }
    int count=0;
    for(int i=0; i<N-2; i++){
        if((Vec.at(i+1)-Vec.at(i))*(Vec.at(i+1)-Vec.at(i+2))<0){
            count ++;
        }
    }
    cout<<count<<endl;
   
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
 
int main() {
    fast_io;
 
    int n;
    cin >> n;
 
    cout << ((n + 999) / 1000) * 1000 - n << "\n";
}

Measured memory_bytes: 3608
import java.awt.geom.Point2D;
import java.util.*;

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

	public Main() {
		AOJ1175 obj = new AOJ1175();
		while(true){
			int n = in.nextInt();
			if(n==0)break;
			obj.doIt(n);
		}
	}

	class AOJ1175{
		boolean[] memo = new boolean[(1<<24)];
		void doIt(int n){
			Arrays.fill(memo,false);
			Data[] data = new Data[n];
			for(int i=0;i<n;i++)data[i] = new Data(in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt());
			long bit = 0;
			for(int i=0;i<n;i++)bit += 1 << i;
			LinkedList<State> q = new LinkedList<State>();
			q.add(new State(bit, 0));
			int cnt[] = new int[n];
			
			int result = -1;
			while(q.size()>0){
				State now = q.remove();
				bit = now.bit;
				result = Math.max(result, now.num);
				Arrays.fill(cnt,0);
				for(int i=0;i<n;i++)for(int s=i-1;s>=0;s--)if((bit>>i)%2==1&&(bit>>s)%2==1){
					if(Point2D.distance(data[i].x, data[i].y, data[s].x, data[s].y)<data[s].r+data[i].r)cnt[i]++;
				}

				for(int i=0;i<n;i++)for(int s=i+1;s<n;s++)if(data[i].color==data[s].color&&cnt[i]==0&&cnt[s]==0){
					if(i==s||((bit>>i)%2==0)||((bit>>s)%2==0))continue;
					long bit2 = bit-(1<<i)-(1<<s);
					if(memo[(int)bit2])continue;
					memo[(int)bit2] = true;
					q.add(new State(bit2,now.num+2));
				}

			}
			System.out.println(result);
		}

		class State{
			long bit;
			int num;
			public State(long bit,int num){
				this.bit = bit;
				this.num = num;
			}
		}

		class Data{
			int x,y,color,r;
			public Data(int x,int y,int r,int color) {
				this.x = x;
				this.y = y;
				this.r = r;
				this.color = color;
			}
		}
	}
}

Measured memory_bytes: 103868
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	
	
	public static int LCS(String x, String y) {
		int[][] table = new int[x.length()+1][y.length()+1];
		
		for (int i = 1; i < x.length()+1; i++) {
			for(int j = 1; j < y.length()+1; j++) {
				if(x.charAt(i-1) != y.charAt(j-1)) {
					table[i][j] = Math.max(table[i-1][j],table[i][j-1]);
				} else {
					table[i][j] = 1+table[i-1][j-1];
				}
			}

		}
		return table[x.length()][y.length()];
	}
	public static void main(String args[]) {
		Scanner k = new Scanner(System.in);
		int n = k.nextInt();
		for(int x = 0; x < n; x++) {
			String s1 = k.next();
			String s2 = k.next();
			System.out.println(LCS(s1,s2));
		}
		
	}
}



Measured memory_bytes: 65060
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] tmpStr = br.readLine().split(" ");
		
		int a = Integer.parseInt(tmpStr[0]);
		int b = Integer.parseInt(tmpStr[1]);

		if(a % 3 == 0 || b % 3 == 0 || (a+b) % 3 == 0){
			System.out.println("Possible");
		}
		else {
			System.out.println("Impossible");
		}
	}

}


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

int cnt[26];

void ext(){ cout <<"No" << endl; exit(0);}

int main(){
  int H,W; cin >> H >> W;
  
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      char a; cin >> a;cnt[a-'a']++;
    }
  }
  
  int mp1 = (H%2)*(W%2);
  
  int mp2 = 0;
  if( H%2 ){ mp2 += (W/2);}
  if( W%2 ){ mp2 += (H/2);}
  
  int mp4 = H*W-mp1-mp2;
  
  
  if( mp1){ 
   for(int i = 0; i < 26; i++){
     if( cnt[i] % 2){ cnt[i]--; break;}
   }
  }
  
  for(int i = 0; i < 26; i++){
    if( cnt[i] % 2 ){ ext();}
  }// 1mod4の判定
  
    int res = 0;
    for(int i = 0; i < 26; i++){
      if( cnt[i] % 4 == 2){ res++;}
    }
  
 
    if( res > mp2){ ext();} //2mod4の判定
  
  
  cout << "Yes" << endl;
  
  return 0;
}
    
    

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

int main(){
    int K;
    long long int i;
    int count;
    long long int mod;
    queue<long long int> q;
    cin >>K;
    for(i=1;i<10;i++)q.push(i);
    for(count=0;count<K-1;count++){
        i=q.front();
        mod=i%10;
        q.pop();
        if(mod!=0)q.push(i*10+mod-1);
        q.push(i*10+mod);
        if(mod!=9)q.push(i*10+mod+1);
    }
    i=q.front();
    cout << i << endl;
}

Measured memory_bytes: 1792
function Main(input) {
    input = input.trim()
  input = input.split("\n");
  var A = input[0].split("");
  var B = input[1].split("");
  var sum = 0;
  if(A[0]==B[0]) sum++;
  if(A[1]==B[1]) sum++;
  if(A[2]==B[2]) sum++;
  console.log(sum)
}Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7372
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <ctype.h>
#include <algorithm>
#include <cmath>
#include <vector>

#define REP(i, n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define square(x) (x) * (x)

const int INF = 1e9;

using namespace std;

int main() {
    int x, y;
    ostringstream os;
    while(1) {
        string op;
        cin >> x >> op >> y;
        if(op == "?")
            break;
        if(op == "+")
            os << x + y << endl;
        if(op == "-")
            os << x - y << endl;
        if(op == "*")
            os << x * y << endl;
        if(op == "/")
            os << x / y << endl;
    }
    cout << os.str();
}

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

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define EXIST(m,v) (m).find((v)) != (m).end()
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

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

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI  = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL<<60;
constexpr long long MOD = 1000000007; // 998244353;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

void Main(){
    int a, b, c;
    cin >> a >> b >> c;
    int k;
    cin >> k;
    int ans = 0;
    while (a >= b) {
        b *= 2;
        ans++;
    }
    while (b >= c) {
        c *= 2;
        ans++;
    }
    if (ans <= k) {
        cout << "Yes" << en;
    } else {
        cout << "No" << en;
    }
}

int main(void){
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15);
    int t=1; //cin>>t;
    REP(_,t) Main();
    return 0;
}


Measured memory_bytes: 3700
/*2019/10/19 */
/*template*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define MOD 1000000007
#define MIN 999999999
#define MAX -999999999
typedef long long int ll;
typedef unsigned long long int ull;
void llswap(ll *x,ll *y){ll tmp;tmp=*x;*x=*y;*y=tmp;}
void swap(int *x,int *y){int tmp;tmp=*x;*x=*y;*y=tmp;}
int rmax(int x,int y){return x>y?x:y;}
int rmin(int x,int y){return x>y?y:x;}
ll llrmax(ll x,ll y){return x>y?x:y;}
ll llrmin(ll x,ll y){return x>y?y:x;}
int asc(const void *a,const void *b){if(*(int*)a < *(int*)b)return -1;else if(*(int*)a == *(int*)b)return 0;else return 1;}
int desc(const void *a,const void *b){if(*(int*)a < *(int*)b)return 1;else if(*(int*)a == *(int*)b)return 0;else return -1;}
int llasc(const void *a,const void *b){if(*(ll*)a < *(ll*)b)return -1;else if(*(ll*)a == *(ll*)b)return 0;else return 1;}
int lldesc(const void *a,const void *b){if(*(ll*)a < *(ll*)b)return 1;else if(*(ll*)a == *(ll*)b)return 0;else return -1;}
int gcd(int x,int y){if(y==0)return x;return gcd(y,x%y);}
 
//int asc_t(const void *a,const void *b){if(((pair_t*)a)->d < ((pair_t*)b)->d)return -1;else if(((pair_t*)a)->d == ((pair_t*)b)->d)return 0;else return 1;}
//int asc_t(const void *a,const void *b){if(((pair_t*)a)->d < ((pair_t*)b)->d)return 1;else if(((pair_t*)a)->d == ((pair_t*)b)->d)return 0;else return -1;}
int main(){
    int n,l[2000];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&l[i]);
    }
    int ans=0;
    qsort(l,n,sizeof(int),asc);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                if(l[i]<l[j]+l[k]&&l[j]<l[i]+l[k]&&l[k]<l[i]+l[j]){
                    ans++;
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
  ll n;
  cin>>n;
  ll i,j,d[n],ans = 0;
  for(i=0;i<n;i++)
  {
    cin>>d[i];
  }
  for(i=0;i<n;i++)
  {
    for(j=i+1;j<n;j++)
    {
      ans+=(d[i]*d[j]);
    }
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e5+100;
int main()
{
    ll n;
    char s[N];
    while(~scanf("%lld",&n))
    {
        scanf("%s",s+1);
        int ans= 0;
        for(int i=1;i<=n;i++)
            if(s[i]!=s[i-1])
              ans++;
        printf("%d\n",ans);
    }
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  ll ans=0;
  for(int i=1;i<=n;++i){
    ll m=n/i;
    ans += m*(1+m)/2*i;
  }
  printf("%lld",ans);
  return 0;
}


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

using namespace std;

typedef long long ll;

template<typename T>
void _dump(const char* s, T&& head)
{
  cerr << s << "=" << head << endl;
}

template<typename T, typename... Args>
void _dump(const char* s, T&& head, Args&&... tail)
{
  while (*s != ',')
    cerr << *s++;
  cerr << "=" << head << ",";
  _dump(s + 1, tail...);
}

template<typename T>
void _dumpv(const char* s, T&& v)
{
  cerr << *s << "=";
  for (auto it = v.begin(); it != v.end(); it++) {
    cerr << *it << " ";
  }
  cerr << endl;
}

#define dump(...) _dump(#__VA_ARGS__, __VA_ARGS__)
#define dumpv(...) _dumpv(#__VA_ARGS__, __VA_ARGS__)

const ll MOD = 1000000007;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  // freopen("template.1", "r", stdin);

  int N;
  cin >> N;
  double ans;
  ans = 0;
  for (int i = 0; i < N; i++) {
    double x;
    string u;
    cin >> x >> u;
    if (u == "JPY") {
      ans += (double)x;
    } else {
      ans += (double)x * 380000.0;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
H,W,K = map(int,input().split())
s=[list(input()) for i in range(H)]
area=[[0 for _ in range(W)] for _ in range(H)]

st_num=[0]*H
st_pos=[[] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if s[i][j]=="#":
            st_num[i] += 1
            st_pos[i].append(j)

#print(st_num)
#print(st_pos)

upper=0
cnt=0
for i in range(H):
    if st_num[i]==0:
        upper=min(upper,i)
    else:
        #print("{}行目処理".format(i))
        cnt+=1
        
        #左の余白
        if st_pos[i][0]>0:
            for p in range(upper,i+1):
                for q in range(st_pos[i][0]):
                    area[p][q]=cnt
        #左端のいちごから右端のいちごまで
        for j in range(st_num[i]-1):
            for p in range(upper,i+1):
                for q in range(st_pos[i][j],st_pos[i][j+1]):
                    area[p][q]=cnt
            cnt+=1
        #右端のいちごから右
        for p in range(upper,i+1):
            for q in range(st_pos[i][-1],W):
                area[p][q]=cnt                    
        upper = i+1
        
if upper!=H:
    for p in range(upper,H):
        for q in range(W):
            area[p][q]=area[upper-1][q]                    
                
for i in area:
    print(*i)

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

#define int long long

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int dp[200000] = {};
  dp[0] = 1;

  int X;
  cin >> X;

  vector<int> v = {100, 101, 102, 103, 104, 105};

  for ( int i = 0; i < 6; i++ ) {
    for ( int j = 0; j < 200000; j++ ) {
      if ( dp[j] && j+v[i] < 200000 ) {
	dp[j+v[i]] = 1;	
      }
    }
  }

  if ( dp[X] ) cout << 1 << endl;
  else cout << 0 << endl;
  
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(ll i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll n, K;
  cin >> n >> K;
  vector<P> p(n);
  rep(i, n) cin >> p[i].first >> p[i].second;
  sort(all(p));
  ll ans = 4e18;
  rep(i, n - K + 1) rep(j, n) rep(k, n) {
    ll x1 = p[i].first;
    ll y1 = p[j].second;
    ll y2 = p[k].second;
    if(y2 < y1) continue;
    ll cnt = 0, x2 = x1;
    rep(a, n) {
      ll x = p[a].first;
      ll y = p[a].second;
      if(x1 <= x && y1 <= y && y <= y2) cnt++;
      if(cnt == K) {
        x2 = x;
        break;
      }
    }
    if(cnt < K) continue;
    ll now = (x2 - x1) * (y2 - y1);
    ans = min(ans, now);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector <long long> tall(n);
    for(int i=0;i<n;i++){
        cin>>tall.at(i);
    }       //入力

    long long result=0;
    for(int i=0;i<n-1;i++){
        if(tall.at(i)>tall.at(i+1)){
            result+=tall.at(i)-tall.at(i+1);
            tall.at(i+1)=tall.at(i);
        }
    }
    cout<<result<<endl;
}

Measured memory_bytes: 4840
#include<stdio.h>
int main()
{
    int n,k,a[100005],i,count=0;
    scanf("%d%d",&n,&k);

    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
     for(i=0; i<=n; i++)
     {
         i=i+k;
         count++;
         if(i==n || i>n)
            break;

         i=i-2;

     }
     printf("%d\n",count);

     return 0;
}


Measured memory_bytes: 512
n = int(input())
g = [[-1 for j in range(n)] for i in range(n)]

for i in range(n):
    a = int(input())
    for _ in range(a):
        x, y = map(int, input().split())
        g[i][x - 1] = y
        
ans = 0
for s in range(2**n):
    ok = True
    k = 0
    for i in range(n):
        if (s >> i & 1) == 1:
            k += 1
            for j in range(n):
                if g[i][j] == -1:
                    continue
                if (s >> j & 1) != g[i][j]:
                    ok = False
    if ok:
        ans = max(ans, k)

print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const int maxx=2e5+10;
typedef long long ll;
ll a[maxx];
int main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);
    ll ans=0;
    for(int i=2;i<=n;i++){
        ans+=a[(i+1)/2];
    }
    cout<<ans;
}


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

using namespace std;

const int MX = 55;

template <typename T> void cmin(T &x, const T &y)
{
	if(y < x) x = y;
}

template <typename T> void cmax(T &x, const T &y)
{
	if(y > x) x = y;
}

template <typename T> void read(T &x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

struct GRAPH
{
	vector<int> v[MX];
	bool e[MX][MX];
	int deg[MX];

	void deleg(int a, int b)
	{
		for(auto i=v[a].begin(); i!=v[a].end(); i++)
			if(*i == b)
			{
				v[a].erase(i);
				break;
			}
		e[a][b] = 0;
		deg[b]--;
	}

	void addeg(int a, int b)
	{
		v[a].push_back(b);
		e[a][b] = 1;
		deg[b]++;
	}

	void init()
	{
		memset(e, 0, sizeof(e));
		memset(deg, 0, sizeof(deg));
		for(int i=0; i<MX; i++) v[i].clear();
	}

	bool no_loop(int n)
	{
		int cnt = 0;
		vector<int> stk;
		for(int i=1; i<=n; i++)
			if(!deg[i])
				stk.push_back(i);
		while(!stk.empty())
		{
			int x = stk.back();
			cnt++;
			stk.pop_back();
			for(auto y : v[x])
				if(!(--deg[y]))
					stk.push_back(y);
		}
		return (cnt==n);
	}
} A, B, C;

int n;

void input()
{
	A.init();
	B.init();
	read(n);
	for(int i=1; i<n; i++)
	{
		int a, b;
		read(a), read(b);
		A.addeg(a, b);
		A.addeg(b, a);
	}
	for(int i=1; i<n; i++)
	{
		int a, b;
		read(a), read(b);
		B.addeg(a, b);
		B.addeg(b, a);
	}
}

bool fxd[MX];
int faa[MX], fab[MX];

void getfa(int x, int f, const GRAPH &g, int *fa)
{
	fa[x] = f;
	for(auto y : g.v[x])
		if(y != f)
			getfa(y, x, g, fa);
}

void dfs(int x, int f)
{
	fxd[x] = 1;
	for(auto y : A.v[x])
	{
		if(y == f) continue;
		if(B.e[x][y]) dfs(y, x);
	}
}

int calc(int root)
{
	memset(fxd, 0, sizeof(fxd));
	getfa(root, 0, A, faa);
	getfa(root, 0, B, fab);
	dfs(root, 0);
	C.init();
	int cnt = 0;
	for(int i=1; i<=n; i++)
	{
		if(!fxd[i]) cnt++;
		if(!fxd[i] && !fxd[faa[i]]) C.addeg(i, faa[i]);
		if(!fxd[i] && !fxd[fab[i]]) C.addeg(fab[i], i);
	}
	if(C.no_loop(n)) return cnt;
	else return n+1;
}

void work()
{
	int ans = n+1;
	for(int i=1; i<=n; i++) cmin(ans, calc(i));
	for(int i=1; i<=n; i++)
		if(A.deg[i] == 1)
			for(int j=1; j<=n; j++)
				if(i != j)
				{
					int f = *A.v[i].begin();
					if(f == j) continue;
					A.deleg(i, f);
					A.deleg(f, i);
					A.addeg(i, j);
					A.addeg(j, i);
					cmin(ans, calc(i)+1);
					A.deleg(i, j);
					A.deleg(j, i);
					A.addeg(i, f);
					A.addeg(f, i);
				}
	if(ans == n+1) puts("-1");
	else printf("%d\n", ans);
}

int main()
{
	int t;
	read(t);
	while(t--)
	{
		input();
		work();
	}
	return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(void) {
	int t, n, m,k=100,kazu=1;

	scanf("%d%d", &n, &m);
	
		for (t = 0; t < k; t++) {
			if (kazu >= m) {
				printf("%d\n", t);
				break;
			}
			else {
				kazu = kazu - 1;
			}
			kazu = kazu + n;
			
		}
	
	return 0;
}

Measured memory_bytes: 256
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars};
#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
	input! {
		mut s: String,
	}

	s.remove(0);
	s.remove(0);
	s.remove(0);
	s.remove(0);
	println!("2018{}", s );
}



Measured memory_bytes: 2128
n=int(input())
lst=[]
for i in range(n):
    w=input()
    if w in lst:
        print("No")
        exit(0)
    elif len(lst)>0:
        if lst[-1][-1]!=w[0]:
            print("No")
            exit(0)
    lst.append(w)
print("Yes")

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

L = {}
R = {}
for i in range(N+1):
    L[i] = []  
    R[i] = []

for i in range(N):
    key = i+1+A[i]
    if key<N+1: L[key].append(i+1)
   
for i in range(N):
    key = i+1-A[i]
    if (key<N+1)and(0<=key): R[key].append(i+1)
    

ans=0
for x in range(N+1):
    ans+=len(L[x])*len(R[x])
print(ans)

Measured memory_bytes: 89908
gets.to_i.times{a,b,c,d,e,f,g,h=gets.split.map &:to_f
i=(b-d)*(e-g)
j=(f-h)*(a-c)
puts ((i-j).abs<=1e-10||(i-j).abs<=1e-10*[i,j].max.abs)?"YES":"NO"}

Measured memory_bytes: 6128
import Control.Applicative

main :: IO ()
main = solve <$> getLine >>= print

solve :: String -> Int
solve s = let ls = length s
              (xs, ys) = splitAt (ls `div` 2) s
              y = head ys
          in sum (zipWith f xs (reverse ys))
             + if odd ls && (y == '(' || y == ')')
               then 1 else 0
  where
    f 'w' 'w' = 0
    f 'i' 'i' = 0
    f '(' ')' = 0
    f ')' '(' = 0
    f _ _ = 1



Measured memory_bytes: 3592
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;




int main(){
  unsigned int N;
  cin >> N;

  string S, T;
  cin >> S;
  cin >> T;
  
  // cout << S << "--" << T << endl;

  for (int i = 0; i < N; ++i) {
    cout << S[i];
    cout << T[i];
  }
  cout << endl;
}


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

typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string>vst;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
#define all(ct) ct.begin() , ct.end()
#define endl "\n"
#define fr(i,a) for(auto i:a)
#define f(i,a,b) for(int i=a;i<b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define in(d,v) d.find(v)!=d.end()
#define mp make_pair
#define size(a) int(a.size())

const ll mod = 1e9 + 7;
const ll inf = ll(1e18);
const double PI = acos(-1);

ll modexp(ll x, ll n, int md) {
    if (n == 0)return 1;
    if (n % 2 == 0)return modexp((x * x) % md, n / 2, md);
    return (x * modexp((x * x) % md, n / 2, md)) % md;
}


int main() {
    fastio;
    // clock_t tm = clock();
    ll n,k,x;
    cin>>n>>k;
    vl pos,neg;
    f(i,0,n){
        cin>>x;
        if(x<0){
            neg.pb(-x);
        }
        else{
            pos.pb(x);
        }
    }
    sort(all(pos),greater<ll>());sort(all(neg),greater<ll>());
    ll ans=1,y=0,np=size(pos),nn=size(neg);x=0;
    if(np+nn==k and nn%2==1){
        f(i,0,nn){
            if(i==0){
                ans=(mod-neg[0])%mod;
            }
            else{
                ans*=neg[i];ans%=mod;
            }
        }
        f(i,0,np){
            ans*=pos[i];ans%=mod;
        }
    }
    else if(np==0 and k%2==1){
        fd(i,nn-1,nn-k){
           if(i==nn-1){
               ans=(mod-neg[nn-1])%mod;
           }
           else{
               ans*=neg[i];ans%=mod;
           }
           //cout<<ans<<endl;
        }
    }
    else {
        if(k%2==1){
            --k;ans*=pos[0];ans%=mod;++x;
        }
        while(k>0){
            if(x<np-1 and y<nn-1){
                if(pos[x]*pos[x+1]>=neg[y]*neg[y+1]){
                    ans*=pos[x];ans%=mod;
                    ans*=pos[x+1];ans%=mod;
                    k-=2;x+=2;
                }
                else{
                    ans*=neg[y];ans%=mod;
                    ans*=neg[y+1];ans%=mod;
                    k-=2;y+=2;
                }
            }
            else if(x<np-1){
                ans*=pos[x];ans%=mod;
                ans*=pos[x+1];ans%=mod;
                k-=2;x+=2;
            }
            else{
                ans*=neg[y];ans%=mod;
                ans*=neg[y+1];ans%=mod;
                k-=2;y+=2;
            }
        }
    }
    cout<<ans<<endl;
    //cout<<((clock()-tm)*1.0)/CLOCKS_PER_SEC<<endl;
}


Measured memory_bytes: 5616
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <string>

using namespace std;

int tmp(int t, int a, int h) {

    return (int)abs(t*1000 - 6*h - a*1000 );
}

int main(int argc, const char * argv[]) {
    
    int n, t, a;
    cin >> n >> t >> a;

    int h;
    cin >> h;
    int min = tmp(t, a, h);
    int index = 1;
    for (int i=1; i < n; i++) {
        cin >> h;
        if (min > tmp(t, a, h)) {
            min = tmp(t, a, h);
            index = i+1;
        }
    }
    
    cout << index << endl;
    return 0;
}

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

template<typename T> T gcd(T a, T b) {
    if(!b) return a;
    return gcd(b, a % b);
}
template<typename T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

template<typename T> void chmin(T& a, T b) { a = (a > b) ? b : a; }
template<typename T> void chmax(T& a, T b) { a = (a < b) ? b : a; }
int in() { int x; scanf("%d", &x); return x; }

using namespace std;

typedef long long Int;
typedef unsigned long long uInt;
typedef unsigned uint;


int A, B;

int main(void) {
    cin >> A >> B;

    if (A <= 0 && B >= 0) {
        cout << "Zero" << endl;
    } else {
        if (A < 0) {
            int cnt = abs(A);
            if (B < 0) {
                cnt -= abs(B) + 1;
            }
            if (cnt % 2 == 0) {
                cout << "Positive" << endl;
            } else {
                cout << "Negative" << endl;
            }
        } else {
            cout << "Positive" << endl;
        }
    }
    return 0;
}






Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        string inpt = Reader.ReadLine();
        string ans = "WA";
        if (Judge(inpt))
        {
            ans = "AC";
        }
        Console.WriteLine(ans);


    }

    private bool Judge(string inpt)
    {
        if (inpt[0] != 'A')
        {
            return false;
        }
        if (inpt.Length < 4)
        {
            return false;
        }

        int cCount = 0;
        for (int i = 2; i <= inpt.Length - 2; i++)
        {
            if (inpt[i] == 'C')
            {
                cCount++;
            }
        }
        if (cCount != 1)
        {
            return false;
        }
        for (int i = 0; i < inpt.Length; i++)
        {
            if (inpt[i] == 'A')
            {
                if (i != 0)
                {
                    return false;
                }
            }
            else if (inpt[i] == 'C')
            {
                if (i < 2 || i > inpt.Length - 2)
                {
                    return false;
                }
            }
            else if (inpt[i] >= 'a' && inpt[i] <= 'z')
            {
                continue;
            }
            else
            {
                return false;
            }
        }
        return true;
    }


    public class Reader
    {
        static StringReader sr;
        public static bool IsDebug = false;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (sr == null)
                {
                    sr = new StringReader(InputText.Trim());
                }
                return sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        private static string InputText = @"
 
 
 
AtCo
 
 
 
";
    }

    public static void Main(string[] args)
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}

Measured memory_bytes: 13140
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<queue>

using namespace std;

int main(){
	int n;
	while(scanf("%d",&n)){
		if(n==0) break;
		int dp[1401][1401]={};
		int max_a=0;
		for(int i=1;i<=n;i++){
			char tp[1001];
			scanf("%s",tp);
			for(int j=1;j<=n;j++){
				if(tp[j-1]=='*')
				dp[i][j]=0;
				else
				dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
				max_a=max(max_a,dp[i][j]);
			}
		}
		printf("%d\n",max_a);
	}
}


Measured memory_bytes: 10896
n, k = map(int, input().split())
mod = 10 ** 9 + 7
max_n = 2050
comb = [[0] * max_n for i in range(max_n)]
for i in range(max_n):
    comb[i][1] = i
    comb[i][i] = 1
    comb[i][0] = 1
for i in range(1, max_n):
    for j in range(1, i):
        comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % mod
for i in range(1, k+1):
    ans = comb[k-1][i-1]
    ans = (ans * comb[n-k+1][i]) % mod
    print(ans)


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

int main(){
	string s1, s2;
	cin >> s1 >> s2;
	for(int i=0; i<3; i++){
		if(s1[i] != s2[2-i]) {
			cout << "NO";
			return 0;
		}
	}
	cout << "YES";
	return 0;
}

Measured memory_bytes: 256
def main():
    a,b,c,d = map(int,input().split())
    A = 1
    while a>0 and c>0:
        if A==1:
            c = c-b
            A=0
        else:
            a = a-d
            A=1
    if A==1:
        print('No')
    else:
        print('Yes')


if __name__ == "__main__":
    main()

Measured memory_bytes: 9188
N, L = map(int, input().split())
taste = sorted([L + i - 1 for i in range(1, N + 1)])

if 0 in taste:
    print(sum(taste))
else:
    if taste[0] > 0:
        print(sum(taste) - taste[0])
    else:
        print(sum(taste) - taste[N - 1])

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(){
    char from,to,cm;
    int num[200];
    fill(num,num+200,0);
    num['A']=1;
    while(cin>>from>>cm>>to){
        swap(num[from],num[to]);
    }
    if(num['A']){
        cout<<"A"<<endl;
    }
    else if(num['B']){
        cout<<"B"<<endl;
    }
    else
        cout<<"C"<<endl;
 
    return 0;
}

Measured memory_bytes: 0
n = gets.to_i
w = gets.split.map(&:to_i)
ws = w.sort
pos = {}
(0...n).each do |i|
  pos[ws[i]] = i
end
min = ws[0]
flag = [true]*n
cost = 0
(0...n).each do |i|
  if flag[i]
    flag[i] = false
    count = 0
    startPos = i
    nextPos = pos[w[i]]
    while nextPos != startPos do
      flag[nextPos] = false
      cost += ws[nextPos]
      count += 1
      nextPos = pos[w[nextPos]]
    end
    if min*count + 2*(min+ws[i]) < ws[i]*count
      cost += min*count + 2*(min+ws[i])
    else
      cost += ws[i]*count
    end
  end
end
printf("%d\n",cost)


Measured memory_bytes: 6956