akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
const int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}


void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n - 1);
  cin >> b;

  a[0] = b[0];
  a[n - 1] = b[n - 2];
  rep3(i, 1, n - 1) {
    a[i] = min(b[i], b[i - 1]);
  }
  // cout << a << endl;
  cout << accumulate(all(a), 0) << endl;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author amotoma3
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskB solver = new TaskB();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskB {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long[] a = in.nextLongArray(n);

            long max = 2;
            long min = 2;

            for (int i = n - 1; i >= 0; i--) {
                if (i < n - 1 && a[i] == a[i + 1]) continue;

                if ((a[i] < min && max / a[i] * a[i] < min) || max < a[i]) {
                    out.println(-1);
                    return;
                }

                max = max / a[i] * a[i] + a[i] - 1;
                min = (min + a[i] - 1) / a[i] * a[i];
            }

            out.println(min + " " + max);
        }

    }

    static class InputReader {
        BufferedReader in;
        StringTokenizer tok;

        public String nextString() {
            while (!tok.hasMoreTokens()) {
                try {
                    tok = new StringTokenizer(in.readLine(), " ");
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return tok.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

        public long nextLong() {
            return Long.parseLong(nextString());
        }

        public long[] nextLongArray(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public InputReader(InputStream inputStream) {
            in = new BufferedReader(new InputStreamReader(inputStream));
            tok = new StringTokenizer("");
        }

    }
}



Measured memory_bytes: 40076
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <utility>
#include <vector>
#define ALL(x) (x).begin(), (x).end()
#define X first
#define Y second
typedef std::pair<int,int> pii;
typedef std::vector<pii> vip;
const int MAXC = 30;
std::bitset<MAXC> rec;
int   ptr[MAXC]{ };
vip	S[MAXC]{ };
int   sub[MAXC]{ };
int C, N;
vip tem;

int main()
{
	scanf(" %d%d", &N, &C);
	for(int i = 0; i < N; ++i)
	{
		pii dur; int chan;
		scanf(" %d%d%d", &dur.X, &dur.Y, &chan);
		S[--chan].push_back(dur);
	}
	for(int i = 0; i < C; ++i)
	{
		tem = S[i];
		S[i].clear();
		std::sort(ALL(tem));
		for(int j = 0; j < (int)tem.size(); ++j)
			if(S[i].empty() || (S[i].back().Y < tem[j].X))
				S[i].push_back(tem[j]);
			else
				S[i].back().Y = tem[j].Y;
	}
	int end = 1E5, ret = 0;
	for(int t = 1; t <= end; ++t)
	{	// Bottleneck
		for(int i = 0; i < MAXC; ++i)
			if((ptr[i] < (int)S[i].size()) && (t == S[i][ptr[i]].X))
				rec.set(i);
		// if(t <= 10) printf("%d: %d\n", t, rec.count());
		ret = std::max(rec.count(), (std::size_t)ret);
		for(int i = 0; i < 30; ++i)
			if((ptr[i] < (int)S[i].size()) && (t == S[i][ptr[i]].Y))
			{
				rec.reset(i);
				++ptr[i];
			}
	}
	printf("%d\n", ret);
	return 0;
}

Measured memory_bytes: 1908
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<Integer, Integer> map =new HashMap<>();
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int count = map.getOrDefault(a, 0);
            map.put(a, ++count);
        }
        
        long ans = 0;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            int key = e.getKey();
            int count = e.getValue();
            if (key > count) {
                ans += count;
            }
            if (key < count) {
                ans += count - key;
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 63140
import java.awt.geom.*;
import java.io.*;
import java.math.*;
import java.text.*; 
import java.util.*;
import java.util.regex.*;

/*
		  br = new BufferedReader(new FileReader("input.txt"));
		  pw = new PrintWriter(new BufferedWriter(new FileWriter("output.txt")));
		  br = new BufferedReader(new InputStreamReader(System.in));
		  pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
 */

public class Main {
	private static BufferedReader br;
	private static StringTokenizer st;
	private static PrintWriter pw;

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		int qq = 1;
		//int qq = Integer.MAX_VALUE;
		//int qq = readInt();
		for(int casenum = 1; casenum <= qq; casenum++)	{
			int n = readInt();
			int m = readInt();
			int[] l = new int[n];
			for(int i = 0; i < n; i++) {
				l[i] = readInt()-1;
			}
			par = new int[n];
			for(int i = 0; i < n; i++) {
				par[i] = i;
			}
			while(m-- > 0) {
				int a = readInt()-1;
				int b = readInt()-1;
				merge(a, b);
			}
			int ret = 0;
			for(int i = 0; i < n; i++) {
				if(find(l[i]) == find(par[i])) {
					ret++;
				}
			}
			pw.println(ret);
		}
		exitImmediately();
	}

	static int[] par;
	public static int find(int x) {
		return par[x] == x ? x : (par[x] = find(par[x]));
	}
	
	public static void merge(int x, int y) {
		par[find(x)] = find(y);
	}
	
	private static void exitImmediately() {
		pw.close();
		System.exit(0);
	}

	private static long readLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	private static double readDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	private static int readInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	private static String nextLine() throws IOException  {
		String s = br.readLine();
		if(s == null) {
			exitImmediately();
		}
		st = null;
		return s;
	}

	private static String nextToken() throws IOException  {
		while(st == null || !st.hasMoreTokens())  {
			st = new StringTokenizer(nextLine().trim());
		}
		return st.nextToken();
	}
}

Measured memory_bytes: 50952
import java.util.*;
import java.math.BigInteger;
 
public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();

        List<Long> list = new ArrayList<Long>();
        for (int i = 0; i < n; i++) {
            long a = scan.nextLong();
            list.add(a);
        }

        Collections.sort(list);//System.out.println(list);
        // listの先頭が0だったら、0を出力して即終了
        if (list.get(0) == 0) {
            System.out.println(0);
            return;
        }

        /*
        * 1. BigIntegerクラスを用いて、オーバーフローが起きないようにする。
        BigInteger ans = BigInteger.ONE;
        boolean isOver = false;
        for (int i = 0; i < n; i++) {
            ans = ans.multiply(BigInteger.valueOf(list.get(i)));
            if (ans.compareTo(BigInteger.valueOf(1000000000000000000l)) > 0) {
                isOver = true;
                break;
            }
        } 
        

        if (isOver) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
        */


        /* 2. multiplyExactメソッド（オーバーフローすると例外送出）を利用する方法。
        long ans = 1l;
        boolean isOver = false;
        try {
            for (int i = 0; i < n; i++) {
                long a = list.get(i);
                ans = Math.multiplyExact(ans, a);
                if (ans > 1000000000000000000l) {
                    isOver = true;
                    break;
                }
            } 
        } catch (ArithmeticException e) {
            isOver = true;
        }
        
        if (isOver) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
      	*/
        
        /* 
        * 3. オーバーフローすると、負の数や0になる可能性があることを考慮して場合わけする。
        long ans = 1l;
        for (int i = 0; i < n; i++) {
            long a = list.get(i);
            ans *= a;
            if (ans > 1000000000000000000l || ans <= 0) {
                break;
            }
        }
        if (ans > 1000000000000000000l || ans <= 0) {
            //System.out.println(ans);
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
        */
        
       
        long ans = 1l;
        boolean isOver = false;
        for (int i = 0; i < n; i++) {
            long a = list.get(i);            
            if (Math.floor(1000000000000000000l / ans) < a) {
                isOver = true;
                break;
            } else {
                ans *= a;
            }
        }
        if (isOver) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
        

    }
}


Measured memory_bytes: 61184
while a = gets
  arr = a.chomp.split("")
  len = arr.length

  w = 0; ans = Array.new
  while w <= len - 1
    if arr[w] == "@"
      word = arr[w+2] * arr[w+1].to_i
      w += 3
      ans.push(word)
    else
      ans.push(arr[w])
      w += 1
    end
  end
  puts ans.join
end

Measured memory_bytes: 8548
import java.util.Scanner;

public class Main{
		
	public static void main(String args[]){
		  
	    Scanner sc = new Scanner(System.in);
	    
	    int N = sc.nextInt();
	    int M = sc.nextInt();
	    int C = sc.nextInt();
	    
	    int B[] = new int[M];
	    int A[][] = new int[N][M];
	    
	    for(int i = 0; i < B.length; i++) {
	    	B[i] = sc.nextInt();
	    }
	    
	    for(int i = 0; i < N; i++) {
	    	for (int j = 0; j < M; j++) {
				A[i] [j] = sc.nextInt();
			}
	    }
	    
	    int cnt = 0;
	    int sum = 0;
	    for(int i = 0; i < N; i++) {
	    	for(int j = 0; j < B.length; j++) {
	    		sum += A[i][j]*B[j];
	    	}
	    	if(sum+C > 0) {
	    		cnt++;
	    	}
	    	sum = 0;
	    }
	    
	    System.out.println(cnt);
	    
	    
	}
	
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<vector<ll> > Graph;
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; }
const ll INF = 1e18;

char c[8][8];

int main(){
    int h,w,k;
    cin >> h >> w >> k;
    rep(i,h)rep(j,w)cin>>c[i][j];
    ll ans = 0;
    for(int bit1=0;bit1<(1<<h);bit1++){
        for(int bit2=0;bit2<(1<<w);bit2++){
            int now = 0;
            rep(i,h){
                rep(j,w){
                    if((bit1>>i)&1)continue;
                    if((bit2>>j)&1)continue;
                    if(c[i][j]=='#')now++;
                }
            }
            if(now==k)ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

const int INF = 1001001001;
//const ll INF = 1000000000000000000;

ll a, b, v, w, t;

int main() {
	int n;
	cin >> n;
	vector<int> x(100001, 0);
	rep(i,n) {
		int tmp;
		cin >> tmp;
		x[tmp]++;
	}

	ll ans = 0;
	rep(i, 100001) ans += i*x[i];

	int q;
	cin >> q;
	rep(i,q) {
		int b, c;
		cin >> b >> c;
		int tmp = x[b];
		x[b] = 0;
		x[c] += tmp;
		ans += tmp*(-b + c);
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3776
#include <stdio.h>

int main(void){
  long int K;
  long int sum = 0;
  scanf("%ld",&K);
  for(int a = 1;a <= K;a++){
    for(int b = 1;b <= a;b++){
      for(int c = 1;c <= b;c++){
        for(int i = c;i > 0;i--){
          if(a%i==0&&b%i==0&&c%i==0){
            if(a==b&&b==c){
              sum+=i;
            }
            else if(a!=b&&b!=c&&c!=a){
              sum+=i*6;
            }
            else{
              sum+=i*3;
            }
            i=0;
          }
        }
      }
    }
  }
  printf("%ld",sum);
  return 0;
}


Measured memory_bytes: 1704
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

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

    ll  a,b,c,d,e,n,maxi=0,f=0,mini=INF,sum=0,q;
	string str,g;
    cin>>n>>a;
    b=1;
    rep(i,n){
        b=min(b+a,b*2);
    }
    cout<<b<<endl;

    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
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;
}
typedef long long int ll;

#define EPS (1e-7)
#define INF (1 << 30)
#define LLINF (1LL << 60)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

//-------------------------------------

ll dp[100010][4];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    dp[0][0] = 1LL;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            if (s[i] == '?')
            {
                (dp[i + 1][j] += dp[i][j] * 3LL) %= MOD;
            }
            else
            {
                (dp[i + 1][j] += dp[i][j]) %= MOD;
            }
        }
        if (s[i] == 'A' || s[i] == '?')
        {
            (dp[i + 1][1] += dp[i][0]) %= MOD;
        }
        if (s[i] == 'B' || s[i] == '?')
        {
            (dp[i + 1][2] += dp[i][1]) %= MOD;
        }
        if (s[i] == 'C' || s[i] == '?')
        {
            (dp[i + 1][3] += dp[i][2]) %= MOD;
        }
    }
    cout << dp[n][3] << endl;
}

Measured memory_bytes: 3664
n, m = map(int,input().split())
a = list(map(int,input().split()))

total = sum(a)
threshold = total / 4 / m

num_over = 0
done = False
for i in a:
    if i >= threshold:
        num_over = num_over + 1
    if num_over == m:
        print('Yes')
        done = True
        break

if not done:
    print('No')

Measured memory_bytes: 3064
a, b = map(int, input().split())


def F(n):
    a = n//2
    if n % 2 == 0:
        if a % 2 == 0:
            return n
        else:
            return n ^ 1
    else:
        if a % 2 == 0:
            return 1
        else:
            return 0


ans = F(a-1) ^ F(b)
print(ans)


Measured memory_bytes: 9160
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define loop(i,N) for(ll (i)=0; (i)<(N);++(i))
struct _OMAZINAI_ { _OMAZINAI_() { std::ios::sync_with_stdio(false); std::cin.tie(0); } } __omazinai_instance__;
#define INF (1LL<<61 + 1<<29)
#define YesNo(x) {std::cout << ((x)?"Yes":"No") << std::endl;}
#define YESNO(x) {std::cout << ((x)?"YES":"NO") << std::endl;}
#define OddEven(x) {std::cout << ((x)%2?"Odd":"Even") << std::endl;}
#define ODDEVEN(x) {std::cout << ((x)%2?"ODD":"EVEN") << std::endl;}
typedef long long int ll;
void _INPUT_IMPL_() {};
template <class T, class... Args> void _INPUT_IMPL_(T& dest, Args&... args) { cin >> dest; _INPUT_IMPL_(args...); }
void _OUTPUT_IMPL_() {};
template <class T, class... Args> void _OUTPUT_IMPL_(T dest, Args... args) { cout<< dest << (sizeof...(Args)?" ":""); _OUTPUT_IMPL_(args...); }
#define in(type, ...) type __VA_ARGS__; _INPUT_IMPL_(__VA_ARGS__)
#define in_v(type, name, cnt) vector<type> name(cnt); loop(i, cnt) cin >> name[i];
#define sort_v(v) std::sort(v.begin(), v.end())
#define out(...) _OUTPUT_IMPL_(__VA_ARGS__)

int main() {
	int t[] = { 0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1 };
	in(int, x, y);
	YesNo(t[x] == t[y]);
}

Measured memory_bytes: 256
def d_median_of_medians(N, A):
    class BIT(object):
        """Binary Indexed Tree (1-indexed)"""

        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, index):
            """tree[1]からtree[index]までの和を計算"""
            ret = 0
            while index > 0:
                ret += self.tree[index]
                index -= index & (-index)
            return ret

        def add(self, index, value):
            """tree[index]にvalueを加算"""
            while index <= self.size:
                self.tree[index] += value
                index += index & (-index)

    def is_accepted(x):
        """
        A[l]からA[r]までの要素の中央値がx以上か。すなわち、A[l]からA[r]までの
        要素のうちx以上であるものが (N*(N+1)/2)/2 個以上か
        """
        from itertools import accumulate
        from math import ceil
        a_larger_x = [(1 if a >= x else -1) for a in A]  # x以上か否かを{1, -1}に変換
        cumsum = list(accumulate(a_larger_x))

        ans = 0
        a_larger_x_sorted = {a: k for k, a in enumerate(sorted(cumsum), 1)}
        bit = BIT(N)
        for c in cumsum:
            ans += bit.sum(a_larger_x_sorted[c]) + int(c >= 0)
            bit.add(a_larger_x_sorted[c], 1)
        return True if ans >= ceil((N * (N + 1)) / 4) else False

    # 二分探索の探索区間は [min(A), max(A)] で十分だが、
    # min, maxはO(N)なので、決め打ちしたほうがNが大きなとき速い
    accept = 0
    reject = 10**9 + 1  # 数列の要素の値の制約から、この値は中央値になりえない
    while reject - accept > 1:
        mid = (accept + reject) // 2
        if is_accepted(mid):
            accept = mid
        else:
            reject = mid
    return accept

N = int(input())
A = [int(i) for i in input().split()]
print(d_median_of_medians(N, A))

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

int main(){
  int n; cin >> n;
  bool ans = true;
  for(int i=0; i<n; ++i){
    int x; cin >> x;
    if(x%2==1)
      ans=!ans;
  }
  cout << (ans?"YES":"NO") << endl;
  return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
s = input()
i = s.find("1")/2
ans = 0

# former part
while ans * (k-1) < i:
    ans += 1
i = max(i, ans * (k-1))

# latter part
tmp = 0
while tmp * (k-1) + i < n-1:
    tmp += 1

print(ans + tmp)


Measured memory_bytes: 4724
n, k = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(n)]

count = [0] * (10 ** 5 + 2)
for a, b in query:
    count[a] += b

for i, c in enumerate(count):
    k -= c
    if k <= 0:
        print(i)
        exit()

Measured memory_bytes: 19440
#include <bits/stdc++.h>
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define deb(x) cout<<#x<<"="<<x<<endl;
#define endl '\n'
#define M 1000000007
#define int long long
#define max_n 1000000

using namespace std;

void solve()
{
	ll n;
	cin>>n;
	string s;
	cin>>s;
	vector<ll> r,g,b;
	for (int i = 0; i < s.length(); ++i)
	{
		if(s[i]=='R')r.push_back(i);
		else if(s[i]=='G')g.push_back(i);
		else b.push_back(i);
	}
	ll ans=0;
	for (int i = 0; i < r.size(); ++i)
	{
		for (int j = 0; j < g.size(); ++j)
		{
			ll x=r[i],y=g[j];
			if(x>y)swap(x,y);
			ans+=b.size();
			// ll i=x,j=y,k;
			if(find(b.begin(), b.end(),2*y-x)!=b.end())ans--;
			// j=x,k=y;
			if(find(b.begin(), b.end(),2*x-y)!=b.end())ans--;
			if((x+y)%2==0 && find(b.begin(), b.end(),(x+y)/2)!=b.end())ans--;
		}
	}
	cout<<ans<<endl;
}

int32_t main() 
{
	IOS	
	ll T=1;
	// cin>>T;
	for(ll i=1;i<=T;++i)
	{		
		// cout<<"Case #"<<i<<": ";
    	solve();
	}
	return 0;
}

Measured memory_bytes: 3684
#include<iostream>
#include<vector>
using namespace std;
int L, sz = 0;
struct edge { int u, v, w; };
vector<edge>e;

int main() {
	cin >> L; L--;
	if (L == 1) {
		cout << "2 2" << endl << "1 2 1" << endl << "1 2 0" << endl;
		return 0;
	}
	while ((1 << sz) <= L)sz++;
	int s = 1, t = sz;
	for (int i = 1; i < sz; i++) {
		e.push_back({ i,i + 1,1 << (sz - i - 1) });
		e.push_back({ i,i + 1,0 });
	}
	int w = 1 << (sz - 1);
	for (int p = sz - 2, i = 1; p >= 0; p--, i++) {
		if (L >> p & 1) {
			e.push_back({ s,i + 1,w });
			w += 1 << p;
		}
	}
	e.push_back({ s,t,L });
	cout << sz << ' ' << e.size() << endl;
	for (auto&& ed : e)cout << ed.u << ' ' << ed.v << ' ' << ed.w << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = [int(a) for a in input().split()]
Card = {}
for i in range(N):
    if A[i] in Card:
        Card[A[i]] += 1
    else:
        Card[A[i]] = 1

rem, double = len(Card), 0
for i in Card:
    if Card[i] % 2 == 0:
        double += 1

print(rem - double % 2)

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

int main(){
  int n;
  cin >> n;
  vector<LL> a(n+1,0);
  for(int i=1;i<=n;i++){
    cin >> a[i];
  }
  sort(a.begin(),a.end());
  vector<LL> ruiseki(n+1,0);
  ruiseki[0]=a[0];
  for(int i=1;i<=n;i++){
    ruiseki[i]=ruiseki[i-1]+a[i];
  }
  int l=0,r=n,mid;
  int now,next;
  while(r-l>1){
    mid=(l+r)/2;
    next=mid;
    // cout << mid << ":";
    while(1){
      now=next;
      next=distance(a.begin(),upper_bound(a.begin(),a.end(),2*ruiseki[now]))-1;
      // cout << next << " ";
      if(next>=n-1){
        r=mid;
        break;
      }
      if(next==now){
        l=mid;
        break;
      }
    }
    // cout << endl;
  }
  cout << n-l << endl;
  return 0;
}


Measured memory_bytes: 1792
import sys
input = sys.stdin.readline
import math

x, n = map(int, input().split())
p = list(map(int, input().split()))

mi = 1000
ans = x
for i in range(105):
    for j in range(n):
        if p[j] == i:
            break
        if j == n - 1:
            if abs(x - i) < mi:
                mi = abs(x - i)
                ans = i
print(ans)


Measured memory_bytes: 9188
#include <iostream>
using namespace std;
const int MAX = 150;

int main(){
    int rect[MAX+1][MAX+1],H,W;
    
    for(int i = 1 ; i <= MAX ; i++)
        for(int j = 1 ; j <= MAX ; j++)
            rect[i][j] = i*i+j*j;
    
    while(cin >> H >> W ,H){
        int cmp_bef = H*H+W*W;
        int nH = MAX,nW = MAX;
   
        for(int i = MAX-1 ; i > 0 ; i--){
            for(int j = MAX ; j > i ; j--){
                if(i == H && j == W) continue;
                int cmp_af = nH*nH+nW*nW;
                if(rect[i][j] > cmp_bef || (rect[i][j] == cmp_bef && i > H)){
                    if(rect[i][j] < cmp_af || (rect[i][j] == cmp_af && i < nH)){
                        nH = i;
                        nW = j;
                    }
                }
            }
        }
        cout << nH << " " << nW << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1244
#include<stdio.h>
int main(){
    int a,b,x,y,z;
    scanf("%d %d",&a,&b);
    x = a+b;
    y = a-b;
    z = a*b;
    int ans;
    if(x>=y && x>=z)printf("%d",x);
    else if(y>=x && y>=z)printf("%d",y);
    else printf("%d",z);
    return 0;

}

Measured memory_bytes: 128
#include<stdio.h>

static const int MAX=500;
static const int INFTY=(1<<21);

int main(){
  int n,i,j;
  int M[MAX][MAX];
  int k,c,u,v;
  int minv;
  int d[MAX];
  int vis[MAX];

  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      M[i][j]=INFTY;
    }
  }

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

  for(i=0;i<n;i++){
    d[i]=INFTY;
    vis[i]=0;
  }

  d[0]=0;

  while(1){
    minv=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(minv>d[i] && !vis[i]){
	u=i;
	minv=d[i];
      }
    }
    if(u==-1)break;
    vis[u]=1;
    for(v=0;v<n;v++){
      if(!vis[v] && M[u][v] !=INFTY){
	if(d[v]>d[u]+M[u][v]){
	  d[v]=d[u]+M[u][v];
	}
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%d %d\n",i,(d[i]==INFTY?-1:d[i]));
  }
  return 0;
}



Measured memory_bytes: 2088
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
#define all(a) a.begin(),a.end()
#define bs binary_search
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ipr pair<ll,ll>
#define ps push_back
#define fs first
#define sc second
#define endl "\n"
#define mod 1000000007
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l,n;
	cin>>n;

	map< pair<ll,ll> ,ll > mp;
	if(n%2==0){
		for(i=1;i<=(n/2);i++){
			mp[{i,n+1-i}]=1;
		}
	}
	else {
		for(i=1;i<=(n/2);i++){
			mp[{i,n-i}]=1;
		}
	}

	vector< pair<ll,ll> > vc;
	for(i=1;i<=n;i++){
		for(j=i+1;j<=n;j++){
			if(mp.find({i,j})==mp.end()){
				vc.ps({i,j});
			}
		}
	}
	l=vc.size();
	cout<<l<<endl;
	for(i=0;i<l;i++){
		cout<<vc[i].fs<<" "<<vc[i].sc<<endl;
	}
	return 0;
}


Measured memory_bytes: 512
package main

import (
	"fmt"
	"sort"
)

type Store struct {
	Price int64
	Num   int
}
type Stores []Store

func (s Stores) Len() int {
	return len(s)
}
func (s Stores) Less(i, j int) bool {
	return s[i].Price < s[j].Price
}
func (s Stores) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func main() {
	var N, M int
	fmt.Scan(&N, &M)

	stores := make([]Store, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&(stores[i].Price), &(stores[i].Num))
	}
	sort.Sort(Stores(stores))
	money := int64(0)
	for i, d := 0, 0; d < M; i++ {
		if d+stores[i].Num <= M {
			money += stores[i].Price * int64(stores[i].Num)
			d += stores[i].Num
		} else {
			money += stores[i].Price * int64(M-d)
			d = M
		}
	}
	fmt.Println(money)
}


Measured memory_bytes: 5376
#include<stdio.h>
int main()
{
double w,h,x,y;
  scanf("%lf %lf %lf %lf",&w,&h,&x,&y);
  printf("%lf ",(w*h)/2);
  if(x*2==w && y*2==h) printf("1");
  else printf("0");
return 0;}

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

using namespace std;

typedef long long ll;

const int MAXN = 50;
int visited[MAXN+1];
int adj[MAXN+1][MAXN+1];
int N;

void dfs(int x){
  if(visited[x]) return;
  visited[x] = 1;
  for(int y=1;y<=N;y++){
    if(adj[x][y]) dfs(y);
  }
}

int main(){
  int M; cin >> N >> M;
  vector<pair<int, int> > edges;
  memset(adj, 0, sizeof adj);
  for(int i=0;i<M;i++){
    int a, b; cin >> a >> b;
    edges.push_back(make_pair(a, b));
    adj[a][b] = 1;
    adj[b][a] = 1;
  }
  int cnt = 0;
  for(int i=0;i<M;i++){
    memset(visited, 0, sizeof visited);
    int x = edges[i].first;
    int y = edges[i].second;
    adj[x][y] = 0;
    adj[y][x] = 0;
    // dfs
    dfs(1);
    int isBridge = 0;
    for(int i=1;i<=N;i++){
      if(visited[i] == false){
        isBridge = 1;
        break;
      }
    }
    if(isBridge) cnt++;
    adj[x][y] = 1;
    adj[y][x] = 1;
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int h[100010], maxv[100010];
int main(){
  int a, b;
  cin >> a >> b;
  for(int i = 0;i < a;i++)
  {
    cin >> h[i];
  }
  for(int i = 0;i < b;i++){
    int x, y;
    cin >> x >> y;
    maxv[x - 1] = max(h[y - 1], maxv[x - 1]);
    maxv[y - 1] = max(h[x - 1], maxv[y - 1]);
  }
  int ans = 0;
  for(int i = 0;i < a;i++)
  {
    ans += h[i] > maxv[i];
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 4340
using System;

namespace MyProgram{
    class AtCoder{
        static void Main(string[] args){
            int N = int.Parse(Console.ReadLine());
            int[] A = new int[N];
            for(var i=0;i<N;i++){
                A[i] = int.Parse(Console.ReadLine());
            }
            int max = 0;
            int second_max = 0;
            int index = 0;
            for(var i=0;i<N;i++){
                if(max<A[i]){
                    second_max = max;
                    index = i;
                    max = A[i];
                }else if(second_max<A[i]){
                    second_max = A[i];
                }
                
            }
            for(var i=0;i<N;i++){
                if(i==index){
                    Console.WriteLine(second_max);
                }else{
                    Console.WriteLine(max);
                }
            }
        }
    }
}

Measured memory_bytes: 18608
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int ara[n+5];
  for(int i=1;i<=n;i++)cin>>ara[i];
  
  bool visit[n+5];
  memset(visit,false,sizeof visit);
  bool f=true;
  int cnt=0;
  int i=1;
  while(1)
  {
    if(visit[i]==true)break;
    if(i==2)
    {
      f=false;
      cout<<cnt<<endl;
      break;
    }
    visit[i]=true;
    cnt++;
    i=ara[i];
  }
  if(f)cout<<-1<<endl;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#include <set>
#define ll long long 
#include <string>
#define pb push_back
#define mp make_pair
# define pi 3.14159265358979323846
#define mod 1000000007
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
void fastio()
{
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

}
ll int multiply(ll int a,ll int b)
{
	ll int ans=(a%mod*b%mod)%mod;
	return ans;
}
ll int add(ll int a, ll int b)
{
	ll int ans=(a%mod+b%mod)% mod;
	return ans;
}
 
void solve()
{
	ll int a,b,c,d;
   cin>>a>>b>>c>>d;
   vector<pair<ll int ,ll int > > v;
   v.pb(mp(a,b));
   v.pb(mp(c,d));
   ll int ans;
   sort(v.begin(),v.end());
   if (v[0].second>=0 && v[1].second>=0)
   {
   	ans=max(v[0].second*v[1].second,v[0].first*v[1].first);
   }
   else if (v[0].first<=0 && v[1].first<=0)
   {
   	ans=max(v[0].first*v[1].first,v[0].second*v[1].second);
   }
   else
   {
   	if (v[0].second<=0 && v[1].first>=0)
   		ans=v[0].second *v[1].first;
   	

   }
   cout<<ans<<endl;
}

int main()
{ 
	fastio();
    ll int t;
    // cin>>t;
    t=1;
    while(t--)
    {
    	solve();
    }
}

	
		
	
	
	
	





Measured memory_bytes: 3640
#include<stdio.h>
#include<stdlib.h>
int main()
{
  int N,*T,M,*P,*X;
  int *gokei,i,j;
  
  scanf("%d",&N);
  T=(int*)malloc(sizeof(int)*N);
  for(i=0;i<N;i++)
    scanf("%d",&T[i]);
  scanf("%d",&M);
  P=(int*)malloc(sizeof(int)*M);
  X=(int*)malloc(sizeof(int)*M);
  gokei=(int*)malloc(sizeof(int)*M);
  for(i=0;i<M;i++)
    scanf("%d %d",&P[i],&X[i]);
      
  for(i=0;i<M;i++){
    gokei[i]=0;
    for(j=0;j<N;j++){
      gokei[i]+=T[j];
    }
    gokei[i]-=T[P[i]-1]-X[i];
    printf("%d\n",gokei[i]);
  }
  
  return 0;
}

Measured memory_bytes: 128
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int a[] = new int[M];
        int b[] = new int[M];
        
        for(int i=0; i<M; i++){
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        
        HashMap<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for(int i=1; i<=N; i++){
        cnt.put(i, 0);
        }
        
        for(int i=0; i<M; i++){
        cnt.put(a[i], cnt.get(a[i])+1);
        cnt.put(b[i], cnt.get(b[i])+1);
        }
        
        for(int key=1; key<N+1; key++){
            int sum = cnt.get(key);
            System.out.println(sum);
        }
        
    }
}

Measured memory_bytes: 21712
#include <bits/stdc++.h>
    using namespace std;
         
    typedef vector<int> VI;
    typedef vector<VI> VVI;
    typedef vector<string> VS;
    typedef pair<int, int> PII;
    typedef long long LL;
    typedef pair<LL, LL> PLL;
         
    #define ALL(a)  (a).begin(),(a).end()
    #define RALL(a) (a).rbegin(), (a).rend()
    #define PB push_back
    #define EB emplace_back
    #define MP make_pair
    #define SZ(a) int((a).size())
    #define SORT(c) sort((c).begin(),(c).end())
         
    #define FOR(i,a,b) for(int i=(a);i<(b);++i)
    #define REP(i,n)  FOR(i,0,n)
         
    #define FF first
    #define SS second
    template<class S, class T>
    istream& operator>>(istream& is, pair<S,T>& p){
      return is >> p.FF >> p.SS;
    }
         
    const double EPS = 1e-10;
    const double PI  = acos(-1.0);
    const LL MOD = 1e9+7;
         
         
    LL dp[310][100010];
    LL mx[310][100010];
     
    // 幅Wの窓で値pを追加した時の最大値
    void add(deque<PLL>& dq, PLL p, int W){
      while(!dq.empty() && dq.back().FF < p.FF)
    	dq.pop_back();
      dq.push_back(p);
      while(!dq.empty() && p.SS - dq.front().SS + 1 > W)
    	dq.pop_front();
    }
     
    int main(){
      cin.tie(0);
      ios_base::sync_with_stdio(false);
         
      LL N, M, K; cin >> N >> M >> K;
      vector<LL> xs(N);
      REP(i,N) cin >> xs[i];
      deque<PLL> dq;
      REP(i,N){
    	dp[1][i] = xs[i];
    	add(dq, MP(dp[1][i],i), M);
    	mx[1][i] = dq.front().FF;
      }
     
      for(LL i=2;i<=K;++i){
    	dq.clear();
    	for(int j=i-1;j<N;++j){
    	  LL nxt = mx[i-1][j-1] + i * xs[j];
    	  dp[i][j] = max(dp[i][j], nxt);
     
    	  add(dq, MP(dp[i][j],j), M);
    	  mx[i][j] = dq.front().FF;
    	}
      }

      LL ans = 0;
      REP(i,N) ans = max(ans, dp[K][i]);
      cout << ans << endl;
          
      return 0;
    }

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


int main() {

  int a, b, k;
  cin >> a >> b >> k;

  vector<int> vec;
  for(int i = 0; i < k; i++){
    if(a > b)
      break;
    vec.push_back(a);
    if(a < b) 
      vec.push_back(b);
    a++;
    b--;
  }
  sort(vec.begin(), vec.end());

  for(int i = 0; i < vec.size(); i++){
    cout << vec[i] << endl;
  }
}

Measured memory_bytes: 256
def put_queen(field,r,c):
    return field | 1<<(r*8+c)

def check_queen(field,r,c):
    return field & 1<<(r*8+c)

def view_field(field):
    for i in range(8):
        for j in range(8):
            print('Q' if check_queen(field,i,j) else '.', end='')
        print()

def placeable(field,r,c):
    for i in range(8):
        if check_queen(field,r,i) or check_queen(field,i,c):
            return False
    if r>c:
        r1,c1 = r-c,0
    else:
        r1,c1 = 0,c-r

    if r>7-c:
        r2,c2 = r-(7-c),7
    else:
        r2,c2 = 0,c+r

    for i in range(8):
        if 0<=r1+i<8 and 0<=c1+i<8 and check_queen(field,r1+i,c1+i)     \
            or                                                          \
            0<=r2+i<8 and 0<=c2-i<8 and check_queen(field,r2+i,c2-i):
            return False

    return True


def make_field(field, queen_num):
    if queen_num==8:
        return field
    for i in range(8):
        for j in range(8):
            if placeable(field,i,j):
                solve_field = make_field(put_queen(field,i,j),queen_num+1)
                if not solve_field==2**64:
                    return solve_field
    return 2**64
    
k=int(input())
field=0
for i in range(k):
    r,c=map(int,input().split())
    field = put_queen(field,r,c)

view_field(make_field(field,k))






Measured memory_bytes: 5612
#include<bits/stdc++.h>
#define ll long long 
#define mp make_pair 
#define f(i,n) for(int i=0;i<n;i++) 
#define F first 
#define S second 
#define pb push_back 

using namespace std;

void test(){
	int x;
	cin>>x;
	for(int i=9;i>=2;i--){
		if(x>=(200*i)){
			cout<<10-i<<"\n";
			break;
		}
	}
}

int main(){
	int tests=1;
	// cin>>tests;
	while(tests--){
		test();
	}
}


Measured memory_bytes: 3632
n = int(input())
a = list(map(int, input().split()))
m = (n * (n + 1) // 2) // 2 + 1


class BIT1():
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s


def check(x):
    # MofM が x以下である
    # x以下の要素が (n*(n+1)//2)//2 + 1 個以上ある

    s = 0
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i]
        if a[i] <= x:
            c[i + 1] += 1
    d = [2 * c[i] - i + n + 1 for i in range(n + 1)]
    d_max = max(d)
    bit = BIT1(d_max)

    cnt = 0
    for i in range(n + 1):
        cnt += bit.sum(d[i] - 1)
        bit.add(d[i], 1)
    return cnt >= m


lb = 0  # False
ub = max(a) + 1  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)


Measured memory_bytes: 121032
#include<iostream>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<vector>
#include<climits>
using namespace std;

int main(void){

    string s;
    cin>>s;
    int count=0;
    int count1=0;

    for(int i=0;i<s.size();i++){
        if(i%2==0) count = ((s[i]=='0') ? count : count+1);
        else count = ((s[i]=='1') ? count : count+1);
        //cout << count;
    }
    //cout<<count<<endl;

    for(int i=0;i<s.size();i++){
        if(i%2==0) count1 = (s[i]=='1') ? count1 : count1+1;
        else count1 = (s[i]=='0') ? count1 : count1+1;
    }
   // cout<<count1<<endl;

    cout<<min(count, count1)<<endl;
    


    return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

int main(){
  int n; cin >> n;
  //L[i] shows the minimum element of Incresing Subsequence whose length is i+1
  vector<int> a, L(n);
  //the length of Longest Increasing Subsequence using a_0 ... a_i
  int length=1;
  for(int i=0;i<n;i++){
    int x; cin >> x;
    a.push_back(x);
  }
  L[0]=a[0];
  for(int i=1;i<n;i++){
    if(L[length-1] < a[i]) L[length++]=a[i];
    else *lower_bound(L.begin(), L.begin()+length, a[i]) = a[i];
  }
  cout << length << endl;
}

Measured memory_bytes: 3820
from string import ascii_lowercase


def solve(N):
    """
    >>> solve(2)
    b
    >>> solve(27)
    aa
    >>> solve(703)
    aaa
    """
    q = N
    ret = ""
    while True:
        q, r = divmod(q - 1, 26)
        ret = ascii_lowercase[r] + ret
        if q == 0:
            print(ret)
            return


def main():
    """
    """
    N = int(input())
    solve(N)


def _test():
    import doctest
    doctest.testmod()


if __name__ == "__main__":
    import sys
    argv = sys.argv
    if len(sys.argv) == 1:
        # no option
        main()
    elif sys.argv[1] == "-t":
        _test()
    else:
        input = open(sys.argv[1]).buffer.readline


Measured memory_bytes: 9976
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 29;
 
int main() {
	string s;
	cin >> s;
	int n = s.size();
	string a = "", b = "";
	rep(i, n) {
		if (i % 2 == 0) {
			a += '0';
			b += '1';
		}
		else {
			a += '1';
			b += '0';
		}
	}
	int cntA = 0, cntB = 0;
	rep(i, n) {
		if (s[i] != a[i]) cntA++;
		if (s[i] != b[i]) cntB++;
	}
	cout << min(cntA, cntB) << endl;
	return 0;
}

Measured memory_bytes: 768
// Problem : B - Frog 2
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

void solve(){
    int n,k;
    cin>>n>>k;
    vi dp(n+1,inf),h(n+1);
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++){
        if(i == 1) dp[i] = 0;
        for(int j=1;j<=k;j++){
            if(i+j <= n) dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
        }
    }
    cout<<dp[n];
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 4784
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;

int main(){

    int r;
    cin >> r;
    cout << r * r << endl;
}

Measured memory_bytes: 256
n = gets.to_i
as = []
bs = []

map = {}

(n-1).times {
	a,b = gets.split.map &:to_i
	as << a
	bs << b

	if map[a] == nil then
		map[a] = []
	end
	map[a] << b
	
	if map[b] == nil then
		map[b] = []
	end
	map[b] << a
}

max = map.each_value.map{ |x| x.size }.max

color = {}

current = [[1, 0]]
temp = nil

while current.size > 0
	next_current = []
	current.each{ |target, temp_color|
		map[target].each{ |node|
			if color[[target, node]] == nil then
				temp_color += 1
				if temp_color > max then
					temp_color -= max
				end
				next_current << [node, temp_color]
				color[[target, node]] = temp_color
				color[[node, target]] = temp_color
			end
		}
	}
	current = next_current
end

puts max

(0...n - 1).each{ |i|
	puts color[[as[i], bs[i]]]
}

Measured memory_bytes: 49324
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <chrono>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)

#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pi >
#define ppi pair<pi,ll>
#define ppp pair<pi,pi >
#define ex(str,a,b) str.substr((int)(a),min((int)str.size()-a,(int)(b-a+1))) 
#define all(X) X.begin(),X.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// for pair comparison function(ascending order) use return (i1.ff < i2.ff);

/* string operations :
   str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
   __builtin_popcount(n) : no. of set bits in n.
*/

const int M = (1<<20)+5;
const int md = 1e9+7;

priority_queue<ll,vector<ll >,greater<ll > > pq;

ll pwr(ll a,ll n,ll m)
{
	ll p=1;
	while(n>0)
	{
		if(n%2==1)
			p=(p*a)%m;
		a=(a*a)%m;
		n=n/2;
	}
	return p;
}

vector<pi > adj[305];
ll dp[305][305][305];

bool check(ll p,ll r,ll g,ll b)
{
	for(auto ed:adj[p])
	{
		ll l = ed.ff;
		ll x = ed.ss;
		ll c = 0;
		if(r>=l) c++;
		if(g>=l) c++;
		if(b>=l) c++;
		if(c != x)
			return 0;
	}
	return 1;
}

void rec(ll r,ll g,ll b)
{
	if(r>=max(g,b))
	{
		ll x = r;
		if(check(x+1,x+1,g,b))
			dp[x+1][g][b] = (dp[r][g][b]+dp[x+1][g][b])%md;
		if(check(x+1,r,x+1,b))
			dp[r][x+1][b] = (dp[r][g][b]+dp[r][x+1][b])%md;
		if(check(x+1,r,g,x+1))
			dp[r][g][x+1] = (dp[r][g][b]+dp[r][g][x+1])%md;
	}
	else if(g>=max(r,b))
	{
		ll x = g; 
		if(check(x+1,x+1,g,b))
			dp[x+1][g][b] = (dp[r][g][b]+dp[x+1][g][b])%md;
		if(check(x+1,r,x+1,b))
			dp[r][x+1][b] = (dp[r][g][b]+dp[r][x+1][b])%md;
		if(check(x+1,r,g,x+1))
			dp[r][g][x+1] = (dp[r][g][b]+dp[r][g][x+1])%md;
	}
	else
	{
		ll x = b; 
		if(check(x+1,x+1,g,b))
			dp[x+1][g][b] = (dp[r][g][b]+dp[x+1][g][b])%md;
		if(check(x+1,r,x+1,b))
			dp[r][x+1][b] = (dp[r][g][b]+dp[r][x+1][b])%md;
		if(check(x+1,r,g,x+1))
			dp[r][g][x+1] = (dp[r][g][b]+dp[r][g][x+1])%md;
	}
}

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

	ll n,m,i,j,k,l,r,x,ans = 0;

	cin >> n >> m;
	for(i=1;i<=m;++i)
	{
		cin >> l >> r >> x;
		if(r-l+1 < x)
		{
			cout << 0 << "\n";
			return 0;
		}
		adj[r].pb(pi(l,x));
	}

	dp[0][0][0] = 1;
	for(i=0;i<=n;++i)
	{
		for(j=0;j<=n;++j)
		{
			for(k=0;k<=n;++k)
			{
				// cout << i << " " << j << " " << k << " " << dp[]
				rec(i,j,k);
			}
		}
	}

	for(i=0;i<n;++i)
	{
		for(j=0;j<n;++j)
		{
			ans = (ans+dp[i][j][n])%md;
			ans = (ans+dp[i][n][j])%md;
			ans = (ans+dp[n][i][j])%md;
		}
	}

	cout << ans << "\n";
}

Measured memory_bytes: 222112
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pil;
typedef complex<double> xy_t;

const lint mod = 1e9 + 7;

int main(){
    int n;
    scanf("%d", &n);
    printf("%d\n", n*(n-1)/2 - n/2);
    For(i, 1, n+1)For(j, i+1, n+1)if((n%2 && i+j!=n) || (n%2==0 && i+j!=n+1)){
        printf("%d %d\n", i, j);
    }
}

Measured memory_bytes: 256