akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = s, i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = s, i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = s; i < (n); ++i)
#define VFORS(i, s, n) for(int i = s; i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = s, i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = s, i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end());

using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;
using VD = vector<double>;
using VLL = vector<ll>;
using VS = vector<string>;

const int MOD = 1000000007;
const int INF = 1000000000;

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

int const MAX_N = 100001;

int main(){
    vector<bool> isprime(MAX_N, true);
    isprime[0] = isprime[1] = false;
    FOR(i, 2, MAX_N) if(isprime[i])
        for(int j = i + i; j <= 100000; j += i)
            isprime[j] = false;
    vector<int> cnt(MAX_N, 0);
    for(int i = 3; i < MAX_N; i += 2)
        if(isprime[i] && isprime[(i+1)/2]) ++cnt[i];
    FOR(i, 3, MAX_N) cnt[i] += cnt[i-1];
    int q; cin >> q;
    REP(i, q){
        int l, r; cin >> l >> r;
        cout << cnt[r] - cnt[l-1] << "\n";
    }
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int n=0;bool b=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')b=0;c=getchar();}
	while(c>='0'&&c<='9')n=(n<<3)+(n<<1)+(c^48),c=getchar();
	return b?n:-n;
}
struct dalao
{
    int left;
	int right;	
}a[100100];
bool juruo(dalao x,dalao y)
{
	return x.right<y.right;
}
int main()
{
	int n,s=1,d;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		int t1=read(),t2=read(); 
		a[i].left=t1-t2,a[i].right=t1+t2;
	}
	sort(a+1,a+n+1,juruo);
	d=a[1].right;
	for (int i=2;i<=n;i++)
	{
		if (a[i].left>=d)
		{
			d=a[i].right;
			s++;
		}
	}
	cout<<s;
	return 0;
} 


Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define MAXN 200000
int n,Q;
char s[MAXN+5];
char A[MAXN+5][1],B[MAXN+5][1];
bool check1(int pos)
{
    char ch=s[pos];
    for(int i=1;i<=Q;i++)
    {
        if(pos==0)return 1;
        if(pos==n+1)return 0;
        if(A[i][0]==ch){pos+=(B[i][0]=='L')?-1:1;ch=s[pos];}
    }
    return (pos==0);
}
bool check2(int pos)
{
    char ch=s[pos];
    for(int i=1;i<=Q;i++)
    {
        if(pos==n+1)return 1;
        if(pos==0)return 0;
        if(A[i][0]==ch){pos+=(B[i][0]=='L')?-1:1;ch=s[pos];}
    }
    return (pos==n+1);
}
int main()
{
    scanf("%d%d",&n,&Q);
    scanf("%s",s+1);
    for(int i=1;i<=Q;i++)
    scanf("%s%s",A[i],B[i]);
    int l=0,r=n+1,pl=0,pr=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check1(mid)){pl=mid;l=mid+1;}
        else r=mid-1;
    }
    l=0,r=n+1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check2(mid)){pr=n-mid+1;r=mid-1;}
        else l=mid+1;
    }
    printf("%d",max(n-pl-pr,0));
}

Measured memory_bytes: 768
def main():
    h,w=[int(i) for i in input().split()]
    field=[]
    for i in range(h):
        field.append(input())

    for i in range(h):
        new_line=[]
        for j in range(w):
            ans=0
            if field[i][j]=='#':
                new_line.append('#')
                continue
            if i-1 >=0 and field[i-1][j]=='#':
                ans+=1
            if i+1 < h  and field[i+1][j]=='#':
                ans+=1
            if j-1 >=0 and field[i][j-1]=='#':
                ans+=1
            if j+1 < w and field[i][j+1]=='#':
                ans+=1
            if i-1 >= 0 and j-1 >= 0 and field[i-1][j-1]=='#':
                ans+=1
            if i-1 >= 0 and j+1 < w and field[i-1][j+1]=='#':
                ans+=1
            if i+1 < h and j-1 >= 0 and field[i+1][j-1]=='#':
                ans+=1
            if i+1 < h and j+1 < w  and field[i+1][j+1]=='#':
                ans+=1
            new_line.append(str(ans))
        print(''.join(new_line))

if __name__=='__main__':
    main()


Measured memory_bytes: 3064
#include <unordered_set>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <functional>
#include <set>

void run() {
	std::string str;
	std::cin >> str;
	str[3] = '8';
	std::cout << str << std::endl;
}
int main() {
	run();
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#define mod 1000000007
using namespace std;
long long int dp[21][1<<22];
int vis[21][1<<22];
int a[21][21];
int n;
long long rec(int i,int st){
	if(st==(1<<n)-1)return 1;
	if(i>=n)return 0;
	if(vis[i][st])return dp[i][st];
	for(int j=0;j<n;j++){
		if(a[i][j]==0)continue;
		if((st&(1<<j))!=0)continue;
		dp[i][st]=(dp[i][st]+rec(i+1,st|(1<<j)))%mod;
	}
	vis[i][st]=1;
	return dp[i][st];
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];
	cout<<rec(0,0);
}

Measured memory_bytes: 497920
import numpy as np
A = int(input())
B = int(input())
C = int(input())
X = int(input())
memo = np.zeros(3).reshape(1,3)

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if X == 500*i + 100*j + 50*k :
                result = np.array([i,j,k])
                memo = np.vstack([memo,result])

print(len(memo[1:]))

Measured memory_bytes: 12488
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)



template<class Abel> struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<Abel> diff_weight;

    UnionFind(int n = 1, Abel SUM_UNITY = 0) {
        init(n, SUM_UNITY);
    }

    void init(int n = 1, Abel SUM_UNITY = 0) {
        par.resize(n); rank.resize(n); diff_weight.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    Abel weight(int x) {
        root(x);
        return diff_weight[x];
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y, Abel w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }

    Abel diff(int x, int y) {
        return weight(y) - weight(x);
    }
};


int main(){
    int N,M;cin >> N >> M;
    UnionFind<int> uni(N);
    rep(i,M){
        int a,b,c;
        cin >> a >> b >> c;
        a--;b--;

        if(uni.issame(a,b)){    // 同一集合内にある時の分岐
            int diff = uni.diff(a,b);

            if(diff != c){
                cout << "No" << endl;
                return 0;
            }
        }
        else{
            uni.merge(a,b,c);
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "YES" << endl
#define pyes cout << "Yes" << endl
#define POK cout << "OK" << endl
#define PNO cout << "NO" << endl
#define pno cout << "No" << endl
#define PNG cout << "NG" << endl
#define ret return 0

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;
typedef pair<ll, ll> pl;

// const
// 円周率
const ld pi = acos(-1);
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)
//  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
//  ba;
struct tsort {
  int V;
  vector<vector<int>> G;
  vector<int> deg, res;
  tsort(int node_size) : V(node_size), G(V), deg(V, 0) {}
  void add_edge(int from, int to) {
    G[from].push_back(to);
    deg[to]++;
  }
  bool sort() {
    queue<int> que;
    for (int i = 0; i < V; i++) {
      if (deg[i] == 0) {
        que.push(i);
      }
    }
    while (!que.empty()) {
      int p = que.front();
      que.pop();
      res.push_back(p);
      for (int v : G[p]) {
        if (--deg[v] == 0) {
          que.push(v);
        }
      }
    }
    return (*max_element(deg.begin(), deg.end()) == 0);
  }
};
signed main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  tsort t(n);
  rep(i, m) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    t.add_edge(x, y);
  }
  t.sort();

  vector<int> dp(n, 0);
  for (int i : t.res) {
    for (int to : t.G[i]) {
      chmax(dp[to], dp[i] + 1);
    }
  }
  cout << MAX(dp) << endl;
  ret;
}


Measured memory_bytes: 9988
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int n,c=0;
    long l,r,d;
    cin>>n>>d;
    for(int i=0;i<n;++i){
        cin>>l>>r;
        if(sqrt(l*l+r*r)>d)
        continue;
        ++c;
    }
    cout<<c;
    
}

Measured memory_bytes: 3676
A = []
B = set()
ans = [[0,0,0],[0,0,0],[0,0,0]]
for i in range(3):
    A.append(list(map(int, input().split())))
N = int(input())
for i in range(N):
    B.add(int(input()))

for i in range(3):
    for j in range(3):
        if A[i][j] in B:
            ans[i][j] = 1

#ゴミコードだなぁ……

if ans[0][0] + ans[0][1] + ans[0][2] == 3:
    print('Yes')
elif ans[0][0] + ans[1][0] + ans[2][0] == 3:
    print('Yes')
elif ans[0][0] + ans[1][1] + ans[2][2] == 3:
    print('Yes')
elif ans[1][0] + ans[1][1] + ans[1][2] == 3:
    print('Yes')
elif ans[2][0] + ans[2][1] + ans[2][2] == 3:
    print('Yes')
elif ans[0][1] + ans[1][1] + ans[2][1] == 3:
    print('Yes')
elif ans[0][2] + ans[1][2] + ans[2][2] == 3:
    print('Yes')
elif ans[0][2] + ans[1][1] + ans[2][0] == 3:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38384
#include <stdio.h>
#define MAX 1000

int m[MAX][MAX],M[MAX],n;

int min(int x,int y)
{
    if( x <= y ) return x;
    else return y;
}

void MatrixChain(){
    int i,j,k,l,q;
    for( i = 1 ; i <= n ; i++ ) {
        m[i][i] = 0;
    }
    for( l = 2 ; l <= n ; l++ ){
        for( i = 1 ; i <= n-l+1 ; i++ ){
            j = i + l - 1;
            m[i][j] = 100000000;
            for( k = i ; k <= j-1 ; k++ ){
                q = m[i][k] + m[k+1][j] + M[i-1]*M[k]*M[j];
                m[i][j] = min(m[i][j],q);
            }
        }
    }
    
}

int main(){
    int i;
    scanf("%d",&n);
    
    for( i = 1  ; i <= n ; i++ ){
        scanf("%d%d",&M[i-1],&M[i]);
    }    
    
    MatrixChain();
    
    printf("%d\n",m[1][n]);
    
    return 0;
}

Measured memory_bytes: 980
N = int(input())

X = [None] * N
U = [None] * N

total = 0.

for i in range(N):
    x, u = input().split()
    x = float(x)
    if u == 'JPY':
        total += x
    else:
        total += 380000. * x

print('{:.5f}'.format(total))

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

using namespace std;

int main()
{
  int H, W;

  cin >> H >> W;

  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      string S;
      cin >> S;
      if(S == "snuke") {
        cout << (char) ('A' + j) << i + 1 << endl;
        return 0;
      }
    }
  }


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n+1); i++)
int main() {
  int A,B,C;
  cin>>A>>B>>C;
  rep(i,100000000){
      if(A==B&&B==C)
      {
        	if(i==0){
              if(A%2==1||B%2==1||C%2==1){
              cout<<0<<endl;
              break;
              }
            }
          cout<<-1<<endl;
        	break;
      }
    if(i==0){
      	if(A%2==1||B%2==1||C%2==1){
              cout<<0<<endl;
              break;
        }
            }
      int D=A;
      int E=B;
      int F=C;
      A=(E+F)/2;
      B=(D+F)/2;
      C=(D+E)/2;
      if(A%2==1||B%2==1||C%2==1){
          cout<<i+1<<endl;
        break;
      }
  }
}


Measured memory_bytes: 3580
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            int h = sc.nextInt();
            int w = sc.nextInt();
            String[] s = new String[h];
            for (int i = 0; i < h; i++) {
                s[i] = sc.next();
            }

            boolean ok = true;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (s[i].charAt(j) == '#') {
                        if ((i == 0 || s[i - 1].charAt(j) != '#') && (i == h - 1 || s[i + 1].charAt(j) != '#')
                                && (j == 0 || s[i].charAt(j - 1) != '#') && (j == w - 1 || s[i].charAt(j + 1) != '#')) {
                            ok = false;
                            break;
                        }
                    }
                }
                if (!ok) {
                    break;
                }
            }

            if (ok) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

}


Measured memory_bytes: 22740
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong n;
string s = "a";
set<char> st;
void dfs(int i) {
    if (i >= n) {
        cout << s << '\n';
        return;
    }

    for (auto ch:st) {
        s.push_back(ch);
        dfs(i + 1);
        s.pop_back();
    }
    
    s.push_back(*(st.rbegin()) + 1);
    st.insert(*(st.rbegin()) + 1);
    dfs(i + 1);
    st.erase(*(st.rbegin()));
    s.pop_back();

    return;
}

int main() {
    cin >> n;

    st.insert('a');
    dfs(1);

    return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <array>
#include <bitset>
using namespace std;

typedef long long ll;
const ll mod=1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<n+1;i++)
int main(){
    int N,M,d[100001],dd,L,R;
    cin>>N>>M;
    rep(i,N) d[i]=0;
    rep(i,M){
        cin>>L>>R;
        d[L-1]+=1;
        d[R]-=1;
    }
    int num=0;
    Rep(i,N){
        dd+=d[i-1];
        if(dd==M) num++;
    }
    cout<<num<<endl;

    return 0;
}

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

int main(int argc, char const *argv[])
{

    int N;
    cin >> N;
    int res = 0, m = 0;
    int preH;
    cin >> preH;
    for (int i = 1; i < N; i++)
    {
        int H;
        cin >> H;
        if (H <= preH)
        {
            m++;
            res = max(res, m);
        }
        else
        {
            res = max(res, m);
            m = 0;
        }
        preH = H;
    }
    cout << res << endl;
    return 0;
}


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

int main(){
  int h1,h2,m1,m2;
  cin>>h1>>m1>>h2>>m2;
  int k;cin>>k;
  m1 += h1*60;
  m2 += h2*60;
  
  cout<<m2-k-m1<<endl;
}

Measured memory_bytes: 3636
import java.util.*;
public class Main {
	Scanner sc = new Scanner(System.in);
	int a,b,c,d,e,f,k,l,m,n,q,x,y,z;
	int ans;
	int[] pl;
	String[] S;

	Main(){
		// 整数の入力
		n = sc.nextInt();
		k = sc.nextInt();
		q = sc.nextInt();

		pl = new int[n];

		for(int i=0;i<q;i++){
			pl[sc.nextInt()-1] += 1;
		}

		for(int i:pl){
			System.out.println(k-q+i>0?"Yes":"No");
		}
	}

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

Measured memory_bytes: 55064
#define _CRT_SECURE_NO_WARNINGS

/* include ***********************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

/* define *************************/
//for
#define REP(i,n) for(int i=0,i##_len=(int)(n);i<i##_len;i++)
#define REPS(i,n) for(int i=1,i##_len=(int)(n);i<=i##_len;i++)
#define RREP(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define RREPS(i,n) for(int i=(int)(n);i>0;i--)
#define FOR(i,s,n) for(int i=(int)(s),i##_len=(int)(n);i<i##_len;i++)
#define RFOR(i,s,n) for(int i=(int)(n)-1,i##_len=(int)(s);i>=i##_len;i--)

//printf
#define PRINTD(d) printf("%d\n",(d))
#define PRINTL(d) printf("%lld\n",(d))

//memset
#define m0(s) memset(s,0,sizeof(s))
#define ml(s) memset(s,63,sizeof(s))
#define fill(s,c) memset(s,c,sizeof(s))

#define INF 1e9
#define MOD 2019

typedef long long ll;
typedef unsigned long long ull;

int diff[4][2] = {
	{ 0, -1 },
	{ -1, 0 },
	{ 1, 0 },
	{ 0, 1 },
};
//今回の変数

int Min(int a, int b) {
	return (a)<(b) ? (a) : (b);
}
int Max(int  a, int  b) {
	return (a) > (b) ? (a) : (b);
}
ll Minl(ll a, ll b) {
	return (a)<(b) ? (a) : (b);
}
ll Maxl(ll a, ll b) {
	return (a)>(b) ? (a) : (b);
}
ll getPow(ll a, ll b){
	if (b == 0) return 1;
	if (b % 2 == 0) {
		ll d = getPow(a, b / 2);
		return (d*d) % MOD;
	}
	else {
		return (a*getPow(a, b - 1))%MOD;
	}
}


int main() {
	int n;
	scanf("%d", &n);

	int a[100000];
	REP(i, n) {
		scanf("%d", &a[i]);
	}

	int ans[100000] = { 0 };
	int sign = 1;
	RREP(i, n) {
		ans[0] += a[i] * sign;
		sign *= -1;
	}
	int x = ans[0] / 2;
	ans[1] = 2 * (a[0] - x);
	FOR(i, 2, n) {
		ans[i] = 2 * (a[i-1] - ans[i - 1]/2);
	}

	REP(i, n) {
		printf("%d ", ans[i]);
	}
	puts("");
}


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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

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

  bool ok = false;
  string s, t;
  cin >> s >> t;
  REP(si, s.size()) {
    s = s.back() + s.substr(0, s.size() - 1);
    if (s == t) ok = true;
  }
  OK(ok);

  

  return 0;
}



Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    A, B, K = list(map(int, input().strip().split()))
    return A, B, K


def solve(A, B, K):
    d = defaultdict(bool)
    for a in range(A, min(A+K, B+1)):
        d[a] = True
    for b in range(B, max(A-1, B-K), -1):
        d[b] = True
    ans = list(sorted(d.keys()))
    for a in ans:
        print(a)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


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

#define pb push_back
#define MAX 100005
#define ff first
#define ss second
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

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

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

int n,m;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    cout<<(n-1)*(m-1)<<"\n";
    return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int n, m;
  cin >> n >> m;

  if (n == m) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3560
#include <stdio.h>
int main(){

  int  x, y,tmp;

  while(1){

   scanf("%d%d",&x, &y);

   if( x == 0 && y == 0 ){

     break;

   } else if(x > y){
     tmp = x; x = y; y = tmp;
   }
    printf("%d %d\n",x, y);
  }
return 0;
}


Measured memory_bytes: 1876
package main

import (
	"fmt"
	"strings"
)

func main() {

	var n, k int
	var s string
	fmt.Scan(&n, &s, &k)

	textList := strings.Split(s, "")
	targetString := textList[k-1]

	var newStrings string
	for _, val := range textList {
		if targetString == val {
			newStrings += val
		} else {
			newStrings += "*"
		}
	}

	fmt.Println(newStrings)
}


Measured memory_bytes: 640
from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[0]*n
dp=[float("inf")]*n
def f(c,d):
    h=bl(dp,a[c])
    g=dp[h]
    dp[h]=min(dp[h],a[c])
    b[c]=bl(dp,float("INF"))
    for i in t[c]:
        if i!=d:f(i,c)
    dp[h]=g
f(0,-1)
for i in b:
    print(i)


Measured memory_bytes: 224816
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

ll mod_pow(ll x,ll n,ll mod){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
int a[100005];
int main()
{
	int n;
	ll mod=1000000000+7;
	while(~scanf("%d",&n)){
		for(int i=0;i<n;i++)
			scanf("%d",&a[i]);
		sort(a,a+n);
		int flag=1;
		if(n%2==1){
			if(n==1){
				if(a[0]==0){
					
				}else{
					flag=0;
				}
			}
			for(int i=1;i<n;i++){
				if(i%2==1){
					if(a[i]==a[i-1]+2){
						
					}else{
						flag=0;
					}
				}else{
					if(a[i]==a[i-2]+2){
						
					}else{
						flag=0;
					}
				}
			}
		}else{
			if(a[0]!=a[1]) flag=0;
			if(a[0]!=1) flag=0;
			for(int i=2;i<n;i++){
				if(i%2==0){
					if(a[i]==a[i-1]+2){
						
					}else{
						flag=0;
					}
				}else{
					if(a[i]==a[i-2]+2){
						
					}else{
						flag=0;
					}
				}
			}
			
		}
		ll l=n/2;
		if(flag==0){
			printf("0\n");
		}else{
			printf("%lld\n",mod_pow(2,l,mod));
			
			
			
		}
	}
	
	return 0;
}

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

int main() {
int  n,d,a,b;
cin >> n >> d;
vector<vector<int>> x(n);
rep(i,n){
  vector<int> y(d);
  rep (j,d){
    cin>>a;
    y[j]=a; 
  }
  x[i]=y;
}
int sum=0;
rep(i,n-1){
   rep2(j,i+1,n) {
   a=0;
      rep(k,d){
         b=abs(x[i][k]-x[j][k]); 
         a+=b*b;
      } 
      double c=sqrt(a);
      if(c==floor(c))sum++;
   }
}
cout<<sum;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1e9+7LL;

int N, M, Q;
ll ans = 0;

void dfs(vector<int> A, vector<int> a, vector<int> b, vector<int> c, vector<int> d){
  	int s = A.size();
    if(s==N){
        ll score = 0;
        rep(i, Q) if(A.at(b.at(i)-1)-A.at(a.at(i)-1)==c.at(i)) score += d.at(i);
        ans = max(ans, score);
        return;
    }
    A.push_back(A.back());
    while(A.back() <= M){
        dfs(A, a, b, c, d);
        A.back()++;
    }
}

int main() {
    cin >> N >> M >> Q;
  	vector<int> a(Q);
  	vector<int> b(Q);
  	vector<int> c(Q);
  	vector<int> d(Q);
    rep(i, Q) cin >> a.at(i) >> b.at(i) >> c.at(i) >> d.at(i);
    for(int st = 1; st <= M; st++) dfs(vector<int>(1,st), a, b, c, d);
    cout << ans << endl;
}

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

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

void solve() {

}

int main() {
  int s,w;
  cin >> s >> w;
  if( w >= s ) puts("unsafe");
  else puts("safe");
  return 0;
}


Measured memory_bytes: 3632
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner stdIn = new Scanner(System.in);
		
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		
		if((a + b) % 2 == 0)
			System.out.println((a + b)/2);
		else if ((a + b) % 2 == 1)
			System.out.println((a + b + 1) / 2);

	}

}


Measured memory_bytes: 19924
/*
 *Author : zsenshi
 DP 
 */
#include <bits/stdc++.h> //Only for gcc compilers
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define dg(x) cout << #x << ":"<<x<<endl
#define dg2(x,y) cout<<#x<<':'<<x<<' '<<#y<<':'<<y<<endl
#define dg3(x,y,z) cout<<#x<<':'<<x<<' '<<#y<<':'<<y<<' '<<#z<<':'<<z<<endl
#define dg4(x,y,z,zz) cout<<#x<<':'<<x<<' '<<#y<<':'<<y<<' '<<#z<<':'<<z<<' '<<#zz<<':'<<zz<<endl
#define rep(i,begin,end) for(__typeof(end) i = (begin)-((begin) > (end)); i != (end) - ((begin) > (end)); i += 1-2*((begin) > (end)))
using namespace std;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vector<pii>> vvpi;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  int h[n];
  int dp[n];
  for(int i = 0; i < n; i++){
    cin >> h[i];
    dp[i] = INT_MAX;
  }
  dp[0] = 0;
  for(int i = 0; i < n; i++){
    for(int val : {i-1,i-2}){
      if(val >= 0){
        dp[i] = min(dp[i],dp[val] + abs(h[i] - h[val]));
      }
    }
  }
  cout << dp[n-1] << "\n"; 
   
}


Measured memory_bytes: 1024
import java.util.ArrayList;
import java.util.Scanner;




class Main{


	static	ArrayList<Integer> one ;
	static	ArrayList<Integer> two ;
	static	ArrayList<Integer> three ;
	static	ArrayList<Integer> four ;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		int[] a = new int[n];
		
		for(int i = 0;i < n;i++){
			a[i] = sc.nextInt();
		}

		long sumx  = 0;
		long sumy  = 0;

		long ansx  = 0;
		long ansy  = 0;



		for(int i = 0;i < n;i++){					//偶数番目で正
			if(i % 2 == 0){
				if(sumx + a[i] > 0){
					sumx += a[i];
				}else{
					ansx += 1 + Math.abs(sumx + a[i]);			//カウントを増やす
					sumx = 1;
				}
			}else{
				if(sumx + a[i] < 0){
					sumx += a[i];
				}else{
					ansx += 1 + Math.abs(sumx + a[i]);			//カウントを増やす
					sumx = -1;
				}
			}

		}
		for(int i = 0;i < n;i++){					//偶数番目で負
			if(i % 2 == 0){
				if(sumy + a[i] < 0){
					sumy += a[i];
				}else{
					ansy += 1 + Math.abs(sumy + a[i]);			//カウントを増やす
					sumy = -1;
				}
			}else{
				if(sumy + a[i] > 0){
					sumy += a[i];
				}else{
					ansy += 1 + Math.abs(sumy + a[i]);			//カウントを増やす
					sumy = 1;
				}

			}
		}

			System.out.println(Math.min(ansx, ansy));




		}

	}

	class Pair implements Comparable{
		Character from;
		int end;
		@Override
		public int compareTo(Object other) {
			Pair otherpair = (Pair)other;

			return end - otherpair.end;
		}
	}




Measured memory_bytes: 50900
#include<stdio.h>
#include<string.h>
using namespace std;

int main(){
	char c[3];
	int ans = 700;
	scanf("%s", c);
	if(c[0] == 'o') ans += 100;
	if(c[1] == 'o') ans += 100;
	if(c[2] == 'o') ans += 100;
	printf("%d\n", ans);

}

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

ll ch[60];
int main() {
	ll n;
	cin>>n;
	ll cnt=n*(n-1)/2;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		for(ll j=0;j<60;j++){
			ch[j]+=(now%2);
			now/=2;
		}
	}
	ll ans=0,kei=1;
	for(ll i=0;i<60;i++){
		//cout <<ans<<endl;
		ll su=(cnt-(ch[i])*(ch[i]-1)/2-(n-ch[i])*(n-ch[i]-1)/2);
		su%=inf;
		ans+=kei*su;
		ans%=inf;
		kei*=2;
		kei%=inf;
	}
	cout <<ans;
	// your code goes here
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

vector<string> f(int d, int n, int& res) {
	if (d == 1) {
		return vector<string> {"3", "5", "7"};
	}
	vector<string> vs, ret = f(d - 1, n, res);
	for (auto s : ret) {
		vs.push_back(s);
		vs.back().push_back('3');
		vs.push_back(s);
		vs.back().push_back('5');
		vs.push_back(s);
		vs.back().push_back('7');
	}
	for (auto s : vs) {
		int d3 = 0, d5 = 0, d7 = 0;
		for (auto ss : s) {
			if (ss == '3') d3++;
			if (ss == '5') d5++;
			if (ss == '7') d7++;
		}
		if (d3 && d5 && d7 && stoll(s) <= n) res++;
	}
	return vs;
}

int main() {
	int n;
	cin >> n;
	int res = 0;
	int l = to_string(n).size();
		f(l, n, res);
	
	cout << res << endl;
}


Measured memory_bytes: 4576
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = sorted(li())
half = A[-1]//2

ind = bisect.bisect_left(A, half)

if (N%2==0 and A[ind]!=half) or (N%2==1 and A[ind]-half > 1):
    if ind > 0 and half - A[ind-1] <= A[ind] - half:
        ind -= 1

print(A[-1], A[ind])

Measured memory_bytes: 14136
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
//syakyou
vector<vector<pair<int,int > > > G;
vector<int> ans;
void dfs(int v,int c, int p){
  int k=1;
  for(int i=0; i<G[v].size(); i++){
    int u=G[v][i].first,ei=G[v][i].second;
    if(u==p) continue;
    if(k==c) k++;
    ans[ei]=k;
    k++;
    
    dfs(u,ans[ei],v);
  }
}
int main(int argc, char *argv[]){
  int N;
  cin>>N;
  G.resize(N);
  for(int i=0; i<N-1; i++){
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    G[a].push_back(make_pair(b,i));
    G[b].push_back(make_pair(a,i));
  }
  ans.resize(N-1);
  dfs(0,-1,-1);
  int mx=-1;
  for(int i=0; i<N-1; i++){
    mx=max(mx,ans[i]);
  }
  cout<<mx<<endl;
  for(int i=0; i<N-1; i++){
    cout<<ans[i]<<endl;
  }
  return 0;
}


Measured memory_bytes: 8320
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		char[] c = s.toCharArray();
		char[] start_black = new char[s.length()];
		char[] start_white = new char[s.length()];
		int bCount = 0;
		int wCount = 0;
		for(int i = 0; i <s.length(); i++) {
			if(i%2==0) {
				start_black[i] = '0';
				start_white[i] = '1';
			}
			else {
				start_black[i] = '1';
				start_white[i] ='0';
			}
		}
		for(int i = 0; i < s.length(); i++) {
			if(c[i] != start_black[i]) {
				bCount++;
			}
			if(c[i] != start_white[i]) {
				wCount++;
			}
		}
		System.out.println(Math.min(wCount, bCount));
	}
}


Measured memory_bytes: 27220
#include <stdio.h>

// a: 500, b: 100, c: 50
int solv(int a, int b, int c, int x) {
  int i, j, k, count = 0, y;

  for (i = 0; i <= a; i++) {
    for (j = 0; j <= b; j++) {
      y = i * 500 + j * 100;
      if (x - y < 0) {
        break;
      }
      k = (x - y) / 50;
      if (k <= c) {
        count++;
      }
    }
  }

  return count;
}

int main(int argc, char **argv) {
  int a, b, c, x;

  while (scanf("%d %d %d %d", &a, &b, &c, &x) != EOF) {
    printf("%d\n", solv(a, b, c, x));
  }

  return 0;
}


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

typedef long long ll;

ll h;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> h;

    ll res = 0;
    ll num = 1;
    while (h > 0) {
        res += num;
        h /= 2;
        num *= 2;
    }

    cout << res << endl;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAX_DEGIT 60
long long dp[100][2];

int main() {
    int N;
    long long K;
    cin >> N >> K;
    vector<long long> A(N);
    for(int i=0; i<N; ++i) cin >> A[i];
    
    memset(dp, -1, sizeof dp);
    dp[0][0] = 0;
    for(int d=0; d<MAX_DEGIT; ++d) {
        long long mask = 1LL << (MAX_DEGIT - d - 1);

        int cnt = 0;
        for(int i=0; i<N; ++i) if(A[i] & mask) ++cnt;

        long long cost0 = cnt * mask;
        long long cost1 = (N - cnt) * mask;

        if(dp[d][1] != -1) {
            dp[d+1][1] = max(dp[d+1][1], dp[d][1] + max(cost0, cost1));
        }
        if(dp[d][0] != -1) {
            if(K & mask) dp[d+1][1] = max(dp[d+1][1], dp[d][0] + cost0);
            if(!(K & mask)) dp[d+1][0] = max(dp[d+1][1], dp[d][0] + cost0);
            else dp[d+1][0] = max(dp[d+1][1], dp[d][0] + cost1);
        }
    }
    cout << max(dp[MAX_DEGIT][0], dp[MAX_DEGIT][1]) << endl;
}

Measured memory_bytes: 1024
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b
n=I()
lis=[I() for i in range(n)]
u=1
for i in range(n):
    u=lcm(u,lis[i])
print(u)


Measured memory_bytes: 3316
// https://atcoder.jp/contests/

#include <iostream>
using namespace std;

int main()
{
  /* Magic word */
  cin.tie(0);
  ios::sync_with_stdio(false);
  /* ---------- */

  double t, x;

  cin >> t >> x;

  cout << t / x << '\n';

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long int int64;


const int N = (int) 1e5 + 100;

vector <int> ch[N];
int k;

struct Ans
{
    vector <int> v;

    Ans() : v({0}) {}

    void eprint()
    {
        for (int i = 0; i < min(k + 1, (int) v.size()); i++)
            eprintf("[%d] %d, ", i, v[(int) v.size() - 1 - i]);
        eprintf("\n");
    }
};


Ans dp[N];


int merge(int a, int b)
{
    if ((int) dp[a].v.size() < (int) dp[b].v.size())
        swap(a, b);

    for (int i = 0; i < (int) dp[b].v.size(); i++)
        dp[a].v[(int) dp[a].v.size() - 1 - i] += dp[b].v[(int) dp[b].v.size() - 1 - i];

    return a;
}

int goUp(int a)
{
    dp[a].v.push_back(1);
    if ((int) dp[a].v.size() >= k + 1)
        dp[a].v.back() += dp[a].v[(int) dp[a].v.size() - k - 1];

    int i = 2;
    while (i <= (int) dp[a].v.size() && dp[a].v[(int) dp[a].v.size() - i] > dp[a].v.back())
    {
        dp[a].v[(int) dp[a].v.size() - i] = dp[a].v.back();
        i++;
    }

    return a;
}

int solve(int v)
{
    int cur = v;
    for (int to : ch[v])
    {
        int nx = solve(to);
        cur = merge(cur, nx);
    }
    //eprintf("(%d): ", v); dp[cur].eprint();
    if (v != 0)
        cur = goUp(cur);
    //eprintf("(%d'): ", v); dp[cur].eprint();
    return cur;
}

int a[N];

int main(int,  char **)
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

    int n;
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        a[i]--;
    }

    for (int i = 1; i < n; i++)
        ch[a[i]].push_back(i);

    int id = solve(0);

    int ans = dp[id].v[max(0, (int) dp[id].v.size() - k - 1)];

    if (a[0] != 0)
        ans++;

    printf("%d\n", ans);

	return 0;
}




Measured memory_bytes: 16896
h=int(input())
for i in range(0, h):
	n=list(map(int, input().split()))#ファイルの読み込み --.py <--.txt
	a=n[0]
	b=n[1]
	c=n[2]
	if a**2+b**2==c**2 or b**2+c**2==a**2 or c**2+a**2==b**2:
		print("YES")
	else:
		print("NO")


Measured memory_bytes: 5596
#include<iostream>
#include<string>
#include<regex>

using namespace std;

int main() {
    string A, B, S;

    cin >> A >> B >> S;

    smatch smatched;
    string sregex = "^[0-9]{" + A + "}-[0-9]{" + B + "}$";

    if (regex_search(S, smatched, regex(sregex))) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import math
ans = 0
N = int(input())
if N <= 5:
  for i in range(N):
    for j in range(N):
        for k in range(N):
            ans += math.gcd(math.gcd(i+1,j+1),math.gcd(j+1,k+1))
else:
    for i in range(N):
        ans += i+1
    for i in range(N-1):
        for j in range(i+1,N):
            ans += 6*math.gcd(i+1,j+1)
    for i in range(N-2):
        for j in range(i+1,N-1):
            for k in range(j+1,N):
                ans += 6*math.gcd(math.gcd(i+1,j+1),math.gcd(j+1,k+1))
print(ans)

Measured memory_bytes: 9220
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

using namespace std;
typedef pair<int, int> P;
int N,K;
int main(){
	cin>>N>>K;
	set<P> mp;
	{
		map<int,int> tem;
		REP(i,N){
			int a;
			cin>>a;
			tem[a]++;
		}
		for(auto ite:tem){
			mp.insert(make_pair(ite.second,ite.first));
		}
	}
	int ans=0;
	auto ite=mp.begin();
	REP(i,(int)mp.size()-K){
		ans+=ite->first;
		ite++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 18944
#include <stdio.h>
#include <iostream>

using namespace std;

int main(){

	int N, counter=0;
	string str;

	cin >> N;

	int a[N];
	for(int i=0;i<N;i++){
		cin >> a[i];
	}

	while(1){
		for(int i=0;i<N;i++){
			if(a[i]%2==0){
				a[i] = a[i]/2;
			}
			else{
				cout << counter << endl;
				return 0;
			}
		}
		counter++;
	}
	return 0;
}

Measured memory_bytes: 256
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1

N,K,S = mint()
A = [S]*K+[10**9-(S==10**9)]*(N-K)
lprint(A,' ')

Measured memory_bytes: 77788
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int count=0;
		while(sc.hasNext()){
			char[] c=sc.next().toCharArray();
			boolean flag=true;
			for(int i=0;i<c.length/2;i++){
				if(c[i]!=c[c.length-i-1]){
					flag=false;
					break;
				}
			}
			if(flag){
				count++;
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 17136
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define ALL(n) begin(n),end(n)

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

    vector<int> a(n);
    REP(i,n){
        cin>>a[i];
    }

    if((n-1)%(k-1)==0){
        cout<<(n-1)/(k-1)<<endl;
    }else{
        cout<<(n-1)/(k-1)+1<<endl;
    }    
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
string s;
bool loor[200100];
int co=0;
int main(){
	cin>>n;
	cin>>s;
	if(s[0]=='W'||s[2*n-1]=='W'){
		cout<<0<<endl;
		return 0;
	}
	loor[0]=false;
	co--;
	FOR(i,1,2*n){
		if(s[i-1]==s[i]){
			loor[i]=!loor[i-1];
		}else{
			loor[i]=loor[i-1];
		}
		if(loor[i])co++;
		else co--;
	}
	if(co!=0){
		cout<<0<<endl;
		return 0;
	}
	ll ans=1;
	ll lr_count=0;
	REP(i,2*n){
		if(loor[i]==0){
			lr_count++;
		}else{
			ans*=lr_count;
			ans%=MOD;
			lr_count--;
			if(lr_count<0){
				cout<<0<<endl;
				return 0;
			}
		}
	}
	FOR(i,1,n+1){
		ans*=i;
		ans%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 772
#include <iostream>

using namespace std;

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

  int res = 0;
  int mn = 200001;
  for (int n = 0; n < N; ++n) {
    int A;
    cin >> A;
    if (A < mn) {
      ++res;
      mn = A;
    }
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 3576
// {{{ Boilerplate Code <--------------------------------------------------
// vim:filetype=cpp:foldmethod=marker:foldmarker={{{,}}}

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define ALL(A)     (A).begin(), (A).end()

using namespace std;

// }}}

int main(){
	int n;

	vector <double> d;

	cin>>n;

	FOR(i,0,n){
		int tmp;
		cin>>tmp;
		d.push_back(tmp);
	}

	vector <double> pos;

	double ret = 0.0;

	FOR(i,0,n){
		double curpos = 0.0;

		curpos=max(curpos,d[i]);

		FOR(j,0,i){
			double e1=d[i]-d[j];
			double e2=d[i]+d[j];
			double e3=sqrt(e2*e2-e1*e1);

			curpos=max(curpos,pos[j]+e3);
		}
		pos.push_back(curpos);

		ret=max(ret,curpos+d[i]);
	}

	cout<<setprecision(15)<<ret<<endl;

}

Measured memory_bytes: 1296
fun main(args: Array<String>) {
    val s = readLine() ?: return
    fun isPalindrome(value: String): Boolean {
        var i = 0
        var j = value.length - 1
        while (i <= j) {
            if (value[i] != value[j]) {
                return false
            }
            i++
            j--
        }
        return true
    }

    val n = s.length
    val s1 = s.substring(0, (n - 1) / 2)
    val s2 = s.substring((n + 3) / 2 - 1, n)

    System.err.println(s1)
    System.err.println(s2)

    if (isPalindrome(s) && isPalindrome(s1) && isPalindrome(s2)) {
        println("Yes")
    } else {
        println("No")
    }
}


Measured memory_bytes: 33476
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100005;
const int D=1e9;

ll tab[N];

bool spr(int n,ll A,ll B,ll v);

 int main()
 {
	int n,i;
	ll A,B;
	scanf("%d%lld%lld",&n,&A,&B);

	for(i=1;i<=n;i++)
	{
		scanf("%lld",&tab[i]);
	}

	ll a,b,v;
	a=0;
	b=D;
	
	while(a<b)
	{
		v=(a+b)/2;

		if(spr(n,A,B,v)) b=v;
		else a=v+1;
	}

	printf("%lld\n",a);
 }
/////
 bool spr(int n,ll A,ll B,ll v)
 {
	ll tmp,il;
	il=0;
	for(int i=1;i<=n;i++)
	{
		tmp=tab[i]-B*v;
		if(tmp>0)
		{
			il+=tmp/(A-B);
			if(tmp%(A-B)!=0) il++;
		}
	}


	if(il>v) return false;
	return true;	
 }



Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include<iomanip>
#include<functional>

using namespace std;
typedef long long ll;

// a と b の最大公約数を返す関数
long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}



int main() {
    int A, B, M;
    cin >> A >> B >> M;
    vector<int> a(A);
    vector<int> b(B);
    int minA = 1e6, minB = 1e6;
    for (int i = 0; i < A; i++) {
        cin >> a[i];
        minA = min(minA, a[i]);
    }
    for (int i = 0; i < B; i++) {
        cin >> b[i];
        minB = min(minB, b[i]);
    }
    int ans = minA + minB;
    for (int i = 0; i < M; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        ans = min(ans, a[x - 1] + b[y - 1] - c);
    }
    cout << ans << endl;
}


Measured memory_bytes: 4048