akhauriyash/Code-Regression huggingface dataset:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

N, M = map(int, input().split())

cond = [-1] * N

for i in range(M):
    s, c = map(int, input().split())
    if cond[s - 1] > -1 and cond[s - 1] != c:
        print(-1)
        exit()
    cond[s - 1] = c

cond = list(map(str, cond))
for i in range(10 ** N):
    si = str(i)
    if N != len(si):
        continue
    ok = True
    for j in range(N):
        if cond[j] == '-1':
            continue
        if si[j] != cond[j]:
            # print(si, si[j], cond[j])
            ok = False
            break
    if ok:
        print(si)
        exit()
print(-1)



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

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	ll N; cin>>N;
	vector<int> L(N);
	for (int i=0; i<N; i++)
		cin>>L[i];
	map<int,int> suf;
	for (auto x : L)
		suf[x]++;
	for (int i=1007; i>=2; i--)
		suf[i-1]+=suf[i];
	ll ret=N*(N-1)*(N-2)/6;
	for (int i=0; i<N; i++)
		for (int j=i+1; j<N; j++)
			ret-=suf[L[i]+L[j]];
	cout<<ret<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
signed main(){
  ll n,a,lim;
  cin>>n>>a;
  lim=a;
  vector<ll> x(n);
  for(ll& i:x)cin>>i,lim=max(lim,i),i-=a;
  vector<vector<ll>> dp(n+1,vector<ll>(lim*n*2+1,0));
  auto cnv=[&](ll crd)->ll{return crd+lim*n;};
  dp[0][cnv(0)]=1;
  for(int i=1;i<=n;++i){
    for(ll y=-lim*n;y<=lim*n;++y){
      assert(dp[i][cnv(y)]==0);
      dp[i][cnv(y)]=dp[i-1][cnv(y)];
      if(abs(y-x[i-1])<=lim*n) dp[i][cnv(y)]+=dp[i-1][cnv(y-x[i-1])];
      if(dp[i][cnv(y)]>400)cerr<<"i"<<i-1<<",cnv:"<<cnv(y)<<"->"<<dp[i][cnv(y)]<<endl;
    }
  }
  cout<<dp[n][cnv(0)]-1;
}

Measured memory_bytes: 2304
import itertools
n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))
t,h = 0,0
a = list(itertools.permutations(range(1,n+1)))
for i,c in enumerate(a):
    if p == c:
        t = i
    if q == c:
        h = i
print(abs(t-h))

Measured memory_bytes: 13892
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>
#include <iomanip>

using namespace std;

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main() {
    vector<vector<int>> c(3, vector<int>(3));
    REP(i, 3)
        REP(j, 3)
            cin >> c[i][j];

    REP(i, 3){
        RFOR(j, 2, 0){
            c[i][j] -= c[i][0];
        }
    }
    if(c[0] == c[1] && c[1] == c[2])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<vi> vvi;
typedef std::vector<ll> vll;
typedef std::vector<vll> vvll;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

int main() {
  int n;
  scan(n);
  string s, t;
  scan(s);
  scan(t);
  for (int i = n; i >= 0; --i) {
    if (s.substr(n-i, i) == t.substr(0, i)) {
      print(2*n - i);
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 888
#include<stdio.h>
int main(void){
	int S,h,m,s;
	
	scanf("%d",&S);
	h=S/3600;
	m=(S%3600)/60;
	s=(S%3600)%60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

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

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

const long long mod = 1000000007;
long long pw[200200] = { 1 };

int main()
{
	map<pair<long long, long long>, pair<int, int> > chk;

	for (int i = 1; i < 200200; i++) pw[i] = (pw[i - 1] * 2) % mod;

	long long a = mod- 1;
	int n; cin >> n;
	while (n--) {
		long long x, y;
		cin >> x >> y;
		if (x == 0 && y == 0) { a++; continue; }
		if (make_pair(x, y) < make_pair(0ll, 0ll)) x = -x, y = -y;
		long long g = gcd(abs(x), abs(y));
		x /= g; y /= g;
		if (y > 0) chk[{x, y}].first++;
		else chk[{-y, x}].second++;
	}

	long long r = 1;
	for (auto& p : chk) {
		r = r * (pw[p.second.first] + pw[p.second.second] - 1) % mod;
	}

	printf("%lld\n", (a + r) % mod);

	return 0;
}

Measured memory_bytes: 17788
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = (int)1e9;
const ll  inf = (ll)1e18;
const int mod = 1000000007;
const int MAX_N = 100010;



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

	int n;
	cin >> n;
	vector<ll> a(3 * n);
	rep(i, 3 * n) cin >> a[i];

	sort(all(a), greater<ll>());

	ll ans = 0LL;
	for (int i = 0; i < n; i++) {
		ans += a[i * 2 + 1];
	}

	out(ans);

	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define fst first
#define scd second
using namespace std;

inline ll read(){
	ll f=1,x=0;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')
		  f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int MAXN=1e5+5;
int n,m,fa[MAXN];
struct EDGE{
	int u,v;
}e[MAXN];
ll ans[MAXN],sz[MAXN];
int get_fa(int x){
	if(x==fa[x]) return x;
	return fa[x]=get_fa(fa[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	n=read();
	m=read();
	for(int i=1; i<=m; ++i){
		e[i].u=read();
		e[i].v=read();
	} 
	for(int i=1; i<=n; ++i)
	  fa[i]=i,sz[i]=1;
	ans[m]=(ll)n*(n-1)/2;
	for(int i=m; i>=1; --i){
		int u=get_fa(e[i].u),v=get_fa(e[i].v);
		if(u==v)
		  ans[i-1]=ans[i];
		else{
			ans[i-1]=ans[i]-sz[v]*sz[u];
			sz[v]+=sz[u]; fa[u]=v;
		}
	}
	for(int i=1; i<=m; ++i)
	  cout<<ans[i]<<endl;
	return 0;
}

Measured memory_bytes: 4096
#!/usr/bin/env python3

N, M, K = map(int, input().split())
A = list(map(int, input().split())) + [0]
B = list(map(int, input().split()))

answer = 0

currA = sum(A)
currB = 0
b_index = 0

for a_index in range(N, -1, -1):
    currA -= A[a_index]
    currK = K - currA
    if currK < 0: continue
    
    while currB <= currK and b_index <= (M - 1):
        nextB = currB + B[b_index]
        if nextB > currK: break
        
        currB = nextB
        b_index += 1
    
    answer = max(answer, a_index + b_index)
    
print(answer)

Measured memory_bytes: 39692
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int x = sc.nextInt();
		int ans = 0;
		for(int i = 0 ; i <= a ; i++) {
			for(int j = 0 ; j <= b ; j++) {
				for(int k = 0 ; k <= c ; k++) {
					if(500 * i + 100 * j + 50 * k == x) {
						ans++;
					}
				}
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef pair<int, int> P;
constexpr auto INF = INT_MAX/2;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

int main() {

	int a, b, q;
	cin >> a >> b >> q;
	vector<ll> s(a), t(b), x(q);
	rep(i, a)cin >> s[i];
	rep(i, b)cin >> t[i];
	rep(i, q)cin >> x[i];

	rep(i, q) {

		ll xx = x[i];
		int ss, tt;
		ss = lower_bound(all(s), xx)-s.begin();
		tt = lower_bound(all(t), xx)-t.begin();

		ll rs, rt, ls, lt;
		if (ss == 0)ls = LINF;
		else ls = xx - s[ss - 1];
		if (tt == 0)lt = LINF;
		else lt = xx - t[tt - 1];
		if (ss == a)rs = LINF;
		else rs = s[ss] - xx;
		if (tt == b)rt = LINF;
		else rt = t[tt] - xx;

		vector<ll> dist;
		dist.push_back(max(ls, lt));
		dist.push_back(max(rs, rt));
		dist.push_back(rs+lt+min(rs,lt));
		dist.push_back(ls+rt+min(ls,rt));
		
		ll ans = LINF;
		rep(j, dist.size())ans = min(ans, dist[j]);
		cout << ans << endl;
	}
}

Measured memory_bytes: 3712
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner x = new Scanner(System.in);
		int n = x.nextInt();
		int[] s = new int[13];
		int[] h = new int[13];
		int[] c = new int[13];
		int[] d = new int[13];
		for(int f = 0 ; f < 13 ; f++ ){
			s[f] = 0 ;
			h[f] = 0 ;
			c[f] = 0 ;
			d[f] = 0 ;
		}
		String mk ;
		int su;
		for(int g = 1 ; g <= n ; g++){
			mk = x.next();
			su = x.nextInt();
			if(mk.equals("S")){
				s[su-1] = 1;
			}else if(mk.equals("H")){
				h[su-1] = 1;
			}else if(mk.equals("C")){
				c[su-1] = 1;
			}else if(mk.equals("D")){
				d[su-1] = 1;
			}
		}
			for(int j = 0 ; j < 13 ; j++){
				if(s[j] == 0){
				System.out.println("S"+" "+ (j+1));
				}
			}
			for(int j = 0 ; j < 13 ; j++){
				if(h[j] == 0){
				System.out.println("H"+" "+ (j+1));
				}
			}
			for(int j = 0 ; j < 13 ; j++){
				if(c[j] == 0){
				System.out.println("C"+" "+ (j+1));
				}
			}
			for(int j = 0 ; j < 13 ; j++){
				if(d[j] == 0){
				System.out.println("D"+" "+ (j+1));
				}
			}
	}
}

Measured memory_bytes: 18060
//
//  main.c
//  C
//
//  Created by s1262004 on 2019/07/19.
//  Copyright © 2019 s1262004. All rights reserved.
//

#include <stdio.h>
#include <limits.h>
#define qLength 100
int n;
int queue[qLength] = {-1}, qh, qt;
typedef struct node{
    int to[100];
    int edge;
    int color; // 0 -> WHITE, 1 -> GREY, 2 -> BLACK
    int d;
} node_t;

node_t vertex[100];

void bfs(int);
int isEmpty();
void enqueue(int);
int dequeue();

int main(int argc, const char * argv[]) {
    qh = qt = 0;
    int i, j;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        int key, num;
        scanf("%d %d", &key, &num);
        vertex[key-1].d = -1;
        vertex[key-1].color = 0;
        vertex[key-1].edge = num;
        for (j = 0; j < num; j++) {
            int temp;
            scanf("%d", &temp);
            vertex[key-1].to[j] = temp - 1;
        }
    }
    
    bfs(0);
    
    for (i = 0; i < n; i++){
        printf("%d %d\n", i + 1, vertex[i].d);
    }
    
    
    return 0;
}

void bfs(int ix){
    vertex[ix].color = 1;
    vertex[ix].d = 0;
    enqueue(ix);
    
    while (!isEmpty()){
        int u = dequeue();
        for (int i = 0; i < vertex[u].edge; i++){
            int link = vertex[u].to[i];
            //printf("(%d, %d)\n", u, link);
            
            if (vertex[link].color == 0){
                vertex[link].color = 1;
                vertex[link].d = vertex[u].d + 1;
                enqueue(link);
            }
        }
        vertex[u].color = 2;
    }
}

int isEmpty(){
    if(qt == qh) return 1;
    return 0;
}

void enqueue(int x){
    queue[qt] = x;
    if (qt + 1 == qLength) qt = 0;
    else qt++;
}

int dequeue(){
    int x = queue[qh];
    if (qh + 1 == qLength) qh = 0;
    else qh++;
    return x;
}



Measured memory_bytes: 2112
#include <iostream>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> hoge(n);
    for(int i=0;i<n;i++) cin>>hoge.at(i);
    
    for(int i=0;i<n;i++){
        cout<<hoge.at(i);
        if(i<n-1) cout<<" ";
    }
    cout<<endl;
    
    for(int i=1;i<n;i++){
        int a=hoge.at(i);
        int j=i-1;
        
        while(0<=j && hoge.at(j)>a){
            hoge.at(j+1)=hoge.at(j);
            j--;
        }
        
        hoge.at(j+1)=a;
        
        for(int i=0;i<n;i++){
            cout<<hoge.at(i);
            if(i<n-1) cout<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 3080
#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
   int h,m,s,ah,am,as;
   cin>>s;
   as=(s%3600)%60;
   am=(s%3600)/60;
   ah=s/3600;
   printf("%d:%d:%d\n",ah,am,as);
   return 0;
}


Measured memory_bytes: 3228
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		
		while(true) {
			int h = scan.nextInt();
			int w = scan.nextInt();
			
			if(h == 0) break;
			
			int check = 0;
			
			for(int i = 0; i < h; i++) {
				for(int j = 0; j < w; j++) {
					if(check % 2 == 0) {
						System.out.print('#');
					}else {
						System.out.print('.');
					}
					check++;
				}
				if(w % 2 == 0) check++;
				System.out.println();
			}
			System.out.println();
		}
		
	}

}



Measured memory_bytes: 39448
#include<bits/stdc++.h>
using namespace std;
int main() {
    int x,n;
    cin>>x>>n;
    set<int> p;
    for (int i=0;i<n;i++) {
        int a;
        cin>>a;
        p.insert(a);
    }
    int m=0;
    for (int i=0;i<=101;i++)
        m = (abs(x-i) < abs(x-m) && !p.count(i) ? i : m);
    cout<<m<<endl;
}

Measured memory_bytes: 3636
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXLEN=100;

char s[MAXLEN+1]; int n;

void run() {
	scanf("%s",s); n=strlen(s);
	int ret=INT_MAX;
	REP(x,26) {
		char c='a'+x;
		vector<int> pos; REP(i,n) if(s[i]==c) pos.PB(i);
		if(SZ(pos)==0) continue;
		int cur=max(pos[0],n-pos[SZ(pos)-1]-1);
		FORSZ(i,1,pos) cur=max(cur,pos[i]-pos[i-1]-1);
		if(cur<ret) ret=cur;
	}
	printf("%d\n",ret);
}

int main() {
	run();
	return 0;
}


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

namespace AtCoderWorkspace
{
    class Program
    {
        static void Main(string[] args)
        {
            var cin = new Scanner();
            var S = cin.next();

            var o = S.Count(s => s == 'o');
            var x = S.Count(s => s == 'x');

            if(x >= 8)
            {
                //lose
                Console.WriteLine("NO");
            }
            else
            {
                Console.WriteLine("YES");
            }            
        }
    }
    
    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

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

        public long nextLong()
        {
            return long.Parse(next());
        }

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

        public double nextDouble()
        {
            return double.Parse(next());
        }


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

        public static T Dequeue<T>(this IList<T> self)
        {
            var result = self[0];
            self.RemoveAt(0);
            return result;
        }


        public static void Enqueue<T>(this IList<T> self, T item)
        {
            self.Add(item);
        }


        public static T Peek<T>(this IList<T> self)
        {
            return self[0];
        }
    }

}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
 
const int MaxX=1e2;
const int MaxP=1e2;
bool IsOn[MaxP+2]={};
int main(){
	int X, N, p;
	scanf("%d %d\n",&X,&N);
	while(N-->0)
		scanf("%d",&p), IsOn[p]=1;
	int Grt, Lss;
	for(Grt=X;IsOn[Grt];Grt++);
	for(Lss=X;IsOn[Lss];Lss--);
	printf("%d\n",(Grt-X<X-Lss)? Grt: Lss);
}

Measured memory_bytes: 3780
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

vector<Int> ps(1e6,0);
map<Int, Int> sq;

template<typename T> 
map<T, Int> factorize(T x){
  map<T, Int> res;
  for(Int i=2;i<=500||i*i*i<=x;i++){
    while(x%i==0){
      x/=i;
      res[i]++;
    }
  }
  if(sq.count(x)) res[sq[x]]+=2,x=1;
  if(x!=1) res[x]++;
  return res;
}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> s(n);
  for(Int i=0;i<n;i++) cin>>s[i];
  
  for(Int i=2;i<(Int)ps.size();i++){
    if(ps[i]) continue;
    for(Int j=i+i;j<(Int)ps.size();j+=i) ps[j]=1;
  }
    
  vector<Int> c;
  for(Int i=2;i<4000;i++) if(!ps[i]) c.emplace_back(i*i*i);
  for(Int i=2;i<(Int)ps.size();i++)  if(!ps[i]) sq[i*i]=i;
  
  for(Int i=0;i<n;i++){
    for(Int j=0;j<(Int)c.size();j++){
      if(s[i]<c[j]) break;
      while(s[i]%c[j]==0) s[i]/=c[j];
    }
  }

  using MP = map<Int, Int>;
  vector<MP> vm(n);
  map<MP, Int> m;
  for(Int i=0;i<n;i++)
    if(s[i]!=1) m[vm[i]=factorize(s[i])]++;
  
  auto comp=[&](MP a){
    MP b;
    for(auto p:a)
      b[p.first]=3-p.second;
    return b;
  };
  Int ans=0;
  for(Int i=0;i<n;i++) ans|=s[i]==1;
  set<MP> used;
  for(Int i=0;i<n;i++){
    //for(auto p:vm[i]) cout<<i<<":"<<p.first<<" "<<p.second<<endl;
    if(used.count(vm[i])) continue;
    auto a=vm[i];
    auto b=comp(a);
    ans+=max(m.count(a)?m[a]:0LL,m.count(b)?m[b]:0LL);
    
    used.emplace(a);
    used.emplace(b);
  }
  
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 121984
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
const double PI = acos(-1);
const double EPS = 1e-15;
long long INF=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};

long long dp[101][4][4][4];

int main(){
  
  int n;
  cin>>n;
  
  //0:A
  //1:C
  //2:G
  //3:T
  //求める文字列の先頭にTを3つ付け加えるとしても答えは変わらない。
  dp[0][3][3][3]=1;
  
  REP(len,n){
    REP(i,4){
      REP(j,4){
        REP(k,4){
          REP(a,4){
            if(a==1 && j==0 && k==2)continue;//AGCが部分文字列として出てきてしまう時
            if(a==1 && j==2 && k==0)continue;//GACが部分文字列として出てきてしまう時
            if(a==2 && j==0 && k==1)continue;//ACGが部分文字列として出てきてしまう時
            if(a==1 && i==0 && k==2)continue;//A?GCが部分文字列として出てきてしまう時
            if(a==1 && i==0 && j==2)continue;//AG?Cが部分文字列として出てきてしまう時
            dp[len+1][j][k][a] += dp[len][i][j][k];
            dp[len+1][j][k][a] %= i_7;
          }
        }
      }
    }
  }
  
  long long ans=0;
  REP(i,4){
    REP(j,4){
      REP(k,4){
        ans += dp[n][i][j][k];
        ans %= i_7;
      }
    }
  }
  
  cout<<ans<<endl;    
  return 0;
}


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

#ifdef DEBUG
#define PRINT(x)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#x<<" = "<<(x)<<endl;
#define PRINTA(a,first,last)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<(first)<<", "<<(last)<<")"<<endl;\
    for (int i=(first);i<(last);++i){cout<<#a<<"["<<i<<"] = "<<(a)[i]<<endl;}
#else
#define PRINT(x)
#define PRINTA(a,first,last)
#endif

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}
template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

int main(void)
{
    constexpr int N_MAX = 100000;
    int N;
    int a[3][N_MAX];
    cin >> N;
    REP(i, N) REP(j, 3) cin >> a[j][i];

    int dp[3][N_MAX];
    REP(i, 3) dp[i][0] = a[i][0];

    FOR(i, 1, N) {
        REP(j, 3) {
            dp[j][i] = 0;
            REP(k, 3) {
                if (k != j) {
                    amax(dp[j][i], dp[k][i - 1] + a[j][i]);
                }
            }
            //printf("dp[%d][%d] = %d\n", j, i, dp[j][i]);
        }
    }
    int result = 0;
    REP(i, 3) amax(result, dp[i][N - 1]);
    cout << result << endl;
    return 0;
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

map <ll,ll>a;
int main() {
	ll n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		ll x,y;
		cin>>x>>y;
		a[x]+=y;
	}
	ll ans=0,cnt=0;
    for(auto itr = a.begin(); itr != a.end(); ++itr) {
        ll val= itr->first;           // キーを表示
        ll su = itr->second;
        cnt+=su;
        ans+=val*su;
        if(cnt>=m){
        	ans-=(cnt-m)*val;
        	break;
        }
    }
    cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 6528
#include<iostream>
#include<iomanip>
#include<limits>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<cmath>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define big ((ll)(1e9)+7)


int main()
{
  ll n;
  cin >> n;
  vector<string> s;
  for(ll i = 0;i < n;i++)
  {
    string S;
    cin >> S;
    s.push_back(S);
  }
  sort(s.begin(),s.end());
  vector<pair<int , string > > ans;
  ans.push_back(make_pair(1,s[0]));
  for(ll i = 0;i < n-1;i++)
  {
    if(s[i] == s[i+1])
      ans[ans.size()-1].first++;
    else
      ans.push_back(make_pair(1,s[i+1]));
  }

  // cout << endl;
  // for(ll i = 0;i < ans.size();i++)
  // {
  //   cout << ans[i].second << endl;
  // }

  sort(ans.rbegin(),ans.rend());
  ll a = ans[0].first;
  // cout << endl;
  vector<string> Ans;
  for(ll i = 0;i < ans.size();i++)
  {
    if(ans[i].first == a)
    {
      // cout << ans[i].second << endl;
      Ans.push_back(ans[i].second);
    }
    else
    {
      break;
    }
  }
  sort(Ans.begin(),Ans.end());
  for(ll i = 0;i < Ans.size();i++)
  {
    cout << Ans[i] << endl;
  }

}


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

using namespace std;

typedef long long ll;


void solve() {
    int k, s;
    ll ans = 0;
    int x , y, z;
    cin >> k >> s;
    for (int i = 0; i <= k; ++i) {
        for (int j=0; j <= k; ++j) {
                if ((s - i - j <= k) && (s - i -j >=0)) ++ans;
        }
    }
    cout << ans;

}

int main() {

    solve();
    return 0;
}


Measured memory_bytes: 3160
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;

vector<pair<int, int> > E[2];
vector<int> G[2][100005];
const long long pr = 100000000000031;

map<pair<int, int>, int> cnt;
set<pair<int, int> > in;

int N;

void add(pair<int, int>& e)
{
	if (e.first > e.second) swap(e.first,e.second);
	int &a = cnt[e];
	if (++a == 2) in.insert(e);
}

void del(pair<int, int>& e)
{
	if (e.first > e.second) swap(e.first,e.second);
	auto I = cnt.find(e);
	I->second--;
	if (I->second == 0) cnt.erase(I);
	else if (I->second == 1) in.erase(e);
}

int main()
{
	scanf ("%d",&N);

	for (int k=0;k<2;k++){
		for (int i=1;i<N;i++){
			int x,y; scanf ("%d %d",&x,&y);
			if (x > y) swap(x,y);
			G[k][x].push_back(E[k].size());
			G[k][y].push_back(E[k].size());
			E[k].push_back({x,y});
			add(E[k].back());
		}
	}

	int d = N-1;
	while (!in.empty()){
		int x = in.begin()->first, y = in.begin()->second;
		if (G[0][x].size() + G[1][x].size() > G[0][y].size() + G[1][y].size()) swap(x,y);
		for (int k=0;k<2;k++){
			vector<pair<int, int> > &e = E[k];
			vector<int> &a = G[k][x];
			vector<int> &b = G[k][y];
			for (auto &i : a){
				if (e[i].first == e[i].second) continue;
				del(e[i]);
				if (e[i].first == x) e[i].first = y;
				if (e[i].second == x) e[i].second = y;
				if (e[i].first == e[i].second) continue;
				b.push_back(i);
				add(e[i]);
			}
			a.clear();
		}
		d--;
	}

	puts(d?"NO":"YES");

	return 0;
}

Measured memory_bytes: 26868
n,m=map(int,input().split())

li = sorted(list(map(int,input().split())),reverse=True)
if n>=m:
    print(0)
    
else:
    long=max(li)-min(li)
    dis=[li[i]-li[i+1] for i in range(m-1)]
    dis_sort=sorted(dis,reverse=True)
    print(sum(dis_sort[n-1:]))

Measured memory_bytes: 13968
#include<iostream>
#include<string>
#include<algorithm>
#include<stack>
#include<math.h>
#include<map>
#include<unordered_map> 
#include<vector>
#include<queue>
#include<set>
#include<bits/stdc++.h>
#include<deque> 
#include<bitset>
#include<string>
#define N 40
#define K 300005
#define MOD 1e9+7
#define int long long 
#define fastio  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

int max(int a, int b){
    if(a>b)
        return a;
    return b;
}
int mod = 1e9 + 7;
int ans = 0;
int vis[100005], dis[100005], in[100005];
void dfs(int pa, int ro, vector<int> g[]){
	vis[ro] = 1;
	

	for(int x: g[ro]){
		in[x] --;
		dis[x] = max(dis[x], dis[ro] + 1);
		if(vis[x] == 0 && in[x] == 0){
			dfs(ro, x, g);
		}
	}

}
int32_t main(){
	int n, m;
	cin>>n>>m;
	vector<int> g[n+1];
	int x, y;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		g[x].push_back(y);
		in[y]++;
	}
	for(int i=1;i<=n;i++){
		//g[0].push_back(i);
		g[0].push_back(i);
        in[i]++;
	}

	dfs(-1, 0, g);
	for(int i=0;i<=n;i++){
		ans = max(ans, dis[i]);
	}
	cout<<ans - 1;
}

Measured memory_bytes: 10356
IDENTIFICATION                   DIVISION.
PROGRAM-ID.                      ABC_059_B.
ENVIRONMENT                      DIVISION.
DATA                             DIVISION.
WORKING-STORAGE                  SECTION.
    01 i      PIC 9(3).
    01 num    PIC 9(3) VALUE 101.
    01 A      PIC X(101).
    01 B      PIC X(101).
    01 strA   PIC X(101).
    01 strB   PIC X(101).
    01 numA   PIC 9(3).
    01 numB   PIC 9(3).
PROCEDURE                        DIVISION.
MAIN.
    ACCEPT A.
    ACCEPT B.

    SUBTRACT FUNCTION STORED-CHAR-LENGTH(A) FROM num GIVING numA.
    SUBTRACT FUNCTION STORED-CHAR-LENGTH(B) FROM num GIVING numB.

    PERFORM VARYING i FROM 1 BY 1 UNTIL numA < i
        STRING
            strA(1:FUNCTION STORED-CHAR-LENGTH(strA))
            ZERO
            INTO strA
        END-STRING
    END-PERFORM.

    STRING
        strA(1:FUNCTION STORED-CHAR-LENGTH(strA))
        A(1:FUNCTION STORED-CHAR-LENGTH(A))
        INTO strA
    END-STRING.

    PERFORM VARYING i FROM 1 BY 1 UNTIL numB < i
        STRING
            strB(1:FUNCTION STORED-CHAR-LENGTH(strB))
            ZERO
            INTO strB
        END-STRING
    END-PERFORM.

    STRING
        strB(1:FUNCTION STORED-CHAR-LENGTH(strB))
        B(1:FUNCTION STORED-CHAR-LENGTH(B))
        INTO strB
    END-STRING.

    IF strA > strB THEN
        DISPLAY "GREATER"
    ELSE
        IF strA < strB THEN
            DISPLAY "LESS"
        ELSE
            DISPLAY "EQUAL"
        END-IF
    END-IF.

    STOP RUN.


Measured memory_bytes: 636
import java.util.Scanner;
import static java.lang.Math.*;

class Main
{
  public static void main(String[]$) {
    long N = new Scanner(System.in).nextLong();
    int ans = 314159265;
    for (long i = 1; i*i <= N; ++i) {
      if(N % i == 0) {
        ans = min(ans, max($(i), $(N/i)));
      }
    }
    System.out.println(ans);
  }
  
  static int $(long n) {
    int cnt  = 0;
    while(n > 0) {
      n /= 10;
      ++cnt;
    }
    return cnt;
  }
}

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

int main() {
  int r, g, b;
  cin >> r >> g >> b;
  
  int num = 0;
  
  num = r * 100 + g * 10 + b;
  
  if (num % 4 == 0) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
    
  return 0;
}

Measured memory_bytes: 3592
import java.util.Scanner

object Main extends App { 
  val sc = new Scanner(System.in)
  val n, q = sc.nextInt()
  val list = (for (i <- 0 until q) yield (sc.nextInt(), sc.nextInt(), sc.nextInt())).toList
 
  type Cmd = (Int, Int, Int)

  val df = 2147483647
  val an = Array.fill(n)(df)

  def update(i:Int, x:Int):Unit = an(i) = x
  def find(s:Int, t:Int):Int = {
    def iter(i:Int, m:Int):Int = {
      if (i > t) m 
      else iter(i+1, m min an(i))
    }
    iter(s, df)
  }

  def solver(l:List[Cmd], acc:List[Int]):List[Int] = {
    if (l.isEmpty) acc.reverse
    else {
      val (com, x, y) = l.head
      com match {
        case 0 => { update(x, y); solver(l.tail,acc) }
        case _ => solver(l.tail, find(x, y)::acc)
      }
    }
  }

  solver(list, Nil).foreach(println)
}



Measured memory_bytes: 284508
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>

using namespace std;

int counter(string data);
int cnt;

int main()
{
	int m, ans;
	string dataset;
	cin >> m;
	for(int i = 0; i < m; i ++){
		cin >> dataset;
		ans = counter(dataset);
		cout << ans << endl;
	}
	return 0;
}

int counter(string data)
{
	set<string> setstr;
	int l = data.length();
	cnt = 0;
	string a, b, str;
	if(l == 1) return 1;
	for(int i = 1; i < l; i++){
		a = data.substr(0, i);
		b = data.substr(i, l - i);
		str = a + b;
		setstr.insert(str);
		str = b + a;
		setstr.insert(str);
		reverse(b.begin(), b.end());
		str = a + b;
		setstr.insert(str);
		str = b + a;
		setstr.insert(str);
		reverse(a.begin(), a.end());
		str = a + b;
		setstr.insert(str);
		str = b + a;
		setstr.insert(str);
		reverse(b.begin(), b.end());
		str = a + b;
		setstr.insert(str);
		str = b + a;
		setstr.insert(str);
	}
	return (int)setstr.size();
}

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

dp = [200000] * 200000
dp[0] = 0

for i in range(N+1):
    for j in range(i+1):
        tmp = 6**j
        if tmp > N or i - tmp < 0:
            break
        dp[i] = min(dp[i], dp[i-tmp]+1)
    for j in range(i+1):
        tmp = 9**j
        if tmp > N or i - tmp < 0:
            break
        dp[i] = min(dp[i], dp[i-tmp]+1)

print(dp[N])

Measured memory_bytes: 4596
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
using namespace std;

int main()
{
  int n,k;
  string s;
  cin>>n>>k>>s;
  for(int i=0;i<n;i++){
    if(i==k-1 && s[i]=='A'){
      cout<<'a';
    }else if(i==k-1 && s[i]=='B'){
      cout<<'b';
    }else if(i==k-1 && s[i]=='C'){
      cout<<'c';
    }else{
      cout<<s[i];
    }
  }
  cout<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

  int N, A, B; cin >> N >> A >> B;
  string S; cin >> S;

  int a = 0, b = 0, n = 0;
  REP(i,N){
	bool ok = false;
	if(S[i] == 'a'){
	  if(n < A+B){
		++a;
		++n;
		ok = true;
	  }
	}
	else if(S[i] == 'b'){
	  if(n < A+B && b < B){
		++b;
		++n;
		ok = true;
	  }
	}
	
	cout << (ok?"Yes":"No") << endl;
  }
  
  
  return 0;
}


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

namespace Reversing_Numbers
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();
            string line = Console.ReadLine();
            string[] strs = line.Split(' ');
            List<int> list = new List<int>();
            foreach (string str in strs)
            {
                list.Add(int.Parse(str));
            }

            ReversingNumbers problem = new ReversingNumbers();
            Console.WriteLine(problem.Show(list));
        }
    }

    public class ReversingNumbers
    {
        public String Show(List<int> list)
        {
            list.Reverse();
            String str = "";
            for (int i = 0; i < list.Count; i++)
            {
                str += list[i];
                if (i != list.Count - 1) str += " ";
            }
            return str;
        }
    }
}

Measured memory_bytes: 5708
//
// Created by 童正阳 on 2018/9/14.
// https://abc044.contest.atcoder.jp/tasks/arc060_a
// 动态规划：dp[i][j][k]表示前i个数中选j个和为k的方法数
// 那么有：dp[i][j][k] = dp[i-1][j-1][k-x[i]] + dp[i-1][j][k]
// 最终结果为：\sum{dp[N][x][A*x]}
//
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int N, A, x[51], sum[51];
ll dp[51][51][2501];
int main() {
    cin >> N >> A;
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= N; i++) {
        cin >> x[i];
        sum[i] = sum[i-1] + x[i];
    }
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k <= sum[i]; k++) {
                if (k >= x[i] && j >= 1) {
                    dp[i][j][k] += dp[i-1][j-1][k-x[i]] + dp[i-1][j][k];
                } else {
                    dp[i][j][k] += dp[i-1][j][k];
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += dp[N][i][i*A];
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 51072
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	string s; cin>>s;
	int n=s.size();
	for(int i=0; i<n; i++) if(s[i]=='?') s[i]='D';
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 3756
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
ll p, q, r;

ll pow(ll x, ll y)
{
	if (y == 0) return 1;
	if (y % 2)
	{
		return pow(x, y - 1) * x % mod;
	}
	else
	{
		ll yyy = pow(x, y / 2);
		return yyy * yyy % mod;
	}
}

ll div(ll x)
{
	return pow(x, mod - 2);
}

int main(void)
{
	cin >> p >> q >> r;
	ll ans = 10000000000;
	ans = min(ans, p + q);
	ans = min(ans, q + r);
	ans = min(ans, r + p);
	cout << ans << endl;
	int www;
	cin >> www;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <set>
#include <numeric>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);
// int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
// int a[12][12];
//平方根　= sqrt


string rotate(string s);

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

  int n = s.size();
  for (int i=0; i<n; i++) {
    if (s==t) {
      cout << "Yes" << endl;
      return 0;
    }
    s = rotate(s);
  }
  cout << "No" << endl;
  return 0;
}

string rotate(string s){
  return s.substr(1) + s[0];
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
#read = sys.stdin.buffer.read

sletter = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
bletter = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

def main():
    s = input()[:-1]
    if s in sletter:
        print('a')
    else:
        print('A')


if __name__ == "__main__":
    main()


Measured memory_bytes: 9104
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<=(b);++i)
#define ROF(i,b,a) for (int i=(b);i>=(a);--i)
typedef long long LL;
inline int read(){
	int x=0,f=1; char ch=getchar();
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	while (ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	return x*f;
}

const int MAXN=300005;
struct list{
	int l,lt[MAXN],nt[MAXN],x[MAXN];
	void clear(){ l=0; memset(lt,0,sizeof(lt)); }
	void addedge(int a,int b){ nt[++l]=lt[a]; lt[a]=l; x[l]=b; }
}E;
LL ans=0;
int n,m,q,a[MAXN],b[MAXN],c[MAXN];
int cmp(int i,int j){ return a[i]<a[j]; }
int dfs(int x,int fa){
	int ret=x; c[x]=1;
	for (int i=E.lt[x];i;i=E.nt[i]) {
		int j=E.x[i];
		if (j!=fa) {
			int k=dfs(j,x);
			if (a[k]<a[ret]) ret=k;
		}
	}
	return ret;
}
int main(){
	n=read(); m=read(); q=(n-1-m)*2; E.clear();
	if (q==0) { printf("0\n"); return 0; }
	//else if (q>n) { printf("Impossible\n"); return 0; }
	FOR(i,1,n) a[i]=read(),b[i]=i,c[i]=0;
	sort(b+1,b+1+n,cmp);
	//FOR(i,1,n) printf("%d%c",b[i]," \n"[i==n]);
	FOR(i,1,m) {
		int x=read()+1,y=read()+1;
		E.addedge(x,y),E.addedge(y,x);
	}
	FOR(i,1,n)
	if (!c[i]) {
		int x=dfs(i,0); ans+=a[x]; a[x]=0; q--;
		//printf("x=%d q=%d ans=%lld\n",x,q,ans);
	}
	if (q==0) { printf("%lld\n",ans); return 0; }
	FOR(i,1,n)
	if (a[b[i]]) {
		ans+=a[b[i]]; a[b[i]]=0; q--;
		if (q==0) { printf("%lld\n",ans); return 0; }
	}
	printf("Impossible\n");
	
	return 0;
}

/*
7 5
1 2 3 4 5 6 7
3 0
4 0
1 2
1 3
5 6

*/


Measured memory_bytes: 5632
/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

#include<bits/stdc++.h>
using namespace std;

#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)(x.size()))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     makep           make_pair
#define     maket           make_tuple
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)+(x)-1)/(x))
#define     gcd(a,b)        (__gcd((a),(b)))
#define     lcm(a,b)        (((a)*(b))/gcd((a),(b)))
#define     dbug(x)         cout<<#x<<": "<<(x)<<"\n"
#define     flush           fflush(stdout)
#define     show(x)         for(auto zz:x)cout<<zz<<" ";cout<<"\n";
#define     show2(x)        for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const ld pi=acos(-1);
const ll inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int a,b,c;
    cin>>a>>b>>c;

    int k;
    cin>>k;

    int ans;

    if(k<=a)
        ans=k;
    else
    {
        ans=a;
        k-=a;

        if(k<=b)
            ;
        else
        {
            k-=b;
            ans-=min(k,c);
        }
    }

    cout<<ans;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 3648
//killer_R@$tog!
#include<bits/stdc++.h>
using namespace std;
#define hell 1000000007
#define pb push_back
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a-1;i>=b;i--)
#define mp make_pair
#define fi first
#define se second
#define ub upper_bound
#define lb lower_bound
#define ll long long int
#define N 100009
#define all(b) b.begin(),b.end();
//int pr[N];
//int seg[N];
/*int query(int l,int r,int sl,int sr,int p)
{
    if(r<sl || l>sr)
        return 0;
    if(sr<=r && sl>=l)
        return seg[p];
    int m=sl+(sr-sl)/2;
    return (__gcd(query(l,r,sl,m,2*p+1),query(l,r,m+1,sr,2*p+2)));
}

int build(int l,int r,int p,int arr[])
{
    if(l==r)
    {
        seg[p]=arr[l];
        return seg[p];
    }
    int m=l+(r-l)/2;
    seg[p]=__gcd(build(l,m,2*p+1,arr),build(m+1,r,2*p+2,arr));
    return seg[p];
}
void isprime()
{
    memset(pr,1,sizeof(pr));
    pr[1]=0;
    for(int i=2;i*i<=N;i++)
    {
        if(pr[i])
        {
            for(j=i*i;j<=N;j+=i)
            {
                pr[j]=0;
            }
        }
    }
}*/
void killer()
{
    int n;cin>>n;double a[n+1];double dp[n+1][n+1];memset(dp,0,sizeof(dp));dp[0][0]=1;
    rep(i,1,n+1)
    cin>>a[i];
    rep(j,1,n+1)
    {
        rep(i,0,j+1)
        {
            if(i==0)
            {
                dp[i][j]=dp[i][j-1]*(1-a[j]);
            }
            else
            dp[i][j]=dp[i][j-1]*(1-a[j])+dp[i-1][j-1]*a[j];
        }
    }double ans=0;
    rep(i,n/2+1,n+1)
    {
        ans=ans+dp[i][n];
    }
    printf("%.10f",ans);
    return;
}
int main()
{
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif*/
    //int h=(int)ceil(log2(n));
    //h=2*(int)pow(2,h)-1;
    //build(0,n-1,0,a);

    ll t;
    t=1;
    while(t--)
        killer();

    return 0;
}

Measured memory_bytes: 70528
import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        init();

        BigInteger a = new BigInteger(next()), b = new BigInteger(next());
        System.out.println(a.multiply(b).divide(a.gcd(b)));
    }

    //Input Reader
    private static BufferedReader reader;
    private static StringTokenizer tokenizer;

    private static void init() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    private static String next() throws IOException {
        String read;
        while (!tokenizer.hasMoreTokens()) {
            read = reader.readLine();
            if (read == null || read.equals(""))
                return "-1";
            tokenizer = new StringTokenizer(read);
        }

        return tokenizer.nextToken();
    }
}

Measured memory_bytes: 21332