akhauriyash/Code-Regression huggingface dataset:
package main

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

var sc *bufio.Scanner

const BufferSize = 1024

func nextInt() int {
	if !sc.Scan() {
		panic(nil)
	}
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

var production bool

func debugf(format string, v ...interface{}) {
	if !production {
		fmt.Printf(format, v...)
	}
}

func answer(reader io.Reader, writer io.Writer) {
	sc = bufio.NewScanner(reader)
	buf := make([]byte, BufferSize)
	sc.Buffer(buf, 1e+6)
	sc.Split(bufio.ScanWords)
	n := nextInt()
	a := make([]int, n+1)
	b := make([]int, n)

	for i := range a {
		a[i] = nextInt()
	}
	for i := range b {
		b[i] = nextInt()
	}
	ans := 0

	debugf("before: %v\n", a)
	for i := range b {
		if a[i] <=  b[i] {
			ans += a[i]
			b[i] -= a[i]
			a[i] = 0
			if a[i+1] <=  b[i] {
				ans += a[i+1]
				b[i] -= a[i+1]
				a[i+1] = 0
			} else {
				ans += b[i]
				a[i+1] -= b[i]
			}
		} else {
			ans += b[i]
			a[i] -= b[i]
		}
	}
	debugf("after: %v\n", a)

	_, _ = fmt.Fprintf(writer, "%d", ans)
}

func main() {
	production = true
	answer(os.Stdin, os.Stdout)
}


Measured memory_bytes: 4736
#include<cstdio>
#define mod 1000000007
typedef long long ll;
using namespace std;

ll kai[100001],inv[100001];
ll gyaku(ll x){
    ll res=1;
    ll y=x;
    for(int i=0;i<30;i++){
        if(((1<<i)&(mod-2))){
            res*=y;
            res%=mod;
        }
        y=y*y;
        y%=mod;
    }
    return res;
}

int main(){
    ll ans;
    int n,a[100001],l,r,f[100001]={};
    scanf("%d",&n);
    for(int i=0;i<n+1;i++){
        scanf("%d",&a[i]);
        if(f[a[i]]){
            r=i;
        }
        f[a[i]]=1;
    }
    for(int i=0;i<r;i++){
        if(a[i]==a[r]){
            l=i;
        }
    }
    kai[0]=1;
    for(int i=1;i<=n+1;i++){
        kai[i]=kai[i-1]*i;
        kai[i]%=mod;
    }
    inv[n+1]=gyaku(kai[n+1]);
    for(int i=n;i>=0;i--){
        inv[i]=inv[i+1]*(i+1);
        inv[i]%=mod;
    }
    printf("%d\n",n);
    for(int i=2;i<=n+1;i++){
        ans=kai[n+1];
        ans*=inv[i];
        ans%=mod;
        ans*=inv[n+1-i];
        ans%=mod;
        if(n+1-(r-l)>=i){
            ans-=kai[n-r+l]*inv[i-1]%mod*inv[n-r+l-i+1]%mod;
            ans+=mod;
            ans%=mod;
        }
        printf("%lld\n",ans);
    }
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

const int MOD = 1000000007;

int main() {
    ll a, b;
    cin >> a >> b;
    ll c = b - a;
    ll sum = 0;
    rep(i, c + 1) sum += i;
    cout << sum - b << endl;
}

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

int main() {
  int H,W;
  cin >> H >> W;
  vector<vector<char>> S(H,vector<char>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin >> S.at(i).at(j);
    }
  }
  
  vector<int> max(H*W);
  vector<vector<int>> dist(H*W,vector<int>(H*W,-1));
  queue<int> que;
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(S.at(i).at(j)!='.') continue;
      dist.at(i*W+j).at(i*W+j)=0;
      que.push(i*W+j);
      
      while(!que.empty()){
        int v=que.front();
        int J=v%W;
        int I=(v-J)/W;
        que.pop();
        
          if(I!=0){
            if(S.at(I-1).at(J)=='.' && dist.at(i*W+j).at(W*(I-1)+J)==-1){
              dist.at(i*W+j).at(W*(I-1)+J)=dist.at(i*W+j).at(W*I+J)+1;
              que.push(W*(I-1)+J);
            }
          }
          if(I!=H-1){
            if(S.at(I+1).at(J)=='.' && dist.at(i*W+j).at(W*(I+1)+J)==-1){
              dist.at(i*W+j).at(W*(I+1)+J)=dist.at(i*W+j).at(W*I+J)+1;
              que.push(W*(I+1)+J);
            }
          }
          if(J!=0){
            if(S.at(I).at(J-1)=='.' && dist.at(i*W+j).at(W*I+J-1)==-1){
             dist.at(i*W+j).at(W*I+J-1)=dist.at(i*W+j).at(W*I+J)+1;
             que.push(W*I+J-1);
            }
          }
          if(J!=W-1){
            if(S.at(I).at(J+1)=='.' && dist.at(i*W+j).at(W*I+J+1)==-1){
             dist.at(i*W+j).at(W*I+J+1)=dist.at(i*W+j).at(W*I+J)+1;
             que.push(W*I+J+1);
            }
          }  
      }
      
      sort(dist.at(i*W+j).begin(),dist.at(i*W+j).end());
      reverse(dist.at(i*W+j).begin(),dist.at(i*W+j).end());
      max.at(i*W+j)=dist.at(i*W+j).at(0);
      
    }
  }
  sort(max.begin(),max.end());
  reverse(max.begin(),max.end());
  cout << max.at(0) << endl;
}

Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
long long A, B, C, N, M, K, T, E[4009], U = 0; vector<long long>V;
int main() {
	cin >> N >> M >> K >> A >> B >> C >> T;
	for (int i = 1; i <= M; i++) cin >> E[i];
	for (int i = 1; i < M; i++) {
		long long rem = T - (E[i] - 1) * B, cx = E[i], cnt = 0; if (rem < 0)continue;
		while (true) {
			long long D = rem / A + 1, F = cx + D; F = min(F, E[i + 1]); D = F - cx;
			if (cnt >= 1)V.push_back(D); else U += D;
			rem -= D*C; cx += D; if (cx >= E[i + 1] || D == 0 || rem < 0LL || cnt > K - M)break; cnt++;
		}
	}
	if ((N - 1)*B <= T)U++;
	sort(V.begin(), V.end(), greater<long long>());
	for (int i = 0; i < min((long long)V.size(), K - M); i++)U += V[i];
	cout << U - 1 << endl;
	return 0;
}

Measured memory_bytes: 6960
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pll;
const int inf = 3000;
const int maxSize=4000;
int n, k;
vector<vector<int> > g(maxSize, vector<int>());
vector<int> subtree;
vector<vector<int> > dp(maxSize, vector<int>());
vector<vector<int> > minn(maxSize, vector<int>());// minn[v][dep] = min over dp[v][0], ..., dp[v][dep]
void dfs(int v, int p)
{
    subtree[v] = 1;
    vector<int> sons;
    for (int to : g[v]) {
        if (to != p) {
            dfs(to, v);
            sons.pb(to);
            subtree[v] += subtree[to];
        }
    }
    dp[v][0] = subtree[v] - 1;
    for (int dep = 1; dep < k; ++dep) {
        int x = min(dep - 1, k - dep - 1);
        int s = 0;
        for (int son : sons) {
            s += minn[son][x];
        }
        for (int son : sons) {
            dp[v][dep] = min(dp[v][dep], dp[son][dep - 1] + s - minn[son][x]);
        }
    }
    int s = subtree[v] - 1;
    for (int son : sons) {
        dp[v][k] = min(dp[v][k], dp[son][k - 1] + s - subtree[son]);
    }
    minn[v][0] = dp[v][0];
    for (int dep = 1; dep <= k; ++dep) {
        minn[v][dep] = min(minn[v][dep - 1], dp[v][dep]);
    }
}

int main()
{

    cin >> n >> k;
    g.resize(n);
    dp.resize(n);
    subtree.resize(n);
    minn.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].pb(v);
        g[v].pb(u);
    }

    for (int i = 0; i < n; ++i) {
        dp[i].assign(k + 1, inf);
        minn[i].resize(k + 1);
    }

    dfs(0, 0);
    /*for (int v = 0; v < n; ++v) {
        for (int dep = 0; dep <= k; ++dep) {
            cout << v << " " << dep << " " << dp[v][dep] << "\n";
        }
    }*/
    int ans = inf;
    for (int dep = 0; dep <= k; ++dep) {
        ans = min(ans, dp[0][dep]);
    }
    for (int v = 1; v < n; ++v) {
        for (int dep = 0; dep <= k; ++dep) {
            ans = min(ans, dp[v][dep] + n - subtree[v]);
        }
    }
    cout << ans << "\n";

}

Measured memory_bytes: 35460
public class Main {
	
	public void run(java.util.Scanner sc, java.io.PrintStream out) {
		PROBLEM:
		for (;;) {
			final int n = sc.nextInt();
			if (n == 0) break ;
			final int[] c = new int[n];
			for (int i = 0; i < n; ++i)
				c[i] = sc.next().charAt(0) - 'A';
			
			final int[] d = new int['Z' - 'A' + 1];
			for (int i = 0; i < n; ++i) {
				d[c[i]] += 1;
				
				for (int k = 0; k < d.length; ++k) {
					boolean flag = true;
					for (int j = 0; j < d.length; ++j) {
						if (j == k) continue ;
						flag = flag && (d[j] + (n - i - 1) < d[k]);
					}
					if (flag) {
						out.println(String.valueOf((char)('A' + k)) + " " + (i + 1));
						continue PROBLEM;
					}
				}
			}
			out.println("TIE");
		}
	}
	
	public static void main(String[] args) {
		try (java.util.Scanner sc = new java.util.Scanner(System.in)) {
			(new Main()).run(sc, System.out);
		}
	}

}

Measured memory_bytes: 47348
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<bitset>
#include<iomanip>
#include<vector>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;



int cnt;
void insertionSort(int *A,int n,int g){
  for(int i=g;i<n;i++){
    int v=A[i];
    int j=i-g;
    while(j>=0&&A[j]>v){
      A[j+g]=A[j];
      j-=g;
      cnt++;
    }
    A[j+g]=v;
  }
}
void shellSort(int *A,int n){
  cnt=0;
  int r=1;
  vector<int> G;
  while(r<=n){
    G.push_back(r);
    r*=2;
  }
  int m=G.size();
  reverse(G.begin(),G.end());
  cout<<m<<endl;
  for(int i=0;i<m;i++) cout<<G[i]<<" \n"[i==m-1];
  for(int i=0;i<m;i++) insertionSort(A,n,G[i]);
  cout<<cnt<<endl;
}
signed main(){
  int n;
  cin>>n;
  int A[n];
  for(int i=0;i<n;i++) cin>>A[i];
  shellSort(A,n);
  for(int k=0;k<n;k++) cout<<A[k]<<endl;
  return 0;
}


Measured memory_bytes: 6996
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

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

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
#define MOD (1e9+7)
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")



/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}
int main() { 
  int N;cin>>N;
  vector<int> A(N),a(N);
  for(int i = 0; N > i; i++){
    cin>>A[i] >> a[i];
    a[i] = 10-a[i];
  }
  double B[N+1];
  B[0] = 1.0;
  for(int i = 1; N >= i; i++){
    B[i] = B[i-1]*a[i-1]/10;
  }
  int Q;cin>>Q;
  loop(Q){
    int l,r;cin>>l>>r;
    auto L = lower_bound(A.begin(),A.end(),l) - A.begin();
    auto R = lower_bound(A.begin(),A.end(),r) - A.begin()-1;
    cout << fixed << setprecision(10);
    if(L > R){
      cout<< (double)1000000000.0 << endl;
    }else{
      double G = 1000000000.0 / B[L] * B[R+1];
      cout << G << endl;
    }

  }

}


Measured memory_bytes: 4384
#ifdef loc
    #include "loc_debug.h"
#else
    #include <bits/stdc++.h>
    #define pr(...)
    #define pra(a,n)
    #define praa(a,n,m)
    #define prl()
#endif
using namespace std;

typedef long long ll;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define sz(a) int(a.size())
const int N = 40065;

int w[N], s[N], a[N];
ll f[1005][N], v[N];

struct Sort {
    bool operator()(int x, int y) {
        if(w[x] + s[x] != w[y] + s[y]) {
            return w[x] + s[x] < w[y] + s[y];
        }
        return x < y;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    rep(i, 1, n + 1) {
        cin >> w[i] >> s[i] >> v[i];
        a[i] = i;
    }
    sort(a + 1, a + n + 1, Sort());
    rep(i, 1, n + 1) {
        rep(j, 0, int(N)) {
            f[i][j] = f[i - 1][j];
        }
        int x = a[i];
        rep(j, 0, s[x] + 1) {
            f[i][j + w[x]] = max(f[i][j + w[x]], f[i - 1][j] + v[x]);
        }
    }
    ll ans = 0;
    rep(i,0,(int)N) {
        ans = max(ans,f[n][i]);
    }
    cout << ans<<endl;
    return 0;
}

Measured memory_bytes: 313344
N,K = [int(x) for x in input().split()]
h = [int(input()) for _ in range(N)]
i=0
hdif = 1000000000000
h.sort()
while(i+K-1<N):
    hdif=min(h[i+K-1]-h[i],hdif)
    i+=1
print(hdif)


Measured memory_bytes: 7488
def show(lists):
    for i in range(len(lists)):
        if i != len(lists) - 1:
            print(lists[i], end=' ')
        else: print(lists[i])

length = int(input())
List = list(map(int, input().split()))

for i in range(length):
    term = List[i]
    j = i - 1
    while j >= 0 and List[j] > term: #ここで変数をiからjに置き換えないといけない、別のループをするから
        List[j+1] = List[j]
        List[j] = term
        j = j - 1
    show(List)


Measured memory_bytes: 5984
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;

int main() {
	int m, n;
	cin >> m >> n;
	cout << m * n << endl;
}

Measured memory_bytes: 3624
#include<iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include<bitset>
#include<string>
#include <deque>
#include<queue>
#include <iomanip>
#include<map>
#include<type_traits>

using namespace std;
long long int dp[1000009][5];
int main(){
	string S;
	cin >> S;
	dp[0][0] = 1;
	for (long long int i = 0; i <S.size(); i++) {
			if (S[i] == 'A') {
				dp[i + 1][0] = dp[i][0]%1000000007;
				dp[i + 1][1] = (dp[i][0] + dp[i][1]) % 1000000007;
				dp[i + 1][2] = dp[i][2] % 1000000007;
				dp[i + 1][3] = dp[i][3] % 1000000007;
			}
			else if (S[i] == 'B') {
				dp[i + 1][0] = dp[i][0] % 1000000007;
				dp[i + 1][1] = dp[i][1] % 1000000007;
				dp[i + 1][2] = (dp[i][2] + dp[i][1] )% 1000000007;
				dp[i + 1][3] = dp[i][3] % 1000000007;
			}
			else if (S[i] == 'C') {
				dp[i + 1][0] = dp[i][0] % 1000000007;
				dp[i + 1][1] = dp[i][1] % 1000000007;
				dp[i + 1][2] = dp[i][2] % 1000000007;
				dp[i + 1][3] = (dp[i][3] + dp[i][2]) % 1000000007;
			}
			else {
				dp[i + 1][0] = 3*dp[i][0] % 1000000007;
				dp[i + 1][1] = (3 * dp[i][1] + dp[i][0]) % 1000000007;
				dp[i + 1][2] = (3 * dp[i][2] + dp[i][1] )% 1000000007;
				dp[i + 1][3] = (3 * dp[i][3] + dp[i][2] )% 1000000007;
			}
		
	}
	cout << dp[S.size()][3] % 1000000007 << endl;
}



Measured memory_bytes: 4608
#include <cstdio>
#include <cstdint>
#include <cctype>
#include <cassert>
#include <vector>
#include <algorithm>
#include <string>

int parse_int(std::string const& s, size_t& i) {
  int res = s[i]-'0';
  while (isdigit(s[++i]))
    res = res*10 + s[i]-'0';
  return res;
}

int apply(int lhs, char op, int rhs) {
  if (op == '+') return lhs + rhs;
  if (op == '-') return lhs - rhs;
  if (op == '*') return lhs * rhs;
  if (op == '/') return lhs / rhs;
  assert(false);
}

const std::vector<std::string> ops = {"+-", "*/"};
int parse(std::string const& s, size_t& i, size_t preced = 0) {
  if (ops.size() == preced) {
    if (isdigit(s[i])) return parse_int(s, i);
    if (s[i] == '(') {
      int res = parse(s, ++i, 0);
      assert(s[i] == ')');
      ++i;
      return res;
    }
    assert(false);
  }
  int res = parse(s, i, preced+1);
  while (i < s.length()) {
    char op = s[i];
    if (!std::count(ops[preced].begin(), ops[preced].end(), op)) break;
    res = apply(res, op, parse(s, ++i, preced+1));
  }
  return res;
}

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

  for (size_t i = 0; i < n; ++i) {
    char buf[1024];
    scanf("%s", buf);
    std::string s = buf;
    if (s.back() != '=') {
      printf("%s\n", s.c_str());
      continue;
    }

    size_t j = 0;
    printf("%d\n", parse(s, j));
  }
}



Measured memory_bytes: 2776
#include <bits/stdc++.h>
using namespace std;
 
int main() {
long long n;cin >> n ;
vector<long long> a(n);
for (long long i = 0; i < n; i++)
{
    cin >> a[i];
}
long long now=1;
for (long long i = 1; i < n+1; i++)
{

    now = a[now-1];
    if (now == 2)
    {
        cout << i << endl;
    return 0;    
    }
    
}
    cout << -1 << endl;
}

Measured memory_bytes: 4028
# -*- coding: utf-8 -*-
x, n = map(int, input().split())
if n != 0:
  p = list(map(int, input().split()))
  
  p.sort()
  x_plus = 0
  x_search = x
  for i in range(n):
    if p[i] == x_search:
      x_search += 1
      if i == n-1:
        x_plus = x_search
    elif p[i] > x_search:
      x_plus = x_search
      break
  p.sort(reverse=True)
  x_minus = 0
  x_search = x
  for i in range(n):
    if p[i] == x_search:
      x_search -= 1
      if i == n-1:
        x_minus = x_search
    elif p[i] < x_search:
      x_minus = x_search
      break
  if abs(x_plus - x) - abs(x_minus -x) >= 0:
    print(x_minus)
  else:
    print(x_plus)
else:
  print(x)

Measured memory_bytes: 9240
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep(i,n) rep2(i,0,n)
#define debug(x) cerr << x << endl
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
template<typename T> struct V : vector<T> { using vector<T>::vector; };
V() -> V<int>;
V(size_t) -> V<int>;
template<typename T> V(size_t, T) -> V<T>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
const int INF = 1<<30;
const ll LINF = 1LL<<61;
const ll MOD = 1000000007;

ll op(ll lh, ll rh) { return max(lh, rh); }
ll e() { return -1; }
int rh;
bool f(ll lh) { return lh < rh; }

int main()
{
    int n, q;
    cin >> n >> q;
    segtree<ll, op, e> seg(n);
    rep(i,n)
    {
        int a;
        cin >> a;
        seg.set(i,a);
    }
    rep(i,q)
    {
        int t;
        cin >> t;
        if(t == 1)
        {
            int p, x;
            cin >> p >> x;
            p--;
            seg.set(p,x);
        }
        else if(t == 2)
        {
            int l, r;
            cin >> l >> r;
            l--;
            cout << seg.prod(l,r) << "\n";
        }
        else if(t == 3)
        {
            int v;
            cin >> v >> rh;
            v--;
            cout << seg.max_right<f>(v) + 1 << "\n";
        }
        
    }

    return 0;
}


Measured memory_bytes: 8996
A,B=[int(s) for s in input().split()]
a=A//100
b=B//100
def pal(num):
  return num*101-num%10-(num//100)*99
ans=b-a-1
if pal(a)>=A:
  ans+=1
if pal(b)<=B:
  ans+=1
print(ans)
  

Measured memory_bytes: 3060
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N, M = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N)]
AB.sort()

ans = 0
rest = M
for a,b in AB:
    buy = min(rest, b)
    ans += a * buy
    rest -= buy
    if rest == 0:
        break
print(ans)

Measured memory_bytes: 21604
from collections import Counter

n, m, k = map(int, input().split())
friends = []
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    friends.append((a - 1, b - 1))
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)

block = [[] for _ in range(n)]
for _ in range(k):
    c, d = map(int, input().split())
    block[c - 1].append(d - 1)
    block[d - 1].append(c - 1)

class Union:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.rank = 0
        self.size = 1

    def get_root(self):
        n = self
        while n.parent != n:
            n = n.parent
        return n

    def find_set(self):
        return self.get_root().val


unions = []
for i in range(n):
    unions.append(Union(i))

for a, b in friends:
    x, y = unions[a], unions[b]
    if x.find_set() == y.find_set():
        continue
    x_root, y_root = x.get_root(), y.get_root()
    if x_root.rank == y_root.rank:
        y_root.parent = x_root
        x_root.rank += 1
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
    else:
        x_root.parent = y_root
    size = x_root.size + y_root.size
    x_root.size = size
    y_root.size = size

d = {}
relation = []
for i in range(n):
    u = unions[i]
    parent = u.find_set()
    relation.append(parent)

parents = Counter(relation)
for i in range(n):
    p = relation[i]
    relation[i] = [p, parents.get(p)]

ans = []
for i in range(n):
    t = relation[i][1] - 1
    parent = relation[i][0]
    for j in graph[i]:
        if relation[j][0] == parent:
            t -= 1
    for k in block[i]:
        if relation[k][0] == parent:
            t -= 1
    ans.append(t)

print(*ans)

Measured memory_bytes: 123936
import sys
si = sys.stdin.readline


def main():
    [x, k, d] = [int(e) for e in si().split()]
    if x == 0:
        if k % 2 == 0:
            print(0)
        else:
            print(abs(d))
    elif x < 0:
        mul = (0-x)//d
        if k <= mul:
            x += d*k
            print(abs(x))
            return
        else:
            x += d*mul
            k -= mul
        while x < 0 and k:
            x += d
            k -= 1
        if k > 0:
            if k % 2:
                print(abs(x-d))
            else:
                print(x)
        else:
            print(abs(x))
    else:
        mul = (x-0)//d
        if k <= mul:
            x -= d*k
            print(x)
            return
        else:
            x -= d*mul
            k -= mul
        while x > 0 and k:
            x -= d
            k -= 1
        if k > 0:
            if k % 2:
                print(x+d)
            else:
                print(abs(x))
        else:
            print(abs(x))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9252
K, N=map(int, input().split())

A=list(map(int, input().split()))
maxL=0
pre=A[-1]
for i in range(N):
  if i==0:
    maxL=K+A[i]-pre
    pre=A[i]
  else:
    maxL=max(maxL, A[i]-pre)
    pre=A[i]
    
print(K-maxL)



Measured memory_bytes: 26444
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;


const ll MOD = 1e9+7;

struct DICE{
    ll num[6];
    ll top;
    ll north,south,west,east;

    DICE(){
        top = 0;
        south = 1;
        east = 2;
        west = 3;
        north = 4;
    }

};


int main(){
    DICE d;
    ll q;

    rep(i,0,6){
        cin >> d.num[i];
    }
    cin >> q;


    srand(time(NULL));
    rep(i,0,q){
        ll a,b;
        cin >> a >> b;

        while(1){
            ll rnd = rand() % 4;
            ll tmp;
            switch(rnd){
                case 0:
                    tmp = d.south;
                    d.south = 5 - d.top;
                    d.north = d.top;
                    d.top = tmp;
                    break;
                case 1:
                    tmp = d.west;
                    d.west = 5 - d.top;
                    d.east = d.top;
                    d.top = tmp;
                    break;
                case 2:
                    tmp = d.north;
                    d.north = 5 - d.top;
                    d.south = d.top;
                    d.top = tmp;
                    break;
                case 3:
                    tmp = d.east;
                    d.east = 5 - d.top;
                    d.west = d.top;
                    d.top = tmp;
                    break;
            }

            if(d.num[d.top] == a && d.num[d.south] == b){
                cout << d.num[d.east] << endl;
                break;
            }
        }
    }
    

    return 0;
}



Measured memory_bytes: 3108
from itertools import *
N,M = map(int,input().split())
K = [list(map(int,input().split()))[1:] for m in range(M)]
P = list(map(int,input().split()))
print(sum([all([sum([s[j-1] for j in v])%2==t for v,t in zip(K,P)]) for s in product([0,1],repeat=N)]))

Measured memory_bytes: 9204
import java.util.Scanner;

public class Main{

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

		Scanner sc = new Scanner(System.in);
		String s = "";
		String p = "";
		String searched_line = "";
		boolean judge = false;
		int count = 0; // 一致している文字数をカウントするための変数

		s = sc.nextLine();
		p = sc.nextLine();

		if (p.length() >= 1 && s.length() >= p.length() && s.length() <= 100) {

			searched_line = s + s.substring(0, p.length() - 1);

			out: for (int i = 0; i < s.length(); i++) {
				count = 0;
				if (("" + searched_line.charAt(i)).equals("" + p.charAt(0))) { // if1
					count++;
					in: for (int j = 1; j < p.length(); j++) {
						if (("" + searched_line.charAt(i + j)).equals("" // if2
								+ p.charAt(j)) == false) {
							break in;
						}// if2ここまで
						count++;
					}// in: for文ここまで

					if (count == p.length()) { // if3
						judge = true;
						break out;
					}// if3ここまで

				} // if1ここまで

			}// out:for文ここまで

			if (judge == true) {
				System.out.println("Yes");

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

		}

	}

}



Measured memory_bytes: 26216
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;

typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#define	GE() printf(">----------\n")
#define	IN() freopen("in.txt","r",stdin)
#define	OUT() freopen("out.txt","w",stdout)
const int mod=1000000007;
const int inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=105;

char s1[maxn], s2[maxn];
int len;

int main()
{
    while(~scanf("%d%s%s", &len, &s1, &s2)){
        if(len==1){
            printf("3\n");break;
        }
        LL ans;
        int i, flag=0;             //flag=0,竖，flag=1，横
        if(s1[0]==s1[1]){
            ans=6;
            i=2;
            flag=1;
        }
        else{   //竖
            ans=3;
            i=1;
        }
        for(i;i<len;i++){
            if(flag){   //前面是横
                if(s1[i]==s1[i+1]){  //当前是横
                    ans=(ans*3)%mod;
                    i++;
                }
                else{               //当前是竖
                    //不变
                    flag=0;
                }
            }
            else{       //前面是竖
                if(s1[i]==s1[i+1]){  //当前是横
                    ans=(ans*2)%mod;
                    i++;
                    flag=1;
                }
                else{               //当前是竖
                    ans=(ans*2)%mod;
                }
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}



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

ll N,M,A,B,C;
ll inf = 1e18;
struct state{
    ll node,dist,velocity;
    bool go;
    bool operator<(const state& r)const{
        return dist>r.dist;
    }
};

struct edge{
    int to,dist;
};

ll next_v(ll v){
    return (A*v+B)%C;
}

ll dp[510][51][2] = {};

int main() {
    vector<vector<edge>> v(510);
    cin >> N >> M;
    for(int i=0;i<M;i++){
        int x,y,t;
        cin >> x >> y >> t;
        v[x].push_back({y,t});
        v[y].push_back({x,t});
    }
    ll v0;
    cin >> v0;
    cin >> A >> B >> C;
    for(int i=1;i<=N;i++) for(int j=0;j<C;j++){
        dp[i][j][0] = inf;
        dp[i][j][1] = inf;
    }
    dp[1][v0][0] = 0;
    priority_queue<state> Q;
    Q.push({1,0,v0,0});
    while(!Q.empty()){
        state now = Q.top(); Q.pop();
        if(dp[now.node][now.velocity][now.go]<now.dist) continue;
        for(auto x:v[now.node]){
            state ne = now;
            ne.velocity = next_v(now.velocity);
            ll d = x.dist*now.velocity;
            ne.node = x.to;
            if(now.node==N) ne.go = true;
            if(dp[x.to][ne.velocity][ne.go]>now.dist+d){
                dp[x.to][ne.velocity][ne.go] = now.dist+d;
                ne.dist = now.dist+d;
                Q.push(ne);
            }
        }
    }
    ll ans = inf;
    for(int i=0;i<C;i++) ans = min(ans,dp[1][i][1]);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 11272
#include <stdio.h>
#include <string.h>

int main(){

    char moji[10000];

    scanf("%s", moji);

    int cnt = 0;

    for(int i = 0; ; i++){
        if(moji[i] != '\0'){
            cnt++;
        }else{
            break;
        }
    }

    if(moji[cnt-1] == 's'){
        strcat(moji, "es");
    }else{
        strcat(moji, "s");
    }

    printf("%s\n", moji);

    return 0;
}

Measured memory_bytes: 2096
// Created by 
// 
//  ████████╗██╗███╗   ███╗ ██████╗ ████████╗██╗  ██╗██╗   ██╗██╗  ██╗
//  ╚══██╔══╝██║████╗ ████║██╔═══██╗╚══██╔══╝██║  ██║╚██╗ ██╔╝╚██╗██╔╝
//     ██║   ██║██╔████╔██║██║   ██║   ██║   ███████║ ╚████╔╝  ╚███╔╝ 
//     ██║   ██║██║╚██╔╝██║██║   ██║   ██║   ██╔══██║  ╚██╔╝   ██╔██╗ 
//     ██║   ██║██║ ╚═╝ ██║╚██████╔╝   ██║   ██║  ██║   ██║   ██╔╝ ██╗
//     ╚═╝   ╚═╝╚═╝     ╚═╝ ╚═════╝    ╚═╝   ╚═╝  ╚═╝   ╚═╝   ╚═╝  ╚═╝
//  

#include<bits/stdc++.h>

using namespace std;

#define fastIO(); ios_base::sync_with_stdio(false); cin.tie(NULL);
#define dbg(x); cout<<"\n"<<#x<<": "<<x;
#define MOD 100000007
#define ret return
#define UC 100007
#define dt long int
#define pf printf
#define sf scanf

typedef vector<long long int> vlli;
typedef vector<long int> vli;
typedef vector<int> vi;
typedef vector<dt> vdti;
typedef vector<unsigned int> vui;
typedef unsigned int ui;    //  0 to e9
typedef long int li;    // e-18 to e18  
typedef long long int lli;  //  e-18 to e18
typedef unsigned long int uli;  // 0 to e19 
typedef unsigned long long int ulli;    //  0 to e19

dt gcd(dt a, dt b){ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b);  
} 

int main(){
    fastIO();
    dt k,sum(0),temp;
    cin>>k;
    for(dt i=1;i<k+1;i++){
        for(dt j=1;j<k+1;j++){
            for(dt l=1;l<k+1;l++){
                temp=gcd(j,l);
                sum+=gcd(i,temp);
            }
        }
    }
    cout<<sum<<"\n";
	ret 0; 
}       

Measured memory_bytes: 3640
#include<stdio.h>

int main(){
  int m[100][100];
  int i,j,n,u,k,v;
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      m[i][j]=0;
    }
  }

  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    u--;
    for(j=0;j<k;j++){
      scanf("%d",&v);
      v--;
      m[u][v]=1;
    }
  }

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      if(j>0)printf(" ");
      printf("%d",m[i][j]);
    }
    printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2048
#include "bits/stdc++.h"
using namespace std;
int N;
int main() {
	cin >> N;
	vector<long long>v(N);
	for (auto &i : v)cin >> i;
	auto D = [&](auto&&d,int l, int r, int x, int y) ->long long {
		if (l + 1 == r)return 0;
		long long e = LLONG_MAX;
		for (int i = l + 1; i < r; i++) {
			e = min(e, ((d(d,l, i, x, x + y)) + (d(d,i, r, x + y, y)) + v[i] * (x + y)));
		}
		return e;
	};
	cout<<D(D,0,N-1,1,1)+v[0]+v[N-1]<<endl;
}


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

int main() {
    int ABC[3];
    cin >> ABC[0] >> ABC[1] >> ABC[2];
    sort(ABC,ABC+3);
    reverse(ABC,ABC+3);
    int result = ABC[0]*10+ABC[1]+ABC[2];
    cout << result << endl;
    return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
#define mp make_pair

const ll INF = (ll)1e18;
const int N = 300300;
ll a[N];
int n;

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    scanf("%d", &n);
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        sum += a[i];
    }
    ll ans = INF;
    for (int i = 0; i < n - 1; i++) {
        sum -= 2 * a[i];
        ans = min(ans, abs(sum));
    }
    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

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

int main()
{
  cout << fixed << setprecision(10);
  int A,B;
  cin >> A >> B;
  if(A%2==1&&B%2==1)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
  return 0;
}


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

int main()
{

    ios_base::sync_with_stdio(false);
    int n,f=0;
    cin>>n;
    if(n>=1 && n<=9)
        cout<<"Yes\n";
    else
    {
        for(int i=2;i<=9;i++)
        {
            if(n%i==0){
            int a=n/i;
            if(a>=1 && a<=9)
            {
                f=1;
                break;
            }

            }
        }
        if(f==0)
            cout<<"No\n";
        else
            cout<<"Yes\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <set>

#define rep(i,n) for(int i = 0;i< (n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;

//priority_queue<int, vector<int>, greater<int>> min_heap;
//long long ccw(const Point& A, const Point& B, const Point& C) {
//   return 1LL * (B.x - A.x)*(C.y - A.y) - 1LL * (B.y - A.y)*(C.x - A.x);
//}
ll gcd(ll x, ll y) {
	if (y == 0)return x;
	else return gcd(y, x%y);
}
bool c[1000001];
int main() { // E 
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	ll a, b;
	cin >> a >> b;
	vector<ll> v;
	for (ll i = 1; i * i <= a; i++) {
		if (a % i == 0) {
			if (i == a / i) {
				v.push_back(i);
			}
			else {
				v.push_back(i);
				v.push_back(a / i);
			}
		}
	}
	vector<ll> v2;
	rep(i, (int)v.size()) {
		if (b % v[i] == 0) {
			v2.push_back(v[i]);
		}
	}
	int ans = 0;
	sort(v2.begin(), v2.end());
	rep(i, (int)v2.size()) {
		if (c[i])continue;
			ans += 1;
		rep(j, (int)v2.size()) {
			if (i == j)continue;
			if (gcd(v2[i], v2[j]) != 1) {
				c[j] = true;
			}
		}
	}
	cout << ans << '\n';





}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
#define mk make_pair
#define all(c) (c).begin(),(c).end()
#define debug(x) cerr<<#x<<" = "<<x<<endl;
#define debug2(x,y) cerr<<"("<<#x<<","<<#y<<") = ("<<x<<","<<y<<")\n";
#define debugM(x,n,m) rep(i,0,n){ rep(j,0,m) cerr<<x[i][j]<<" ";cerr<<endl;}
#define debugV(x,n) rep(i,0,n){cerr<<x[i]<<" ";}cerr<<endl; 
#define pi 3.14159265358979323846264338
typedef pair<int,int> ii;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-9;
const int MOD = 1e9+7;

int n,a,b,v[111];

int main(){
	cin>>n>>a>>b;
	vector <int> x,y,z;
	rep(i,0,n){
		scanf("%d",&v[i]);
		if(v[i]<=a) x.pb(v[i]);
		else if(v[i]<=b) y.pb(v[i]);
		else z.pb(v[i]);
	}
	printf("%d\n",min(min(x.size(),y.size()),z.size()));
	return 0;	
}

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

int main(){
    double PI = M_PI;
    int a, b, h, m;
    cin >> a >> b >> h >> m;

    double hx, hy, mx, my;
    hx = a * cos(2.0 * PI * (h / 12.0 + m / 720.0));
    hy = a * sin(2.0 * PI * (h / 12.0 + m / 720.0));
    mx = b * cos(2.0 * PI * m / 60.0);
    my = b * sin(2.0 * PI * m / 60.0);

    double ans = sqrt((hx - mx) * (hx - mx) + (hy - my) * (hy - my));

    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 4164
n = int(input())
days,lastChoco = map(int, input().split())
a = [int(input()) for i in range(n)]

allEatChoco = 0
for i in range(0,n):
    eatChoco = 1
    for j in range(1,102):
        if a[i] * j + 1 <= days:
            eatChoco += 1
        else:
            break
    allEatChoco += eatChoco

print(allEatChoco+lastChoco)
    


Measured memory_bytes: 3060
#include<iostream>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int colornum(string color){
  //cout<<color<<endl;
  if(color=="Red")return 0;
  if(color=="Yellow")return 1;
  if(color=="Blue")return 2;
  if(color=="Magenta")return 3;
  if(color=="Green")return 4;
  if(color=="Cyan")return 5;
  return 0;
}

int main(){
  int n;
  while(true){
    cin>>n;
    if(!n)break;
    set<int> dice;
    for(int i=0;i<n;i++){
      int d=0;
      int red = 0;
      vector<string> colors(6);
      for(int j=0;j<6;j++){
	cin>>colors[j];
	if (colors[j]=="Red")
	  red = j;
      }
      d = colornum(colors[5-red])*1296;
      int side[4];
      if(red==0)side[0] = 1,side[1]=2;
      if(red==1)side[0] = 0,side[1]=3;
      if(red==2)side[0] = 0,side[1]=1;
      if(red==3)side[0] = 0,side[1]=4;
      if(red==4)side[0] = 0,side[1]=2;
      if(red==5)side[0] = 1,side[1]=3;
      side[2] = 5-side[0];
      side[3] = 5-side[1];
      int dmin = 1296;
      for(int j=0;j<4;j++){
	int dd = 0;
	for(int k=0;k<4;k++){
	  dd *= 6;
	  dd += colornum(colors[side[(j+k)%4]]);
	}
	if(dd<dmin)dmin=dd;
      }
      d += dmin;
      dice.insert(d);
    }
    cout<<(n-dice.size())<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 300;

int n, c[N], d[N];
char s[N];
vector <int> g[N];

void dfs(int cur, int col) {
	if (c[cur] == col) {
		return;
	}
	if (c[cur] >= 0 && c[cur] != col) {
		puts("-1");
		exit(0);
	}
	c[cur] = col;
	for (int i = 0; i < g[cur].size(); i++) {
		dfs(g[cur][i], 1 - col);
	}
}

int main() {

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%s", s);
		for (int j = 0; j < n; j++) {
			if (s[j] == '1') {
				g[i].push_back(j);
				g[j].push_back(i);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		c[i] = -1;
	}

	dfs(0, 0);

	int res = 0;

	for (int i = 0; i < n; i++) {
		vector <int> q;
		for (int j = 0; j < n; j++) {
			d[j] = -1;
		}
		d[i] = 0;
		q.push_back(i);
		for (int j = 0; j < q.size(); j++) {
			int cur = q[j];
			res = max(res, d[cur] + 1);
			for (int k = 0; k < g[cur].size(); k++) {
				int t = g[cur][k];
				if (d[t] == -1) {
					d[t] = d[cur] + 1;
					q.push_back(t);
				}
			}
		}
	}

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

	return 0;

}

Measured memory_bytes: 640
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <map>
#include <string>

int main() {
  size_t N;
  intmax_t x;
  scanf("%zu %jd", &N, &x);

  std::vector<intmax_t> a(N);
  for (size_t i=0; i<N; ++i)
    scanf("%jd", &a[i]);

  std::sort(a.begin(), a.end());
  int res=0;
  for (size_t i=0; i+1<N; ++i) {
    if (a[i] <= x) {
      x -= a[i];
      ++res;
    }
  }
  if (x == a[N-1]) ++res;
  printf("%d\n", res);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };  // i<4:4way i<8:8way
int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

ll dp[200005][4]; // dp[i][j] := i番目まで見てj個余分なXを入れたときのmax


int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    int k = 1 + n % 2;
    rep(i,n+1)rep(j,k+1)dp[i][j] = -1e15;
    dp[0][0] = 0;
    rep(i,n){
        rep(j,k+1){
            // x を一個挿入する
            chmax(dp[i+1][j+1],dp[i][j]);

            // 余計なxを入れずにox列の通りに次の数を当てはめる
            ll now = dp[i][j]; // 現在までのmax
            if( (i+j)%2 == 0 ) now += a[i]; // 現在地がoだったら加算する
            chmax(dp[i+1][j],now); // i+1番目まで見てxをj個入れた時の値を更新する
        }
    }
    ll ans = dp[n][k];
    cout << ans << endl;
}

Measured memory_bytes: 11116
#include <bits/stdc++.h>
using namespace std;
#define ll                      long long
#define pb                      push_back
#define rep(i,a,b,c)            for(ll i=(a);i<=(b);i+=(c))
#define repb(i,a,b,c)           for(ll i=(a);i>=(b);i-=(c))
#define MOD                     998244353
#define inf                     3e18
#define ld                      long double
#define mp                      make_pair
#define vpll                    vector<pair<ll,ll> >
#define vll                     vector<ll>
#define vld                     vector<ld>
#define vvll                    vector<vector<ll>>
#define vvld                    vector<vector<ld>>
#define pll                     pair<ll,ll>
#define vvpll                   vector<vector<pair<ll,ll>>>
#define pqll                    priority_queue<ll>
#define mll                     map<ll,ll>
#define mlc                     map<ll,char>
#define um                      unordered_map
#define umll                    um<ll,ll>
#define umlc                    um<ll,char>
#define all(x)                  x.begin(),x.end()
#define fi                      first
#define se                      second
#define ln                      cout<<"\n";
#define endl                    "\n"
#define test                    ll T;cin>>T;while(T--)
#define isvowel(a)              (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
#define fastIO                  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define show(w,size)            for(ll i=0;i<size;i++) cout<<w[i]<<" ";
#define prll(a)                 cout<<a<<"\n";
#define mset(dp,no)             memset(dp,no,sizeof(dp))
#define input(a,n)              rep(i,0,n-1,1) cin>>a[i];
#define countbit                __builtin_popcount                                           //Number of setbits in decimal notation
#define lb(v,cur)               lower_bound(all(v),cur)-v.begin()
#define ub(v,cur)               upper_bound(all(v),cur)-v.begin()
#define db(...)                 __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 <<'\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
long long pows(long long a, long long b)
{
  long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll powm(ll x,ll y,ll m=MOD){x=x%m;ll res=1;while(y){if(y&1)res=res*x;res%=m;y=y>>1;x=x*x;x%=m;}return res;}
ll modInverse(ll a, ll m=MOD){if(m == 1)return 0;ll m0=m,y=0,x=1;while(a>1){ll q=a/m,t=m;m=a%m,a=t;t=y;y=x-q*y;x=t;}if(x<0) x+=m0;return x;}
int main()
{
fastIO
ll n,m,i,j,k,x,y,z,t,e,f,p,q,g,l,r,w,h,count1=0,prod=1,a,b,c,d,index,x1,x2,y1,y2,diff,ans=0,sum=0,sum1=0,sum2=0,flag=0,flag1=0,flag2=0;
string s,s1,s2;
cin>>a>>b;
if(b>=a)
{
  cout<<"unsafe";
}
else
{
  cout<<"safe";
}
}


Measured memory_bytes: 3656
import java.util.*;
public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();

    int []ary = new int[N];
    int count=0;
    for(int i = 0 ; i < N ; i++){
      ary[i] = sc.nextInt();
    }

    Arrays.sort(ary);
    for(int i = 0 ; i < N-2 ; i++){
      for(int j = i+1 ; j < N-1 ; j++){
        int high = N;
        int low = 0;
        while(high-low > 1){
          int middle = (high+low)/2;
          if(ary[middle] < ary[i] + ary[j]){
            low = middle;
          }else{
            high = middle;
          }
        }
        count += high-j-1;
      }
    }
    System.out.println(count);
  }
}


Measured memory_bytes: 28420
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {

		int n,x,m=0;
		int a[] = new int[256];

		Scanner scan = new Scanner(System.in);

		while(true)
		{
			int cnt=0;
			n = scan.nextInt();
			x = scan.nextInt();

			if( (n|x) == 0) break;

			for(int i=1; i<=n; i++)
			{
				for(int j=i+1; j<=n; j++)
				{
					for(int k=j+1; k<=n; k++)
					{
						if(i+j+k == x)
						{
							//System.out.printf("%d %d %d\n", i, j, k);
							cnt++;
						}
					}
				}
			}

			a[m++] = cnt;
		}

		scan.close();

		for(int i=0; i<m; i++) System.out.println(a[i]);
	}
}

Measured memory_bytes: 26680
#include <bits/stdc++.h>
#include <set>
#define rep(i,n) for (int i=0; i < (n); ++i)
#define all(a) a.begin(), a.end()
using ll = long long;
using namespace std;
 
// ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }


// const double PI = acos(-1);



int main() {
  // input
  int n; cin >> n;
  vector<int> d(n); 
  rep(i,n) cin >> d[i];
  // sort (vector)
  sort(d.begin(),d.end());
  int answer = d[d.size()/2] - d[d.size()/2-1];
  cout << answer << endl;

  return 0;


}

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

using namespace std;

#define INF (1ll << 62)
#define pb push_back
#define ii pair<int,int>
#define OK cerr <<"OK"<< endl
#define debug(x) cerr << #x " = " << (x) << endl
#define ff first
#define ss second
#define int long long
#define tt tuple<int, int, int>
#define endl '\n'

signed main () {
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, k;

  cin >> n >> k;

  vector<int> dp(n + 1);
  vector<int> arr(n + 1);

  for(int i = 1; i <= n; i++) {
  	cin >> arr[i];
  }

  for(int i = 2; i <= n; i++) {
  	dp[i] = INF;
  	for(int j = 1; j <= k; j++) {
  		if(i - j >= 1) {
  			dp[i] = min(dp[i], abs(arr[i] - arr[i - j]) + dp[i - j]);
  		} else {
  			break;
  		}
  	}
  }

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


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

int a[5];

int main(){
	for(int i=1;i<=3;i++) cin>>a[i];
	sort(a+1,a+4);
	int t=unique(a+1,a+4)-(a+1);
	cout<<t<<endl;
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define IL inline
#define RI register int
std::string a;
int ans;
int main()
{
    std::cin>>a;
    for(RI i=1;i<a.length();i++)
    if(a[i]!=a[i-1])ans++;
    std::cout<<ans<<std::endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const ll mod = (ll)10e9+7;
const int INF = 0x3f3f3f3f;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    int w=0, p=0, l=0;
    for(int i=0; i<s.length(); i++)
    {
        if(s[i]=='g'&&(p+1)*2<=i+1)
        {
            p++;
            w++;
        }
        else if(s[i]=='p')
        {
            if((p+1)*2<=i+1)
                p++;
            else l++;
        }
    }
    cout << w-l;
}

//TODO: 46


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i<(n);i++)
#define fore(i,a) for(auto &i:a)
#define debug(a,b) cout << "debug : " << a << " , "<< b << endl
using ll=long long;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
const ll INF=1LL<<60;
const ll mod=1E9+7;


int main(){
  int n;cin >> n;
  if(n%1000!=0)cout << 1000-n%1000;
  else cout << 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int main(){
  string x;
  cin>>x;
  int a=200000,b=0;
  for(int i=0;i<x.size();i++){
    if(x[i]=='A'){
      if(i<a){
        a=i;
      }
    }
    if(x[i]=='Z'){
      if(i>b){
        b=i;
      }
    }
  }
  if(b>a){
    cout<<b-a+1<<endl;
  }
}


Measured memory_bytes: 640