akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

N = int(input())

a = int_mtx(N)
visit = [0]*(N+1)
now = 1
visit[now] = 1

ans = 0

for i in range(0,N):
    ans += 1
    now = a[now-1][0]
    if now == 2:
        print(ans)
        exit()
    if visit[now] == 1:
        print(-1)
        exit()
    visit[now] = 1







Measured memory_bytes: 41208
#include <bits/stdc++.h>
		using namespace std;
		typedef long long ll;
		#define PI 3.14159265358979
		#define EPS 1e-8
		#define mod  998244353
		#define fi first
		#define se second
		#define mp make_pair
		#define pb push_back
		#define endl "\n"
			 
		const ll INF=1e15;	
		const int N=2e5+50;
		 

		 
		long long binpow(long long a, long long b, long long m) {
			a %= m;
			long long res = 1;
			while (b > 0) {
				if (b & 1)
					res = res * a % m;
				a = a * a % m;
				b >>= 1;
			}
			return res;
		}
		
		ll modinverse(ll a,ll m)
		{
			return binpow(a,m-2,m);
		}
		ll fact[N];
		ll ncr(ll n,ll r)
		{
			return fact[n]*modinverse(fact[r],mod) % mod * modinverse(fact[n-r],mod) %mod;
		}
		
		int main()
		{
			ios_base::sync_with_stdio(false);
			cin.tie(NULL);cout.tie(0);
			
			fact[0]=fact[1]=1;
			
			for(ll i=2;i<=2e5;i++)
			{
				fact[i]= i* fact[i-1];
				fact[i]%=mod;
			}
			
			ll n,m,k;
			cin>>n>>m>>k;
			ll ans=0;
			for(ll i=0;i<=k;i++)
			{
				ans+= m* binpow(m-1,n-i-1,mod)%mod * ncr(n-1,i)%mod;
				ans%=mod;
			}
			cout<<ans;
			
			
			
		}
			
			
		


Measured memory_bytes: 5232
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cstring>
#define MAX 1000001

typedef long long ll;

using namespace std;

int m;
int table[2000][2000]={{0,0}};
int dp[2000][2000]={{0, 0}};
int dx[4]={0, 1, 0, -1};
int dy[4]={1, 0, -1, 0};
bool prime[MAX]; 
pair<int, int>coord[MAX];//座標
pair<int, int> ans;// <素数の数, 出口の番号>


void dfs(int count, int y, int x){
	int n = table[y][x];
	if(n <= 0 || m < n) return;

	if(count < dp[y][x] || (count == dp[y][x] && prime[n] == false && dp[y][x] !=0)) return;
	dp[y][x] = count;
	if(prime[n] == true){
		count++;
		dp[y][x] = count;
		if(ans.first < count || (ans.first == count && ans.second < n)){
			ans.first = count;
			ans.second = n;
		}
	}

	for(int dx=-1; dx<=1; dx++){
		dfs(count, y+1, x+dx);
	}
}


int main(void){
	fill(prime, prime+MAX, true);
	prime[0] = prime[1] = false;
	for(int i=2; i<MAX; i++){
		if(prime[i]){
			for(int j=i+i; j<MAX; j+=i){
				prime[j] = false;
			}
		}
	}

	int d=0;
	int x=1000, y=1000;
	for(int i=1; i<MAX; i++){
		table[y][x] = i;
		coord[i] = make_pair(y, x);
		if(table[y+dy[(d+1)%4]][x+dx[(d+1)%4]] == 0) d++;
		x += dx[d%4];
		y += dy[d%4];
	}

	while(1){
		int n; cin >> m >> n;
		if(!m && !n) break;

		int y = coord[n].first;
		int x = coord[n].second;
		fill(dp[0], dp[2000], 0);
		ans = make_pair(0,0);
		dfs(0, y, x);
		cout << ans.first << " " << ans.second << endl;
	}

	return 0;
}


Measured memory_bytes: 35336
// 愚直に2重ループ
//
//   https://kimiyuki.net/writeup/algo/atcoder/arc-092-d/
// で紹介されている
//   https://atcoder.jp/contests/arc092/submissions/2242270
//   https://atcoder.jp/contests/arc092/submissions/2251371
// を参考に、
//   #pragma GCC optimize ("-O3", "unroll-loops")
//   __attribute__((target("avx")))
// を指定した
// ("avx2"の指定だとRE)

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int As[200000];
int Bs[200000];

#pragma GCC optimize ("-O3", "unroll-loops")

__attribute__((target("avx"))) int main(void)
{
    cin.sync_with_stdio(false);
    int N;
    scanf("%d", &N);
    REP(n, N) scanf("%d", &As[n]);
    REP(n, N) scanf("%d", &Bs[n]);

    int ans = 0;
    int i = 0;
    for( ; i < (N / 8) * 8; i += 8) {
        // ここで明示的にSIMD命令を使うべきか？
        int a0 = As[i];
        int a1 = As[i + 1];
        int a2 = As[i + 2];
        int a3 = As[i + 3];
        int a4 = As[i + 4];
        int a5 = As[i + 5];
        int a6 = As[i + 6];
        int a7 = As[i + 7];
        for(int j = 0; j < N; j++) {
            int b = Bs[j];
            ans ^= a0 + b;
            ans ^= a1 + b;
            ans ^= a2 + b;
            ans ^= a3 + b;
            ans ^= a4 + b;
            ans ^= a5 + b;
            ans ^= a6 + b;
            ans ^= a7 + b;
        }
    }
    for( ; i < N; i++) {
        int a = As[i];
        for(int j = 0; j < N; j++) {
            ans ^= a + Bs[j];
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
#include <iostream>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
 
#define debug(format, ...) printf(format, __VA_ARGS__);

int N, K;
const int K_ = 2050;
int tb[K_][K_];

void add (int x1, int x2, int y1, int y2) {
  if(x1 >= 2*K) {
    x1 -= 2*K;
    x2 -= 2*K;
  }
  if(y1 >= 2*K) {
    y1 -= 2*K;
    y2 -= 2*K;
  }
  if(y2 > 2*K) {
    add(x1, x2, 0, y2-2*K);
    y2 = 2*K;
  }
  if(x2 > 2*K) {
    add(0, x2-2*K, y1, y2);
    x2 = 2*K;
  }
  tb[x1][y1] += 1;
  tb[x1][y2] -= 1;
  tb[x2][y1] -= 1;
  tb[x2][y2] += 1;
}

int main() {
#ifdef IN_MY_COMPUTER
  freopen("d.in", "r", stdin);
#endif
  scanf("%d%d", &N, &K);
  for(int i = 0; i < N; i++) {
    int x, y; char c[3]; scanf("%d%d%s", &x, &y, c);
    x %= 2*K;
    y %= 2*K;
    if(*c != 'B') {
      // [x, x+K) x [y, y+K)
      // [x+K, x+2K) x [y+K, y+2K)
      add(x, x+K, y, y+K);
      add(x+K, x+2*K, y+K, y+2*K);
    }else {
      // [x, x+K) x [y+K, y+2K)
      // [x+K, x+2K) x [y, y+K)
      add(x, x+K, y+K, y+2*K);
      add(x+K, x+2*K, y, y+K);
    }
  }


  for(int x = 0; x <= 2*K; x++) {
    for(int y = 0; y <= 2*K; y++) {
      tb[x][y] += (y > 0 ? tb[x][y-1] : 0)
                      + (x > 0 ? tb[x-1][y] : 0) 
                      - (x > 0 && y > 0 ? tb[x-1][y-1] : 0);
    }
  }

  int ans = 0;
  for(int x = 0; x < 2*K; x++) {
    for(int y = 0; y < 2*K; y++) {
      ans = max(ans, tb[x][y]);
    }
  }

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

Measured memory_bytes: 16640
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const int MOD = 1e9 + 7;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k; cin >> n >> k;
    string s; cin >> s;
    k--;
    if(s[k] >= 'A' and s[k] <= 'Z') s[k] += 'a' - 'A';
    cout << s << endl;
    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  
  int H,N,A[100001],i,sum=0;
  scanf("%d %d",&H,&N);
 for(i=0;i<N;i++){
   scanf("%d",&A[i]);
   sum+=A[i];
 }
  if(sum>=H) printf("Yes");
  else printf("No");
    return 0;
}

Measured memory_bytes: 512
////////////////////////////////////////////////////////////////////
// This source code is for Visual Studio
////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <stack>
#include <functional>
#include <iomanip>
#include <string>
#include <cstring>
#include <deque>
#include <math.h>
#include <assert.h>

#define	numberof(a)	(sizeof(a) / sizeof(a[0]))
#define	INF32		INT32_MAX
#define	INF64		INT64_MAX
#define Rep(i,n) for(int i = 0; i < (n); ++i )

using namespace std;

typedef vector< vector<int> > MAT;
typedef pair<int, int> PINT;
typedef long long ll;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int32_t s32;
typedef int64_t s64;

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

// main function
int main()
{
	string ans = "NO";
	string S = "";
	string keyence = "keyence";

	cin >> S;
	int len = S.length();
	int i = 0;

	if (S.substr(0, 7) == keyence) {
		ans = "YES";
	}
	else if (S.substr(len - 7, 7) == keyence) {
		ans = "YES";
	}
	else {
		int same_len = 0;
		for (i = 0; i < 7; ++i) {
			if (S[i] != keyence[i]) {
				same_len = i;
				break;
			}
		}
		int remain_len = keyence.length() - same_len;
		for (i = 0; i < remain_len; ++i) {
			//printf("%c - %c \n", S[len - remain_len + i], keyence[same_len + i]);
			if (S[len - remain_len + i] != keyence[same_len + i]) {
				break;
			}
		}
		same_len += i;
		if (same_len == keyence.length()) ans = "YES";
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque
inf = 10 ** 15
mod = 10 ** 9 + 7
s = input()
n = len(s)
stack = []
for c in s:
    if c == 'S':
        stack.append(c)
    if c == 'T':
        if stack:
            if stack.pop() == 'T':
                stack.append('T')
                stack.append(c)
        else:
            stack.append(c)
print(len(stack))

Measured memory_bytes: 49120
#include<bits/stdc++.h>
using namespace std;
typedef long  long int ll;
int main(){
    
    string s;
    cin>>s;
    if(s[2]==s[3] && s[5]==s[4])
    {
        cout<<"Yes"<<"\n";
    }
    else
    {
        cout<<"No"<<"\n";
    }
    
}

Measured memory_bytes: 256
n = int(input())

# initial observation
cur_min = int(input())
max_diff = -1 * (10**9) - 1

for i in range(n - 1) :
    num = int(input())
    
    max_diff = max(max_diff, num - cur_min)
    
    if num < cur_min :
        cur_min = num
    
print(max_diff)


Measured memory_bytes: 5612
#n, m = gets.chomp.split.map(&:to_i)
#ary = []; n.times { cakes << gets.chomp.split.map(&:to_i).to_a } 
#def cb(i);	i==1 ? 1 : -1;end
n = gets.chomp.to_i.to_s
l = n.length
min = 1000
0.step(l-3,1) {|i|
   min = (753 - n[i,3].to_i).abs < min ? (753 - n[i,3].to_i).abs : min
}
p min

Measured memory_bytes: 1788
/* ITP1_9_B: Shuffle */

#include <iostream>
#include <string>
using std::string;

int main() {
    std::ios::sync_with_stdio(false);
    string cards, subcards;
    int n_shuffles, length;

    while(std::cin) {
        std::cin >> cards;
        if (cards == "-") break;

        std::cin >> n_shuffles;
        for (int i = 0; i < n_shuffles; i++) {
            std::cin >> length;
            subcards = cards.substr(0, length);
            cards = cards.substr(length) + subcards;
        }
        std::cout << cards << "\n";
    }

    return 0;
}

Measured memory_bytes: 1208
n=int(input())

if n<600:
    print(8)
    exit()
    
if n<800:
    print(7)
    exit()
    
if n<1000:
    print(6)
    exit()
    
if n<1200:
    print(5)
    exit()
    
if n<1400:
    print(4)
    exit()
    
if n<1600:
    print(3)
    exit()
    
if n<1800:
    print(2)
    exit()
    
if n<2000:
    print(1)
    exit()

Measured memory_bytes: 9184
/* Dsingh_24 */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ios	    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define N  100005
ll n,x,y;
vi a[N];
ll dp[N][2];
ll dfs(ll node,ll p){
	for(auto i:a[node]){
		if(i!=p){
			//cout<<"node="<<node<<" "<<dp[node][0]<<" "<<dp[node][1]<<"\n";
			dfs(i,node);
			dp[node][0]*=((dp[i][0]+dp[i][1])%hell);
			dp[node][0]%=hell;
			dp[node][1]*=dp[i][0];
			dp[node][1]%=hell;
		}
	}
	if(a[node].size()==1&&p!=0)
		dp[node][0]=1,dp[node][1]=1;
}
int main()
{
	ios
	cin>>n;
	ll i,j;
	if(n==1){cout<<"2";return 0;}
	for(i=0;i<n-1;i++){
		cin>>x>>y;
		a[x].pb(y);
		a[y].pb(x);
	}
	for(i=0;i<N;i++)
		for(j=0;j<2;j++)
			dp[i][j]=1;
	dfs(1,0);
	cout<<(dp[1][0]+dp[1][1])%hell;
	return 0;
}

Measured memory_bytes: 14208
#include <iostream>
#include <map>
using namespace std;
typedef pair<string, string> P;
typedef long long ll;
map<P, ll> p,q;
int main(void){
    int n;
    ll m=0;
    string s;
    cin>>n>>s;
    for(int i=0;i<(1<<n);i++){
        string a="",b="",c="",d="";
        for(int j=0;j<n;j++){
            if(((i>>j)&1)==1){
                a+=s[j];
                c+=s[n*2-1-j];
            }else{
                b+=s[j];
                d+=s[n*2-1-j];
            }
        }
        p[P(a, b)]++;
        q[P(c, d)]++;
    }
    for(auto x=p.begin();x!=p.end();x++){
        m+=(x->second)*q[(x->first)];
    }
    cout<<m<<endl;
}


Measured memory_bytes: 108288
import sys
l = sys.stdin.readlines()
n, m = (int(x) for x in l[0].split())

from_1, to_n = set(), set()
for a, b in ((int(x) for x in l[i].split()) for i in range(1, m+1)):
    if a == 1: from_1.add(b)
    elif b == n: to_n.add(a)

print("POSSIBLE" if from_1 & to_n else "IMPOSSIBLE")


Measured memory_bytes: 33132
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n=sc.nextInt();
    int a[]=new int[n];
    for(int i=0;i<n;i++){
        a[i]=sc.nextInt();
    }
    Arrays.sort(a);
    System.out.println(a[n/2]-a[n/2-1]);
  }
}

Measured memory_bytes: 52844
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <algorithm>
#include <cmath>
#include <iomanip>
 
 
int main()
{
    int a, b, c, x, y;
    std::cin >> a >> b >> c >> x >> y;
    int mi = INT32_MAX;

    for(int i=0; i<=std::max(x, y); i++)
    {
        mi =  std::min(mi, 2 * c * i + a * std::max(x-i, 0) + b * std::max(y-i, 0));
    }

    std::cout << mi << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int BIG = 2e9 + 55;
const int maxN = 200 + 5;

int n;
int a[maxN];
int memo[maxN][maxN];
bool calc[maxN][maxN];

int dp(int i, int curH){
    if(i == n){
        return (curH != a[i]);
    }

    if(calc[i][curH]){
        return memo[i][curH];
    }

    int ans = n;
    for(int nxtH = 1; nxtH < maxN; nxtH++){
        if(curH != nxtH){
            ans = min(ans, dp(i + 1, nxtH) + (curH != a[i]));
        }
    }

    calc[i][curH] = true;
    return (memo[i][curH] = ans);
}

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

    cin >> n;

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

    int mn = n;

    for(int curH = 1; curH < maxN; curH++){
        mn = min(mn, dp(1, curH));
    }

    cout << mn << '\n';

    return 0;
}

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

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

Measured memory_bytes: 3572
h,w=map(int,input().split())
from collections import Counter
c=Counter()
for i in range(h):
    s=list(input())
    c+=Counter(s)

if h==1 and w==1:
    print("Yes")
elif h==1:
    s2=w//2
    for k,v in c.items():
        c[k]-=2*(v//2)
        s2-=v//2
    if s2==0:
        print("Yes")
    else:
        print("No")
elif w==1:
    s2=h//2
    for k,v in c.items():
        c[k]-=2*(v//2)
        s2-=v//2
    if s2==0:
        print("Yes")
    else:
        print("No")
else:
    s4=((w//2)*(h//2))
    s2=0
    if w%2 and h%2:
        s2=(h+w-2)//2
    elif w%2:
        s2=(h//2)
    elif h%2:
        s2=w//2
    for k,v in c.items():
        s4-=v//4
        c[k]-=4*(v//4)
        s2-=c[k]//2
        c[k]-=2*(c[k]//2)
    if s4==0 and s2==0:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 39664
using System;

class Program
{
  static void Main()
  {
    string[] input = Console.ReadLine().Split(' ');
    int N = int.Parse(input[0]);
    int M = int.Parse(input[1]);
   	string[] input2 = Console.ReadLine().Split(' ');
    int[] nums = new int[M];
    int[] cost = new int[M - 1];
    
    for(int i = 0; i < M; i++)
      nums[i] = int.Parse(input2[i]);
    Array.Sort(nums);
    for(int j = 0; j < M - 1; j++)
    {
      cost[j] = nums[j + 1] - nums[j]; 
    }
    Array.Sort(cost);
    int ans = nums[M - 1] - nums[0];
    Array.Reverse(cost);
    int count = Math.Min(M, N);
    for(int k = 0; k < count - 1; k++)
    {
       ans -= cost[k];
    }
    Console.WriteLine(ans);
  }
}

Measured memory_bytes: 19552
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
#pragma GCC optimize ("Ofast")
#define ll long long
#define pll pair<long long,long long>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define forn(i, n) for(int i=0; i<int(n); i++)
#define Forn(i, n) for(int i=1; i<=int(n); i++)

using namespace std;

/*#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;*/


int main()
{
    cin.tie(0);ios_base::sync_with_stdio(false);
    int k;
    string s;
    cin >> k >> s;
    if(s.size()<=k) cout << s << endl;
    else
    {
        forn(i, k) cout << s[i];
        cout << "..." << endl;
    }
}



Measured memory_bytes: 3644
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

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

  int n;
  cin>>n;
  if(n%2==0){
    cout<<n/2-1<<endl;
  }else{
    cout<<n/2<<endl;
  }
  



  return 0;
}


Measured memory_bytes: 384
import java.util.*;
import java.io.*;

public class Main {

  private static void solve() {
    int n = nextInt();

    double[] p = new double[n];

    for (int i = 0; i < n; i++) {
      p[i] = nextDouble();
    }

    double[][] dp = new double[n][n + 1];

    dp[0][0] = 1 - p[0];
    dp[0][1] = p[0];

    for (int i = 1; i < n; i++) {
      for (int j = 0; j <= n; j++) {
        dp[i][j] = dp[i - 1][j] * (1 - p[i]) + (j == 0 ? 0 : (dp[i - 1][j - 1] * p[i]));
      }
    }

    double ans = 0;
    for (int i = n / 2 + 1; i <= n; i++) {
      ans += dp[n - 1][i];
    }

    System.out.println(ans);
  }

  private static void run() {
    br = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(System.out);

    solve();

    out.close();
  }

  private static StringTokenizer st;
  private static BufferedReader br;
  private static PrintWriter out;

  private static String next() {
    while (st == null || !st.hasMoreElements()) {
      String s;
      try {
        s = br.readLine();
      } catch (IOException e) {
        return null;
      }
      st = new StringTokenizer(s);
    }
    return st.nextToken();
  }

  private static double nextDouble() {
    return Double.parseDouble(next());
  }

  private static int nextInt() {
    return Integer.parseInt(next());
  }

  private static long nextLong() {
    return Long.parseLong(next());
  }

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

Measured memory_bytes: 132564
#include "bits/stdc++.h"
using namespace std;

int main() {
	vector<int> A, B;
	for (int i = 1; ; i++) {
		int j = (i * (i + 1) * (i + 2)) / 6;
		if (j >= 1000000) break;
		A.push_back(j);
		if (j % 2 == 1) B.push_back(j);
	}
	vector<int> DPA(1000000, 1000000), DPB(1000000, 1000000);
	DPA[0] = 0, DPB[0] = 0;
	for (int i = 0; i < A.size(); i++) {
		int X = A[i], Y = 1;
		while (1) {
			for (int j = 0; j < 1000000; j++) {
				if (j + X < 1000000) {
					DPA[j + X] = min(DPA[j + X], DPA[j] + Y);
				}
			}
			X <<= 1, Y <<= 1;
			if (X >= 1000000) break;
		}
	}
	for (int i = 0; i < B.size(); i++) {
		int X = B[i], Y = 1;
		while (1) {
			for (int j = 0; j < 1000000; j++) {
				if (j + X < 1000000) {
					DPB[j + X] = min(DPB[j + X], DPB[j] + Y);
				}
			}
			X <<= 1, Y <<= 1;
			if (X >= 1000000) break;
		}
	}
	int N;
	while (cin >> N) {
		if (N == 0) return 0;
		cout << DPA[N] << " " << DPB[N] << endl;
	}
}


Measured memory_bytes: 10644
N,M=input().split()
from math import factorial 
if int(N)>=2 and int(M)>=2:
    print('{:.0f}'.format(factorial(int(N))/2/factorial(int(N)-2)+factorial(int(M))/2/factorial(int(M)-2)))
elif int(N)<2 and int(M)>=2:
     print('{:.0f}'.format(factorial(int(M))/2/factorial(int(M)-2)))
elif int(M)<2 and int(N)>=2:
     print('{:.0f}'.format(factorial(int(N))/2/factorial(int(N)-2)))
else:
    print("0")

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

int main(){
  int N;
  int a[12] = {1,6,9,36,81,216,729,1296,6561,7776,46656,59049};
  int dp[100010]; //dp[n] 和がnとなる場合の数
  int i,j;
  int a_j;
  cin >> N;
  for(i=2;i<=N;i++){
    dp[i] = 100000;
  }
  dp[1] = 1;
  for(i=1;i<=N+1;i++){
    for(j=0;j<12;j++){
      if(i-a[j] >= 0){
        a_j = a[j];
        dp[i] = min(dp[i],dp[i-a_j]+1);
      }
    }
  }
  cout << dp[N] << endl;
  return 0;
}


Measured memory_bytes: 768
// Author : Hardik Upadhyay
// college: SVNIT 
// slogan : Ab to phod dunga
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrep(i,a,b) for(int i = a ; i >= b; i--)
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define sq(a) (a)*(a)
#define nl "\n"
#define all(x) x.begin(),x.end()

using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,
//tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const int MAXN = 100005;
ll mod=1000000007;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	// cin>>n;
	n = 5;
	// vi a(n);
	rep(i,1,n){
		int tmp;
		cin>>tmp;
		if(tmp == 0){
			cout<<i<<nl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 3608
#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define REREP(i,n) for(int i = int(n - 1); i >= 0; i--)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define REFOR(i, m, n) for(int i = int(n - 1);i >= int(m);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define fi first 
#define se second

#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VD vector<double>
#define VVD vector<vector<double>>
#define VVVD vector<vector<vector<double>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VVVL vector<vector<vector<ll>>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define VVVB vector<vector<vector<bool>>>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVVS vector<vector<vector<string>>>

#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<ll,ll>
#define VPII vector<pair<int,int>>
#define VVPII vector<vector<pair<int,int>>>
#define VVVPII vector<vector<vector<pair<int,int>>>>
#define VPLL vector<pair<ll,ll>>
#define VVPLL vector<vector<pair<ll,ll>>>
#define VVVPLL vector<vector<vector<pair<ll,ll>>>>

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;


void YN(bool flag) {
	cout << ((flag) ? "YES" : "NO") << endl;
}

void Yn(bool flag) {
	cout << ((flag) ? "Yes" : "No") << endl;
}

void yn(bool flag) {
	cout << ((flag) ? "yes" : "no") << endl;
}

template<class T> class Union_Find {
public:
	vector<int> prnt;
	vector<int> rank;
	vector<T> dist;

	Union_Find(int N = 1) :prnt(vector<int>(N)), rank(vector<int>(N, 0)), dist(vector<int>(N, 0)) {
		for (int i = 0; i < N; ++i) prnt[i] = i;
	}

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

	T updated_dist(int x) {
		root(x);
		return dist[x];
	}

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

	bool merge(int x, int y, T d) {
		d += updated_dist(x);
		d -= updated_dist(y);
		x = root(x); y = root(y);
		if (x == y) return false;
		if (rank[x] < rank[y]) {
			swap(x, y);
			d = -d;
		}
		if (rank[x] == rank[y]) ++rank[x];
		prnt[y] = x;
		dist[y] = d;
		return true;
	}

	T diff(int x, int y) {
		return updated_dist(y) - updated_dist(x);
	}
};

int main() {
	int N, M; cin >> N >> M;
	Union_Find<int> UF(N + M);
	REP(i,N){
		int K; cin >> K;
		REP(j,K) {
			int L; cin >> L;
			UF.merge(i, N + L - 1, 1);
		}
	}
	bool flg = true;
	REP(i, N) if (!UF.same(0, i)) flg = false;
	YN(flg);
	return 0;
}



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

int d,ans[365],c[26],s[365][26],last[26],tlast[26];
const int INF=1e9;

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

void FIN(int a){
  if(a){
    ofstream fout("output.txt");
    REP(i,d)fout<<ans[i]<<"\n";
    fout.close();
    return;
  }
  REP(i,d)cout<<ans[i]<<"\n";
  return;
}

int score(){
  int res=0;
  memset(tlast,-1,sizeof(tlast));
  REP(day,d){
    res+=s[day][ans[day]-1];
    tlast[ans[day]-1]=day;
    REP(i,26)res-=c[i]*(day-tlast[i]);
  }
  return res;
}
void swap(){
  int day=rand()%362,diff=rand()%3,nowscore=score();
  swap(ans[day],ans[day+diff]);
  if(score()<nowscore)swap(ans[day],ans[day+diff]);
}
void onechange(){
  int day=rand()%365,nowscore=score();
  REP(i,26){
    int tmp=ans[day];
    ans[day]=i+1;
    if(score()<nowscore)ans[day]=tmp;
    else nowscore=score();
  }
}

int main(){
  memset(last,-1,sizeof(last));
  cin>>d;
  REP(i,26)cin>>c[i];
  REP(i,d)REP(j,26)cin>>s[i][j];
  REP(day,d){
    int idx,mx=-INF;
    REP(i,26){
      int A=c[i]*(day-last[i])+s[day][i];
      if(mx<A)mx=A,idx=i;
    }
    ans[day]=idx+1,last[idx]=day;
  }
  REP(_,80){
    REP(__,100)swap();
    REP(__,100)onechange();
  }
  FIN(0);
}


Measured memory_bytes: 3600
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

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

const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

template<class TYPE>
struct edge{
    TYPE to,cost; 
    edge(TYPE t,TYPE c){
        to = t;
        cost = c;
    }
};

int main(){
    int N;
    cin >> N;
    int a[N];
    for(int i = 0; i < N; i++) cin >> a[i];
    int res = 0;
    for(int i = 0; i < N; i++){
        res ^= a[i];
    }
    for(int i = 0; i < N; i++){
        int temp = res;
        temp ^= a[i];
        cout << temp << " ";
    }
    cout << endl;
    return 0;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

const int MAX_N = 112345;
int A[MAX_N];

int main2() {
  int N = nextInt();
  REP(i, N) A[i+1] = nextInt();
  A[0] = 0;
  A[N+1] = 0;
  ll sum = 0;
  for (int i = 1; i <= N + 1; i++) {
    sum += abs(A[i] - A[i-1]);
  }

  for (int i = 1; i <= N; i++) {
    ll ans = sum;
    ans -= abs(A[i] - A[i-1]);
    ans -= abs(A[i] - A[i+1]);
    ans += abs(A[i-1] - A[i+1]);
    printf("%lld\n", ans);
  }
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 1664
d,g = map(int,input().split())
pc = []
for i in range(d):
    p,c = map(int,input().split())
    pc.append((p,c))
minimum = 2000
for i in range(2**d):
    count = 0
    remain = g
    for j in range(d):
        if i >> j & 1:
            count += pc[j][0]
            remain -= (j+1)*100*pc[j][0]
            remain -= pc[j][1]
    highest = d*100
    while remain > 0 and highest >= 100:
        if not i >> (highest//100-1) & 1:
            if highest * pc[highest//100-1][0] >= remain:
                count += -(-remain//highest)
                remain -= -(-remain//highest)*highest
            else:
                count += pc[highest//100-1][0]
                remain -= pc[highest//100-1][0]*highest
        highest -= 100
    if remain <= 0:
        minimum = min(minimum,count)
print(minimum)

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>

#define INIT_CAP 10
#define INF 1000000000

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

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

typedef struct {
	int to, w;
} Edge;

typedef struct {
	Edge *elem;
	int cap, size;
} VecEdge;

typedef struct {
	int num, d;
} PNumDis;

VecEdge adj[30 * 30 * 4];
PNumDis heap[30 * 30 * 4 * 4];
int hsize;
int d[30 * 30 * 4];

void init(int n) {
	while (n--)
		adj[n] = (VecEdge){malloc(sizeof(Edge) * INIT_CAP), INIT_CAP, 0};
}

inline void add(int from, int to, int w) {
	if (adj[from].size == adj[from].cap) {
		adj[from].cap <<= 1;
		adj[from].elem = realloc(adj[from].elem, sizeof(Edge) * adj[from].cap);
	}
	adj[from].elem[adj[from].size++] = (Edge){to, w};
}

inline void insert(int num, int d) {
	int i;
	for (i = hsize++; i > 0 && d < heap[i - 1 >> 1].d; i = i - 1 >> 1)
		heap[i] = heap[i - 1 >> 1];
	heap[i] = (PNumDis){num, d};
}

inline int calcNextIdx(int i) {
	return i * 2 + 1 + (i * 2 + 2 < hsize && heap[i * 2 + 1].d > heap[i * 2 + 2].d);
}

inline PNumDis delete(void) {
	int i;
	int nextIdx;
	const PNumDis root = heap[0], last = heap[--hsize];

	for (i = 0; i * 2 + 1 < hsize && last.d > heap[nextIdx = calcNextIdx(i)].d; i = nextIdx)
		heap[i] = heap[nextIdx];
	heap[i] = last;

	return root;
}

void dijkstra(int n, int s) {
	int i;

	for (i = 0; i < n; i++)
		d[i] = INF;

	d[s] = 0;
	insert(s, 0);
	while (hsize > 0) {
		const PNumDis fromP = delete();

		if (fromP.d > d[fromP.num])
			continue;

		for (i = 0; i < adj[fromP.num].size; i++) {
			const Edge e = adj[fromP.num].elem[i];
			if (fromP.d + e.w < d[e.to]) {
				d[e.to] = fromP.d + e.w;
				insert(e.to, d[e.to]);
			}
		}
	}
}

int main(void) {
	int i, j, k, l;
	int w, h;

	while (scanf("%d %d", &w, &h), w) {
		int s[30][30], c[4];

		for (i = 0; i < h; i++)
			for (j = 0; j < w; j++)
				scanf("%d", s[i] + j);

		for (i = 0; i < 4; i++)
			scanf("%d", c + i);

		init(h * w * 4);
		for (i = 0; i < h; i++)
			for (j = 0; j < w; j++)
				for (k = 0; k < 4; k++)
					for (l = 0; l < 4; l++) {
						int nd = k + l & 3;
						int ni = i + di[nd], nj = j + dj[nd];
						if (ni >= 0 && ni < h && nj >= 0 && nj < w)
							add(i * w * 4 + j * 4 + k, ni * w * 4 + nj * 4 + nd, l == s[i][j] ? 0 : c[l]);
					}

		dijkstra(h * w * 4, 1);

		printf("%d\n", min(d[(h - 1) * w * 4 + (w - 1) * 4 + 1], d[(h - 1) * w * 4 + (w - 1) * 4 + 2]));
	}

	return 0;
}

Measured memory_bytes: 8888
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left
 
 
n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()
 
bc = [[int(x) for x in input().rstrip().split()]for i in range(m)]
bc.sort(reverse=True, key=lambda x: x[1])

 
i = 0
d = []
for b, c in bc:
    d.extend([c]*b)
    if len(d) >= n:
        break
 
a=a+d
a.sort(reverse=True)
print(sum(a[:n]))

#l.sort(reverse=True)
#A=A+l[:N]
#A.sort(reverse=True)



    




Measured memory_bytes: 30032
A, B, C, D, E, F = map(int, raw_input().split(' '))

ans_water = None
ans_sugar = None

for a in xrange(0, int(F/(100*A))+1):
  waterA = 100 * A * a
  for b in xrange(0, int((F-waterA)/(100*B))+1):
    water = waterA + 100 * B * b
    for c in xrange(0, int((F-water)/C)+1):
      sugarC = C * c
      for d in xrange(0, int((F-water-sugarC)/D)+1):
        sugar = sugarC + D * d
        if sugar * (100 + E) <= (water + sugar) * E:
          if (not ans_water) or (not ans_sugar) or ans_sugar * (water + sugar) < (ans_water + ans_sugar) * sugar:
            ans_water = water
            ans_sugar = sugar

print (ans_water + ans_sugar), ans_sugar

Measured memory_bytes: 2696
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;
using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;
const int INF=1<<30,MOD=1000000007;const ll LINF=1ll<<60;
#define _ol3(_1,_2,_3,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...) _ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,v) REP(i,v.size())
#define all(v) (v).begin(),(v).end()
#define bit(n) (1ll<<(n))
#define clamp(n,mi,ma) max(min(n,ma),mi)
#define uniq(v) sort(all(v));v.erase(unique(all(v)),v.end())
#define pb push_back
#define F first
#define S second
#define endl '\n'
#ifndef LOCAL
struct ostdmy{template<class T>ostdmy&operator<<(const T&t){return*this;}};ostdmy cer_;
#define cerr cer_
#endif
#define cho(n,a,b) cout<<((n)?a:b)<<endl
#define YES(n) cho(n,"YES","NO")
#define Yes(n) cho(n,"Yes","No")
#define Poss(n) cho(n,"Possible","Impossible")
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(a>b){a=b;return 1;}return 0;}
template<class T>ostream&operator<<(ostream&o,const vector<T>&v){for(const T&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>ostream&operator<<(ostream&o,const set<T>&v){for(const T&i:v)o<<i<<' ';return o;}
#define MAX_V 100000
int V,E;
vector<int> G[MAX_V];
void dijkstra(int start, vector<int>&arr){
    priority_queue<P,vector<P>,greater<P>> Q;
    arr[start]=0;
    Q.push(make_pair(0,start));
    while(!Q.empty()){
        P p=Q.top();
        Q.pop();
        int v=p.second;
        if(arr[v]<p.first)continue;
        REPA(i,G[v]){
            int e=G[v][i];
            if(arr[e]>arr[v]+1){
                arr[e]=arr[v]+1;
                Q.push(make_pair(arr[e],e));
            }
        }
    }
}
int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int n;
    cin>>n;
    REP(i,n-1){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    vi d1(n,INF);
    vi d2(n,INF);
    dijkstra(0,d1);
    dijkstra(n-1,d2);
    int ans=0;
    REP(i,1,n-1){
        cerr<<i<<':'<<d1[i]<<':'<<d2[i]<<endl;
        if(d1[i]<=d2[i])ans--; // sente yuuri
        else ans++; // sente furi
    }
    cerr<<ans<<endl;
    if(ans<0)cout<<"Fennec"<<endl; // sente make
    else cout<<"Snuke"<<endl; // sente kachi
    return 0;
}


Measured memory_bytes: 6976
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    int N;
    while(cin>>N,N){
        int num[150][150]={{0}};
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                cin>>num[i][j];
                num[i][N]+=num[i][j];
                num[N][j]+=num[i][j];
                num[N][N]+=num[i][j];
            }
        }
        for(int i=0;i<=N;i++){
            for(int j=0;j<=N;j++){
                if(num[i][j]<10){
                    for(int k=0;k<4;k++)cout<<" ";
                }
                else if(num[i][j]<100){
                    for(int k=0;k<3;k++)cout<<" ";
                }
                else if(num[i][j]<1000){
                    for(int k=0;k<2;k++)cout<<" ";
                }
                else if(num[i][j]<10000){
                    for(int k=0;k<1;k++)cout<<" ";
                }
                cout<<num[i][j];
            }
            cout<<endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vl v(n);
	REP(i, n)cin >> v[i];
	ll ans = 0;
	vl a(n + 1, 0);
	map<ll, int> cnt;
	a[0] = 0;
	REP(i, n)a[i + 1] = v[i] + a[i];
	REP(i, n+1)cnt[a[i]]++;
	

	REP(i, n) {
		ans += cnt[a[i]]-1;
		cnt[a[i]]--;
	}
	cout << ans << endl;
}


Measured memory_bytes: 15872
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <tuple>

using namespace std;
using ll = long long;
using ull = unsigned long long;
#define out(S) cout<<(S)<<endl;
#define REP(i,b) for(size_t i=0;i<(b);i++)
#define rREP(i,b) for(int i=(b)-1;i>=0;i--)
#define FOR(i,a,b) for(size_t i=(a);i<(b);i++)
#define rFOR(i,a,b) for(int i=(b)-1;i>=0;i--)
#define Foreach(item,collection) for(auto item:collection)
#define mod(i) ((i) % (ll)(1e9 + 7))
ll modpow(ll i, ll j) { ll tmp = 1; while (j) { if (j % 2)tmp = mod(tmp*i); i = mod(i*i); j /= 2; }return tmp; }
#define divmod(a,b) (mod(a * modpow((ll)b,(ll)(1e9 + 5))))
#define Yes out("Yes")
#define No out("No")
#define NO out("NO")
#define YES out("YES")
#define INF 2e10;
#define ShowAll(collection) for(auto i:collection){out(i);}
#define IfOut(condition,text) if((condition)){out(text);return 0;}
#define IfeOut(condition,itext,etext) if(condition){out(itext);return 0;}else{out(etext);return 0;}
#define Select(collection,condition,result) Foreach(i,collection){result+=condition;}
template<typename T> pair<vector<T>,int> getAuto() {int N; cin >> N; pair<vector<T>, int> rt;rt.first.resize(N);rt.second = N;REP(i, N) cin >> rt.first[i];return rt;}
void removeAt(string& s, int index) { s.erase(index, 1); }
template<typename T> void removeAt(vector<T>& v, int index) { v.erase(v.begin() + index); }
ll manhattanDistance(ll x1, ll y1, ll x2, ll y2) { return (abs(x2 - x1) + abs(y2 - y1)); }


int main() {
	int N, M;
	cin >> N >> M;
	vector<ll> a, b, c, d;
	a.resize(N); b.resize(N);
	c.resize(M); d.resize(M);
	REP(i, N) { cin >> a[i] >> b[i]; }
	REP(i, M) { cin >> c[i] >> d[i]; }
	REP(n, N) {
		ll _min = INF;
		int index = 0;
		REP(m, M) {
			int distance = manhattanDistance(a[n], b[n], c[m], d[m]);
			if (_min > distance) { index = m; _min = distance; } 
		}
		out(index+1);
	}
}



Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<vector>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"basic.hpp"
#else
template <class... T> void printl(T&&...){ }
template <class... T> void printc(T&&...){ }
template <class... T> void prints(T&&...){ }
#endif

int main(){
    int k, s;
    cin >> k >> s;
    int ret = 0;
    for(int i=0;i<=k;i++){
        for(int j=0;j<=k;j++){
            int rem = s - i - j;
            ret += (0 <= rem && rem <= k);
        }
    }
    cout << ret << '\n';
    return 0;
}


Measured memory_bytes: 888
require 'prime'

N = gets.to_i

count = 0

(1..N).each{ |k|
	if k % 2 == 0 then
		next
	end

	p = Prime.prime_division(k)
	if p.map{ |x| x[1] + 1 }.inject(1, :*) == 8 then
		count += 1
	end
}

puts count

Measured memory_bytes: 2044
#include<iostream>

using namespace std;

int main(){
  char  moji1 ;
  int moji;
  cin >> moji1;
  moji = (int)moji1;	
  
  if(65 <= moji && moji <= 90){
    cout << 'A';
  }

  else{
    cout << 'a';
  }  
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define repl(i, l, r) for (int i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main()
{
    string s;
    cin >> s;
    if(s[0] == 'R') {
        if(s[1] == 'S') cout << 1 << endl;
        else {
            if(s[2] == 'S') cout << 2 << endl;
            else cout << 3 << endl;
        }
    }
    else if(s[1] == 'R') {
        if(s[2] == 'S') cout << 1 << endl;
        else cout << 2 << endl;
    }
    else {
        if(s[2] == 'R') cout << 1 << endl;
        else cout << 0 << endl;
    }
    return 0;
}


Measured memory_bytes: 3576
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
static_assert(sizeof(long) >= 8, "sizeof(long) >= 8");
char s[200001];
int cnt[26];
int main() {
    scanf("%s", s);
    int n = strlen(s);
    long ans = 1;
    for (int i = 0; i < n; i++) {
        ans += (i - cnt[s[i] - 'a']);
        cnt[s[i] - 'a']++;
    }
    printf("%ld\n", ans);
}


Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(){
  int N,L;
  int i,j;
  scanf("%d%d",&N,&L);
  char S[N][L+1];
  for(i=0;i<N;i++)
  {
  	scanf("%s",S[i]);
  }
  
  char tmp[L+1];
  
  for(i=1;i<N;i++){
  	for(j=N-1;j>=i;j--){
    	if(strcmp(S[j-1],S[j])>0){
        	strcpy(tmp,S[j-1]);
          	strcpy(S[j-1],S[j]);
          	strcpy(S[j],tmp);
        }
    }
  }
  for(i=0;i<N;i++){
  	printf("%s",S[i]);
  }
 
  return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;

long long t[1<<20];

int mirror(int comb){
  int res = 0;
  for(int i=0;i<5;i++){
    for(int j=0;j<5;j++){
      res |= ( ( (comb >> (i*5+j)) ) & 1) << (i*5+4-j);
    }
  }
  return res;
}

int rot(int comb){
  int res = 0;
  for(int i=0;i<5;i++){
    for(int j=0;j<5;j++){
      if( ( comb >> (i*5 + j) ) & 1){
	res |= 1 << ( (4-j)*5 + i);
      }
    }
  }
  return res;
}

void print(int t){
  for(int i=0;i<5;i++){
    for(int j=0;j<5;j++)cout << ( (t>>((i*5)+j))&1 );
    cout << endl;
  }
  cout << endl;
}

int main(){
  string s[10];
  int mask = (1<<25) -1;
  set<int> sa,sb;
  vector<int> a,b;

  while(cin >> s[0] , s[0]!="END"){
    for(int i=1;i<10;i++)cin >> s[i];
    for(int i=0;i<(1<<20);i++)t[i] = 0LL;

    int ans = 0;
    int comb = (1<<5) - 1;
    while(comb < (1<<10)){
      a.clear(); b.clear();
      for(int i=0;i<10;i++){
        if( (comb >> i) & 1)a.push_back(i);
        else b.push_back(i);
      }
      sa.clear(); sb.clear();
      do{
        for(int k=0;k<(1<<5);k++){
          int tmp = 0;
          for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
              if(s[a[i]][j] == '1'){
                if( (k>>i) &1)tmp |= 1<<( (i*5)+j);
                else tmp |=1<<( (i*5)+ 4-j);
              }
            }
          }
          sa.insert(tmp);
        }
      }while(next_permutation(a.begin(),a.end()));

      do{
        for(int k=0;k<(1<<5);k++){
          int tmp = 0;
          for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
              if(s[b[i]][j] == '1'){
                if( (k>>i) &1)tmp |= 1<<( (j*5)+i);
                else tmp |=1<<( ((4-j)*5)+ i);
              }
            }
          }
          sb.insert(tmp^mask);
        }
      }while(next_permutation(b.begin(),b.end()));

      for(set<int>::iterator ite=sa.begin();ite!=sa.end();ite++){
	int x = *ite;
        if(sb.find(x)!=sb.end()){
          long long f = 0LL;
          for(int j=0;j<2;j++){
            x = mirror(x);
            for(int k=0;k<4;k++){
              x = rot(x);
              if(k&1)f += (t[x/64]>>(x%64)) & 1LL;
              else f += (t[(x^mask)/64]>>((x^mask)%64)) & 1LL;
	    }
	  }
          if(!f){
            t[x/64] |= 1LL<<(x%64);
	    ans++;
          }
	}
      }

      int x = comb & -comb, y = comb + x;
      comb = (((comb & ~y) / x )>> 1) | y;
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 9228
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.next();
		char c = input.charAt(0);
		char out;

		switch (c) {
		case 'A':
			out = 'T';
			break;
		case 'C':
			out = 'G';
			break;
		case 'G':
			out = 'C';
			break;
		case 'T':
			out = 'A';
			break;

		default:
			out = '?';
			break;
		}

		System.out.println(out);
		
		sc.close();
	}
}


Measured memory_bytes: 20564
def fact(n)
  @facts ||= [1]
  (@facts.size).upto(n){|i| @facts << @facts[-1]*i % MOD}
  return @facts[n]
end

def modpow(x,n)
  ret = 1
  while n > 0
    ret = (ret * x) % MOD if n&1 == 1
    x = (x*x) % MOD
    n >>= 1
  end
  return ret
end

def modinv(x)
  return modpow(x,MOD-2)
end

def combin(n,k)
  return (((fact(n) * modinv(fact(n-k))) % MOD) * modinv(fact(k))) % MOD
end

MOD = 10**9+7
n,k = gets.split.map(&:to_i)

if n==k
  p 1
  (k-1).times do 
    p 0
  end
else
  1.upto(k) do |i|
    
    t = 0
    t += combin(n-k-1,i) if n-k-1 >= i
    t += combin(n-k-1,i-1) * 2 if n-k-1 >= i-1
    t += combin(n-k-1,i-2) if n-k-1 >= i-2 && i-2 >= 0
    t %= MOD
    
    p (combin(k-1,i-1) * t) % MOD
  end
end

Measured memory_bytes: 2044
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <random>
#include <bitset>
using namespace std;
 

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define pb push_back
#define forn(i, n) for (int i = 0; i < n; ++i)
#define int long long

 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
 
 
const int MAXN = 2e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = INT64_MAX;


random_device rd;
mt19937 rnd(rd());


signed main() {
	FAST_IO;
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> cnt(1e5 + 5);
	int s = 0;
	forn(i, n) {
		cin >> a[i];
		s += a[i];
		cnt[a[i]]++;
	}
	int q;
	cin >> q;
	while (q--) {
		int b, c;
		cin >> b >> c;
		s -= b * cnt[b];
		s += c * cnt[b];
		cnt[c] += cnt[b];
		cnt[b] = 0;
		cout << s << "\n";
	}
 	return 0;
}

Measured memory_bytes: 4744