akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

//ポイント
//しりとり⇒有効グラフとみなせる
//一周する⇒各アルファベットの入次数と出次数が等しくなる
//          使用したアルファベットを全て探索できる

public class Main {

	// アルファベットの個数
	int MAX = 'Z' - 'A' + 1;

	// 入力
	char[][] s;

	// 隣接行列 アルファベットの数
	int[][] nei;

	// 入次数、出次数
	int[] indeg, outdeg;

	// あるアルファベットを訪れたかどうか
	// 訪れたら１、使用していない０、訪れていない-1
	int[] visit;

	boolean check() {
		// 入力されたアルファベットを全て通ったかどうか
		for (int i = 0; i < MAX; i++) {
			if (visit[i] == -1) {
				return false;
			}
		}

		// 入次数 == 出次数 : 返って来れる
		// 入次数 != 出次数 : ダメ
		for (int i = 0; i < MAX; i++) {
			if (indeg[i] != outdeg[i]) {
				return false;
			}
		}

		return true;
	}

	// 深さ優先探索
	void dfs(int k) {
		if (visit[k] == 1)
			return;

		visit[k] = 1;

		for (int i = 0; i < MAX; i++) {
			if (nei[k][i] == 1) {
				dfs(i);
			}
		}
	}

	void run() {
		Scanner sc = new Scanner(System.in);

		while (true) {
			int n = sc.nextInt();

			if (n == 0) {
				break;
			}

			int a = 0;
			s = new char[n][MAX];
			nei = new int[MAX][MAX];
			indeg = new int[MAX];
			outdeg = new int[MAX];
			visit = new int[MAX];

			Arrays.fill(visit, 0);

			// nextメソッドは空白まで
			for (int i = 0; i < n; i++) {
				s[i] = sc.next().toCharArray();

				// 入力された文字の最初と最後
				int u = s[i][0] - 'a';
				int v = s[i][s[i].length - 1] - 'a';

				// 入次数と出次数を計算
				indeg[v]++;
				outdeg[u]++;

				// アルファベット間に有効辺を引く
				nei[u][v] = 1;

				// 使用するアルファベット
				visit[u] = visit[v] = -1;

				a = u;
			}

			// しりとりをする
			dfs(a);

			if (check()) {
				System.out.println("OK");
			} else {
				System.out.println("NG");
			}
		}

		sc.close();

	}

	public static void main(String[] args) {
		new Main().run();
	}

}

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

int main() {
	int N,count;
	cin >> N;
	vector<int>pn(N);
	
	for(int i=0;i<N;i++){
		cin >> pn.at(i);
	}
	
	for (int i=1;i<N-1;i++){
		if(pn.at(i-1)<pn.at(i) &&pn.at(i)<pn.at(i+1)){
			count ++;
		}
		else if(pn.at(i+1)<pn.at(i) && pn.at(i) <pn.at(i-1)){
			count ++;
		}
	}
	
	cout << count << endl;
	
}



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

using namespace std;

const int N = 3e6 + 5, oo = 1e9;

int main()
{
    ll n, c = 0;
    ll sum = 0;
    scanf("%lld", &n);
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 1 ; j <= n ; j++)
        {
            for(int w = 1 ; w <= n ; w++)
            {
                sum += __gcd(i, __gcd(j, w));
            }
        }
    }
    printf("%lld\n", sum);
    return 0;
}


Measured memory_bytes: 3848
#include<cstdio>
using namespace std;
typedef long long LL;
LL n,num=1;
int ans1,ans2;
int main()
{
	scanf("%lld",&n);
	for(LL x=n;x;x/=10) ans1+=x%10,num*=10;
	num/=10;
	for(LL x=n/num*num-1;x;x/=10) ans2+=x%10;
	printf("%d",ans1>ans2?ans1:ans2);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
const int maxn=301000;
int n,L;
int a[maxn],t[maxn];
int b[maxn];
int main(){
//	freopen("D.in","r",stdin);
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&t[i]);
	long long cnt=1;
	for(int i=1;i<=n;i++){
		cnt=cnt+t[i]/(2*L);
		t[i]=t[i]%(2*L);
	}
	for(int i=1;i<=n;i++){
		if(t[i]==0) b[i]=0;
		else{
			if(t[i]<=a[i]*2)
				b[i]|=1;
			if(t[i]<=(L-a[i])*2)
				b[i]|=2;
			cnt++;
		}
	}
	int top=0,sum=0;
	if(b[n]&2) cnt--,b[n]=0;
	for(int i=n;i>=1;i--){
		if(b[i]<=0) continue;
		if(b[i]==1){
			if(top)
				top--,cnt--;
			else if(sum)
				sum--,top++;
		}
		else if(b[i]==2)
			top++;
		else{
			if(top)
				top--,sum++,cnt--;
			else
				top++;
		}
	}
	printf("%lld\n",cnt*L*2);
	return 0;
}


Measured memory_bytes: 3712
#define _GLIBCXX_DEBUG//TLEの原因になるので注意！！！！！！！！！！！
#include<cmath>
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<int> arr;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.xise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//#define int long long

//cerrはコメントアウトしなくても通る//ただしTLEを引き起こすことがある

ll N,M,H,W,K,Q,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
//const ll INF = 1LL << 60;
//typedef pair<ll,ll> P;
typedef pair<int, int> P;
bool chmx(int &a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

bool chmn(int &a, int b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}

int main(){
	double l;
	cin >> l;
	double r=l/3;
	double ans=r*r*r;
	printf("%.10lf\n",ans);
    return 0;
}



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

#define int long long

using namespace std;

const int N = 100, K = 3000, INF = 1e18;

struct node
{
    int city;
    int cost;
    int time;
};

vector<node> g[N];
int dp[N][K], c[N], d[N];

void dijkstra(int &s)
{
    dp[1][s] = 0;
    priority_queue<pair<int, pair<int, int>>> q;
    q.push({0, {s, 1}});
    while (!q.empty())
    {
        int utime = -q.top().first;
        int ucoin = q.top().second.first;
        int ucity = q.top().second.second;
        q.pop();
        if (dp[ucity][ucoin] < utime) continue;
        for (auto v : g[ucity])
        {
            if (ucoin >= v.cost && dp[v.city][ucoin - v.cost] > utime + v.time)
            {
                dp[v.city][ucoin - v.cost] = utime + v.time;
                q.push({-utime - v.time, {ucoin - v.cost, v.city}});
            }
        }
        if (ucoin + c[ucity] < K && dp[ucity][ucoin + c[ucity]] > utime + d[ucity])
        {
            dp[ucity][ucoin + c[ucity]] = utime + d[ucity];
            q.push({-utime - d[ucity], {ucoin + c[ucity], ucity}});
        }
    }
}

int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    
    int n, m, s;
    cin >> n >> m >> s;
    s = min(s, K - 1);
    while (m--)
    {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        g[u].push_back({v, a, b});
        g[v].push_back({u, a, b});
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> c[i] >> d[i];
        for (int j = 0; j < K; ++j) dp[i][j] = INF;
    }
    dijkstra(s);
    for (int i = 2; i <= n; ++i)
    {
        cout << *min_element(dp[i], dp[i] + K) << '\n';
    }
    return 0;
}


Measured memory_bytes: 7104
#include<bits/stdc++.h>
using namespace std;
#define fuck pair<int,int>
int p[200010],q[200010];
int pos[200010];
vector< fuck > v[200010];
priority_queue< fuck ,vector< fuck >,greater< fuck > > pq;
fuck fk;
struct Tree
{
    int l,r,val;
}tree1[400010],tree2[400010];
void build1(int id,int l,int r)
{
    tree1[id].l=l;tree1[id].r=r;
    if (l==r)
    {
        tree1[id].val=p[2*l-1];
        return ;
    }
    int mid=(l+r)/2;
    build1(id*2,l,mid);
    build1(id*2+1,mid+1,r);
    tree1[id].val=min(tree1[id*2].val,tree1[id*2+1].val);
}
void build2(int id,int l,int r)
{
    tree2[id].l=l;tree2[id].r=r;
    if (l==r)
    {
        tree2[id].val=p[2*l];
        return ;
    }
    int mid=(l+r)/2;
    build2(id*2,l,mid);
    build2(id*2+1,mid+1,r);
    tree2[id].val=min(tree2[id*2].val,tree2[id*2+1].val);
}
int query1(int id,int l,int r)
{
    if (tree1[id].l==l && tree1[id].r==r) return tree1[id].val;
    int mid=(tree1[id].l+tree1[id].r)/2;
    if (r<=mid) return query1(id*2,l,r);
    else
     if (l>mid) return query1(id*2+1,l,r);
     else return min(query1(id*2,l,mid),query1(id*2+1,mid+1,r));
}
int query2(int id,int l,int r)
{
    if (tree2[id].l==l && tree2[id].r==r) return tree2[id].val;
    int mid=(tree2[id].l+tree2[id].r)/2;
    if (r<=mid) return query2(id*2,l,r);
    else
     if (l>mid) return query2(id*2+1,l,r);
     else return min(query2(id*2,l,mid),query2(id*2+1,mid+1,r));
}
void dfs(int l,int r,int fl,int fr)
{
    int ll,rr,ans,pl,pr;
    if (l & 1)
    {
        ll=(l+1)/2;rr=r/2;
        ans=query1(1,ll,rr);pl=pos[ans];
        ll=(pl+1)/2;rr=r/2;
        ans=query2(1,ll,rr);pr=pos[ans];
    }
    else
    {
        ll=l/2;rr=(r-1)/2;
        ans=query2(1,ll,rr);pl=pos[ans];
        ll=(pl+2)/2;rr=(r+1)/2;
        ans=query1(1,ll,rr);pr=pos[ans];
    }
    v[p[fl]].push_back(make_pair(p[pl],p[pr]));
    if (l<pl) dfs(l,pl-1,pl,pr);
    if (pl+1<pr) dfs(pl+1,pr-1,pl,pr);
    if (pr<r) dfs(pr+1,r,pl,pr);
}
int main()
{
    int n,i,j,x,y,cnt,f,s;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        pos[p[i]]=i;
    }
    build1(1,1,n/2);
    build2(1,1,n/2);
    dfs(1,n,0,0);cnt=0;
    pq.push(v[0][0]);
    while(!pq.empty())
    {
        fk=pq.top();pq.pop();
        f=fk.first;s=fk.second;
        cnt++;q[cnt]=f;
        cnt++;q[cnt]=s;
        for(i=0;i<v[f].size();i++)
            pq.push(v[f][i]);
    }
    for(i=1;i<=n;i++)
        if (i==n) printf("%d\n",q[i]);
        else printf("%d ",q[i]);
    return 0;
}

Measured memory_bytes: 27392
/**
*    author:  Dooloper
*    created: 11.08.2020 21:57:55
**/

#pragma region Macros
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using P = pair<int,int>;
using ll = long long;

#define rep(i,n) for(int i = 0; i < (n); i++)
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
   cout << H << " ";
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

const double PI = acos(-1);
const int mod = 1000000007;
class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const {
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};
#pragma endregion

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  string s;
  ll ans = 0;
  cin >> s;
  int n = s.length() - 1;
  for(int i = 0; i < (1<<n); i++){
    int prev = 0;
    ll rec = 0;
    for(int j = 0; j < s.length()-1; j++){
      if(i & (1<<j)){
        for(int k = prev; k <= j; k++){
          rec = rec*10 + (s[k] - '0');
        }
        ans += rec;
        prev = j+1;
      }
      rec = 0;
    }
    for(int k = prev; k < s.length(); k++){
      rec = rec*10 + (s[k] - '0');
    }
    ans += rec;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define de(x) cout<<#x<<"="<<x<<endl
#define dd(x) cout<<#x<<"="<<x<<" "
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repd(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b,t) for(int i=a;i<(b);i+=t)
#define mt(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp(u,v) make_pair(u,v)
#define sz(a) (int)a.size()
#define pb push_back
#define PI acos(-1.0)
#define qc std::ios::sync_with_stdio(false)
#define all(a) a.begin(),a.end()
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;
typedef pair<int,pii> piii;

const ll mod = 1000000007;
const int N = 2e5+6;
const int M = 2e6+6;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;

bool eq(const db &a, const db &b) { return fabs(a - b) < eps; }
bool ls(const db &a, const db &b) { return a + eps < b; }
bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); }
ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); };
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//inv[1]=1;
//for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
int n;
string  s;
int main() {
	while(cin>>n>>s) {
		// cin>>s
		int ret = 0;
		rep(i, 0, sz(s) - 2) {
			if(s[i] == 'A') {
				if(s[i + 1] == 'B' && s[i + 2] == 'C') ret++;
			}
		}
		cout<<ret<<endl;
	}
    return 0;
}


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

using namespace std;

int ans;
int D, G;
vector<int> p, c;

void calc(int k, int count, int sum) {
	if (sum >= G) {
		if (count < ans) ans = count;
	}
	else if (k >= 0) {
		//100*(k+1)点問題を
		//完全に解く
		calc(k - 1, count + p[k], sum + 100 * (k + 1)*p[k] + c[k]);
		//全く解かない
		calc(k - 1, count, sum);
		//一部解く
		int num = (int)ceil((double)(G - sum) / (100 * (k + 1)));
		if (num < p[k] && ans > count + num) {
			ans = count + num;
		}
	}

}


int main() {
	cin >> D >> G;
	p.resize(D); c.resize(D);

	for (int i = 0; i < D; i++) {
		int tmp1, tmp2;
		cin >> tmp1 >> tmp2;
		p[i] = tmp1;
		c[i] = tmp2;
	}

	ans = 10000;
	calc(D - 1, 0, 0);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <functional>
    #include <cmath>
    using namespace std;
     
    int myPower(int a, int n) { // aのn乗の計算
    	int x = 1;
    	while (n > 0) { // 全てのbitが捨てられるまで
    		if ( n & 1) { // 一番右のbitが１のとき
    			x *= a;
    		}
    		a *= a;
    		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
    	}
    	return x;
    }
    
    int main() {
    	int i, j;
    	long long int n;
    	cin >> n;
    	long long int a[n+1];
    	long long int b[n];
    	for (i = 0; i < n+1; i++) {
    		cin >> a[i];
    	}
    	for (i = 0; i < n; i++) {
    		cin >> b[i];
    	}
    	long long int ans = 0;
    	for (i = 0; i < n; i++) {
    		if (b[i] > a[i]) {
    			b[i] -= a[i];
    			ans += a[i];
    			a[i] = 0;
    			if ((b[i] > (long long)0) && (a[i+1] - b[i] > (long long)0)) {
    				a[i+1] -= b[i];
    				ans += b[i];
    			} else if ((b[i] > (long long)0) && (a[i+1] - b[i] <= (long long)0)) {
    				ans += a[i+1];
    				a[i+1] = 0; 
    			}
    		} else {
    			a[i] -= b[i];
    			ans += b[i];
    		}
    	}
     
    	cout << ans << endl;
    	return 0;
    }

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

#define rep(i, n) for(int i = 0; i < n; i++)

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    string S; cin >> S;
    int ans = 0;
    int N = S.length();
    vector<char> ls(4);
    ls[0] = 'A'; ls[1] = 'G'; ls[2] = 'C'; ls[3] = 'T';
    int right = 0;
    for(int left = 0; left < N; left++){
        while(right < N){
            bool in = false;
            rep(i, 4) if(ls[i] == S[right]) in = true;
            if(in) right++;
            else break;
        }
        ans = max(ans, right-left);

        if(right == left) ++right;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
	n = readline() |> parseInt
	a,b = readline() |> split |> parseMap
	p = readline() |> split |> parseMap
	ca = 0
	cb = 0
	for i in 1:n
		if p[i] <= a
			ca += 1
		elseif p[i] <= b
			cb += 1
		end
	end
	println(min(ca,cb,n-ca-cb))
end

main()


Measured memory_bytes: 118476
#define _USE_MATH_DEFINES 
#include <cmath>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#define rep(i,start,n) for(int i=start;i<n;i++)
#define And &&
#define Or ||
#define Lb cout<<endl
using namespace std;

int main(void) {
	int n, m, l; cin >> n >> m >> l;
	vector<vector<int> > a(n, vector<int>(m));
	vector<vector<int> > b(m, vector<int>(l));
	vector<vector<long long> > c(n, vector<long long>(l));
	rep(i, 0, n) {
		rep(j, 0, m) {
			cin >> a[i][j];
		}
	}
	rep(i, 0, m) {
		rep(j, 0, l) {
			cin >> b[i][j];
		}
	}
	rep(i, 0, n) {
		rep(j, 0, l) {
			rep(k, 0, m) {
				c[i][j] += a[i][k] * b[k][j];
			}
		}
	}

	rep(i, 0, n) {
		rep(j, 0, l) {
			cout << c[i][j];
			if (j != l - 1)cout << " ";
		}
		Lb;
	}
}

Measured memory_bytes: 1372
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
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()))

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

# 素数判定
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

a,b = inpl()
d = make_divisors(fractions.gcd(a,b))
res = 0
for i in d:
    if is_prime(i):
        res += 1
print(res+1)

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

ll a[50];
int main() {
	for(ll i=0;i<50;i++){
		a[i]=49-i;
	}
	ll k;
	cin>>k;
	for(ll i=0;i<50;i++){
		a[i]+=k/50;
	}
	for(ll i=0;i<k%50;i++){
		a[i]++;
	}
	cout << 50<<endl;
	for(ll i=0;i<50;i++){
		cout << a[i]<<" ";
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

const int MAX_H = 310;
int H, W;
char c[MAX_H][MAX_H];

int cnt[MAX_H][MAX_H];

int dp[MAX_H][MAX_H];

long long count(const int i, const int h1, const int h2) {
    if (cnt[h1][h2] != -1) {
        return cnt[h1][h2];
    }
    if (h1 == H || h2 == H) {
        cnt[h1][h2] = 0;
        return 0;
    }
    long long ret = (c[H-h1][i] == c[H-h2][i+1]) ? 1 : 0;
    ret += count(i, h1+1, h2+1);
    cnt[h1][h2] = ret;
    return ret;
}

long long calc(const int i, const int h1, const int h2) {
    if (dp[h1][h2] != -1) {
        return dp[h1][h2];
    }
    if (h1 == H || h2 == H) {
        dp[h1][h2] = 0;
        return 0;
    }

    long long ret = count(i, h1, h2);
    ret += std::min(calc(i, h1+1, h2), calc(i, h1, h2+1));
    dp[h1][h2] = ret;
    return ret;
}

int main(int argc, char **argv) {
    std::cin >> H >> W;

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            std::cin >> c[i][j];
        }
    }

    //std::cout << c[1][1] << " " << c[2][3] << std::endl;

    //std::cout << calc(1, 0, 0);

    long long ret = 0;

    for (int i = 1; i < W; i++) {
        for (int j = 0; j <= H; j++) {
            for (int k = 0; k <= H; k++) {
                dp[j][k] = -1;
                cnt[j][k] = -1;
            }
        }
        ret += calc(i, 0, 0);
        //std::cout << i << " " << ret << std::endl;
    }

    std::cout << ret << std::endl;

    return 0;
}



Measured memory_bytes: 1152
def main():
    H, W = (int(i) for i in input().split())
    A = [input() for i in range(H)]
    cut_h = []
    cut_w = []
    for h in range(H):
        if all(s == "." for s in A[h]):
            cut_h.append(h)
    for w in range(W):
        if all("." == A[i][w] for i in range(H)):
            cut_w.append(w)
    for h in range(H):
        if h in cut_h:
            continue
        for w in range(W):
            if w in cut_w:
                continue
            print(A[h][w], end="")
        print()


if __name__ == '__main__':
    main()


Measured memory_bytes: 43096
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
typedef pair<int, int> P;
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const ll MOD = 1e9+7;

int n;
vector<int> abc(3);
int ans = INF;
vector<P> now(4, P(0, 0));

void dfs(int depth, vector<int> &l) {
    if (depth == n) {
        int tmp = 0;
        rep(i, 3) {
            if (now[i].second == 0) return;
            tmp += abs(abc[i] - now[i].first) + 10 * (now[i].second - 1);
        }
        ans = min(ans, tmp);
        return;
    }
    rep(i, 4) {
        now[i].first += l[depth];
        now[i].second += 1;
        dfs(depth + 1, l);
        now[i].first -= l[depth];
        now[i].second -= 1;
    }
}

int main() {
	cin >> n;
    rep(i, 3) cin >> abc[i];
    vector<int> l(n);
    rep(i, n) cin >> l[i];
    dfs(0, l);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
package main

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

var cache map[int64]int64

func main() {
	K := nextInt64()
	cache = map[int64]int64{}

	// primes := make([]bool, K+1)
	// primes[1] = true
	// primes[2] = true
	// for i := int64(3); i <= K; i++ {
	// 	primes[i] = true
	// 	for j := int64(2); j*j <= i; j++ {
	// 		if i%j == 0 {
	// 			primes[i] = false
	// 			break
	// 		}
	// 	}
	// }

	sum := int64(0)
	for a := int64(1); a <= K; a++ {
		// if primes[a] {
		// 	fmt.Println(a, K*K)
		// 	sum += K * K
		// 	continue
		// }
		for b := int64(1); b <= K; b++ {
			// if primes[b] {
			// 	fmt.Println(a, b, K)
			// 	sum += K
			// 	continue
			// }
			for c := int64(1); c <= K; c++ {
				// if primes[c] {
				// 	sum++
				// 	continue
				// }
				sum += gcd(gcd(a, b), c)
			}
		}
	}
	fmt.Println(sum)
}

func gcd(a, b int64) int64 {
	if b > a {
		a, b = b, a
	}
	key := a*1000 + b
	value, ok := cache[key]
	if !ok {
		for b != 0 {
			a, b = b, a%b
		}
		value = a
		cache[key] = a
	}
	return value
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 3240
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
int n, k, a[123456], b[123456];
signed main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++)cin >> a[i];
	int f = 0, l = 0, ans = n + 1, sum = 0;
	while (f < n) {
		while (sum < k && l < n) {
			if (a[l] <= k && b[a[l]] == 0)sum++;
			b[a[l++]]++;
		}
		if (sum < k)break;
		ans = min(ans, l - f);
		if (a[f] <= k && b[a[f]] == 1)sum--;
		b[a[f++]]--;
	}
	if (ans > n)cout << "0\n";
	else cout << ans << endl;
}


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

int d;
vector<int> cs;
vector<int> ts;
vector<vector<int> > sm;
int m;
vector<vector<int> > dq;

int total_satisfaction() {
	vector<int> ls;//(26, 0);
	for (int i = 0; i < 26; i++) ls.push_back(0);
	int s = 0;

	for (int i = 0; i < d; i++) {
		int t = ts[i];
		t--;
		s += sm[i][t];
		ls[t] = i + 1;
		
		int dis = 0;
		for (int j = 0; j < 26; j++) {
			dis += cs[j] * ((i+1) - ls[j]);
		}
		s -= dis;
	}

	return s;
}

int main() {
	
	cin >> d;

	int x;
	for (int i = 0; i < 26; i++) {
		cin >> x;
		cs.push_back(x);
	}
	for (int i = 0; i < d; i++) {
		vector<int> v;
		sm.push_back(v);
		for (int j = 0; j < 26; j++) {
			cin >> x;
			sm[i].push_back(x);
		}
	}
	for (int i = 0; i < d; i++) {
		cin >> x;
		ts.push_back(x);
	}

	cin >> m;
	dq.assign(m, vector<int>(2, 0));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < 2; j++) {
			cin >> dq[i][j];
		}
	}

	//for (int i = 0; i < 26; i++) cout << cs[i] << " ";
	//cout << endl;
	//for (int i = 0; i < d; i++) {
	//	for (int j = 0; j < 26; j++) {
	//		cout << sm[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	//for (int i = 0; i < d; i++) cout << ts[i] << " ";
	//cout << endl;
	
	for (int i = 0; i < m; i++) {
		int di = dq[i][0];
		int qi = dq[i][1];

		ts[di - 1] = qi;

		int s = total_satisfaction();
		printf("%d\n", s);
	}
}


Measured memory_bytes: 8680
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c, d;
  cin >> a >> b >> c >>d;
  if(a+b == c+d) {
      cout << "Balanced" << endl;
  }else if(a+b < c+d) {
      cout << "Right" << endl;
  }else{
      cout << "Left" << endl;
  }
}

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

#define ll long long
#define ld long double

using namespace std;

const long long LINF = LLONG_MAX;
const int INF = INT_MAX;
const int MOD = 1000000007;

const ld PI = 3.14159265358979323;

const int N = 2e2 + 111;

int n, a[N];

int main() {
    #ifdef Vova
        freopen("input", "r", stdin);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a+n);
    int ans = 0;
    for (int i = 0; i < n; i++){
        for (int j = upper_bound(a+i, a+n, a[i]) - a; j < n; j++){
            ans += lower_bound(a+j, a+n, a[i] + a[j]) - upper_bound(a+j, a+n, a[j]);
        }
    }
    cout << ans;
}

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

int main(){
  int n; cin>>n;
  ll sum=0,tox0=0;
  vector<int> num(n),ans(n);
  for(int i=0;i<n;i++){
    cin>>num[i];
    sum+=num[i];
    if(i%2==1){
      tox0+=2*num[i];
    }
  }ans[0]=sum-tox0;
  for(int i=0;i<n-1;i++){
    ans[i+1]=2*num[i]-ans[i];
    cout<<ans[i]<<' ';
  }
  cout<<ans[n-1]<<endl;
}

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

#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define INF ((1LL<<62)-(1LL<<31))


ll n;
int main(){
	scanf("%lld",&n);
	printf("%lld\n",n/3);
	return 0;
}

Measured memory_bytes: 128
N, A, B = map(int, input().split())
total = 0
for n in range(1, N + 1):
    i = n
    num = 0
    while n > 0:
        w = n % 10
        n = n // 10
        num += w
    if num >= A and num <= B:
        total += i
print(total)

Measured memory_bytes: 3060
#include <iostream>
using std::cin;
using std::cout;

int main (){
  int N,K,height,numOfGood = 0;
  cin >> N >> K ;
  for(int i = 0;i<N;++i){
    cin >> height;
    if(height >= K){
      numOfGood++;
    }
  }
  cout << numOfGood << std::endl;
  return 0; 
}

Measured memory_bytes: 256
/*author - Ashutosh Chitranshi*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"
#define pow2(x) ((x)*(x))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mod 998244353
#define ordered_set tree<pair<ll,ll>,null_type,less<pair<ll,ll>>,rb_tree_tag,tree_order_statistics_node_update>
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
#define mp make_pair
#define ff first
#define ss second
#define null NULL
#define all(c) (c).begin(),(c).end()
#define nl "\n"
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef vector< vl > vvl;
typedef pair< int,int > ii;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;
typedef map< int,int> mii;
ll dp[305][305][305];
ll dp1[305][305];
ll dp2[305][305];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string str;
   	cin >> str;
   	ll k;
   	cin >> k;
   	ll n = str.size();
   	k = min(n,k);
   	vl v;
   	for(int i=0;i<n;i++)
   	{
   		ll count = 0ll;
   		while(i<n && str[i] == '1')
   		{
   			count++;
   			i++;
   		}
   		v.eb(count);
   	}
   	ll size = v.size();
   	for(int i=0;i<=k;i++)
   		dp[0][0][i] = 1ll;
   	for(int i=0;i<size;i++)
   	{
	    for(int s=0;s<=n;s++)
	    {
	    	dp1[s][0] = dp[i][0][s];
	    	dp2[s][0] = dp[i][0][s];
	    }
	    for(int s=0;s<=n;s++)
	    {
	    	for(int j=1;j+s<=n;j++)
	        	dp1[s][j] = (dp1[s][j-1] + dp[i][j][j+s])%mod;
	      	for(int j = 1;j<= n;j++)
	        	dp2[s][j] = (dp2[s][j-1] + dp[i][j][s])%mod;
    	}
    	for(int j=0;j<=n;j++)
    	{
	    	for(int k=j;k<=n;k++)
	        	dp[i+1][j][k] = ((dp2[k][j] + dp1[k-j][j+v[i]])%mod - dp1[k-j][j] + mod)%mod;
    	}
  	}
  	cout << dp[size][0][0] << nl;
    return 0;
}

Measured memory_bytes: 219864
# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
# define int long long

using namespace std;

const int N = 2e5 + 7;

int cnt[N];

int32_t main() {
    speed;
    int a, b;
    cin >> a >> b;

    for ( int i = 1; i <= 1000; i++ ) {

        int x = i * 0.08, y = i * 0.1;

        if ( x == a && y == b ) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
}   
  

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}


int d[3] = {-1,0,1};
int main(){
    int n;cin>>n;
    map<int,int>G;
    int cnt = 0;
    REP(i,1,n){
        int a;cin>>a;
        if(G[a] == i)cnt++;
        G[i] = a;
    }
    cout<<cnt;
}



Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;



int main(void)
{
    int N, x, cnt = 0;
    cin >> N >> x;

    int chd[N];
    for(int i = 0; i < N; i++) cin >> chd[i];
    sort(chd, chd+N);

    for(int i = 0; i < N; i++)
    {
        if(x - chd[i] < 0)
        {
            break;
        }
        else
        {
            if(i == N - 1 and x != chd[i])
            {
                break;
            }
            x -= chd[i];
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int n;
  cin >> n;
  vector<int> memo(1000000, 0);
  for (int i = 0; i < n; i++) {
    int temp;
    cin >> temp;

    memo[temp]++;
    if (temp != 0) memo[temp - 1]++;
    memo[temp + 1]++;
  }

  cout << *max_element(memo.begin(), memo.end()) << endl;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
const ll INF = (1ll << 60);

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

  vi x(N);
  for (ll i = 0; i < N; i++) {
    cin >> x[i];
  }

  ll L;
  cin >> L;

  vvi dp(N, vi(20, -1));

  for (ll i = 0; i < N; i++) {
    dp[i][0] =
        distance(x.begin(), upper_bound(x.begin(), x.end(), x[i] + L)) - 1;
  }

  for (ll i = 1; i < 20; i++) {
    for (ll j = N - 1; j >= 0; j--) {
      dp[j][i] = dp[dp[j][i - 1]][i - 1];
    }
  }

  ll Q;
  cin >> Q;
  for (ll i = 0; i < Q; i++) {
    ll a, b;
    cin >> a >> b;

    a -= 1;
    b -= 1;

    if (a > b)
      swap(a, b);

    ll cnt = 0;
    while (true) {
      ll j =
          distance(dp[a].begin(), lower_bound(dp[a].begin(), dp[a].end(), b));
      if (j == 0) {
        cnt += 1;
        break;
      }
      a = dp[a][j - 1];
      cnt += 1ll << (j - 1);
    }

    cout << cnt << endl;
  }
}

Measured memory_bytes: 23040
#include<stdio.h>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>>
#include<stdlib.h>
#define MAX  100005
#define ll long long
using namespace std;
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    int n,sum=0;
    scanf("%d",&n);
    int a[2][101],b[101]={0},i,j;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[0][i]);
    }
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[1][i]);
    }
    sum=sum+a[0][0]+a[1][n-1];
    for(i=0;i<n-1;i++)
    {
        for(j=i;j<n-1;j++)
        {
            b[i]=b[i]+a[1][j];
        }
        for(j=0;j<i;j++)
        {
            b[i]=b[i]+a[0][j+1];
        }
    }
    sort(b,b+(n-1),cmp);
    sum=sum+b[0];
    printf("%d\n",sum);
    return 0;
}

Measured memory_bytes: 256
use std::io::{self, Stdin};
use std::str::{self, FromStr};
use std::error::Error;
use std::thread;

fn exec() {
    let mut sc = Scanner::new();
    let n: usize = sc.ne();
    let m: usize = sc.ne();
    let cc = m / 2;
    if n >= cc {
        println!("{}", cc);
        std::process::exit(0);
    }
    let rest = m - n * 2;
    let ans = n + rest / 4;
    println!("{}", ans);
}

fn main() {
    const DEFAULT_STACK: usize = 16 * 1024 * 1024;
    let builder = thread::Builder::new();
    let th = builder.stack_size(DEFAULT_STACK);
    let handle = th.spawn(|| { exec(); }).unwrap();
    let _ = handle.join();
}

#[allow(dead_code)]
struct Scanner {
    stdin: Stdin,
    id: usize,
    buf: Vec<u8>,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        Scanner {
            stdin: io::stdin(),
            id: 0,
            buf: Vec::new(),
        }
    }
    fn next_line(&mut self) -> Option<String> {
        let mut res = String::new();
        match self.stdin.read_line(&mut res) {
            Ok(0) => return None,
            Ok(_) => Some(res),
            Err(why) => panic!("error in read_line: {}", why.description()),
        }
    }
    fn next<T: FromStr>(&mut self) -> Option<T> {
        while self.buf.len() == 0 {
            self.buf = match self.next_line() {
                Some(r) => {
                    self.id = 0;
                    r.trim().as_bytes().to_owned()
                }
                None => return None,
            };
        }
        let l = self.id;
        assert!(self.buf[l] != b' ');
        let n = self.buf.len();
        let mut r = l;
        while r < n && self.buf[r] != b' ' {
            r += 1;
        }
        let res = match str::from_utf8(&self.buf[l..r]).ok().unwrap().parse::<T>() {
            Ok(s) => Some(s),
            Err(_) => {
                panic!("parse error, {:?}",
                       String::from_utf8(self.buf[l..r].to_owned()))
            }
        };
        while r < n && self.buf[r] == b' ' {
            r += 1;
        }
        if r == n {
            self.buf.clear();
        } else {
            self.id = r;
        }
        res
    }
    fn ne<T: FromStr>(&mut self) -> T {
        self.next::<T>().unwrap()
    }
}

Measured memory_bytes: 8572
#include <bits/stdc++.h>
 
#define ll long long
#define loop(a) loopi(i,a)
#define loopi(i,a) for(int i=0; i<(a); i++)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pow2(x) (1ll<<(x))
 
using namespace std;
 
const int Mod=1e9+7;

ll legendre(ll n, ll p){
	ll x=p;
	ll ans=0;
	while(n>=x){
		ans+=n/x;
		x*=p;
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	ll n;
	cin >> n;
	if(n%2==0){
		n=n/2;
		cout << legendre(n,5) << "\n";
	}
	else{
		cout << 0 << "\n";
	}
	return 0;
}


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

const int mod = 1000000007;
class mint {
    long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
    return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

mint f(mint k){
    return k*(k+1)/2;
}

int main(){
    mint k;
    int n,l;
    cin >> n >> l;
    k = mint(l);
    mint ans = 0;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    vector<int> forw(n),backw(n);
    rep(i,n){
        int cnt = 0;
        for(int j = i+1;j<=n-1;j++) if(a[i] > a[j]) cnt++;
        //cout << cnt << endl;
        forw[i] = cnt;
        cnt = 0;
        for(int j = 0;j<i;j++) if(a[i]>a[j]) cnt++;
        //cout << " " << cnt << endl;
        backw[i] = cnt;
    }

    for(auto v:forw) ans += mint(v)*f(k);
    for(auto v:backw) ans += mint(v)*f(k-1);
    //for(auto v:forw) cout << v << endl;
    cout << ans << endl;
}

Measured memory_bytes: 3620
//皆さん、第9回シンデレラガール総選挙は、トップでオンリーワンを目指す城ヶ崎美嘉に
//そしてボイスアイドルオーディションは、プログラミングが趣味の才女大石泉に、ぜひ投票をお願いします！
//#城ヶ崎美嘉を009のシンデレラに
//#大石泉の必勝プログラム
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int num[110];
int main()
{
	rep(i,105) num[i]=1;
	int n,k,d,a,out=0;
	cin>>n>>k;
	rep(i,k){
		cin>>d;
		rep(j,d){
			cin>>a;a--;num[a]=0;
		}
	}
	rep(i,n) out+=num[i];
	cout<<out<<endl;
}


Measured memory_bytes: 3632
#!/usr/bin/ruby
#
# 1032.rb: Course Planning for Lazy Students
#

### subroutines

def count_rec(k, num, csum, bits)
  return num if csum >= $u
  return $n if k >= $n

  min_num = count_rec(k + 1, num, csum, bits)

  ci, bi = $ncrs[k]
  if (bits & bi) == bi
    num0 = count_rec(k + 1, num + 1, csum + ci, bits | (1 << k))
    min_num = num0 if min_num > num0
  end

  min_num
end

### main

loop do
  $n, $u = gets.split.map(&:to_i)
  break if $n == 0 && $u == 0

  crs = []

  for i in (0...$n)
    ci, ki, *ris = gets.split.map(&:to_i)
    crs << [i, ci, ki, ris]
  end

  newseq = []
  newid = 0
  q = crs.clone

  while newid < $n
    cr = q.shift
    i, ci, ki, ris = cr

    if ris.select{|ri| newseq[ri].nil?}.length == 0
      newseq[i] = newid
      newid += 1
    else
      q << cr
    end
  end
  #p newseq

  $ncrs = []
  for cr in crs
    i, ci, ki, ris = cr

    nid = newseq[i]
    nrib = ris.inject(0){|b, ri| b | (1 << newseq[ri])}

    $ncrs[nid] = [ci, nrib]
  end
  #p $ncrs

  min_num = count_rec(0, 0, 0, 0)
  puts min_num
end

Measured memory_bytes: 6116
n, k = map(int, input().split())
h = list(map(int, input().split()))
h.insert(0,0) #index調整
 
dp = [1<<64] * (n+1)
dp[1] = 0
 
for i in range(2,n+1):
    for j in range(1,k+1):
        if i - j >= 1:
            dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]), dp[i])
            
print(dp[n])

Measured memory_bytes: 53856
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<int> si;
typedef map<string, int> msi;
typedef greater<int> gt;
typedef priority_queue<int, vector<int>, gt> minq;
typedef long long ll;
const ll INF = 1e18L + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  int n; cin >> n;
  string a,b,c;
  cin >> a>>b>>c;
  int ans=0;
  rep (i, n) {
    if (a[i]==b[i] && b[i]==c[i]) continue;
    if (a[i]==b[i] || b[i]==c[i] || a[i] == c[i]) ans++;
    else ans+=2;
  }
  cout << ans << endl;
  return 0;
} 

Measured memory_bytes: 256
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

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

        if x == y:
            return

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

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

    def find(self, x):          #親を出力
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def size(self, x):          #グループの要素数
        return -self.parents[self.find(x)]

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if x < 0}

    def group_count(self):      #グループの個数
        return len(self.roots())

    def all_group_members(self):      #グループのメンバー一覧
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

################

def main():
    N, M = map(int, input().split())
    P = list(map(int,input().split()))
    uf = UnionFind(N)
    for i in range(M):
        a,b = map(int,input().split())
        uf.union(a-1, b-1)

    ret = 0
    for i in range(N):
        if uf.same(P[i]-1, i):
            ret += 1
    print(ret)

if __name__ == '__main__':
    main()

Measured memory_bytes: 13812
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int x, y[1000] = {};
    int v, j;
    cin >> x;
    for (int i = 0;i < x;i++){
        cin >> y[i];
    }
    for(int i = 0;i < x;i++){
        if(i != x-1){
            printf("%d ", y[i]);
        }
        else{
            printf("%d\n", y[i]);
        }
    }
    for (int i = 1;i < x;i++){
        v = y[i];
        j = i - 1;
        while(j >= 0 && y[j] > v){
            y[j+1] = y[j];
            j--;
        }
        y[j+1] = v;
        for(int i = 0;i < x;i++){
            if(i != x-1){
                printf("%d ", y[i]);
            }
            else{
                printf("%d\n", y[i]);
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,k;cin >>n>>k;
    string s;cin >>s;
    int hap=0;
    for (int i=0;i<n-1;i++){
        if (s[i]==s[i+1]) hap++;
    }
    int pair = (n-1-hap)/2;
    if (pair>=k) hap += 2*k;
    else hap=n-1;
    cout << hap<<endl;
}

Measured memory_bytes: 512
n=int(input())
a=list(map(int,input().split()))
s=[0]*n
p=sum(a)
for i in range(n):
    p-=a[i]
    s[i]=p
ans=0
for i in range(n):
    ans+=(s[i]*a[i])
    ans=ans%(10**9+7)
print(ans)


Measured memory_bytes: 31720
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define ull unsigned ll
typedef long double ld;
#define ALL(a) (a).begin(),(a).end()
#define ifnot(a) if(not a)
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

void reader(int &a) { scanf("%d", &a); }
void reader(double &a) { scanf("%lf", &a); }
void reader(char a[]) { scanf("%s", a); }
void reader(char &a) { scanf(" %c", &a); }
void reader(ll &a) { scanf("%lld", &a); }
void reader(ull &a) { scanf("%llu", &a); }
// void reader(string& a){cin >> a;};
template<class T, class U> void reader(T& t, U& u) { reader(t); reader(u); }
template<class T, class U, class V> void reader(T& t, U& u, V& v) { reader(t); reader(u); reader(v); }

void writer(const int a, char c) { printf("%d", a); putchar(c); }
void writer(const ll a, char c) { printf("%lld", a); putchar(c); }
void writer(const ull a, char c) { printf("%llu", a); putchar(c); }
void writer(const double a, char c) { printf("%.20lf", a); putchar(c); }
void writer(const char a[]) { printf("%s", a); };
void writer(const char a[], char c) { printf("%s", a); putchar(c); };
void writer(const char a, char c) { putchar(a); putchar(c); };
template<class T> void writerLn(T t) { writer(t, '\n'); }
template<class T, class U> void writerLn(T t, U u) { writer(t, ' '); writer(u, '\n'); }
template<class T, class U, class V> void writerLn(T t, U u, V v) { writer(t, ' '); writer(u, ' '); writer(v, '\n'); }
template<class T> void writerArr(T x[], int n) { int i; if (!n) { putchar('\n'); return; }rep(i, n - 1) writer(x[i], ' '); writer(x[n - 1], '\n'); }
template<class T> void writerVec(vector<T> x) { int n = x.size(); int i; if (!n) { putchar('\n'); return; }rep(i, n - 1) writer(x[i], ' '); writer(x[n - 1], '\n'); }

vector<string> split(const string &str, char sep) { vector<string> v; stringstream ss(str); string buffer; while (getline(ss, buffer, sep)) { v.push_back(buffer); }return v; }
// #define int ll
bool test = 1;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define MAX MAX000
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................

int W, H;
char c[100][100];

signed main(void)
{
	ull i, j, k;
	while (1) {
		int n;
		cin >> n;
		if (n == 0) break;
		int cnt = 0;
		REP(i, n + 1, 2*n+1) {
			for (j = 2; j*j <= i; j++) {
				if (i % j == 0) break;
			}
			if (j*j > i) {
				cnt++;
			}
		}
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 3124