akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
 
using namespace std;

int main() {
	int m[30][30],vx[4]={1,0,-1,0},vy[4]={0,-1,0,1};
    int i,j,k,w,h,t,cn,v,a,b;
    char c[30][30],g[4]={'E','N','W','S'};
    while(cin >> w >> h && w>0) {
		cn=0;
		for (i=0;i<h;i++) { 
			cin >> c[i];
			for (j=0;j<w;j++) {
				m[i][j]=-9;
				for (k=0;k<4;k++) if (g[k]==c[i][j]) { m[i][j]=k+1; cn++;}
			}
		} 
		
		for (t=1;t<181;t++) {
			for (i=0;i<h;i++) for (j=0;j<w;j++) {
				if (m[i][j]>0 && m[i][j]<5) {
					for (k=0;k<4;k++) {
						v=(m[i][j]+2+k) % 4; a=i+vy[v]; b=j+vx[v];
						if (a<0 || a>=h || b<0 || b>=w) continue; 
						if (c[a][b]!='#' && m[a][b]<1) {
							 m[i][j]=v+1;
							 if (m[a][b]<-((v+2) % 4)) m[a][b]=-((v+2) % 4);
							 break;
						 } 
					}
				}
			}
			
			for (i=0;i<h;i++) for (j=0;j<w;j++) {
				if (m[i][j]>-4 && m[i][j]<1) {
					v=-m[i][j];
					if (c[i][j]=='X')  {cn--; m[i][j]=-9;} else m[i][j]=((v+2) % 4)+1;
					m[i+vy[v]][j+vx[v]]=-9;
				}
			}
		if (cn==0) break;  
		}		
		if (t<181) cout << t << endl; else cout << "NA" << endl;
	}		   
	return 0;
}

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

using namespace std;
using ll = long long;

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

  int n;
  cin >> n;
  vector<int> h(n + 1);
  for (int i = 0; i < n; i++)
    cin >> h[i + 1];
  h[0] = h[1];

  vector<int> dp(n + 1, 1e9);
  dp[0] = 0;

  for (int i = 0; i < n; i++) {
    dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
    if (i + 2 <= n)
      dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
  }

  cout << dp[n] << endl;

  return 0;
}


Measured memory_bytes: 3980
program main
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int64):: n,x,m
    integer(int64):: i
    integer(int64):: c, l_len, l_num, end_len
    integer(int64):: v_loop, v_non_loop
    integer(int64), allocatable:: v(:), v_sum(:), ind(:)


    read*, n,x,m
    allocate(v, source=[(merge(x,0_8,i==1),i=1,m)])
    allocate(v_sum(0:m), source=[0_8,v])
    allocate(ind(0:m), source=[(merge(1_8,0_8,i==x),i=0,m)])

    do i=2,m+1
        v(i)=mod(v(i-1)*v(i-1),m)
        v_sum(i)=v_sum(i-1)+v(i)
        if (i==n) then
            print'(i0)', v_sum(i)
            stop
        end if

        if (ind(v(i)) == 0) then
            ind(v(i))=i
        else
            c = ind(v(i))-1
            l_len = i-ind(v(i))
            l_num = (n-c)/l_len
            end_len = mod((n-c),l_len)

            v_loop = (v_sum(c+l_len)-v_sum(c))*l_num
            v_non_loop = v_sum(c+end_len)
            print'(i0)', v_loop+v_non_loop
            stop
        end if
    end do
end program main

Measured memory_bytes: 6840
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout<<endl
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll mod = 1e9 + 7;
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; }

struct edge
{
	int to;
	int d;
};

vector<int> ans;
vector<vector<edge>> adj;

void dfs(int from, int col, int par)
{
	rep(i, sz(adj[from]))
	{
		int next = adj[from][i].to;
		if (next != par)
		{
			int w = adj[from][i].d;
			if (w % 2 == 0)
			{
				ans[next] = col;
			}
			else
			{
				ans[next] = (col + 1) % 2;
			}
			dfs(next, ans[next], from);
		}
	}
}

int main()
{
	int n; cin >> n;
	adj = vector<vector<edge>>(n);
	ans = vector<int>(n, -1);
	rep(i, n - 1)
	{
		int u, v, w; cin >> u >> v >> w;
		u--; v--;
		edge e = { v, w };
		adj[u].push_back(e);
		e = { u, w };
		adj[v].push_back(e);
	}
	ans[0] = 0;
	dfs(0, ans[0], -1);
	rep(i, n)co(ans[i]);
	return 0;
}


Measured memory_bytes: 8960
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
s = input()
n = len(s)
left = 0
flag1 = True
right = n
flag2 = True
for i in range(n):
    if s[i] == "A" and flag1:
        left = i
        flag1 = False
    if s[n - i - 1] == "Z" and flag2:
        right = n - i - 1
        flag2 = False
# print("right =", right)
# print("left =", left)
print(right - left + 1)   

Measured memory_bytes: 5560
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  long n, k; readV(n, k);

  auto x = n/k, y = 0L;
  if (k%2 == 0) y = x + (n%k >= k/2 ? 1 : 0);

  writeln(x^^3+y^^3);
}


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


void solve(long long L){
    long double a = L/3.0;
    cout << setprecision(10) << a*a*a << endl; 

}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long L;
    scanf("%lld",&L);
    solve(L);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
using ll = long long;



int main() {
	int n;
	ll c = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		if (i % 3 == 0 && i % 5 == 0) continue;
		else if (i % 3 == 0) continue;
		else if (i % 5 == 0) continue;
		c += i;
	}
	cout << c << endl;

	return 0;
}


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

ll dist(ll x, ll y) {
  return (x - 1) + (y - 1);
}

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

  ll ans = dist(1, N);
  for (ll i = 2; i*i <= N; i++) {
    if (N % i == 0) {
      ans = min(ans, dist(i, N / i));
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int H, W;    /* 幅、高さの格納用変数*/
    int i, j;    /* カウンタ用変数*/
    /* 無限ループ */
    while(1){
        /* 高さ、幅の入力 */
        scanf("%d %d", &H, &W);
        /* 終了条件の確認 */
        if(H == 0 && W == 0){
            break;
        }
        /* 長方形の出力 */
        for(i = 1;i <= H;i++){
            for(j = 1;j <= W;j++){
                if(i % 2 == j % 2){
                    /* "#"の出力 */
                    printf("#");
                }
                else{
                    /* "."の出力 */
                    printf(".");
                }
            }
            /* 最終列の出力 */
            printf("\n");
        }
        /* 改行 */
        printf("\n");
    }
    /* 0を返す */
    return 0;
}


Measured memory_bytes: 2040
#include <stdio.h>
#include <stdlib.h>


int main(void) {
    int L, R;
    int Lmod, Rmod, min, tmp;
    
    scanf("%d %d", &L, &R);
    Lmod = L % 2019;
    Rmod = R % 2019;


    min = (Lmod * Rmod) % 2019;
    for (int i=Lmod;i<Lmod+2019 && (L+i-Lmod)<R;i++) {
        for (int j=i+1;j<i+2020 && (L+j-Lmod)<=R;j++) {
            tmp = (i * j) % 2019;
            //printf("%d %d   %d %d   %d ", L+i-Lmod, L+j-Lmod, i, j, tmp);
            if (tmp < min) {
                min = tmp;
                //printf("*\n");
            } else {
                //printf("\n");
            }
        }
        if (min == 0)
            break;
    }
    
    //printf("--------\n");

    printf("%d", min);
    return 0;
}

Measured memory_bytes: 128
n = int(input())
a = list(map(int, input().split()))
x=a[n-1]
for i in range(0,n-2,2):
	x += a[i] - a[i+1]
x /= 2
m = [x]
for t in range(n-1):
	m.append(a[t]-m[t])
m = [str(int(mountain * 2)) for mountain in m]
print(' '.join(m))



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

// comb(n,r)は rを固定すると nについて単調増加
// よって n*= max a[i] が最適. あとは min(r,n*-r)を最大にするr を求めればいい
int main(){
  int N;
  cin >> N;

  vector<int> data(N);
  for(int i=0; i<N; i++){
    cin >> data.at(i);
  }
  sort(data.begin(), data.end());

  int ans_n= data.back();

  auto itr_over = lower_bound(data.begin(), data.end(), ans_n/2);
  auto itr_under= prev(itr_over);

  int ans_r= (min(*itr_over, ans_n- *itr_over) > min(*itr_under, ans_n- *itr_under)) ? *itr_over
                                                                                     : *itr_under;

  cout << ans_n <<" "<< ans_r << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
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() {
    string s;
    cin >> s;
    bool fg1 = true;//yymm
    bool fg2 = true;//mmyy
    if(s[2] == '0' && s[3] == '0') fg1 = false;
    else if(s[2] != '0' && s[2] != '1') fg1 = false;
    else if(s[2] == '1' && s[3] == '3') fg1 = false;
    else if(s[2] == '1' && s[3] == '4') fg1 = false;
    else if(s[2] == '1' && s[3] == '5') fg1 = false;
    else if (s[2] == '1' && s[3] == '6') fg1 = false;
    else if(s[2] == '1' && s[3] == '7') fg1 = false;
    else if(s[2] == '1' && s[3] == '8') fg1 = false;
    else if(s[2] == '1' && s[3] == '9') fg1 = false;
    string t = s;
    s[0] = t[2];
    s[1] = t[3];
    s[2] = t[0];
    s[3] = t[1];
    if(s[2] == '0' && s[3] == '0') fg2 = false;
    else if(s[2] != '0' && s[2] != '1') fg2 = false;
    else if(s[2] == '1' && s[3] == '3') fg2 = false;
    else if(s[2] == '1' && s[3] == '4') fg2 = false;
    else if(s[2] == '1' && s[3] == '5') fg2 = false;
    else if (s[2] == '1' && s[3] == '6') fg2 = false;
    else if(s[2] == '1' && s[3] == '7') fg2 = false;
    else if(s[2] == '1' && s[3] == '8') fg2 = false;
    else if(s[2] == '1' && s[3] == '9') fg2 = false;

    if(fg1 && fg2) {
        cout << "AMBIGUOUS" << endl;
    } else if(fg1) cout << "YYMM" <<endl;
    else if (fg2) cout << "MMYY" << endl;
    else cout << "NA" << endl;


    
}

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

using namespace std;
#define ll long long
#define ld long double

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n, d;
    cin >> n >> d;
    int a[n][d];
    for(int i=0;i<n;i++) {
        for(int j=0;j<d;j++) {
            cin >> a[i][j];
        }
    }
    int cnt = 0;
    for(int i=0;i<n-1;i++) {
        for(int j=i+1;j<n;j++) {
            double sum = 0.0;
            for(int k=0;k<d;k++) {
                sum += pow(abs(a[i][k] - a[j][k]), 2);
            }
            sum = sqrt(sum);
            if(sum == floor(sum)) cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
const int maxn = 3030;
const int mod = 1e9 + 7;
typedef long long ll;
inline void reduce(int & x){
	x += x >> 31 & mod;
}
int n,q,a[maxn];
int dp[maxn][maxn];
int tm[maxn][maxn];
int dp2[maxn][maxn];
int pw[maxn];
int now;
inline void down(int x,int y){
	if(tm[x][y] != now){
		dp[x][y] = (ll) dp[x][y] * pw[now - tm[x][y]] % mod;
		tm[x][y] = now;
	}
}
int main(){
	std::ios::sync_with_stdio(false),std::cin.tie(0);
	std::cin >> n >> q;
	*pw = 1;
	for(int i = 1;i < maxn;++i) pw[i] = pw[i - 1] * 2 % mod;
	for(int i = 1;i <= n;++i) std::cin >> a[i];
	for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j) dp[i][j] = a[i] > a[j];
	for(int i = 1,x,y;i <= q;++i){
		std::cin >> x >> y;
		for(int i = 1;i <= n;++i) {
			down(i,x); down(i,y), down(x,i); down(y,i);
			dp2[i][x] = dp[i][x], dp2[i][y] = dp[i][y];
			dp2[x][i] = dp[x][i], dp2[y][i] = dp[y][i];
		}
		for(int i = 1;i <= n;++i) if(i != x && i != y){
			reduce(dp2[i][x] += dp[i][y] - mod);
			reduce(dp2[x][i] += dp[y][i] - mod);
			reduce(dp2[i][y] += dp[i][x] - mod);
			reduce(dp2[y][i] += dp[x][i] - mod);
		}
		dp2[x][y] = dp2[y][x] = (dp2[x][y] + dp2[y][x]) % mod;
		now = i;
		for(int i = 1;i <= n;++i) {
			dp[i][x] = dp2[i][x], dp[i][y] = dp2[i][y];
			dp[x][i] = dp2[x][i], dp[y][i] = dp2[y][i];
			tm[i][x] = tm[i][y] = tm[x][i] = tm[y][i] = now;
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;++i) for(int j = i + 1;j <= n;++j) {
		down(i,j), reduce(ans += dp[i][j] - mod);
	}
	std::cout << ans << '\n';
}


Measured memory_bytes: 107520
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    edges[a].append(b)
    edges[b].append(a)

next_v = deque([0])
prev = [-1]*n
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if prev[v2] != -1:
            continue
        prev[v2] = v+1
        next_v.append(v2)
print('Yes')
for x in prev[1:]:
    print(x)


Measured memory_bytes: 38024
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define REP(i, b, n) for (Int i = b; i < Int(n); i++)
#define rep(i, n) REP(i, 0, n)
using namespace std;
using Int = long long;
Int inf = 1000000000000000001LL;
using vi = vector<Int>;
using vvi = vector<vi>;
using mapis = unordered_map<Int,string>;
using mapii = unordered_map<Int,Int>;
using pii = pair<Int,Int>;

Int GCD(Int a, Int b){
    if(b==0) return a;
    if(a < b) return GCD(b, a);
    unsigned r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}
Int printX(Int r, Int D, Int X, int count){
    if(count == 10){
        return 0;
    }
    Int nextX = r*X - D;
    cout<< nextX <<endl;
    printX(r,D,nextX,count+1);

}
int main() {
    int r,D,X;
    cin >> r >> D >> X;
    Int ans;
    printX(r,D,X,0);


    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;

int main(){
    int a,b;
    cin >> a >> b;
    string ans = "Odd";
    if((a*b)%2==0)ans = "Even";
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int a, b;
    cin >> a >> b;
    if(b >= a) {
        cout << a << endl;
    } else {
        cout << a - 1 << endl;
    }
    return 0;
}

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

int main() {
    int a,b,c;
    cin >> a >> b >> c;
    bool flag = true;
    if (
        (a == b && a != c) ||
        (b == c && a != c) ||
        (a == c && b != c)
    ) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;
}

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

int N, A, B, C;
vector<int> l(8);
int cost = 9999999;

int natural_num(int i)
{
    if (i < 0)
    {
        return 0;
    }
    else
    {
        return i;
    }
}

void calc(vector<int> v)
{
    int a = 0, b = 0, c = 0;
    int A_hight = 0, B_hight = 0, C_hight = 0;
    for (int i = 0; i < v.size(); i++)
    {
        // aggregate l to a, b, c
        if (v[i] == 0)
        {
            A_hight += l[i];
            a++;
        }
        else if (v[i] == 1)
        {
            B_hight += l[i];
            b++;
        }
        else if (v[i] == 2)
        {
            C_hight += l[i];
            c++;
        }
    }
    // calculate cost
    if (a != 0 & b != 0 & c != 0)
    {
        int da = natural_num(a - 1) * 10;
        int db = natural_num(b - 1) * 10;
        int dc = natural_num(c - 1) * 10;
        da += abs(A - A_hight);
        db += abs(B - B_hight);
        dc += abs(C - C_hight);
        int cost_tmp = da + db + dc;
        // cout << "cost" << cost_tmp << endl;
        if (cost_tmp < cost)
        {
            cost = cost_tmp;
        }
    }
}

void dfs(int depth, vector<int> v)
{
    if (depth == N)
    {
        calc(v);
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        v[depth] = i;
        dfs(depth + 1, v);
    }
}

int main(void)
{
    cin >> N >> A >> B >> C;
    for (int i = 0; i < N; i++)
    {
        cin >> l[i];
    }
    vector<int> v(N, 0);
    dfs(0, v);
    cout << cost << endl;
    return 0;
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> c[i];
  }
  int ans = INT_MIN;
  for (int i = 0; i <= (1 << n) - 1; ++i) {
    int tmp = 0;
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) {
        tmp += v[j] - c[j];
      }
    }
    ans = max(ans, tmp);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
s=input()

for i in range(7):
    op=bin(i)[2:].zfill(3).replace('0','+').replace('1','-')
    v=s[0]+op[0]+s[1]+op[1]+s[2]+op[2]+s[3]+'==7'
    if eval(v):
        print(v.replace('==','='))
        exit(0)


Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>




using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const int INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
const ll mod = 1000 * 1000 * 1000 + 7;

vector<int> comp;
ll col;
vector<vector<int> > g1;

void dfs(int pos) {
    comp[pos] = col;
    for (int i = 0; i < g1[pos].size(); ++i) {
        int to = g1[pos][i];
        if (comp[to] == -1)
            dfs(to);
    }
}

void solve() {
    ll n, m, q;
    cin >> n >> m >> q;
    g1.resize(n);
    vector<pii> ed;
    int a, b, c;
    for (int i = 0; i < q; ++i) {
        cin >> a >> b >> c;
        if (c == 0) {
            g1[a].push_back(b);
            g1[b].push_back(a);
        }
        else {
            ed.push_back(pii(a, b));
        }
    }
    comp.assign(n, -1);
    col = 0;
    for (int i = 0; i < n; ++i) {
        if (comp[i] == -1) {
            dfs(i);
            ++col;
        }
    }
    for (int i = 0; i < ed.size(); ++i) {
        int a = ed[i].first, b = ed[i].second;
        if (comp[a] == comp[b]) {
            cout << "No\n";
            return;
        }
    }
    if (col == 1) {
        if (m == n - 1) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
        return;
    }
    if (col == 2) {
        if ((ed.empty()) && (m == n - 1)) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
        return;
    }
    ll m1 = n - 1;
    if (!ed.empty()) {
        m1 = n;
    }
    ll m2 = col * (col - 1) / 2 + n - col;
    if ((m >= m1) && (m <= m2)) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
        return;

}


//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    solve();


#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}

Measured memory_bytes: 6656
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int powmod(int a, int n, int mod) {
	if (n == 0) return 1;
	if (n % 2 == 0) return powmod((a * a) % mod, n / 2, mod);
	return (a * powmod(a, n - 1, mod)) % mod;
}

int mod = 1000000007;
int n, k;
int a[100000];
int fact[200001];
int finv[200001];

int comb(int n, int k) {
	return fact[n] * finv[k] % mod * finv[n - k] % mod;
}

signed main() {
	int i;
	
	fact[0] = 1;
	finv[0] = 1;
	for (i = 1; i <= 200000; i++) {
		fact[i] = (i * fact[i - 1]) % mod;
		finv[i] = powmod(fact[i], mod - 2, mod);
	}
	
	cin >> n >> k;
	rep(i, n) {
		cin >> a[i];
		a[i] += mod;
	}
	sort(a, a + n);
	
	int smax = 0;
	int smin = 0;
	for (i = k - 1; i < n; i++) {
		smax += comb(i, k - 1) * a[i];
		smin += comb(i, k - 1) * a[n - 1 - i];
		smax %= mod;
		smin %= mod;
	}
	cout << (smax - smin + mod) % mod << endl;
	return 0;
}

Measured memory_bytes: 4096
import java.util.*;

public class Main {
  public static void main(String[] args) {
    try (Scanner sc = new Scanner(System.in)) {
      int N = sc.nextInt();
      int T = sc.nextInt();
      int A = sc.nextInt();
      int[] H = new int[N];
      for ( int j = 0; j < N; j++ ) {
        H[j] = sc.nextInt();
      }
      double h = (T-A)/0.006;
      double diff = Math.abs(H[0] - h);
      int answer = 1;
      if ( N > 1 ) {
        for ( int j = 1; j < N; j++ ) {
          double tempDiff = Math.abs(H[j] - h);
          if ( tempDiff < diff ) {
            diff = tempDiff;
            answer = j + 1;
          }
        }
      }
      System.out.println(answer);
    }
  }
}

Measured memory_bytes: 24020
MOD = 10**9+7
T = [1]*(10**5+1)
D = [1]*(10**5+1)
for i in range(10**5):
  T[i+1] = T[i]*3 % MOD
  D[i+1] = D[i]*2 % MOD
L = input()
n = len(L)
ans = 1
count = 0
for i in range(n):
  if L[i] == "1":
    ans += (T[n-1-i]+1)*D[count]
    ans %= MOD
    count += 1
print(ans)

Measured memory_bytes: 11104
from collections import defaultdict

v, e = map(int, input().split())

links = [set() for _ in range(v)]
bests = [None] * (1 << v)

for _ in range(e):
    s, t, d = map(int, input().split())
    links[s].add((t, d))

bests[0] = {0: 0}

for visited, best in enumerate(bests):
    if best is None:
        continue
    for last, cost in best.items():
        for t, d in links[last]:
            new_visited = visited | (1 << t)
            if visited == new_visited:
                continue
            new_best = bests[new_visited]
            if new_best is None:
                bests[new_visited] = defaultdict(lambda: 15001, [(t, cost + d)])
            else:
                new_best[t] = min(new_best[t], cost + d)

result = bests[-1]
print(-1 if result is None else -1 if result[0] == 15001 else result[0])

Measured memory_bytes: 36628
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF LLONG_MAX
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;

#define ARRAY_MAX 5005

int main(){


    ll n;
    while(cin >> n,n){
        vector<ll> arr(ARRAY_MAX,0);
        REP(i,n){
            cin >> arr[i+1];
        }
        arr[0] = 0;
        REP(i,n){
            arr[i+1] += arr[i];
        }

        ll maxi = -INF;
        for(int i = n;i >= 0;i--){
            for(int j = 0;j < i;j++){
                maxi = max(maxi,arr[i]-arr[j]);
            }
        }
        cout << maxi << endl;
    }

    return 0;
}



Measured memory_bytes: 3144
#include<iostream>
using namespace std;
int main(){
	int a[3000][2];
	int i,j,tmp;
	int cnt=0;
	for(i=0; i<3000; i++){
		for(j=0; j<2; j++){
			cin>>a[i][j];
		}
		if(a[i][0]==0 && a[i][1]==0){
			break;
		}
		cnt+=1;
		if(a[i][0]>a[i][1]){
				tmp=a[i][0];
				a[i][0]=a[i][1];
				a[i][1]=tmp;
		}
	}
	for(i=0; i<cnt; i++){
			cout<<a[i][0]<<" "<<a[i][1]<<"\n";
	}
	return 0;
}


Measured memory_bytes: 3084
n=int(input())
c=list(range(1,1+2*n))
for _ in[0]*int(input()):
    k=int(input())
    if k:c=c[k:]+c[:k]
    else:
        for a,b in zip(c[:n],c[n:]):
            c+=[a,b]
        c=c[2*n:]
print(*c,sep='\n')


Measured memory_bytes: 5632
n = int(input())
s=input()
isi=[]
for i in s:
    isi.append(i)

R_kosuu=isi.count("R")
irekaekosuu=0
for i in range(R_kosuu):
    if isi[i]=="W":
        irekaekosuu+=1


print(irekaekosuu)

Measured memory_bytes: 87540
#include <iostream>
#include <vector>

int main() {
  unsigned H, W;
  std::cin >> H >> W;
  std::vector<unsigned> cnt('z' - 'a' + 1, 0);
  for (unsigned i = 0; i < H * W; ++i) {
    char c;
    std::cin >> c;
    ++cnt[c - 'a'];
  }
  for (auto &i : cnt) { i %= 4; }
  std::vector<unsigned> cnt2(4, 0);
  for (int i = 0; i <= 'z' - 'a'; ++i) {
    ++cnt2[cnt[i]];
  }
  bool ok;
  if (H % 2 == 0 && W % 2 == 0) {
    ok = cnt2[1] == 0 && cnt2[2] == 0 && cnt2[3] == 0;
  } else if (H % 2 == 1 && W % 2 == 0) {
    ok = cnt2[1] == 0 && cnt2[2] <= W / 2 && cnt2[3] == 0;
  } else if (H % 2 == 0 && W % 2 == 1) {
    ok = cnt2[1] == 0 && cnt2[2] <= H / 2 && cnt2[3] == 0;
  } else {
    ok = (cnt2[1] == 1 && cnt2[2] <= H / 2 + W / 2 && cnt2[3] == 0) ||
        (cnt2[1] == 0 && cnt2[2] <= H / 2 + W / 2 && cnt2[3] == 1);
  }
  if (ok) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
  return 0;
}

Measured memory_bytes: 888
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime> 
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>
 
using namespace std;
 
const int INF = 1e9 + 239;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int x, n;
	cin >> x >> n;
	set<int> s;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		s.insert(p);
	}
	int ans = INF;
	int who = -1;
	{
		int c = x;
		while (s.count(c)) {
			c--;
		}
		if (abs(c - x) < ans) {
			ans = abs(c - x);
			who = c;
		}
	}
	{
		int c = x;
		while (s.count(c)) {
			c++;
		}
		if (abs(c - x) < ans) {
			ans = abs(c - x);
			who = c;
		}
	}
	cout << who << endl;
}

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

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

  long long n, k;
  cin >> n >> k;
  if(k > (n-1)*(n-2)/2ll){
    cout << -1 << endl;
    return 0;
  }
  vector<pair<int, int> > ans;
  for(int i=1;i<n;i++){ //uni
    ans.push_back(make_pair(0, i));
  }
  k-=(n-1)*(n-2)/2ll;
  int now=1;
  while(k != 0){
    for(int i=now+1;i<n;i++){
      if(k==0) break;
      ans.push_back(make_pair(now, i));
      k++;
    }
    now++;
  }
  cout << ans.size() << endl;
  for(size_t i=0;i<ans.size();i++){
    cout << ans[i].first+1 << " " << ans[i].second+1 << endl;
  }
  return 0;
}


Measured memory_bytes: 384
#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

const int mod = 1'000'000'007;

void add(int &a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}

const int N = 2'009;

int p[N];

int find(int x) {
  if (p[x] != x) {
    p[x] = find(p[x]);
  }
  return p[x];
}

int x[N];
int y[N];
int v[N];
int pw[N];

int main() {
  int n, m;
  long long w;
  scanf("%d %d %lld", &n, &m, &w);
  for (int i = 0; i < m; ++i) {
    scanf("%d %d %d", x + i, y + i, v + i);
    --x[i];
    --y[i];
  }
  for (int i = 0; i < m; ++i) {
    for (int j = i + 1; j < m; ++j) {
      if (v[j] < v[i]) {
        swap(x[i], x[j]);
        swap(y[i], y[j]);
        swap(v[i], v[j]);
      }
    }
  }
  int cnt1 = 0, cnt2 = 0;
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      p[j] = j;
    }
    p[x[i]] = y[i];
    long long curw = v[i];
    for (int j = 0; j < m; ++j) {
      int px = find(x[j]);
      int py = find(y[j]);
      if (px == py) {
        continue;
      }
      p[px] = py;
      curw += v[j];
    }
    if (curw < w) {
      ++cnt1;
    } else
    if (curw == w) {
      ++cnt2;
    }
  }
  if (cnt2 == 0) {
    puts("0");
    return 0;
  }
  pw[0] = 1;
  for (int i = 1; i < N; ++i) {
    pw[i] = 2 * pw[i - 1] % mod;
  }
  int bad = 0;
  if (cnt1 != 0) {
    add(bad, pw[m]);
    add(bad, mod - pw[m - cnt1 + 1]);
  }
  add(bad, pw[m - cnt1 - cnt2 + 1]);
  printf("%d\n", (pw[m] - bad + mod) % mod);
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
int s(int n){
    int t=n,a=0;
    while(t){
        a+=t%10;
        t/=10;
    }
    return a;
}
int main(){
    int n;
    cin>>n;
    if(n%s(n)==0) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}





Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N, M;
vector<int> E[601];
double dp[601], dp2[601];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b; cin >> a >> b;
		a--; b--;
		E[a].push_back(b);
	}

	rrep(cu, N - 2, 0) {
		fore(to, E[cu]) dp[cu] += dp[to];
		dp[cu] /= (int)E[cu].size();
		dp[cu] += 1;
	}

	double ans = dp[0];

	rep(stop, 0, N - 1) {
		rep(i, 0, N) dp2[i] = dp[i];
		rep(i, 0, stop + 1) dp2[i] = 0;

		int sz = E[stop].size();
		if (2 <= sz) {
			vector<double> v;
			fore(to, E[stop]) v.push_back(dp2[to]);
			sort(all(v));

			rep(i, 0, sz - 1) dp2[stop] += v[i];
			dp2[stop] /= sz - 1;
			dp2[stop] += 1;
		}
		else continue;

		rrep(cu, stop - 1, 0) {
			fore(to, E[cu]) dp2[cu] += dp2[to];
			dp2[cu] /= E[cu].size();
			dp2[cu] += 1;
		}
		chmin(ans, dp2[0]);
	}

	printf("%.10f\n", ans);
}







Measured memory_bytes: 1408
L = list(input())
for bit in range(1 << 3) :
    P = [""]*4
    for k in range(3) :
        if bit & (1 << k) :
            P[k] = "+"
        else :
            P[k] = "-"
    calc = ""
    for i in range(4) :
        calc += L[i] + P[i]
    if eval(calc) == 7 :
        ans = calc + "=7"
        break
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
  int high[10];
  REP(i,10){
    cin >> high[i];
  }
  sort(high,high+10);
  cout << high[9] << endl;
  cout << high[8] << endl;
  cout << high[7] << endl;
}

Measured memory_bytes: 1176
#include<iostream>
using namespace std;
int main(){
	int n,s=0,e=10007;
	int i,j,k;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>k;
		s+=k;
		if(k%10!=0 && k<e)e=k;
	}
	if(s%10==0)s-=e;
	if(s<0)s=0;
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector<vector<int>> fG;
vector<vector<int>> bG;
vector<int> label;
int nextL = 1;
void dfs(int node, int l) {
	if (label[node] != 0)
		return;
	int i = 0;
	label[node] = l;
	while (fG[node][i] != -1) {
		dfs(fG[node][i], l);
		i++;
	}
	if (nextL == l)
		nextL++;
	return;
}
int main() {
	int n, m, k, a, b, c, d;
	scanf("%d%d%d", &n, &m, &k);
	fG.resize(n);
	bG.resize(n);
	label.resize(n, 0);
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		a--;
		b--;
		fG[a].push_back(b);
		fG[b].push_back(a);
	}
	for (int i = 0; i < n; i++) {
		fG[i].push_back(-1);
	}
	for (int i = 0; i < k; i++) {
		scanf("%d%d", &c, &d);
		c--;
		d--;
		bG[c].push_back(d);
		bG[d].push_back(c);
	}
	for (int i = 0; i < n; i++) {
		bG[i].push_back(-1);
	}
	// dfs, label,各頂点について連結の名前を付ける
	for (int i = 0; i < n; i++) {
		dfs(i, nextL);
	}
	vector<int> labelCnt(n, 0);
	for (int i = 0; i < n; i++) {
		// printf("%d ", label[i]);
		labelCnt[label[i] - 1]++;
	}
	// printf("\n");
	for (int i = 0; i < n; i++) {
		int ans, fCnt = 0, fbCnt = 0, bCnt = 0;
		while (fG[i][fCnt] != -1)
			fCnt++;
		while (bG[i][bCnt] != -1) {
			if (label[bG[i][bCnt]] == label[i])
				fbCnt++;
			bCnt++;
		}
		// printf("l:%d f:%d b:%d ", labelCnt[label[i] - 1], fCnt, fbCnt);
		ans = labelCnt[label[i] - 1] - fCnt - fbCnt - 1;
		printf("%d ", ans);
	}
	return 0;
}

Measured memory_bytes: 14720
// AtCoder ABC139: B - Power Socket
// 2019.9.2 bal4u

#include <stdio.h>

int main()
{
	int A, B, a, b, ans;
	
	scanf("%d%d", &A, &B);
	if (B <= 1) ans = 0;
	else if (B <= A) ans = 1;
	else ans = (B-A-1)/(A-1)+2;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
n, x, y = map(int, input().split())

dist = [0] * (n + 1)
dist[0] = -1

for i in range(1, n + 1):
    if y == i:
        dist[i] = dist[x] + 1
    else:
        dist[i] = dist[i - 1] + 1

for i in range(y - 1, x - 1, -1):
    dist[i] = min(dist[i], dist[y] + (y - i))

cnt = [0] * (n + 1)

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if x < i < y:
            d = min(j - i, (i - x) + 1 + abs(y - j))
            cnt[d] += 1
        else:
            cnt[dist[j] - dist[i]] += 1

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


Measured memory_bytes: 3444
#include<bits/stdc++.h>
using namespace std;
int main()
{
  char c;
  cin>>c;
  if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o')
  {
    cout<<"vowel"<<endl;
  }else
  {
    cout<<"consonant"<<endl;
  }
}

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

int main()
{
    int N, M;
    cin >> N >> M;

    vector<int> A(N);
    vector<int> B(N);
    vector<int> C(M);
    vector<int> D(M);

    for (int i = 0; i < N; i++)
    {
        cin >> A.at(i) >> B.at(i);
    }

    for (int i = 0; i < M; i++)
    {
        cin >> C.at(i) >> D.at(i);
    }

    int c;
    int d;
    int min;
    int l;

    vector<int> P(N);
    for (int i = 0; i < N; i++)
    {
        min = 2147483647;
        for (int j = 0; j < M; j++)
        {
            l = abs(A.at(i) - C.at(j)) + abs(B.at(i) - D.at(j));
            if (l < min)
            {
                min = l;
                P.at(i) = j + 1;
            }
        }
    }

    for (int i = 0; i < N; i++)
    {
        cout << P.at(i) << endl;
    }

    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 4e3 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int read()
{
	int x;
	scanf("%d", &x);
	return x;
}

int n, m, s[maxn], t[maxn], dp[maxn][maxn];

int main()
{
	n = read(), m = read();
	for(int i = 1; i <= n; i ++)
	{
		s[i] = read();
	}
	for(int i = 1; i <= m; i ++)
	{
		t[i] = read();
	}
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j ++)
		{
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % mod;
			if(s[i] == t[j])
			{
				dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] + 1) % mod;
			}
			if(dp[i][j] < 0)
			{
				dp[i][j] = dp[i][j] + mod;
			}
		}
	}
	cout << (dp[n][m] + 1) % mod << endl;
	return 0;
}
	

Measured memory_bytes: 32512
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
using Pair = pair<ll,pair<int,int>>;
#define pq priority_queue<Pair, vector<Pair>, greater<Pair>> 
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
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; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



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

  ll a,b;
  cin>>a>>b;


  cout << lcm(a,b) << endl;
}

Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <queue>

using namespace std;

int markpower[128];
int numpower[128];

int main()
{
    for (char c = '0'; c <= '9'; c++) {
        numpower[c] = c - '0';
    }
    numpower['T'] = 10;
    numpower['J'] = 11;
    numpower['Q'] = 12;
    numpower['K'] = 13;
    numpower['A'] = 14;
    char trump;
    while (cin >> trump, trump != '#') {
        string input[4][13];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 13; j++) {
                cin >> input[i][j];
            }
        }
        int win = 3;
        int ns = 0, ew = 0;
        for (int j = 0; j < 13; j++) {
            priority_queue<pair<int, int>> que;
            for (int i = 0; i < 4; i++) {
                fill_n((int *)markpower, 128, 0);
                markpower[input[win][j][1]] = 100;
                markpower[trump] = 200;
                int power = markpower[input[i][j][1]]+numpower[input[i][j][0]];
                que.push({power, i});
            }
            win = que.top().second;
            if (win % 2 == 0) ns++;
            else ew++;
        }
        if (ns > ew)
            cout << "NS " << ns % 6 << endl;
        else
            cout << "EW " << ew % 6 << endl;
    }
    return 0;
}

Measured memory_bytes: 3040
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    S = readline().strip()
    T = readline().strip()
    N = len(S)
    M = len(T)

    SS = S + S

    A = [False] * 26
    for c in S:
        A[ord(c) - 97] = True

    for c in T:
        if not A[ord(c) - 97]:
            print(-1)
            return

    B = [[-1] * N for _ in range(26)]
    for c in set(T):
        code = ord(c) - 97
        row = B[code]

        left = right = 0
        while True:
            right = SS.find(c, left + 1)
            if right < N:
                row[left:right] = [right] * (right - left)
                left = right
            else:
                row[left:N] = [right] * (N - left)
                break

    ans = i = S.find(T[0])
    for c in T[1:]:
        j = B[ord(c) - 97][i]
        ans += j - i
        if j < N:
            i = j
        else:
            i = j - N

    print(ans + 1)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 108576
n = int(input())
a = list(map(int,input().split()))
ans = [0]*(n)
for i in range(n):
  ans[0] += a[i]*(-1)**(i)
for i in range(1,n):
  ans[i] = (a[i-1]-(ans[i-1]//2))*2
print(*ans)

Measured memory_bytes: 14028
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
#include <numeric>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };




signed main() {
	ll n, sum = 0;
	vector<ll>list;
	
	cin >> n;

	for (int i = 0; i <= 44723; i++) {
		sum += i;
		list.push_back(sum);
	}

	ll ans;

	for (int i = 0; i < list.size(); i++) {
		if (list[i] == n) {
			ans = i;
			break;
		}
		else if (list[i] > n) {
			ans = i;
			break;
		}

		if (i >= 5 && i <= 44700)continue;
		//cout << "i->" << i << " " << list[i] << endl;
	}


	cout << ans << endl;



	return 0;
}

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

int main(){
  int len,n,num1,num2,max,suji,temp,cnt2=1,result;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> suji;
    temp = suji;
    len = cnt2;
      int cnt = 0;
      // cout << "len" << len << endl;
     while(suji >= 10){
       max = -1;
       cnt2 = 1;
       while(temp > 0){
	 cnt2++;
	 temp/=10;
       }
       len = cnt2;
       int waru_num = 1;
      for(int j = 1; j < len; j++){
	waru_num *= 10;
	//cout << "waru_num" << waru_num << endl;
	num1 = suji / waru_num;
	//cout << "num1 " << num1 << endl;
	num2 = suji % waru_num;
	//cout << "num2 " << num2 << endl;
	result = num1 * num2;
	if(max < result){
	  max = result;
	  //cout << "max" << max << endl;
	}
      }
      suji = max;
      temp = suji;
      cnt++;
    }
     if(cnt > 10000000)cout << "-1" << endl;
     else cout << cnt << endl;
       
     }
    
  return 0;
}

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

int main(int, char**)
{
	long long X, Y;
	cin >> X >> Y;
	if ((2 * Y - X) % 3 != 0 || (2 * X - Y) % 3 != 0)
	{
		cout << 0 << endl;
		return 0;
	}
	long long alpha = (2 * Y - X) / 3, beta = (2 * X - Y) / 3;
	if (alpha < 0 || beta < 0)
	{
		cout << 0 << endl;
		return 0;
	}
	const long long M = 1000000000 + 7;
	long long n = alpha + beta;
	long long k = min(alpha, beta);
	vector<long long> fact(n + 1, 1), inv1(n + 1, 1), inv2(n + 1, 1);
	for (long long i = 2; i <= n; ++i)
	{
		fact[i] = fact[i - 1] * i % M;
		inv2[i] = M - inv2[M % i] * (M / i) % M;
		inv1[i] = inv1[i - 1] * inv2[i] % M;
	}
	cout << fact[n] * (inv1[k] * inv1[n - k] % M) % M << endl;
	return 0;
}


Measured memory_bytes: 15872
#include <iostream>
#include <array>
#include <algorithm>

auto read = [](auto &x){std::cin >>x;};
auto readSeq = [](auto *begin, auto *end){
                  std::for_each(begin, end, read);
                };
auto printSeq = [](auto *begin, auto *end){
                   std::for_each(begin, end-1, [](auto x){std::cout<<x<<" ";});
                   std::cout << *(end-1) <<  std::endl;
                 };

int bubbleSort(int *begin, int *end);

int main ()
{
  int n;
  const int max_n = 100;
  std::array<int, max_n> arr;

  read(n);
  readSeq(arr.begin(), arr.begin()+n);

  auto cnt = bubbleSort(arr.begin(), arr.begin()+n);


  printSeq(arr.begin(), arr.begin()+n);
  std::cout << cnt << std::endl;

  return 0;
}

int bubbleSort(int *begin, int *end)
{
  auto swap = [](auto &a, auto &b){
                auto tmp = a;
                a = b;
                b =tmp;
              };

  auto n = std::distance(begin, end);
  auto itr = begin;

  auto cnt = 0;

  for (int i=0; i<n; i++)
    {
      for (int j=n-1; j>i; j--)
        {
          if (itr[j-1] > itr[j])
            {
              swap(itr[j-1], itr[j]);
              cnt++;
            }
        }
    }

  return cnt;
}



Measured memory_bytes: 3104