akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P std::pair<int,int>
#define PiP std::pair<int,std::pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp std::make_pair
#define prique(T) std::priority_queue<T,vector<T>,greater<T>>
using namespace std;
template<class T> inline void chmax(T &a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T &a, T b) {
	a = std::min(a, b);
}

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)
			return false;
	}
	return x != 1;
}
int gcd(int x, int y) {
	if (y == 0)
		return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i;
		res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m = mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)
		return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod ;
}
int get_rand(int MIN, int MAX) {
	std::random_device rnd;
	std::mt19937 mt32(rnd());
	std::uniform_int_distribution<int> engine(MIN, MAX);
	return engine(mt32);
}
/*--------Library Zone!--------*/

int n;
vector<int>G[200005];
int cnt[200005];
bool used[200005];
int ans;
int par[200005];
int dfs(int x){
	used[x]=true;
	int all=0;
	for(int i:G[x]){
		if(!used[i]){
			par[i]=x;
			cnt[x]+=dfs(i);
		}
	}
	cnt[x]++;
	return cnt[x];
}
signed main() {
	cin>>n;
	rep(i,n-1){
		int a,b;cin>>a>>b;
		a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0);
	int all=mod_pow(2,n);
	rep(i,n){
		int zen=mod_pow(2,n-1);
		zen--;
		for(int j:G[i]){
			if(j==par[i])continue;
			zen-=mod_pow(2,cnt[j])-1;
			zen=(zen+mod)%mod;
		}
		zen-=mod_pow(2,n-cnt[i])-1;
		zen=(zen+mod)%mod;
		ans+=zen;
		ans%=mod;
	}
	cout<<ans*mod_pow(all,mod-2)%mod<<endl;
}


Measured memory_bytes: 19328
#include <bits/stdc++.h>
#define mp make_pair
#define sqr(x) (x)*(x)
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=1000007;
const ll inf=0x3f3f3f3f;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int mod=1e9+7;
int pown(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=(1LL*ans*a)%mod;
        a=(1LL*a*a)%mod;
        b>>=1;
    }
    return ans;
}
void add(int &x,int y){
    x+=y;
    if(x>=mod) x-=mod;
}
int mul(int x,int y){
    return 1LL*x*y%mod;
}
void del(int x,int y){
    x-=y;
    if(x<0) x+=mod;
}
int fac[maxn],inv[maxn];
int C(int a,int b){
    if(a<b) return 0;
    return 1LL*fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int val[maxn];
int mu[maxn],phi[maxn],sum[maxn];
int len,p[2000007];
int main(){
    mu[1]=1;phi[1]=1;
	for(int i=2;i<=100009;i++){
		if(!phi[i]) p[++len]=i,mu[i]=-1,phi[i]=i-1;
		for(int k=1;k<=len&&i*p[k]<=100000;k++){
			if(i%p[k]!=0) phi[i*p[k]]=phi[i]*phi[p[k]],mu[i*p[k]]=mu[i]*mu[p[k]];
			else {phi[i*p[k]]=phi[i]*p[k],mu[i*p[k]]=0;break;}
		}
	}
    for(int i=1;i<=100000;i++) if(mu[i]==-1) mu[i]=mod-1;
    int n=read(),K=read();
    for(int i=1;i<=K;i++){
        for(int k=i;k<=K;k+=i) add(val[k],mul(i,mu[k/i]));
    }
    int sum=0;
    for(int i=1;i<=K;i++){
        add(sum,mul(val[i],pown(K/i,n)));
    }
    cout<<sum;
    return 0;
}

Measured memory_bytes: 4800
import math

n = int(input())

cnts = [0] * (n + 1)
sn = int(math.sqrt(n)) + 1
for x in range(1, sn + 1):
  for y in range(1, sn + 1):
    for z in range(1, sn + 1):
      g = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
      if 1 <= g <= n:
        cnts[g] += 1

for i in range(1, n + 1):
  print(cnts[i])


Measured memory_bytes: 9176
#include <bits/stdc++.h>
 
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
ll mod =  1000000007;
ll maxn = 1000000000;
 
//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pii という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------

int main(){
   ll n;
   cin>>n;
   vll a(n);
   rep(i,n)cin>>a.at(i);
   sort(ALL(a));
   cout<<a.at(n/2)-a.at(n/2-1)<<endl;
}
   



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define all(c) c.begin(),c.end()
#define init(c) memset(c,0,sizeof c)
#define S second
#define F first
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=20000005;
int n,k,x,t,a,b,m;
string s,s1;
vi v;
int main(){

	cin >> s >> s1;
	if(s == s1.substr(0,s.length())){
		cout << "Yes";
	}else{
		cout << "No";
	}


	
	return 0;
}

Measured memory_bytes: 3620
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

vector<int> G[100001];
vector<bool> used;

int main(){
    int n,k;
    cin>>n>>k;
    used.resize(n,false);
    
    vector<int> indeg(n,0), outdeg(n,0);
    
    rep(i,n){
        int to;
        cin>>to;
        to--;
        if(to>=0){
            G[i].pb(to);
            indeg[to]++;
            outdeg[i]++;
        }
    }
    rep(i,n){
        if(outdeg[i]==0)used[i] = true;
    }
    
    rep(i,n){
        if(indeg[i]==0){
            G[n].pb(i);
        }
    }
    
    vector<int> d(n+1,INF);
    d[n] = 0;
    
    queue<int> que;
    que.push(n);
    
    while(que.size()){
        int q = que.front();
        que.pop();
        
        for(auto e:G[q]){
            if(d[e]>d[q]+1){
                d[e] = d[q]+1;
                que.push(e);
            }
        }
    }
    rep(i,n){
        if(d[i]<=k)used[i] = true;
    }
    
    int ans = 0;
    rep(i,n)if(used[i])ans++;
    
    cout<<ans<<endl;
    
}

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

ll gcd(ll a, ll b){return b!=0 ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

int main(){
	int a, b;
	cin >> a >> b;
	string s;
	cin >> s;
	
	for(int i = 0; i < s.size(); ++i){
		if(i < a && '0' <= s[i] && s[i] <= '9') continue;
		if(i == a && s[i] == '-') continue;
		if(i > a && '0' <= s[i] && s[i] <= '9') continue;
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
//typedef tuple<ll, ll, ll> T;

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 dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w;
    cin>>h>>w;
    int odd=0;
    vector<vector<int>> hw(h,vector<int>(w,0));
    REP(i,h) REP(j,w){
        cin>>hw[i][j];
        if(hw[i][j]&1)odd++;
    }

    vector<pair<P,P>> res;
    int num=0;
    int x=0,y=0;
    for(int iter=0;iter<w*h;++iter){
        if(hw[x][y]&1)++num;
        int nx=x,ny=y;
        if(x%2==0){
            if(ny==w-1) ++nx;
            else ++ny;
        }
        else{
            if(ny==0)++nx;
            else --ny;
        }
        if(num&1) if(num<odd) res.push_back(pair<P,P>(P(x,y),P(nx,ny)));
        x=nx,y=ny;
    }
    cout<<res.size()<<endl;
    for(auto p:res){
        cout<<p.first.first+1<<" "<<p.first.second+1<<" "<<p.second.first+1<<" "<<p.second.second+1<<endl;
    }
}


Measured memory_bytes: 5236
a = int(input())
b = int(input())
c = int(input())
x = int(input())
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            temp = 500 * i + 100 * j + 50 * k
            if temp == x:
                ans += 1
            elif temp > x:
                break
        if 500 * i + 100 * j > x:
            break
print(ans)

Measured memory_bytes: 3064
import sys
import math
import heapq


def input():
    return sys.stdin.readline().rstrip()


def dijkstra(s, n, es, L):
    # n:頂点数, es: 辺uvのコスト
    d = [10 ** 14 + 7] * n
    # 探索リスト
    S = [(0, s)]
    # 優先度付きキューを使うと計算量が少なくなるよ
    heapq.heapify(S)
    used = [False] * n

    d[s] = 0

    while S:
        # 最小コストの頂点を取り出し
        dg, v = heapq.heappop(S)
        if used[v] == True:
            continue
        used[v] = True
        for u, w in es[v]:
            if d[v] % L + w > L:
                cost = d[v] - d[v] % L + L + w
            else:
                cost = d[v] + w

            if d[u] > cost:
                d[u] = cost
                heapq.heappush(S, (d[u], u))

        # print("d", d)
    return d


def main():
    N, M, L = map(int, input().split())

    dp = [[L+2]*N for _ in range(N)]
    for i in range(N):
        dp[i][i] =0
    for i in range(M):
        x, y, z = map(int, input().split())
        if z > L:
            continue

        x = x - 1
        y = y - 1
        dp[x][y] =z
        dp[y][x]=z



    def warshal(ws,n):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    ws[i][j] =min(ws[i][j],ws[i][k]+ws[k][j])
        return ws

    ls =warshal(dp,N)
    for i in range(N):
        for j in range(N):
            if ls[i][j] <=L:
                ls[i][j] =1
            else:
                ls[i][j] =500
    vs = warshal(ls,N)

    Q =int(input())

    for j in range(Q):
        s,t =map(int,input().split())
        ans = vs[s - 1][t - 1] - 1
        if ans >=N:
            print(-1)
        else:
            print(vs[s-1][t-1]-1)





if __name__ == "__main__":
    main()

# \n


Measured memory_bytes: 78228
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N; cin>>N;
    vector<long long> d(N);
    for(int i=0;i<N;i++)cin>>d[i];
    sort(d.begin(),d.end());
    long long l,s;
    l=d[(N/2)-1];
    s=d[N/2];
    if(l==s)cout<<0<<endl;
    else cout<<s-l<<endl;

}

Measured memory_bytes: 1152
A,B,C,K = map(int,input().split())

a = min(K, A)  # 1を選ぶ数
G = K - a
b = min(G,B)#０を選ぶ数
F = G - b
c = min(F,C)
D = F - c
print(a+(-1*c))

Measured memory_bytes: 9132
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}


signed main() {
    int N;
    cin >> N;
    vi shops(N, 0);
    vvi p(N, vi(10));
    rep(i, N) {
        int mul = 1;
        rep(j, 10) {
            int f;
            cin >> f;
            shops[i] += f*mul;
            mul *= 2;
        }
    }
    rep(i, N) rep(j, 11) cin >> p[i][j];

    int res = -1e15;
    for(int i=1; i<(1<<10); i++) {
        int temp = 0;
        rep(j, N) {
            int ti = i, tj = shops[j];
            int cnt = 0;
            rep(k, 10) {
                if(ti&1 && tj&1) cnt++;
                ti>>=1; tj>>=1;
            }
            temp += p[j][cnt];
        }
        res = max(res, temp);
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
//using P = pair<int,int>;
//#########################################
const int mod = 1000000007;
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
vector<int> f = {1},fi = {1};
int fact(int x){
    while((int)f.size() <=x)f.push_back((f.back()*f.size())%mod);
    return f[x];
}
int ifact(int x){
    return modpow(fact(x),mod-2,mod);
}
int C(int x,int y){
    if(x < y)return 0;
    return fact(x)*ifact(y)%mod*ifact(x-y)%mod;
}
int P(int x,int y){
    if(x < y)return 0;
    return fact(x)*ifact(x-y)%mod;
}
signed main(){
    int n,m;cin >> n >> m;
    int ans = P(m,n)*P(m,n)%mod;
    for(int k = 1;k <= n;k++){
        int now = C(n,k)*P(m,k)%mod*P(m-k,n-k)%mod*P(m-k,n-k)%mod;
        if(k%2)now = -now;
        ans += now;
    }
    cout << (ans%mod + mod)%mod << endl;

    return 0;
}

Measured memory_bytes: 7416
#include<cstdio>
#include<string>
#include<cstring>
#include<utility>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<vector>
#include<iostream>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define inf 0x7fffffff
using namespace std;
vector<int> ve[5];
bool vis[5];
int dfs(int x,int y)
{
//	printf("%d %d\n",x,y);
	if(y==4)
	{
		return 1;
	}
	int i,an=0;
	for(i=0;i<ve[x].size();i++)
	{
		if(!vis[ve[x][i]])
		{
			vis[ve[x][i]]=1;
			an|=dfs(ve[x][i],y+1);
		}
	}
	return an;
}
int main()
{
	int i,j,k,n,m,x,y;
	scanf("%d%d",&x,&y);
	ve[x].push_back(y);
	ve[y].push_back(x);
	scanf("%d%d",&x,&y);
	ve[x].push_back(y);
	ve[y].push_back(x);
	scanf("%d%d",&x,&y);
	ve[x].push_back(y);
	ve[y].push_back(x);
	vis[1]=1;
	if(dfs(1,1))
	{
		printf("YES");
	}
	else
	{
		printf("NO");
	}
}


Measured memory_bytes: 384
program main
   integer :: x(3),t(3) = (/ 4, -9, 5 /)
   read(*, *)n,m
   i = n - m/1000
   dmax = i*2.d0/9.d0
   k = floor(dmax)
   x = (/-i, 2*i, m/1000/) + k*t
   if(any(x < 0)) x = -1
   write(*, *) x
end

Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Main {

	static int n, m;
	static ArrayList<ArrayList<Integer>> al;
	static int count;

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		n = sc.nextInt();
		m = sc.nextInt();
		al = new ArrayList<>();
		for (int i = 0; i < n; i++)
			al.add(new ArrayList<>());
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			al.get(a).add(b);
			al.get(b).add(a);
		}

		count = 0;
		boolean[] reach = new boolean[n];
		dfs(0, 0, reach);
		out.println(count);
		out.flush();
	}

	static void dfs(int now, int num, boolean[] reach) {
		if (num == n - 1) {
			count++;
			return;
		}
		for (Integer v : al.get(now)) {
			reach[now] = true;
			if (!reach[v]) dfs(v, num + 1, reach);
			reach[now] = false;
		}
	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) { return false; }
		}
		return true;
	}

	private byte readByte() {
		if (hasNextByte()) {
			return buffer[ptr++];
		} else {
			return -1;
		}
	}

	private boolean isPrintableChar(int c) {
		return '!' <= c && c <= '~';
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext()) { throw new NoSuchElementException(); }
		StringBuilder sb = new StringBuilder();
		byte b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public int nextInt() {
		if (!hasNext()) { throw new NoSuchElementException(); }
		int n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) { throw new NumberFormatException(); }
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public long nextLong() {
		if (!hasNext()) { throw new NoSuchElementException(); }
		long n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) { throw new NumberFormatException(); }
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

}

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

using namespace std;

//int a[1000000];

int deal(vector<int> a) {
    int cnt = 0;
    for(int i = 1; i < a.size(); i++) {
        if(a[i] == a[i - 1]) {
            cnt += 1;
            a[i] ^= 1;
        }
    }
    return cnt;
}

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

    string s;
    cin >> s;

    vector<int> a(s.length());
    for(int i = 0; i < s.length(); i++)
        a[i] = s[i] - '0';

    int ans = deal(a);

    a[0] ^= 1;

    ans = min(ans, 1 + deal(a));
    cout << ans << endl;
}


Measured memory_bytes: 1232
import java.util.*;
 
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
      
      int x = n-1;
      if(n==m){
        System.out.print(x*x);
      }else{
        System.out.print((x*x)+((m-n)*x));
      }
      
    }
}

Measured memory_bytes: 23124
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;
    int X[m], L[m-1];
    rep(i, m) {
        cin >> X[i];
    }

    sort(X, X+m);

    rep(i, m-1) {
        L[i] = X[i+1] - X[i];
    }
    
    sort(L, L+m-1);

    if(m <= n) {
        cout << 0;
    }
    else {
        int ans = X[m-1] - X[0];
        for(int i = 0; i < n-1; i++) {
            ans -= L[m-2-i];
        }

        cout << ans;
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 1024
def main():

    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            ans += A[i] * A[j]
    print(ans)
    ans /= N * (N - 1) / 2

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<P>> a(n);
    rep(i,n){
        int b;
        cin >> b;
        rep(j,b){
            int x, y;
            cin >> x >> y;
            x--;
            a[i].emplace_back(x, y);
        }
    }
    int ans = 0;
    rep(S,(1<<n)){
        int score = 0;
        vector<bool> tru(n, false);
        rep(j,n){
            if((S>>j) & 1){
                score++;
                tru[j] = true;
            }
        }
        bool con = true;
        rep(i,n){
            if(tru[i]){
                rep(j,a[i].size()){
                    if(a[i][j].second == 0){
                        if(tru[a[i][j].first]){
                            score = -1;
                            break;
                        }
                    }
                    else{
                        if(!tru[a[i][j].first]){
                            score = -1;
                            break;
                        }
                    }
                }
                if(score == -1) break;
            }
        }
        chmax(ans, score);
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    int N, Y, sum, x = -1, y = -1, z = -1;
    cin >> N >> Y;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j + i <= N; j++) {
            sum = 10000 * i + 5000 * j + 1000 * (N - i - j);
            if (sum == Y) {
                x = i, y = j, z = (N - i - j);
                break;
            }
        }
    }
    cout << x << " " << y << " " << z << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
al = list(map(int,input().split()))

head = 0
tail = 0
sub = 0
ll = 0
ans = 0
while True:
    if sub + al[tail] == sub ^ al[tail]:
        ll += 1
        if tail == n-1:
            for i in range(ll+1):
                ans += i
            break
        sub += al[tail]
        tail += 1
    else:
        ans += ll
        ll -= 1
        sub -= al[head]
        head += 1

print(ans)

Measured memory_bytes: 77644
coin = [500,100,50,10]
flag = false
loop{
	price = gets.chomp.to_i;
	if (price == 0) then
		break;
	end
	if flag then
		puts ""
	end
	flag = true
	arr = gets.split.map(&:to_i).reverse!
	
	amount = 0
	arr.each_index{|i|
		amount += arr[i] * coin[i]
	}
	last = amount - price
	
	lc = Array.new(4,0)
	
	coin.each_with_index{|c, i|
		lc[i] = last / c
		last -= lc[i] * c
	}
	lc.reverse!
	arr.reverse!
	
	coin.reverse.each_with_index{|c,i|
		if (arr[i] > lc[i]) then
			puts c.to_s + " " + (arr[i] - lc[i]).to_s			
		end
	}
}

Measured memory_bytes: 6104
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <numeric>
#include <regex>

#define FOR(i, f, n) for(int (i) = (f); (i) < (n); (i)++)
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (n); (i)--)
#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define RREP(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define forin(i, a) for(auto i: (a))
#define p(...) printf(__VA_ARGS__); cout << endl;
#define in(...) __VA_ARGS__; input__(__VA_ARGS__);
#define input(...) in(__VA_ARGS__)
#define out(...) output__(__VA_ARGS__);
#define output(...) out(__VA_ARGS__)
#define list_input(x, n) x[(n)]; for(int (i) = 0; (i) < (n); (i)++) cin >> x[i];
#define lambda(a, b, c) [](auto const &a, auto const &b){ return c ;}
#define key(t, x, compare) [](const t &a, const t &b){ return a x compare b x ;}
#define unless(a) if(!(a))

using namespace std;

using pii = pair<int, int>;

template <class... T>
void input__(T &...a) {
  for(auto v: {&a...}) {
    cin >> *v;
  }
}

void output__(){
  cout << endl;
}

template <class Head, class... T>
void output__(Head const &v, T const &...a) {
  if(sizeof...(a) == 0) {
    cout << v;
  } else {
    cout << v << " ";
  }
  output__(a...);
}

int main(){
  int in(a, b);
  string in(s);
  rep(i, a) {
    unless('0' <= s[i] and s[i] <= '9') {
      out("No");
      exit(0);
    }
  }
  unless(s[a] == '-') {
    out("No");
    exit(0);
  }
  FOR(i, a + 1, b + a) {
    unless('0' <= s[i] and s[i] <= '9') {
      out("No");
      exit(0);
    }
  }
  out("Yes");
}


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

typedef long long ll;
const ll mod = 1000000007;

int main() {
    int n;
    cin >> n;
    string alphabet = "abcdefghijklmnopqrstuvwxyz";
    map<char, int>mp;

    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        map<char, int> m;
        for (int j = 0; j < s.size(); j++) {
            m[s[j]]++;
        }
        for (int j = 0; j < alphabet.size(); j++) {
            if (i == 0) {
                mp[alphabet[j]] = m[alphabet[j]];
            } else {
                mp[alphabet[j]] = min(mp[alphabet[j]], m[alphabet[j]]);
            }
        }
    }

    string ans = "";
    for (int i = 0; i < alphabet.size(); i++) {
        if (mp[alphabet[i]] > 0) {
            for (int j = 0; j < mp[alphabet[i]]; j++) {
                ans += alphabet[i];
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import math
N = int(input())
D = [int(x) for x in input().split()]

num = [0] * 100000

maxd = 0
for d in D:
    num[d] += 1
    maxd = max(d, maxd)

if D[0] != 0 or num[0] != 1:
    ans = 0
else:
    ans = 1
    for i in range(1, maxd):
        for _ in range(num[i+1]):
            ans *= num[i]%998244353
        ans %= 998244353
        if ans == 0:
            break
print(ans%998244353)


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

typedef long long ll;
// 二次元累積和
ll sum[10000][10000];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        int x, y;
        char c;
        cin >> x >> y >> c;
        
        // すべて(c='B')にして、([0, 2k), [0, 2k))に圧縮
        if(c == 'W'){
            y += k;
        }
        x %= 2 * k;
        y %= 2 * k;
        
        ++sum[x + 1][y + 1];
    }
    
    // 二次元累積和
    // 横方向の累積和
    for(int i = 0; i <= 2 * k; ++i){
        for(int j = 0; j <= 2 * k; ++j){
            sum[i][j+1] += sum[i][j];
        }
    }
    // 縦方向の累積和
    for(int i = 0; i <= 2 * k; ++i){
        for(int j = 0; j <= 2 * k; ++j){
            sum[i+1][j] += sum[i][j];
        }
    }
    
    ll res = 0;
    // (0, 0) ~ (2k-1, 2k-1)
    for(int tx = 0; tx < 2 * k; ++tx){
        for(int ty = 0; ty < 2 * k; ++ty){
                ll temp = 0;
                
                // ([0, 2k], [0, 2k])内の黒に塗る部分に関して、点の数を足し合わせる
                if(tx <= k && ty <= k){
                    temp += sum[tx][ty];
                    temp += sum[tx][2*k] - sum[tx][ty+k];
                    temp += sum[2*k][ty] - sum[tx+k][ty];
                    temp += sum[tx+k][ty+k] - sum[tx+k][ty] - sum[tx][ty+k] + sum[tx][ty];
                    temp += sum[2*k][2*k] - sum[2*k][ty+k] - sum[tx+k][2*k] + sum[tx+k][ty+k];
                }
                else if(tx > k && ty > k){
                    temp += sum[tx-k][ty-k];
                    temp += sum[tx-k][2*k] - sum[tx-k][ty];
                    temp += sum[2*k][ty-k] - sum[tx][ty-k];
                    temp += sum[tx][ty] - sum[tx][ty-k] - sum[tx-k][ty] + sum[tx-k][ty-k];
                    temp += sum[2*k][2*k] - sum[2*k][ty] - sum[tx][2*k] + sum[tx][ty];
                }
                else if(tx > k){        // tx > k && ty <= k
                    temp += sum[tx][ty] - sum[tx-k][ty];
                    temp += sum[tx-k][ty+k] - sum[tx-k][ty];
                    temp += sum[tx][2*k] - sum[tx][ty+k] - sum[tx-k][2*k] + sum[tx-k][ty+k];
                    temp += sum[2*k][ty+k] - sum[2*k][ty] - sum[tx][ty+k] + sum[tx][ty];
                }
                else{       // tx <= k && ty > k
                    temp += sum[tx+k][ty-k] - sum[tx][ty-k];
                    temp += sum[tx][ty] - sum[tx][ty-k];
                    temp += sum[tx+k][2*k] - sum[tx+k][ty] - sum[tx][2*k] + sum[tx][ty];
                    temp += sum[2*k][ty] - sum[2*k][ty-k] - sum[tx+k][ty] + sum[tx+k][ty-k];
                }
                
                res = max(res, temp);
        }
    }
    
    cout << res << endl;
}

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

int main() {
  int n;
  string s;
  bool a = false;
  cin >> n;
  for (int i; i < n; i++) {
    cin >> s;
    if (s == "Y") {
      a = true;
      break;
    }
  }
  if (a) cout << "Four" << endl;
  else cout << "Three" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;cin>>N;
    long A[N],B[N];long sum_A=0,sum_B=0;
    vector<long> plus;long minus=0;int rec=0; 
    for(int i=0;i<N;i++){
        cin>>A[i];
        sum_A+=A[i];
    }for(int j=0;j<N;j++){
        cin>>B[j];
        sum_B+=B[j];
        if(A[j]>B[j]){
            plus.push_back(A[j]-B[j]);
        }else if(A[j]<B[j]){
            rec++;
            minus+=B[j]-A[j];
        }
    }if(sum_A<sum_B){
        cout<<-1<<endl;
    }else{
        sort(plus.begin(),plus.end());
        reverse(plus.begin(),plus.end());
        long result=0;
        for(int j=0;j<plus.size();j++){
            if(result>=minus){
                cout<<rec+j<<endl;
                return 0;
            }result+=plus.at(j);
        }cout<<rec+plus.size()<<endl;
    }
}

Measured memory_bytes: 2296
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 200010;
const int MAXM = 1000010;
const int MAXK = 510;
const int MAXQ = 200010;

int n, a[MAXN], b[MAXN];
vector<int> res;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    FOR(i,1,n) cin >> a[i];
    FORE(i,n,1) {
        if (a[i] == 1) {
            if (b[i] == 0) b[i] = 1;
            else b[i] = 0;
        }
        else {
            if (b[i] == 0) b[i] = 0;
            else b[i] = 1;
        }
        FOR(j,1,int(sqrt(i))) {
            if (i % j == 0) {
                if (j != i) b[j] = (b[j] + b[i]) % 2;
                if (i / j != i && i / j != j) b[i/j] = (b[i/j] + b[i]) % 2;
            }
        }
    }
    FOR(i,1,n)
        if (b[i]) res.emplace_back(i);
    cout << SZ(res) << "\n";
    FOR(i,0,SZ(res)-1) cout << res[i] << ' ';
    return 0;
}


Measured memory_bytes: 3192
use std::str::FromStr;

fn get_one<T : FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    return s.trim().parse().ok().unwrap();
}

fn get_vec<T : FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    return s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();
}

fn get_vec_by_lines<T : FromStr>(n : usize) -> Vec<T> {
    let mut v : Vec<T> = Vec::new();
    for _i in 0..n {
        let x : T = get_one();
        v.push(x);
    }
    return v;
}

fn main() {
    let s : String = get_one();
    if s.contains('A') && s.contains('B') {
        println!("{}", "Yes");
    }
    else {
        println!("{}", "No");
    }
}


Measured memory_bytes: 4352
// AtCoder Regular Contest 061
// E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

#include <cstdio>
#include <unordered_map>
#include <queue>
#include <utility>
#include <functional>
#define MAX_N 100000
#define MAX_C 1000000
#define INF 100000000
#define S 0
#define T (N - 1)
#define ARR 0 // arrival 到着
#define DEP 1 // departure 出発
#define TRS 2 // transfer 乗換
using namespace std;


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


class Graph {
public:
  void add_edge(ll from, ll to, int cost); // 有向辺を追加
  void dijkstra(ll s);
  ll count_at(ll s);
  unordered_map<ll, int> dist;
private:
  unordered_map<ll, vector<PAIR> > g; // cost, to
};

void Graph::add_edge(ll from, ll to, int cost) {
  g[from].push_back(PAIR(cost, to));
  return;
}

void Graph::dijkstra(ll s) {
  priority_queue<PAIR, vector<PAIR>, greater<PAIR> > q;
  PAIR p, e;

  dist.clear();
  dist[s] = 0;
  q.push(PAIR(dist[s], s));
  while(!q.empty()){
    p = q.top();
    q.pop();
    if (dist[p.second] == 0 && p.second != s) {
      dist[p.second] = INF;
    }
    if (dist[p.second] < p.first) {
      continue;
    }
    for (ll i = 0; i < (ll)g[p.second].size(); i++) {
      e = g[p.second][i];
      if (dist[e.second] == 0 && e.second != s) {
        dist[e.second] = INF;
      }
      if (dist[e.second] > dist[p.second] + e.first) {
        dist[e.second] = dist[p.second] + e.first;
        q.push(PAIR(dist[e.second], e.second));
      }
    }
  }
  return;
}

ll Graph::count_at(ll s) {
  return g[s].size();
}



int N, M;
Graph G;
int ans;

ll to_index(int n, int c, int type) {
  return (ll)n * (MAX_C * 2 + 1) + type * MAX_C + (type == TRS ? 0 : c);
}

void one_way_connect(int from, int to, int c) {
  ll s_dep, t_arr;
  s_dep = to_index(from, c, DEP);
  t_arr = to_index(to, c, ARR);

  // 駅 n における鉄道会社 c の最初の路線を作成するとき
  // 駅内の edge を新設
  if (G.count_at(s_dep) == 0) {
    G.add_edge(to_index(from, c, TRS), s_dep, 1);
  }
  if (G.count_at(t_arr) == 0) {
    G.add_edge(t_arr, to_index(to, c, TRS), 0);
    G.add_edge(t_arr, to_index(to, c, DEP), 0);
  }

  G.add_edge(s_dep, t_arr, 0);
}

int main() {

  int p, q, c;

  scanf("%d%d", &N, &M);
  for (int i = 0; i < M; i++) {
    scanf("%d%d%d", &p, &q, &c);
    p--; q--; c--;
    one_way_connect(p, q, c);
    one_way_connect(q, p, c);
  }

  G.dijkstra(to_index(S, -1, TRS));

  ans = G.dist[to_index(T, -1, TRS)];
  if (ans == INF || (ans == 0 && S != T)) {
    ans = -1;
  }
  printf("%d\n", ans);

  return 0;

}




Measured memory_bytes: 129424
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<cassert>
#include<numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
const int INF = 1001001001;
const long long LINF = 1001002003004005006ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int,int> P;

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll 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;
  }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(){
  int n;
  cin >> n;
  mint ans = mint(10).pow(n);
  ans -= mint(9).pow(n);
  ans -= mint(9).pow(n);
  ans += mint(8).pow(n);
  cout << ans << endl;
}

Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int L[2010];
bool judge(int x, int y, int z) {
	if (x < y + z && y < x + z && z < x + y) return true;
	else return false;
}
int main() 
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> L[i];
	sort(L, L + N);
	ll ans = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			int ok = j;
			int ng = N;
			while (abs(ok - ng) > 1) {
				int mid = (ok + ng) / 2;
				if (judge(L[i], L[j], L[mid])) ok = mid;
				else ng = mid;
			}
			ans += ok - j;
		}
	}
	cout << ans << endl;
}


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

using ll = long long;
const ll MOD = 1e9 + 7;

int main() {
    int N, M, p;
    cin >> N >> M;
    vector<int> AC(N, 0), WA(N, 0);
    string S;
    rep(i, M) {
        cin >> p >> S;
        p--;
        if (S == "AC") {
            AC[p] = 1;
        } else {
            if (AC[p] == 0) WA[p]++;
        }
    }
    int ansAC = 0, ansWA = 0;
    rep(i, N) {
        ansAC += AC[i];
        if (AC[i] == 1) ansWA += WA[i];
    }
    cout << ansAC << " " << ansWA << endl;
}

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

#define reint register int
#define coint const int

using namespace std;

char li1[10], li2[10];

int main(void) {
    scanf("%s%s", li1 + 1, li2 + 1);
    int cnt = (li1[1] == li2[1]) + (li1[2] == li2[2]) + (li1[3] == li2[3]);
    printf("%d\n", cnt);
    return 0;
}


Measured memory_bytes: 256
function main()
    h, w = parse.(Int, split(readline()))
    s = Vector{String}(undef, h)
    for i in 1:h
         s[i] = readline()
    end
    dx = [0, 1]
    dy = [1, 0]
    dp = zeros(Int, h, w)
    fill!(dp, 10000)
    dp[1,1] = ifelse(s[1][1] == '#', 1, 0)

    for i in 1:h
        for j in 1:w
            for dir in 1:2
                ni = i + dx[dir]
                nj = j + dy[dir]

                ni > h && continue
                nj > w && continue

                dif = ifelse(s[ni][nj] == '#' && s[i][j] == '.', 1, 0)
                dp[ni, nj] = min(dp[ni, nj], dp[i, j] + dif)
            end
        end
    end

    println(dp[end,end])
end


main()

Measured memory_bytes: 181580
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  ll dp[n + 1] = {};
  dp[0] = 2;
  dp[1] = 1;
  rep(i, 2, n + 1) dp[i] = dp[i - 1] + dp[i - 2];

  cout << dp[n] << endl;
}


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

int main()
{
  int n, m;
  while (cin >> n >> m) {
    if ((n|m) == 0)
      break;

    string chair(n, '#');

    while (m--) {
      string a;
      cin >> a;
      if (a == "A") {
	for (int i = 0; i < n; ++i) {
	  if (chair[i] == '#') {
	    chair[i] = 'A';
	    break;
	  }
	}
      } else if (a == "B") {
	int sit = -1;
	for (int i = n-1; i > 0 && sit == -1; --i) {
	  if (chair[i] != '#')
	    continue;

	  if (i == 0) {
	    if (chair[i+1] != 'A')
	      sit = i;
	  } else if (i == n-1) {
	    if (chair[i-1] != 'A')
	      sit = i;
	  } else if (chair[i+1] != 'A' && chair[i-1] != 'A') {
	    sit = i;
	  }
	}
	if (sit != -1) {
	  chair[sit] = 'B';
	  continue;
	}

	for (int i = 0; i < n; ++i) {
	  if (chair[i] == '#') {
	    chair[i] = 'B';
	    break;
	  }
	}
      } else if (a  == "C") {
	int sit = -1;
	for (int i = 0; i < n && sit == -1; ++i) {
	  if (chair[i] == '#')
	    continue;

	  if (i == 0) {
	    if (chair[i+1] == '#')
	      sit = i+1;
	  } else if (i == n-1) {
	    if (chair[i-1] == '#')
	      sit = i-1;
	  } else if (chair[i+1] == '#') {
	    sit = i+1;
	  } else if (chair[i-1] == '#') {
	    sit = i-1;
	  }
	}
	if (sit != -1) {
	  chair[sit] = 'C';
	  continue;
	}

	if (n&1)
	  chair[(n+1)/2-1] = 'C';
	else
	  chair[n/2] = 'C';
      } else {
	int maxIndex = -1, dist = -1;
	for (int i = 0; i < n; ++i) {
	  if (chair[i] != '#')
	    continue;

	  int right = 0;
	  if (i == n-1)
	    right = n;
	  for (int j = i+1; j < n; ++j) {
	    if (chair[j] == '#')
	      ++right;
	    else
	      break;
	  }

	  int left = 0;
	  if (i == 0)
	    left = n;
	  for (int j = i-1; j >= 0; --j) {
	    if (chair[j] == '#')
	      ++left;
	    else
	      break;
	  }

	  if (dist < min(right, left)) {
	    maxIndex = i;
	    dist = min(right, left);
	  }
	}
	chair[maxIndex] = 'D';
      }
    }

    cout << chair << endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	a = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int l[2][225816],r[2][225816],u[2][225816],d[2][225816];

int main(void){
	int h,w,n,i,j,sr,sc,x,y;
	string s[2];
	cin >> h >> w >> n;
	cin >> sr >> sc;
	cin >> s[0];
	cin >> s[1];
	for(i=0; i<n; ++i){
		for(j=0; j<2; ++j){
			l[j][i+1] = l[j][i+1];
			r[j][i+1] = r[j][i+1];
			u[j][i+1] = u[j][i+1];
			d[j][i+1] = d[j][i+1];
			if(s[j][i]=='L'){
				++l[j][i+1];
			}
			if(s[j][i]=='R'){
				++r[j][i+1];
			}
			if(s[j][i]=='U'){
				++u[j][i+1];
			}
			if(s[j][i]=='D'){
				++d[j][i+1];
			}
		}
	}
	// U
	x = sr; y = sc;
	for(i=0; i<n; ++i){
		if(s[0][i] == 'U'){
			--x;
		}
		if(x<=0){
			cout << "NO" << endl;
			return 0;
		}
		if(s[1][i] == 'D' && x+1+d[0][n]-d[0][i+1]<=h){
			++x;
		}
	}
	// D
	x = sr; y = sc;
	for(i=0; i<n; ++i){
		if(s[0][i] == 'D'){
			++x;
		}
		if(x>h){
			cout << "NO" << endl;
			return 0;
		}
		if(s[1][i] == 'U' && x-1-u[0][n]+u[0][i+1]>0){
			--x;
		}
	}
	// L
	x = sr; y = sc;
	for(i=0; i<n; ++i){
		if(s[0][i] == 'L'){
			--y;
		}
		if(y<=0){
			cout << "NO" << endl;
			return 0;
		}
		if(s[1][i] == 'R' && y+1+r[0][n]-r[0][i+1]<=w){
			++y;
		}
	}
	// R
	x = sr; y = sc;
	for(i=0; i<n; ++i){
		if(s[0][i] == 'R'){
			++y;
		}
		if(y>w){
			cout << "NO" << endl;
			return 0;
		}
		if(s[1][i] == 'L' && y-1-l[0][n]+l[0][i+1]>0){
			--y;
		}
	}
	cout << "YES" << endl;
	return 0;
}


Measured memory_bytes: 7432
#include <iostream>
using namespace std;
string st;
int w;
int main()
{
	cin>>st;
	for (int i=0;i<st.size();i++)
	{
		if (st[i]=='C') w=1;
		if (st[i]=='F' && w==1) 
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		int maxWeight = scn.nextInt();
		int[][] itemvaw = new int[n+1][2];
		
		for(int i=1;i<=n;i++){
		    itemvaw[i][0] = scn.nextInt();
		    itemvaw[i][1] = scn.nextInt();
		}
		long[][] memo = new long[n+1][maxWeight+1];
		System.out.println(knapsack_memoized(1,itemvaw,maxWeight,memo));
	}
	
	public static long knapsack_memoized(int cii, int[][] itemvaw, int capacityLeft, long[][] memo) {
		if (cii == itemvaw.length)return 0;
		if (capacityLeft == 0)return 0;
		if (memo[cii][capacityLeft] != 0)return memo[cii][capacityLeft];
		long o1 = capacityLeft - itemvaw[cii][0] >= 0 ?
		         itemvaw[cii][1] + knapsack_memoized(cii + 1, itemvaw, capacityLeft - itemvaw[cii][0], memo) : Integer.MIN_VALUE;
		long o2 = knapsack_memoized(cii + 1, itemvaw, capacityLeft, memo);
		return memo[cii][capacityLeft] = Math.max(o1, o2);
	}
}


Measured memory_bytes: 138692
N = int(input())
l = []
for _ in range(N):
    A, B = map(int, input().split())
    l.append((-abs(A+B), -A, -B))
l.sort()
a, b = 0, 0
for i in range(N):
    if i%2:
        b -= l[i][2]
    else:
        a -= l[i][1]

print(a-b)


Measured memory_bytes: 20992
#include <bits/stdc++.h>
#define REP(i,n,N) for(int i=n;i<N;i++)
#define p(S) cout<<(S)<<endl
#define ck(a,b) (0<=(a)&&(a)<b)
using namespace std;

string abcgene(string anss){
	queue<string> q;
	q.push(anss);
	string c[3]={"A","B","C"};
	map<string,bool> m;
	m[anss]=true;
	while(!q.empty()){
		string s=q.front();
		q.pop();
		if(s=="ABC") return "Yes";
		REP(j,0,3){
			string tmps=s;
			int cnt=0;
			REP(i,0,(int) tmps.size()-2){
				if(tmps.substr(i,3)=="ABC"){
					tmps.replace(i,3,c[j]);
					cnt++;
				}
			}
			if(cnt != count(tmps.begin(),tmps.end(),'A'+j)) continue;
			if(!m[tmps]) {
				m[tmps]=true;
				q.push(tmps);
			}
		}
	}
	return "No";
}

int main(){
	string ans;
	cin>>ans;
	p(abcgene(ans));
	return 0;
}

Measured memory_bytes: 9256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<long long> h(n);
  for(int i=0;i<n;i++)cin>>h.at(i);
  vector<int> a(m),b(m);
  vector<bool> ok(n,true);
  for(int i=0;i<m;i++)cin>>a.at(i)>>b.at(i);
  for(int i=0;i<m;i++){
    a.at(i)--;
    b.at(i)--;
    if(h.at(a.at(i))>=h.at(b.at(i)))ok.at(b.at(i))=false;
    if(h.at(b.at(i))>=h.at(a.at(i)))ok.at(a.at(i))=false;
  }
  int ans=0;
  for(int i=0;i<n;i++){
    if(ok.at(i))ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 4844