akhauriyash/Code-Regression huggingface dataset:
//g++ main.cpp -I /usr/local/include/ac-library
#include<cmath>
//#include <atcoder/all>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
//using namespace atcoder;
stack<int> st;
queue<int> qu;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
#define ALL(a) a.begin(), a.end()
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define pb push_back
#define sz(x) (int)(x).size()
#define mod 1000000007
//#define mint=modint1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
typedef pair<int, int> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
ll N,K;

int main(){
    cin>>N>>K;
    ll ans = N - K + 1;
    vec a(N);
    rep(i,N) cin>>a[i];
    ll last = a[0], lid = 0;
    vector<bool> so(N,false);
    reps(i,1,N){
        if(last > a[i]){
            lid = i;
        }else if(i - K + 1 >= lid){
                so[i - K + 1] = true;
        }
        last = a[i];
    }
    set<ll> sub;
    reps(i,1,K) sub.insert(a[i]);
    reps(i,K,N){
        if((*sub.begin() > a[i-K]) && (sub.lower_bound(a[i]) == sub.end()) && (!so[i-K])){
            --ans;
        }
        sub.erase(a[i-K+1]);
        if(i != N-1) sub.insert(a[i]);
    }
    bool first = true;
    rep(i,N) {
        if(so[i]){
            if(first) first = false;
            else --ans;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 14124
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<queue>
#include<deque>
using namespace std;
typedef pair<int, int>P;
typedef pair<int, pair<int, int>>PP;
typedef long long ll;
ll inf = -1;

int main() {
	int p, q, r;
	cin >> p >> q >> r;
	cout << min(p + q, min(q + r, p + r)) << endl;
	return 0;
}

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

int INF=1e9;
int dp[30][60000];

int main(){
    int n,m;
    cin>>n>>m;
    int c[50];
    for(int i=0;i<m;i++) cin>>c[i];
    for(int i=0;i<=n;i++) dp[0][i]=INF;
    for(int i=0;i<=m;i++) dp[i][0]=0;

    for(int i=0;i<m;i++){
        for(int j=0;j<=n;j++){
            if(j<c[i]) dp[i+1][j]=dp[i][j];
            else{
                dp[i+1][j]=min(dp[i][j],dp[i+1][j-c[i]]+1);
            }
        }
    }
    cout<<dp[m][n]<<endl;
}


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

int main(void)
{
    long long H, W, K;
    cin >> H >> W >> K;
    vector<vector<char>> c(H,vector<char>(W));
    for (long long i = 0; i < H; i++)
    {
        for (long long j = 0; j < W; j++)
        {
            cin >> c[i][j];
        }
    }

    vector<long long> hcnt(H);
    vector<long long> wcnt(W);
    long long allcount = 0;
    for (long long i = 0; i < W; i++)
    {
        for (long long j = 0; j < H; j++)
        {
            if (c[j][i] == '#')
            {
                hcnt[j]++;
                wcnt[i]++;
                allcount++;
            }
        }
    }

    long long ans = 0;
    for (long long i = 0; i < pow(2, H); i++)
    {
        vector<long long> hcnt;
        long long cnt = 0;
        long long ia = i;
        long long hcount = 0;
        while(ia > 0)
		{
			if (ia & 1)
			{
			    hcnt.push_back(cnt);
                for (long long h = 0; h < W; h++)
                {
                    if (c[cnt][h] == '#')
                    {
                        hcount++;
                    }
                }
			}
            cnt++;
            ia >>= 1;
        }
        for (long long j = 0; j < pow(2,W); j++)
        {
            vector<long long> wcnt;
            long long cnt = 0;
            long long ja = j;
            long long wcount = 0;
            while(ja > 0)
		    {
			    if (ja & 1)
			    {
			        wcnt.push_back(cnt);
                    for (long long w = 0; w < H; w++)
                    {
                        if (c[w][cnt] == '#')
                        {
                            wcount++;
                        }
                    }
			    }
                cnt++;
                ja >>= 1;
            }
            long long hwcount = 0;
            for (long long a = 0; a < hcnt.size(); a++)
            {
                for (long long b = 0; b < wcnt.size(); b++)
                {
                    if (c[hcnt[a]][wcnt[b]] == '#')
                    {
                        hwcount++;
                    }
                }
            }
            if (allcount - hcount - wcount + hwcount == K)
            {
                ans++;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 4112
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m, a, b, A, B, C;
int main(){
	scanf("%d%d%d%d", &n, &m, &a, &b);
	if(n%a==0&&m%b==0){printf("No"); return 0;}
	printf("Yes\n");
	if(n%a){
		A=(n-1)/a+1; B=n-A; C=a-1;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++)printf("%d ", i%a==1?B+C:-A-1);
			printf("\n");
		}
		return 0;
	}
	A=(m-1)/b+1; B=m-A; C=b-1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++)printf("%d ", j%b==1?B+C:-A-1);
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1280
# ABC090C 3/18
#import numpy as np
#import math
def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def zeros(n): return [0]*n
def zeros2(n, m): return [zeros(m)]*n # obsoleted zeros((n, m))で代替
def getIntLines(n): return [int(input()) for i in range(n)]
def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros2(n, m)
    for i in range(n):
        mat[i] = getIntList()
    return mat
class Debug():
    def __init__(self):
        self.debug = True

    def off(self):
        self.debug = False

    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob():
    d = Debug()
    d.off()
    N, K = getIntList()
    d.dmp((N, K),'N,K')
    count = 0
    for b in range(K+1, N+1):
        q = N // b 
        r = N % b
        d.dmp((b, q, r),'b * q + r')
        count += q*(b-K)
        d.dmp((count),'count 1')
        if r > 0:
            if K == 0:
                count += r
            else:
                count += max(0, r-K+1)
        d.dmp((count),'count 2')
    d.dmp((count),'count')
    return count


ans = prob()
if ans is None:
    pass
elif type(ans) == list and ans[0] == 'col':
    for elm in ans[1]:
        print(elm)
else:
    print(ans)


Measured memory_bytes: 3064
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=0
d=[]
for i in range(n):
  d.append(0)
  
for i in range(n):
  if a[i]>=b[i]:
    c+=b[i]
  elif a[i]+a[i+1]>b[i]:
    c+=b[i]
    a[i+1]-=b[i]-a[i]
  else:
    c+=a[i]
    c+=a[i+1]
    a[i+1]=0
    
print(c)
    

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

using namespace std;

int main()
{
    int n;
    char s[200];
    char a[]="keyence";
    cin>>s;

    n=strlen(s);
    char *p=strstr(s,a);
    if(p)
    {
        if(p-s==0 || p-s==n-7)cout<<"YES";
        else cout<<"NO";
        return 0;
    }

    int ok=0,j=0,k=6;

    while(s[j]==a[j])
        j++;
    j--;
    while(s[--n]==a[k])
        k--;
    k++;
    if(j+7-k>=6)cout<<"YES";
    else cout<<"NO";
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
		public static void main(String[] args){
			
			Scanner sc=new Scanner(System.in);

			int n=sc.nextInt();
			
			LinkedList <Integer>[] tree=new LinkedList [n+1];
			for(int i=0;i<n+1;i++){
				tree[i]=new LinkedList();
			}
			
			LinkedHashMap<Integer, String> order=new LinkedHashMap<Integer, String>();
			HashMap<String, Integer> answer=new LinkedHashMap<String, Integer>();
			
			for(int i=0;i<n-1;i++){
				int a=sc.nextInt();
				int b=sc.nextInt();
				
				tree[a].add(b);
				tree[b].add(a);
				
				order.put(i, a+"-"+b);
				answer.put(a+"-"+b,i);
				
			}
	
			int deg=0;
			
			HashMap<Integer, Integer> visited=new HashMap<Integer, Integer>();
			
			LinkedList<Integer> que=new LinkedList<Integer>();
			que.add(1);
			
			int index=1;
			
			while(!que.isEmpty()){
				int v=que.pop();
				if(deg<tree[v].size())deg=tree[v].size();//最大次数の更新
				int curcolor=1;
				for(int u:tree[v]){
					if(visited.containsKey(u))continue;
					
					que.add(u);
					
					ArrayList<Integer> a= new ArrayList<Integer>();
					if(visited.containsKey(v)){
						while(visited.get(v)==curcolor){
						  curcolor++;
						}	
					}
					if(visited.containsKey(v)){
						visited.put(v,Math.max(visited.get(v),curcolor));
						}else{
						visited.put(v,curcolor);
					}
					if(visited.containsKey(u)){
						visited.put(u,Math.max(visited.get(u),curcolor));
						}else{
						visited.put(u,curcolor);
					}
					
					if(answer.containsKey(v+"-"+u)){
						answer.put(v+"-"+u, curcolor);
					}else{
						answer.put(u+"-"+v, curcolor);
					}
					
					curcolor++;
					
				}
			}
			
			System.out.println(deg);
			for(int i=0;i<n-1;i++){
				
				System.out.println(answer.get(order.get(i)));
				
			}
		
		}

  }






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

using namespace std;

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

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
    public static void main(String[] args ) throws Exception {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        int W = sc.nextInt();
        if(W >= S){
            System.out.println("unsafe");
        } else {
            System.out.println("safe");
        }
    }
}

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

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 1;
    for (int i = 0; i < s.size(); i++) {
        if (i && s[i] != s[i - 1]) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
# coding: utf-8
N,A,B,C=map(int,input().split())
L=[]
for i in range(N):
    L.append(int(input()))

def Base_10_to_n(X, base_n, len_N):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%base_n)+out
        X_dumy = int(X_dumy/base_n)
    return out.zfill(len_N)

ans=10**6

for i in range(4**N):
    bit=Base_10_to_n(i,4,N)
    group=[[] for j in range(4)]
    
    for j in range(N):
        group[int(bit[j])].append(L[j])
    
    if not(group[1]) or not(group[2]) or not(group[3]):
        continue
    
    costA = abs(A-sum(group[1])) + (len(group[1])-1)*10
    costB = abs(B-sum(group[2])) + (len(group[2])-1)*10
    costC = abs(C-sum(group[3])) + (len(group[3])-1)*10
    
    cost = costA + costB + costC
    
    ans=min(ans,cost)

print(ans)

Measured memory_bytes: 3064
import java.util.*;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Deque;


public class Main {
    static int count = 0;
    static boolean[] visited;
    static boolean[][] connected;
    
    public static void main(String[] args) throws Exception {
        // Your code here!
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);
        
        connected = new boolean[n][n];
        visited = new boolean[n];
        
        for (int i = 0; i < m; i++) {
            String[] fromTo = br.readLine().split(" ");
            int from = Integer.parseInt(fromTo[0])-1;
            int to = Integer.parseInt(fromTo[1])-1;
            connected[from][to] = true;
        }
        
        dfs(0);
        
        System.out.println(count);
        
    }
    
    static boolean all_visited = true;
    static void dfs(int n) {
        visited[n] = true;
        
        for (int i = 0; i < visited.length; i++) {
            if (visited[i] != true) {
                all_visited = false;
                break;
            }
        }
        
        if (all_visited) {
            count++;
            return;
        }
        
        all_visited = true;
        
        for (int i = 0; i < connected[n].length; i++) {
            if ((connected[n][i] || connected[i][n]) && !visited[i]) {
                dfs(i);
                visited[i] = false;
            }
        }
    }
}


Measured memory_bytes: 22868
#include <stdio.h>
#include <string.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <utility>
#include <queue>
#include <climits>
using namespace std;

#define endl '\n'
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define FORE(i, a, b) for(int i=(a); i<=(b); i++)
typedef pair<int, int> ii;
typedef long long LL;
typedef long double LD;

string s;

void solve(){
    for(int i=0; i<s.size(); i++) {
    	if(s[i] == 'C') {
    		for(int j=i+1; j<s.size(); j++) {
    			if(s[j] == 'F') {
    				cout << "Yes" << endl;
    				return;
    			}
    		}
    		break;
    	}
    }
    cout << "No" << endl;
}

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    while(cin >> s) {
    	solve();
    }
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
#AGC37 C

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop,heapify
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = LI()
h = []
for i in range(n):
    heappush(h,(-b[i],i))
ans = 0
while h:
    v,i = heappop(h)
    v = -v
    tmp = b[(i+1) % n] + b[i-1]
    if v == a[i]:
        continue
    s = (v - a[i])//tmp

    if s <= 0:
        print(-1)
        quit()

    ans += s
    v -= s*tmp
    b[i] = v
    if v != a[i]:
        heappush(h,(-v,i))
print(ans)


Measured memory_bytes: 122828
#include<iostream>
#include<utility>
#include<vector>

#define MOD 998244353
long long mod_div(long long a, long long b)
{
	if(a % b == 0)
	{
		return a / b;
	}
	long long tmp = MOD - 2, c = b, ret = 1;
	while(tmp > 0)
	{
		if(tmp & 1)
		{
			ret *= c;
			ret %= MOD;
		}
		c *= c;
		c %= MOD;
		tmp >>= 1;
	}
	return a * ret % MOD;
}

#define MAX_K 333333
long long combination(long long n, long long r)
{
	static std::vector<long long>kaijo(MAX_K);
	if(n < r || n < 0 || r < 0)
	{
		return -1;
	}
	if(kaijo[0] != 1)
	{
		kaijo[0] = 1;
		for(long long i = 1; i < MAX_K; i++)
		{
			kaijo[i] = (kaijo[i - 1] * i) % MOD;
		}
	}
	long long ret = kaijo[n];
	long long tmp = (kaijo[r] * kaijo[n - r]) % MOD;
	return mod_div(ret, tmp);
}

signed main()
{
	long long n, a, b, k;
	std::cin >> n >> a >> b >> k;
	std::vector<std::pair<long, long>>pairs;
	pairs.reserve(n);
	for(long long x = 0; x <= n; x++)
	{
		if((k - a * x) % b == 0)
		{
			long long y = (k - a * x) / b;
			if(0 <= y && y <= n)
			{
				pairs.push_back(std::make_pair(x, y));
			}
		}
	}
	long long ans = 0;
	for(auto i : pairs)
	{
		ans += combination(n, i.first) * combination(n, i.second) % MOD;
		ans %= MOD;
	}
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 6528
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
    // Your code here!
    while(1){
        int n;
        cin >> n;
        if(n == 0){
            break;
        }
        
        int s[n];
        for(int i = 0; i < n; i++){
            cin >> s[i];
        }
        
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += s[i];
        }
        
        double m = (double)sum / n;
        double sum2 = 0;
        for(int i = 0; i < n; i++){
            sum2 += pow(s[i] - m, 2);
        }
        
        cout << sqrt(sum2 / n) << endl;
    }
}



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

int main() {
	std::string S;
	int w;
	std::string answer;

	std::cin >> S >> w;

	for (std::string::size_type i = 0; i < S.size(); i++) {
		if (i%w == 0)
			answer += S[i];
	}

	std::cout << answer << std::endl;

	return 0;
}

Measured memory_bytes: 256
#include "iostream"
#include "vector"
#include "array"
#include "string"
#include "algorithm"
#include "functional"
#include <math.h>
#include "tuple"


using namespace std;
#define rep(p,q) for(int i = p;i < q;i++)


//B
int main(void) {

	int count[5]{ 0,0,0,0,0 };
	rep(0, 3) {
		int a, b;
		cin >> a >> b;
		count[a]++;
		count[b]++;
	}
	string ans = "YES";
	rep(1, 5) {
		if (count[i] == 0 || count[i] == 3) {
			ans = "NO";
			continue;
		}
	}
	cout << ans << endl;
}

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

int main() {
  int n;
  cin >> n;
  typedef map<string, int> INTMAP;
  INTMAP myMap;
  for (int i = 0; i < n; i++){
    string str;
    cin >> str;
    myMap[str]++;
  }
  int max = 0;
  vector<string> v;
  for (auto p: myMap) {
    auto key = p.first;
    auto value =  p.second;
    if (max == 0) {
      max = value;
      v.push_back(key);
    } else {
      if (max < value) {
        vector<string> s;
        s.push_back(key);
        v = s;
        max = value;
      } else if (max == value) {
        v.push_back(key);
      }
    }
  }
  sort(v.begin(), v.end());
  for (int i = 0; i < v.size(); i++){
    cout << v[i] << endl;
  } 
}

Measured memory_bytes: 27164
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<math.h>
using namespace std;
const int maxn=1010;
int n,m,vis[maxn][maxn],flag,sum,ans;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char ch[maxn][maxn];
struct node{
	int x,y,step;
};
queue<node>qu;
bool check(int x,int y){
	if(x>=0&&x<n&&y>=0&&y<m)
		return 1;
	return 0;
}
void bfs1(int x,int y){
	node no,po;
	no.x=x;no.y=y;no.step=0;
	vis[x][y]=1;
	qu.push(no);
	while(!qu.empty()){
		no=qu.front();
		qu.pop();
		//printf("%d %d %d\n",no.x,no.y,no.step);
		//printf("%d %d\n",po.x,po.y);
		if(no.x==n-1&&no.y==m-1){
			ans=no.step;
			return ;
		}
		for(int i=0;i<4;i++){
			int xx=dx[i]+no.x;
			int yy=dy[i]+no.y;
			if(check(xx,yy)&&vis[xx][yy]==0&&ch[xx][yy]!='#'){
				vis[xx][yy]=1;
				po.x=xx;
				po.y=yy;
				po.step=no.step+1;
				qu.push(po);
			}
		}
	}
}
int main(){
	int i,j;
	memset(vis,0,sizeof(vis));
	flag=1;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++){
		scanf("%s",ch[i]);
	}
	sum=0;
	ans=-1;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++)
			if(ch[i][j]=='.')
				sum++;
	}
	if(ch[0][0]=='#'){
		printf("-1\n");
		return 0;
	}
	bfs1(0,0);
	if(ans==-1){
		printf("-1\n");
		return 0;
	}
	printf("%d\n",n*m-(n*m-sum)-ans-1);
	return 0;
} 

Measured memory_bytes: 4224
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;

int main(){
	int n, m;
	cin>>n>>m;
	vector<string> s(n);
	rep(i, n) cin>>s[i];

	int di[4]={-1, 1, 0, 0};
	int dj[4]={0, 0, -1, 1};

	auto ind=[&](int i, int j){ return i*m+j; };

	mf_graph<int> mfg(n*m+2);
	rep(i, n) rep(j, m) if((i+j)%2==0) if(s[i][j]=='.'){
		rep(k, 4){
			int ti=i+di[k], tj=j+dj[k];
			if(0<=ti && ti<n && 0<=tj && tj<m) if(s[ti][tj]=='.'){
				mfg.add_edge(ind(i, j), ind(ti, tj), 1);
			}
		}
	}
	rep(i, n) rep(j, m) if((i+j)%2==0) mfg.add_edge(n*m, ind(i, j), 1);
	rep(i, n) rep(j, m) if((i+j)%2==1) mfg.add_edge(ind(i, j), n*m+1, 1);

	int ans=mfg.flow(n*m, n*m+1);
	for(auto e : mfg.edges()){
		if(e.flow){
			int a=e.from, b=e.to;
			if(a>b) swap(a, b);
			if(b>=n*m) continue;
			if(a/m==b/m){//yoko
				s[a/m][a%m]='>';
				s[b/m][b%m]='<';
			}
			else{
				s[a/m][a%m]='v';
				s[b/m][b%m]='^';
			}
		}
	}

	cout<<ans<<endl;
	rep(i, n) cout<<s[i]<<endl;
	return 0;
}


Measured memory_bytes: 5828
n, m, k = map(int, input().split())
par = [-1 for _ in range(n)]

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])  # 経路圧縮
        return par[x]

def same(x, y):
    return find(x) == find(y)

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    # サイズの大きい木にサイズの小さい木をくっつける。親の直下に親をくっつける。
    # 親のサイズは負の値になっているので、符号に注意
    if par[x] < par[y]:
        par[x] += par[y]
        par[y] = x
    else:
        par[y] += par[x]
        par[x] = y
    return True

friends_num = [0] * 100005
for _ in range(m):
    num_from, num_to = map(int, input().split())
    num_from -= 1
    num_to -= 1
    friends_num[num_from] += 1
    friends_num[num_to] += 1
    unite(num_from, num_to)

blocks = [[] * n for i in range(n)]
for _ in range(k):
    num_from, num_to = map(int, input().split())
    num_from -= 1
    num_to -= 1
    blocks[num_from].append(num_to)
    blocks[num_to].append(num_from)

ans_list = []
for i in range(n):
    ans = -par[find(i)] - friends_num[i] - 1
    for b in blocks[i]:
        if same(i, b):
            ans -= 1
    ans_list.append(ans)

print(' '.join(map(str, ans_list)))

Measured memory_bytes: 33300
dict1 = {" ":"101","'":"000000",",":"000011","-":"10010001",".":"010001","?":"000001","A":"100101","B":"10011010","C":"0101","D":"0001","E":"110","F":"01001","G":"10011011","H":"010000","I":"0111","J":"10011000","K":"0110","L":"00100","M":"10011001","N":"10011110","O":"00101","P":"111","Q":"10011111","R":"1000","S":"00110","T":"00111","U":"10011100","V":"10011101","W":"000010","X":"10010010","Y":"10010011","Z":"10010000",}
dict2 = {"00000":"A","00001":"B","00010":"C","00011":"D","00100":"E","00101":"F","00110":"G","00111":"H","01000":"I","01001":"J","01010":"K","01011":"L","01100":"M","01101":"N","01110":"O","01111":"P","10000":"Q","10001":"R","10010":"S","10011":"T","10100":"U","10101":"V","10110":"W","10111":"X","11000":"Y","11001":"Z","11010":" ","11011":".","11100":",","11101":"-","11110":"'","11111":"?"}

while True:
	try:
		code,decode = "",""
		inp = raw_input()
		for alph in inp:
			code += dict1[alph]
		if len(code)%5 != 0:
			code += "0"*(5-len(code)%5)
		for i in range(0,len(code),5):
			decode += dict2[code[i:i+5]]
		print decode
	except:
		break

Measured memory_bytes: 4324
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long x, long long y){
    if(x>y)swap(x,y);
    if(y%x==0)return x;
    else return gcd(y%x,x);
}
int main(void){
    int n;cin>>n;
    long long a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    long long g[n];//i番目を除いたn-1この整数の最大公約数
    long long r[n],l[n];
    /*
    r[i]=gcd(a[0),a[1],…,a[i]);
    l[i]=gcd(a[n-1],a[n-2],a[n-3],…,a[i]);
    g[n]=gcd(r[i],l[i]);
    */
    r[0]=a[0];l[n-1]=a[n-1];
    for(int i=1;i<n;i++){
        r[i]=gcd(r[i-1],a[i]);
        l[n-i-1]=gcd(l[n-i],a[n-1-i]);
    }
    g[0]=l[1];g[n-1]=r[n-2];
    for(int i=1;i<n-1;i++){
        g[i]=gcd(r[i-1],l[i+1]);
    }
    long long res=0;
    for(int i=0;i<n;i++){
        res=max(res,g[i]);
    }
    cout<<res<<endl;
}


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

using namespace std;

using ll = long long;

const long long MOD = 1e9+7;

#define ALL(A) A.begin(),A.end()

void ALLIN1_NUMBER(vector<ll>& V)
{
    for(auto& x : V)
    {
        cin >> x;
    }
}

void ALLOUT_NUMBER(vector<ll> V)
{
    ll N = V.size();
    for(ll i=0;i<N;i++)
    {
        cout << V[i];
        if(i<N-1) cout << ' ';
    }
    cout << endl;
}

class Mll
{
    public:
    ll x;

    Mll() : x(0){}
    Mll(ll x=0) : x((x%MOD+MOD)%MOD){}

    Mll operator-() const
    {
        return Mll(-x);
    }

    Mll& operator+=(const Mll& A)
    {
        if((x += A.x) >= MOD) x -= MOD;
        return *this;
    }
    Mll& operator-=(const Mll& A)
    {
        if((x += MOD - A.x) >= MOD) x -= MOD;
        return *this;
    }
    Mll& operator*=(const Mll& A)
    {
        (x *= A.x) %= MOD;
        return *this;
    }
    
    Mll operator+(const Mll& A)
    {
        Mll res(*this);
        return res+=A;
    }
    Mll operator-(const Mll& A)
    {
        Mll res(*this);
        return res-=A;
    }
    Mll operator*(const Mll& A)
    {
        Mll res(*this);
        return res*=A;
    }
    
    Mll pow(ll t) const // t乗
    {
        if(t==0) return 1;
        Mll A = pow(t>>1);
        A *= A;
        if(t&1) A *= *this;
        return A;
    }

    // for prime mod
    Mll inv() const
    {
        return pow(MOD-2);
    }
    Mll& operator/=(const Mll& A)
    {
        return (*this) *= A.inv();
    }
    Mll operator/(const Mll& A) const
    {
        Mll res(*this);
        return res/=A;
    }

    friend ostream& operator<<(ostream& os, const Mll& M)
    {
        os << M.x;
        return os;
    }
};

vector<Mll> ALLIN_MLL(ll N)
{
    vector<ll> numbers_ll(N);
    ALLIN1_NUMBER(numbers_ll);

    vector<Mll> numbers_Mll;
    for(ll i=0;i<N;i++)
    {
        Mll add(numbers_ll[i]);
        numbers_Mll.push_back(add);
    }

    return numbers_Mll;
}

template<class T>
void OUT0(T N)
{
    cout << N << endl;
}

static const double pi = acos(-1.0);

double Cos(double D)
{
    return cos(pi/180 * D);
}

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

    ll N_copy = N;

    string s;

    while(N!=0)
    {
        if(N%-2==0)
        {
            s.push_back('0');
            N/=-2;
        }
        else
        {
            s.push_back('1');
            N-=1;
            N/=-2;
        }
    }

    reverse(ALL(s));

    if(N_copy==0)
    {
        cout << '0' << endl;
    }
    else
    {
        cout << s << endl;
    }

    return 0;
}

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

int main() {
  int w,a,b; 
  cin >> w >> a >> b;
  
  if(b<a){
    int t = a;
    a = b; b = t;
  }
  
  if(a+w>=b) cout << 0 << endl;
  else cout << b-a-w << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int n,m;
  cin >> n >> m;
  int ans=0;
  rep(i,n+1)rep(j,n+1) {
    int z=m-i-j;
    if(z>=0&&z<=n) ans++;
  }
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
#include <cstdio>

using s32 = int;
using u32 = unsigned int;
using s64 = long long int;
using u64 = unsigned long long int;

u64 n;

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

  int ans = 0;
  for(int i = 2; i <= 1000000 && i <= n; ++i){
    int k = 0;
    int l = 1;
    int m = 1;
    while(n % i == 0){ n /= i; ++k; if(k == l){ ++ans;  ++m; l += m;} }
  }
  if(n != 1) ++ans;

  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 1736
# -*- coding: utf-8 -*-

"""
name: 153B.py
プログラムの説明
"""

def main():
    H,N = map(int, input().split())
    A = input().split()

    TotalA = 0
    for i in A:
        TotalA += int(i)
    
    if H>TotalA:
        print('No')
    else:
        print('Yes')

if __name__ == '__main__':
    main()

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

using namespace std;

int main(){
  char c;
  string boin = "aeiou";
  cin >> c;
  
  bool flag = false;
  
  for (const auto& i: boin){
    if (i == c){
      flag = true;
    }
  }
  if (flag) {
    cout << "vowel" << endl;
  }
  else {
    cout << "consonant" << endl;
  }
}

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 ff                  first
#define ss                  second
#define endl                "\n"
#define loop(i,s,e)         for(int i=s;i<e;i++)
// #define int                 long long
#define vi                  vector<int> 
#define S(v)                sort(v.begin(),v.end())
#define RS(v)               sort(v.rbegin(),v.rend())
#define R(v)                reverse(v.begin(),v.end())
#define mxpq(T)             priority_queue <T>
#define mnpq(T)             priority_queue<T,vector<T>,greater<T>>
#define prv(v)              for(auto &x : v)cout << x << " ";
#define piirv(v)            for(auto &x : v)cout << x.ff << " " << x.ss << endl;
#define prvv(v)             for(auto &x : v)for(auto &y : x.ss)cout << y << " ";
#define mp                  make_pair
#define pii                 pair<int,int>
#define mset(a,f)           memset(a , f , sizeof(a))
#define pb                  push_back
#define inf                 INT_MAX
#define INF                 LLONG_MAX
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;

const int N = 2e6 + 6;
int A[N];
int n;

#define pi 3.1415926535897932

void solve()
{
	long double l;
	cin >> l;

	cout << (2*(pi)*l);
}
 
int32_t main()
{
 
cout<<fixed<<setprecision(16);

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

 	int t = 1;
 	// cin >> t;
 	while(t--)solve();
  
}

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

using namespace std;

int main(){
  string str;
  cin >> str;
  if(str.length()==2){
    cout << str;
  }else{
    for(int i = 2; i >= 0; i--)
    {
      cout << str.c_str()[i];
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
using namespace std;
char map[110][110];
int ans[110][110];
int n, m;
int main() {
	scanf("%d%d", &n, &m);
	getchar();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) cin>>map[i][j];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			if(map[i][j]=='.') {
				if(map[i+1][j-1]=='#') ans[i][j]++;
				if(map[i+1][j]=='#') ans[i][j]++;
				if(map[i+1][j+1]=='#') ans[i][j]++;
				if(map[i][j-1]=='#') ans[i][j]++;
				if(map[i][j+1]=='#') ans[i][j]++;
				if(map[i-1][j-1]=='#') ans[i][j]++;
				if(map[i-1][j]=='#') ans[i][j]++;
				if(map[i-1][j+1]=='#') ans[i][j]++;
			}
			if(map[i][j]=='#') ans[i][j]=-1;
		}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			if(ans[i][j]!=-1) printf("%d", ans[i][j]);
			else printf("#");
			if(j==m) printf("\n");
		}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int N,W;
    int i,j;
    int list[10001][101];
    int v[101],w[101];
    scanf("%d %d",&N,&W);
    for(i=1;i<=N;i++)scanf("%d %d",&v[i],&w[i]);
    for(i=0;i<=N;i++)for(j=0;j<=W;j++)list[j][i] = 0;
    for(i=1;i<=N;i++){
        for(j=1;j<=W;j++){
            if(j>=w[i]){
                if(list[j-w[i]][i-1]+v[i] > list[j][i-1]){
                    list[j][i] = list[j-w[i]][i-1]+v[i];
                }else{
                    list[j][i] = list[j][i-1];
                }
            }else{
                list[j][i] = list[j][i-1];
            }
        }
    }
    printf("%d\n",list[W][N]);
}

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

int main(){
    int N;
    int d[102];
    long ans = 0;

    cin >> N;
    for(int i=0;i<N;i++) cin >> d[i];

    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            ans += d[i]*d[j];
        }
    }
    cout << ans << endl;

    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<int,int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

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

    ll n,x;cin>>n>>x;
    vector<ll> a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    ll cnt=0,res=0;
    sort(a.begin(),a.end());
    for(int i=0;i<n;i++){
        if(cnt+a[i]<=x){
            res++;
            cnt += a[i];
        }
    }
    if(res==n && cnt!=x) cout<<res-1<<endl;
    else cout<<res<<endl;
}


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

int main() {
  int a,b;
  cin >> a >> b;
  int c;
  if(b == 100){
    c = 1000*a + b;
  }
  else if(10 <= b  && b <= 99){
    c = 100*a + b;
  }
  else if(1 <= b && b <= 9){
    c = 10*a + b;
  }

  int d=0;
  for(int i=0;i <= 1000;i++){
    if(i*i==c){
      d++;
    }
  }
  
  if(d==0){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;
  }
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <numeric>

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

using namespace std;
using ll = long long int;
using ull = unsigned long long;

float myPower(int a, int n) { // aのn乗の計算
	float x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

int main() {
	ll n;
	cin >> n;
	ll sum = 0;
	for (ll i = 1; i <= n; i++) {
		if (i % 15 == 0) {
			continue;
		} else if (i % 3 == 0) {
			continue;
		} else if (i % 5 == 0) {
			continue;
		} else {
			sum += i;
		}
	}
	cout << sum << endl;
	return 0;
}

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

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, m, n) for (ll i = (m); i < (n); i++)
#define FORR(i, m, n) for (ll i = (m); i >= (n); i--)
#define INF 1e9
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl

int main(int argc, char const *argv[])
{
    ll n, m;
    cin >> n;
    string ss;
    vector<string> s(n);
    REP(i, n)
    {
        cin >> s[i];
    }
    cin >> m;
    vector<string> t(m);
    REP(i, m)
    {
        cin >> t[i];
    }
    ll point_max = 0;
    REP(i, n)
    {
        ll cnt1 = count(ALL(s), s[i]);
        ll cnt2 = count(ALL(t), s[i]);
        ll point = cnt1 - cnt2;
        if (point > point_max)
        {
            point_max = point;
        }
    }
    cout << point_max << endl;
    return 0;
}


Measured memory_bytes: 256
def examB():
    a, b , x = LI()
    ans = b//x - (a-1)//x
    print(ans)


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()

Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	int  N, M, X, Y;
	cin >> N >> M >> X >> Y;
	int x[101], y[101];

	for (int i = 1; i <= N; i++) {
		cin >> x[i];
	}
	for (int i = 1; i <= M; i++) {
		cin >> y[i];
	}
	sort(x + 1 , x + N + 1);
	sort(y + 1 , y + M + 1);
	if (x[N] < y[1] && x[N] > X && y[1] <= Y)cout << "No War";
	else cout << "War";
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
const ll INF = 1LL << 60;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a, b;
  cin >> a >> b;
  if ((a * b) & 1) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#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>;

int main() {
    int n;
    cin >> n;
    int t[n+1] = {}, x[n+1] = {}, y[n+1] = {};
    rep(i,n) cin >> t[i+1] >> x[i+1] >> y[i+1];
    bool ok = true;
    rep(i,n) {
        int shortest = abs(x[i] - x[i+1]) + abs(y[i] - y[i+1]);
        int time = t[i+1] - t[i];
        if (shortest > time || (time - shortest) % 2 == 1) ok = false;
    }
    string ans = "No";
    if (ok) ans = "Yes";
    cout << ans << endl;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#include<cmath>
#define pb push_back
#define ld long double
#define mp make_pair
#define vl vector<ll> 
#define vd vector<double>
#define vld vector<long double>
#define ll long long int
#define pl pair<ll, ll>
#define all(a) a.begin(), a.end()
#define forr(i, n) for(ll i=0; i<n; i++) 
#define forr1(i, n) for(ll i=1; i<=n; i++)
using namespace std;
const ld PI =3.1415926535897923846;
const ll MOD = 1e9+7;
void solve()
{
    ll a, b, c, d;
    cin>>a>>b>>c>>d;
    while(a>0&&c>0)
    {
        c-=b;
        if(c<=0)
        {
            cout<<"Yes";
            return;
        }
        a-=d;
        if(a<=0)
        {
            cout<<"No";
            return;
        }
    }
}
int main()
{
    ll test=1;
    //cin>>test;
    while(test--)
        solve();
}

Measured memory_bytes: 3632
#pragma GCC optimize ("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
#define all(x) x.begin(), x.end()
#define trav(i,a) for(auto &i:a) 
inline int in(){int x;scanf("%lld",&x);return x;}
int n;
int l[101];
int32_t main()
{
	n=in();
	for(int i=0;i<n;i++)l[i]=in();
	set<tuple<int,int,int>> s;
	//sort(l,l+n);
	for(int i=0;i<n;i++)
	for(int j=i+1;j<n;j++)
	for(int k=j+1;k<n;k++)
	{
		
		int a=l[i];int b=l[j];int c=l[k];
		if((a!=b) and (b!=c) and (c!=a))
		{
			
			if((a+b)>c and (c+b)>a and (a+c)>b)
			{
				s.insert({i+1,j+1,k+1});
			}
		}
	}
	cout<<s.size()<<"\n";
	
	
	
}

Measured memory_bytes: 13740
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
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 = 1LL <<60;
const int INF = 10000;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

const int MAX = 510000;
const int MOD = 1000000007;

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

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

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


//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始
int main(){
  int n;
  cin>>n;
  int d[n];
  for(int i = 0; i < n; i++)cin>>d[i];
  ll sum = 0;
  for(int i = 0; i < n-1; i++){
    for(int j = i+1; j < n; j++){
      sum+=d[i]*d[j];
    }
  }
  cout<<sum<<endl;
  return 0;
}


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

int main(){
    double a[1000000];
    int i = 0;
    while( scanf("%lf", a+i) != EOF ) i++;
    sort(a, a+i);
    printf("%lf\n", a[i-1] - a[0]);
    return 0;
}

Measured memory_bytes: 1096
#include <iostream>
#include <string>
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  int cnt = 0;
  rep(i, N-1) {
    if (S[i] == S[i+1]) ++cnt;
  }
  int ans = cnt + 2 * K;
  if (ans > N-1) ans = N-1;
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define x first
#define y second
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
#define pb push_back
#define rep(i, a, b) for(int i = a; i < b; i++)
#define mem(i) memset((i), (-1), (sizeof(i)))
#define all(i) (i).begin(), (i).end()
using namespace std;

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

const int MN = 3000;
int n, m;
string s, t;
int dp[MN][MN];

int LCS(int i, int j)
{
	if (i == n || j == m) return 0;
	int &ret = dp[i][j];
	if (ret != -1) return ret;

	ret = max(LCS(i + 1, j), LCS(i, j + 1));
	if (s[i] == t[j]) ret = max(ret, LCS(i + 1, j + 1) + 1);

	return ret;
}

void trace(int i, int j, string &ans)
{
	if (i == n || j == m) return;
	if (s[i] == t[j])
	{
		ans.pb(s[i]);
		trace(i + 1, j + 1, ans);
	}
	else
	{
		if (LCS(i + 1, j) > LCS(i, j + 1)) trace(i + 1, j, ans);
		else trace(i, j + 1, ans);
	}
}

int main()
{
	fastio;
	cin >> s >> t;
	n = s.size(); m = t.size();
	mem(dp);
	string ans = "";
	trace(0, 0, ans);
	cout << ans << '\n';
}

Measured memory_bytes: 35968
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;


int main(){

int n,m;
cin >> n >> m;

char a[n][n],b[m][m];

rep(i,n)rep(j,n)cin >> a[i][j];
rep(i,m)rep(j,m)cin >> b[i][j];

bool exist =false;
rep(i,n){
    rep(j,n){
        if(j+m-1>=n or i+m-1>=n) continue;
        bool match = true;
        rep(k,m){
            rep(l,m){
                if(a[i+k][j+l]!=b[k][l])match = false;
            }

        } 
        if(match)exist = true;  
     }
}

if(exist)cout << "Yes" << endl;
else cout << "No" << endl;


return 0;

}




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

using namespace std;
typedef long long int lli;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef pair <lli,lli> pii;
#define all(vec) vec.begin(),vec.end()
#define ff first
#define ss second
#define inf 4e18
#define MOD 1000000007
#define push_back emplace_back
#define pb push_back
#define for1(low,high,k) for(int i=low;i<high;i+=k)
#define for2(low,high,k) for(int j=low;j<high;j+=k)
#define rev(high,low,k) for(int i=high;i>=low;i-=k) 

int main(){
	fast;
	lli x;
	cin>>x;
	lli k=100;
	int c=0;
	while (k<x){
		k=k+k/100;
		c++;
	}
	cout<<c<<endl;
}

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

string board[50];
int main(){
    int H,W; cin >> H >> W;
    rep(i,H) cin >> board[i];
    
    const int dx[8]={1,1,0,-1,-1,-1,0,1};
    const int dy[8]={0,1,1,1,0,-1,-1,-1};
    
    rep(i,H){
        rep(j,W){
            if(board[i][j]=='.'){
                int cnt=0;
                rep(k,8){
                    int x=i+dx[k];
                    int y=j+dy[k];
                    if(x>=0 && x<H && y>=0 && y<W && board[x][y]=='#'){
                        cnt++;
                    }
                    board[i][j]='0'+cnt;
                }
            }
        }
    }
    for (int i=0; i<H; i++) cout << board[i] << endl;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
su=0
c=[]
for i in range(n):
    x=a[i]-b[i]
    if x>=0:
        su += x
    else:
        c.append(-x)
cap=0
for i in range(len(c)):
    cap += c[i]//2
if cap>=su:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 4596
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

y=0
for i in b:
    y+=i
#print(y)

x=0
for j in range(n-1):
    if a[j]-a[j+1]==-1:
        
        x+=c[(a[j])-1]
#print(x)

print(x+y)

Measured memory_bytes: 3064
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
p = [0] * (n+1)
c = 0
penalty = [0] * (n+1)
ans2 = 0
for _ in range(m):
    ps = stdin.readline().rstrip().split(" ")
    pi, si = int(ps[0]), ps[1]
    if p[pi]==0:
        if si == "AC":
            p[pi] = 1
            ans2 += penalty[pi]
        else:
            penalty[pi]+=1
print(sum(p), ans2)
        


Measured memory_bytes: 5204
#include <iostream>

using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	bool h = false;
	for (int i = 1; i < 110; i++) {
		if ((i * a) % b == c) {
			h = true;
			break;
		}
	}

	if (h) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

long long max(long long a,long long b){
	if(a>b)return a;
	else return b;
}
long long min(long long a,long long b){
	if(a<b)return a;
	return b;
}
int main(){
	long long n,m;
	cin>>n>>m;
	cout<<min(n,m/2)+max(0,m-2*n)/4<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>
#define INF 100000000
#define INFLL (long long)1e14
#define Loops(i, n) for(int i = 0; i < (int)n; i++)
#define Loops1(i, n) for(int i = 1; i <= (int)n; i++)
int mem[200000];
int main(void){
	int n;
	std::cin>>n;
	Loops(i,200000){
		mem[i]=0;
	}
	Loops(i,n){
		int x;
		std::cin>>x;
		mem[x]++;
	}
	int numcard=0;
	int ryousicard=0;
	Loops(i,100001){
		if(mem[i]!=0)numcard++;
		if(mem[i]>=2)ryousicard+=mem[i]-1;
	}
	if(ryousicard%2==0){
		std::cout<<numcard<<std::endl;
	}else {
		std::cout<<numcard-1<<std::endl;
	}
	return 0;
}

Measured memory_bytes: 1024
var
    a,b:int64;
begin
    read(a,b);
    if (a<0) and (0<b) or (a*b=0) then writeln('Zero')
    else if (a>0) or (b<0) and ((b-a+1) mod 2=0) then writeln('Positive')
        else writeln('Negative');
end.

Measured memory_bytes: 128
n = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

list = [a,b,c,d,e]
list.sort()

div = list[0]

q = n // div
p = n % div

if p != 0:
    print(5+q)
else:
    print(4+q)

Measured memory_bytes: 3064