akhauriyash/Code-Regression huggingface dataset:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,k=map(int,readline().split())

    if k>(n-1)*(n-2)//2:
        print(-1)
    else:
        m=n-1
        G=[]
        for i in range(2,n+1):
            G.append((1,i))
        cnt=(n-1)*(n-2)//2

        i=2
        j=3
        while k!=cnt:
            G.append((i,j))
            if j<n:
                j+=1
            else:
                i+=1
                j=i+1
            m+=1
            cnt-=1

        print(m)
        for i in range(m):
            print(*G[i])
            
if __name__=="__main__":
    main()

Measured memory_bytes: 3992
Q, H, S, D = map(int, input().split())
N = int(input())

compare2 = [Q*8, H*4, S*2, D]
Q2, H2, S2, D2 = compare2

compare3 = [Q*8, H*4, S*2]
Q3, H3, S3 = compare3

ans = 0
if D2 == min(compare2):
    ans = (N // 2) * D
    N %= 2

if Q3 == min(compare3):
    ans += N * Q * 4
elif H3 == min(compare3):
    ans += N * H * 2
elif S3 == min(compare3):
    ans += N * S

print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class T>
istream& operator >> (istream& is, vector<T>& v)
{
	for (auto &i : v) is >> i;
	return is;
}
template<class T>
ostream& operator<<(ostream& os, vector<T>& v)
{
	const string delimiter = "\n";
	REP(i, v.size())
	{
		os << v[i];
		if (i != v.size() - 1) os << delimiter;
	}
	return os;
}
/*--------------------template--------------------*/

const int INF = 1e9;

int n, m;
vi a, b;
int dp[2][2][51][51][51][51];
bool memo[2][2][51][51][51][51];

int solve(int turn, int pass, int a_stack_btm, int a_deck_top, int b_stack_btm, int b_deck_top)
{
	if (memo[turn][pass][a_stack_btm][a_deck_top][b_stack_btm][b_deck_top]) return dp[turn][pass][a_stack_btm][a_deck_top][b_stack_btm][b_deck_top];
	int res;
	if (turn == 0)
	{
		res = -INF;
		// put on stack
		if (a_deck_top < n)
		{
			chmax(res, solve(1, 0, a_stack_btm, a_deck_top + 1, b_stack_btm, b_deck_top));
		}
		// pass
		if (pass)
		{
			chmax(res, 0);
		}
		else
		{
			int score_a = 0, score_b = 0;
			int ta = a_stack_btm, tb = b_stack_btm;
			int empty = (a_deck_top == a_stack_btm && b_deck_top == b_stack_btm);
			if (a_deck_top - a_stack_btm < b_deck_top - b_stack_btm)
			{
				if (b[tb] != -1) score_b += b[tb];
				tb++;
			}
			REP(i, a_deck_top - a_stack_btm)
			{
				if (a[ta + i] == -1) score_b = 0;
				else score_a += a[ta + i];
				if (b[tb + i] == -1) score_a = 0;
				else score_b += b[tb + i];
			}
			chmax(res, solve(1, empty, a_deck_top, a_deck_top, b_deck_top, b_deck_top) + score_a - score_b);
		}
	}
	else
	{
		res = INF;
		// put on stack
		if (b_deck_top < m)
		{
			chmin(res, solve(0, 0, a_stack_btm, a_deck_top, b_stack_btm, b_deck_top + 1));
		}
		// pass
		if (pass)
		{
			chmin(res, 0);
		}
		else
		{
			int score_a = 0, score_b = 0;
			int ta = a_stack_btm, tb = b_stack_btm;
			int empty = (a_deck_top == a_stack_btm && b_deck_top == b_stack_btm);
			if (a_deck_top - a_stack_btm > b_deck_top - b_stack_btm)
			{
				if (a[ta] != -1) score_a += a[ta];
				ta++;
			}
			REP(i, b_deck_top - b_stack_btm)
			{
				if (b[tb + i] == -1) score_a = 0;
				else score_b += b[tb + i];
				if (a[ta + i] == -1) score_b = 0;
				else score_a += a[ta + i];
			}
			chmin(res, solve(0, empty, a_deck_top, a_deck_top, b_deck_top, b_deck_top) + score_a - score_b);
		}
	}
	memo[turn][pass][a_stack_btm][a_deck_top][b_stack_btm][b_deck_top] = true;
	return dp[turn][pass][a_stack_btm][a_deck_top][b_stack_btm][b_deck_top] = res;
}

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	MS(memo, false);
	cin >> n >> m;
	a.resize(n);
	b.resize(m);
	cin >> a >> b;
	cout << solve(0, 0, 0, 0, 0, 0) << endl;
	return 0;
}

Measured memory_bytes: 56068
def main():
    import sys
    input = sys.stdin.readline

    H, W, M = map(int, input().split())

    H_list = [[0, i] for i in range(H + 1)] 
    W_list = [[0, i] for i in range(W + 1)] 


    S = set()
    S_add = S.add
    INF = 10 ** 6

    for _ in range(M):
        a, b = map(int, input().split())
        tmp = INF * a + b
        S_add(tmp)
        H_list[a][0] += 1
        W_list[b][0] += 1

    ans = 0
    H_list.sort(reverse=True)
    W_list.sort(reverse=True)

    tmp_H = H_list[0][0]
    tmp_W = W_list[0][0]
    tmp_ans = tmp_H + tmp_W

    for h in range(H):
        if H_list[h][0] + 1 < tmp_H:
            continue
        h_ = H_list[h][1]
        H_ = H_list[h][0]
        for w in range(W):
            if W_list[w][0] + H_ + 1 < tmp_ans:
                break
            w_ = W_list[w][1]
            tmp = H_ + W_list[w][0]
            if INF * h_ + w_ in S:
                tmp -= 1
            ans = max(ans, tmp)
            if ans == tmp_ans:
                print (ans)
                return

    print (ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 172140
#import numpy as np
#import functools
#import operator
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as comb_with
#from itertools import permutations as perm


N = int(input())
#H1,M1,H2,M2,K= map(int,input().split())
#A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())
#prod = functools.partial(functools.reduce, operator.mul)
#c=np.array(A)
#p=np.prod(A)
if N==1:
    print(0)
    exit()
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
z=0
for v in factorization(N):
    fla=True

    i=1
    while fla==True:
#        print(v)
        if v[1]-i>=0:
            v[1] -= i
            z+=1
            i+=1
        else:
            fla=False
print(z)

Measured memory_bytes: 9480
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		long[] A = new long[N];
		for (int i = 0; i < N; i++) {
			A[i] = in.nextLong() * 2;
		}
		long offset = 0;
		for (int i = 0; i < N; ++i) {
			offset = A[i] - offset;
		}
		long x = offset / 2;
		long cur = x;
		for (int i = 0; i < N; ++i) {
			System.out.println(cur);
			cur = A[i] - cur;
		}
		in.close();
	}
}

Measured memory_bytes: 70708
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>
#include <functional>
#include <iomanip>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

template< typename T >
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;
int negative[2510] = {};

template< typename T >
vector< T > bellman_ford(Edges< T > &edges, int V, int s) {
  const auto INF = numeric_limits< T >::max();
  vector< T > dist(V, INF);
  dist[s] = 0;
  for(int i = 0; i < V - 1; i++) {
    for(auto &e : edges) {
      if(dist[e.src] == INF) continue;
      dist[e.to] = min(dist[e.to], dist[e.src] + e.cost);
    }
  }
  bool flag = 0;
  for(int i = 0; i < 2*V; i++){
    for(auto &e : edges) {
        if(dist[e.src] == INF) continue;
        if(dist[e.src] + e.cost < dist[e.to])
        {
            dist[e.to] = dist[e.src] + e.cost;
            negative[e.to] = 1;
        }
    }
  }
  return dist;
}

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    LL N,M,P; cin >>N>>M>>P;
    Edges<LL> es;
    REP(i,2510) negative[i] = 0;
    REP(i,M)
    {
        LL a,b,c; cin>>a>>b>>c;
        a--; b--;
        //c *= -1;
        c -= P;
        c *= -1;
        es.emplace_back(a,b,c);
    }
    auto dists = bellman_ford(es,N,0);
    if(negative[N-1] == 1)
    {
        cout << -1 << endl;
        return 0;
    }
    else
    {
        cout << max(dists[N-1] * -1,0LL) << endl;
    }

}


Measured memory_bytes: 512
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kein Yukiyoshi
 */

#include "bits/stdc++.h"
#define int long long
#define rep(i, n)           for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b)        for (int i = (int)(a); i < (int)(b); i++)
#define FOR(i, a)           for (auto &i : a)
#define ALL(obj)            begin(obj), end(obj)
#define MAX(x)              *max_element(ALL(x))
#define MIN(x)              *min_element(ALL(x))
#define SUM(x)              accumulate(ALL(x), 0LL)
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))

using namespace std;
const int MOD    = (int)(1e9 + 7);
const int INF    = (int)(1e13 + 7);
const double EPS = 1e-14;
const double PI  = acos(-1);

int CEIL(int a, int b) { return (a >= 0 ? (a + (b - 1)) / b : (a - (b - 1)) / b); } //ceil() for int
int mod(int a, int b) { return a >= 0 ? a % b : a - (b * CEIL(a, b)); }             //always return positive num
int bpm(int a, int b) {                                                             //return x^y in order(log(y))
  int res = 1;
  for (a %= MOD; b; a = a * a % MOD, b >>= 1)
    if (b & 1) res = res * a % MOD;
  return res;
}

int nCk(int a, int b) {
  int ret = 1;
  vector<int> temp{};
  rep(i, b) temp.emplace_back(i + 1);
  rep(j, b) {
    ret *= a - j;
    rep(k, temp.size()) {
      if (ret % temp[k] == 0 and temp[k] > 1) {
        ret /= temp[k];
        temp[k] = 1;
      }
    }
  }
  return ret;
}

class DMaximumAverageSets {
public:
  static void solve(istream &cin, ostream &cout) {
    int N, A, B;
    cin >> N >> A >> B;
    vector<int> v(N);
    rep(i, N) cin >> v[i];
    sort(ALL(v));
    int ans = 0;
    rep(i, A) ans += v[N - 1 - i];
    cout << setprecision(20) << (double)ans / (double)A << fixed << endl;
    int ans2 = 0;
    map<int, int> num;
    FOR(i, v)
    num[i]++;
    if (num[v[N - 1]] >= B) {
      REP(k, A, B + 1) {
        ans2 += nCk(num[v[N - 1]], k);
      }
    } else if (num[v[N - 1]] < B and num[v[N - 1]] >= A) {
      REP(k, A, num[v[N - 1]] + 1) {
        ans2 += nCk(num[v[N - 1]], k);
      }
    } else {
      int temp = 0;
      rep(i, N) {
        if (v[i] > v[N - A]) temp++;
      }
      ans2 = nCk(num[v[N - A]], A - temp);
    }
    cout << max(ans2, 1LL) << endl;
  }
};


signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(15);
  DMaximumAverageSets solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}


Measured memory_bytes: 3828
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dd;
const int INF = 1e9 + 5;
void solve()
{
		int n;
		cin >> n;
		vector <int> h(n, 0);
		
		for(int &x : h)
			cin >> x;
			
		vector <int> dp(n, INF);
		dp[0] = 0;
		for(int i = 0; i<n; i++)
		{
			for(int j = i+1; j<i+3; j++)
			{
				if(j < n)
				{
					dp[j] = min(dp[j], dp[i] + abs(h[i]-h[j]));
				}
			}
		}
		
		cout << dp[n-1];
		
}

int main()
{
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		ll t = 1;
	//	cin >> t
		while(t--)
		{
			solve();
		}
	return 0;
}


Measured memory_bytes: 1152
import std;

char get(char a, char b) {
    foreach (c; "RGB") {
        if (c != a && c != b) return c;
    }
    assert(false);
}

long calc(string s) {
    int n = cast(int)s.length;

    auto r = new int[n];
    auto g = new int[n];
    auto b = new int[n];
    if (s[0] == 'R') r[0] = 1;
    if (s[0] == 'G') g[0] = 1;
    if (s[0] == 'B') b[0] = 1;
    foreach (i; 1..n) {
        r[i] = r[i-1] + (s[i] == 'R');
        g[i] = g[i-1] + (s[i] == 'G');
        b[i] = b[i-1] + (s[i] == 'B');
    }

    long ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            if (s[i] == s[j]) continue;

            char c = get(s[i], s[j]);
            // writeln("i ", i, " j ", j, " ", c);
            int step = j - i;
            if (c == 'R') {
                ans += r[$-1] - r[j-1];
                if (j + step < n && s[j + step] == 'R') ans--;
            }
            if (c == 'G') {
                ans += g[$-1] - g[j-1];
                if (j + step < n && s[j + step] == 'G') ans--;
            }
            if (c == 'B') {
                ans += b[$-1] - b[j-1];
                if (j + step < n && s[j + step] == 'B') ans--;
            }
        }
    }
    return ans;

}

void main() {
    readint;
    string s = read!string;
    writeln(calc(s));
}

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;


Measured memory_bytes: 3684
#include<iostream>
using namespace std;
int main(){
 int W, X, x, y, r, w, h, a, b;
 cin >> W >> X >> x >> y >> r;
 w = x+r;
 h = y+r;
 a = x-r;
 b = y-r;
 if ( w <= W && a >= 0 && h <= X && b >= 0 ){
 cout << "Yes" << endl;
}else{
 cout << "No" << endl;
}
return 0;
}

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

#define int long long

int h[1000002];
int ans[1000002];

signed main(){

	int n,m;
	cin>>n>>m;
	int a;
	for(int i=0;i<=n;i++){
		h[i]=ans[i]=0;
	}
	for(int i=0;i<m;i++){
		cin>>a;
		h[a] = 1;
	}

	ans[0]=1;
	for(int i=0;i<n;i++){
		if(h[i+1]==0)ans[i+1]+=ans[i];
		if(h[i+2]==0)ans[i+2]+=ans[i];
		ans[i+1]%=1000000007;
		ans[i+2]%=1000000007;
	}
	cout<<ans[n]<<endl;
	return(0);
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    int H,W;
    cin >> H >> W;
    int cnt = 0;
    REP(i,H){
        string str; cin >> str;
        for(const auto &it: str) if (it == '#') cnt ++;
    }
    if (cnt == (H+W-1)) cout << "Possible" << endl;
    else cout << "Impossible" << endl;

}

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


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll longinf = 5LL << 60;
const ll mod = 1e9 + 7;

struct Edge {
	int to;
};
using Graph = vector<vector<Edge>>;
using P = pair<long, long>;
/* Lowlink: グラフの関節点・橋を列挙する構造体
	作成: O(E+V)
	関節点の集合: vector<int> aps
	橋の集合: vector<P> bridges
*/
struct LowLink {
	const Graph &G;
	vector<int> used, ord, low;
	vector<int> aps;  // articulation points
	vector<P> bridges;
	LowLink(const Graph &G_) : G(G_) {
		used.assign(G.size(), 0);
		ord.assign(G.size(), 0);
		low.assign(G.size(), 0);
		int k = 0;
		for(int i = 0; i < (int)G.size(); i++) {
			if(!used[i]) k = dfs(i, k, -1);
		}
		sort(aps.begin(), aps.end());		   // 必要ならソートする
		sort(bridges.begin(), bridges.end());  // 必要ならソートする
	}
	int dfs(int id, int k, int par) {  // id:探索中の頂点, k:dfsで何番目に探索するか, par:idの親
		used[id] = true;
		ord[id] = k++;
		low[id] = ord[id];
		bool is_aps = false;
		int count = 0;	// 子の数
		for(auto &e : G[id]) {
			if(!used[e.to]) {
				count++;
				k = dfs(e.to, k, id);
				low[id] = min(low[id], low[e.to]);
				if(par != -1 && ord[id] <= low[e.to]) is_aps = true;
				if(ord[id] < low[e.to]) bridges.emplace_back(min(id, e.to), max(id, e.to));	 // 条件を満たすので橋
			} else if(e.to != par) {														 // eが後退辺の時
				low[id] = min(low[id], ord[e.to]);
			}
		}
		if(par == -1 && count >= 2) is_aps = true;
		if(is_aps) aps.push_back(id);
		return k;
	}
};

int main() {
	int N, M;
	cin >> N >> M;
	Graph g(N);
	for(int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(Edge{b});
		g[b].push_back(Edge{a});
	}

	LowLink link(g);
	cout << link.bridges.size() << "\n";
	return 0;
}

Measured memory_bytes: 256
import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)

Measured memory_bytes: 44912
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	private static final byte MASK_RIGHT = 0x0F;
	private static int[][] paper = new int[10][10];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 128);
		String sLine;
		while ((sLine = reader.readLine()) != null) {
			droppingInk(sLine.charAt(0) & MASK_RIGHT, sLine.charAt(2) & MASK_RIGHT, sLine.charAt(4) & MASK_RIGHT);
		}
		calcResult();
	}

	private static void droppingInk(int x, int y, int size) {
		staining(x, y - 1);
		staining(x - 1, y);
		staining(x, y);
		staining(x + 1, y);
		staining(x, y + 1);
		if (size == 1) {
			return;
		}

		staining(x - 1, y - 1);
		staining(x + 1, y - 1);
		staining(x - 1, y + 1);
		staining(x + 1, y + 1);
		if (size == 2) {
			return;
		}

		staining(x, y - 2);
		staining(x - 2, y);
		staining(x + 2, y);
		staining(x, y + 2);
	}

	private static void staining(int x, int y) {
		if (x >= 0 && x < 10 && y >= 0 && y < 10) {
			paper[x][y]++;
		}
	}

	private static void calcResult() {
		int white = 0;
		int maxnoud = 0;
		for (int[] row : paper) {
			for (int colum : row) {
				if (colum == 0) {
					white++;
				} else if (colum > maxnoud) {
					maxnoud = colum;
				}
			}
		}
		System.out.println(white);
		System.out.println(maxnoud);
	}
}

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

#define sz(a) (int)a.size()
#define re return
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(), a.end()
#define gr greater <int>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")

using namespace std;

typedef long long ll;
typedef string str;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;

///!!!<3<3<3<3<3!!!
void ProdamGaraje () {
   str s, s1;
   cin >> s >> s1;
   if (s1.substr(0, sz(s1) - 1) == s)
      cout << "Yes";
   else
      cout << "No";
}
///!!!<3<3<3<3<3!!!
int main () {
   //freopen ("input.txt", "r", stdin);
   //freopen ("output.txt", "w", stdout);
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   int tt = 1;
   //cin >> tt;
   while (tt--)
      ProdamGaraje ();
}
///GOOOOOOSE!!!!
/*
     ▄▀▀▀▄
▄███▀░0░░░▌
    ▌░░░░░▐
    ▌░░░░░▐
     ▌▌ ▌▌
     ▌▌ ▌▌
     ▌▌ ▌▌
     ▌▌ ▌▌
     ▌▌ ▌▌
   ▄▄▌▌▄▌▌        */


Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
void solving(){
  int n,m;
  cin>>n>>m;
  int a[m];
  int sum=0;
  for(int i=0;i<m;i++){cin>>a[i];sum+=a[i];}
  n=n-sum;
  if(n<0)cout<<"-1";
  else cout<<n<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
solving();
return 0;
}


Measured memory_bytes: 3660
use std::cmp::{max,min};
fn main() {
    let (n,t) = {
        let s = rv::<usize>();
        (s[0],s[1])
    };
    let mut ab = Vec::with_capacity(n);
    for _ in 0..n {
        let (a,b) = {
            let s = rv::<usize>();
            (s[0],s[1])
        };
        ab.push((a,b));
    }
    ab.sort();
    let mut dp = vec![0;t];
    let mut s = 0;
    for (a,b) in ab {
        s = max(s,dp[t-1]+b);
        for i in (0..t-min(t,a)).rev() {
            dp[i+a] = max(dp[i+a],dp[i]+b);
        }
    }
    println!("{}",s);
}
fn rl() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s
}
fn rv<T>() -> Vec<T>
  where T: std::str::FromStr, T::Err: std::fmt::Debug, {
    rl().split_whitespace().map(|x|x.parse::<T>().unwrap()).collect()
}

Measured memory_bytes: 4352
#include <cstdio>

using namespace std;

int a[100000];

int main() {
    int k, i;
    long long m1 = 2, m2 = 2;
    
    scanf("%d", &k);
    
    for (i = 0; i < k; i++) scanf("%d", &a[i]);
    
    for (i = k - 1; i >= 0; i--) {
        long long p = m1 / a[i] * a[i];
        
        if (p < m1) p += a[i];
        
        if (p > m2) {
            puts("-1");
            
            return 0;
        }
        
        m1 = p;
        m2 = m2 / a[i] * a[i] + a[i] - 1;
        
        if (m1 > m2) {
            puts("-1");
            
            return 0;
        }
    }
    
    printf("%lld %lld\n", m1, m2);
    
    return 0;
}


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

using namespace std;
using Int = long long;

signed main(){
    Int n, m;
    cin >> n >> m;
    vector<Int> l, r;
    for (Int i = 0; i < m; i++){
        Int tmp_l, tmp_r;
        cin >> tmp_l >> tmp_r;
        l.push_back(tmp_l);
        r.push_back(tmp_r);
    }
    Int l_max = *max_element(l.begin(), l.end());
    Int r_min = *min_element(r.begin(), r.end());
    Int ans = 0;
    if (l_max <= r_min) {
        ans = r_min - l_max + 1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2036
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring> 
#include<cassert>
#include<cmath>
#include<sstream>
#include<fstream>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
using namespace std;
int par[200005];
int fin(int x)
{
	if (par[x]==-1)return x; else return par[x]=fin(par[x]);
}
void bing(int x,int y)
{
	par[fin(x)]=fin(y);
}
pair<int,pair<int,int> > a[100005];
pair<int,pair<int,int> >mi[200005];
bool com(pair<int,pair<int,int> >x,pair<int,pair<int,int> >y)
{
	return x.second.first<y.second.first;
}
int main()
{
	int n;
	scanf("%d",&n);
	memset(par,-1,sizeof(par)); 
	for(int i=0;i<n;i++)
	{
		scanf("%d %d",&a[i].first,&a[i].second.first);
		a[i].second.second=i;
	}
	sort(a,a+n);
	int cnt=0;
	for(int i=1;i<n;i++)
	{
//		cout<<a[i].first<<" ";
		mi[cnt].first=a[i].first-a[i-1].first;
		mi[cnt].second.first=a[i].second.second;
		mi[cnt++].second.second=a[i-1].second.second;
//		cout<<mi[cnt-1].first<<endl;
	}
	sort(a,a+n,com);
	for(int i=1;i<n;i++)
	{
	//	cout<<mi[cnt].first<<endl;
		mi[cnt].first=a[i].second.first-a[i-1].second.first;
		mi[cnt].second.first=a[i].second.second;
		mi[cnt++].second.second=a[i-1].second.second;
//		cout<<mi[cnt-1].first<<endl;
	}
	
	sort(mi,mi+cnt);
	long long res=0;
	for(int i=0;i<cnt;i++)
	{
		int x=mi[i].second.first;
		int y=mi[i].second.second;
		if(fin(x)!=fin(y))
		{
			bing(x,y);
			res+=mi[i].first;
		}
	}
	cout<<res;
	return 0;
}

Measured memory_bytes: 4480
#include<iostream>
#include<algorithm>

using namespace std;


int main()
{
	int n, m, t;
	int a[2001] = { 0 };

	ios::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i != n; ++i) 
	{
		cin>>t;
		for (int j = 2000; j != 0; --j)
		{
			if (a[j])
			{
				a[j + t] = 1;
			}
		}
		a[t] = 1;
	}

	cin>>m;
	for (int i = 0; i != m;++i)
	{
		cin >> t;
		cout << (a[t]? "yes" : "no") << endl;
	}

	return 0;

}


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

int main(){
  int N;
  cin>>N;
  vector<pair<int,int>> table;
  for (int i=0;i<N;i++){
    int a,b;
    cin>>a>>b;
    table.emplace_back(make_pair(b,a));
  }
  sort(table.begin(),table.end());
  int sum=0;
  bool flag=1;
  for(int i=0;i<N;i++){
    sum+=table.at(i).second;
    if(sum>table.at(i).first){
      flag=0;
      break;
    }
  }
  if(flag){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  

}
      

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < n;i++)
const int INF = 1e9;

int main(){
	int N;string S;
	cin >> S ; N = S.length();
  	int ans = INF;
  	rep(i,N-1){
  	  if(S[i]!=S[i+1]) ans = min(ans,max(i+1,N-i-1));
  	}
  	if(ans==INF) ans = N;
  	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll xmax = 1000000000;

int main() {
  ll N, D, A;
  cin >> N >> D >> A;
  ll x[N], h[N];
  vector<P> v;
  
  for (ll i = 0; i < N; i++) {
    ll a, b;
    cin >> a >> b;
    v.push_back(P(a, b));
  }
  sort(v.begin(), v.end());
  
  for (ll i = 0; i < N; i++) {
    x[i] = v[i].first;
    h[i] = v[i].second;
  }
  
  
  //二分探索で、Xi+2D >= Xjなるj (bom[i]) を求めておく
  ll bom[N];
  for (ll i = 0; i < N; i++) {
    ll lb = i; ll ub = N;
    while (ub - lb > 1) {
      ll mid = (ub+lb)/2;
      if (x[i]+2*D >= x[mid]) {lb = mid;}
      else {ub = mid;}
    }
    bom[i] = lb;
  }
  
  //左端から始めて、最左端で生き残っているモンスターに対する攻撃を繰り返す
  //最左端のモンスターが受けたダメージの総数damage[N]
  //隣り合うモンスター同士のダメージの差をdiff[i]:=damage[i+1]-damage[i]として管理
  
  ll damage[N];
  for (ll i = 0; i < N; i++) {
    damage[i] = 0;
  }
  ll diff[N-1];
  for (ll i = 0; i < N-1; i++) {
    diff[i] = 0;
  }
  
  ll ans = 0;
  for (ll i = 0; i < N-1; i++) {
    //残っている体力
    ll res = h[i] - damage[i];
    //爆弾を使う回数
    ll times;
    if (res <= 0) {times = 0;}
    else {times = (res+A-1)/A;}
    ans += times;
    
    //ダメージの総数を更新
    damage[i] += (times * A);
    if (i > 0) {diff[i-1] += (times * A);}
    if (bom[i] < N-1) {diff[bom[i]] -= (times * A);}
    damage[i+1] = damage[i] + diff[i];
  }
  
  ll resn, timesn;
  resn = h[N-1] - damage[N-1];
  if (resn <= 0) {timesn = 0;}
  else {timesn = (resn+A-1)/A;}
  ans += timesn;
  
  cout << ans << endl;
}
    

Measured memory_bytes: 12268
N = int(input())
S = [0] * N
X = [0] * N
Y = [0] * N
for i in range(N):
    X[i], Y[i] = map(int, input().split())
    S[i] = X[i] + Y[i]
    #偶奇が一致しているか
    if (S[i] - S[0]) % 2 != 0:
        print(-1)
        exit()

nums = []
for i in range(30, -1, -1):
    #2の冪乗を生成
    nums.append(1 << i)

#偶数で一致している時、1を加えて偶数間を移動できるようにする
if S[0] % 2 == 0:
    nums.append(1)

m = len(nums)

print(m)
print(*nums)

for i in range(N):
    u = X[i] + Y[i]
    v = X[i] - Y[i]
    #貪欲に足し引きをしていくとu, vへの移動が完了する
    for num in nums:
        if u >= 0:
            if v >= 0:
                print('R',end='')
                u -= num
                v -= num
            else:
                print('U',end='')
                u -= num
                v += num
        else:
            if v >= 0:
                print('D',end='')
                u += num
                v -= num
            else:
                print('L',end='')
                u += num
                v += num
    print()

print()


Measured memory_bytes: 4528
#include <bits/stdc++.h>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <set>
#include <cmath>
#include <tuple>
#include <vector>
#include <array>
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define D()
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

ll saiki(std::bitset<11> b, std::string s, int d){
	ll ans = 0;
	if(d < s.size()){
		d++;
		ans += saiki(b, s, d);
		b[d-1] = true;
		ans += saiki(b, s, d);
	}else{
		ans = 0;
		ll num = 0;
		bool flag = false;
		for ( int i = 0 ; i < s.size() ; i++ ) {
			if(!b[i]){
				num *= 10;
				num += s[i] - '0';
			}
			if(b[i]){
				ans += num;
				num = s[i] - '0';
			}
		}
		ans += num;

	}
	return ans;
}

int main(){
	std::string s;
	std::cin >> s;
	ll ans = 0;
	std::bitset<11> b;
	ans = saiki(b,s,1);
	std::cout << ans << std::endl;
	return 0;
}



Measured memory_bytes: 256
def gcd(x, y):
    xx = 0; yy = 0
    if x >= y:
        xx = x; yy = y
    else:
        xx = y; yy = x
    while yy > 0:
        xx, yy = yy, xx%yy
    return xx


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    # i を入れた場合のgcdと i を入れない場合のgcdを考える
    ans = 1
    # gcd の結合則を利用する(X, Y, Zがありgcd(gcd(x,y),z)==gcd(x,gcd(x, y)))
    l = [0 for i in range(n)]
    r = [0 for i in range(n+1)]
    for i in range(n-1):
        l[i+1] = gcd(l[i], a[i])
    for i in range(n-1, -1, -1):
        r[i] = gcd(r[i+1],a[i])
    for i in range(n):
        ans = max(ans, gcd(l[i], r[i+1]))
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 14428
#include <iostream>
#include <vector>
#include <utility>
#include <cmath>

using namespace std;

vector<int> readnums(size_t n)
{
    vector<int> v;
    v.reserve(n);
    for(size_t i = 0; i < n; ++i){
        int m;
        cin >> m;
        v.push_back(m);
    }
    return v;
}

int main(){
    int N, T;
    cin >> N >> T;
    const vector<int> ti = readnums(N);
    
    size_t sum = T;
    
    for(int i = 0; i < N-1; ++i){
        sum += min(T, ti[i+1]-ti[i]);
    }
    
    cout << sum;
    return 0;
}


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

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 { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= 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 { return mint(*this) /= 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 = 0;
  ans += mint(10).pow(n);
  ans -= mint(9).pow(n);
  ans -= mint(9).pow(n);
  ans += mint(8).pow(n);
    //ans = ans+1000000007;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

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

const ll INF = LLONG_MAX;
const ll MOD = 1e9+7;

int main() {
    // input, ready
    string S;
    cin >> S;

    // output
    if (S == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;

    return 0;
}


Measured memory_bytes: 3592
import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
		sc.close();
		int d[] = new int[n - 1];
		for (int i = 1; i < n; ++i) {
			for (int j = i + 1; j <= n; ++j) {
				int dij = Math.min(j - i, Math.abs(x - i) + 1 + Math.abs(j - y));
				dij = Math.min(dij, Math.abs(y - i) + 1 + Math.abs(j - x));
				d[dij - 1]++;
			}
		}
		for (int dij : d)
			System.out.println(dij);
	}
}


Measured memory_bytes: 22484
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

#define loop(var, from, to) for (int var=from; var<to; ++var)

using namespace std;

int main() {
  vector<int> times;
#ifdef LOCAL
  cout << "Enter A to B, B to C, C to A:" << endl;
#endif
  string line;
  getline(cin, line, '\n');
  stringstream nss(line);
  int number;
  vector<int> walks;
  while (nss >> number)
    times.push_back(number);
  cout << endl;

  int ab_bc = times[0] + times[1];
  int ab_ca = times[0] + times[2];
  int bc_ca = times[1] + times[2];

  cout << min(min(ab_bc, ab_ca), bc_ca) << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long 
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define all(a) a.begin(),a.end()
#define ld long double
#define ub upper_bound
#define lb lower_bound
#define pii pair<int,int>
using namespace std;
signed main(){
    fast;
    int n,k;
    cin>>n>>k;
    int a[n+1];
    for(int i=1;i<=n;i++)
    	cin>>a[i];
    sort(a+1,a+n+1,greater<int>());
    int ans = 0;
    for(int i=k+1;i<=n;i++){
    	ans+=a[i];
    }
    cout<<ans;
}  

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int ans = 0;
		for (int i=1; i <= N ;i++) {
			ans +=i;

		}



		System.out.println(ans);

		sc.close();
	}

}


Measured memory_bytes: 9936
/*		Author : Kaustubh Gangwar
		||S||A||M||R||A||T||
*/
#include <bits/stdc++.h>
using namespace std;
#define modo 1000000007
#define ff first
#define ss second 
#define ld long double
#define pb push_back
#define gcd __gcd
#define vi vector<int>
#define vll vector<long long>
#define all(x) (x).begin(),(x).end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define fe(i,a,b) for(int i=a;i<=b;i++)
#define nl '\n'
typedef long long  ll;
typedef pair<int,int> pii;

ll bpow(ll a, ll b) {
	a=a; ll res = 1;
    while(b){
        if (b & 1)
        res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
void solve(ll n)
{	ll a[n+1]={0};
	fe(i,1,100)
	{
		fe(j,1,100)
		{
			fe(k,1,100)
			{
				if(i*i+j*j+k*k+i*j+j*k+k*i<=n)
				a[i*i+j*j+k*k+i*j+j*k+k*i]++;
			}
		}
	}
	fe(i,1,n)
	cout<<a[i]<<nl;
	
	
}

int32_t main()
{	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	ll test=1;
//	cin>>test;
	while(test--)
	{
		ll n; cin>>n;
		solve(n);
		
	}
return 0;
}


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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

// clang-format off
template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) { return stream << p.first << "," << p.second; }
template <typename T>
void print(const vector<T> vec) { rep (i, vec.size() - 1) cout << vec[i] << ' '; cout << vec[vec.size() - 1] << '\n'; }
template <typename Arg>
void print(const Arg arg) { cout << arg << '\n'; }
template <typename Head, typename... Args>
void print(const Head head, const Args... args) { cout << head << " "; print(args...); }
template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) { rep (i, v.size()) cin >> v[i] >> w[i]; }
template <typename T>
void init(vector<T>& v) { rep (i, v.size()) cin >> v[i]; }
template <typename T>
T sum_(vector<T> vec, T init = 0) { return std::accumulate(all(vec), T(init)); }
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m=0) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    double x;
    cin >> x;
    cout << setprecision(10) << 2 * M_PI * x << endl;

    return 0;
}


Measured memory_bytes: 3808
mod=10**9+7
s=list(input())
s=['-']+s
#print(s)
l=len(s)
dp=[[0 for j in range(4)] for i in range(l)]
dp[0][0]=1
for i in range(1,l):
    for j in range(4):
        dp[i][j]=dp[i-1][j]
        if s[i]=='?':
            dp[i][j]*=3;
        if (j  > 0) and (s[i]=='?' or 'ABC'[j-1]==s[i]):
            dp[i][j] += dp[i-1][j-1]
        dp[i][j] %= mod
        
print(dp[-1][3])
#print(dp)

Measured memory_bytes: 32476
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>


using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7;
const int MINF = -1050000000;


int main() {
	int h, a;
	cin >> h >> a;

	

	if (h%a == 0) {
		cout << h / a << endl;
		return 0;
	}
	else {
		cout << h / a + 1;
		return 0;
	}
	

	return 0;
}


Measured memory_bytes: 256
/*
 * ID: ITP2_10_C
 * Problem: Bit Flag
 */

#include <stdio.h>

int main(void)
{
    unsigned long a = 0;
    int i, n;

    scanf("%d", &n);

    int query, set;
    for (i = 0; i < n; i++) {
        int j, count;
        scanf("%d", &query);
        if (query < 4)
            scanf("%d", &set);
        switch (query) {
            case 0: // test(i)
                printf("%d\n", (a & (0x01L << set)) == 0 ? 0 : 1);
                break;
            case 1: // set(i);
                a |= 0x01L << set;
                break;
            case 2: // clear(i);
                a &= 0xffffffffffffffffL ^ (0x01L << set);
                break;
            case 3: // flip(i);
                a ^= 0x01L << set;
                break;
            case 4: // all
                printf("%d\n", a == 0xffffffffffffffffL ? 1 : 0);
                break;
            case 5: // any
                printf("%d\n", a >= 1 ? 1 : 0);
                break;
            case 6: // none
                printf("%d\n", a == 0 ? 1 : 0);
                break;
            case 7: // count
                for (j = 0, count = 0; j < 64; j++) {
                    if (a & (0x01L << j))
                        count++;
                }
                printf("%d\n", count);
                break;
            case 8: // val
                printf("%lu\n", a);
                break;
            //case 9: // val by hex
            //    printf("%lx\n", a);
            //    break;
        }
    }

    return 0;
}




Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
int x,y;
main()
{
  cin>>x>>y;
  if(x==1&&y==1) cout<<1000000;
  else
  {
    int z=(4-x>=1?(4-x)*100000:0);
    int z1=(4-y>=1?(4-y)*100000:0);
   	cout<<z+z1;
  }
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main 
{
	private static final int INFINITY = 1 << 30;

	class Vertex {
		int u;
		int d;
		boolean visited;
		List<Edge> edges = new ArrayList<>();
		public Vertex(int u) {
			this.u = u;
			this.d = INFINITY;
			this.visited = false;
		}
	}
	
	class Edge {
		int v;
		int c;
		public Edge(int v, int c) {
			this.v = v;
			this.c = c;
		}
	}
	
	class VertexComparator implements Comparator<Vertex> {
		@Override
		public int compare(Vertex arg0, Vertex arg1) {
			return arg0.d - arg1.d;
		}
	}
	
	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	
	private void run() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		Vertex[] vertices = new Vertex[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(reader.readLine());
			int u = Integer.parseInt(st.nextToken());
			vertices[i] = new Vertex(u); 
			int k = Integer.parseInt(st.nextToken());
			for (int j = 0; j < k; j++) {
				int v = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				vertices[i].edges.add(new Edge(v, c));
			}
		}
		reader.close();
		
		dijkstra(n, vertices);
	}

	private void dijkstra(int n, Vertex[] vertices) {
		
		vertices[0].d = 0;
		PriorityQueue<Vertex> pq = new PriorityQueue<>(5, new VertexComparator());
		pq.add(vertices[0]);
		while (!pq.isEmpty()) {
			Vertex cur = pq.poll();
			if (cur.visited) continue;
			cur.visited = true;
			for (Edge edge : cur.edges) {
				vertices[edge.v].d = Math.min(vertices[edge.v].d, cur.d + edge.c);
				pq.add(vertices[edge.v]);
			}
		}
		
		for (int i = 0; i < n; i++) {
			System.out.println(vertices[i].u + " " + vertices[i].d);
		}
	}
}


Measured memory_bytes: 89004
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

int const modulo = 1000000007;
  using ll = long long;

class Matrix{
//indexed from 1
private:
  int n, m;
public:
  vector<vector<int>> mat;
  Matrix(int n, int m){
    this->n = n;
    this->m = m;

    mat.resize(1 + n);
    for(int i = 1;i <= n; i++)
      mat[i].resize(1 + m);
  }
  Matrix operator * (Matrix const &a) const{
    assert(m == a.n);
    Matrix result(n, a.m);
    for(int i = 1;i <= n; i++)
      for(int j = 1;j <= a.m; j++)
        for(int h = 1; h <= m; h++)
          result.mat[i][j] = (result.mat[i][j] + 1LL * mat[i][h] * a.mat[h][j]) % modulo;
    return result;
  }

  Matrix lgpow(Matrix a, ll b){
    if(b == 0){
      Matrix result(a.n, a.m);
      for(int i = 1;i <= a.n; i++)
        result.mat[i][i] = 1;
      return result;
    } else if(b == 1)
      return a;
    else {
      Matrix result = lgpow(a, b / 2);
      if(b % 2 == 0)
        return result * result;
      else
        return result * result * a;
    }
  }
  Matrix operator ^ (ll b){
    return lgpow(*this, b);
  }
};

int lgpow(int a, ll b){
  if(b == 0)
    return 1;
  else if(b == 1)
    return a;
  else {
    int result = lgpow(a, b / 2);
    if(b % 2 == 0)
      return 1LL * result * result % modulo;
    else
      return 1LL * result * result % modulo * a % modulo;
  }
}

int const nmax = 1000;
char v[5 + nmax][5 + nmax];

int main()
{
  ll n, m, k;
  cin >> n >> m >> k;
  int connecth = 0, connectv = 0;
  int internh = 0, internv = 0;
  int blocks = 0;
  for(int i = 1;i <= n; i++)
    for(int j = 1;j <= m; j++) {
      cin >> v[i][j];
      v[i][j] = (v[i][j] == '#');
      blocks += v[i][j];
    }

  for(int i = 1; i <= n; i++)
    for(int j = 1;j <= m; j++){
      internh += (v[i][j] & v[i][j + 1]);
      internv += (v[i][j] & v[i + 1][j]);
    }

  for(int i = 1; i <= n; i++)
    connecth += (v[i][1] & v[i][m]);
  for(int i = 1;i <= m; i++)
    connectv += (v[1][i] & v[n][i]);

  if(k <= 1) {
    cout << 1;
    return 0;
  }
  if(0 < connecth && 0 < connectv)
    cout << 1;
  else if(0 == connecth && 0 == connectv)
    cout << lgpow(blocks, k - 1);
  else {
    Matrix init(2, 2), f(2, 2);
    init.mat[1][1] = 1;
    init.mat[1][2] = 1;

    if(0 < connecth){
      f.mat[1][1] = blocks;
      f.mat[2][1] = (modulo - internh) % modulo;
      f.mat[2][2] = connecth;
    } else {
      f.mat[1][1] = blocks;
      f.mat[2][1] = (modulo - internv) % modulo;
      f.mat[2][2] = connectv;
    }

    cout << (init * (f ^ (k - 1))).mat[1][1] << '\n';
  }
  return 0;
}


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

int main() {
  int h, w, m;
  cin >> h >> w >> m;
  vector<pair<int, int>> cnth(h), cntw(w);
  set<pair<int, int>> g;
  for(int i = 0; i < m; i++){
    int x, y;
    cin >> y >> x;
    x--, y--;
    cnth.at(y).first++, cntw.at(x).first++;
    g.insert({x, y});
  }
  
  for(int i = 0; i < h; i++) cnth.at(i).second = i;
  for(int j = 0; j < w; j++) cntw.at(j).second = j;
  
  sort(cnth.begin(), cnth.end()), sort(cntw.begin(), cntw.end());
  reverse(cnth.begin(), cnth.end()), reverse(cntw.begin(), cntw.end());
  
  int ans = 0, ansh = cnth.at(0).first, answ = cntw.at(0).first;
  for(int i = 0; i < h; i++){
    if(ansh-1 > cnth.at(i).first) break;
    bool ok = false;
    for(int j = 0; j < w; j++){
      if(answ-1 > cntw.at(j).first) break;
      int k = cnth.at(i).first + cntw.at(j).first;
      if(g.count({cntw.at(j).second, cnth.at(i).second})) k--;
      else ok = true;
      ans = max(ans, k);
      if(ok) break;
    }
    if(ok) break;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 21992
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int num[5]={0};
	for(int i=1;i<=3;i++)
	{
		int from,to;
		cin>>from>>to;
		num[from]++;
		num[to]++;
	}
	int c=0;
	for(int i=1;i<=4;i++)
	{
		if(num[i]&1==1)c++;
	}
	if(c==0||c==2)cout<<"YES";
	else cout<<"NO";
	return 0;
}

Measured memory_bytes: 256