akhauriyash/Code-Regression huggingface dataset:
//#include<bits/stdc++.h>
//using namespace std;
//int dis[100005];
//int n;
//vector<int>vec[100005];
//void dfs(int i)
//{
//	dis[i]=1;
//	for(int j=0;j<vec[i].size();j++)
//		if(dis[vec[i][j]]==0)
//		{
//			dfs(vec[i][j]);
//			dis[i]+=dis[vec[i][j]];
//		}
//}
//vector<int>ans;
//bool vis[100005],ok;
//void dfs2(int x)
//{
//	vis[x]=1;
//	if(!ok)ans.push_back(x);
//	if(x==n)
//	{
//		ok=1;
//		return;
//	}
//	for(int i=0;i<vec[x].size();i++)
//		if(!vis[vec[x][i]])
//			dfs2(vec[x][i]);
//	if(!ok)ans.pop_back();
//}
//int main()
//{
//	cin>>n;
//	for(int i=0;i<n-1;i++)
//	{
//		int x,y;
//		cin>>x>>y;
//		vec[x].push_back(y);
//		vec[y].push_back(x);
//	}
//	dfs(1);
////	for(int i=1;i<=n;i++)
////		cout<<dis[i]<<' ';
////	cout<<endl;
//	dfs2(1);
//	int x=ans[(ans.size()+1)/2];
////	for(int i=0;i<ans.size();i++)
////		cout<<ans[i]<<' ';
////	cout<<endl;
//	x=dis[x];
//	if(x>=n-x)cout<<"Snuke";
//	else cout<<"Fennec";
//	return 0;
//}

#include<bits/stdc++.h>
using namespace std;
int n,p[100005],sz[100005];
vector<int>vec[100005];
void dfs(int x)
{
	sz[x]=1;
	for(int i=0;i<vec[x].size();i++)
	{
		if(vec[x][i]!=p[x])
		{
			p[vec[x][i]]=x;
			dfs(vec[x][i]);
			sz[x]+=sz[vec[x][i]];
		}
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	dfs(1);
	vector<int>path;
	int c=n,psz=0;
	while(c>0)
	{
		path.push_back(sz[c]-psz);
		psz=sz[c];
		c=p[c];
	}
	reverse(path.begin(),path.end());
	int l=0,r=0;
	int i=0,j=path.size()-1;
	while(i<=j)
	{
		l+=path[i++];
		if(i<=j)r+=path[j--];
	}
	if(l>r)cout<<"Fennec";
	else cout<<"Snuke";
	return 0;
}

Measured memory_bytes: 11772
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define INF 100000000
#define rep(i,s,n) for (int i = (int)(s); i < (int)(n); i++)
#define repp(i,n,s) for (int i= (int)(n); i >= (int)(s); i--)
#define mp make_pair
ll mod = 1000000007;
ll mod2 = 998244353;

int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,k;cin>>n>>m>>k;
    vector<ll> a(n),b(m),c(n+1),d(m+1);
    rep(i,0,n) cin>>a[i];
    rep(i,0,m) cin>>b[i];
    rep(i,0,n) c[i+1] = a[i] + c[i];
    rep(i,0,m) d[i+1] = b[i] + d[i];
    int j = 0;
    int ans = 0;
    repp(i,n,0){
        if (c[i]>k) continue;
        while (true){
            if (j==m+1) {
                 j--;
                 break;
            }
            if (c[i]+d[j]>k){
                j--;
                break;
            }
            j++;
        }
        ans = max(ans,i+j);
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 9504
r1,c1,r2,c2 = map(int,input().split())

# 二項係数 mod P

mod = 10**9+7

m = r2+c2 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod


def g(r,c):
    ret = 0
    for i in range(0,r+1):
        ret += comb(i+c+1,i+1)
        ret %= mod
    return ret

ans = (g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1))%mod
print(ans)

Measured memory_bytes: 87148
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    string r = "";
    for(int i = 0; i < s.size(); i++) {
        int n = 0;
        for(int j = 0; j < s.size(); j++) {
            //cout << s[(i+j)%s.size()] << " " << t[j] << endl;
            if(s[(i+j)%s.size()] == t[j]) {
                n++;
            }
            else {
                n = 0;
                break;
            }
        }
        if(n == s.size()) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

const double eps = 1e-9;

typedef long long ll;

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

  map<string, vector<int>> m = {
    {"hon", {2, 4, 5, 7, 9}},
    {"pon", {0, 1, 6, 8}},
    {"bon", {3}}
  };
  int x;
  cin >> x;
  x %= 10;
  for (auto e : m) {
    for (auto ee : e.second) {
      if (ee == x) {
        cout << e.first << endl;
        return 0;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//uniform_int_distribution<int>(1000,10000)(rng)

ll binpow(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
        return res * a;
    return res;
}

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

string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,a=0,w=0,t=0,r=0;
    cin>>n;
    string s;
    while (n--)
    {
        cin>>s;
        if (s[0]=='A')
            ++a;
        if (s[0]=='W')
            ++w;
        if (s[0]=='T')
            ++t;
        if (s[0]=='R')
            ++r;
    }
    cout<<"AC x "<<a<<"\n";
    cout<<"WA x "<<w<<"\n";
    cout<<"TLE x "<<t<<"\n";
    cout<<"RE x "<<r<<"\n";
    return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define rrep(i,n) for(int (i)=1;i<=(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define INF 1e18
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};

int n;
vector<int> l(55);
vector<int> sum(55);
vector<int> yokan;

bool check(int minlen, int maxlen) {
	vector<int> dp(55, 0);
	dp[0] = 1;
	rrep(i, n) {
		rep(j, i) {
			int nowlen = sum[i] - sum[j];
			if(minlen <= nowlen && nowlen <= maxlen && dp[j]) dp[i] = 1;
		}
	}
	return dp[n];
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	//cout << fixed << setprecision(15);
	
	cin >> n;
	rep(i, n) {
		cin >> l[i];
		sum[i+1] = sum[i] + l[i];
	}
	rep(i, n+1) {
		REP(j, i+1, n+1) {
			if(i == 0 && j == n) continue;
			yokan.push_back(sum[j] - sum[i]);
		}
	}
	//for(auto &x : yokan) cout << x << " ";
	sort(all(yokan));
	int ans = sum[n];
	rep(i, yokan.size()) {
		REP(j, i+1, yokan.size()) {
			int minlen = yokan[i];
			int maxlen = yokan[j];
			if(check(minlen, maxlen)) chmin(ans, maxlen - minlen);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3260
import scala.io.StdIn
import scala.math._

object Main {
  def main(args: Array[String]): Unit = {
    val n = StdIn.readLong

    val minFlow = ((1 to 5).toList.map(_ => StdIn.readLong).min)

    println((n + minFlow - 1) / minFlow + 4)

  }
  
}

Measured memory_bytes: 27036
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


n = int(input())
A = list(map(int, input().split()))

gcd_from_left = [0]*n
gcd_from_right = [0]*n

for i in range(1, n):
    gcd_from_left[i] = gcd(A[i-1], gcd_from_left[i-1])
    gcd_from_right[n-i-1] = gcd(A[n-i], gcd_from_right[n-i])

ans = 0

for a, b in zip(gcd_from_left, gcd_from_right):
    x = gcd(a, b)
    if ans < x:
        ans = x

print(ans)


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

int N;
vector<int> v;
int main (){
	cin >> N;
	for(int i=0;i<N;i++){
		int x;
		cin >> x;
		v.push_back(x);
	}
	int ans=0;
	int cnt=0;
	for(int i=0;i<N-1;i++){
		if(v[i] >= v[i+1]) {
			cnt++;
			ans = max(ans,cnt);
		} else cnt = 0;
	}
  cout << ans << endl;
	return 0;
}

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

void solver() {
  int n, k;
  cin >> n >> k;
  vector<bool> as(n);

  for (int i = 0; i < k; i++) {
    int d;
    cin >> d;
    for (int j = 0; j < d; j++) {
      int a;
      cin >> a;
      as[a-1] = true;
    }
  }

  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (!as[i]) ans++;
  }

  cout << ans << "\n";
}

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


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Welcome to my source code!

int main() {
    ll n, a, b, c, d, e;
    cin >> n >> a >> b >> c >> d >> e;
    cout << max({ (n - 1) / a, (n - 1) / b, (n - 1) / c, (n - 1) / d, (n - 1) / e }) + 5 << endl;
}

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

using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int a, h;
    cin >> h >> a;
    cout << (h + a - 1) / a;
    return 0;
}

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

modd = 1000000007
dp = [[[[0 for k in range(4)] for i in range(4) ]for j in range(4) ]for n in range(N+1)]

dp[0][3][3][3] = 1


for L in range(N):
    for i in range(4):
        
        for j in range(4):
        
            for k in range(4):
                if (dp[L][i][j][k]==0): continue
                for a in range(4):
                    if (a == 2 and i == 1 and j == 0):    continue
                    if (a == 2 and i == 0 and j == 1):    continue
                    if (a == 1 and i == 2 and j == 0):    continue
                    if (a == 2 and i == 1 and k == 0):    continue
                    if (a == 2 and j == 1 and k == 0):    continue
                    
                    dp[L+1][a][i][j] += dp[L][i][j][k]
                    dp[L+1][a][i][j] %= modd
  
ans = 0         
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += dp[N][i][j][k]
            ans %= modd
print(ans)
                

Measured memory_bytes: 3316
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef pair<int, int>P;
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
typedef vector<vector<ll>> mat;
typedef vector<int> vec;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
const ll mod = 1000000007;
const ll INF = mod * mod;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll qp(ll a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

void solve() {
    ll a, b, c, d, n, k, x;
    string s, t;
    ll ans = 0;
    double dans = 0;
    string sans = "YES";

    cin  >> n >> d ;

    ll arr[10][10];

    rep(i,n){
        rep(j,d){
            cin >> arr[i][j];

        }
    }

    rep(i,n-1){
        Rep(j,i+1,n){
            ll tmp=0;
            rep(k, d){
                tmp += pow((arr[i][k] - arr[j][k]),2);
            }
            double hoge = sqrt(tmp);
            if(hoge == lround(hoge))ans++;
        }
    }




    std::cout << ans << endl; 
    // std::cout << sans << endl; 
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    solve();
    // stop
        return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int top, S[1000];

void push(int x) { S[++top] = x; }

int pop() {
  top--;
  return S[top + 1];
}

int main() {
  int a, b;
  top = 0;
  char s[100];

  while (scanf("%s", s) != EOF) {
    if (s[0] == '+') {
      a = pop();
      b = pop();
      push(a + b);
    } else if (s[0] == '-') {
      b = pop();
      a = pop();
      push(a - b);
    } else if (s[0] == '*') {
      a = pop();
      b = pop();
      push(a * b);
    } else {
      push(atoi(s));
    }
  }

  printf("%d\n", pop());
  return 0;
}


Measured memory_bytes: 2096
# なぜかうまくいかない
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect, bisect_right, bisect_left

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
# 0 0 0の左
zero = A.count(0)
# A.(0)
l = bisect_left(A, 0)
r = bisect(A, 0)
zero = r - l
C = []
for a in A[:l]:
    if a == 0:
        continue
    C.append(a)
    
B = C + A[r:]


w = K - zero
ans = INF
B.insert(0, -INF)
B.append(INF)
if zero == K:
    print(0)
    exit()

for i in range(len(B) - K + 1):
    r = B[i + K - zero - 1]
    l = B[i]
    tmp = INF
    if l < 0 and r > 0:
        tmp = min(abs(l), r) + r - l
    # ans = min(ans, tmp)
    elif l > 0 and B[i-1] < 0:
        # tmp = min(abs(l), r) + r - l
        tmp = r

    elif r < 0 and B[i + K - zero - 1 + 1] > 0:
        # tmp = min(abs(l), r) + r - l
        tmp = abs(l)
    ans = min(ans, tmp)
print(ans)


        # if abs(B[i]) <= :

#         tmp = B[i + K - zero-1] - B[i]
#         print(B[i+K-zero-1])
#         print(B[i])
#         ans = min(ans, tmp)
# print(ans)

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

using namespace std;
#ifdef ONLINE_JUDGE
#define cerr if(false)cerr
#endif
//#define int long long
#define ld1 long double
#define watch(x) cerr << (#x) << " is " << (x) << endl
#define faster ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL),cout<<setprecision(14);
#define cint int t;cin>>t;while(t--)
#define vint vector<int>
#define all(v) (v).begin(), (v).end()
#define pii pair<int,int>
#define pb push_back
#define N 50011
#define mm0(X) memset((X), 0, sizeof((X)))
#define mm1(X) memset((X), -1, sizeof((X)))
#define MAXN (int)1e6 + 11
#define INF (int)1e9
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define endl '\n'

const int mod=1000000007;
int powmod(int a,int b) {int res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}

void solve(){
    int n,k;
    cin>>n>>k;

    int a[n+1]={};

    for(int i=0;i<k;i++){
        int d;
        cin>>d;
        for(int i=0;i<d;i++){
            int x;
            cin>>x;
            a[x]++;
        }
    }
    int count=0;
    for(int i=1;i<=n;i++){
        if(!a[i]) count++;
    }
    cout<<count<<endl;
}

int32_t main() {
    faster;

#ifndef ONLINE_JUDGE
    READ("inp.txt");
    WRITE("out.txt");
    double beg=clock();
#endif

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

    while(t--){
        solve();
    }

#ifndef ONLINE_JUDGE
    double end=clock();
    cerr<<"*** Total time = "<<(end-beg)/CLOCKS_PER_SEC;
#endif
}


Measured memory_bytes: 3652
import java.util.*;


import java.io.*;
 
public class Main {
	private static void solve(){
		//Implement solution here.
		int n = ni();
		int[] v = na(n);
		Arrays.sort(v);
		double result = v[0];
		for(int i = 1; i < n; i++){
			result = (result + v[i])/2;
		}
		System.out.println(result);
	}
	
	//Switch input source (stdin/file)
	private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args){
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		} 
		solve();
	}
 
	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define lcm(x, y) ((x) * (y) / __gcd((x), (y)))
#define sz(a) (long long)((a).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout << "----------------------------------\n";
#define mp make_pair
#include <iostream>
#define fastinput                     \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

LL dp[100 + 2][2 * 100000 + 1];
LL sum[100 + 2][2 * 100000 + 1];

int main()
{
    fastinput;
    LL n, i, j, k, t, temp;
    //state=[spent][child_left]
    cin >> n >> k;
    //debug(n);
    //debug(k);
    LL a[n + 1];
    for (i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i]%=MOD;
    }
    //cout << "taking inputs" << endl;

    for (i = 0; i <= n; i++)
    {
        for (j = 0; j <= 2 * k + 1; j++)
        {
            dp[i][j] = 0;
            sum[i][j] = 0;
        }
    }

    dp[0][0] = 1;
    for (i = 0; i <= n - 1; i++)
    {
        for (j = 0; j <= k; j++)
        {
            //ways to spend j candies among first i people
            sum[i + 1][j] += (dp[i][j]+MOD) % MOD;
            sum[i + 1][j] =  (sum[i + 1][j]+MOD)%MOD;
            if (j + a[i + 1] + 1 <= k)
            {
                sum[i + 1][j + a[i + 1] + 1] -= ((dp[i][j]) +MOD)% MOD;
                sum[i + 1][j + a[i + 1] + 1] =  (sum[i + 1][j + a[i + 1] + 1]+MOD)%MOD;
            }
        }

        for (j = 0; j <= k; j++)
        {
            //cout << "sum[" << i + 1 << "][" << j << "] is " << sum[i + 1][j] << endl;
        }
        dp[i + 1][0] = sum[i + 1][0];
        for (j = 1; j <= k; j++)
        {
            dp[i + 1][j] = (dp[i + 1][j - 1] + sum[i + 1][j]+MOD)%MOD;
            //cout << "dp[" << i + 1 << "][" << j << "] is " << dp[i + 1][j] << endl;
        }
    }

    cout << (dp[n][k]+MOD)%MOD << endl;

    return 0;
}

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

namespace ABC148B
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = Cin.Int();
            var st = Cin.String();

            List<char> a = new List<char>();
            for (int i = 0; i < n; i++)
            {
                a.Add(st[i]);
                a.Add(st[i+n+1]);
            }

            Console.WriteLine(new String(a.ToArray()));
        }
    }

    class Solver
    {
        public Solver()
        {

        }

        public IConvertible Solve()
        {
            return 0;
        }
    }

    internal static class Cin
    {
        public static string String()
        {
            return Console.ReadLine();
        }

        public static int Int()
        {
            return int.Parse(String());
        }

        public static int[] IArr()
        {
            return Split().Select(int.Parse).ToArray();
        }

        public static long Long()
        {
            return long.Parse(String());
        }

        public static long[] LArr()
        {
            return Split().Select(long.Parse).ToArray();
        }

        public static double Double()
        {
            return double.Parse(String());
        }

        public static double[] DArr()
        {
            return Split().Select(double.Parse).ToArray();
        }

        private static IEnumerable<String> Split()
        {
            return String().Split(' ');
        }
    }
}

Measured memory_bytes: 13140
#include <cstdio>
#include <algorithm>
using namespace std;

bool straight(int* a){
	for(int i = 0; i < 4; i++){
		if(a[i + 1] - a[i] != 1) break;
		if(i + 1 == 4) return true;
	}
	
	return (a[0] == 1 && a[1] == 10 && a[2] == 11 && a[3] == 12 && a[4] == 13);
}

int main(){
	int card[5];
	
	while((scanf("%d,%d,%d,%d,%d", &card[0], &card[1], &card[2], &card[3], &card[4])) != EOF){
		sort(card, card + 5);
		
		//four card
		if(card[2] == card[1] && card[2] == card[3] && (card[2] == card[0] || card[2] == card[4])){
			printf("four card\n");
		}
		//full house
		else if(card[0] == card[1] && card[3] == card[4] && (card[2] == card[1] || card[2] == card[3])){
			printf("full house\n");
		}
		//straight
		else if(straight(card)){
			printf("straight\n");
		}
		//three card
		else if((card[0] == card[1] && card[1] == card[2]) || (card[1] == card[2] && card[2] == card[3]) || (card[2] == card[3] && card[3] == card[4])){
			printf("three card\n");
		}
		//two pair
		else if((card[0] == card[1] && (card[2] == card[3] || card[3] == card[4])) || (card[1] == card[2] && card[3] == card[4])){
			printf("two pair\n");
		}
		//one pair
		else if(card[0] == card[1] || card[1] == card[2] || card[2] == card[3] || card[3] == card[4]){
			printf("one pair\n");
		}
		//null
		else{
			printf("null\n");
		}
	}
	
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <map>
#include <deque>
#include <queue>
#include <climits>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(v) sort(v.begin(), v.end())
#define SORTFUNC(v, func) sort(v.begin(), v.end(), func)
#define PRINT(v) REP(i, v.size()) printf("%d ", v[i]); cout << endl
#define IN(n) scanf("%d", &(n))

int main(){
  int n;
  IN(n);
  vector<int> tab(n);
  REP(i, n) IN(tab[i]);
  SORT(tab);
  ll sum[100000];
  sum[0] = tab[0];
  FOR(i, 1, n) sum[i] = tab[i] + sum[i-1];
  int res = 1;
  for(int i = n-2; i >= 0; i--){
    if (2*sum[i] >= tab[i+1]) res++;
    else break;
  }
  printf("%d\n", res);
  return 0;
}
























// I'd like to scroll past the end of document using Atom but I seemigly have to use these blank lines instead


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

using namespace std;
#define int long long
#define x first
#define y second

#define vert int v, int tl, int tr
#define tm ((tl + tr) >> 1)
#define left (v << 1), tl, tm
#define right (v << 1) + 1, tm, tr

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

int n;
int a[100009];
int pref[100009];

int tree[800009];
void build(vert) {
    tree[v] = 0;
    if (tr - tl == 1) return;

    build(left);
    build(right);
}

void upd(vert, int i, int x) {
    tree[v] += x;
    if (tr - tl == 1) {
        return;
    }

    if (i < tm) {
        upd(left, i, x);
    }

    else {
        upd(right, i, x);
    }
}

int getsum(vert, int l, int r) {
    if (l >= tr || tl >= r) return 0;
    if (tl >= l && tr <= r) return tree[v];
    return getsum(left, l, r) + getsum(right, l, r);
}

int check(int x) {
    for (int i = 0; i < n; i ++) {
        if (a[i] >= x)
            pref[i + 1] = pref[i] + 1;
        else
            pref[i + 1] = pref[i] - 1;
    }

    build(1, 0, 2 * n + 2);
    int cnt = 0;
    for (int i = 0; i <= n; i ++) {
        cnt += getsum(1, 0, 2 * n + 2, 0, pref[i] + n + 1);
        upd(1, 0, 2 * n + 2, pref[i] + n, 1);
    }

    return cnt;
}

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

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

    int l = 0, r = (1e9) + 1;
    int eth = (n * n) / 2;
    while (r - l > 1) {
        int m = (r + l) / 2;
        if (check(m) <= (eth + 1) / 2) {
            r = m;
        }

        else {
            l = m;
        }
    }

    cout << l;

    return 0;
}


Measured memory_bytes: 7936
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	string s;
	while(cin>>n>>s&&n!=0){
		vector<int> trump(n,0);
		int stage=0;
		for(int i=0;i<100;i++){
			if(s[i]=='S'){
				stage+=trump[i%n]+1;
				trump[i%n]=0;
			}else if(s[i]=='M'){
				trump[i%n]++;
			}else if(s[i]=='L'){
				trump[i%n]+=stage+1;
				stage=0;
			}
		}
		sort(trump.begin(),trump.end());
		for(int i=0;i<n;i++){
			cout<<trump[i]<<" ";
		}
		cout<<stage<<endl;
	}
}

Measured memory_bytes: 1220
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	int a, b, c, d, p,ans[5];
	cin >> a >> b >> c >> d >> p;
	ans[1] = a * p;
	ans[2] = b;
	if (p > c) {
		p = p - c;
		ans[2] = ans[2] + p * d;
	}
	cout << min(ans[1], ans[2]) << endl;
}


Measured memory_bytes: 3108
//
//  Poor.cpp
//  NYU Progteam
//
//  Created by Xinyu Qu on 2/28/20.
//  Copyright © 2020 Xinyu Qu. All rights reserved.
//
/*A triple of numbers is said to be poor when two of those numbers are equal but the other number is different from those two numbers.

You will be given three integers
A
,
B
, and
C
. If this triple is poor, print Yes; otherwise, print No.*/

#include <stdio.h>
#include <iostream>
using namespace std;

int main(){
    int arr[10] = {0};
    int num;
    for(int i = 0; i < 3; i++){
        cin >> num;
        arr[num]++;
    }
    for(int i = 0; i < 10; i++){
        if(arr[i] == 2){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,a,b) for(int i(a);i<b;i++)
#define rep(i,n) for(int i(0);i<n;i++)
#define fast  ios_base::sync_with_stdio(0); cin.tie(0);
#define pres(x) cout<<fixed; cout<<setprecision(x);
#define open freopen("input.txt","r",stdin) ; freopen("output.txt","w",stdout);
#define watch(x) cout<<(#x)<<" is "<<x<<"\n";
#define mod 1000000007

int32_t main(){
	
	fast;
	//open;

	int n;
	cin>>n;
	int array[n];
	rep(i,n)cin>>array[i];
	sort(array, array+n);
	//watch(array[n/2]); watch(array[n/2 -1]);
	cout<<array[n/2] - array[n/2 - 1];


	return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void) {
	int N;
	scanf("%d", &N);
	int divMax = 0;
	int ans = 1;
	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		int tmp = i;
		while (tmp > 0) {
			// cout << tmp << "\n";
			if (tmp % 2 == 0) {
				tmp /= 2;
				cnt++;
			} else {
				break;
			}
		}
		if (cnt > divMax) {
			divMax = cnt;
			ans = i;
		}
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 3756
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <map>
#include <set>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <stdlib.h>

using namespace std;
 
typedef long long i64;
typedef pair<i64, i64> P;

template<class T>
const T INF = numeric_limits<T>::max();
template<class T>
const T SINF = numeric_limits<T>::max() / 10;
static const i64 MOD = 1000000007;

int dx[4] = {0,1,0,-1}, dy[4] = {-1,0,1,0};
//int dx[5] = {-1,0,0,0,1}, dy[5] = {0,-1,0,1,0};
//int dx[8] = {-1,0,1,1,1,0,-1,-1}, dy[8] = {1,1,1,0,-1,-1,-1,0};
//int dx[9] = {-1,0,1,1,1,0,-1,-1,0}, dy[9] = {1,1,1,0,-1,-1,-1,0,0};

struct edge {
	i64 from, to, cost;
	edge(i64 to, i64 cost) : from(-1), to(to), cost(cost) {}
	edge(i64 src, i64 to, i64 cost) : from(src), to(to), cost(cost) {}
};

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}

//-----end of template-----//

int h, w;

#define BLACK '#'
#define WHITE '.'

int csolve(vector<string>& s){
	bool used[400][400];
	for(int i = 0; i < 400; ++i) for(int j = 0; j < 400; ++j) used[i][j] = false;
	int ans = 0;
	for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j){
		if(used[i][j]) continue;
		vector<int> cnt(200, 0);
		queue<P> que;
		que.push(P(i, j));
		cnt[s[i][j]]++;
		used[i][j] = true;
		while(!que.empty()){
			P t = que.front(); que.pop();
			int x = t.first;
			int y = t.second;
			for(int k = 0; k < 4; ++k){
				int nx = x + dx[k];
				int ny = y + dy[k];
				if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
				if((s[nx][ny] != s[x][y]) && !used[nx][ny]){
					que.push(P(nx, ny));
					cnt[s[nx][ny]]++;
					used[nx][ny] = true;
				}
			}
		}
		ans += cnt[WHITE] * cnt[BLACK];
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	i64 h, w;
	cin >> h >> w;
	vector<string> s(h);
	bool used[400][400];
	for(i64 i = 0; i < 400; ++i) for(i64 j = 0; j < 400; ++j) used[i][j] = false;
	i64 ans = 0;
	for(i64 i = 0; i < h; ++i) cin >> s[i];
	for(i64 i = 0; i < h; ++i) for(i64 j = 0; j < w; ++j){
		if(used[i][j]) continue;
		vector<i64> cnt(200, 0);
		queue<P> que;
		que.push(P(i, j));
		cnt[s[i][j]]++;
		used[i][j] = true;
		while(!que.empty()){
			P t = que.front(); que.pop();
			i64 x = t.first;
			i64 y = t.second;
			for(i64 k = 0; k < 4; ++k){
				i64 nx = x + dx[k];
				i64 ny = y + dy[k];
				if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
				if((s[nx][ny] != s[x][y]) && !used[nx][ny]){
					que.push(P(nx, ny));
					cnt[s[nx][ny]]++;
					used[nx][ny] = true;
				}
			}
		}
		ans += cnt[WHITE] * cnt[BLACK];
	}
	cout << ans << endl;
}

Measured memory_bytes: 640
from fractions import gcd

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

S = input()
T = input()

G = gcd(N, M)

n = N // G
m = M // G

L = N * M // G

for i in range(0, G):
    a = i * n
    b = i * m

    if S[a] != T[b]:
        print(-1)
        exit()

print(L)


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

long long solve(string N, int K){
  long long ret = 0;
  if(K == 1){
    ret = 9 * (N.length() - 1) + (N[0] - '0');
  }else if(K == 2){
    if(N.length() < 2){
      ret = 0;
    }else{
      long long top_zero = 9 * 9 * (N.length() - 1) * (N.length() - 2) / 2;
      long long top_lt = (N[0] - '0' - 1) * 9 * (N.length() - 1);
      int first_nonzero_idx = 1;
      while(first_nonzero_idx < N.length() && N[first_nonzero_idx] == '0'){
        first_nonzero_idx++;
      }
      long long top_eq = 0;
      if(first_nonzero_idx < N.length()){
        top_eq = solve(N.substr(first_nonzero_idx, N.length() - first_nonzero_idx), K - 1);
      }
      ret = top_zero + top_lt + top_eq;
    }
  }else{
    if(N.length() < 3){
      ret = 0;
    }else{
      long long top_zero = 9LL * 9 * 9 * (N.length() - 1) * (N.length() - 2) * (N.length() - 3) / 6;
      long long top_lt = 9LL * 9 * (N[0] - '0' - 1) * (N.length() - 1) * (N.length() - 2) / 2;
      int first_nonzero_idx = 1;
      while(first_nonzero_idx < N.length() && N[first_nonzero_idx] == '0'){
        first_nonzero_idx++;
      }
      long long top_eq = 0;
      if(first_nonzero_idx < N.length()){
        top_eq = solve(N.substr(first_nonzero_idx, N.length() - first_nonzero_idx), K - 1);
      }
      ret = top_zero + top_lt + top_eq;
    }
  }
  return ret;
}

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

  int K;
  cin >> K;


  cout << solve(N, K) << endl;
}


Measured memory_bytes: 888
#include <iostream>

using namespace std;

int main(){

	int n,q;
	int ans[110];
	

	while(cin>>n>>q){
		if(n==0&&q==0)break;

		int maxSum=0;
		int maxPos=0;
		
		for(int i=0;i<110;i++){
			ans[i]=0;
		}
		for(int i=0;i<n;i++){
			int m;
			cin>>m;
			int *data;
			data = new int[m];

			for(int j=0;j<m;j++){
				cin>>data[j];
				ans[data[j]]++;
			}
		}
		int flag=0;
		for(int i=0;i<110;i++){
			if(ans[i]>=q && maxSum<ans[i]){
				maxSum=ans[i];
				maxPos=i;
			}
		}
		cout<<maxPos<<endl;

	}

	return 0;
}

Measured memory_bytes: 1472
#include <iostream>
#include <string>
#include <stack>
#include <cstdlib> 
using namespace std;
  
int main(){
 
    stack<int> st;
    string s;
    int a,b;
 
    while(cin >> s){
        if(s=="+"){
            a=st.top();
            st.pop();
            b=st.top();
            st.pop();
            st.push(a+b);
        }
        else if(s=="-"){
            a=st.top();
            st.pop();
            b=st.top();
            st.pop();
            st.push(b-a);
        }
        else if(s=="*"){
            a=st.top();
            st.pop();
            b=st.top();
            st.pop();
            st.push(a*b);
        }
        else st.push(atoi(s.c_str()));
    }
 
    cout << st.top() << endl;
 
    return 0;
 
} 

Measured memory_bytes: 3168
void main() {
    auto N = ri;
    auto A = readAs!(int[]);
    
    ulong res;
    void dfs(int[] arr) {
        if(arr.length == N) {
            if(arr.any!(v => v % 2 == 0)) res++;
            return;
        }
        foreach(i; A[arr.length] - 1 .. A[arr.length] + 2) {
            dfs(arr ~ i);
        }
    }
    dfs([]);
    res.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

long rl() {
	return readAs!long;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 1276
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
char memarr[96000000];
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
struct graph{
  int N;
  int *es;
  int **edge;
  void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
    int i;
    N = N__;
    walloc1d(&es, N, mem);
    walloc1d(&edge, N, mem);
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      es[A[i]]++;
      es[B[i]]++;
    }
    for(i=(0);i<(N);i++){
      walloc1d(&edge[i], es[i], mem);
    }
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      edge[A[i]][es[A[i]]++] = B[i];
      edge[B[i]][es[B[i]]++] = A[i];
    }
  }
  void getDist(int root, int res[], void *mem = wmem){
    int i;
    int j;
    int k;
    int*q;
    int s;
    int z;
    walloc1d(&q, N, &mem);
    for(i=(0);i<(N);i++){
      res[i]=-1;
    }
    res[root]=0;
    s=0;
    z=1;
    q[0]=root;
    while(z){
      i=q[s++];
      z--;
      for(j=(0);j<(es[i]);j++){
        k=edge[i][j];
        if(res[k]>=0){
          continue;
        }
        res[k]=res[i]+1;
        q[s+z++]=k;
      }
    }
  }
}
;
int N;
int U;
int V;
int A[100000];
int B[100000];
graph g;
int d1[100000];
int d2[100000];
int main(){
  int i;
  wmem = memarr;
  int res = 0;
  rd(N);
  rd(U);U += (-1);
  rd(V);V += (-1);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N-1);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);A[Lj4PdHRW] += (-1);
      rd(B[Lj4PdHRW]);B[Lj4PdHRW] += (-1);
    }
  }
  g.setEdge(N,N-1,A,B);
  g.getDist(U,d1);
  g.getDist(V,d2);
  for(i=(0);i<(N);i++){
    if(d1[i] < d2[i]){
      chmax(res, d2[i] - 1);
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200119-1

// --- original code ---
// int N, U, V, A[1d5], B[1d5];
// graph g;
// int d1[1d5], d2[1d5];
// {
//   int res = 0;
//   rd(N,U--,V--,(A--,B--)(N-1));
//   g.setEdge(N,N-1,A,B);
//   g.getDist(U,d1);
//   g.getDist(V,d2);
//   rep(i,N) if(d1[i] < d2[i]) res >?= d2[i] - 1;
//   wt(res);
// }


Measured memory_bytes: 6400
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

vector<vector<int>> v;
vector<bool> seen;
vector<int> d,f;
int t = 0;

void dfs(int u,int &t){
    t++;
    d[u] = t; // 初訪問時の時刻
    seen[u] = true;
    for(int i=0;i<v[u].size();i++){
        if(seen[v[u][i]]) continue;
        dfs(v[u][i],t);
    }
    t++;
    f[u] = t;
}

int main(){
    int n;
    cin >> n;

    v.resize(n+1);
    seen.resize(n+1);
    d.resize(n+1);
    f.resize(n+1);
    rep(i,n+1) seen[i] = false;

    rep(i,n){
        int u,k;
        cin >> u >> k;
        rep(j,k){
            int tmp;
            cin >> tmp;
            v[u].push_back(tmp);
        }
    }
    // 深さ優先探索で探索する.
    for(int i=1;i<=n;i++){
        if(seen[i])continue;
        dfs(i,t);
    }
    for(int i=1;i<=n;i++){
        cout << i << " " << d[i] << " " << f[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3180
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N, x = map(int, input().split())
    A = list(map(int, input().split()))

    ans = 0
    for i in range(N):
        if A[i] > x:
            d = A[i] - x
            ans += d
            A[i] = x

    for i in range(1, N):
        if A[i - 1] + A[i] > x:
            d = A[i - 1] + A[i] - x
            A[i] -= d
            ans += d
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 15016
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n; cin >> n;
    string s = to_string(n);
    int d = 0;
    REP(i,s.size()) d += s[i] - '0';
    ATYN(n % d == 0)

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <functional>
#include <numeric>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;

const int INF = 1 << 29;
typedef pair<int, int> P;


int main(void)
{
	int n, q; cin >> n;
	vector<int> s(n);
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	int ans = 0;
	sort(s.begin(), s.end());
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		int t; cin >> t;
		vector<int>::iterator it = lower_bound(s.begin(), s.end(), t);
		if(it != s.end() && *it == t) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1248
import sys
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def rec(i, dp, nodes):
    # 更新済みのデータの場合はそのまま返す
    if dp[i] != -1:
        return dp[i]

    res = 0
    for next in nodes[i]:
        res = max(res, rec(next, dp, nodes) + 1)
    dp[i] = res
    return res

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, M = map(int, input().rstrip().split())
    nodes = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().rstrip().split())
        nodes[x-1].append(y-1)

    # dp[i] = i番目のノードを始点としたときの最大パス長
    dp = [-1] * N
    ans = 0
    for i in range(N):
        ans = max(ans, rec(i, dp, nodes))
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 131292
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define F first
#define S second
#define INF 1 << 30

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int A, N[1000001];

int main(){
  int a;
  while(scanf("%d", &a) && a){
    memset(N, 0, sizeof(N));
    rep(i, a){
      scanf("%d", &A);
      N[A]++;
    }
    rep(i, 1000001) if(N[i] > a/2){ printf("%d\n", i); goto e;}
    puts("NO COLOR");
  e:;
  }
  return 0;
}

Measured memory_bytes: 5108
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>
#include <iomanip>
#include <limits>

#define roop(i, n) for(int i=0;i<n;i++)
#define DIV 1000000007
//static const long double pi = 3.1415926535897932;

using namespace std;
using ll = long long int;
using ull = unsigned long long;

char toSmall(char c) { // 大文字を小文字へ
	return (c + 0x20);
}

char toLarge(char c) { // 小文字を大文字へ
	return (c - 0x20);
}

float myPower(int a, int n) { // aのn乗の計算
	float x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

ll combination(ll n, ll r) { // nCr の計算
	if (n < 0 || r < 0 || r > n) return -1;

	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> num(r);
	vector<ll> den(r);

	for (ll i = 0; i < r; i++) {
		num[i] = n - r + i + 1;
		den[i] = i + 1;
	}

	for (ll p = 2; p <= r; p++) {
		ll pivot = den[p - 1];
		if (pivot > 1) {
			ll offset = (n - r) % p;
			for (ll k = p - 1; k < r; k += p) {
				num[k - offset] /= pivot;
				den[k] /= pivot;
			}
		}
	}
	ll result = 1;
	for (ll k = 0; k < r; k++) {
		if (num[k] > 1) result *= num[k];
	}
	return result;
}

vector<string> split(const string& src, const char* delim = ",") { //カンマ区切り
	vector<string> vec;
	string::size_type len = src.length();

	for (string::size_type i = 0, n; i < len; i = n + 1) {
		n = src.find_first_of(delim, i);
		if (n == string::npos) {
			n = len;
		}
		vec.push_back(src.substr(i, n - i));
	}

	return vec;
}

bool check_int(string str)
{
	if (all_of(str.cbegin(), str.cend(), [](char ch) { return isdigit(ch);}))
	{
		return true;
	}
	return false;
}

struct rest {
	string s;
	int p;
	int num;

	/* -------------------------------------
	sort関数を使用したときのソートの定義をする。
	まずは文字列sでソートする。
	文字列sが同じだった場合、pでソートする。
	この条件を参考演算子で表現(ifでもOK)
	-------------------------------------*/
	bool operator<(const rest& right) const {
		return s == right.s ? p > right.p : s < right.s;
	}
};

int f(int n) {
	int ans = 0;
	int flag = 0;
	for (int x = 1; x <= sqrt(n); x++) {
		for (int y = x; y <= sqrt(n); y++) {
			for (int z = y; z <= sqrt(n); z++) {
				if ((x + y + z) * (x + y + z) - (x*y + y*z + z*x) == n) {
					if (x == y && y == z) {
						ans++;
					} else if (x == y || y == z) {
						ans += 3;
					} else {
						ans += 6;
					}
				}
			}
		}
	}
	return ans;
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cout << f(i) << endl;
	}
	return 0;
}

Measured memory_bytes: 3428
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define endl '\n'

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;

    vector<int> v(n);
    rep(i,n) cin >> v[i];

    int ans = 1e9;

    for(int p = 1; p <= 100; p++){
        int tmp = 0;
        for(int i = 0; i < n; i++){
            tmp += (v[i] - p) * (v[i] - p);
        }
        ans = min(ans,tmp);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define PI       3.1415926535897932384626433832795028841971
#define INF      100000000
#define EPS      1e-10
#define MOD      1000000007
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

ll n, m;
ll x[100001];
ll hoge[100001];
map<ll,ll> ma;
map<ll,ll>::iterator it;

int main(){
    cin >> n >> m;
    rep(i,n){
        ll y;
        cin >> y;
        ma[y]++;
        x[y%m]++;
    }
    for(it = ma.begin(); it != ma.end(); it++){
        ll p = (*it).first, q = (*it).second;
        hoge[p%m] += q/2;
    }
    ll ans = 0;
    rep(i,m-1){
        if((i+1)*2 == m){
            ans += x[i+1]/2;
            x[i+1] %= 2;
            continue;
        }
        ans += min(x[i+1],x[m-i-1]);
        ll z = min(x[i+1],x[m-i-1]);
        x[i+1] -= z;
        x[m-i-1] -= z;
    }
    ans += x[0]/2;
    for(ll i = 1; i < m; i++){
        ans += min(hoge[i],x[i]/2);
    }
    cout << ans << endl;
}


Measured memory_bytes: 8064
H, W, N = map(int, input().split())
AB = dict()
for i in range(N):
  a, b = list(map(int, input().split()))
  for i in range(3):
    for j in range(3):
      x = (a - 1) - i
      y = (b - 1) - j
      if (0 <= x < H - 2) and (0 <= y < W - 2):
        ab = str(x) + "ab" + str(y)
        if ab in AB:
          AB[ab] += 1
        else:
          AB[ab] = 1
#print(AB)          

ans = [0] * 10
for i in AB.values():
  ans[i] += 1
ans[0] = (H - 2) * (W - 2) - sum(ans)
for i in range(10):
  print(ans[i])

Measured memory_bytes: 248308