akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
累積和をとる⇒各要素をmで割った余りを出す
同じ余りの場合、その間はkの倍数になっている
同じ余りのものを2つ選ぶ総数
"""
n,m = LI()
a = LI()
a = list(accumulate(a))
lst = [0] + [i % m for i in a]
lst = list(Counter(lst).items())
ans = 0
for i,j in lst:
    if j >= 2:
        ans += j*(j-1)//2
print(ans)

Measured memory_bytes: 60956
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
a=[0]
b=[0]
for i in range(N):
	a.append(a[i] + A[i])
for i in range(M):
	b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N + 1):
	if a[i] > K:
		break
	while b[j] > K - a[i]:
		j -= 1
	ans = max(ans, i + j)
print(ans)


Measured memory_bytes: 47364
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
x = 1
manzoku = 0
manzoku += sum(B)
for a in A:
   if x < N:
      if A[x] - a == 1:
         manzoku += C[A[x] - 2]
      x += 1

print(manzoku)

Measured memory_bytes: 3064
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) //[l, r)
#define rep(i,n) REP(i,0,n)           //[0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl
#define showslr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i];}cerr<<endl //[l, r))

#define yes puts("Yes")
#define no puts("No")
#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

inline void io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}

void _DEBUG(){cerr<<endl;}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<",";_DEBUG(b...);}

template<typename T> inline void in(T &e){cin>>e;}
template<typename H,typename... T>void in(H &a, T&... b){in(a);in(b...);}
template<typename T> inline void out(T e){cout<<e<<endl;}
template<typename H,typename... T> void out(H a, T... b){out(a);out(b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;

string s1,s2,s3;

signed main(){
    io();

    in(s1,s2,s3);
    printf("%c%c%c\n",s1[0],s2[1],s3[2]);

    return 0;
}


Measured memory_bytes: 888
S = list(input())
stlen = len(S) 
if len(S)%2 == 0:
    a = '10'*(int(stlen/2))
    b = '01'*(int(stlen/2))
    counta = countb = 0
    for i in range(stlen):
        if a[i] != S[i]:
            counta += 1
        if b[i] != S[i]:
            countb += 1
    print(min(counta,countb))
else:
    a = '10'*(int(stlen/2))+'1'
    b = '01'*(int(stlen/2))+'0'
    counta = countb = 0
    for i in range(stlen):
        if a[i] != S[i]:
            counta += 1
        if b[i] != S[i]:
            countb += 1
    print(min(counta,countb))

Measured memory_bytes: 4008
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <cstdio>
#include <set>
#include <stack>
#include <queue>
#include <cassert>
#include <numeric>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define rrep(i,n) for(int i=n; i>=1 ; i--)
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define SP <<" "<<
//#define int ll
typedef long long ll;

const int md = 1000000007;
const int INF = 1<<30;
using namespace std;



int main(){
    
    ll n; cin >> n;
    ll a[5];
    ll nmin = __LONG_LONG_MAX__;
    rep(i,5) {
        cin >> a[i];
        nmin = min(a[i], nmin);
    }

    cout << 4 + ((n-1)/nmin)+1 << endl;
    

    
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define ll long long
#define double long double
#define MAX (int)(5*pow(10,3) + 10)
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = pow(10,18);
ll INF = inf;
ll modulo = pow(10,9) + 7;
double eps = 1e-10;
ifstream in;
ofstream out;


void deal(){
	ll a,b;
	cin>>a>>b;
	cout<<max(a+b, max(a-b,a*b));
}
 
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))

sita_maxi = [0 for i in range(n+1)]
sita_maxi[n] = a[n]
for i in range(n-1, -1, -1):
    sita_maxi[i] = sita_maxi[i+1] + a[i]

if a[0] > 1:
    print(-1)
    exit()

lst = [1]
for i in range(1, n+1):
    lst.append(min((lst[i-1]-a[i-1])*2, sita_maxi[i]))
    if lst[-1] < a[i]:
        print(-1)
        exit()

print(sum(lst))

Measured memory_bytes: 22148
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cctype>
#define rep(i,a,b) for(int i=(a);i<b;i++)
#define INF 1000000000
#define MAX_N 105
using namespace std;
bool debug=false;

bool check(int n){
  int k=0,x=n;
  while(x){
    k++;
    x/=10;
  }
  if(k==1){
    return true;
  }else if(k==2){
    if(n%10==n/10)return true;
  }else if(k==3){
    if(n%10==n/100)return true;
  }else if(k==4){
    if((n%10==n/1000)&&(n/10%10==n/100%10))return true;
  }
  return false;
}

int main(){
  int n;
  cin>>n;
  for(int i=0;i<1000;i++){
    if(check(n-i)&&n-i>0){
      cout<<n-i<<endl;
      return 0;
    }
    if(check(n+i)&&n<=10000){
      cout<<n+i<<endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 3096
s = input()
t = input()

l = []

for i in range(len(s)-len(t) + 1):
    f = True
    for j in range(len(t)):
        if s[i+j] != '?' and s[i+j] != t[j]:
            f = False
            break
    if f:
        a = s[:i] + t + s[i+len(t):]
        l.append(a.replace('?','a'))
if len(l)>0:
    print(min(l))
else:
    print('UNRESTORABLE')


Measured memory_bytes: 3060
n, p = map(int,input().split())
if n == 1:
  print(p)
elif n > 40:
  print(1)
else:
  ans = 1
  i = 1
  while(True):
    if i ** n > p:
      break
    if p % (i ** n) == 0:
      ans = i
    i += 1
  print(ans)

Measured memory_bytes: 9180
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

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

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

signed main(){
    int n; cin >> n;
    int inp;
    string s = "";
    rep(i,0,n) {
        cin >> inp;
        s += (char)((int)'0' + inp);
    }

    int cnt[10010] = {};
    repq(i,1,4) {
        if((int)s.length() - i >= 0) {
            repq(j,0,s.length() - i) {
                string sb = s.substr(j,i);
                cnt[ atoi(sb.c_str()) ]++;
            }
        }
    }

    rep(i,0,10010) {
        if(cnt[i] == 0) {
            cout << i << endl;
            return 0;
        }
    }
    cout << "?" << endl;
    return 0;
}

Measured memory_bytes: 3300
#include<stdio.h>
int main(void)
{
    int a[60000];
    int n;
    int ans1,ans2;
    int i,j;
    for(i = 1; i <= 60000; i++){
        a[i] = 0;
    }
    a[1]=1;
    for(i = 4; i <= 60000; i+=2){
        a[i]=1;
    }
    for(i = 3; i*i <= 60000; i++){
        if(a[i]==0){
            for(j = i; j<=60000; j+=i){
                a[j]=1;
            }
            a[i]=0;
        }
    }
    while(scanf("%d",&n) != EOF){
        for(i = 1; i <= 60000; i++){
            if(a[i] == 0 && i < n) ans1 = i;
            if(a[i] == 0 && i > n){
                ans2 = i;
                break;
            }
        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}

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

int main()
{
  static const int STATE_GTCOUNT = 0;
  static const int STATE_LTCOUNT = 1;
  int state = STATE_GTCOUNT;
  int64_t gtCount = 0; // Nの範囲的に32bitではたりない
  int64_t ltCount = 0; // Nの範囲的に32bitではたりない
  int64_t sum = 0;     // Nの範囲的に32bitではたりない
  
  string s;
  cin >> s;

  for (const auto& c : s)
  {
    if (c == '<')
    {
      if (state == STATE_LTCOUNT)
      {
        sum += ltCount * (ltCount - 1) / 2 + gtCount * (gtCount - 1) / 2 + max(ltCount, gtCount);
        
        gtCount = 0;
        ltCount = 0;
        state = STATE_GTCOUNT;
      }
      gtCount++;
    }
    else // if (c == '>')
    {
      ltCount++;
      if (state == STATE_GTCOUNT)
      {
        state = STATE_LTCOUNT;
      }
    }
  }
  sum += ltCount * (ltCount - 1) / 2 + gtCount * (gtCount - 1) / 2 + max(ltCount, gtCount);
  cout << sum << endl;
  
  return 0;
}


Measured memory_bytes: 900
def part(a, q, r)
  x = a[r]
  i = q - 1
  for j in 0...r - q
    if a[q + j] <= x
      i += 1
      a[i], a[q + j] = a[q + j], a[i]
    end
  end
  a[i + 1], a[r] = "[" + a[r].to_s + "]", a[i + 1]
  return i + 1
end
gets
a = gets.split(" ").map(&:to_i)
part(a, 0, a.length - 1)
puts a.join(" ")

Measured memory_bytes: 21432
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key = lambda x:x[1])
point = 0 
cnt = 0
for a, b in ab:
  if a < point:
    continue
  else:
    cnt += 1
    point = b
print(cnt)

Measured memory_bytes: 29084
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string s;
	cin>>s;
	if(s=="SUN") cout<<7;	
	if(s=="SAT") cout<<1;
	if(s=="FRI") cout<<2;
	if(s=="THU") cout<<3;
	if(s=="WED") cout<<4;
	if(s=="TUE") cout<<5;
	if(s=="MON") cout<<6;
}

Measured memory_bytes: 256
"use strict";

const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0]);
    
    let list = [];
    
    if(N < 4) {
    for(let i=1; i<N; i++) {
        if(N % i === 0) {
            list.push((parseInt(i) + (N / i)) - 2);
        }
    }
    
    } else {
    for(let i=1; i<=Math.sqrt(N); i++) {
        if(N % i === 0) {
            list.push((parseInt(i) + (N / i)) - 2);
        }
    }
    }

    console.log(Math.min(...list));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

using namespace std;
using namespace __gnu_pbds;

#define     mod             (int)1e9+7
#define     MOD             998244353
#define     ll              long long
#define     mp              make_pair
#define     F               first
#define     S               second
#define     t()             int test;cin>>test;while(test--)
#define     ii              pair<int,int>
#define     que_max         priority_queue <int>
#define     que_min         priority_queue <int, vector<int> , greater<int> >
#define     IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define     endl            "\n"
typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
    cout << name << " : " << arg1 << endl;
    //use cerr if u want to display at the bottom
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define trace(...)
#endif




int32_t main()

{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    IOS;

    int n, k;
    cin >> n >> k;
    vector<int> v(n);

    vector<int> dp(n + 1, 0);

    for (auto &i : v)cin >> i;

    dp[1] = abs(v[0] - v[1]);



    for (int i = 2; i < n; i++)
    {
        dp[i] = dp[i - 1] + abs(v[i] - v[i - 1]);
        for (int j = i - 2; j >= max(0, i - k); j--)
        {

            dp[i] = min((dp[j] + abs(v[i] - v[j]))  , dp[i]);

        }

    }

    cout << dp[n - 1] << endl;




}

Measured memory_bytes: 3920
n = gets.to_i
as = gets.split.map(&:to_i)

def gcd(a,b)
  return a.abs if b == 0
  gcd(b, a%b)
end

def gcds(arr)
  ans = arr[0]
  arr.size.times do |i|
    ans = gcd(ans, arr[i])
  end
  ans
end

puts gcds(as)

Measured memory_bytes: 8452
#include <bits/stdc++.h>
#define REP(a,b) for(int a=0; a<(b); ++a)
#define FWD(a,b,c) for(int a=(b); a<(c); ++a)
#define FWDS(a,b,c,d) for(int a=(b); a<(c); a+=d)
#define BCK(a,b,c) for(int a=(b); a>(c); --a)
#define ALL(a) (a).begin(), (a).end()
#define SIZE(a) ((int)(a).size())
#define VAR(x) #x ": " << x << " "
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define gcd __gcd
#define x first
#define y second
#define st first
#define nd second
#define pb push_back

using namespace std;

template<typename T> ostream& operator<<(ostream &out, const vector<T> &v){ out << "{"; for(const T &a : v) out << a << ", "; out << "}"; return out; }
template<typename S, typename T> ostream& operator<<(ostream &out, const pair<S,T> &p){ out << "(" << p.st << ", " << p.nd << ")"; return out; }

typedef long long LL;
typedef pair<int, int> PII;
typedef long double K;
typedef vector<int> VI;

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

int h, w;
char M[10][10];

int main(){
	scanf("%d %d", &h, &w);
	FWD(i,0,h) scanf("%s", M[i]);	
	int x = 0, y = 0;
	M[x][y] = '.';
	while(x != h-1 || y != w-1){
		if(M[x+1][y] == '#'){
			++x;
		}else if(M[x][y+1] == '#'){
			++y;
		}else{
			break;
		}
		M[x][y] = '.';
	}
	FWD(i,0,h)
		FWD(j,0,w)
			if(M[i][j] == '#'){
				printf("Impossible\n");
				return 0;
			}
	printf("Possible\n");
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
    int ans[1001],a=0,i;
    while(1)
    {
        int value[12];
        value[10]=0;
        scanf("%d",&value[0]);
        if(value[0]==0)
            break;
        for(i=1;i<10;i++)
        {
            scanf("%d",&value[i]);
            value[10]+=value[i];
        }
        value[11]=value[0]-value[10];
        ans[a]=value[11];
        a++;
    }
    for(i=0;i<a;i++)
        printf("%d\n",ans[i]);
    return 0;
}

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

// int/long:		-2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:	-9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// A.erase(unique(A.begin(), A.end()), A.end())

// bit: &/and, |/or, ^/xor, ~/not

// getline(cin, String)
// while (getline(cin, S)) {}

// cout <<fixed <<setprecision(10)

// priority_queue<int> q;
// priority_queue<int, vector<int>, less<int>> q; // Default: vector, less
// priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> q;

// Graph
// Warshall-Floyd: Distance between each node, N^3
// Dijkstra: Distance from the start node, N^2
// DFS(Depth-First Search)

//
// Notes
//
// When specified less than N, try full scan.
// RE: empty vector
// Check Qs
// long/int
// xor -> count each bit
// Check values
// 	1,000,000 -> Loop
// 	100,000	-> vector(int:400KB, long:800KB) 

#define	INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define	MOD 1000000007

#define	Rep0(i, n)	for (int i=0; i<n; i++)
#define	Rep1(i, n)	for (int i=1; i<=n; i++)
#define Sort(P)	sort(P.begin(), P.end())
#define Rev(P)	reverse(P.begin(), P.end())

int	main() {
	int N, K;
	cin >>N >>K;
	int i=1;
	while (N>=K) {
		N /=K;
		i++;
	}
	cout <<i <<endl;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int (i)=0;(i) < (N); (i)++)
#define all(V) V.begin(), V.end()
using i64 = int_fast64_t;
using P = pair<int,int>;

int main(){
    string s1, s2;
    cin >> s1 >> s2;
    const int N = s1.size();
    const int M = s2.size();

    vector<vector<i64>> dp(N+1, vector<i64>(M+1, 0));
    rep(i, N+1) dp[i][0] = i;
    rep(i, M+1) dp[0][i] = i;

    for(int i = 1; i <= N; i++ ){
        for(int j = 1; j <= M; j++){
            dp[i][j] = min(min(dp[i-1][j], dp[i][j-1])+1, dp[i-1][j-1] + (s1[i-1] != s2[j-1]));
        }
    }

    cout << dp[N][M] << endl;
}



Measured memory_bytes: 10732
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  int K;
  cin >> N >> K;
  int* H = new int[N];
  for(int i=0; i<N; i++){
	cin >> H[i];
  }
  // k 必殺技の回数
  if(N <= K){
	cout << "0" << endl;
	return 0;
  }

  sort(H, H+N);//昇順ソート


  long long int sum=0;
  for(int i=0; i<N-K; i++){
	sum+=H[i];
	//cout << H[i] << endl;
  }
  cout << sum << endl;

  
  delete[] H;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i ++)
#define irep(i,n) for (int i = (int)(n) - 1;i >= 0;--i)
using namespace std;
using ll = long long;
using PL = pair<ll,ll>;
using P = pair<int,int>;
constexpr int INF = 1000000000;
constexpr long long HINF = 1000000000000000;
constexpr long long MOD = 1000000007;// = 998244353;
constexpr double EPS = 1e-4;
constexpr double PI = 3.14159265358979;

template<class T> T gcd(T a,T b) {return (b ? gcd(b,a%b): a);}

struct Sieve {
    int N;
    vector<int> min_factor;
    Sieve(int _N):N(_N) {
        min_factor.assign(N + 1,-1);
        int i = 2;
        for (; i*i <= N; ++i) {
            if (min_factor[i] < 0) {
                min_factor[i] = i;
                for (int p = i*i; p <= N; p += i) {
                    if (min_factor[p] < 0) min_factor[p] = i;
                }
            }
        }
        for (int j = i; j <= N; ++j) {
            if (min_factor[j] < 0) min_factor[j] = j;
        }
    }
    // M > 1 
    vector<pair<int,int>> factorization(int M) {
        vector<pair<int,int>> ret;
        while (M > 1) {
            int p = min_factor[M],e = 1;
            M /= p;
            while (p == min_factor[M]) {
                ++e;
                M /= p;
            }
            ret.emplace_back(p,e);
        }
        return ret;
    }
    int count_factor(int M) {
        int ans = 1;
        vector<pair<int,int>> factor = factorization(M);
        for (P &p:factor) ans *= (p.second + 1);
        return ans;
    }
};

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

    int N; cin >> N;
    vector<int> A(N);
    rep(i,N) cin >> A[i];

    Sieve sieve(1000010);
    
    // pair 
    bool p = true;
    vector<int> fac(1000010,0);
    rep(i,N) {
        auto f = sieve.factorization(A[i]);
        for (P &x:f) {
            if (fac[x.first] > 0) {
                p = false;
                break;
            }
            fac[x.first]++;
        }
    }

    // set
    bool s = false;
    int g = 0;
    rep(i,N) g = gcd(g,A[i]);
    if (g == 1) s = true;

    if (p) cout << "pairwise coprime" << '\n'; 
    else if (s) cout << "setwise coprime" << '\n';
    else cout << "not coprime" << '\n';
    return 0;
}

Measured memory_bytes: 15036
#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
  
int t[3][3];
int limit;
  
int getHeuri(){
  int res=0,a;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      if(t[i][j]==0)continue;
      a=t[i][j]-1;
      res+=abs(a/3-i)+abs(a%3-j);
    }
  }
  return res;
}
  
bool check(int depth,int prev,int py,int px){
  int heuri=getHeuri();
  if(heuri+depth>limit)return false;
  if(heuri==0)return true;
  for(int i=0;i<4;i++){
    if(abs(i-prev)==2)continue;
    int ny=py+dy[i],nx=px+dx[i];
    if(ny<0||nx<0)continue;
    if(ny>=3||nx>=3)continue;
    swap(t[ny][nx],t[py][px]);
    if(check(depth+1,i,ny,nx)) return true;
    swap(t[ny][nx],t[py][px]);
  }
  return false;
}
  
void solve(int py,int px){
  for(limit=0;;limit++){
    if(check(0,99,py,px)){
      cout<<limit<<endl;
      return;
    }
  }
}
int main(){
  int py,px;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>t[i][j];
      if(t[i][j]==0){
    py=i;
    px=j;
      }
    }
  }
  solve(py,px);
  return 0;

}

Measured memory_bytes: 3096
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<set>
#include<string>
typedef long long ll;
using namespace std;
#define INF (1 << 30)
#define INFLL (1LL << 60)
#define rep(i, n) for(int i=0; i<(n); ++i)


int popcount(string bin)
{
	int cnt = 0;
	rep(i, bin.size()) if (bin[i] == '1') ++cnt;
	return cnt;
}
int popcount(ll bits)
{
	bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
	bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
	bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
	bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
	return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
}
int funcOnce(string bin, int div)
{
	int deci = 0;
	rep(i, bin.size()) deci = (deci * 2 + bin[i] - '0') % div;
	return deci;
}

vector<int> funcOnceNote(string bin, int div)
{
	int deci = 0;
	int D = bin.size();
	vector<int> imod(D);
	rep(i, D) {
		deci = (deci * 2 + bin[i] - '0') % div;
		imod[D - i - 1] = deci;
	}
	return imod;
}

int func(string bin, int div)
{
	if (div == 0) return 0;
	int deci = funcOnce(bin, div);
	int bitcnt = popcount(deci);
	int cnt = 1;
	while (deci > 0) {
		deci = deci % bitcnt;
		bitcnt = popcount(deci);
		++cnt;
	}
	return cnt;
}

int main()
{
	int N; cin >> N;
	string X; cin >> X;
	int bitcnt = popcount(X);

	string binn(N, '0');
	binn[0] = '1';

	int xmodp1, xmodm1; 
	vector<int> imodp1, imodm1;

	xmodp1 = funcOnce(X, bitcnt + 1);
	imodp1 = funcOnceNote(binn, bitcnt + 1);
	if (bitcnt > 1) {
		xmodm1 = funcOnce(X, bitcnt - 1);
		imodm1 = funcOnceNote(binn, bitcnt - 1);
	}

	vector<int> ans(N, 0);
	rep(i, N) {
		int mod, xmod;
		if (X[i] == '1') {
			mod = bitcnt - 1;
			if (mod < 1) continue;
			xmod = (mod + xmodm1 - imodm1[i]) % mod;
		}
		else {
			mod = bitcnt + 1;
			xmod = (xmodp1 + imodp1[i]) % mod;
		}
		++ans[i];
		while (xmod > 0) {
			xmod = xmod % popcount(xmod);
			++ans[i];
		}
	}

	rep(i, N) cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 5624
#include<cstdio>
int main(void)
{
    int a,b;
    scanf("%d %d" ,&a,&b);
    for(int i=0;i<10000;i++)
    {
        if(i*8/100==a && i/10==b)
        {
            printf("%d" ,i);
            return 0;
        }
    }
    printf("-1");
    return 0;
}


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

using namespace std;
#define ll long long
#define ld long double

ll binPow(ll a, ll b) {
    ll ans = 1;
    while(b > 0) {
        if(b & 1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}

ll binPowMod(ll a, ll b, ll m) {
    ll ans = 1;
    a %= m;
    while(b > 0) {
        if(b & 1) ans *= a % m;
        a *= a % m;
        b >>= 1;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    string s;
    cin >> s;
    int n = s.length();
    if(s[0] == 'A') {
        int cCnt = 0;
        for(int i=2;i<n-1;i++) {
            if(s[i] == 'C') cCnt++;
        }
        if(cCnt > 1 || cCnt == 0) {
            cout << "WA\n";
            return 0;
        }
        for(int i=1;i<n;i++) {
            if(s[i] != 'C') {
                if(isupper(s[i])) {
                    cout << "WA\n";
                    return 0;
                }
            }
        }
        cout << "AC\n";
        return 0;
    } 
    cout << "WA\n";
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int x[5];
  scanf("%d %d %d %d %d", &x[0], &x[1], &x[2], &x[3], &x[4]);
  for(int i = 0; i < 5; i++) if(x[i] == 0) printf("%d", i + 1);
  return 0;
}

Measured memory_bytes: 1684
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
const ll C = 1e9+7;

int main() {
    int N;
    cin >> N;
    int A[2][N];
    for(int i=0; i<2; i++) for(int j=0; j<N; j++) cin >> A[i][j];
    int dp[2][N];

    dp[0][0] = A[0][0];
    dp[1][0] = dp[0][0] + A[1][0];

    for(int j=1; j<N; j++) {
        dp[0][j] = dp[0][j-1] + A[0][j];
        dp[1][j] = max(dp[0][j] + A[1][j], dp[1][j-1] + A[1][j]);
    }
    cout << dp[1][N-1] << endl;
}

Measured memory_bytes: 3640
#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<tuple>
#include<algorithm>
#include<numeric>
#include<math.h>

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

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
	int N;
	cin >> N;
	ll name_count[5];
	REP(i, 5) name_count[i] = 0;

	string name;
	REP(i, N) {
		cin >> name;
		switch (name[0]) {
		case 'M':
			name_count[0]++;
			break;
		case 'A':
			name_count[1]++;
			break;
		case 'R':
			name_count[2]++;
			break;		
		case 'C':
			name_count[3]++;
			break;
		case 'H':
			name_count[4]++;
			break;
		}
	}
	
	ll ans = 0;
	REPS(i, 0, 3) {
		REPS(j, i + 1, 4) {
			REPS(k, j + 1, 5) {
				ans += (name_count[i] * name_count[j] * name_count[k]);
			}
		}
	}
	cout << ans;
	system("pause");
	return 0;
}

Measured memory_bytes: 504
import math

a, b, ca = map(float, input().split())
ca = math.radians(ca)
s = a * b * math.sin(ca) / 2
c = (a ** 2 + b ** 2 - 2 * a * b * math.cos(ca)) ** 0.5
h = b * math.sin(ca)
print("{:.5f}".format(s))
print("{:.5f}".format(a + b + c))
print("{:.5f}".format(h))


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

vector<ll>adj[100005];
bool visited[100005];
ll dp[100005];

void dfs(ll s)
{
    ll len=1;
    visited[s]=true;
    for(auto x : adj[s])
    {
        if(visited[x]==false)
            dfs(x);

        dp[s]=max(dp[s],len+dp[x]);
    }
}


int main()
{
    ll n,m,x,y;
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        cin>>x>>y;
        adj[x].push_back(y);
        //adj[y].push_back(x);
    }

    ll mx_len=0;

    for(int i=1; i<=n; i++)
    {
        if(visited[i]==false)
        {
            dfs(i);
        }
        mx_len=max(mx_len,dp[i]);
    }


    cout<<mx_len<<endl;

    return 0;
}



Measured memory_bytes: 12680
#include <iostream>
//#include <iomanip>
#include <algorithm>
//#include <numeric>
//#include <queue>
//#include <stack>
#include <math.h>
#include <vector>
//#include <string>
typedef long long LL;
using namespace std;
struct city{
    int p;
    int y;
    
    city(int input_p, int input_y){
        p = input_p;
        y = input_y;
    }
};

int main(){
    int n;
    int m;
    int p_tmp;
    int y_tmp;
    vector<city> citys;
    cin >> n >> m;
    vector<vector <int>> pref(n);
    for(int i=0; i<m; i++){
        cin >> p_tmp >> y_tmp;
        p_tmp--;
        y_tmp--;
        citys.push_back(city(p_tmp, y_tmp));
        pref[p_tmp].push_back(y_tmp);
    }

    for(int i=0; i<n; i++){
        if(pref[i].size()!=0){
            sort(pref[i].begin(), pref[i].end());
        }
    }

    for(int i=0; i<m; i++){
        auto city_position = lower_bound(pref[citys[i].p].begin(), pref[citys[i].p].end(), citys[i].y);
        int city_index = distance(pref[citys[i].p].begin(), city_position);
        city_index++;
        int city_pref = citys[i].p+1;
        int num_zero_cp = 5 - (int)log10f(city_pref);
        int num_zero_ci = 5 - (int)log10f(city_index);
        for(int i=0; i<num_zero_cp; i++){
            cout << '0';
        }
        cout << city_pref;
        for(int i=0; i<num_zero_ci; i++){
            cout << '0';
        }
        cout << city_index << endl;
    }
}

Measured memory_bytes: 7796
def solve(l:list):
    flg = 0
    bef = "f"
    for i in l:
        if i == bef:
            flg += 1
        bef = i
    return flg > 0

def main():
    l = list(input())
    print("Bad") if solve(l) else print("Good")

if __name__ == "__main__":
    main()

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int arr[300] = {};
    int cnt=0;
    for(int i=1; i<=k; i++){
        int d;
        cin>>d;
        for(int j=1; j<=d; j++){
            int m;
            cin>>m;
            arr[m] = 1;
        }
    }
    for(int i=1; i<=n; i++){
        if(arr[i]==0)
            cnt++;
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 3576
#include <cstdio>
const int MAXN = 1e5+1;
const int LOGV = 17;
int F[LOGV][MAXN];
int X[MAXN];
int main()
{
	int N, L, Q, i, j, logV, step;
	scanf("%d", &N);
	for(logV=1; (1<<(logV+1))<=N; ++logV);
	for(i=1; i<=N; ++i)
		scanf("%d", X+i);
	scanf("%d", &L);
	for(i=j=1; i<=N; ++i)
	{
		while(j<=N && X[j]-X[i]<=L) ++j;
		F[0][i] = j-1;
	}
	for(i=1; i<=logV; ++i)
		for(j=1; j+(1<<i)-1<=N; ++j)
			F[i][j] = F[i-1][F[i-1][j]];
	scanf("%d", &Q);
	int a, b;
	while (Q--)
	{
		scanf("%d%d", &a, &b);
		if(a > b)
			a ^= b ^= a ^= b;
		step = 0;
		for(i=logV; i>=0; --i)
			if(F[i][a] && F[i][a]<b)
				step += 1<<i,
				a = F[i][a];
		printf("%d\n", step+1);
	}
}

Measured memory_bytes: 7296
def solve(A, B, arr):
  lowNum = len(list(filter(lambda n: n <= A, arr)))
  highNum = len(list(filter(lambda n: n > B, arr)))
  midNum = len(arr) - lowNum - highNum
  return min([lowNum, midNum, highNum])

N = int(input())
A, B = map(int, input().split())
arr = list(map(int, input().split()))

print(solve(A, B, arr))

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

int main() {
	int n;
	cin >> n;
	int cn[2][n];
	int ans = 0;
	int dif=0,dif0=0,dif1=0;
	for (int i = 0;i < 2;i++) {
		for (int j = 0;j < n;j++) {
			cin >> cn[i][j];
		}
	}
	for (int i = 0;i < n;i++) {
		ans += cn[0][i];
	}
	ans += cn[1][n-1];
	for (int i = n-1;i > 0;i--) {
		dif0+=cn[0][i];
		dif1+=cn[1][i-1];
		dif = max(dif,dif1-dif0);
	}
	cout << ans + dif << endl;
}

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

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

	sort(A, A + N, greater<int>());
	int a=0,b=0;
	for (int i = 0; i < N; i++) {
		if (i % 2 == 0) a += A[i];
		else b += A[i];
    }
	cout << a - b << endl;

}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int n,a[500][500],f[500][500];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)cin>>a[i][j];
	long long ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		{
			bool f=0;
			for(int k=1;k<=n;k++)
				if(i!=k&&j!=k)
				{
					if(a[i][k]+a[k][j]<a[i][j]){cout<<-1<<endl;return 0;}
					if(a[i][k]+a[k][j]==a[i][j]){f=1;break;}
				}
			if(!f)ans+=a[i][j];
		}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 896
#include<bits/stdc++.h> 
#define int long long 
#define pp pair<int,int> 
#define ss second 
#define ff first 
#define pb push_back
#define mod 1000000007
#define mk(arr,n,type)  type *arr=new type[n];
#define sl s1.length();
using namespace std; 
void fastio()
{
  #ifndef ONLINE_JUDGE
  freopen("INPUT.txt","r",stdin);
  freopen("OUTPUT.txt","w",stdout); 
  #endif
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL) ; 
  cout.tie(NULL);
}
signed main()
{
    int n;
    cin>>n;
    cout<<n*n;
}

Measured memory_bytes: 3648
#include<stdio.h>
int main(){
  int n,m,i;
  scanf("%d%d",&n,&m);
  char s[m+1][2];
  int p[m+1],a[n+1][2];
  for(i=0;i<m;i++){
    scanf("%d",&p[i]);
    scanf("%s",s[i]);
  }
  for(i=1;i<=n;i++){
    a[i][0]=0;
    a[i][1]=0;
  }
  for(i=0;i<m;i++){
    if(s[i][0]=='W' && s[i][1]=='A'){
      if(a[p[i]][0]==0)
        a[p[i]][1]++;
    }
    else
      a[p[i]][0]=1;
  }
  int check=0,pena=0;
  for(i=1;i<=n;i++){
    if(a[i][0]==1){
      check+=1;
      pena+=a[i][1];
    }
  }
  printf("%d %d\n",check,pena);
  return 0;
}


Measured memory_bytes: 1536
N=input();
N=int(N);
S=[];
ans=[0,0,0,0];
for i in range(N):
  s=input();
  if s=="AC":
    ans[0]=ans[0]+1;
  if s=="WA":
    ans[1]=ans[1]+1;
  if s=="TLE":
    ans[2]=ans[2]+1;
  if s=="RE":
    ans[3]=ans[3]+1;
print("AC x "+str(ans[0]));
print("WA x "+str(ans[1]));
print("TLE x "+str(ans[2]));
print("RE x "+str(ans[3]));

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

int main() {
    ll a,b,c,count=0;
    cin>>a>>b>>c;
    if((a==b && b==c) || (a%2 == 1 || b%2 == 1 || c%2 == 1)) {
        if(a%2 == 0 && b%2 == 0 && c%2 == 0) {
            cout<<-1<<"\n";
            return 0;
        }
        else {
            cout<<0<<"\n";
            return 0;
        }
    }
    while(a%2 == 0 && b%2 == 0 && c%2 == 0) {
        ll d=a, e=b, f=c;
        a = (e+f)/2;
        b = (d+f)/2;
        c = (d+e)/2;
        count++;
    }
    cout<<count<<"\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define imx INT_MAX
#define imn INT_MIN
#define llmx LLONG_MAX
#define llmn LLONG_MIN
#define INF         100000000000000000
#define PI          3.1415926535897932384626433832795l



#define fi first
#define se second
#define pb push_back
#define f_s(a) sort(a.begin(), a.end())
#define b_s(a) sort(a.rbegin(), a.rend())
#define p(a) cout<<a<<"\n"


// ll mod = 1000000007;
// #define l(i, )
// #define rl(i, a, b) for(int i = a; i < b; i++)






// struct mycomp {
//     bool operator() (const pair<int,int> &a, const pair<int,int> &b) const{
//         if (a.second-a.first != b.second-b.first)
//         return (a.second-a.first > b.second-b.first);
//         return a.first < b.first;
//     }
// };



/////////////////////GCD//////////////////////
ll gcd(ll a, ll b)
{
	if(b==0) return a;
	return gcd(b, a%b);
}


ll extended_gcd(ll a, ll b, ll& x, ll& y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	ll x1, y1;
	ll d = extended_gcd(b, a%b, x1, y1);
	x=y1;
	y=x1-y1*(a/b);
	return d;
}

////////////////////SIEVE OF ERATOSTHENES//////////////////////
vector<int> sieveoferatosthenes(int n)
{
	vector<bool> prime(n+1, true);
	for(int i = 2; i <= sqrt(n); i++)
	{
		if(prime[i])
		{
			for(int j = i*i; j<=n; j+=i)
			{
				prime[j]=false;
			}
		}
	}	
	vector<int> all_primes;
	for(int i = 2; i <=n; i++)
	{
		if(prime[i]) all_primes.pb(i);
	}
	return all_primes;
}

////////////////////BINARY EXPONENTIATION///////////////////////
ll bin_exp(ll a, ll b, ll mod)
{
	ll ans = 1;
	while(b)
	{
		if(b%2)
		{
			b--;
			ans = (ans%mod*a%mod)%mod;
		}
		b/=2;
		a = (a%mod*a%mod)%mod;
	}
	return ans;
}


///////////////////////////BFS//////////////////////////////////
void bfs(vector<int>& distance, vector<int> a[], vector<bool>& visited, int u, vector<int>& parent)
{
	visited[u]=true;
	parent[u]=-1;
	distance[u]=0;
	queue<int> q;

	q.push(u); 
    while (!q.empty()) { 
  
        int f = q.front(); 
        q.pop(); 
  		for(int i =0; i < a[f].size(); i++)
  		{
  			if(visited[a[f][i]]==false)
  			{
  				distance[a[f][i]]=distance[f]+1;
  				parent[a[f][i]]=f;
  				visited[a[f][i]]=true;
  				q.push(a[f][i]);
  			}
  		}
    } 

}

void solve()
{

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

	// #ifndef ONLINE_JUDGE
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	// #endif
	int k, a, b, c;
	cin>>a>>b>>c>>k;

	while(b<=a and k>0)
	{
		b*=2;
		k--;
	}
	while(k>0 and c<=b)
	{
		c*=2;
		k--;
	}
	if(b>a and c>b)
	{
		cout<<"Yes"<<endl;
	}
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 3676
N,M = map(int,input().split())
o = {}
if N==1 and M==0:
  print(0)
else:
  for i in range(M):
    s,c = map(int,input().split())
    if o.get(s,-1)==-1:
        o[s]=c
    elif o.get(s,-1)!=-1 and o[s]!=c:
        print(-1)
        break
  else:
    m = [1]+[0]*(N-1)
    for k in o.keys():
        m[k-1]=o[k]
    if N!=1 and m[0]==0:
      print(-1)
    else:
      print(''.join([str(a) for a in m]))


Measured memory_bytes: 3064
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s1,s2;
    cin>>s1>>s2;
    int n=s1.size(),m=s2.size();
    int dp[n+1][m+1];
    for(int i=0;i<n+1;i++){
        for(int j=0;j<m+1;j++){
            dp[i][j]=0;
        }
    }
    for(int i=1;i<n+1;i++){
        for(int j=1;j<m+1;j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
                dp[i][j] = max(dp[i-1][j],dp[i][j]);
                dp[i][j] = max(dp[i][j-1],dp[i][j]);
            }
            else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    /*for(int i=0;i<n+1;i++){
        for(int j=0;j<m+1;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    string ans ="";
    int len = dp[n][m];
    if(len==0){
        cout<<""<<endl;
        return 0;
    }
    //cout<<len<<" len "<<endl;
    int j=m;
    int i=n;
    while(i>0 && j>0){
        if(s1[i-1]==s2[j-1]){
            ans=s1[i-1]+ans;
            i-=1;
            j-=1;
        }
        else{
            if(dp[i-1][j]>dp[i][j-1]){
                i-=1;
            }
            else{
                j-=1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 35456
/*input
1
0.5
*/
 
// author - Madhav Thakker
 
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace std;
 
#define ll long long
#define ld long double
#define int ll
#define endl '\n'

typedef pair<int, int> pii; 
typedef pair<ld, ld> pdd;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define FileIn(file) freopen(file, "r", stdin)
#define FileOut(file) freopen(file, "w", stdout)
#define all(c) c.begin(), c.end() 
#define tr(container, it )\
for(__typeof__(container.begin()) it = container.begin(); it != container.end(); it++) 
#define present(container, element) (container.find(element) != container.end())  //map, set
#define cpresent(container, element) (find(aint(container),element) != container.end()) //vector
#define what_is(x) cout << #x << " is " << x << endl; 
#define all(c) c.begin(), c.end() 
 
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
 
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
const int MOD = 1e9+7;
 
 
int fast_pow(int a, int b){
	int res = a, ret = 1;
	while(b>0){
		if(b%2)
			ret = (ret*res)%MOD;
		res = (res*res)%MOD;b/=2;
	}
	return ret;
}
 
// --
// -- 
// -- 
// std::cout << std::fixed;
// std::cout << std::setprecision(26) << f << '\n';
// str = to_string(n)
// stoi , stoll, stol
// sort(arr, arr+n, greater<int>());
// fill(prefix.begin(), prefix.end(), 0);
// 
// 
 
 
 
////
const int maxN = 3e3+7;
ld p[maxN];
ld dp[maxN][maxN];
////

signed main(){
 
	fastio;
	time_t time_t1, time_t2;
	time_t1 = clock();
 
	////////////////////////////////

	int t = 1;
	// cin >> t ;

	while(t--){

		int n;
		cin >> n;

		for (int i = 1; i <= n; ++i){
			cin >> p[i];
		}
		
		memset(dp, 0, sizeof dp);

		dp[1][1] = 1.0*p[1];
		dp[1][0] = 1.0*(1 - p[1]);
		
		for (int i = 2; i <= n; ++i){
			dp[i][0] = 1.0*dp[i-1][0]*(1 - p[i]);
			for (int j = 1; j <= n; ++j){
				dp[i][j] = 1.0*dp[i-1][j-1]*(p[i]);
				dp[i][j] = dp[i][j] +  1.0*dp[i-1][j]*(1 - p[i]);
			}
		}
		
		ld ans = 0;
		for (int i = n/2 + 1; i <= n; ++i){
			ans += dp[n][i];
		}
		printf("%0.12Lf\n", ans);
	}
 	
	///////////////////////////////
	// 
 
	time_t2 = clock();
	// cerr << "time taken :" << time_t2 - time_t1 << endl;
 
	return 0;
}


Measured memory_bytes: 141696
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef long long int lint;
typedef unsigned long long int ulint;

//#define DEBUG

#ifdef DEBUG
#	define dump(i) cout << "[*] " #i " : " << i << endl;
#	define debug(i) i
#else
#	define dump(i)
#	define debug(i)
#endif
#define rep(i, MAX) for (int i = 0; i < (MAX); ++i)

int l;

int asdf(int num) {
	string ai = to_string(num);
	while (ai.size() < l) {
		ai += '0';
	}
	sort(ai.begin(), ai.end());
	num = stoi(ai);
	reverse(ai.begin(), ai.end());
	return (stoi(ai) - num);
}

inline void solve() {
	while (true) {
		int a[25] = {};
		cin >> a[0] >> l;
		if (!a[0] && !l) break;

		dump(a[0]);
		for (int i = 1; i < 25; ++i) {
			a[i] = asdf(a[i-1]);
			dump(a[i]);
		}

		unordered_map<int, int> table;
		int ans[3] = {};
		for (int i = 0; i < 25; ++i) {
			if (table.find(a[i]) != table.end()) {
				ans[0] = table[a[i]];
				ans[1] = a[i];
				ans[2] = i - ans[0];
				break;
			}
			table[a[i]] = i;
		}
		cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
	}
}

int main() {
	//*
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	// */
#ifdef DEBUG
	const auto start = chrono::high_resolution_clock::now();
#endif
	solve();
#ifdef DEBUG
	const auto stop = chrono::high_resolution_clock::now();
	cerr << "[*] time: " << chrono::duration_cast<chrono::milliseconds>(stop-start).count()
		<< " [ms]" << endl;
#endif
	return 0;
}



Measured memory_bytes: 3248
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using pll=pair<ll,ll>;

const ll MOD=1000000007;

ll abs1(ll a){
  if(a>=0)return a;
  else return -a;
}

ll pow1(ll a,ll b,ll p){
  ll ret=1;
  while(b!=0){
    if((b&1)==1){
      ret*=a;
    }
    a*=a;
    if(a>=p)a%=p;
    b=b>>1;
  }
  return ret;
}

int digit(ll a,ll b){
  int i=0;
  while(a!=0){
    a/=b;
    i++;
  }
  return i;
}

ll gcd1(ll a,ll b){
  if(a==0 && b==0)return 0;
  ll n;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}

ll solveLinear(ll n,ll m,ll c){
  if(n==0 && m==0)return 0;
  ll a[100],b[100];
  a[0]=n;b[0]=m;
  int i=1;
  while(b[i-1]!=0){
    a[i]=b[i-1];
    b[i]=a[i-1]%b[i-1];
    i++;
  }
  n=i;
  if(c%a[n-1]!=0){
    return 0;
  }
  ll x=c/a[n-1],y=0;
  for(i=1;i<n;i++){
    ll cnt=x;
    x=y;
    y=cnt-(a[n-i-1]/b[n-i-1])*y;
  }
  return x;
}

ll modRev(ll a,ll p=MOD){
  a%=p;
  ll n=solveLinear(a,p,1);
  n%=p;
  if(n<0)return n+p;
  return n;
}

ll fact(ll n,ll p=MOD){
  if(n<0)return 0;
  int i;
  ll ret=1;
  for(i=0;i<n;i++){
    ret=ret*(i+1);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll perm(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    if(ret>=p)ret%=p;
  }
  return ret;
}

ll binom(ll n,ll k,ll p=MOD){
  if(n<0 || k<0 || n<k)return 0;
  int i;
  ll ret=1,fact=1;
  for(i=0;i<k;i++){
    ret=ret*(n-i);
    fact*=i+1;
    if(ret>=p)ret%=p;
    if(fact>=p)fact%=p;
  }
  return (ret*modRev(fact))%p;
}

int main(){
  int i,j,k,cnt=0;
  int n;
  cin>>n;
  ll a[n],b[n];
  for(i=0;i<n;i++)cin>>a[i];
  for(i=0;i<n;i++)cin>>b[i];
  vector<pll> v;
  for(i=0;i<n;i++){
    v.push_back(pll(a[i],0));
    v.push_back(pll(b[i],1));
  }
  sort(v.begin(),v.end());
  int p[2*n];
  for(i=0;i<2*n;i++)p[i]=1;
  for(i=1;i<2*n;i++){
    if(v[i-1].second==v[i].second)p[cnt]++;
    else cnt++;
  }
  ll ans=1;
  n=cnt+1;cnt=0;
  for(i=0;i<n-1;i++){
    if(p[i]<=p[i+1]){
      ans*=fact(p[i]);
      p[i+1]-=p[i];
    }
    else{
      ans*=perm(p[i],p[i+1]);
      if(i!=n-2)p[i+2]+=p[i]-p[i+1];
      p[i+1]=0;
    }
    if(ans>=MOD)ans%=MOD;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 8048
import sys

n,a,b,c = map(int,input().split())
d = {'A':a,'B':b,'C':c}

s = []
for _ in range(n):
	s.append(input())

ans = []
for i in range(n):

	if d[s[i][0]] <= 0 and d[s[i][1]] <= 0:
		print('No')
		sys.exit()
	if d[s[i][0]] < d[s[i][1]]:
		d[s[i][1]] -= 1
		d[s[i][0]] += 1
		ans.append(s[i][0])
	elif d[s[i][0]] > d[s[i][1]]:
		d[s[i][0]] -= 1
		d[s[i][1]] += 1
		ans.append(s[i][1])
	else:
		if i < n-1 and s[i+1].strip(s[i]) != '' and d[s[i+1].strip(s[i])] == 0:
			string = s[i+1].strip(s[i+1].strip(s[i]))
			d[string] += 1
			d[s[i].strip(string)] -= 1
			ans.append(s[i+1].strip(s[i+1].strip(s[i])))
		else:
			d[s[i][0]] += 1
			d[s[i][1]] -= 1
			ans.append(s[i][0])
print('Yes')
for i in range(len(ans)):
	print(ans[i])



Measured memory_bytes: 17012
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define mp make_pair 
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define rrep(i,a,b) for(int i = a; i >=b; i--)
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define sq(a) (a)*(a)
#define nl "\n"
#define all(x) (x).begin(),(x).end()
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,
//tree_order_statistics_node_update> indexed_set;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using ii = pair<int, int>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using pil = pair<int,ll>;
using vvi = vector<vi>;
using vpi = vector<ii>;

const int N = 100100;
ll mod=1000000007;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    int cnt =0;
    rep(i,0,s.size()-1){
        if(s[i]=='1')cnt++;
    } 
    cout<<cnt<<nl;
    return 0;
}


Measured memory_bytes: 3644
#include<stdio.h>

int max(int,int);

int main(){
	int a=0;
	int S=0,T=0;
	int i=0;
	for(i=0;i<4;i++){
		scanf("%d",&a);
		S=S+a;
	}
	for(i=0;i<4;i++){
		scanf("%d",&a);
		T=T+a;
	}

	a=max(S,T);
	printf("%d\n",a);

	return 0;
}


int max(int a,int b){
	if(a<b){
		return b;
	}else{
		return a;
	}
}

Measured memory_bytes: 0