akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long int lli;
typedef long double ld;
const int oo = 1e9;

int n;
const int nx = 1e5+5;
int ac[nx][3];
int dp[3][nx];
int go(int a, int i)
{
	if(i==n) return 0;
	if(dp[a][i] != -1) return dp[a][i];
	int& ans = dp[a][i];
	if(a==0)
	{
		ans=max(ans, go(1, i+1)+ac[i][0]);
		ans=max(ans, go(2, i+1)+ac[i][0]);
	}
	if(a==1)
	{
		ans=max(ans, go(0, i+1)+ac[i][1]);
		ans=max(ans, go(2, i+1)+ac[i][1]);
	}
	if(a==2)
	{
		ans=max(ans, go(0, i+1)+ac[i][2]);
		ans=max(ans, go(1, i+1)+ac[i][2]);
	}
	
	return ans;
	
}
int main()
{
    cin>>n;
    for(int i=0; i<n; i++) cin>>ac[i][0]>>ac[i][1]>>ac[i][2];
    memset(dp, -1, sizeof dp);
    cout<<max(go(0,0), max(go(1,0),go(2,0)))<<"\n";
}
	

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

void printA(int A[], int N){
    for(int i = 0; i < N - 1; ++i){
        cout << A[i] << " ";
    }
    cout << A[N - 1] << "\n";
}

int bubbleSort(int A[], int N){
    int nSwap = 0;
    bool flg = true;

    for(int i = 0; flg; ++i){
        flg = false;
        for(int j = N - 1; j >= i + 1; --j){
            if(A[j] < A[j - 1]){
                swap<int>(A[j], A[j - 1]);
                ++nSwap;
                flg = true;
            }
        }
    }

    printA(A, N);
    return nSwap;
}

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

    int N;
    int A[100];

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

    cout << bubbleSort(A, N) << "\n";

    return 0;
}


Measured memory_bytes: 3132
//abc152_b.cpp
//Sun Jan 19 20:45:36 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int a,b;
	cin >> a >> b;

	if (a<b){
		for (int i=0;i<b;i++){
			cout << a;
		}
	}else{
		for (int i=0;i<a;i++){
			cout << b;
		}
	}

	printf("\n");
//	printf("%.4f\n",ans);
}

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

#define REP(i, s,  n) for(int i = s;i < (n);i++)
#define VSORT(v) sort(v.begin(), v.end());
#define int64 long long
#define pb(a) push_back(a)
#define REP64(i, s,  n) for(int64 i = s;i < (n);i++)
#define INF 999999999
#define MOD 1000000007
using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> PP;

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

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

//---------------------------------------------------------------
// C_2 と同じテストケースでエラーとなる・・・
//---------------------------------------------------------------

int H, W;
char C[500][500];
int M[500][500];		// 処理済みなら　１
stack<P> S;				// スタック

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

	cin >> H >> W;
	REP(i, 0, H)	cin >> C[i];

	int64 ans = 0;
	REP(i, 0, H)	REP(j, 0, W) {
		S.push( P(i,j) );			// スタートをスタックに積む

		int64 b = 0;
		int64 w = 0;
		while(!S.empty()) {				// スタックが空になるまで（スタートから届く範囲だけ処理する）
			P p = S.top(); S.pop();
			int ii = p.first;
			int jj = p.second;
			if(M[ii][jj] != 0)	continue;
			M[ii][jj] = 1;				// 処理済みとする
			if(C[ii][jj] == '#')	b++;
			else					w++;

										// 処理していなければ、スタックに積む
			if(ii > 0     && C[ii][jj] != C[ii-1][jj])	S.push( P(ii-1, jj) );
			if(ii < H - 1 && C[ii][jj] != C[ii+1][jj])	S.push( P(ii+1, jj) );
			if(jj > 0     && C[ii][jj] != C[ii][jj-1])	S.push( P(ii, jj-1) );
			if(jj < W - 1 && C[ii][jj] != C[ii][jj+1])	S.push( P(ii, jj+1) );
		}
		ans += b * w;
	}
	
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 4480
X,Y = map(int,input().split())
p = (4*X-Y)/2
q = (Y-2*X)/2
result = 'No'
if (4*X-Y)%2==0 and (Y-2*X)%2==0:
	if p>=0 and q>=0:
		if not(p==0 and q==0):
			result ='Yes'
print(result)

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n;
string s[100];

int main() {
	cin >> n;
	inc(i, n) { cin >> s[i]; }
	
	bool ans = true;
	inc(i, n) {
	inc(j, i) {
		if(s[i] == s[j]) { ans = false; }
	}
	}
	inc(i, n - 1) { if(s[i].back() != s[i + 1].front()) { ans = false; } }
	
	cout << (ans ? "Yes" : "No") << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define MOD (int)(1e9+7)
#define ceil(x, y) (x%y==0? (x/y) : (x/y+1))
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define FOR1(i, N) for(int i = 1; i <= N; ++i)
#define vi vector <int>
#define pii pair <int, int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mset(a, v) memset(a, v, sizeof(a))
#define all(v) (v).begin(), (v).end()
#define INF 2e9
#define EPS 1e-9
#define int long long
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef cc_hash_table<int, int, hash<int>> ht; // while using, comment #define int long long  */

void __print(int x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif
using namespace std;
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("in6.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    int T=1;
    // cin >> T;
    
    FOR1(tt, T){
        // cout << "Case #" << tt << ": ";
        vector<int> plus, minus;

        int n; cin >> n;
        FOR1(i, n){
            int x, y;
            cin >> x >> y;
            plus.pb(x+y);
            minus.pb(x-y);
        }
        sort(all(plus));
        sort(all(minus));
        cout << max(plus[n-1] - plus[0], minus[n-1] - minus[0]);
        cout << '\n';
    }
    return 0;
}


Measured memory_bytes: 6672
N,M=map(int,input().split())
A=sorted(list(map(int,input().split())))
BC=[list(map(int,input().split())) for i in range(M)]
BC=sorted(BC,key=lambda x:x[1],reverse=True)
sumA=sum([i for i in A if i>=BC[0][1]])
A=[i for i in A if i<BC[0][1]]
idx=0
BCidx=0
lenA=len(A)
lenBC=len(BC)
while idx<lenA and BCidx<lenBC:
    if BC[BCidx][0]:
        if BC[BCidx][1]>A[idx] :
            A[idx]=BC[BCidx][1]
            idx+=1
            BC[BCidx][0]-=1
        else:
            idx+=1
    else:
        BCidx+=1
print(sumA+sum(A))


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

t_zero = [-1] * N

t = 0
a = 1

while t_zero[a-1] == -1:
  if t == K:
    break
  t_zero[a-1] = t
  t += 1
  a = A[a-1]
else:
  k = (K - t_zero[a-1]) % (t - t_zero[a-1])
  a = t_zero.index(t_zero[a-1] + k) + 1
print(a)

Measured memory_bytes: 32356
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  ll n;
  cin >> n;
  cout << n*(n-1)/2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a, b, c;

	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);

	if (a < b && b < c) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 580
#include <iostream>

using namespace std;

int main() {
  int n; cin >> n;
  int max = 0;
  int sum = 0;

  for (int i = 0; i < n; ++i) {
    int p; cin >> p;
    if (p > max) max = p;
    sum += p;
  }

  sum -= max / 2;

  cout << sum << endl;

  return 0;
}

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

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;
const ll mod = 1e9 + 7;

ll a[N];
ll fact[N];
int n, k;

ll bigmod(ll p, ll q) {
  ll res = 1ll;
  while(q) {
    if(q & 1ll) {
      res = (res * p) % mod;
    }
    q >>= 1;
    p = (p * p) % mod;
  }
  return res;
}


ll inverse(ll p) {
  return bigmod(p, mod - 2);
}

ll combi(ll n, ll r) {
  if(n < 0 or r < 0 or r > n) return 0;
  ll u = fact[n];
  ll v = (fact[r] * fact[n - r]) % mod;
  return (u * inverse(v)) % mod;
}


int main() {
  fact[0] = 1;
  for(int i = 1; i < N; i++) {
    fact[i] = (fact[i - 1] * i) % mod;
  }
  cin >> n >> k;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n);
  ll mx_sum = 0;
  for(int i = k; i <= n; i++) {
    mx_sum = (mx_sum + a[i] * 1LL * combi(i - 1, k - 1) % mod) % mod;
  }
  ll mn_sum = 0;
  for(int i = 1; i <= n - k + 1; i++) {
    mn_sum = (mn_sum + a[i] * 1LL * combi(n - i, k - 1) % mod) % mod;
  }
  cout << (mx_sum - mn_sum + mod) % mod << '\n';
}


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

struct Doll{
  int h,r;
  Doll(int a,int b){h=a;r=b;};
};

int n;
int h,r;
int m;
vector<Doll>doll;
int memo[201]={0};

bool comp(Doll a, Doll b){return a.h<b.h && a.r<b.r;};

int rec(int id)
{
  if(memo[id]!=0)return memo[id];

  int ans=0;
  for(int i=0;i<n+m;i++){
    if(comp(doll[i],doll[id]))ans=max(rec(i)+1,ans);
  }

  return memo[id]=ans;
}

int main()
{
  while(cin>>n,n){
    doll.clear();
    for(int i=0;i<200;i++)memo[i]=0;

    for(int i=0;i<n;i++){
      cin>>h>>r;
      doll.push_back(Doll(h,r));
    }
    cin>>m;
    for(int i=0;i<m;i++){
      cin>>h>>r;
      doll.push_back(Doll(h,r));
    }

    doll.push_back(Doll(1001,1001));

    cout<<rec(n+m)<<endl;
  }
}

Measured memory_bytes: 0
import java.util.*;
import java.util.stream.*;

public class Main {
    static Scanner scan = new Scanner(System.in);

    public static void main(String[] args) {
        List<Integer> NMC = numbers();
        List<Integer> B = numbers();

        int count = 0;
        for(int n=0; n<NMC.get(0); n++) {
            List<Integer> A = numbers();
            int sum = 0;
            for(int m=0; m<NMC.get(1); m++) {
                sum += A.get(m) * B.get(m);
            }
            sum += NMC.get(2);
            if(sum > 0) {
                count++;
            }
        }

        print(count);
    }

    public static List<Integer> numbers() {
        List<Integer> integers = new ArrayList<>();
        for(String item: getLine().split(" ")) {
            integers.add(toInt(item));
        }
        return integers;
    }

    public static void add(int[][] a, int[] n, int[] m) {
        for(int i = 0; i < n.length; i++) {

        }
    }

    public static int sum(int[][] a, int[] n, int[] m) {
        int sum = 0;
        for(int i=0; i<n.length; i++) {
            for(int j=0; j<m.length; j++) {
                if(n[i] == 1 && m[j] == 1) {
                    sum += a[i][j];
                }
            }
        }

        return sum;
    }

    public static int getInt() {
        return scan.nextInt();
    }

    public static String getLine() {
        return scan.nextLine();
    }

    public static int toInt(String str) {
        return Integer.parseInt(str);
    }

    public static long toLong(String str) {
        return Long.parseLong(str);
    }

    public static void print(String str) {
        System.out.println(str);
    }

    public static void print(int num) {
        print("" + num);
    }
}


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

int main(){
    int N,i,j;
    int alice = 0;
    int Bob = 0;
    cin >> N;
    vector<int> card(N);
    for(i=0;i<N;++i){
      cin >> card.at(i);
    }

    for(i=0;i<N-1;++i){
      int t=0;
      for(j=i+1;j<N;++j){
        if(card.at(i) < card.at(j)){
          t = card.at(i);
          card.at(i) = card.at(j);
          card.at(j) = t;
        }
      }
    }
    
    for(i=0;i<N;++i){
      if(i % 2 == 0){
        alice += card.at(i);
      }else{
        Bob += card.at(i);
      }
    }

    cout << alice - Bob <<endl;
}
  


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

int main() {
    int const MOD = 1e9 + 7;
    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];
    sort(a, a + n);

    if (n % 2 == 0) {
        bool ok = true;
        int cnt = 0;
        for (int i = 0; i < n; i += 2) {
            int b = 2 * cnt + 1;
            if (!(a[i] == b && a[i + 1] == b)) ok = false;
            cnt++;
        }
        if (!ok) {
            cout << 0 << endl;
            return 0;
        }
    } else {
        if (a[1] == 0) {
            cout << 0 << endl;
            return 0;
        }
    }

    ll ans = 1;
    rep(i, n / 2) ans = (ans * 2) % MOD;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3972
#include <iostream>
#include <array>

int main()
{
  std::array<char , 4> S;
  int ans = 0;
  for(int i = 0; i < 4; i++){
    std::cin >> S.at(i);
  }
  for(int i = 0; i < 4; i++){
    if(S.at(i) == '+'){
      ans ++;
    }else{
      ans--;
    }
  }
  std::cout << ans;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

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

    int N; cin>>N;
    if(N%2==0){
        cout<<N/2-1<<endl;
    }else{
        cout<<N/2<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
n, a, b = map(int, input().split())
p = 10 ** 9 + 7

def cmb(n, r, p):
    up = 1
    down = 1
    count = r
    for i in range(n + 1):
        if count <= 0:
            break
        else:
            up = up * (n - i) % p
            down = factinv[i + 1]
            count -= 1
    return ((up * down) % p)

def pow(a, n, p):
    bi = str(format(n, 'b'))
    res = 1
    for i in range(len(bi)):
        res = (res * res) % p
        if bi[i] == '1':
            res = (res * a) % p
    return res
                      
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, 2 * 10**5 + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

print((pow(2, n, p) - cmb(n, a, p) - cmb(n, b, p) - 1) % p)


Measured memory_bytes: 27212
import java.util.*;
import java.util.Map;
import java.util.HashMap;


public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N =sc.nextInt();
        int A[]=new int[N];
        Map<Integer,Integer> map = new HashMap<>();
        Map<Integer,Integer> nmap = new HashMap<>();
        for(int i = 0;i<N;i++){
            map.put(i,sc.nextInt());
        }

        map.entrySet().stream().sorted(java.util.Map.Entry.comparingByValue()).forEach(s->{
            System.out.print(s.getKey()+1+" ");
        });

    }
}


Measured memory_bytes: 72936
#include <bits/stdc++.h>
using namespace std;
int ans = 0;
int main(){
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i++){
        if (s[i] == '?') printf("D");
        else printf("%c",s[i]);
    }
}


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

const int INF=1e9;
int choco[15][1005];
int s[15][1005]; //(0,0) から (i,j)　までの　ホワイトチョコの数

int sum(int w1,int h1,int w2,int h2){
    return s[h2][w2]-s[h1-1][w2]-s[h2][w1-1]+s[h1-1][w1-1];
}

int main(){
    int h,w,k; cin >> h >> w >> k;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            char c; cin >> c;
            if(c=='0') choco[i][j]=0;
            else choco[i][j]=1;
            s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+choco[i][j];
        }
    }
    // for(int i=1;i<=h;i++){
    //     for(int j=1;j<=w;j++){
    //         cout << sum(0,0,j,i);
    //     }
    //     cout << endl;
    // }
    int m=(1<<(h-1));
    int ans=INF;
    int cut[15];
    for(int i=0;i<m;i++){
        int hcnt=0;
        cut[0]=0;
        
        for(int j=1;j<h;j++){
            if(i & (1<<(j-1))){
                hcnt++;
                cut[hcnt]=j;
            }
        }
        cut[hcnt+1]=h;
        int wcnt=0;
        int latest=0;
        bool loop=false;
        bool retry=false;
        for(int j=1;j<=w;j++){
            retry=false;
            for(int l=0;l<=hcnt;l++){
                if(sum(latest,cut[l]+1,j,cut[l+1])>k){
                    if(sum(j,cut[l]+1,j,cut[l+1])>k) loop=true;
                    wcnt++;
                    latest=j;
                    retry=true;
                    break;
                }
            }
            if(loop) break;
            if(retry){
                j--; continue;
            }
            retry=false;
        }
        if(!loop){
            ans=min(ans,hcnt+wcnt);
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define _ << ": " <<
#define watch1(var1) cerr << (#var1) _ var1 << '\n'
#define watch2(var1, var2) cerr << (#var1) _ var1 << ", " << (#var2) _ var2 << '\n'
#define watch3(var1, var2, var3) cerr << (#var1) _ var1 << ", " << (#var2) _ var2 << ", " << (#var3) _ var3 << '\n'
#define wloop(size, arr) cerr << (#arr) << ": "; for (int i = 0; i < int(size); i++) cerr << arr[i] << " \n"[i+1 == int(size)]

template<typename... Args>
void read(Args&... args) { ((cin >> args), ...); }

template<typename... Args>
void show(Args... args) { ((cout << args << " "), ...); }

#define ll long long
#define ints(a...) int a; read(a)
#define IN(a) for (auto &it : a) cin >> it

int dp[3001][3001];

void solve() {
    string s, t;
    read(s, t);

    for (int i = 1; i <= (int)s.size(); i++) {
        for (int j = 1; j <= (int)t.size(); j++) {
            if (s[i - 1] == t[j - 1]) 
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else 
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    vector<char> ans;
    int i = s.size(), j = t.size();
    while (i != 0 && j != 0) {
        if (dp[i - 1][j] == dp[i][j]) i--;
        else if (dp[i][j - 1] == dp[i][j]) j--;
        else ans.emplace_back(s[i - 1]), i--, j--;
    }

    for (int i = ans.size() - 1; ~i; i--) cout << ans[i];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1; 
    // cin >> T;
    while (T--) solve();
    return 0;
}

Measured memory_bytes: 38816
#include<cstdio>
#include<cstring>

#define M 1046527
#define NIL (-1)
#define L 14

char H[M][L];

int getChar(char ch) {
    if (ch == 'A') return 1;
    else if (ch == 'C') return 2;
    else if (ch == 'G') return 3;
    else if (ch == 'T') return 4;
    else return 0;
}

long long getKey(char str[]) {
    long long sum = 0, p = 1, i;
    for (i = 0; i < strlen(str); i++) {
        sum += p*(getChar(str[i]));
        p *= 5;
    }
    return sum;
}

int h1(int key){ return key % M; }
int h2(int key){ return 1 + (key % (M - 1)); }

int find(char str[]) {
    long long key, i, h;
    key = getKey(str);
    for (i = 0;; i++) {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h], str) == 0) return 1;
        else if (strlen(H[h]) == 0) return 0;
    }
    return 0;
}

int insert(char str[]) {
    long long key, i, h;
    key = getKey(str);
    for (i = 0;; i++) {
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(H[h], str) == 0) return 1;
        else if (strlen(H[h]) == 0) {
            strcpy(H[h], str);
            return 0;
        }
    }
    return 0;
}

int main() {
    int i, n, h;
    char str[L], com[9];
    for (i = 0; i < M; i++) H[i][0] = '\0';
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%s %s", com, str);
        if (com[0] == 'i') {
            insert(str);
        } else {
            if (find(str)) {
                printf("yes\n");
            } else {
                printf("no\n");
            }
        }
    }
    return 0;
}


Measured memory_bytes: 16996
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
   char s[11];
   scanf("%s",&s);
   int i,j;
   for(i=0;s[i];++i)
   {
     if(s[i]=='B')
     {
       for(j=i-1;j>=0;--j)
       {
         if(s[j]!='*' && s[j]!='B')
         { s[j]='*';
           break;
         }
       }
     }
   }
  
  for(i=0;s[i];++i)
  {
    if(s[i]!='*' && s[i]!='B')
        printf("%c",s[i]);
  }
          
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main()
{
 int ans=0;
 string S,T;
 cin>>S>>T;
 if(T[0]==S[0]){
    ans=ans+1;
 }
 if(T[1]==S[1]){
    ans=ans+1;
 }
 if(T[2]==S[2]){
    ans=ans+1;
 }
 cout<<ans;
}


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

int main(){
  int A, B, C;
  cin >> A >> B >> C;
  
  if(A==5 && B==5 && C==7 || A==5 && B==7 && C==5 || A==7 && B==5 && C==5){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}


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

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;

  int max_sum = 0;
  if (A > K) {
    max_sum += K;
  }
  else {
    max_sum += A;
    K -= A;

    if (B > K) {
      // do nothing
    }
    else {
      K -= B;

      if (C > K) {
        max_sum -= K;
      }
      else {
        max_sum -= C;
      }
    }
  }
  cout << max_sum << endl;
}

Measured memory_bytes: 3596
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int M = scan.nextInt();
		int K = scan.nextInt();

		//友人，ブロック，無関係
		ArrayList<ArrayList<Integer>> friends = new ArrayList<ArrayList<Integer>>();
		ArrayList<ArrayList<Integer>> blocked = new ArrayList<ArrayList<Integer>>();

		for(int i = 0; i < N; i++){
			ArrayList<Integer> x = new ArrayList<Integer>();
			ArrayList<Integer> y = new ArrayList<Integer>();
			friends.add(x);
			blocked.add(y);
		}
		
		for(int i = 0; i < M; i++){
			int a = scan.nextInt() - 1;
			int b = scan.nextInt() - 1;
			friends.get(a).add(b);
			friends.get(b).add(a);
		}

		for(int i = 0; i < K; i++){
			int a = scan.nextInt() - 1;
			int b = scan.nextInt() - 1;
			blocked.get(a).add(b);
			blocked.get(b).add(a);
		}
		
		//各連結成分のサイズ
		int size[] = new int[N];
		Arrays.fill(size, 0);
		//どの連結成分に属しているか
		int belong[] = new int[N];

		boolean seen[] = new boolean[N];
		Arrays.fill(seen, false);
		Queue<Integer> queue = new ArrayDeque<Integer>();
		
		for(int i = 0; i < N; i++){
			
			if(seen[i] != true){
				queue.add(i);
				seen[i] = true;
				while(!queue.isEmpty()){
					int x = queue.poll();
					belong[x] = i;
					size[belong[x]]++;
					for(int j = 0; j < friends.get(x).size(); j++){
						if(seen[friends.get(x).get(j)] != true){
							queue.add(friends.get(x).get(j));
							seen[friends.get(x).get(j)] = true;
							
						}
					}
				}
			}
		}
		
		for(int i = 0; i < N; i++){
			int result = size[belong[i]] - 1;
			for(int j = 0; j < friends.get(i).size(); j++){
				if(belong[friends.get(i).get(j)] == belong[i])result--;
			}
			for(int j = 0; j < blocked.get(i).size(); j++){
				if(belong[blocked.get(i).get(j)] == belong[i])result--;
			}
			System.out.println(result);
		}
	}
}

Measured memory_bytes: 156276
#include <bits/stdc++.h>
#define fr(i, n) for (int i = 0; i < n; ++i)
#define frab(i, a, b) for (int i = a; i < b; ++i)
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef double ld;

const int N = 100;
const int INF = 1e9 + 10;

int main() {
    //freopen("a.in", "r", stdin);
    vector <ll> a(3);
    for (int i = 0; i < 3; i++)
        cin >> a[i];
    int cnt = 0;
    while (a[0] % 2 == 0 && a[1] % 2 == 0 && a[2] % 2 == 0) {
        sort(a.begin(), a.end());
        vector <ll> b = a;
        b[0] = (a[1] + a[2]) / 2;
        b[1] = (a[0] + a[2]) / 2;
        b[2] = (a[0] + a[1]) / 2;
        a = b;
        cnt++;
        if (b[0] == b[1] && b[0] == b[2]) {
            cout << -1;
            return 0;
        }
    }
    cout << cnt;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>
#include <string.h>
#include <bitset>
#include <stack>

using namespace std;
typedef long long ll;

int main(){
  int n, q;
  string s;
  cin >> n >> q >> s;
  
  vector<int> vec(s.size() + 1, 0);
  for (int i = 1; i < s.size(); i++) {
    vec[i] = vec[i - 1] + (s[i - 1] == 'A' && s[i] == 'C' ? 1 : 0);
  }
  
  while(q--) {
    int l, r;
    cin >> l >> r;
    cout << vec[r - 1] - vec[l - 1] << endl;
  }
  return 0;
}


Measured memory_bytes: 1408
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath> 
#include<cstring> 
#include<cassert>
#include<string>
#include<sstream>
#include<fstream>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<set>
#include<bitset>
#include<iomanip>
#include<utility>
#include<functional>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cwchar>
#include<cwctype>
#include<exception>
#include<locale>
#include<numeric>
#include<new>
#include<stdexcept>
#include<limits>
using namespace std;

#define ll long long
#define INF 1e9
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pii pair<int,int>
#define sz(s) s.size()
#define all(s) (s.begin(),s.end())

const int maxn=100005;
int n,k;
bool ok;
vector<int>edge[maxn];
int l[maxn],r[maxn],odd[maxn],ans[maxn];
bool have[maxn];

void dfs(int x,int par){
	int curl=-INF,curr=INF,curodd=0;
	rep(i,edge[x].size()){
		int y=edge[x][i];
		if(y==par)continue;
		dfs(y,x);
		if(curodd&&odd[y]==curodd){
			puts("No");
			exit(0);
		}
		if(odd[y])curodd=3-odd[y];
		curl=max(curl,l[y]-1);
		curr=min(curr,r[y]+1);
		if(curl>curr){
			puts("No");
			exit(0);
		}
	}
	if(have[x]){
		if(curl>l[x]||curr<r[x]||(curodd&&curodd!=odd[x])){
			puts("No");
			exit(0);
		}
	}
	else{
		l[x]=curl;
		r[x]=curr;
		odd[x]=curodd;
	}
} 

void dfs2(int x,int par){
	rep(i,edge[x].size()){
		int y=edge[x][i];
		if(y==par)continue;
		if(have[y]){
			if(l[x]-1>l[y]||r[x]+1<r[y]||(odd[x]&&odd[x]==odd[y])){
				puts("No");
				exit(0);
			}
			dfs2(y,x);
			continue;
		}
		if(odd[x]&&odd[y]==odd[x]){
			puts("No");
			exit(0);
		}
		if(!odd[y])odd[y]=3-odd[x];
		l[y]=max(l[y],l[x]-1);
		r[y]=min(r[y],r[x]+1);
		if(l[y]>r[y]){
			puts("No");
			exit(0); 
		}
		dfs2(y,x);
	}
}

int main(){
	scanf("%d",&n);
	rep(i,n+1)l[i]=-INF,r[i]=INF;
	rep(i,n-1){
		int u,v;
		scanf("%d%d",&u,&v);
		edge[u].push_back(v);
		edge[v].push_back(u); 
	}
	scanf("%d",&k);
	rep(i,k){
		int v,p;
		scanf("%d%d",&v,&p);
		have[v]=true;
		l[v]=r[v]=p;
		odd[v]=p&1?1:2;
	}
	dfs(1,0);
	dfs2(1,0);
	puts("Yes");
	REP(i,n)printf("%d\n",r[i]);
	return 0;
}
/*
4
1 2
2 3
3 4
2
1 1
3 3
*/

Measured memory_bytes: 17024
/* ex 7_3
   KitamoriFumiya */

#include <stdio.h>
#include <stdlib.h>

int main(void){
	int i, j, row, column, *ptr_row, *ptr_column;
	char **ptr;
	scanf("%d %d\n", &row, &column);
	//各行の配列へのポインタ分のメモリ領域を確保
	ptr = (char**)calloc(row, sizeof(char*));
	if(ptr == NULL){
		fprintf(stderr, "calloc error.\n");
		exit(1);
	}
	
	//各行の要素分のメモリ領域を確保
	for(i = 0; i < row; i++){
		ptr[i] = (char*)calloc(column, sizeof(char));
		if(ptr[i] == NULL){
			fprintf(stderr, "calloc error.\n");
			exit(1);
		}
	}
	// 残る行を記録するためのメモリ領域を確保
	ptr_row = (int*)calloc(row, sizeof(int));
	if(ptr_row == NULL){
		fprintf(stderr, "calloc error.\n");
		exit(1);
	}
	// 残る行を記録するptr_rowを初期化
	for(i = 0; i < row; i++){
		ptr_row[i] = 0;
	}
	// 残る列を記録するためのメモリ領域を確保
	ptr_column = (int*)calloc(column, sizeof(int));
	if(ptr_column == NULL){
		fprintf(stderr, "calloc error.\n");
		exit(1);
	}
	// 残る列を記録するptr_columnを初期化
	for(i = 0; i < column; i++){
		ptr_column[i] = 0;
	}
	// 元のマス目を入力し、黒を含む行と列は残すので残る列、行を記録する配列に1を格納
	for(i = 0; i < row; i++){
		for(j = 0; j < column; j++){
			scanf(" %c", &ptr[i][j]);
			if(ptr[i][j] == '#'){
				ptr_row[i] = 1;
				ptr_column[j] = 1;
			}
		}
	}
	// 黒のマスを含む行列を出力
	for(i = 0; i < row; i++){
		if(ptr_row[i] == 1){
			for(j = 0; j < column; j++){
				if(ptr_column[j] == 1){
					printf("%c", ptr[i][j]);
				}
			}
			printf("\n");
		}
	}
	
	// 残る行を記録するためのメモリ領域を開放
	free(ptr_row);
	// 残る列を記録するためのメモリ領域を開放
	free(ptr_column);
	
	//メモリ領域の解放，各行の要素分の領域を開放し，
	//各行の配列へのポインタの領域を解放
	//（メモリ領域の確保と逆順）
	for(i = 0; i < row; i++){
		free(ptr[i]);
	}
	free(ptr);
	
	return 0;
}

Measured memory_bytes: 1636
#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pi pair<int,int>
#define vi vector<int>
#define pL pair<ll,ll>
#define vL vector<ll>
#define vp vector<pi>
#define vpL vector<pL>
#define pi3 pair<int, pi>
#define pi4 pair<pi, pi>

const int MX=300000+10;
const ll mod=998244353;


int main()
{
    FasterIO;

    string s="ACL", s2="";
    
    int k; cin>>k;
    
    for(int i=0; i<k; i++) s2+=s;
    
    cout<<s2<<endl;
    
    return 0;
}


Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {

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

	    int n=gi();
	    int t= n;
	    int f=0;
	    while(t>0) {
	    	f+=t%10;
	    	t=(t-(t%10))/10;
	    }
	    //System.out.print();
	    if (n%f==0) {
	    	System.out.print("Yes");
	    }else {
	    	System.out.print("No");
	    }



	}

	public static long d(long n) {
		String a=String.valueOf(n);
		return (long)a.length();
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35564
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
 
using namespace std;
 
int main (){
  
  int a,b,k;
  cin >> a >>b;
  
   
  for(int i=0;i<=a;i++){
    for(int j =0;j<=a;j++){
      k = a -i -j;
      if(b ==10000*i+5000*j+1000*k && k>=0){
        
        cout << i <<" "<< j << " " << k << endl;
        
        return 0;
      }
    }
  }
  
  cout <<"-1" << " " << "-1" << " " << "-1" << endl;
  
  return 0;
}
   
         


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

int main() {
    int n; cin >> n;
    vector<int> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];
    int q; cin >> q;
    vector<int>  t(q);
    for (int i = 0; i < q; i++) cin >> t[i];

    int ans = 0;
    for (int i = 0; i < q; i++) {
        if (t[i] == *lower_bound(s.begin(), s.end(), t[i])) ans++;
    }
    cout << ans << endl;    
}


Measured memory_bytes: 3248
input()
passport = input().split()
approveflag=True
for strx in passport:
    x = int(strx)
    if x%2==0 and not (x%3==0 or x%5==0):
        approveflag = False

if approveflag == True:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007ll
#define INF 1000000000ll
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	vector<ll> a(n);
	REP(i,n) cin>>a[i];
	vector<ll> c;
	ll tmp=1;
	FOR(i,1,n) {
		if(a[i]!=a[i-1]) {
			c.pb(tmp);
			tmp=1;
		} else tmp++;
	}
	c.pb(tmp);
	ll ans=0;
	REP(i,c.size()) ans+=c[i]/2;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n)repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
typedef pair<int,int> P;
typedef pair<int, P> PP;
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define fi first
#define se second
const int inf = 1e9+7;
const int INF = 1e18+7;
int mod = 1e9+7;

vector<int> v6, v2, v3, ans;
void init(){
	rrep(i,30000){
		if(i%6 == 0)v6.push_back(i);
		else if(i%2 == 0)v2.push_back(i);
		else if(i%3 == 0)v3.push_back(i);
	}
}

signed main(){
	int n;
	init();
	scanf("%lld", &n);
	
	if(n == 3){
		printf("2 5 63\n");
		return 0;
	}
	
	int cnt = 0;
	rep(i,v2.size()/2){
		if(n < 4)break;
		rep(j,2)ans.push_back(v2[cnt++]);
		n -= 2;
	}
	cnt = 0;
	rep(i,v3.size()/2){
		if(n < 2)break;
		rep(j,2)ans.push_back(v3[cnt++]);
		n -= 2;
	}
	cnt = 0;
	rep(i,v6.size()){
		if(n == 0)break;
		ans.push_back(v6[cnt++]);
		n--;
	}
	
	int s = 0;
	rep(i,ans.size())s += ans[i];
	//printf("%lld\n", s);
	rep(i,ans.size())printf("%lld%c", ans[i], i == ans.size()-1 ? '\n' : ' ');
	return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<utility>
#include<queue>
#define rep(i, n) for(int i=0;i<=n;i++)
using namespace std;
int main(){
	int n, y;
	cin>>n>>y;
	rep(i, n){
		rep(j, n){
			if(i+j>n)
				break;
			if(10000*i+5000*j+1000*(n-i-j)==y){
				cout<<i<<" "<<j<<" "<<n-i-j<<endl;
				return 0;
			}
		}
	}
	cout<<"-1 -1 -1"<<endl;
	return 0;
}

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

int main() {
  long long  N;
  cin >> N ;
  long long  n1 = N/500;
  // cout << n1 << endl;
  long long tmp = N - n1*500;
  long long  n2 = tmp/5;
  // cout << n2 << endl;
  tmp += (tmp-n2);

  long long  ans = n1*1000 + n2*5;
  cout << ans << endl;
}


Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int N, M; cin >> N >> M;
    vi A(M), B(M); 
    REP(i, M) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }

    vvi es(N);
    REP(i,M) {
        es[A[i]].push_back(B[i]);
        es[B[i]].push_back(A[i]);
    }

    queue<int> que;
    que.push(0);
    vb vis(N, false);
    vi dist(N, INF);
    dist[0] = 0;

    while(!que.empty()) {
        int x = que.front(); que.pop();
        vis[x] = true;

        for(int nx : es[x]) {
            if (vis[nx]) continue;

            dist[nx] = dist[x] + 1;
            que.push(nx);
        }
    }

    string ans = dist[N - 1] <= 2 ? "POSSIBLE" : "IMPOSSIBLE";
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 14832
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    int n,k;
    cin >> n >> k;
    if(k == 1)cout << 0 << endl;
    else
        cout << n-k << endl;
    return 0;
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    string S;
    cin >> S;
    map<char, ll> cnt;
    ll N = S.size();
    rep(i, N) {
        cnt[S[i]]++;
    }
    if (cnt.size() == 1) {
        if (cnt[S[0]] == 1) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }
    } else if (cnt.size() == 2) {
        if (cnt[S[0]] == 1) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }
    }else {
        bool ok = true;
        for (P p : cnt) {
            if (p.second > (N + 2) / 3) {
                ok = false;
            }
        }
        if (ok) {
            cout << "YES" << '\n';
        } else {
            cout << "NO" << '\n';
        }
    }
}

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


Measured memory_bytes: 512
S = input()[::-1]
Surpus = [0] * 2019
Surpus[0] = 1

sum = 0
x = 1
for i in S:
    sum += int(i) * x
    Surpus[sum % 2019] += 1
    x *= 10
    x %= 2019

ans = 0
for i in Surpus:
    ans += i * (i - 1) // 2

print(ans)

Measured memory_bytes: 9388
#include <stdio.h>

int main() {
	int n;
	int a;
	int b;
	int a_sum;
    scanf("%d", &n);
    scanf("%d", &a);
    scanf("%d", &b);
	a_sum = n * a;
	if (a_sum < b) {
		printf("%d\n", a_sum);
    }
	else {
		printf("%d\n", b);
	}
	return 0;
}

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

#define select(_1, _2, x, ...) x

#define repn(i, n) for (int i = 0; i < (n); i++)
#define repr(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, ...) select(__VA_ARGS__, repr, repn)(i, __VA_ARGS__)

#define rrepn(i, n) for (int i = (n - 1); i >= 0; i--)
#define rrepr(i, a, b) for (int i = (b - 1); i >= (a); i--)
#define rrep(i, ...) select(__VA_ARGS__, rrepr, rrepn)(i, __VA_ARGS__)

#define umax(m, x) (m = max(m, x));
#define umin(m, x) (m = min(m, x));

#define rng(v) v.begin(), v.end()
#define rrng(v) v.rbegin(), v.rend()

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

using ll = long long int;

using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;

using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;

const int INF = 1e9;
const ll LINF = 1e18;

inline void yn(bool f) { cout << (f ? "Yes" : "No") << endl; }


int main() {
    int w, s;
    cin >> s >> w;

    if (w >= s)
        printf("unsafe\n");
    else
    {
        printf("safe\n");
    }
    

    return 0;
}


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

#define ll long long
#define sz(x) (int)x.size();
#define go ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

using namespace std;

int main(){
	go;
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a.begin(), a.end());
	ll ans=0;
	for(int i=0;i<k;i++){
		ans+=a[i];
	}
	cout<<ans;
	
}

Measured memory_bytes: 3648
from fractions import *
n,k=map(int,input().split())
a=list(map(int,input().split()))
g=a[0]
for i in range(1,n):
    g=gcd(g,a[i])
if k%g==0 and k<=max(a):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 21324
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
typedef long long ll;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define rrep(i,n,a) for(int i=n;i>=a;i--)
#define FOR(i,n) for(int i=0;i<n;i++)
#define all(s) s.begin(),s.end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define pcnt(n) __builtin_popcount(n)
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;


signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    double r;
    cin>>r;
    double PI = 3.1415926535897932384626;
    cout<<setprecision(20)<<2.0*r*PI<<endl;
}

Measured memory_bytes: 3800
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		String s=sc.next();
		String t=sc.next();
		int sum=0;
		for(int i=0;i<s.length();i++) {
			if(s.charAt(i)!=t.charAt(i)) {
				sum++;
			}
		}
		System.out.println(sum);
		
	}
}

Measured memory_bytes: 41236
from fractions import gcd

A,B = [int(zz) for zz in input().split()]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

x = gcd(A,B)

print(len(set(prime_factorize(x)))+1)


Measured memory_bytes: 5176
#include <iostream>

#include <string>
#include <regex>
#include <vector>
#include <memory>
//namespace fs = boost::filesystem;
const long int MOD = 1e9+7;
int main(void){
    long long int N;

    std::cin>>N;
    int Power = 1;

    for(int i = 1 ; i < N+1 ; i++){
        Power = ((Power%MOD)*(i%MOD))%(MOD);
    }
    std::cout<<Power<<std::endl;

 	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int cnt = 0;
  while(1) {
    if(a == b && b == c && a % 2 == 0) {
      cout << -1;
      return 0;
    } else if(a % 2 == 1 || b % 2 == 1 || c % 2 == 1) {
      cout << cnt;
      return 0;
    } else {
      cnt++;
      int ha = a / 2, hb = b / 2, hc = c / 2;
      a = hb + hc;
      b = ha + hc;
      c = hb + ha;
    }
  }
}
    

Measured memory_bytes: 256
import scala.io.Source

object Main {
  def main(args: Array[String]) = {
    val lines = Source.stdin.getLines.toStream

    val str = lines.head.replace("?", ".")
    val target = lines.drop(1).head

    val res = (0 to (str.length - target.length)).flatMap { n =>
      // println(str.slice(n, n + target.length))
      str.slice(n, n + target.length).r.findFirstIn(target).map(_ => n)
    }

    if (res.nonEmpty) {
      val posLast = res.last
      println(str.slice(0, res.last).replace(".", "a") + target + str.slice(res.last + target.length, str.length).replace(".", "a"))
    } else {
      println("UNRESTORABLE")
    }
  }
}


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

int main(void){
    int k ,x; cin >> k >> x;
    for(int i=max(-1000000,x-k+1);i<=min(1000000,x+k-1);i++){
        cout << i;
        if(i!=min(1000000,x+k-1)) cout <<' ';
    }
    cout << endl;
    return 0;
}


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

using namespace std;
const int N = 2e3 + 5, MOD = 1e9 + 7;
int n, k;
long long f[N];
long long power(long long base, long long e) {
	long long ret = 1;
	while (e) {
		if (e % 2 == 0) {
			base = (base * base) % MOD;
			e /= 2;
		}
		ret = (ret * base) % MOD;
		--e;
	}
	return ret;
}

long long nCr(long long n, long long r) {
	return (f[n] * power(f[r] * f[n - r] % MOD, MOD - 2)) % MOD;
}

long long mem[N][N];
long long go(int places, int rem) {
	if (rem == 0 || places == 1)
		return 1;
	long long &ret = mem[places][rem];
	if (~ret)
		return ret;
	ret = (go(places - 1, rem) + go(places, rem - 1)) % MOD;
	return ret;
}
int main() {
#ifndef ONLINE_JUDGE
	//freopen("input.in", "r", stdin);
#endif
	memset(mem, -1, sizeof mem);
	f[0] = 1;
	for (int i = 1; i < N; ++i)
		f[i] = (f[i - 1] * i) % MOD;
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= k; ++i) {
		long long places = nCr(k - 1, i - 1);
		int rem = n - k - i + 1;
		if (rem < 0)
			puts("0");
		else
			printf("%lld\n", (places * go(i + 1, rem)) % MOD);
	}
	return 0;
}

Measured memory_bytes: 31744
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # データの状態に左右されないためにrandom.choice()を用いることもある。
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right


if __name__ == "__main__":
    s = input()
    if s[2]==s[3] and s[4]==s[5]:
        print('Yes')
    else:
        print('No')
            



      
# for i in range(10):
#     print(i)
#     if i%5==4:
#         break

Measured memory_bytes: 3064