akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
//#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define se second
#define fi first
#define pai acos(-1)
#define maxe max_element
#define mine min_element
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(itr,s) for(itr=s.begin();itr!=s.end();itr++)
#define W while
#define pp pair<ll,ll>
#define ppi pair<ll,ll>
#define vl vector<ll>
#define vll vector<pp >
#define vi vector<int>
#define vii vector<ppi>
#define debug(x) cerr<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;
#define debug4(x,y,z,w) cerr<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\t"<<#w<<" :: "<<w<<endl;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define boost  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define SIZE 5000 + 1
const ll MAX=1e9;
const ll mod=1e9+7;

ll expo(ll x,ll n,ll M=mod){
    ll ans=1;
    while(n>0)
    {
        if(n&1){ans=(ans*x)%M;}
                x=(x*x)%M;
                n>>=1;
    }
    return ans;
}

vl adj[200001];
ll c[200001],sum[200001],sz[200001],ans[200001];
ll n;
ll dfs1(ll u,ll pa)
{
    ll i;
    ll cc=0;
    fn(i,adj[u].size())
    {
        if(adj[u][i]==pa)continue;
        cc+=dfs1(adj[u][i],u);
    }
    sz[u]=cc;
    return cc+1;
}

void dfs2(ll u,ll pa)
{
    ll i;
    ll temp=0;
    if(sum[c[u]]!=0)
    {
      temp=sum[c[u]];
      sum[c[u]]=0;
    }
    fn(i,adj[u].size())
    {
        if(adj[u][i]==pa)continue;
        dfs2(adj[u][i],u);
       // debug3(sz[adj[u][i]],sum[c[u]],u);
        ans[c[u]]-=((sz[adj[u][i]]+1-sum[c[u]])*(sz[adj[u][i]]+1-sum[c[u]]+1))/2;
        sum[c[u]]=0;
    }
    sum[c[u]]=temp+sz[u]+1;
}

void intial()
{
    ll i;
    fs(i,1,n+1)
    {
        ans[i]=(n*(n+1))/2;
    }
}

void solve()
{
    ll i;
  cin>>n;
  map<ll,ll> mp;
  set<ll> st;
  fs(i,1,n+1){cin>>c[i];mp[c[i]]++;st.insert(c[i]);}
  fs(i,1,n)
  {
      ll u,v;
      cin>>u>>v;
      adj[u].pb(v);adj[v].pb(u);
  }
   intial();
  dfs1(1,0);
  dfs2(1,0);
  set<ll> ::iterator itr;
  for(itr=st.begin();itr!=st.end();itr++)
  {
      ll i=*itr;
      ans[i]-=((n-sum[i])*(n-sum[i]+1))/2;
  }

  fs(i,1,n+1)
  if(st.find(i)!=st.end())
  cout<<ans[i]<<endl;
  else
    cout<<0<<endl;
}

int main()
{
  boost;
  ll t=1;
 // cin>>t;
  while(t--)
  {

      solve();
  }
}


Measured memory_bytes: 50264
n,m = map(int,input().split())
id = sorted([list(map(int,input().split())) for _ in range(m)])
maxl = id[0][0]
minr = id[0][1]
for i in range(1,len(id)):
    maxl = max([maxl, id[i][0]])
    minr = min([minr, id[i][1]])

print(max([minr-maxl+1,0]))

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

int main() {    
    long long int a,b,c,k;
    cin>>a>>b>>c>>k;
    while(b<=a&&k>0)
    {
        b*=2;
        k-=1;
    }
    while(c<=b&&k>0)
    {
        c*=2;
        k-=1;
    }
    
    if(c>b&&b>a)
    cout<<"Yes";
    else
    cout<<"No";
    
	return 0;
}


Measured memory_bytes: 3632
package main

import (
	"fmt"
)

type pair struct {
	i, j int
}

func grid(h, w int, input []string) string {
	for i := range input {
		for j := range input[i] {
			if input[i][j] == '.' {
				continue
			}
			var count int
			for _, p := range []pair{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
				si := i + p.i
				sj := j + p.j
				if si >= 0 &&
					sj >= 0 &&
					si < h &&
					sj < w &&
					input[si][sj] == '#' {
					count++
				}
			}
			if count == 0 {
				return "No"
			}
		}
	}
	return "Yes"
}

func main() {
	var h, w int
	fmt.Scan(&h, &w)
	input := make([]string, h)
	for i := range input {
		fmt.Scan(&input[i])
	}
	fmt.Println(grid(h, w, input))
}


Measured memory_bytes: 512
##!/usr/bin/env python
## -*- coding: utf-8 -*-
#import sys
#import os
#f = open('input.txt', 'r')
#sys.stdin = f
#input = sys.stdin.readline
# A　range flip find route

h, w = map(int, input().split())

dp = [[0 for i in range(w)] for j in range(h)]

maze = []
for i in range(h):
    sub = list(input())
    maze.append(sub)

if maze[0][0] == "#":
    dp[0][0] = 1
for i in range(1, w):
    if maze[0][i - 1] == "." and maze[0][i] == "#":
        dp[0][i] = dp[0][i - 1] + 1

    else:
        dp[0][i] = dp[0][i - 1]
for j in range(1, h):
    if maze[j - 1][0] == "." and maze[j][0] == "#":
        dp[j][0] = dp[j - 1][0] + 1
    else:
        dp[j][0] = dp[j - 1][0]

for i in range(1, h):
    for j in range(1, w):
        d = dp[i - 1][j]
        e = dp[i][j - 1]
        if maze[i - 1][j] == "." and maze[i][j] == "#":
            d += 1
        if maze[i][j - 1] == "." and maze[i][j] == "#":
            e += 1
        dp[i][j] = min(d, e)
print(dp[h - 1][w - 1])


Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<vector<pair<int, bool>>> vp(n, vector<pair<int, bool>>());
  rep(i, n){
    int a;
    cin >> a;
    rep(j, a){
      int x, y;
      cin >> x >> y;
      x--;
      vp.at(i).push_back({x, y});
    }
  }

  int ans = 0;
  rep(bit, 1 << n){
    bool f = true;
    int co = 0;
    rep(i, n){
      if((bit & (1 << i)) == 0) continue;
      co++;
      for(auto p : vp.at(i)){
        if(p.second == true){
          if((bit & (1 << p.first)) == 0){
            f = false;
            break;
          }
        }else{
          if((bit & (1 << p.first)) != 0){
            f = false;
            break;
          }
        }
      }
      if(f == false) break;
    }
    // cerr << bit << " " << f << endl;
    if(f == true){
      ans = max(ans, co);
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

int main(){
    string s; cin >> s;
    ll a[4];
    rep(i,4) a[i] = s[i]-'0';
    ll sum = a[0] + a[1] + a[2] + a[3];
    vector<char> op(3,'+');
    char pm[2] = {'+','-'};
    bool flag = false;
    for(ll bit=0; bit<(1<<3); bit++){
        ll tmp = sum;
        if(flag) break;
        REP(i,1,4){
            if(bit & 1<<(i-1)){
                tmp -= 2*a[i];
                op[i-1] = '-';
            }
            if(tmp == 7){
                rep(j,3){
                    cout << a[j] << op[j];
                }
                cout << a[3];
                flag = true;
                break;
            }
        }
        //cout << tmp << endl;
        rep(i,3) op[i] = '+';
    }
    cout << "=7" << endl;
}

Measured memory_bytes: 256
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=1
f=1
i=0
for i in range(n):
  if ans<=10**18:
    ans=ans*l[i]
  else:
  	f=0
if f==1 and ans<=10**18:
  print(ans)
else:
  print(-1)



Measured memory_bytes: 84648
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
	String n = sc.next();
	char[] a = new char[4];
	for(int i=0; i<4; i++){
		a[i] = n.charAt(i);
	}
	boolean b = false;
	if(a[1] == a[2]){
		if(a[1] == a[0] || a[1] == a[3]){
			b=true;
		}
	}
	if(b){
		System.out.println("Yes");
	}else{
		System.out.println("No");
	}
	sc.close();

	}
}


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

int main()
{
	int a, b, c[5] = {0};
	cin >> a >> b;
	c[a] = c[b] = 1;
	for (int i =1 ; i <= 3; i++){
		if (!c[i]){
			printf("%d", i);
		}
	} 
	return 0;
}

Measured memory_bytes: 256
/*
 * VJUDGE D - Streamline
 * author: roy4801
 * (C++)
 */
#include <bits/stdc++.h>

using namespace std;

#define PROB "D"
#define TESTC ""

#define USE_CPPIO() ios_base::sync_with_stdio(0); cin.tie(0)
typedef long long int LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
#define F first
#define S second
#define INF 0x3f3f3f3f
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define N 100000
int n, m, acc;
int a[N+5], dif[N+5];
int main()
{
	#ifdef DBG
	freopen("./testdata/" PROB TESTC ".in", "r", stdin);
	freopen("./testdata/" PROB ".out", "w", stdout);
	#endif
	while(cin >> n >> m)
	{
		acc = 0;
		for(int i = 0; i < m && cin >> a[i]; i++);
		sort(a, a+m);
		for(int i = 1; i < m; i++)
			dif[i] = a[i] - a[i-1];
		sort(dif+1, dif+m);

		// for(int i = 1; i < m; i++)
		// 	printf("%d ", dif[i]);
		// puts("");

		for(int i = 1; i < m-1-n+2; i++)
			acc += dif[i];
		printf("%d\n", acc);
	}

	return 0;
}


Measured memory_bytes: 1024
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, A, B, C, D = lr()
S = input()
# if C > D:
#     if "..." not in S[B-1:D]:
#         print("No")
#         exit(0)
# if "##" in S[A-1:C] or "##" in S[B-1:D]:
#     print("No")
# else:
#     print("Yes")

# ans = "Yes"
# if C > D:
#     tmp = S[B-2:D+1].count("...")
#     if tmp == 0:
#         ans = "No"

# tmp = S[A-1:max(C, D)].count("##")
# if tmp > 0:
#     ans = "No"
# print(ans)

ans="Yes"

if D<C:
  if "..." not in S[B-2:D+1]:
    ans="No"

if "##" in S[A-1:max(C,D)]:
  ans="No"

print(ans)

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

vector<long long> div(long long n){
  vector<long long> a;
  
  for(long long i = 1; i * i <= n; ++i){
    if(n % i != 0) continue;
    a.push_back(i);
    if(i * i != n) a.push_back(n / i);
  }
  
  return a;
}

int main() {
  long long n;
  cin >> n;
  
  long long ans = 0;
  for(long long x : div(n)){
    if(x == 1) continue;
    long long k = n;
    while(k % x == 0) k /= x;
    if(k % x == 1) ans++;
  }
  ans += div(n - 1).size() - 1;
  
  cout << ans << endl;
}

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

using namespace std; 
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>; 
#define INF INT_MAX //(1<<(4*4-1))
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

struct BIT{
   int sz;
   vector<ll>nd;

   BIT(int n):nd(vector<ll>(n+1,0)),sz(n){}

   ll sum(int i){
      if(!i) return 0;
      return nd[i]+sum(i-(i&-i));
   }

   void add(ll i,int x){
      if(i>sz)return;
      nd[i]+=x;
      add(i+(i&-i),x);
   }

};

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

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

   int offset = 100001;
   int A = *max_element(rng(a));
   ll ok=0;
   ll ng=INF;
   ll md;
   while(ok+1!=ng){
      md=(ok+ng)/2;
      ll sum=0;
      BIT bit(201010);
      int tot=0;
      bit.add(offset,1); //0
      for(int i=0;i<N;i++){
         if(md<=a[i])tot++;
         else tot--;
         sum+=bit.sum(tot+offset);
         bit.add(tot+offset,1);
      }
      if(sum>=((1LL*N*(N-1)/2+N+1)/2)) ok=md;
      else ng=md;
   }
   cout<<ok<<endl;
   return 0;
}



Measured memory_bytes: 2268
N = int(input())
a = list(map(int, input().split()))
a = [0] + a
b = [0] * (N + 1)
for i in range(N, 0, -1):
    tmp = 0
    for j in range(2 * i, N + 1, i):
        tmp += b[j]
        tmp %= 2

    b[i] = tmp ^ a[i]

ans = []
for j in range(1, N + 1):
    if b[j] == 1:
        ans.append(j)

print(len(ans))
print(*ans)



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

int main(){

    while(1){
        int n, q; cin >> n >> q;
        if(!n && !q) break;
        map<string, pair<long long, long long> > era;
        
        string s[1000];
        for(int i = 0; i < n; i++){
            long long by, wy;
            cin >> s[i] >> by >> wy;
            era[s[i]] = make_pair(wy - (by - 1), wy);
        }

        for(int i = 0; i < q; i++){
            long long qu; cin >> qu;
            for(int j = 0; j < n; j++){
                if(era[s[j]].first <= qu && era[s[j]].second >= qu){
                    cout << s[j] << " " << qu + 1 - era[s[j]].first << endl;
                    break;
                }else if(j == n - 1){
                    cout << "Unknown" << endl;
                }
            }
        }
    }
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int main()
{
  char s[maxn];
  cin>>s+1;
  int len = strlen(s+1);
  if(s[len] == '1' || s[1] == '0')
  {
    puts("-1");
    return 0;
  }
  for(int i = 1 ; i < len ; i++)
  {
    if(s[i] != s[len - i])
    {
      puts("-1");
      return 0;
    }
  }
  int root = 1;
  for(int i = 2 ; i <= len ; i++)
  {
    cout<<root<<" "<<i<<endl;
    if(s[i-1] == '1') root = i;
  }
}

Measured memory_bytes: 1536
def sort_ab(int_a, int_b):
    if int_a >= int_b:
        print('{} {}'.format(int_b, int_a))
    else:
        print('{} {}'.format(int_a, int_b))

while(True):
    a, b = map(int, input().split())
    if a==0 and b==0:
        break
    sort_ab(a,b)


Measured memory_bytes: 5620
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second
 
int main(int argc, char **argv) {
	ll a[3], k;
	cin >> a[0] >> a[1] >> a[2] >> k;
	sort(a, a+3);
	REP(i, k) a[2] *= 2;
	cout << (a[0] + a[1] + a[2]) << endl;
	return 0;
}
 

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

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  
  if((a+b)==c||(a+c)==b||(b+c)==a){
  cout<<"Yes"<<endl;
  }
  else{
  cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
bool used[100001];
int p[1000];
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	p[a]++;p[c]++;
	p[b]--;p[d]--;
	int s=0,pp=0;
	r(i,400){
		pp+=p[i];
		if(pp==2)s++;
	}
	cout<<s<<endl;
}

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

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

  bool isEasy = true;
  for (int i = 1; i < S.length(); i += 2) {
    if (S[i] == 'R') isEasy = false;
  }

  for (int i = 0; i < S.length(); i += 2) {
    if (S[i] == 'L') isEasy = false;
  }

  if (isEasy) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

 int main(){
string S;
cin >> S;
S.at(3) = '8';
print(S);
 }

Measured memory_bytes: 256
n,x,y = map(int,input().split())
x -= 1 ; y -= 1

ans = [0 for i in range(n)]
for s in range(n) :
  for g in range(s,n) :
    if s == g :
      continue
    dis = min(abs(g-s),abs(abs(x-s)+1+abs(y-g)),abs(abs(y-s)+1+abs(x-g)))
    ans[dis] += 1
    
for i in range(1,n) :
  print(ans[i])

Measured memory_bytes: 48476
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   long N = sc.nextLong();
   double Nroot = Math.sqrt(N);
   int Nrint = (int) Nroot;
   long tmp =N;
   for(int i =Nrint;i>=1;i--)
   {
     if(N%i==0) 
     {
       tmp = (long)N/i; 
       break;
     }
   }
   int ans =1;
   while(tmp>=10)
   {
     tmp/=10;
     ans++;
   }
   System.out.println(ans);
 }
}

Measured memory_bytes: 23508
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
#include<algorithm>

using namespace std;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(long long i=(a),i##Len_=(b);i<i##Len_;i++)
typedef long long ll;

int main()
{
    ll N,res,T;
    vector <ll> A(3);
    REP(i,3)cin >> A[i];

    sort(A.begin(),A.end());
    res = 0;

    res+= A[1]-A[0];
    res+= A[2]-A[1];
    cout << res << endl;

}



Measured memory_bytes: 256
n,m = map(int, input().split())
l=[]
for i in range(m):
    s = input()
    l.append(s.split())

ac=[0]*n
ac_cnt=0
wa_cnt=[0]*n
for i in range(len(l)):
    num = int(l[i][0])-1
    acwa= l[i][1]
    if ac[num]==0:
        if acwa == "AC":
            ac_cnt+=1
            ac[num]=1
        elif acwa=="WA":
            wa_cnt[num]+=1

wa_ans=0
for i in range(n):
    if ac[i] == 1:
        wa_ans+=wa_cnt[i]
print(ac_cnt,wa_ans)

Measured memory_bytes: 68696
/*The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

//PRABHJOT SINGH A.K.A. PRABHI
//~~~~~conquizztador~~~~~


#include<bits/stdc++.h>
using namespace std;
using lli = long long int;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
const int MOD = 1000000007;
const int MOD1 = 998244353;
const int maxn = 100010;
const int lim = (int)1e9;
int ct;
bool prime[10 * maxn];
int p[10 * maxn];
void makeSieve()
{
	for (int i = 2; i < 10 * maxn; ++i)
	{
		if (!prime[i])
			p[++ct] = i;
		for (int j = 1; j <= ct && p[j]*i < 10 * maxn; ++j)
		{
			prime[p[j]*i] = true;
			if (i % p[j] == 0)
				break;
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n = 0;
	cin >> n;
	vector<int> a(n);
	map<int, int> mp;
	for (auto &i : a)
	{
		cin >> i; ++mp[i];
	}
	makeSieve();
	bool flag = false;
	for (int i = 1; i <= ct; ++i)
	{
		int x = p[i], sum = 0;
		for (int j = x; j < 10 * maxn; j += x)
			sum += mp[j];
		if (sum == n)
		{
			cout << "not coprime" << endl;
			return 0;
		}
		flag |= (sum > 1);
	}
	if (flag)
		cout << "setwise coprime" << endl;
	else
		cout << "pairwise coprime" << endl;
}

Measured memory_bytes: 55192
n = int(input())
ns = list(map(float, input().split()))
dp = [[0 for j in range(n+1)] for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    for j in range(0, i + 1):
        dp[i][j] = dp[i-1][j] * (1-ns[i-1]) + dp[i-1][j-1] * ns[i-1]
print(sum(dp[-1][(n+1)//2:]))

Measured memory_bytes: 261512
#include "bits/stdc++.h"
 
typedef long long ll;
//#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2

using namespace std;

int MOD = 1000000007;
int xx[4010][16001] = {0};
int yy[4010][16001] = {0};

signed main(){
    int x,y;
    string s;
    cin >> s >> x >> y;

    int size = s.size();
    int i = 0;
    while(s[i] == 'F'){
        i++;
    }

    xx[0][i+8000] = 1;
    yy[0][0+8000] = 1;
    int cnts = 1;
    int m = 1;
    for(;i < size;){
        int cntt = 0; 
        int cntf = 0;
        while(i < size && s[i] == 'T'){
            cntt++;
            i++;
        }
        while(i < size && s[i] == 'F'){
            cntf++;
            i++;
        }
        if(cntt%2 == 1)m *= -1;
        if(m == 1){
            rep(j,16001){
                if(xx[cnts-1][j]){
                    xx[cnts][j+cntf] = 1;
                    xx[cnts][j-cntf] = 1;
                }
                yy[cnts][j] = yy[cnts-1][j];
            }
        }else{
            rep(j,16001){
                if(yy[cnts-1][j]){
                    yy[cnts][j+cntf] = 1;
                    yy[cnts][j-cntf] = 1;
                }
                xx[cnts][j] = xx[cnts-1][j];
            }
        }
        cnts++;
    }

    if(xx[cnts-1][x+8000] && yy[cnts-1][y+8000]){
        cout << "Yes" << endl;
    }else{
        cout << "No" <<endl;
    }




    return 0;
}
// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl 

Measured memory_bytes: 499712
import itertools
import math

def main():
    N = int(input())

    xys = [[int(y) for y in input().split()] for _ in range(N)]

    routes = itertools.permutations(xys, len(xys))

    sumup = 0
    count = 0 # cuz len(routes) doesn't work :(
    for route in routes:
        count += 1
        for i in range(1, N):
            xy_0 = route[i - 1]
            xy_1 = route[i]
            sumup += math.sqrt((xy_0[0] - xy_1[0]) ** 2 + (xy_0[1] - xy_1[1]) ** 2)

    print(sumup / count)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll ans = 0;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            if(i<(n/i)-1){
                ans+=(n/i)-1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(void){
	int n;
	cin >> n;
	int ans = 0;
	int m = 0;
	for(int i = 0; i < n; ++i){
		int h;
		cin >> h;
		if(h>=m) ans++;
		m = max(h, m);
	}
	cout << ans << endl;
}

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

int main()
{
  string s;
  cin >> s;
  set<char> st;
  for (int i = 0; i < s.size(); i++) {
    if (st.find(s[i]) != st.end()) {
      cout << "no" << endl;
      return 0;
    }
    st.insert(s[i]);
  }
  cout << "yes" << endl;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func readLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func main() {
	argv := strings.Split(readLine(), " ")
	N, _ := strconv.Atoi(argv[0])
	T, _ := strconv.Atoi(argv[1])

	t := strings.Split(readLine(), " ")

	preNum, _ := strconv.Atoi(t[0])
	var result int

	for i := 1; i < N; i++ {
		ti, _ := strconv.Atoi(t[i])
		if ti-preNum > T {
			result += T
		} else {
			result += ti - preNum
		}
		preNum = ti
	}
	fmt.Println(result + T)
}


Measured memory_bytes: 9344
#include<stdio.h>
int main(int argc, char const *argv[]) {
  int h,m,s,S;
  scanf("%d",&S);
  h=S/3600;
  m=(S-h*3600)/60;
  s=S-(h*3600+m*60);
  printf("%d:%d:%d\n", h,m,s);
  
  return 0;
}

Measured memory_bytes: 592
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <numeric>
#include <string>
#include <functional>

using namespace std;

int main(void){
    int match[10]={10,2,5,5,4,5,6,3,7,6};
    int N,M;
    cin>>N>>M;
    vector<int> A(M);
    for(int i=0;i<M;i++){
        cin>>A[i];
    }

    vector<int> dp(N+1,-1);
    dp[0]=0;
    for(int i=1;i<N+1;i++){
        for(int k=0;k<M;k++){
            int leftMatch=i-match[A[k]];
            if(leftMatch>=0&&dp[leftMatch]>=0){
                dp[i]=max(dp[i],dp[leftMatch]+1);
            }
        }
    }

    sort(A.begin(),A.end(),greater<int>());
    string ans="";

    int digit=dp[N];
    for(int i=0;i<digit;i++){
        for(int k=0;k<M;k++){
            if(N-match[A[k]]>=0&&dp[N-match[A[k]]]==(dp[N]-1)){
                ans+=to_string(A[k]);
                N-=match[A[k]];
                break;
            }
        }
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def fact_mod(n, MOD):
    ret = 1
    for i in range(1, n + 1):
        ret *= i
        ret %= MOD
    return ret

def resolve():
    N, M = LI()

    if N == M:
        ans = 2 * pow(fact_mod(N, MOD), 2, MOD)
        ans %= MOD
        print(ans)
    elif abs(N - M) <= 1:
        ans = fact_mod(N, MOD) * fact_mod(M, MOD)
        ans %= MOD
        print(ans)
    else:
        print(0)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 9224
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
D, G = map(int, input().split())

P = [0] * D
C = [0] * D
for i in range(D):
    P[i], C[i] = map(int, input().split())


ans = INF
for i in range(1 << D):
    points = 0
    solved = 0
    for j in range(D):
        if i & 1 << j > 0:
            points += C[j]
            points += P[j] * (j + 1) * 100
            solved += P[j]

    left = G - points
    for j in range(D - 1, -1, -1):
        if left <= 0:
            break
        if i & 1 << j > 0:
            continue
        val = min(100 * (j + 1) * (P[j] - 1), left)
        left -= val
        if val % (100 * (j + 1)) != 0:
            solved += val // (100 * (j + 1)) + 1
        else:
            solved += val // (100 * (j + 1))

    if left > 0:
        continue
    ans = min(ans, solved)
print(ans)

            



Measured memory_bytes: 9388
//https://atcoder.jp/contests/abc140/tasks/abc140_e
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define FOR(i,a,b) for(int64_t i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in"); //input.txt
    std::cin.rdbuf(in.rdbuf());
#endif
    ll N; cin>>N;
    vector<ll> pn(N+1);
    vector<ll> pos(N+1); //aは1..Nを並べ替えたもの
    FOR(i,1,N+1){
        ll p; cin>>p;
        pn.at(i)=p;
        pos.at(p)=i; //場所
    }

    ll ans = 0;
    set<ll> used{0,N+1}; //placeがはいる

    used.insert(pos.at(N)); //Nはいれる
    for(ll v=N-1;v>=1;--v){ //大きいほうから
        auto now_pos=pos.at(v);
        auto it = used.lower_bound(now_pos);
        auto r0 = *it;
        auto r1 = *std::next(it);
        auto l0 = *std::prev(it);
        auto l1 = *std::prev(it,2);
        if (l0>0){
            ans += v*(l0-l1)*(r0-now_pos);
        }
        if (r0<N+1){
            ans += v*(r1-r0)*(now_pos-l0);
        }
        used.insert(now_pos);
    }
    cout<<ans<<endl;
#if 0
    FOR(a,1,N+1){ //aを1から
        auto now_pos=pos[a]; //今の場所
        auto it = used.lower_bound(now_pos); //以上,upper_bound(より上)でもよい
        auto l = *it; //数字が小さい順のplaceを入れていって、その左右をみていく
        auto r = *(--it);
        ans += a*(r-now_pos)*(now_pos-l);
        used.insert(pos[a]);
    }
    cout<<ans<<endl;
#endif
    return 0;
}

Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	long long n; cin >> n;
	long long sol = 1000 * (n / 500);
	n %= 500;
	sol += 5 * (n / 5);
	cout << sol << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
#define regsiter register
#define CL fclose(stdin),fclose(stdout)
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
	long long G()
	{
		long long n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
}
char s[111111];
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	int l=1,r=n;
	int cl=0,cr=0;
	int ans=0;
	while(l<r)
	{
		cl=0,cr=0;
		while(s[l]=='x')++cl,++l;
		while(s[r]=='x')++cr,--r;
		if(s[l]!=s[r]){puts("-1");return 0;}
		ans+=dmax(cl-cr,cr-cl);
		l++,r--;
	}
	printf("%d\n",ans);
	return 0;
}




Measured memory_bytes: 256
/// Containers Start
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// C Header Files
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <math.h>
#include <stdio.h>
/// Containers End

using namespace std;

/// Math Start
#define PI acos(-1.0)
#define Pi 3.141592653589793
#define EPS (1e-7)
#define INF (0x3f3f3f3f)
/// Math End

/// Extra Start
#define nn '\n'
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define sz(a) int((a).size())
#define space " "
#define All(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
/// Extra End

#define rep(i, n) for (int i = 0; i < n; i++)
#define Cini(a)                                                                \
    int a;                                                                     \
    cin >> a;
#define Cinii(a, b)                                                            \
    int a, b;                                                                  \
    cin >> a >> b;
#define Ciniii(a, b, c)                                                        \
    int a, b, c;                                                               \
    cin >> a >> b >> c;
#define Cins(s)                                                                \
    string s;                                                                  \
    cin >> s;
#define Cinss(s1, s2)                                                          \
    string s1, s2;                                                             \
    cin >> s1 >> s2;
#define Cinc(c)                                                                \
    char c;                                                                    \
    cin >> c;
/// Functions End

/// Debug Start
#define deb(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << '\t' << #y << ": " << y << endl;
#define deb3(x, y, z)                                                          \
    cout << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": "   \
         << z << endl;
/// Debug End

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

/**>>>>>>>>>>>>>>>>>>> END <<<<<<<<<<<<<<<<<<**/

/// template

signed main(void) {
    cin.sync_with_stdio(false);
    cin.tie(0);
    string s[7] = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
    reverse(s,s+7);
    Cins(S);
    auto p = find(s,s+7,S) -s;
    cout << p + 1 << nn;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const long long INF = 1e18;

vector<long long> dijkstra(vector< vector< pair<long long, int> > > &G, int s){
  int n = G.size();
  vector<long long> ret(n, INF);
  priority_queue< pair<long long, int> > wait;
  wait.emplace(0,s);
  ret[s] = 0;
  while(!wait.empty()){
    int v = wait.top().second;
    long long cost = -wait.top().first;
    wait.pop();
    if(cost > ret[v]) continue;
    for(int i = 0; i < (int)G[v].size(); ++i){
      int v_ = G[v][i].second;
      long long cost_ = cost + G[v][i].first;
      if(cost_ < ret[v_]){
        ret[v_] = cost_;
        wait.emplace(-cost_,v_);
      }
    }
  }
  return ret;
}

int main(){
  int n, m, s, t;
  cin >> n >> m >> s >> t;
  vector< vector< pair<long long, int> > > Ga(n), Gb(n);
  for(int i = 0; i < m; ++i){
    int u, v;
    long long a, b;
    cin >> u >> v >> a >> b;
    --u,--v;
    Ga[u].emplace_back(a,v);
    Ga[v].emplace_back(a,u);
    Gb[u].emplace_back(b,v);
    Gb[v].emplace_back(b,u);
  }
  vector<long long> A = dijkstra(Ga,s-1), B = dijkstra(Gb, t-1);
  vector<long long> ans(n,(long long)(1e15));
  long long d = INF;
  for(int i = n-1; i >= 0; --i){
    d = min(d, A[i]+B[i]);
    ans[i] -= d;
  }
  for(int i = 0; i < n; ++i) cout << ans[i] << endl;
  return 0;
}


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

typedef long long int ll;
typedef pair<ll,ll> P;

set<string> m;
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        string tmp;
        cin>>tmp;
        m.insert(tmp);
    }
    cout<<m.size();


    return 0;
}

Measured memory_bytes: 19220
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

a,b = inpl()
if a%3==0 or b%3==0 or (a+b)%3==0 :
    print('Possible')
else:
    print('Impossible')

Measured memory_bytes: 5076
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

public class Main {

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

		// 入力
		int L = sc.nextInt();
		BigDecimal l = new BigDecimal(L);
		BigDecimal divide = l.divide(new BigDecimal(3),6,RoundingMode.HALF_UP);
		BigDecimal ans = divide.multiply(divide.multiply(divide));
		System.out.println(ans);			
	}

	
	// ユークリッドの控除法(最大公約数を求める)
	private static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}

	// 複数の最大公約数を求める
	private static long gcdex(long param[]) {
		long g = gcd(param[0], param[1]);
		for (int i = 1; i < param.length-1; i++) {
			g = gcd(g, param[i+1]);
		}
		return g;
	}

	// 最小公倍数を求める
	private static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	//
	private static long all(long n, long count, int N) {
		if (count == N) {
			return count;
		}
		return all(1, count, N);
	}

}

Measured memory_bytes: 22100
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 10000000


int main(){

	string N;
	cin>>N;
	
	if(N[0]==N[2]){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	
    return 0;
}



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

using namespace std;

int main(void){
  string S;
  int count = 0, ans = 0;
  cin >> S;
  for(int i=0;i<S.size();i++){
    if(S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T'){
      count++;
    }
    else{
      count = 0;
    }
    if(count > ans){
      ans = count;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
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 unite(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)

n, m = map(int, input().split())
edge = []
for i in range(m):
    a, b = map(int, input().split())
    edge.append([a - 1, b - 1])
ans = 0
for i in range(m):
    uf = UnionFind(n)
    for j in range(m):
        if i != j: uf.unite(edge[j][0], edge[j][1])
    ans += not uf.same(edge[i][0], edge[i][1])
print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#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--)
typedef long long LL;
LL X,Y;
int main(){
	cin>>X>>Y;
	if(X>Y){
	   LL temp=X;
	   X=Y;
	   Y=temp;
	}
	if(X==0&&Y==0){
	   cout<<"Brown"<<endl;
	   return 0;
	}
	if(X==0&&Y==1){
	   cout<<"Brown"<<endl;
	   return 0;
	}
	if(X==1&&Y==2){
	   cout<<"Brown"<<endl;
	   return 0;
	}
	if(X==Y){
	   cout<<"Brown"<<endl;
	   return 0;
	}
	if(X-Y==-1){
           cout<<"Brown"<<endl;
           return 0;
	}
        cout<<"Alice"<<endl;
	return(0);
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define REP(i,a) for(int i = 0; i < (a);i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using Graph = vector < vector<int>>;
long int sum[200020] = {};
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x,long long int y) {
	return(x + y-1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}

int main() {
	int N, K;
	cin >> N >> K;
	string s;
	cin >> s;
	char c = ' ';
	c = s[0];
	int sum = 0;
	sum = sum + 1;
	vector<int> k;
	for (int i = 1; i < N; i++) {
		if (c != s[i]) {
			k.push_back(sum);
			c = s[i];
			sum = 0;
			sum = sum + 1;
		}
		else {
			sum = sum + 1;
		}
		if (i == N - 1) {
			k.push_back(sum);
		}
	}
	int genkai = k.size() / 2;
	if (K >= genkai) {
		cout << s.size() - 1;
	}
	else {
		int sum = 0;
		for (auto i : k) {
			sum = sum + i-1;
		}
		cout << sum + K + K;
	}
}

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

using namespace std;

typedef long long ll;

const int MOD = 998244353; // change if needed

struct Modint {
  ll val;
  
  Modint (ll _val = 0)
    : val(_val % MOD) {}

  Modint operator+ (Modint other) const {
    return Modint(val + other.val);
  }

  void operator+= (Modint other) {
    val += other.val;
    val %= MOD;
  }

  Modint operator- () const {
    return Modint(MOD - val);
  }

  Modint operator- (Modint other) const {
    return Modint(val + MOD - other.val);
  }

  void operator-= (Modint other) {
    val += MOD - other.val;
    val %= MOD;
  }

  Modint operator* (Modint other) const {
    return Modint(val * other.val);
  }

  void operator*= (Modint other) {
    val *= other.val;
    val %= MOD;
  }

  bool operator== (Modint other) const {
    return val == other.val;
  }

  bool operator!= (Modint other) const {
    return val != other.val;
  }
};

Modint exp (Modint a, int k) {
  if (k == 0) {
    return Modint(1);
  } else if (k % 2 == 0) {
    Modint half = exp(a, k / 2);
    return half * half;
  } else {
    return a * exp(a, k - 1);
  }
}

Modint inv (Modint a) {
  return exp(a, MOD - 2);
}

ostream& operator<< (ostream& out, Modint p) {
  out << p.val;
  return out;
}

const int MAX_N = 305;

Modint dp [MAX_N][MAX_N];

Modint prea [MAX_N][MAX_N];
Modint preb [MAX_N][MAX_N];

int main () {
  string s;
  int K;

  cin >> s >> K;

  vector<int> orig;
  int buf = 0;
  for (char c : s) {
    if (c == '0') {
      orig.push_back(buf);
      buf = 0;
    } else {
      buf++;
    }
  }
  orig.push_back(buf);
  buf = 0;
  
  int n = orig.size();
  int sfx = 0;
  for (int i = 0; i < n; i++) {
    sfx += orig[i];
  }

  dp[0][0] = Modint(1);
  for (int i = 0; i < n; i++) {
    sfx -= orig[i];
    // reset prea and preb
    for (int j = 0; j < MAX_N; j++) {
      for (int k = 0; k < MAX_N; k++) {
        prea[j][k] = 0;
        preb[j][k] = 0;
      }
    }

    // calculate the new prea and preb
    for (int j = 0; j < MAX_N; j++) {
      for (int k = 0; k < MAX_N; k++) {
        prea[j][k] += dp[j][k];
        if (k - orig[i] - 1 >= 0) {
          prea[j][k - orig[i] - 1] -= dp[j][k];
        }

        int lft = sfx - k;
        if (lft > 0) {
          if (j + 1 < MAX_N && k + 1 < MAX_N) {
            preb[j + 1][k + 1] += dp[j][k];
          }

          if (j + lft + 1 < MAX_N && k + lft + 1 < MAX_N) {
            preb[j + lft + 1][k + lft + 1] -= dp[j][k];
          }
        }
      }
    }
    
    // prefixize prea by k in reverse
    for (int j = 0; j < MAX_N; j++) {
      for (int k = MAX_N - 2; k >= 0; k--) {
        prea[j][k] += prea[j][k + 1];
      }
    }
    
    // prefixize preb by the diagonals
    for (int j = 1; j < MAX_N; j++) {
      for (int k = 1; k < MAX_N; k++) {
        preb[j][k] += preb[j - 1][k - 1];
      }
    }

    // update the dp
    for (int j = 0; j < MAX_N; j++) {
      for (int k = 0; k < MAX_N; k++) {
        dp[j][k] = prea[j][k] + preb[j][k];
      }
    }
  }

  Modint ans (0);
  for (int j = 0; j <= K && j < MAX_N; j++) {
    ans += dp[j][0];
  }
  cout << ans << endl;
}


Measured memory_bytes: 5404
#include <iostream>

int main()
{
	while (1) {
		int x, y;
		std::cin >> x >> y;
		if (x == 0 && y == 0) { break; }

		if (x > y) {
			std::cout << y << " " << x << std::endl;
		}
		if(x<=y) {
			std::cout << x << " " << y << std::endl;
		}
	}


    return 0;
}

Measured memory_bytes: 3012
#include <bits/stdc++.h>
#include <algorithm>  
#include <unordered_set>

#define ll long long

using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, k;

	cin >> n >> k;
	vector<int> a(n + 1);

	priority_queue<int, vector<int>> h;

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

		if (h.size() < k) {
			h.push(a[i]);
		}
		else {
			if (a[i] < h.top()) {
				h.pop();
				h.push(a[i]);
			}
		}
	}



	int x = 0;
	while (!h.empty()) {
		x += h.top();
		h.pop();
	}

	cout << x << endl;


	return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(void)
{
	int sum, book;
	int i;
	
	while (scanf("%d", &sum), sum != 0){
		
		for (i = 0; i < 9; i++){
			scanf("%d", &book);
			sum -= book;
		}
		
		printf("%d\n", sum);
	}
	return (0);
}

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

int main(){
	int n;
	while(cin >> n){
		if(n==0)
			break;
		int m;
		cin >> m;
		for(int i=0;i<m;i++){
			int a,b;
			cin >> a >> b;
			n -= b-a;
		}
		if(n>0)
			cout << n << endl;
		else
			cout << "OK" << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int mod_pow(Int x, Int a, Int m = MOD){
    if(a == 0)return 1;
    Int res = mod_pow(x, a / 2, m);
    res = res * res % m;
    if(a % 2)res *= x;
    return res % m;
}

Int inv(Int x, Int m = MOD){
    return mod_pow(x, m-2, m);
}

Int n;
Int acum[1080000];
Int a[1080000];


int main(){
    cin >> n;
    for(Int i = 0;i < n;i++){
        cin >> a[i];
        acum[i] = a[i];
        if(i)acum[i] ^= acum[i-1];
    }
    vector< vector<Int> > app(1LL << 20);
    vector<Int> zerocnt(1080000, 0);
    for(Int i = 0;i < n;i++){
        if(i)zerocnt[i] = zerocnt[i-1];
        if(acum[i] == 0)zerocnt[i]++;
        app[acum[i]].push_back(i);
    }
    Int res = 0;
    for(Int i = 1;i < app.size();i++){
        Int dp = 0;
        Int dps = 0;
        Int dpss = 0;
        for(auto p:app[i]){
            dp = zerocnt[p] * dps % MOD - dpss + 1;dp %= MOD;
            if(dp < 0)dp += MOD;
            dps += dp;dps %= MOD;
            dpss += zerocnt[p] * dp % MOD;dpss %= MOD;
        }
        if(acum[n-1] == 0){
            res += dps;
            res %= MOD;
        }else if(acum[n-1] == i){
            res += dp;
        }
    }
    if(acum[n-1] == 0)
        res += mod_pow(2, app[0].size() - 1);
    cout << res % MOD<< endl;
    return 0;
}


Measured memory_bytes: 53872
S = list(raw_input())
K = input()

k = K

for i,s in enumerate(S):
    cost = ord('z')-ord(s)+1
    if cost <= k and s != "a":
        k-=cost
        S[i] = 'a'


c = chr((ord(S[-1])-ord('a')+k)%26+ord('a'))
S[-1] = c

print "".join(S)


Measured memory_bytes: 15984
//Andrew Yang
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <fstream>
#include <string>
#include <string.h>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>	
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <climits>
using namespace std;
#define FOR(index, start, end) for(int index = start; index < end; index++)
#define RFOR(index, start, end) for(int index = start; index > end; index--)
#define FOREACH(itr, b) for(auto itr = b.begin(); itr != b.end(); itr++)
#define RFOREACH(itr, b) for(auto itr = b.rbegin(); itr != b.rend(); itr++)
#define INF 1000000000
#define M 1000000007
typedef long long ll;
typedef pair<int, int> pii;

int main(void)
{
	int n;
	scanf("%d", &n);
	multiset<int> s;
	FOR(i, 0, 3 * n)
	{
		int x;
		scanf("%d", &x);
		s.insert(x);
	}
	ll ans = 0;
	while (s.size() > 0)
	{
		s.erase(s.begin());
		s.erase(--s.end());
		ans += *(--s.end());
		s.erase(--s.end());
	}
	cout << ans << endl;
}

Measured memory_bytes: 14336
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int r[200001]={0},d[200001]={0};
vector<int> A[200001];
int search1(int x){
  r[x]=1;
  for(auto i:A[x]) if(!r[i]) d[i]=d[x]+1,search1(i);
}
int search2(int x){
  r[x]=1;
  for(auto i:A[x]) if(!r[i]&&d[x]-1==d[i]) search2(i);
}
int main(){
    int n,a,b,B[200001],ans=0;
    cin>>n;
    rep(i,n-1) cin>>a>>b,A[a].push_back(b),A[b].push_back(a);
    search1(1);
    rep(i,n) r[i+1]=0;
    search2(n);
    rep(i,n) if(r[i+1]) B[d[i+1]]=i+1;
    rep(i,n) r[i+1]=0;
    rep(i,d[n]/2+1) r[B[i]]=1;
    search1(n);
    rep(i,n) if(r[i+1]) ans++;
    if(ans-d[n]/2-1>=(n+1)/2) cout<<"Snuke";
    else cout<<"Fennec";
}

Measured memory_bytes: 13056