akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;


using i64 = long long;

signed main(){
    int n;
    cin >> n;
    vector<int> a(n - 1), b(n - 1);
    for(int i = 0; i < n - 1; ++i)
        cin >> a[i] >> b[i];
    for(int i = 0; i < n - 1; ++i)
        --a[i], --b[i];
    vector<vector<int>> edges(n);
    for(int i = 0; i < n - 1; ++i){
        edges[a[i]].emplace_back(i);
        edges[b[i]].emplace_back(i);
    }
    vector<int> v(n - 1, -1);
    function<void(int,int)> f = [&](int x, int col){
        int k = (col == 0);
        for(auto idx : edges[x]){
            if(v[idx] != -1)
                continue;
            v[idx] = k;
            f(a[idx] == x ? b[idx] : a[idx], k);
            k = (k + 1 == col ? k + 2 : k + 1);
        }
    };
    f(0, -1);
    cout << *max_element(v.begin(), v.end())+1 << endl;
    for(int i = 0; i < n - 1; ++i)
        cout << v[i] + 1 << endl;
}


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

using namespace std;

int n, k, lose, win;
double ans;

int main(){
	cin >> n >> k;
	
	for(int i = 1; i <= n; ++i){
		int num = i;
		int count = 0;
		while(num < k){
			count++;
			num *= 2;
		}
		ans += (1.0/n)*(double)pow(1.0/2, count);
	}
	printf("%.16f\n", ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <set>
#include <stack>
using namespace std;
int N, M; 
vector<int> E[400010]; 
int visited[400010]; 
int main(){
	string S; 
	cin >> N >> M >> S; 
	set<pair<int, int>> T;
	for(int i = 0; i < M; i++){
		int a, b; cin >> a >> b; 
		a--; b--; 
		if(a > b) swap(a, b); 
		T.insert(make_pair(a, b)); 
	}
	int In[400010] = {};
	for(auto it = T.begin(); it != T.end(); it++){
		int a = (*it).first; int b = (*it).second; 
		if(S[a] == 'A' && S[b] == 'A'){
			E[2*a+1].push_back(2*b); In[2*b] ++; 
			if(a!= b) {
				E[2*b+1].push_back(2*a); In[2*a] ++; 
			}
		}
		if(S[a] == 'A' && S[b] == 'B'){
			E[2*a].push_back(2*b); In[2*b] ++; 
			E[2*b+1].push_back(2*a+1); In[2*a+1] ++; 
		}
		if(S[a] == 'B' && S[b] == 'A'){
			E[2*a+1].push_back(2*b+1); In[2*b+1] ++; 
			E[2*b].push_back(2*a); In[2*a] ++; 
		}
		if(S[a] == 'B' && S[b] == 'B'){
			E[2*a].push_back(2*b+1); In[2*b+1] ++; 
			if(a != b){
				E[2*b].push_back(2*a+1); In[2*a+1] ++; 
			}
		}
	}
	stack<int> st;
	for(int i = 0; i < N*2; i++){
		if(!In[i]) st.push(i); 
	}
	vector<int> Top = {}; //トポロジカルソート後
	while(st.size()){
		int i = st.top(); st.pop(); 
		Top.push_back(i); 
		for(int j = 0; j < E[i].size(); j++){
			In[E[i].at(j)] --; 
			if(!In[E[i].at(j)]) st.push(E[i].at(j)); 
		}
	}
	cout << ((Top.size() == N*2) ? "No" : "Yes") << endl;
}

Measured memory_bytes: 30376
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
h,w,k = readInts()
c = [input() for _ in range(h)]
# dp = [[0] * (w+1) for _ in range(h+1)]
# dp[0][0] = 1
# # dp[i+1][j+1] = i列目, j行目を選んだ時
black = 0
for nya in c:
    black += nya.count('#')

# 視点からどのくらいの距離を見るか
ans = 0

# if black == k:
#     print(1)
# else:
for bitx in range(1 << w):
    for bity in range(1 << h):
        cost = 0
        table = [[0] * w for _ in range(h)]
        for y in range(h):
            for x in range(w):
                if bitx & (1 << x):
                    for i in range(h):
                        table[i][x] = 1
                if bity & (1 << y):
                    for i in range(w):
                        table[y][i] = 1
        for y in range(h):
            for x in range(w):
                if table[y][x] != 1:
                    if c[y][x] == '#':
                        cost += 1
        if cost == k:
            ans += 1
print(ans)


Measured memory_bytes: 73804
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	int n;
  	cin>>n;
  	vector<int> h(n);
  for(int i=0;i<n;i++) cin>>h[i];
  vector<int> dp(n,0);
  dp[1] = abs(h[1]-h[0]);
  for(int i=2;i<n;i++){
  	dp[i] = min(abs(h[i]-h[i-2]) + dp[i-2] , abs(h[i]-h[i-1]) + dp[i-1]);
  }
  cout<<dp[n-1];
  return 0;
}

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

int N, M, Q;
vector<int> a,b,c,d;
int ans;

void dfs(vector<int> A){
    if(A.size() == N+1){
        int now =0;
        for(int i=0; i<Q; i++){
            if (A[b[i]] - A[a[i]] == c[i]){
                now += d[i];
            }
        }
        ans = max(ans, now);
        return;
    }

    A.push_back(A.back());
    while(A.back() <= M){
        dfs(A);
        A.back()++;
    }


}

int main() {
    cin >> N >> M >> Q;
    a = b = c = d = vector<int>(Q);
    for(int i=0; i<Q; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    dfs(vector<int>(1,1));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
typedef long long ll;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 1 << 30;
const ll INFll = 1ll << 60;
template <typename T>
bool chmax(T& a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T& a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

int main() {
  string O, E;
  cin >> O >> E;
  int len = O.length() + E.length();

  int o = 0, e = 0;
  rep(i, len) {
    if (i % 2 == 0) {
      cout << O[o];
      o++;
    } else {
      cout << E[e];
      e++;
    }
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long int
#define mod 1000000007
#define string_mod 2549536629329_base_255
#define pb push_back
#define F first
#define S second
#define ff first
#define endl "\n"
#define ss second
#define all(v) v.begin(), v.end()
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int power(int x, unsigned int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res % p;
}
vector<int> v[100];

int n, m, x;
int solve(int in,vector<int>&ve){
    int f = 0;
    for (int i = 0; i < ve.size(); i++)
    {
        if (ve[i] < x)
        {
            f = 1;
        }
    }
    if (f == 0)
    {
        return 0;
    }

    if (in >=n)
    {
        return 1e15;
    }

 
      int ans = 1e18;
      vector<int> tmp = ve;
      for (int i = 1; i <= m;i++){
        tmp[i - 1] += v[in][i];
      }
      
      ans = min(ans, v[in][0]+solve(in + 1, tmp));
      ans = min(ans, solve(in + 1, ve));
      return ans;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc;
    tc = 1;
    //cin >> tc;
    while (tc--)
    {
        cin >> n >> m >> x;
        int a;
        for (int i = 0; i < n;i++){
            for (int j = 0; j <= m;j++){
                cin >> a;
            v[i].pb(a);}
        }

        vector<int> ve;
        for (int i = 0; i < m;i++){
            ve.pb(0);
        }
        int ans = solve(0, ve);
        if(ans>=1e10){
            ans = -1;
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 3652
N, X, Y = gets.chomp.split.map(&:to_i)

result = Array.new(N - 1) { 0 }

(1..N-1).to_a.each {|i|
  (i+1..N).to_a.each {|j|
    min_d = [
      j - i,
      (X - i).abs + 1 + (j - Y).abs,
    ].min
    result[min_d - 1] += 1
  }
}

result.each {|r| puts r}

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

#define REP(i,n) for(decltype(n) i=0; i<(n); ++i)
#define ALL(c) (c).begin(), (c).end()
#define st first
#define nd second
#define pb push_back

typedef pair<int,int> pii;
typedef vector<int> vi;

int a,b,c,d,e,f;

inline bool ok(int w, int s){
    return w+s <= f && 100*s <= w*e;
}

inline bool cmp(int w1, int s1, int w2, int s2){
    return s1*w2 < s2*w1;
}

void solve(){
    cin>>a>>b>>c>>d>>e>>f;
    set<int> W, S;
    for(int i=100;i*a<=f;i+=100)
        for(int j=0;i*a+j*b<=f;j+=100)
            W.insert(i*a+b*j);
    for(int i=0;i*c<=f;++i)
        for(int j=0;i*c+j*d<=f;++j)
            S.insert(i*c+j*d);
    int w1=0, s1=-1;
    for(int w : W)
        for(int s : S){
            if(ok(w,s) && cmp(w1,s1,w,s)){
                w1 = w;
                s1 = s;
            }
        }
    cout<<w1+s1<<' '<<s1<<'\n';
}

int main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    solve();
    return 0;
}


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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
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 pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;

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

int main(){

  ll a,b;cin>>a>>b;
  if(a+b==15)out("+");
  else if(a*b==15)out("*");
  else out("x");

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define EPS 1e-9
#define INF MOD
#define MOD 1000000007LL
#define fir first
#define iss istringstream
#define sst stringstream
#define ite iterator
#define ll long long
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define pi pair<int,int>
#define pb push_back
#define sec second
#define sh(i) (1LL<<i)
#define sz size()
#define vi vector<int>
#define vc vector
#define vl vector<ll>
#define vs vector<string>

int c[12],t[12],l;
char s[80010];

int main(){
	while(cin>>s&&((l=strlen(s))>1||s[0]!='0')){
		memset(c,0,sizeof(c));
		int a=0;
		rep(i,l){
			int x=s[i]-'0';
			copy(c,c+11,t);
			rep(j,11){
				if(i%2)c[(j+x)%11]=t[j];
				else c[(j-x+11)%11]=t[j];
			}
			if(x){
				if(i%2)c[x]++;
				else c[11-x]++;
			}
			a+=c[0];
		}
		cout<<a<<endl;
	}
}

Measured memory_bytes: 936
//#include <bits/stdc++.h>
#include "bits/stdc++.h"
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> VI;
typedef vector<VI> VVI;//例: VVI dp(10, vector<int>(10, INF);
typedef priority_queue<int, vector<int>, less<int> > QUE_int;
const int INF = pow(10, 5) + 1;//+1しないとREになる(out of rangeになるんかな?? )

int main(void) {
	int N, M;
	cin >> N >> M;
	vector<int> a(M), b(M);
	VVI node(N, vector<int>());
	for (int i = 0; i < M; i++) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		node[a[i]].push_back(b[i]);
		node[b[i]].push_back(a[i]);
	}

	vector<int> perm(N);//0からはじまり 2番目の数字以降は1~N-1の順列
	perm[0] = 0; //必ずノード0から開始するので最初は0
	for (int i = 1; i < N; i++) perm[i] = i;
	
	
	int ans = 0;
	do {
		//for (int i = 0; i < N; i++) cout << perm[i] << " ";
		//cout << endl;
		
		bool is_goal = true;
		for (int i = 0; i < N-1; i++) {
			int now_node = perm[i];
			int next_node = perm[i + 1];
			for (int j = 0; j < node[now_node].size(); j++) {
				if (node[now_node][j] == next_node) break;
				if (j == node[now_node].size() - 1) {
					is_goal = false; //now_nodeとnext_nodeがつながっていない
				}
			}
		}
		if (is_goal == true) ans++;
	} while (next_permutation(perm.begin()+1, perm.end()));
	//↑最初の数字は0からはじまり，　2番目以降を順列に並べる

	cout << ans << endl;
}	


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
 
vector<pair<int, int>> g[1000000];
vector<bool> v(1000000);
vector<int> dis(1000000);
bool res = true;
 
void dfs(int node) {
	if (v[node]) { return; }
	v[node] = true;
 
	for (auto i : g[node]) {
		if (!v[i.first]) {
			dis[i.first] = dis[node] + i.second;
			dfs(i.first);
		} else if (dis[i.first] != dis[node] + i.second) {
			res = false;
		}
	}
}
 
int main() {
	int n, m;
	cin >> n >> m;
 
	for (int i = 0; i < m; ++i) {
		int l, r, d;
		cin >> l >> r >> d;
 
		g[l].push_back(make_pair(r, d));
		g[r].push_back(make_pair(l, -1 * d));
	}
 
	for (int i = 1; i <= n; i++) {
		bool res = true;
		if (!v[i]) {
			dfs(i);
		}
	}
 
	cout << (res ? "Yes" : "No") << endl;
}

Measured memory_bytes: 36736
# frozen_string_literal: true

n, m, x = gets.split.map(&:to_i)
arr = []
alg = Array.new(m, 0)
sum = 0
n.times do
  a = gets.split.map(&:to_i)
  (1..m).each do |i|
    alg[i - 1] += a[i]
  end
  sum += a[0]
  arr << a
end
unless alg.select { |i| i < x }.empty?
  puts -1
  exit
end
(1..n).each do |i|
  arr.combination(i).each do |a|
    count = 0
    al = Array.new(m, 0)
    a.each do |c, *v|
      count += c
      m.times do |i|
        al[i] += v[i]
      end
    end
    if al.select { |i| i < x }.empty?
      sum = count if sum > count
    end
  end
end
puts sum


Measured memory_bytes: 14840
#include <bits/stdc++.h> 
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
#define MAX 100005
#define DEBUG 0 
#define LIMIT (LONG_MAX / 10)
#define POSITIVE_LAST_D (LONG_MAX % 10)
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    if(n%2!=0){
        cout<<"No"<<endl;
        return 0;
    }else{
        int cnt=0;
        for(int i=0;i<n/2;i++){
            if(s[i]==s[n/2+i])cnt++;
        }
        if(cnt==n/2){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

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

int main() {
  int64_t n,a,b;
  cin >> n >> a >> b;
  int64_t m=n/(a+b);
  int64_t bsum=m*a;
  int64_t o=m*(a+b);
  
  if((n-o)>=a){
    bsum=bsum+a;
  }
  else{
    bsum=bsum+n-o;
  }
  cout << bsum << endl;
}


Measured memory_bytes: 256
n = gets.to_i
as = gets.split.map(&:to_i)
rates = 8.times.map { |i| (i * 400...(i + 1) * 400) }

count = 0 # gte 3200
ans = as.each_with_object([]) do |a, arr|
  if a < 3200
    arr << rates.index { |r| r.include?(a) }
  else
    count += 1
  end
end.uniq

puts [(ans.count > 0 ? ans.count : 1), ans.count + count].join(" ")


Measured memory_bytes: 1788
/*
...........__________    							 |										    ___  __
.............|       |     						     |											 |   /
.............|       |     						     |									  		 |  /
.............|       |                               |                         __                | /      _______
.............|_______|  _______            _______   |______   ________   /|  /  |               |/       |      |
.............| \               | |      | |          |      |          | / | /   |               |\       |
.............|  \       _______| |      | |_______   |      |   _______|   |/    |               | \      |
.............|   \      |      | |      |         |  |      |  |       |   |     |               |  \     |
.........  __|    \__|  |______| |______| ________|  |      |_ |_______|   |     |__|           _|   \__ _|        .

*/
#include<bits/stdc++.h>
using namespace std ;
#define int 				long long
#define ull 				unsigned long long int
#define ld 					long double
#define vi 					vector<int>
#define vii 				vector<pair<int,int>>
#define vvi 				vector<vector<int>>
#define pf 					push_front
#define popb 				pop_back
#define pb 					push_back
#define eb 					emplace_back
#define pii 				pair<int,int>
#define prec(x) 			fixed<<setprecision(15)<<x
#define all(x) 				x.begin(),x.end()
#define rall(x) 			x.rbegin(),x.rend()
#define mset(a,b) 			memset(a,b,sizeof(a))
#define mcpy(a,b) 			memcpy(a,b,sizeof(a))
#define fo0(i,n) 			for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) 			for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) 			for(int i=a,i##end=b;i<=i##end;i++)
#define foe(i,x)			for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)			for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define inf 1e18
const int mod=1e9+7;
const int N=4e5+10;

void raushan_kumar(){
	int n;cin>>n;
	int ans=ceil(n*1.0/2);
	cout<<ans;
}

int32_t main()
{
	
	fast;int t=1;
	//cin>>t;
	while(t--){
		raushan_kumar();
	}

}

Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
N = int(input())
count = 0

for a in range(A+1):
	for b in range(B+1):
		for c in range(C+1):
			if 500*a + 100*b + 50*c == N:
				count+=1
print(count)

Measured memory_bytes: 3060
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String s = sc.next().replace("C","A").replace("G","A").replace("T","A");
	int len = s.length();
	int max = 0;
	for(int i = len; i>=0; i--) {
	    String str = "";
	    for(int j = 0; j<i;j++) {
		str = str + "A";
	    }
	    if(s.indexOf(str)>=0) {
		System.out.println(i);
		return;
	    }
	}



    }
}

Measured memory_bytes: 21844
from fractions import gcd

n, k = map(int, input().split())
a = list(map(int, input().split()))
n = a[0]
max_num = max(a)
for num in a[1:]:
    n = gcd(n, num)
if k % n == 0 and k <= max_num:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 16280
using System;
using System.Linq;
using System.Collections.Generic;
class c
{
    static void Main()
    {
        var nmx = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int n = nmx[0], m = nmx[1], x = nmx[2];
        var list = new List<int[]>();
        for (int i = 0; i < n; i++)
        {
            list.Add(Array.ConvertAll(Console.ReadLine().Split(), int.Parse));
        }
        var ans = int.MaxValue;
        int POW2_12 = (int)Math.Pow(2, n);
        for (int a = 0; a < POW2_12; a++)
        {
            var check = new int[m];
            var cost = 0;
            for (int i = 0; i < n; i++)
            {
                if ((a >> i & 1) == 1)
                {
                    cost += list[i][0];
                    for (int j = 0; j < m; j++)
                    {
                        check[j] += list[i][j + 1];
                    }
                }
            }
            if (check.Count(f => f < x) == 0) ans = Math.Min(ans, cost);
        }
        Console.WriteLine(ans == int.MaxValue ? -1 : ans);
    }
}

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

int main (void){
  long long int n = 0,k = 0,ans = 0;

  cin >> n >> k;

  vector<long long int> s(n,10000);
  for(int i = 0;i < n;i++){
    cin >> s[i];
  }

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

  for(int i = 0;i < k;i++){
    ans = ans + s[i];
  }

  cout << ans << endl;
  return 0;

}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define all(x) (x.begin(),x.end())
#define pii pair<int,int> 
#define vi vector<int> 
#define FOR(i,n) for(int i=0;i<n;i++)
#define MOD 1000000007
#define fi first
#define se second
using namespace std;
void solve()
{
 int n;
 cin>>n;
 vector<int> v(n);
 for(int i=0;i<n;i++)
 {
 	cin>>v[i];
 }	
 vector<int> pref(n);
 pref[n-1]=v[n-1]%MOD;
 for(int i=n-2;i>=0;i--)
 pref[i]=(pref[i+1]%MOD+v[i]%MOD)%MOD;
 int sum=0;
 for(int i=0;i<n-1;i++)
 sum=(sum%MOD+(v[i]%MOD)*(pref[i+1]%MOD))%MOD;
 cout<<sum%MOD<<endl;
}
int32_t main()
{
	int t=1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}
// Problem : C - Sum of product of pairs
// Contest : AtCoder - AtCoder Beginner Contest 177
// URL : https://atcoder.jp/contests/abc177/tasks/abc177_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)



Measured memory_bytes: 6420
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define maxn 100000
LL a[maxn],ans=0;
struct Base{
	LL a[63];
	void insert(LL x){
		for(int i=62;~i;i--){
			if(ans&(1ll<<i))continue;
			if(x&(1ll<<i)){
				if(!a[i]){a[i]=x;return;}
				x^=a[i];
			}
		}
	}
	LL Max(){
		LL ans=0;
		for(int i=62;~i;i--){
			ans^=(ans&(1ll<<i))?0:a[i];
		}
		return ans;
	}
}S;
int main(){
	int n;scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%lld",a+i),ans^=a[i];
	for(int i=0;i<n;i++)S.insert(a[i]);
	LL w=S.Max();
	printf("%lld",((w^(w&ans))<<1)+ans);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    string s;
    cin >> s;
    if (s[2] == s[3] && s[4] == s[5]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
s=[]
for i in range(m):
  s+=[list(map(int,input().split()))]
#print(s)
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  a=[]
  for _ in range(n):
    a+=[i%2]
    i//=2
  #print(a)
  pp=1
  for j in range(m):
    num=0
    for si in s[j][1:]:
      if a[si-1]==1:
        num+=1
    #print(num)
    if num%2!=p[j]:
      pp=0
  if pp==1:
    ans+=1
print(ans)
  
    

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

int main(){
    int N, W;
    cin >> N >> W;
    int dp[10001]; //重さwでの最大価値
    fill_n(dp, W+1, -1);
    dp[0] = 0;

    for(int i = 0; i < N; i++){
        int v, w;
        cin >> v >> w;
        for(int j = w; j <= W; j++){
            if(dp[j-w] != -1) dp[j] = max( dp[j-w] + v, dp[j]);
        }
    }
    cout << *max_element(dp, dp + W + 1 ) << endl;
}


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

using namespace std;

long long n, z = 0, ma = 0, pr;
long long a[100100];
bool f = false;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if(a[i] == i)
        {
            if(f)
            {
                f = false;
            }
            else
            {
                f = true;
                ma++;
            }
        }
        else
        {
            f = false;
        }
    }
    cout << ma;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define int long long   // aaaaaaaaaaaaaaaaaa
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define SIZE(buff) (sizeof(buff)/sizeof(buff[0]))
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
template<typename T, typename U>ostream& operator << (ostream& os, pair<T, U>& pair_var)
{os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}
// head
int q,m,n,k,res,tmp,tmp2;
int a[16][16] = {};
int b[200010] = {};
VVI g(100010);
VVI g2(100010);
deque<PII> que;
int dp[100010][3];
int hukasa[100010];
string s;

int dfs(int x , int y){
	for(auto i : g[x]){
		if (hukasa[i] > y+1){
			hukasa[i] = y+1;
			que.pb({i,y+1});
			g2[x].pb(i);
		}
	}
}

signed main() {
	cin.tie(0);
    ios::sync_with_stdio(false);
	std::cin >>n;
	rep(i,0,n-1){
		cin>>tmp>>tmp2;
		tmp--;tmp2--;
		g[tmp].pb(tmp2);
		g[tmp2].pb(tmp);
	}
	rep(i,0,n){
		hukasa[i] = 1<<30;
	}
	hukasa[0] = 0;
	que.pb({0,0});
	while(que.size()){
		PII ima = que.front();
		que.pop_front();
		dfs(ima.first,ima.second);
	}
	vector <PII> vec;
	rep(i,0,n){
	vec.pb({hukasa[i],i});
	}
	sort(vec.begin(), vec.end(), greater<PII>());
	for(auto x : vec){
		if (g2[x.se].size()== 0){
			dp[x.se][0] = dp[x.se][1] = 1;
			continue;
		}
		tmp = 1;
		tmp2 = 1;
		for(auto k : g2[x.se]){
			tmp *= dp[k][0];
			tmp2 *= (dp[k][0] + dp[k][1]);
			tmp %=mod;
			tmp2 %= mod;
		}
		dp[x.se][1] = tmp;
		dp[x.se][0] = tmp2;
	}
	cout<<(dp[0][0] + dp[0][1])%mod<<endl;
}


Measured memory_bytes: 17520
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def SS(): return map(str,sys.stdin.readline().rstrip().split())
def II(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
d = LI()
d.sort()

if N % 2 != 0:
  print(0)
  exit()

print(d[int(N/2)] - d[int(N/2)-1])

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

public class Main {
	
	private void solve() {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int M = in.nextInt();
		ArrayList<ArrayList<Integer>> connect = new ArrayList<>(M);
		for(int i=0; i<M; i++){
			ArrayList<Integer> switches = new ArrayList<>();
			int k = in.nextInt();
			for(int j=0; j<k; j++) {
				switches.add(in.nextInt());
			}
			connect.add(switches);
		}
		int[] condition = new int[M];
		for(int i=0; i<M; i++) {
			condition[i] = in.nextInt();
		}
		
		int count = 0;
		AllPat : for(int pat=0; pat<(1<<N); pat++) {
			for(int l =0; l<M; l++) {
				int on = 0;
				for(Integer s : connect.get(l)) {
					if(((1<<(s-1)) & pat) != 0) on++;
				}
				if(on%2 != condition[l]) continue AllPat;
			}
			count ++;
		}
		System.out.println(count);
	}
	
	public static void main(String[] args) {
		new Main().solve();
	}
}


Measured memory_bytes: 23124
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>  // std::accumulate(m.begin(), m.end(), 0LL);
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {
  std::string a, b; std::cin >> a >> b;
  std::string N = a + b;
  int k = std::stoi(N);
  if ( k == std::pow((int)std::sqrt(k),2) ) std::cout << "Yes" << std::endl;
  else std::cout << "No" << std::endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))

A_dict = {}

for i in A:
    if i in A_dict:
        A_dict[i] += 1
    else:
        A_dict[i] = 1



A_tuple = sorted(A_dict.items(), key=lambda x: -x[0])
side = []


for i in A_tuple:
    if i[1] >= 4:
        side.append(i[0])
        side.append(i[0])
    elif i[1] >= 2:
        side.append(i[0])
    if len(side) >= 2:
        break


if len(side) < 2:
    print(0)
else:
    print(side[0] * side[1])

Measured memory_bytes: 70680
#include<queue>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

struct Dinic {
    typedef LL Flow;
    static const Flow INF = 1LL<<50;
    struct Edge {
	int src, dst;
	Flow cap;
	int rev;
    };
    typedef vector<vector<Edge> > Graph;
    Graph G;
    vector<int>len, iter;
    Dinic(int N) : G(N) {}
    void add_edge(int u, int v, Flow c) {
	G[u].push_back((Edge){ u, v, c, (int)G[v].size() });
	G[v].push_back((Edge){ v, u, 0, (int)G[u].size()-1 });
    }
    Flow dfs(int v, int s, Flow c) {
	if (v == s || c == 0) return c;
	Flow ret = 0;
	for (int &i=iter[v]; i<(int)G[v].size(); i++) {
	    Edge &e = G[v][i], &re = G[e.dst][e.rev];
	    if (re.cap > 0 && len[v] > len[e.dst]) {
		Flow f = dfs(e.dst, s, min(c-ret, re.cap));
		ret += f;
		e.cap += f; re.cap -= f;
		if (ret == c) break;
	    }
	}
	return ret;
    }
    void bfs(int s) {
	len.assign(G.size(), -1);
	queue<int>qu;
	qu.push(s);
	len[s] = 0;
	for (;!qu.empty();) {
	    int v = qu.front(); qu.pop();
	    for (int i=0; i<(int)G[v].size(); i++) {
		const Edge &e = G[v][i];
		if (e.cap > 0 && len[e.dst] == -1) {
		    len[e.dst] = len[v] + 1;
		    qu.push(e.dst);
		}
	    }
	}
    }
    Flow _flow;
    Flow flow(int source, int sink, Flow limit=-1) {
	if (limit == -1) limit = INF;
	Flow ret = 0;
	while (true) {
	    bfs(source);
	    if (len[sink] == -1 || limit == 0) return _flow = ret;
	    iter.assign(G.size(), 0);
	    Flow tmp = dfs(sink, source, limit);
	    ret += tmp;
	    limit -= tmp;
	}
    }
};
const Dinic::Flow Dinic::INF;

int N;
int A[111];

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", A+i);

    int SRC = N, SNK = SRC+1;
    Dinic X(SNK+1);

    LL add = 0;
    REP (i, N) {
	if (A[i] >= 0) {
	    add += A[i];
	    X.add_edge(i, SNK, A[i]);
	} else {
	    X.add_edge(SRC, i, -A[i]);
	}
    }
    REP (b, N) REP (a, b) {
	int aval = a+1;
	int bval = b+1;
	if (bval % aval == 0) {
	    X.add_edge(a, b, X.INF);
	}
    }

    
    LL f = X.flow(SRC, SNK);
    LL ans = add - f;
    printf("%lld\n", ans);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 1000000000
using namespace std;
typedef pair<int,int> P;
struct edge{
    int to,cost;
};
int d[100000];
vector<edge> G[100000];
int main(){
    int v,e,r;
    scanf("%d %d %d",&v,&e,&r);
    for(int i=0;i<e;i++){
        int s,t,d;
        scanf("%d %d %d",&s,&t,&d);
        edge e;
        e.to=t; e.cost=d;
        G[s].push_back(e);
    }
    priority_queue<P,vector<P>,greater<P> > q;
    fill(d,d+v,INF);
    d[r]=0;
    q.push(P(0,r));
    while(!q.empty()){
        P p=q.top(); q.pop();
        int x=p.second;
        if(d[x]<p.first) continue;
        for(int i=0;i<G[x].size();i++){
            edge e=G[x][i];
            if(d[e.to]>e.cost+d[x]){
                d[e.to]=e.cost+d[x];
                q.push(P(d[e.to],e.to));
            }
        }
    }
    for(int i=0;i<v;i++){
        if(d[i]==INF) printf("INF\n");
        else printf("%d\n",d[i]);
    }
    return 0;
}

Measured memory_bytes: 11180
#include <iostream>
#include <string>

using namespace std;

class dice 
{
private:
	
public:
	dice(int array[]);
	void turnE();
	void turnN();
	void turnS();
	void turnW();
	void command(string com);
	void displayTop();
	int findRight(int top, int front);
	int num[7];
};

dice::dice(int array[])
{
	int i;
	for (i = 0; i < 6; i++)
		num[i + 1] = array[i];
}

void dice::command(string com)
{
	int len = com.length();
	int i;
	char ch;
	for (i = 0; i < len; i++)
	{
		ch = com.at(i);
		if (ch == 'E')
		{
			turnE();
			continue;
		}
		if (ch == 'N')
		{
			turnN();
			continue;
		}
		if (ch == 'W')
		{
			turnW();
			continue;
		}
		if (ch == 'S')
		{
			turnS();
			continue;
		}
	}
}

void dice::turnE()
{
	int temp;
	temp = num[6];
	num[6] = num[3];
	num[3] = num[1];
	num[1] = num[4];
	num[4] = temp;
}

void dice::turnN()
{
	int temp;
	temp = num[6];
	num[6] = num[5];
	num[5] = num[1];
	num[1] = num[2];
	num[2] = temp;
}

void dice::turnS()
{
	int temp;
	temp = num[6];
	num[6] = num[2];
	num[2] = num[1];
	num[1] = num[5];
	num[5] = temp;
}

void dice::turnW()
{
	int temp;
	temp = num[6];
	num[6] = num[4];
	num[4] = num[1];
	num[1] = num[3];
	num[3] = temp;
}

void dice::displayTop()
{
	cout << num[1] << endl;
}

int dice::findRight(int top, int front)
{
	int i;
	// find_front
	for (i = 1; i < 7 && num[i] != front; i++);
	if (i == 1)
		turnS();
	else if (i == 3)
	{
		turnW();
		turnS();
	}
	else if (i == 4)
	{
		turnE();
		turnS();
	}
	else if (i == 5)
	{
		turnS();
		turnS();
	}
	else if (i == 6)
	{
		turnN();
	}
	// now let the front to front

	for (i = 1; i < 7 && num[i] != top; i++);
	if (i == 4)
	{
		turnE();
	}
	else if (i == 6)
	{
		turnE();
		turnE();
	}
	else if (i == 3)
	{
		turnW();
	}

	return num[3];
}

int main(void)
{
	int array[6];
	int i;
	for (i = 0; i < 6; i++)
		cin >> array[i];
	dice dic1(array);

	for (i = 0; i < 6; i++)
		cin >> array[i];
	dice dic2(array);

	int flag = 0;
	int front = dic1.num[2];
	int top = dic1.num[1];
	int rightFind = dic2.findRight(top, front);
	if (rightFind == dic1.num[3])
	{
		front = dic1.num[6];
		top = dic1.num[5];
		rightFind = dic2.findRight(top, front);
		if (rightFind == dic1.num[4])
			flag = 1;
	}

	if (flag == 1)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;

}


Measured memory_bytes: 3116
#include"bits/stdc++.h"
using namespace std;
#define int long long
int32_t main()
{
 	int a,b,x; cin>>a>>b>>x;
  	if(a>x){
      cout<<"NO"<<endl;
      return 0;
    }
  	else if(a+b>=x or a==x) cout<<"YES"<<endl;
  	else cout<<"NO"<<endl;
  	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<iomanip>
#include<utility>
using namespace std;
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define rg register
#define il inline
#define lch(x) ((x)<<1)
#define rch(x) ((x)<<1^1)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define rep0(i,n) for(register int i=0;i<(n);++i)
#define per0(i,n) for(register int i=(n)-1;i>=0;--i)
#define rep(i,st,ed) for(register int i=(st);i<=(ed);++i)
#define per(i,ed,st) for(register int i=(ed);i>=(st);--i)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double dbl;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> il T qmin(const T &a,const T &b){return a<b?a:b;}
template<typename T> il T qmax(const T &a,const T &b){return a>b?a:b;}
template<typename T> il void getmin(T &a,const T &b){if(a>b) a=b;}
template<typename T> il void getmax(T &a,const T &b){if(a<b) a=b;}
il void fileio(string s){
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

const int inf=(int)1e9+7;
const ll linf=(ll)1e17+7;
const int N=1e5+7;

int a[N],ans=1,n;

int main(){
//	fileio("test");
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",a+i),ans^=a[i]&1;
	printf("%s\n",ans?"YES":"NO");
	return 0;
} 

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<ctype.h>
# define pb push_back
#define fst first
#define sec second
#define For(i,a,b) for(int i=a;i<b;i++)
#define ll long long int
#define ull unsigned long long int
#define mod 1000000007
#define fo(i,n) for(ll i=0;i<n;i++)
#define endl "\n"
#define rev(i,n) for(ll i=n-1;i>=0;i--)
#define fo1(i,n) for(ll i=1;i<=n;i++)
#define boolsize 1000001
#define pi pair<ll,ll>
#define vi vector<ll>
#define vii vector<pi>
using namespace std;
template<typename T>
void showvector(vector <T> v)
{
    for(T x:v)
        cout<<x<<" ";
    cout<<endl;

}
template<typename T>
void showvector1(vector <T> v)
{
    ll n=v.size();
    fo1(i,n-1)
        cout<<v[i]<<endl;

}
template<typename T>
void showset(set <T> s)
{
    for(T x: s)
        cout<<x<<" ";
    cout<<endl;
}
template<class T>
void showvectorpair(vector<T> v)
{
    for(auto it=v.begin();it!=v.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    cout<<endl;
}
template<typename T,typename P>
void showmap(map <T,P> m)
{
    for(auto it=m.begin();it!=m.end();it++)
        cout<<it->first<<" "<<it->second<<endl;
    cout<<endl;
}
template<typename T>
bool comp(T a,T b)
{
    return (a>b);
}
template<class T>
bool comppair(T a,T b)
{
    if(a.first==b.first)
        return(a.second>b.second);
    return (a.first>b.first);
}
bool sameparity(ll a,ll b)
{
    return (a%2==b%2);
}
bool difparity(ll a,ll b)
{
    return !(a%2==b%2);
}
bool isprime(ll x)
{   if(x<=1)
     return false;
    for(ll i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}
bool iseven(ll x)
{
    return !(x%2);
}
bool isodd(ll x)
{
    return (x%2);
}
/// check for test case before submitting
void vfun()
{
    ll n,k;
    cin>>n;
    vector <ll> v(n);
    fo(i,n)
    cin>>v[i];

}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("inputh.txt", "r", stdin);
    freopen("outputh.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0); ///cant use scanf, printf
    cin.tie(0);cout.tie(0); /// no longer auto flush cout before each cin, remove for interactive
    //cout << fixed << setprecision(11); /// no scientific output
    ll test=1;
   // cin>>test;
    while(test--)
    {
            ll n;
            cin>>n;
            vector <pair<ll,ll>> v(n);
            fo(i,n)
                cin>>v[i].fst>>v[i].sec;
            ll x,y,p1,p2,x1=v[0].fst,y1=v[0].sec;
            fo1(i,n-1)
            {
                p1=v[i].fst,p2=v[i].sec;
                x=(x1%p1==0)?x1/p1:x1/p1+1;
                y=(y1%p2==0)?y1/p2:y1/p2+1;
                ll m=max(x,y);
                x1=m*p1,y1=m*p2;

            }
            cout<<x1+y1<<endl;

//         if(vfun())
//            cout<<"YES\n";
//         else
//            cout<<"NO\n";
    }
}
///before sub
/// check for value of zero and single input in array
///loop vars,1LL in mult, equal, one, bounds, int v ll, endl, finish taking inputs
/// check whether test cases are given or not




Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod


#include <bits/stdc++.h>
using namespace std;
signed main(){
    int N; cin>>N;
    vec A(N);
    REP(i,N) cin>>A[i];
    int ans = 0;
    REP(i,N){
        if(A[A[i]-1]==i+1){
            ans ++;
        }
    }
    Out(ans/2);
}


Measured memory_bytes: 1024
/// @file

#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <string>

namespace {

bool run(std::istream& is, std::ostream& os);
}  // unnamed namespace

/// @brief エントリポイント
#ifdef _TEST
static int run()
#else
int main()
#endif
{
  try {
    if (run(std::cin, std::cout) == false) {
      std::cerr << "main funciton error.\n";
      return EXIT_FAILURE;
    }
  } catch (const std::exception& e) {
    std::cerr << "catch exception\n";
    std::cerr << e.what() << "\n";
    return EXIT_FAILURE;
  }

  return EXIT_SUCCESS;
}

namespace {

/// @brief 実行処理
bool run(std::istream& is, std::ostream& os)
{
  using Numeric_t = int;

  Numeric_t n;
  is >> n;

  // 解の公式を利用して部分集合の k を求める
  // N は 1 以上のため、 k が正の整数になるためには、 + 側のみ
  const double K_PLUS = (1. + std::sqrt(1. + 8. * n)) / 2.;

  // k が整数でなければ部分集合を作れない
  if ((K_PLUS - std::floor(K_PLUS)) != 0.) {
    os << "No\n";
    return true;
  }

  // 部分集合を作成する
  const Numeric_t K(K_PLUS);
  std::map<Numeric_t, std::set<Numeric_t>> sub;
  for (Numeric_t i = 1, sum = 0; i < K; ++i) {
    sum += i;
    sub[0].insert(sum);
  }
  for (Numeric_t i = 1, sum = 1; i < K; sum += i, ++i) {
    Numeric_t count(sum);
    for (Numeric_t j = 0; j < K - 1; ++j, ++count) {
      sub[i].insert(count);
      if (sub[0].find(count) != sub[0].end()) break;
    }
    for (Numeric_t j = i, vsum = i; count <= n; ++j) {
      count += vsum;
      if (count > n) break;
      ++vsum;
      sub[i].insert(count);
    }
  }

  os << "Yes\n";
  os << K << "\n";
  for (const auto& s: sub) {
    os << s.second.size();
    for (const auto& v: s.second) os << " " << v;
    os << "\n";
  }

  return true;
}
}  // unnamed namespace


Measured memory_bytes: 10752
#include <bits/stdc++.h>
#include <chrono>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

const int mod = 1e9+7;
const int N = 1e5+5;
int a[N];

int main()

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

    int n, k, x, ans = 0;

    cin >> n >> k;

    while (n--) {

        cin >> x;

        ans += min(x, k-x)*2;
    }

    cout << ans;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,ini,n) for(int i=ini;i<n;i++)
#define _rep(i,ini,n) for(int i=ini;i>=n;i--)
#define ToEnd(a) a.begin(),a.end()
uint64_t MOD=1000000007;

int main(){
    int a,b;cin>>a>>b;
    string s;cin>>s;

    string ans="Yes";
    rep(i,0,s.size()){
        char c=s.at(i);
        if(i==a && c!='-'){
            ans="No";
            break;
        }
        else if(i!=a && (c>'9' || c<'0')){
            ans="No";
            break;
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

#define all(a) (a).begin(), (a).end()

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

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

    string s; cin>>s;

    cout << (s[1] == 'B' ? "ARC" : "ABC") << endl;

    return 0;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define F(i,n) for(int i=0;i<n;i++)
#define G(i,j,n) for(int i=j;i<n;i++)
int main()
{
string n;
cin>>n;
ll sum=0;
F(i,n.size())
{
    sum+= n[i]-'0';
}
if(sum%9==0) cout<<"Yes";
else cout<<"No";

return 0;
}


Measured memory_bytes: 3748
N = int(input())
 
cnt = 0
ans = 'No'
for i in range(N):
	D1, D2 = map(int, input().split())
	if D1 == D2:
		cnt += 1
	else:
		cnt = 0
   
	if cnt > 2:
		ans = 'Yes'
		break
      
print(ans)

Measured memory_bytes: 62240
#include<bits/stdc++.h>
using namespace std;
#define int long long

int H,N;
vector<int> A, B;

vector<int> dp;

signed main() {
  cin >> H >> N;
  A.resize(N);
  B.resize(N);
  for(int i=0; i<N; i++) cin >> A[i] >> B[i];

  dp.resize(H+1, 1LL<<60);

  dp[0] = 0;
  for(int h=1; h<=H; h++) {
    for(int i=0; i<N; i++) {
      if(h<=A[i]) dp[h] = min(dp[h], B[i]);
      else        dp[h] = min(dp[h], dp[h-A[i]] + B[i]);
    }
  }
  cout << dp[H] << endl;
}

Measured memory_bytes: 384
n = int(input())
A = list(map(int, input().split()))

count1 = 0
count2 = 0
count4 = 0

for a in A:
    if a % 4 == 0:
        count4 += 1
    elif a % 2 == 0:
        count2 += 1
    else:
        count1 += 1

count4 -= count1
if count2:
    count4 -= 1

if count4 >= -1:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 14252
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

const int Cin()
{
    int n;
    cin >> n;
    return n;
}

const int DFS(const vector<vector<int>> &adList, const int v, const int rem, vector<bool> &hasNotVisited)
{
    // 残り長点数がゼロ＝全ての頂点を回り終えたら＋１する
    if (rem == 0)
    {
        hasNotVisited[v] = true;
        return 1;
    }
    // vに繋がる頂点のうち，未訪問の頂点へ移動
    int ans = 0;
    for (const int u : adList[v])
    {
        if (hasNotVisited[u])
        {
            hasNotVisited[u] = false;
            ans += DFS(adList, u, rem - 1, hasNotVisited);
            hasNotVisited[u] = true;
        }
    }
    return ans;
}

int main()
{
    // 始点が1に固定＆N≤1と小さいので
    // DFSを用いた全探索で間に合う
    int N = Cin(), M = Cin();
    vector<vector<int>> adList(N);
    for (int i = 0; i < M; ++i)
    {
        int ai = Cin() - 1, bi = Cin() - 1;
        adList[ai].push_back(bi);
        adList[bi].push_back(ai);
    }
    // DFS
    vector<bool> hasNotVisited(N, true);
    hasNotVisited[0] = false;
    cout << DFS(adList, 0, N - 1, hasNotVisited) << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	int a,b,c,m;
	scanf("%d %d %d\n",&a,&b,&c);
	if(a>c){
		m=a;
		a=c;
		c=m;}
	if(a>b){
		m=a;
		a=b;
		b=m;}
	if(b>c){
		m=b;
		b=c;
		c=m;}
	printf("%d %d %d\n",a,b,c);
	return 0;
}



Measured memory_bytes: 2100