akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <functional>
#include <iomanip>
#include <bitset>
#include <numeric>
#include <queue>
#include <map>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
const long long mod = 1000000007;
typedef long long ll;
typedef pair<int, double> P;
const vector<int> di = {-1, 0, 1, 0};
const vector<int> dj = { 0, 1, 0, -1 };

int main() {

	string s;
	cin >> s;
	int len = s.size();
	ll sum = 0;
	for (int tmp = 0; tmp < (1 << (len - 1)); tmp++) {
		bitset<9> sb(tmp);
		int num = 0;
		for (int i = 0; i < (len - 1); i++) {
			if (sb.test(i)) {
				sum += stoi(s.substr(num, i + 1 - num));
				num = i + 1;
			}
			if (i == len - 2) {
				sum += stoll(s.substr(num, i + 2 - num));
			}
		}
	}
	if (len == 1) {
		sum = stoi(s);
	}
	cout << sum << endl;
	
	return 0;
}

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

N, M = map(int, input().split())
uf = UnionFind(N)
def int_(num):
    return int(num)-1
plist = list(map(int_, input().split()))
for _ in range(M):
    x, y = map(int, input().split())
    uf.union(x-1, y-1)
ans = 0
for i in range(N):
    if uf.same(i, plist[i]):
        ans += 1
print(ans)

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

using namespace std;

#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vi>
#define pi  pair<int,int>
#define mp  make_pair
#define pb  push_back
#define MOD int(1e9) + 7
#define PAI  3.1415926535
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define chmax(x, y) x = max(x,y)
#define chmin(x, y) x = min(x,y)
#define pr(x) cout << x << endl
#define Endl endl
#define rep(i, n) for(int i = 0 ; i < n; ++i)

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int ddx[8] = {-1,0,1,-1,1,-1,0,1};
const int ddy[8] = {-1,-1,-1,0,0,1,1,1};
const int inf = 99999999;
const ll linf = 1LL << 62;

ll gcd(ll a,ll b){
  if(a < b)swap(a , b);
  if(a % b != 0) return(gcd(b, a%b));
  return b;
}

ll lcm(ll a,ll b){
  if(a < b)swap(a , b);
  return (a / gcd(a , b)) * b;
}

int Uniform_random(int a, int b){

  random_device rd;
  mt19937 mt(rd());
  
  uniform_int_distribution<int> rv1(a, b);
  return rv1(mt);
  
}

int main(){

  int n;
  cin >> n;
  string s = "", t = "";
  
  for (int i = 0; i < n; i++)
  {
    char c; cin >> c;
    if(i < n / 2)
      s += c;
    else
      t += c;

  }
  
  if(s == t)
    cout << "Yes" << endl;
  else 
    cout << "No" << endl;

  return 0; 
}

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

using namespace std;
typedef pair<double, double> P;

double helon(P p1, P p2, P p3)
{
	double a = sqrt((p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second));
	double b = sqrt((p2.first - p3.first) * (p2.first - p3.first) + (p2.second - p3.second) * (p2.second - p3.second));
	double c = sqrt((p3.first - p1.first) * (p3.first - p1.first) + (p3.second - p1.second) * (p3.second - p1.second));
	double s = (a + b + c) / 2;
	return(sqrt(s * (s - a) * (s - b) * (s - c)));
}

void solve()
{
	P p[3];
	P xp;
	while(cin >> p[0].first >> p[0].second >> p[1].first >> p[1].second >> p[2].first >> p[2].second >> xp.first >> xp.second)
	{
		double square1 = helon(p[0], p[1], p[2]);
		double square2 = helon(p[0], p[1], xp);
		double square3 = helon(p[0], p[2], xp);
		double square4 = helon(p[1], p[2], xp);
		if(fabs(square1 - square2 - square3 - square4) < 1e-8)
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
}

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

Measured memory_bytes: 1216
#include<stdio.h>
int main()
{
	int n,m,a,h,p,q;
	while(scanf("%d%d%d",&n,&m,&a),n)
	{
		int l[1001][101]={0};
		while(m--)
		{
			scanf("%d%d%d",&h,&p,&q);
			l[h][p]=q;l[h][q]=p;
		}
		for(h=1000;h>0;--h)
			if(l[h][a])a=l[h][a];
		printf("%d\n",a);
	}
	return 0;
}

Measured memory_bytes: 0
T1, T2 = gets.split.map &:to_i
A1, A2 = gets.split.map &:to_i
B1, B2 = gets.split.map &:to_i
a1 = T1 * A1
a2 = T2 * A2
b1 = T1 * B1
b2 = T2 * B2
if a1 + a2 == b1 + b2
    puts :infinity
elsif (a1 - b1) * ((a1 - b1) + (a2 - b2)) > 0
    puts 0
else
    puts 2 * ((b1 - a1) / ((a1 - b1) + (a2 - b2))) + (((b1 - a1) % ((a1 - b1) + (a2 - b2)) == 0) ? 0 : 1)
end


Measured memory_bytes: 3836
#include <iostream>

using namespace std;

int N;

int main(){
    cin >> N;

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

    int m1 = -1;
    int i1 = -1;
    for(int i=0; i<N; i++){
        m1 = max(A[i], m1);
        if(A[i] == m1) i1 = i;
    }

    int m2 = -1;
    for(int i=0; i<N; i++){
        if(i1 != i){
            m2 = max(A[i], m2);
        }
    }

    for(int i=0; i<N; i++){
        if(i1 == i) cout << m2 << endl;
        else cout << m1 << endl;
    }

    return 0;

}

Measured memory_bytes: 2432
import sys
#input = sys.stdin.buffer.readline
from collections import defaultdict

def main():
    N = int(input())
    s = input()
    d1,d2,d3 = defaultdict(int),defaultdict(int),defaultdict(int) 
    
    for moji in s:
        for m2 in d2:
            d3[m2+moji] += 1
        for m1 in d1:
            d2[m1+moji] += 1
        d1[moji] += 1
    
    print(len(d3))
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 3572
/*+lmake
 * STD = c++14
 * DEFINE += WAAUTOMATON
 */
#include <bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#ifdef WAAUTOMATON
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;

LL cal(vector<LL>& a,LL b)
{
	LL ans=0;
	for(auto i:a) {
		ans+=abs(i-b);
	}
	return ans;
}
void solve(long long N, vector<long long> A){
	double sum=0;
	for(int i=0; i<N; ++i) {
		A[i]-=i+1;
		sum+=A[i];
	}	
	sort(A.begin(),A.end());
	LL ans;
	if (N%2!=0) 
		ans=cal(A,A[N/2]);
	else 
		ans=min(cal(A,(A[N/2]+A[N/2-1])/2),cal(A,(A[N/2]+A[N/2-1]/2)+1));
	cout<<ans<<endl;
}

int main(){	
#ifdef WAAUTOMATON
	//freopen("in.txt","r",stdin);
#endif
	long long N;
	scanf("%lld",&N);
	vector<long long> A(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&A[i]);
	}
	solve(N, A);
	return 0;
}



Measured memory_bytes: 3328
#include<cstdio>
#include<algorithm>
int main(){
    int n,a,k,ans=100;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        for(k=0;a%2==0;k++)a/=2;
        ans=std::min(ans,k);
    }
    printf("%d",ans);
    return 0;
}

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

using namespace std;

const int mod = 1e9 + 7;

int N, M;
int dp[301][301][301];

int rec(int step, int sc1, int out)
{
  if(step == M) return (sc1 == N);
  if(~dp[step][sc1][out]) return (dp[step][sc1][out]);
  int ret = 0;
  if(sc1 + out + 1 <= N) {
    (ret += 1LL * rec(step + 1, sc1, out + 1) * (N - sc1 - out) % mod) %= mod;
  }
  if(out > 0) {
    (ret += 1LL * rec(step + 1, sc1, out) * out % mod) %= mod;
  }
  (ret += 1LL * rec(step + 1, sc1 + out, 0) * sc1 % mod) %= mod;
  return (dp[step][sc1][out] = ret);
}

int main()
{
  cin >> N >> M;
  memset(dp, -1, sizeof(dp));
  cout << rec(0, 1, 0) << endl;
}

Measured memory_bytes: 106752
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

	int mod = 2019;
	vector<int> dp(s.length() + 1);
	int t = 1;
	for (int i = s.length() - 1; i >= 0; i--) {
		dp[i] = (s[i] - '0') * t + dp[i + 1];
		dp[i] %= mod;
		
		t *= 10;
		t %= mod;
	}

	int a[2019] = {};
	for (int i = 0; i <= s.length(); i++) {
		a[dp[i]]++;
	}

	long long ans = 0;
	for (int i = 0; i < 2019; i++) {
		ans += a[i] * (a[i] - 1) / 2;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4360
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
struct node
{
	string s;
	int p;
}word[200005];
int cmp(node a,node b)
{
	if(a.p==b.p)
		return  a.s<b.s;
	return  a.p>b.p;
}
string s[200005];
map<string,int>m;
int main(void)
{
	int n,i=0;
	cin>>n;
	for(int ii=0;ii<n;ii++)
	{
		string a;
		cin>>a;
		if(!m[a])
		{
			s[i++]=a;
		}
		m[a]++;
	}
	for(int ii=0;ii<i;ii++)
	{
		word[ii].s=s[ii];
		word[ii].p=m[s[ii]];
	}
	sort(word,word+i,cmp);
	int q=0;
	cout<<word[q].s<<endl;
	while(1)
	{
		q++;
		if(word[q].p==word[q-1].p)
			cout<<word[q].s<<endl;
		else
			break;
	}
	return 0;

}


Measured memory_bytes: 29952
//おまじない
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#define INF 1e9+7
#define rep(i,m,n) for(int i=m;i<n;i++)
#define mrep(i,m,n) for(int i=m;i<n;i--)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65
//おまじない



int main() {

	string a, b;
	cin >> a >> b;

	if (a.size() > b.size()) {
		cout << "GREATER" << endl;
		return 0;
	}
	else if (a.size() == b.size()) {
		rep(i, 0, a.size()) {
			if (a[i] > b[i]) {
				cout << "GREATER" << endl;
				return 0;
			}
			else if (a[i] < b[i]) {
				cout << "LESS" << endl;
				return 0;
			}
			else {
				continue;
			}
		}
	}
	else {
		cout << "LESS" << endl;
		return 0;
	}
	
	cout << "EQUAL" << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define int ll
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
#define r1 rt<<1
#define r2 rt<<1|1
#define fi first
#define se second
#define db double
#define ld long db
#define ri register int
#define rep(i,a,b) for(ri i=(a);i<=(b);++i)
#define rep2(i,a,b,c) for(ri i=(a);i<=(b);i+=(c))
#define REP(i,a,b) for(ri i=(a);i>=(b);--i)
#define REP2(i,a,b,c) for(ri i=(a);i>=(b);i-=(c))
using namespace std;

inline ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x*f;
}
string s[60];
int t[60];
signed main()
{
	ri n;ri x=0;cin>>n;
	rep(i,1,n){
		cin>>s[i]>>t[i];
	}
	string ss;cin>>ss;bool ok=0;
	rep(i,1,n){
		if(ok)x+=t[i];
		if(s[i]==ss)ok=1;
	}
	cout<<x;
	return 0; 
}

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

#ifdef _DEBUG
    #include "/home/v-o_o-v/deb.h"
    #define deb(x...)cerr << "[" << #x << "] = [";_print(x);
#else
    #define deb(x...)
#endif

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;

void a();void b();void c();void d();void e();void f();

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    // a();
    b();
    // c();
    // d();
    // e();
    // f();
    return 0;
}
// Write Here

void a(){
    int n;
    cin >> n;
    int amt = 0;
    while(amt < n)amt += 1000;
    cout << amt - n << '\n';
}

void b(){
    int n;
    cin >> n;
    map<string, int> m;
    while(n--){
        string s;
        cin >> s;
        m[s]++;
    }
    string a[] = {"AC", "WA", "TLE", "RE"};
    for(int i = 0; i < 4; i++)cout << a[i] << " x " << m[a[i]] << '\n';
}

void c(){

}

void d(){

}

void e(){

}

void f(){

}

Measured memory_bytes: 3668
n = int(input())

from collections import defaultdict
d = defaultdict(int)

ul=int(n**0.5)

for i in range(1,ul):
  for j in range(1,ul):
    for k in range(1,ul):
      d[i**2+j**2+k**2+i*j+j*k+k*i]+=1
for j in range(1,n+1):
  print(d.get(j,0))
#  print(d[j] if d[j] else 0)
    

Measured memory_bytes: 11912
#define __USE_MINGW_ANSI_STDIO
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef long long ull;
typedef pair<int, int> ii;

#define all(v)		((v).begin()), ((v).end())
#define sz(v)		((int)((v).size()))
#define endl		"\n"
#define fx(n)		fixed<<setprecision(n)
#define mk			make_pair	

void fast()
{
	ios::sync_with_stdio(NULL);
	cout.tie(NULL);
	cin.tie(NULL);
/*#ifndef ONLINE_JUDGE
	freopen("output.txt", "w", stdout);
	freopen("input.txt", "r", stdin);
#endif
#ifdef ONLINE_JUDGE
	/*freopen("output.txt", "w", stdout);
	freopen("pyramid.in", "r", stdin);
#endif*/
}
const double pi = 2 * acos(0.0);
const ll oo = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int nn = 2e2 + 15;
int dx[8] = { -1, 0, 0, 1, 1, -1, 1, -1 };
int dy[8] = { 0, -1, 1, 0, 1, -1, -1, 1 };

int main()
{
	fast();
	ll a, b, c;
	cin >> a >> b >> c;
	cout << ceil(double(c) / max(a, b)) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define N 100000

int main() {
	static int pp[N];
	int n, i, tmp, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &pp[i]);
	ans = 0;
	for (i = 0; i < n; i++)
		if (pp[i] == i + 1) {
			ans++;
			if (i < n - 1) {
				tmp = pp[i];
				pp[i] = pp[i + 1];
				pp[i + 1] = tmp;
			} else {
				tmp = pp[i - 1];
				pp[i - 1] = pp[i];
				pp[i] = tmp;
			}
		}
	printf("%d\n", ans);
	return 0;
}


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

int main() {
    int N;
    long long x;
    cin >> N >> x;
    vector<long long> a(N);
    vector< vector<long long> > b(N, vector<long long>(N));
    for(int i=0; i<N; ++i) {
        cin >> a[i];
        b[0][i] = a[i];
    }

    long long res = accumulate(a.begin(), a.end(), 0LL);
    for(int k=1; k<N; ++k) {
        long long tmp = k * x;
        for(int i=0; i<N; ++i) {
            b[k][i] = min(b[k - 1][i], a[(i - k + N) % N]); 
            tmp += b[k][i];
        }
        res = min(res, tmp);
    }

    cout << res << endl;
}

Measured memory_bytes: 31616
#include<iostream>
using namespace std;main(){int n,h,H,a,b;for(cin>>n;cin>>n;cout<<a<<" "<<-b<<endl)for(cin>>h,a=b=0;--n>0;a<H-h&&(a=H-h),H-h<b&&(b=H-h),h=H)cin>>H;}

Measured memory_bytes: 0
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <map>
#include <utility>

using namespace std;

#define ll long long

void solve()
{
    ll N;
    cin >> N;
    vector<ll> H(N);
    ll maxCount = 0;
    ll count = 0;
    for (ll i = 0; i < N; i++)
    {
        cin >> H.at(i);
        if (i != 0 && H.at(i - 1) < H.at(i))
        {
            count = 0;
        }
        count++;
        maxCount = max(maxCount, count);
    }

    cout << maxCount - 1 << endl;
}

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


Measured memory_bytes: 1152
// Reads multiple ints in a line, separate by a space.
// It works even if the actual number of ints is smaller than n.
// WARNING: This function does not work for -2^31.
// NOTE: This function does not handle error cases.
fun fastReadInts(n: Int): IntArray {
  val xs = IntArray(n)
  val s = readLine()!!
  var currentValue = 0
  var isNegative = false
  var currentIndex = 0
  for (c in s) {
    if (c == ' ') {
      xs[currentIndex] = currentValue * if (isNegative) -1 else 1
      currentValue = 0
      isNegative = false
      currentIndex++
    } else if (c == '-') {
      isNegative = true
    } else {
      currentValue *= 10
      currentValue += c - '0'
    }
  }
  xs[currentIndex] = currentValue * if (isNegative) -1 else 1
  return xs
}

fun main(args: Array<String>) {
  val n = readLine()!!.toInt()
  val xs = LongArray(n)
  val ys = LongArray(n)
  repeat(n) {
    val (x, y) = fastReadInts(2)
    xs[it] = x.toLong()
    ys[it] = y.toLong()
  }

  if ((0 until n).all { xs[it] == ys[it] }) {
    println(0)
    return
  }

  val r = (0 until n).filter { xs[it] > ys[it] }.map { ys[it] }.min()!!
  println(xs.sum() - r)
}

Measured memory_bytes: 41072
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }

    input!{
      s: chars,
    }
    let n = s.len();
    let mut dp = vec![vec![0; 4]; n];

    for i in 0..n {
        for j in 0..4 {
            for k in 0..4 {
                if i + j >= n {
                    continue;
                }
                if i < (k+1) {
                    dp[i][j] = max(dp[i][j], 1);
                    continue;
                }
                if j == k {
                    let s1 = &s[i..i+j+1];
                    let s2 = &s[i-j-1..i];
                    if s1 == s2 {
                        continue;
                    }
                }
                dp[i][j] = max(dp[i-k-1][k] + 1, dp[i][j]);
            }
        }
    }
    let mut ans = 0;
    for j in 0..3 {
        ans = max(ans, dp[n-j-1][j]);
    }
    puts!("{}\n", ans);
}


Measured memory_bytes: 14588
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    map<string,int> memo;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        memo[s]++;
    }

    int maxv=0;
    for(const auto& x:memo){
        int v=x.second;
        maxv=max(maxv,v);
    }
    for(auto it=memo.begin();it!=memo.end();it++){
        if(it->second==maxv){
            cout<<it->first<<endl;
        }
    }
}

Measured memory_bytes: 25216
import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	static int d;
	public static void main(String[] args) {
		while(read()){
			solve();
		}
	}
	static boolean read(){
		if(!sc.hasNext())
			return false;
		d = sc.nextInt();
		return true;
	}
	static void solve(){
		int devide = 0;
		devide = 600 / d;
		int x = 0;
		int y = 0;
		int Sum = 0;
		for(int i = 1; i < devide; i++){
			x = x + d;
			y = x*x;
			Sum = Sum + d*y;
		}
		System.out.println(Sum);

	}

}

Measured memory_bytes: 12000
#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<set>
#include<cstdlib>
using namespace std;
typedef long long ll;
int main(void)
{
	ll a,b,n;
	cin>>a>>b>>n;
	ll ma=0;
	if(n>=b) n=b-1;
	cout<<n*a/b;
}

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

int main(){
  int k=0,s=0;
  
  cin >> k >> s;
  
  int ans=0;
  
  for(int x=0;x<=k;x++){
  	for(int y=0;y<=k;y++){
    	int z = s-x-y;
      	if(z >= 0 && z <= k){
        	ans += 1;
        }
    }
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3592
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;

long long GCD(long long a, long long b) {
    if(b == 0)
        return a;
    else
        return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
    long long g = GCD(a, b);
    return a / g * b;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    int N;
    cin >> N;
    vector<int> a(N + 1);
    int tmp = 0;
    int sum = 0;
    rep(i, 0, N) {
        cin >> a[i];
        sum += abs(tmp - a[i]);
        tmp = a[i];
    }
    sum += abs(0 - a[N - 1]);
    int mae = 0;
    a[N] = 0;
    rep(i, 0, N) {
        int ato = a[i + 1];
        int t = sum - (abs(a[i] - mae)) - (abs(a[i] - ato)) + (abs(ato - mae));
        mae = a[i];
        cout << t << endl;
    }
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define inf (int)(1e8)
using namespace std;

struct dat {
  int x, y, cost;
  dat(int _x, int _y, int c = 0) : x(_x), y(_y), cost(c) {}
  bool operator<(const dat& r) const { return cost > r.cost; }
};

using P = pair<int, int>;
int h, w, sx, sy, gx, gy;
vector<string> s;
vector<vector<int>> dist;
int d[4] = {0, 1, 0, -1};

int solve();
bool isvalid(int x, int y) {
  return x >= 0 && x < h && y >= 0 && y < w && s[x][y] == '.';
}

int main() {
  cin >> h >> w >> sx >> sy >> gx >> gy;
  --sx, --sy, --gx, --gy;
  dist.assign(h, vector<int>(w, inf));
  s.resize(h);
  for (auto& p : s) cin >> p;
  cout << solve() << endl;
  return 0;
}

int solve() {
  priority_queue<dat> pq;
  pq.push(dat(sx, sy, 0));
  dist[sx][sy] = 0;
  while (pq.size()) {
    auto [x, y, c] = pq.top();
    pq.pop();
    if (dist[x][y] != c) continue;

    for (int i = 0; i < 4; ++i) {
      int nx = x + d[i], ny = y + d[i ^ 1];
      if (!isvalid(nx, ny)) continue;
      if (dist[nx][ny] > c) {
        dist[nx][ny] = c;
        pq.push(dat(nx, ny, c));
      }
    }

    for (int i = -2; i <= 2; ++i)
      for (int j = -2; j <= 2; ++j) {
        int nx = x + i, ny = y + j;
        if (!isvalid(nx, ny)) continue;
        if (dist[nx][ny] > c + 1) {
          dist[nx][ny] = c + 1;
          pq.push(dat(nx, ny, c + 1));
        }
      }
  }
  if (dist[gx][gy] == inf) return -1;
  return dist[gx][gy];
}


Measured memory_bytes: 9604
#include <bits/stdc++.h>
#define base 1000000007LL
#define ll long long
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define CLR(a) memset(a,0,sizeof(a))
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORE(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)

using namespace std;

typedef pair<int, int> II;
typedef vector<II> vi;

string s;
int f[30];

int main()
{
    ios::sync_with_stdio(0);
    //freopen("inp.txt", "r", stdin);
    cin >> s;
    FOR(i,0,s.length()-1) f[s[i]-'a']++;
    FOR(i,0,25)
        if (f[i] & 1) {
            cout << "No";
            return 0;
        }
    cout << "Yes";
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  int sum = 0, tmp = n;
  while (tmp > 0) {
    sum += tmp % 10;
    tmp /= 10;
  }
  if (n % sum == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits>
#include <map>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <stack>
#include <cstring>

typedef long long li;
using namespace std;

li max(li a, li b) {
    return a > b ? a : b;
}

li max(li a, li b, li c) {
    return max(a, max(b, c));
}

li max(li a, li b, li c, li d) {
    return max(a, max(b, max(c, d)));
}

li max(li a, li b, li c, li d, li e) {
    return max(a, max(b, max(c, max(d, e))));
}


li pow_mod(li n, li e, li mod)
{
    li r = 1;
    
    while(e > 0)
    {
        if(e & 1)
            r *= n;
            r %= mod;
        
        n *= n;
        n %= mod;
        e >>= 1;
    }
    
    return r;
}
void dfs(int n, string & s, vector<int> visited, int & cnt, unordered_map<string, int> & m) {
    if (s.length() == n) {
        m[s] = cnt++;
        return;
    }
    
    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0) {
            visited[i] = 1;
            s += (i + '0');
            dfs(n, s, visited, cnt, m);
            s.pop_back();
            visited[i] = 0;
        }
    }
}

int main() {
    // ifstream fin("read.txt");
    int n, cnt = 0;
    string s1 = "", s2 = "";
    char c;
    unordered_map<string, int> m;
    cin >> n;
    vector<int> visited(n + 1, 0);
    
    
    for (int i = 0; i < n; i++) {
        cin >> c;
        s1 += c;
    }
    
    for (int i = 0; i < n; i++) {
        cin >> c;
        s2 += c;
    }
    
    string str = "";
    
    dfs(n, str, visited, cnt, m);
    
    int ans = abs(m[s1] - m[s2]);
    
    cout << ans << endl;
    
    
    return 0;
}








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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	string s;
	cin>>s;
	while(s.size()){
		s.pop_back();
		if(s.size()%2==1)continue;
		int size=s.size();
		string a=s.substr(0,size/2);
		string b=s.substr(size/2);
		if(a==b)break;
	}
	cout<<s.size()<<"\n"s;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        int r = sc.nextInt();
        int D = sc.nextInt();
        int x = sc.nextInt();

        sc.close();

        for(int i=1; i<=10; i++){
            x = r * x - D;
            System.out.println(x);
        }


    }
}

Measured memory_bytes: 21972
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main() {
    ll n,v[25],c[25];
    
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> v[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> c[i];
    }
    ll result = 0;
    
    for (int i = 0; i < n; i++) {
        if(v[i]-c[i]>0){
            result += v[i]-c[i];
        }
    }
    
    
    std::cout << result << std::endl;
    
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<math.h>
#include<time.h>

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)

typedef long long i64;
typedef pair<i64,i64> P;


i64 a,b;

int main(){
	cin >> a >> b;
	
	i64 ans = 0;
	i64 A, B;
	if((a-1) % 2) A = (a/2%2);
	else A = a-1 + ((a-1)/2%2);
	if(b % 2) B = ((b+1)/2%2);
	else B = b + (b/2%2);
	ans = A^B;
	cout << ans << endl;
	
	return 0;
}

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

int main(){
  double N, K;
  cin >> N >> K;
  
  double ans = 0.0;
  for(int i = 0;i < N;i++){
    double score = i + 1;
    double prob = 1 / N;
    while(score < K){
      prob /= 2;
      score *= 2;
    }
    ans += prob;
  }
  
  cout << fixed << setprecision(10);
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3768
def main():
    n = int(input())
    X = [int(x) for x in input().split()]
    min_x = min(X)
    max_x = max(X)
    min_e = 10**6
    for i in range(min_x, max_x+1):
        error = 0
        for x in X:
            error += (x-i) ** 2
        min_e = min(min_e, error)
    print(min_e)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9188
from fractions import gcd

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
if max(a) < k:
    print("IMPOSSIBLE")
    exit()
x = a[0]
for i in range(1,n):
    x = gcd(x, a[i])

print("IMPOSSIBLE" if k % x else "POSSIBLE")


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

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

	int cnt=0, tgt=1;
	for(int i=0;i<n;i++){
		if(a[i]==tgt){
			++tgt;	continue;
		}else{
			cnt++;
		}
	}

	//cout<<"cnt: "<<cnt<<endl;

	if(cnt==n)cout<<"-1"<<endl;
	else cout<<cnt<<endl;

	return 0;
}


Measured memory_bytes: 1024
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  a,b,x=LI()

  c=(2*x)/(a*a)-b

  if c>=0:
    tanx=(b-c)/a
    return math.degrees(math.atan(tanx))

  c=(2*x)/(a*b)
  tanx=b/c
  return math.degrees(math.atan(tanx))

# main()
print(main())


Measured memory_bytes: 6444
L = int(input())
r = 0
while 2 ** r <= L:
    r += 1
r -= 1

ans = []
N = r + 1
for i in range(1, N):
    ans.append((i, i + 1, 0))
    ans.append((i, i + 1, 2 ** (i - 1)))
    
for t in range(N - 1, 0, -1):
    if L - 2 ** (t - 1) >= 2 ** r:
        ans.append((t, N, L - 2 ** (t - 1)))
        L -= 2 ** (t - 1)
        
print(N, len(ans))
for i in ans:
    print(i[0], i[1], i[2])

Measured memory_bytes: 3064
function Main (S) {
  S = String(S.split("\n")[0]).split("");
  if (S[0] == S[1] || S[1] == S[2] || S[2] == S[3]) {
    console.log("Bad");
  }
  else {
    console.log("Good");
  }
}

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

Measured memory_bytes: 9420
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N, D = next(it), next(it)

    d2 = D**2
    ans = 0
    for x, y in zip(it, it):
        if x**2 + y**2 <= d2:
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 107916
use std::collections::HashSet;

pub struct Scanner{
    line : Vec<String> ,
    idx : usize
}

#[allow(dead_code)]
impl  Scanner{
   fn new() -> Scanner{
       return Scanner{ line: vec![], idx : 0}
   }
   fn next<T: std::str::FromStr> (&mut self) -> T{
       if self.idx == self.line.len() {
           let mut buffer = String::new();
           std::io::stdin().read_line(&mut buffer).ok();

           let a : Vec<&str>  = buffer.trim().split(' ').collect();
           self.line = a.iter().map(|&s| String::from(s)).collect();
           self.idx = 0;
       }
       let ret : T = self.line[self.idx].parse::<T>().ok().expect("Parse error.");
       self.idx += 1;
       ret
   }
   fn next_string(&mut self) -> Vec<char> {
       let s : String = self.next();
       return s.chars().collect::<Vec<char>>();
   }
   fn next_vec<T: std::str::FromStr>  (&mut self, n: usize) -> Vec<T>{
       let mut v : Vec<T>= Vec::with_capacity(n);
       for _i in 0..n {
           v.push(self.next());
       }
       v
   }
}


fn main() {
    let mut scan = Scanner::new();
    let n:i64 = scan.next();
    let mut k = HashSet::new();
    
    for i in 2..n {
        if (n - 1) % i == 0{
            k.insert(i);
            k.insert((n - 1) / i);
        }
        if i*i > n{
            break;
        }
    }
    if n > 2{
        k.insert(n - 1);
    }
    for i in 2..n {
        let mut m = n; 
        while m % i == 0{
            m /= i;
        }
        if m % i == 1{
            k.insert(i);
        }
        if n % i == 0 && i != n/i{
            let mut m = n;
            let x = n / i; 
            while m % x == 0{
                m /= x;
            }
            if m % x == 1{
                k.insert(x);
            }      
        }

        if i*i > n{
            break;
        }
    }
    k.insert(n);
    println!("{}", k.len());
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>
#include <queue>


using namespace std;

int main() {
    string s;

    cin >> s;
    if (s[0] + s[1] + s[2] + s[3] - 4 * 48 == 7) {
        cout << s[0] << '+' << s[1] << '+' << s[2] << '+' << s[3] << "=7";
    }
    else if (s[0] - s[1] + s[2] + s[3] - 2 * 48 == 7) {
        cout << s[0] << '-' << s[1] << '+' << s[2] << '+' << s[3] << "=7";
    }
    else if (s[0] + s[1] - s[2] + s[3] - 2 * 48 == 7) {
        cout << s[0] << '+' << s[1] << '-' << s[2] << '+' << s[3] << "=7";
    }
    else if (s[0] + s[1] + s[2] - s[3] - 2 * 48 == 7) {
        cout << s[0] << '+' << s[1] << '+' << s[2] << '-' << s[3] << "=7";
    }
    else if (s[0] - s[1] - s[2] + s[3] == 7) {
        cout << s[0] << '-' << s[1] << '-' << s[2] << '+' << s[3] << "=7";
    }
    else if (s[0] - s[1] + s[2] - s[3] == 7) {
        cout << s[0] << '-' << s[1] << '+' << s[2] << '-' << s[3] << "=7";
    }
    else if (s[0] + s[1] - s[2] - s[3] == 7) {
        cout << s[0] << '+' << s[1] << '-' << s[2] << '-' << s[3] << "=7";
    }
    else if (s[0] - s[1] - s[2] - s[3] + 2 * 48 == 7) {
        cout << s[0] << '-' << s[1] << '-' << s[2] << '-' << s[3] << "=7";
    }

    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long ll;
int main()
{
    ll a,b,c,d,n;
    scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&n);
    ll aa=a*8,bb=b*4,cc=c*2;
    ll ans=min(min(min(aa,bb),cc),d);
    ll sum=0;
    sum+=n/2*ans;
    n-=n/2*2;
    aa=a*4,bb=b*2;
    ans=min(min(aa,bb),c);
    sum+=n*ans;
    printf("%lld\n",sum);
}


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

struct node { int p, l, r; };
node t[25];

void pre(int u) {
	if (!~u)return;
	printf(" %d", u);
	pre(t[u].l); pre(t[u].r);
}
void in(int u) {
	if (!~u)return;
	in(t[u].l);
	printf(" %d", u);
	in(t[u].r);
}
void post(int u) {
	if (!~u)return;
	post(t[u].l);
	post(t[u].r);
	printf(" %d", u);
}
int main() {
	int n; scanf("%d", &n);
	rep(i, n)t[i].p = -1;
	rep(i, n) {
		int id, l, r; scanf("%d%d%d", &id, &l, &r);
		t[id].l = l; t[id].r = r;
		t[l].p = t[r].p = id;
	}
	int r = 0;
	rep(i, n) {
		if (!~t[i].p) { r = i; break; }
	}
	puts("Preorder"); pre(r); puts("");
	puts("Inorder"); in(r); puts("");
	puts("Postorder"); post(r); puts("");
}

Measured memory_bytes: 3208
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
using namespace std;
int main()
{
    double n, l, i, a, ans=0;
    scanf("%lf%lf",&n,&l);
    a=l;
    int la=abs(l);
    for(double i=1; i<=n; i++)
    {
        ans+=a++;
    }
    if(l>=0)
        ans-=l;
    else if((l+n-1)<=0)
        ans-=(l+n-1);
    cout << ans << '\n';
}

Measured memory_bytes: 256
class Dice:
    def __init__(self):
        self.d = list(map(int, input().split()))

    def setNum(self, n0, n1, n2, n3, n4, n5):
        self.d[0], self.d[1], self.d[2], self.d[3], self.d[4], self.d[5] = (
            n0,
            n1,
            n2,
            n3,
            n4,
            n5,
        )

    def roll(self, direction):
        if direction == "E":
            self.setNum(
                self.d[3], self.d[1], self.d[0], self.d[5], self.d[4], self.d[2]
            )
        elif direction == "N":
            self.setNum(
                self.d[1], self.d[5], self.d[2], self.d[3], self.d[0], self.d[4]
            )
        elif direction == "S":
            self.setNum(
                self.d[4], self.d[0], self.d[2], self.d[3], self.d[5], self.d[1]
            )
        elif direction == "W":
            self.setNum(
                self.d[2], self.d[1], self.d[5], self.d[0], self.d[4], self.d[3]
            )

    def top(self):
        return self.d[0]


dice = Dice()
o = list(map(str, input()))

for i in o:
    dice.roll(i)
print(dice.top())



Measured memory_bytes: 5608
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int n,m;
 map<string, int> map{};
 cin>>n;
 for(int i = 0; i < n; i++){
   string s;
   cin>>s;
   if(map.count(s)){
     map[s]++;
   }
   else{
     map[s];
   }
 }
 cin>>m;
 for(int i = 0; i < m; i++){
   string s;
   cin>>s;
   if(map.count(s)){
     map[s]--;
   }
   else{
     map[s];
   }
 }
 int ans = -1;
 for(pair<string,int> element : map){
   if(element.second > ans){
     ans = element.second;
   }
 }
 if(ans < 0){
        cout << 0 << endl;
    }else{
        cout << ans+1 << endl;
    }
}

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

using namespace std;



int main() {
	int n, k;
	int dp[101][10] = {0};
	int data[101] = {0};
	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int a;
		cin >> a;
		cin >> data[a];

	}
	if (data[1] != 0) {
		if (data[2] != 0) {
			dp[2][data[2] + 3 * (data[1] - 1)] = 1;
		}
		else {
			for (int i = 1; i <= 3; i++) {
				int b = (data[1]-1)*3 + i;
				dp[2][b] = 1;
			}
		}
	}
	else {
		if (data[2] != 0) {
			for (int i = 0; i < 3; i++) {
				int c = i * 3 + data[2];
				dp[2][c] = 1;
			}
		}
		else {
			for (int i = 1; i <= 9; i++) {
				dp[2][i] = 1;
			}
		}
	}
	for (int i = 3; i <= n; i++) {
		if (data[i] != 0) {
			for (int j = 0; j < 3; j++) {
				int k = data[i] + j * 3;
				for (int l = 0; l < 3; l++) {
					int m = j+1+ l * 3;
					int o = 0;
					if (m == 1 || m == 5 || m == 9) {
						if (k == m) {
							o = 1;
						}
						
					}
					if(o==0){
						dp[i][k] += dp[i - 1][m];
					}
					o = 0;
				}
			}
		}
		else {
			for (int j = 1; j <= 9; j++) {
				if (j <= 3) {
					if (j == 1) {
						dp[i][1] += dp[i - 1][4] + dp[i - 1][7];
					}
					else {
						dp[i][j] += dp[i - 1][1] + dp[i - 1][4] + dp[i - 1][7];
					}
				} 
				else if (j >= 4 && j <= 6) {
					if (j == 5) {
						dp[i][5] += dp[i - 1][2] + dp[i - 1][8];
					}
					else {
						dp[i][j] += dp[i - 1][2] + dp[i - 1][5] + dp[i - 1][8];
					}
				}
				else {
					if (j == 9) {
						dp[i][9] += dp[i - 1][3] + dp[i - 1][6];
					}
					else {
						dp[i][j] += dp[i - 1][3] + dp[i - 1][6] + dp[i - 1][9];

					}
				}
			}
		}
		for (int j = 1; j <= 9; j++) {
			if (dp[i][j] >= 10000) {
				dp[i][j] = dp[i][j] % 10000;
			}
		}
	}
	int z = 0;
	for (int i = 1; i <= 9; i++) {
		z += dp[n][i];
		if (z >= 10000) {
			z = z % 10000;
		}
	}
	cout << z << endl;
	return 0;
}

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

long long n;
map<long long, int> mp;
vector<long long> v;

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i) {
    long long a;
    cin >> a;
    ++mp[a];
    if(mp[a] == 2) {
      mp[a] = 0;
      v.push_back(a);
    }
  }
  sort(v.begin(), v.end(), greater<long long>());
  if(v.size() < 2)
    cout << 0 << endl;
  else {
    cout << v[0] * v[1] << endl;
  }
  return 0;
}

Measured memory_bytes: 6528
import math
import itertools

N,P = [int(i) for i in input().split(" ")]
A = [int(i) for i in input().split(" ")]
k = 0
for i in range(N):
    if int(A[i] % 2) == P:
        k += 1

if k == 0:
    if P == 0:
        tmp = 0
        i = 0
        while i <= N-k:
            tmp += int(math.factorial(N-k)/(math.factorial(N-k-i)*math.factorial(i)))
            i += 2
        print(tmp)
    elif P == 1:
        print(0)
else:
    tmp = 0
    i = 0
    while i <= N-k:
        tmp += int(math.factorial(N-k)/(math.factorial(N-k-i)*math.factorial(i)))
        i += 2
    print(pow(2,k)*tmp)


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <cmath>
#include <ios>
#include <ctype.h>
#include <stack>
#include <istream>
#include <stdio.h>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <functional>
#include <bitset>
#include <list>
#include <deque>
#include <time.h>
#include <random>
#include <iomanip>
#include <fstream>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
ll ceil(const ll a, const ll b) { return (a + b - 1) / b; }
class cum_sum{
  private:
    vector<long long>sum;
    vector<long long>tmp;
    int n;
  public:
    cum_sum(vector<long long>v):tmp(v),n(v.size()){
      sum.resize(n + 1);
      for(int i = 0; i < n; i++){
        sum[i + 1] = sum[i] + tmp[i];
      }
    };
    long long range_sum(int l, int r){
      if(l > r)swap(l,r);
      return sum[r + 1] - sum[l];
    }
}; 
int main(){
  int n;
  cin >> n;
  vector<ll>v(n);
  rep(i,n)cin >> v[i];
  sort(all(v));
  reverse(all(v));
  cum_sum sum(v);
  int ans = 1;
  REP(i,1,n){
    if(v[i - 1] <= sum.range_sum(i,n - 1) * 2)ans++;
    else break;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3328
/*
	In the name of Allah.
*/

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
#define gap ' '
#define INF 99999999
 
const int MAXN = 2 * 1e5 + 5;


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

    return 0;
}


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

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

  if (d <= s*t) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
char s[SIZE];
int dp[SIZE][4];
int an;
template <class T>
void maa(T& x,T y){
    if(x<y)x=y;
}
template <class T>
void mii(T& x,T y){
    if(x>y)x=y;
}
void solve(VI& d){
    REP(i,SZ(d))REP(j,4)dp[i][j]=-1;
    dp[0][0]=0;
    REP(i,SZ(d)-1){
        REP(j,4)maa(dp[i+1][0],dp[i][j]);
        if(dp[i][0]!=-1){
            if(d[i+1]==1){
                maa(dp[i+1][1],dp[i][0]+d[i]);
            }
            else{
                maa(dp[i+1][1],dp[i][0]+d[i+1]);
                maa(dp[i+1][2],dp[i][0]+d[i+1]-1);
                maa(dp[i+1][3],dp[i][0]+d[i]);
            }
        }
        if(dp[i][2]!=-1){
            if(d[i+1]==1){
                maa(dp[i+1][1],dp[i][2]+1);
            }
            else{
                maa(dp[i+1][1],dp[i][2]+d[i+1]);
                maa(dp[i+1][2],dp[i][2]+d[i+1]-1);
            }
        }
        if(dp[i][3]!=-1){
            if(d[i+1]==1){
                maa(dp[i+1][1],dp[i][3]+d[i]-1);
            }
            else{
                maa(dp[i+1][1],dp[i][3]+d[i+1]);
                maa(dp[i+1][2],dp[i][3]+d[i+1]-1);
                maa(dp[i+1][3],dp[i][3]+d[i]-1);
            }
        }
    }
    int ma=0;
    REP(i,4){
        ma=max(ma,dp[SZ(d)-1][i]);
    }
    an+=ma;
}
int main(){
    DRI(N);
    RS(s);
    VPII pp;
    for(int i=0,j;i<N;i=j){
        if(s[i]=='0'){
            j=i+1;
        }
        else{
            for(j=i+1;j<N&&s[j]=='1';j++);
            pp.PB(MP(i,j));
        }
    }
    for(int i=0,j;i<SZ(pp);i=j){
        VI d;
        d.PB(pp[i].S-pp[i].F);
        for(j=i+1;j<SZ(pp)&&pp[j].F==pp[j-1].S+1;j++){
            d.PB(pp[j].S-pp[j].F);
        }
        solve(d);
    }
    printf("%d\n",an);
    return 0;
}


Measured memory_bytes: 3448
//
//  main.cpp
//  070Cgo home
//
//  Created by zhangdenny on 2017/7/21.
//  Copyright © 2017年 Kirito. All rights reserved.
//

#include  <functional>
#include  <algorithm>
#include  <exception>
#include  <stdexcept>
#include  <streambuf>
#include  <iterator>
#include  <string.h>
#include  <stdlib.h>
#include  <typeinfo>
#include  <valarray>
#include  <iostream>
#include  <sstream>
#include  <istream>
#include  <stdio.h>
#include  <climits>
#include  <clocale>
#include  <complex>
#include  <csetjmp>
#include  <csignal>
#include  <cstdarg>
#include  <cstddef>
#include  <ctype.h>
#include  <cassert>
#include  <cstdlib>
#include  <utility>
#include  <cstring>
#include  <numeric>
#include  <ostream>
#include  <cwctype>
#include  <fstream>
#include  <iomanip>
#include  <math.h>
#include  <bitset>
#include  <cctype>
#include  <string>
#include  <vector>
#include  <limits>
#include  <locale>
#include  <memory>
#include  <cerrno>
#include  <iosfwd>
#include  <cfloat>
#include  <cstdio>
#include  <cwchar>
#include  <cmath>
#include  <ctime>
#include  <deque>
#include  <queue>
#include  <stack>
#include  <list>
#include  <ios>
#include  <map>
#include  <set>
#include  <new>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=50000;
int x;
int sum[maxn];
int main()
{
    for(int i=1;i<=maxn;i++)
        sum[i]=sum[i-1]+i;
    cin>>x;
    int ans=lower_bound(sum,sum+maxn,x)-sum;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 384