akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string a, b, c;

int main() {
    cin >> a >> b >> c;

    char A = a[0] - 32;
    char B = b[0] - 32;
    char C = c[0] - 32;
    
    cout << A << B << C << endl;

    return 0;
}


Measured memory_bytes: 256
N,A,B = map(int, input().split())
H = [int(input()) for _ in range(N)]


def f(n, H, A, B): #n回の爆発で魔物を全て倒せるか判定
    c = 0
    for i in range(len(H)):
        t = H[i]
        t -= B*n
        if t > 0:
            c += t//(A-B) + min(1, t%(A-B))
    if c > n:
        return False
    else:
        return True
    
    
def g(u, l, H, A, B): #魔物を倒すことができる爆発の最小回数を二分探索
    if u-l < 2:
        if f(l, H, A, B):
            return l
        else:
            return u
    m = (u+l)//2
    if f(m, H, A, B):
        return g(m, l, H, A, B)
    else:
        return g(u, m, H, A, B)
    
    
ans = g(10**9, 1, H, A, B)
print(ans)

Measured memory_bytes: 7072
a, b, c, d = [int(elem) for elem in input().split()]

if c % b != 0:
    turn1 = (c // b) + 1
else:
    turn1 = (c // b)
if a % d != 0:
    turn2 = (a // d) + 1
else:
    turn2 = (a // d)
    
if turn1 <= turn2:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9184
object Main {
  def solve(i:Int, n: Int, maxNum: Int, arr: IndexedSeq[Int]):Int = {
    if (n == maxNum){
      -1
    }else{
      if(arr(i)==1){
        n + 1
      }else{
        solve(arr(i), n+1, maxNum, arr)
      }
    }
  }

  def main(args: Array[String]): Unit = {
    val n = io.StdIn.readLine().toInt
    val arr = for(i <- 0 until n) yield io.StdIn.readLine().toInt-1
    println(solve(0,0,n,arr))
  }
}


Measured memory_bytes: 39536
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

k, a, b = map(int, read().split())
for i in range(a, b + 1):
    if i % k == 0:
        print('OK')
        exit()
print('NG')


Measured memory_bytes: 9168
using System;

namespace tst
{
    class Program
    {
        public static void Main()
        {
            int[] L = new int[] { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
            int k = int.Parse(Console.ReadLine());
            Console.WriteLine(L[k - 1]);
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N; cin >>N;
  for(int i=0;i<=100;i++){
    for(int j=0;j<=100;j++){
      if(i*4+j*7==N){
        cout<<"Yes"<<endl;
        return 0;
      }
    }
    
  }
  cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;

typedef long long ll;

inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0' || '9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
	return x*f;
}

const int N=1e6+9;

int n;
int to[N<<1],nxt[N<<1],beg[N],tot;
int stk[N],top;

inline void adde(int u,int v)
{
	to[++tot]=v;
	nxt[tot]=beg[u];
	beg[u]=tot;
}

inline void add(int u,int v)
{
	adde(u,v);adde(v,u);
}

bool dfs(int u,int fa)
{
	if(u==n)
	{
		stk[++top]=n;
		return 1;
	}

	for(int i=beg[u],v;i;i=nxt[i])
		if((v=to[i])!=fa)
			if(dfs(v,u))
			{
				stk[++top]=u;
				return 1;
			}
	return 0;
}

int dfs2(int u,int fa)
{
	int ret=1;
	for(int i=beg[u],v;i;i=nxt[i])
		if((v=to[i])!=fa)
			ret+=dfs2(v,u);
	return ret;
}

int main()
{
	n=read();
	for(int i=1;i<n;i++)
		add(read(),read());
	
	dfs(1,0);
	reverse(stk+1,stk+top+1);

	int enda=top>>1;
	if(top&1)
		enda++;

	int siza=dfs2(stk[enda],stk[enda+1]);

	if(siza>n-siza)
		puts("Fennec");
	else
		puts("Snuke");

	return 0;
}


Measured memory_bytes: 16000
#include "bits/stdc++.h"
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
#define ri register int
#define Max(x, y) (((x) > (y)) ? (x) : (y))
#define Min(x, y) (((x) < (y)) ? (x) : (y))
#define Abs(x) ((x) < 0 ? (-(x)) : (x))
#define int long long
const int maxn = 1e3 + 10;
inline int read()
{
    int f = 1, r = 0;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (isdigit(c)) {
        r = 10 * r + c - '0';
        c = getchar();
    }
    return f * r;
}
inline void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline void writesp(int x) { write(x), putchar(' '); }
inline void writeln(int x) { write(x), puts(""); }
int N, L;
std::string s[maxn];

signed main()
{
    N = read(), L = read();
    for (ri i = 1; i <= N; ++i) {
        std::cin >> s[i];
    }
    std::sort(s + 1, s + 1 + N);
    for (ri i = 1; i <= N; ++i) {
        std::cout << s[i];
    }
    std::cout << std::endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws Exception {
    // Here your code !
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String N = br.readLine();

    int sum = 0;
    String line;
    while((line = br.readLine()) != null) {
      String[] l = line.split(" ");
      sum += (Integer.parseInt(l[1]) - Integer.parseInt(l[0])) + 1;
    }
    System.out.println(sum);
  }
}


Measured memory_bytes: 22356
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N;
  cin >> N;
  vi A(3*N);
  rep(i,3*N) {
    cin >> A[i];
  }
  sort(rng(A));
  reverse(rng(A));
  ll ans = 0;
  rep(k,N) {
    ans += A[k*2+1];
  }
  cout << ans << endl;
  return 0;
}

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

bool possible = true;
int A[100005];
int main()
{
	int n; cin >> n;
	for (int i = 0; i < n; i++) cin >> A[i];
	A[0]--;
	for (int i = 1; i < n; i++)
	{
		if (A[i]-1 >= A[i-1])A[i]--;
		if (A[i] < A[i-1]) possible = false;
	}
	cout << (possible ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
  
int main()
{
  int n;
  cin>>n;
  int ar[n];
  for(int i=0;i<n;i++)
   cin>>ar[i];
  map<int,long long int > mp;
  for(int i=0;i<n;i++)
   {
   	if(mp.find(ar[i])==mp.end())
   	  mp[ar[i]]=1;
   	else 
   	mp[ar[i]]++;
   }
   //cout<<mp[1]<<endl;
  long long int ans=0;
  for(auto i : mp)
  ans+=((i.second)*(i.second-1))/2;
  for(int i=0;i<n;i++)
  cout<<ans-mp[ar[i]]+1<<endl;
  return 0;
} 


Measured memory_bytes: 10240
#!/usr/bin/env python3
import sys
from math import factorial
from functools import lru_cache

def fact(x: int):
    if(x == 0 or x == 1):
        return 1
    if(dp[x] != 0):
        return dp[x]
    else:
        dp[x] = x * fact(x-1)
        
    return dp[x]

# @lru_cache(maxsize=1000000000)
def comb(n: int, r: int):
    # return fact(n) // (fact(r)*fact(n-r))
    return factorial(n) // (factorial(r)*factorial(n-r))


# dp = [0] * 1000000000

def solve(n: int, a: "List[int]"):
    a.sort()

    m = a[-1]
    print(m, min(a, key=lambda x:abs(m-x*2)))
    
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(n)]  # type: "List[int]"
    solve(n, a)

if __name__ == '__main__':
    main()


Measured memory_bytes: 16064
# abc131_a.py
# https://atcoder.jp/contests/abc131/tasks/abc131_a

# A - Security /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点: 100点

# 問題文
# すぬけ君の管理する研究室の扉にはロックがかかっており、解錠にはセキュリティコードを入力する必要があります。
# セキュリティコードは 4桁の数字列です。セキュリティコードが「入力しづらい」とは、同じ数字が連続する箇所が存在することを言います。
# 現在のセキュリティコード Sが与えられます。Sが「入力しづらい」なら Bad を、そうでなければ Good を出力してください。

# 制約
#     Sは半角数字のみからなる長さ 4の文字列

# 入力
# 入力は以下の形式で標準入力から与えられます。
# S


# 出力
# セキュリティコード Sが「入力しづらい」なら Bad を、そうでなければ Good を出力してください。

# 入力例 1
# 3776

# 出力例 1
# Bad

# 2文字目と 3 文字目が同じなので、3776は入力しづらいセキュリティコードです。

# 入力例 2
# 8080

# 出力例 2
# Good

# 同じ数字が連続していないので、8080は入力しづらいセキュリティコードではありません。

# 入力例 3
# 1333

# 出力例 3
# Bad

# 入力例 4
# 0024

# 出力例 4
# Bad


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    S = lines[0]
    # N = int(lines[0])
    # X, A = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(6):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(M):
    #     valueses.append(list(map(int, lines[i+1].split())))

    result = 'Good'
    for i in range(3):
        if S[i] == S[i+1]:
            result = 'Bad'

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['3776']
        lines_export = ['Bad']
    if pattern == 2:
        lines_input = ['8080']
        lines_export = ['Good']
    if pattern == 3:
        lines_input = ['1333']
        lines_export = ['Bad']
    if pattern == 4:
        lines_input = ['0024']
        lines_export = ['Bad']
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9148
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
#define double long double
#define EPS 1e-9
//#define PI 3.14159265358979

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

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < A[i].size(); j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}
template < typename T, typename U >
ostream &operator<<(ostream &os, const pair< T, U > &p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}
template < typename T, typename U >
istream &operator>>(istream &is, pair< T, U > &p) {
	is >> p.first >> p.second;
	return is;
}
template < typename T >
istream &operator>>(istream &is, vector< T > &A) {
	rep(i, A.size()) is >> A[i];
	return is;
}

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

struct edge {
	int from, to, d, c, i;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1LL << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

template < typename A, size_t N, typename T >
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
struct initializer {
	initializer() {
		cout << fixed << setprecision(20);
	}
};
initializer _____;

int N, M, K, T, Q, H, W;
signed main() {
	cin >> K;
	string S = "ACL";
	rep(i, K) cout << S;
	cout << endl;
	return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

using pii = pair<int, int>;

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N;
  while (cin >> N) {
    vec<pii, 2> G(N);
    for (int i = 0; i < N - 1; i++) {
      int a, b;
      cin >> a >> b;
      --a;
      --b;
      G[a].emplace_back(b, i);
      G[b].emplace_back(a, i);
    }
    int M;
    cin >> M;
    vector<pii> rules;
    for (int i = 0; i < M; i++) {
      int a, b;
      cin >> a >> b;
      --a;
      --b;
      rules.emplace_back(a, b);
    }
    vector<ll> edge_masks(N);
    auto dfs = [&](auto& dfs, int v, int p = -1, ll m = 0) -> void {
      edge_masks[v] = m;
      for (auto e : G[v]) {
        if (e.fst == p) continue;
        dfs(dfs, e.fst, v, m | (1ll << e.snd));
      }
    };
    dfs(dfs, 0);
    ll res = 0;
    for (int m = 0; m < (1 << M); m++) {
      ll white = 0;
      for (int i = 0; i < M; i++) {
        if (((m >> i) & 1) == 0) continue;
        int x = rules[i].fst, y = rules[i].snd;
        white |= edge_masks[x] ^ edge_masks[y];
      }
      int c = __builtin_popcount(m);
      ll ways = 1ll << ((N - 1) - __builtin_popcountll(white));
      if (c % 2 == 0) {
        res += ways;
      } else {
        res -= ways;
      }
    }
    cout << res << endl;
  }
  return 0;
}


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


long long digitSum( long long b, long long n )
{
    if( n < b ) return n;
    return digitSum(b, n/b) + n%b;
}


int main()
{
    long long n, s;
    cin >> n >> s;

    long long ans = -1;
    if( n == s ) ans = n+1;
    else{
        // 2 <= b <= sqrt(n) までを探索
        for( long long b = 2; b*b <= n; ++b ){
            if( digitSum(b, n) == s ){
                ans = b;
                break;
            }
        }
        // sqrt(n) < b <= n を全探索
        if( ans == -1 ){
            for( long long p = sqrt(n); p > 0; --p ){
                long long b = (n - s)/(long long)p + 1;
                if( b > p ){
                    if( digitSum(b, n) == s ){
                        ans = b;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define MAX 100000

int parent(int i){return i/2;}
int left(int i){return 2*i;}
int right(int i){return 2*i+1;}

int main(){
  int H,i,A[MAX+1];

  cin>>H;
  for(i=1;i<=H;i++) cin>>A[i];

  for(i=1;i<=H;i++){
    cout<<"node "<<i<<": key = "<<A[i]<<", ";
    if(parent(i)>=1) cout<<"parent key = "<<A[parent(i)]<<", ";
    if(left(i)<=H) cout<<"left key = "<<A[left(i)]<<", ";
    if(right(i)<=H) cout<<"right key = "<<A[right(i)]<<", ";
    cout<<endl;
  }
  return 0;
}



Measured memory_bytes: 3108
#include <stdio.h>
int main(void)
{
    int H,W,a,b;
    
    while(1){
        scanf("%d %d",&H ,&W);
        if( H == 0 && W == 0) break;
        
        for ( a = 0; a < H;  a++ ){
             for ( b = 0; b < W; b++ ){
             if(a == 0 || a == H-1 || b == 0 || b == W-1){    
                 
           
            printf("#");
        }
    
        else { 
            printf(".");
        }
             }
        printf("\n");
        }
    
       printf("\n");
                            
    
    }                
  
  
  return 0;
}


Measured memory_bytes: 2104
import math
ps = [tuple(map(int,input().split())) for i in range(3)]

def dist(p1,p2):
    x1,y1 = p1
    x2,y2 = p2
    return math.hypot(x1-x2, y1-y2)

es = [dist(ps[0],ps[1]), dist(ps[1],ps[2]), dist(ps[2],ps[0])]
longest = max(es)

#Heron
s = sum(es) / 2
area = math.sqrt(s * (s-es[0]) * (s-es[1]) * (s-es[2]))

h = 2 * area / longest
r = (longest * h) / (sum(es) + 2*h)
print(r)

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

/* メモリ食い過ぎ注意 */
#define int long long

typedef long long ll;

ll gcd(ll a, ll b)
{
    if (a < b)
        gcd(b, a);
    if (b == 0)
        return a;
    int r;
    while ((r = a % b))
    {
        a = b;
        b = r;
    }
    return b;
}

/* define const */
const ll INF = (1ll << 60);
const ll MOD = (ll)1e9 + 7;
/* end defineing */

signed main()
{
    vector<int> v;
    int tmp;
    cin >> tmp;
    v.push_back(tmp);
    cin >> tmp;
    v.push_back(tmp);
    cin >> tmp;
    v.push_back(tmp);
    sort(v.begin(),v.end());

    cout << v[0]+v[1] << endl;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll R0, W0, C, R;
    while (cin >> R0 >> W0 >> C >> R, W0 || R0 || C || R) {
        ll ans = max(0LL, (C * W0 - R0 + R - 1) / R);
        cout << ans << endl;
    }
}

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

using namespace std;
int arr[40][3],a,b,n;
int mem[40][401][401];
int dp(int i,int x,int y)
{
    if(i==n)
    {
        if(y!=0)
        {
            int q=__gcd(x,y);
        x/=q;
        y/=q;
        if(x==a&&y==b)
            return 0;
        else
            return 1e9;
        }
        else
            return 1e9;
    }
    if(mem[i][x][y]==-1)
    {
        mem[i][x][y]=min(dp(i+1,x,y),dp(i+1,x+arr[i][0],y+arr[i][1])+arr[i][2]);
    }
    return mem[i][x][y];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>a>>b;
    int c=__gcd(a,b);
    a/=c;
    b/=c;
    for (int i=0;i<n;i++)
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    memset(mem,-1,sizeof(mem));
    int f=dp(0,0,0);
    if(f>=1e8)
        cout<<-1<<endl;
    else
        cout<<f<<endl;
    return 0;
}


Measured memory_bytes: 25344
#include <stdio.h>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define REP(i, n) for (int i = 0; i < n; ++i)
#define REP1(i, n) for (int i = 1; i <= n; ++i)
#define REP2(i, n) for (int i = 2; i <= n; ++i)

vector<int> v;

void solve(int n) {
    REP2(base, n) REP2(exp, n) {
        int temp = pow(base, exp);
        // printf("base = %d, exp = %d, pow = %d\n", base, exp, temp);
        if (n >= temp) {
            v.push_back(temp);
        } else {
            break;
        }
    }
}

int main() {
    int X; // 1000
    scanf("%d", &X);

    if (X == 1) {
        printf("1\n");
        return 0;
    }

    solve(X);

    sort(v.begin(), v.end());

    printf("%d\n", v.back());

    return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>
int main(void){
    int len,que;
    int *flag;
    int *ac_n;
    char *x;
    int l,r,i,j,ans,temp;
    scanf("%d %d",&len,&que);
    flag=(int*)malloc(sizeof(int)*(len+10));
    x=(char*)malloc(sizeof(char)*(len+10));
    ac_n=(int*)malloc(sizeof(int)*(len+10));
    for(i=0;i<len+10;i++){
        flag[i]=0;
        x[i]=0;
        ac_n[i]=0;
    }
    scanf("%s",x);
    for(i=0;i<len+10;i++){
        if(x[i]=='A'){
            flag[i]=1;
        }else if(x[i]=='C'){
            flag[i]=2;
        }
    }
    temp=0;
    for(i=0;i<len+5;i++){
        if(flag[i]==1&&flag[i+1]==2){
            temp++;
        }
        ac_n[i+1]=temp;
    }

    for(i=0;i<que;i++){
        scanf("%d %d",&l,&r);
        l--;
        r--;
        ans=ac_n[r]-ac_n[l];
        printf("%d\n",ans);
    }
    free(flag);
    free(x);
    free(ac_n);
    return 0;
}

Measured memory_bytes: 1664
// {{{ include
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
// }}}
#include <tuple>

using namespace std;

typedef long long ll;
inline int in(){int x;scanf("%d",&x);return x;}

struct Team {
  int accept;
  int penalty;
  int id;
  Team(int id) : id(id), accept(0), penalty(0) {}
  bool operator<(const Team& rhs) const {
    return make_tuple(-accept, penalty, -id) < make_tuple(-rhs.accept, rhs.penalty, -rhs.id);
  }
  bool operator==(const Team& rhs) const {
    return accept == rhs.accept && penalty == rhs.penalty;
  }
};

int main()
{
  int M, T, P, R;
  while (M = in(), T = in(), P = in(), R = in(), M || T || P || R){
    vector<vector<int>> wa(T, vector<int>(P, 0));

    vector<Team> teams;
    teams.reserve(T);
    for (int i = 0; i < T; i++){
      teams.emplace_back(i + 1);
    }
    for (int i = 0; i < R; i++){
      int m = in(), t = in() - 1, p = in() - 1, j = in();
      if (j != 0) wa[t][p]++;
      else teams[t].penalty += wa[t][p] * 20 + m, teams[t].accept++;
    }
    sort(begin(teams), end(teams));
    auto prev = teams[0];
    for (int i = 0; i < T; i++){
      if (i != 0) putchar(",="[prev == teams[i]]);
      printf("%d", teams[i].id);
      prev = teams[i];
    }
    puts("");
  }
  return 0;
}

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

using namespace std;


/// Bismilahir Rahmanir Rahim


typedef unsigned int ui;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef short int si;
typedef unsigned short int usi;
typedef pair <int, int> pii;


#define CASE false
#define TEST false
#define BUFFER true
#define TIME false
#define DEBUG true
#define SET_GEN false
#define _ << " " <<
#define __ << "\n"
#define ff first
#define ss second
#define RANGE(a, b) (rand() % (b-a+1) + a)


const double pi = acos(-1.);
const double eps = 1e-7;
const int inf = 2147483647;
const int _inf = -2147483648;
const int mod = 1e9+7;
const int maxx = 1000000;


void delay(int sec); // DEBUG


void solution(void)
{
    string s, t;

    cin >> s >> t;
    int lens = s.length(), lent = t.length();

    vector <vector <int>> dp(lens+1, vector <int> (lent+1, 0));
    vector <char> lcs;

    for(int i = 1; i <= lens; ++i) {
        for(int j = 1; j <= lent; ++j) {
            if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    int i = lens-1, j = lent-1;
    while (i >= 0 && j >= 0) {
        if (s[i] == t[j]) {
            lcs.push_back(s[i]);
            i--;
            j--;
        }
        else if (dp[i][j+1] > dp[i+1][j]) i--;
        else j--;
    }

    reverse(lcs.begin(), lcs.end());

    int sz = lcs.size();
    for(int i = 0; i < sz; ++i) cout << lcs[i];



    return ;
}

int main(int argc, char *arv[])
{
    #if BUFFER
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #endif

    #if SET_GEN
    srand((unsigned int) time(0));
    #endif


    int t = 1;

    #if CASE
    int cnt = 1;
    #endif

    #if TEST
    cin >> t;
    #endif

    #if TIME
    clock_t start_time, end_time;
    double time_elapsed;
    #endif


    while(t--) {

        #if TIME
        start_time = clock();
        #endif

        #if CASE
        cout << "Case " << cnt++ << ": ";
        #endif

        solution();

        #if TIME
        end_time = clock();

        time_elapsed = (double) (end_time - start_time) / CLOCKS_PER_SEC;

        cout << "\nRuntime: " << fixed << setprecision(7) << time_elapsed << "\n";
        #endif
    }


    return 0;
}

void delay(int sec)
{
    int mili_sec = 1000 * sec;

    clock_t start_time = clock();

    while (clock() < start_time + mili_sec);

    return ;
}


Measured memory_bytes: 38512
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

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

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a = (a - b + MOD) % MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}
const int MAX = 200002;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
   int n;
   cin >> n;
   int pos1 = -1;
   int pos2 = -1;
   map<int, int> log;
   int tmp;
   int a[n + 1];
   memset(a, 0, sizeof(a));
   for (int i = 0; i < n + 1; i++) {
      cin >> tmp;
      tmp--;
      if(a[tmp] == 0) a[tmp] = i + 1;
      else {
         pos1 = a[tmp];
         pos2 = i + 1;
         break;
      }
   }
   int C = pos1 - 1;
   int B = n + 1 - pos2;
   COMinit();

   cout << n << endl;
   for (int k = 2; k <= n; k++) {
      ll ans = COM(n + 1, k);
      if (B + C >= k - 1) {
         ll tmp = COM(B + C, k - 1);
         sub(ans, tmp);
      }
      cout << ans << endl;
   }
   cout << 1 << endl;
   return 0;
}


Measured memory_bytes: 6272
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>
#include <list>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

#define _upgrade ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const long double PI = 3.14159265358979323846;

// ****************************************CODE***************************************//


int main() {
    int k, x;
    cin >> k >> x;

    int minval = -1000000;
    int maxval = 1000000;

    minval = max(minval, x-k+1);
    maxval = min(maxval, x+k-1);

    for(int i = minval; i <= maxval; i++){
        cout << i << " ";
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#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 INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;


ll dp[1005][4200];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m;cin >> n>> m;
  rep(i,1005){
      FOR(j,1,4200){
          dp[i][j] = LINF;
      }
  }
  vector<P> v(m);
  rep(i,m){
      ll a,b;cin >> a >> b;
      ll key = 0;
      rep(j,b){
          ll c; cin >> c;c--;
          key += (1ll<<c);
      }
      v[i] = mp(key,a);
  }
  dp[0][0] = 0;
  rep(i,m){
      ll key = v[i].first;
      ll a = v[i].second;
      rep(j,(1ll<<n)){
          dp[i+1][j] = min(dp[i][j],dp[i+1][j]);
          dp[i+1][j|key] = min(dp[i][j] + a, dp[i+1][j|key]);
      }
  }
  ll ans = dp[m][(1ll<<n)-1];
  
  if(ans==LINF){
      cout << -1 << endl;;
  }else{
      cout << ans << endl;
  }
}

Measured memory_bytes: 33280
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int cl(int a, int b) {
	return (a - (a%b)) / b;//b=0だと積む
}
int up(int a, int b) {
	return cl(a + b - 1, b);//b=0だと積む
}
int main() {
    int az=0;
    while(az==0){
    int n,k, ns,tu; int ans = 0;
	cin >> n >> k;
    if(n==0){
    az=1;
    }
    else{
	int wa = 0;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < k; i++) {
		wa = wa + a[i];
	}
	ans = wa;
	for (int i = k - 1; i+1 < n; i++) {
		wa = wa - a[i - k + 1] + a[i + 1];
		ans = max(ans, wa);
	}
	cout << ans<<endl;  
    }
    }
}



Measured memory_bytes: 3020
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000;
int n,x,y;
int ans[maxn+5];
int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>x>>y;
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        {
            int d=j-i;
            d=min(d,abs(x-i)+1+abs(y-j));
            d=min(d,abs(y-i)+1+abs(x-j));
            ans[d]+=1;
        }
    for(int i=1;i<n;++i) printf("%d\n",ans[i]);
    return 0;
}

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

#define INPUT_ARRAY(N, A) \
    int N; \
    std::cin >> N; \
    std::vector<int> A(N); \
    for(int i = 0; i < N; ++i) std::cin >> A[i];

template<class T>
void print(const T &C)
{
    for(auto i : C)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
}

int main()
{
    INPUT_ARRAY(N, A);
    
    std::sort(begin(A), end(A), [](int l, int r){ return l > r; });
    auto rit = std::unique(begin(A), end(A));
    A.erase(rit, A.end());
    
    std::cout << A.size();
}


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

using namespace std;

const long long INF = 1e15;
const long long Y = 128;
int main(){
	long long n,m;
	while(cin>>n>>m,n){
		vector<long long> cod(m),signal(n);
		for(int i=0;i<m;i++){//code input
			cin >> cod[i];
		}
		for(int i=0;i<n;i++){//signal input
			cin >> signal[i];
		}
		vector<vector<long long>> dp(n+1,vector<long long>(256,INF));
		for(int i=0;i<m;i++){
			int next_j = Y + cod[i];
			if(next_j>255)next_j = 255;
			else if(next_j<0)next_j = 0;
			dp[0][next_j] = (signal[0] - (next_j))*(signal[0] - (next_j));
		}
		for(int i=0;i<n-1;i++){
			for(int j=0;j<256;j++){
				if(dp[i][j] == INF)continue;
				for(int k=0;k<m;k++){
					int next_j = j + cod[k];
					if(next_j>255)next_j = 255;
					else if(next_j<0)next_j = 0;
					int zip_square = (signal[i+1] - next_j)*(signal[i+1] - next_j);
					dp[i+1][next_j] = min(dp[i+1][next_j],dp[i][j] + zip_square);
				}
			}
		}
		long long ans = INF;
		for(int i = 0;i<256;i++)
			ans = min(ans,dp[n-1][i]);
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 43716
#include<iostream>
    #include<vector>
    #include<climits>
    using namespace std;
    int frog(vector<int>& v){
      if(v.size()==1)
        return v[0];
      vector<int> dp(v.size());
      dp[0]=0;
      dp[1]=abs(v[1]-v[0]);
      for(int i=2; i<int(v.size()); i++){
      	dp[i] = min(abs(v[i-1]-v[i])+dp[i-1], abs(v[i-2]-v[i])+dp[i-2]);
      }
      return dp[v.size()-1];
    }
    int main(){
    	int n, tmp;
     	cin>>n;
      	vector<int> v;
      	for(int i=0;i<n;i++){
          cin>>tmp;
          v.push_back(tmp);
        }
      cout<<frog(v);
    	return 0;
    }

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

#define ll long long
#define ld long double
#define COIN const int
#define ite iterator
#define PII pair<int,int>
#define PSI pair<string,int>
#define PIS pair<int,string>

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define REPD(i,n) for((i)=(n)-1;(i)>=0;(i)--)

#define ALL(c) (c).begin(), (c).end()
#define sz(s) (s).size()
#define CLEAR(x) memset(x,0,sizeof x);

#define MP make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define X first
#define Y second

#define VI vector<int>
#define VS vector<string>
#define VII vector<PII>
#define VVI vector<VI>

#define PIII 3.1415926
#define PI 3.14
/*****************************************************************************/
const ll mod=1e9+7;
const ll INF=1e18;
/*****************************************************************************/

using namespace std;

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	string s; cin >>s;
	int cnt=0,mx=-1;
	if (s=="RSS") {
		cout <<"1";
		return 0;
	}
	bool ok=0;
	for (int i=0;i<3;i++) {
		if (s[i]=='R') {
			if (ok==0) ok=1;
			cnt++;
		}
		if (s[i]=='S') {
			ok=0;
			mx=cnt;
			cnt=0;
		}
	}
	cout <<max(mx,cnt);
	return 0;
}
/******************************************************************************
******************************************************************************/


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;

vector<ll> yakusu(ll n) {
    vector<ll> res;
    for (ll i = 1; i*i <= n; i++) {
        if (n%i == 0) {
            res.push_back(i);
            if (n/i != i) res.push_back(n/i);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main() {
    int n;
    ll m;
    cin >> n >> m;
    auto f = yakusu(m);
    auto iter = lower_bound(f.begin(), f.end(), n);
    ll ans = *iter;
    ans = m/ans;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3600
pub trait Bisect: Copy {
    fn halve(self, other: Self) -> Self;
    fn section_end(self, other: Self) -> bool;
}
impl Bisect for usize {
    fn halve(self, other: Self) -> Self {
        if self > other {
            other + (self - other) / 2
        } else {
            self + (other - self) / 2
        }
    }
    fn section_end(self, other: Self) -> bool {
        (if self > other {
            self - other
        } else {
            other - self
        }) <= 1
    }
}
impl Bisect for i64 {
    fn halve(self, other: Self) -> Self {
        (self + other) / 2
    }
    fn section_end(self, other: Self) -> bool {
        (self - other).abs() <= 1
    }
}
impl Bisect for f64 {
    fn halve(self, other: Self) -> Self {
        (self + other) / 2.
    }
    fn section_end(self, other: Self) -> bool {
        (self - other).abs() <= 1e-8
    }
}
pub fn binary_search<T: Bisect, F: Fn(T) -> bool>(f: F, ok: T, err: T) -> T {
    let mut ok = ok;
    let mut err = err;
    while !ok.section_end(err) {
        let m = ok.halve(err);
        if f(m) {
            ok = m;
        } else {
            err = m;
        }
    }
    ok
}
use std::io::Write;
use std::io::{stdin, stdout};
fn query(n: usize) -> bool {
    println!("? {}", n);
    stdout().flush().unwrap();
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.chars().collect::<Vec<_>>()[0] == 'Y'
}
fn main() {
    let kth = |k| {
        // k: [1, 1_000_000_000]
        let mut v = vec![];
        let mut b = 111_111_111;
        let mut p = 0;
        let mut ls = 0;
        for i in 1..10 {
            ls = i;
            let tb = if i == 1 { b + 1 } else { b };
            if p + tb < k {
                p += tb;
            } else {
                break;
            }
        }
        v.push(ls);
        while b > 1 {
            b /= 10;
            let mut ls = 0;
            let mut fin = false;
            for i in 0..10 {
                ls = i;
                if p + b < k {
                    p += b;
                } else {
                    if i == 0 {
                        if p + 1 < k {
                            p += 1;
                        } else {
                            fin = true;
                        }
                    }
                    break;
                }
            }
            if fin {
                break;
            }
            v.push(ls);
        }
        let mut x = 0usize;
        for &y in &v {
            x = x * 10 + y;
        }
        x
    };
    let k = binary_search(
        |k| {
            let mut n = kth(k);
            while n <= 1_000_000_000 {
                n *= 10;
            }
            !query(n)
        },
        1usize,
        1_000_000_001usize,
    );
    let mut x = kth(k + 1);
    while x % 10 == 0 {
        x /= 10;
    }
    let mut l = binary_search(|l| query(10usize.pow((l - 1) as u32)), 1usize, 11);
    if l >= 10 {
        l = binary_search(|l| query(2 * 10usize.pow((l - 1) as u32)), 10, 0usize);
    }
    while format!("{}", x).len() < l {
        x *= 10;
    }
    println!("! {}", x);
}


Measured memory_bytes: 4692
package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextInt() (int, error) {
	return strconv.Atoi(nextString())
}

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

func stringifyArray(arr []int) string {
	return strings.TrimRight(fmt.Sprintf("%+v", arr)[1:], "]")
}

func mul(a, b [][]int) [][]int {
	n := len(a)
	m := len(b)
	l := len(b[0])

	// fmt.Println(n,m,l)

	c := make([][]int, n)
	for i := 0; i < n; i++ {
		c[i] = make([]int, l)
		for j := 0; j < m; j++ {
			for k := 0; k < l; k++ {
				// fmt.Println(i,j,k)
				c[i][k] += a[i][j] * b[j][k]
			}
		}
	}
	return c
}

func main() {
	scanner.Split(bufio.ScanWords)

	n, _ := nextInt()
	m, _ := nextInt()

	a := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		a[i] = make([]int, m+1)
	}
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			a[i][j], _ = nextInt()
			a[i][m] += a[i][j]
			// fmt.Println(n, m, i, j, a)
			a[n][j] += a[i][j]
		}
		a[n][m] += a[i][m]
	}

	for i := 0; i < n+1; i++ {
		fmt.Println(stringifyArray(a[i]))
	}
}



Measured memory_bytes: 1384
#!/usr/bin/env python

# Initially, all cards face up.
# Given that N,M >= 0.
# Let N <= M.
# Ultimately:
#   if N,M==1:      singular card will flip.
#   elif N==1:      interior cards will flip (interior to line).
#   else N,M > 1:   interior cards will flip (interior to area).

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

# Ensuring N <= M
if N > M:
    M,N = N,M

# Requires N <= M:
def numflips(N,M):
    if N==0: return 0
    if N==1:
        if M==1: return 1
        return (M-2)
    return (N-2)*(M-2)

ans = numflips(N,M)
print(ans)

Measured memory_bytes: 3060
#113-C
n,m=map(int,input().split())
l=[list(map(int,input().split()))+[i] for i in range(m)]
#p,y
l=sorted(l, key=lambda x: x[1])  # 1番目の要素
ans=[]

from collections import defaultdict
cnt=defaultdict(lambda:0)

for i in range(m):
    cnt[l[i][0]]+=1
    s=str(l[i][0])
    i_str=str(cnt[l[i][0]])
    s_keta=len(s)
    i_keta=len(i_str)
    ans+=[['0'*(6-s_keta)+s+'0'*(6-i_keta)+str(cnt[l[i][0]]),l[i][-1]]]

ans=sorted(ans,key=lambda x:x[1])
#print(*ans,sep='\n')


for i in ans:
    print(i[0])


Measured memory_bytes: 49872
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    String[] yoko = new String[h];
    for (int i = 0; i < h; i++) {
      yoko[i] = sc.next();
    }
    String[] yoko_c = new String[h];
    int y_idx = 0;
    for (int i = 0; i < h; i++) {
      if (yoko[i].contains("#")) {
        yoko_c[y_idx] = yoko[i];
        y_idx++;
      }
    }
    ArrayList<Integer> ary = new ArrayList<>();
    for (int i = 0; i < w; i++) {
      boolean flag = false;
      for (int j = 0; j < y_idx; j++) {
        if (yoko_c[j].charAt(i) == '#') {
          flag = true;
        }
      }
      if (flag) {
        ary.add(i);
      }
    }
    for (int i = 0; i < y_idx; i++) {
      for (int j = 0; j < ary.size(); j++) {
        System.out.print(yoko_c[i].charAt(ary.get(j)));
      }
      System.out.println();
    }
  }
}

Measured memory_bytes: 25940
// Vicfred
// https://atcoder.jp/contests/abc152/tasks/abc152_d
// math, combinatorics
import std.conv;
import std.stdio;
import std.string;

void main() {
    int n = readln.chomp.to!int;

    long[10][10] digits;

    // count the numbers starting in i and ending in j
    for(int i = 0; i <= n; i++)
        digits[i.to!string[0] - '0'][i.to!string[$-1] - '0'] += 1L;

    long answer = 0L;
    for(int i = 1; i <= 9; ++i)
        for(int j = 0; j <= 9; ++j)
            answer += digits[i][j]*digits[j][i];

    answer.writeln;
}



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

int main()
{
    int h = 0, w = 0;
    cin >> h >> w;
    vector<string>s(h);
    for (int i = 0; i < h; i++)
    {
        cin >> s[i];
    }
    for (int i = 0; i < h; i++)
    {
        for (int y = 0; y < 2; y++)
        {
            cout << s[i] << endl;
        }
    }
    return 0;
}

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

int func(int num);

int main()
{
    int n=0;
    int i,j,k;
    char bi[200020]={0};
    int numofi=0;
    int upper,lower;
    int z1[200020]={1};
    int z2[200020]={1};
    long long int first1=0;
    long long int first2=0;

    scanf("%d",&n);
    scanf("%s",bi);
    for(i=0;i<n;i++)
    {
        bi[i]-='0';
        if(bi[i]==1)numofi++;
    }
    //剰余テーブルを2つ作る
    upper=numofi+1;
    lower=numofi-1;
    for(j=1;j<n;j++)
    {
        z1[j]=((z1[j-1]*2)%upper);
        if(lower!=0)z2[j]=((z2[j-1]*2)%lower);
    }
    //初期値を計算
    for(k=0;k<n;k++)
    {
        if(bi[k]==1)
        {
            first1+=(long long int)z1[n-1-k];
            first2+=(long long int)z2[n-1-k];
        }
    }
    for(i=0;i<n;i++)
    {
        if(bi[i]==0)//0から1になる
        {
            printf("%d\n",func((int)((first1+(long long int)z1[n-1-i])%(long long int)upper)));
        }
        else if(bi[i]==1)//1から0になる
        {
            if(lower==0)printf("0\n");
            else printf("%d\n",func((int)((first2-(long long int)z2[n-1-i])%(long long int)lower)));
        }
    }

    //printf("%d",numofi);
}

int func(int num)
{
    int n=num;
    int m=0;
    int ret=1;
    int def=0;
    while(n>0)
    {
        m=n;
        while(m>0)
        {
            if(m%2==1)def++;
            m/=2;
        }
        n=(n%def);
        def=0;
        ret++;
    }
    return ret;
}

Measured memory_bytes: 3492
/*maximum subarray sum 
 * kadane algo space optimize dp
*/




#include <bits/stdc++.h>
using namespace std;



int main()
{
	int n;
	cin>>n;
	int k;
	cin>>k;
	int arr[n];
	for(int i = 0;i<n;i++)
	cin>>arr[i];
	int dp[n];
	dp[0] = 0;
	for(int i  = 1;i<n;i++)
	{
		int ans = INT_MAX;
		for(int j = i - 1;j>=0&&(i-j)<=k;j--) // contradiction
		ans = min(ans,abs(arr[i] - arr[j]) + dp[j]);
		
		dp[i] = ans;
	}
	cout<<dp[n-1]<<endl;
	
}


Measured memory_bytes: 4368
#include<iostream>
using namespace std;
int mod(int a,int b)
{
  if(a>b)
    return a-b;
  else
    return b-a;
}
int main()
{
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  cin>>a[i];
  if(n==1)
  {
    cout<<0<<endl;
    return 0;
  }
  int dp[n];
  dp[0]=0;
  dp[1]=mod(a[0],a[1]);
  for(int i=2;i<n;i++)
  {
    dp[i]=min(dp[i-1]+mod(a[i],a[i-1]),dp[i-2]+mod(a[i],a[i-2]));
  }
  cout<<dp[n-1]<<endl;
  return 0;
}


Measured memory_bytes: 1024
H,W = map(int,input().split())
A = []
for i in range(H):
    a = list(input())
    if "#" in a:
        A.append(a)
    else:
        H -= 1
for j in range(W-1,-1,-1):
    for i in range(H):
        if A[i][j] == "#":
            break
        elif i == H - 1:
            for k in range(H):
                del A[k][j]
for e in A:
    print("".join(e))

Measured memory_bytes: 3064