akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
typedef pair<string,string>str;
typedef map<str,ll> mp;
const int L=50;
mp dict;
char s[L];
int n;
void dfs1(string s1,string s2,int x){
    //cout<<"s1:"<<s1<<'\n';
    //cout<<"s2:"<<s2<<'\n';
    if(x==n+1){
        dict[str(s1,s2)]++;
        return ;
    }
    dfs1(s1+s[x],s2,x+1);
    dfs1(s1,s2+s[x],x+1);
}
ll ans;
void dfs2(string s1,string s2,int x){
    //cout<<"s1:"<<s1<<'\n';
    //cout<<"s2:"<<s2<<'\n';
    if(x==n){
        if(dict.find(str(s2,s1))!=dict.end()){
            ans+=dict[str(s2,s1)];
        }
        return ;
    }
    dfs2(s1+s[x],s2,x-1);
    dfs2(s1,s2+s[x],x-1);
}
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    string s1,s2;
    dfs1(s1,s2,1);
    dfs2(s1,s2,n*2);
    printf("%lld\n",ans);
}


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define endl "\n"

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

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

  int K;
  cin>>K;
  ll ans=0;
  for(int i=1;i<=K;i++){
    for(int j=1;j<=K;j++){
      for(int k=1;k<=K;k++){
        ans+=gcd(i,gcd(j,k));
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3640
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int max = -1000000; 
		int min = 1000000;
		long sum = 0;
		for(int i = 0;i < n;i++){
			int newValue = sc.nextInt();
			if(newValue < min){
				min = newValue;
			}
			if(newValue > max){
				max = newValue;
			}
			sum += newValue;
		}
		System.out.println(min + " " + max + " " + sum);
	}
}


Measured memory_bytes: 42392
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<vector>
#include<map>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	int a,b;
	while(cin>>a>>b)
	{
		int i;
		bool flag=0;
		for(i=1;i<=3;i++)
			if(a*b*i%2)
			{
				cout<<"Yes"<<endl;
				flag=1;
				break;
			}
		if(flag==0)
			cout<<"No"<<endl;
			
	}
	return 0;
}


Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
	let n: i64 = read();
	let W: i64 = read();
	let mut v: Vec<i64> = Vec::with_capacity(n as usize);
	let mut w: Vec<i64> = Vec::with_capacity(n as usize);
	for _ in 0..n {
		v.push(read());
		w.push(read());
	}

	let mut dp: Vec<Vec<i64>> = (0..(n + 1)).into_iter().map(|_| (0..(W + 1)).into_iter().map(|_| 0).collect()).collect();
	
	for i in 0..(n as usize) {
		for j in 0..(W as usize + 1) {
			if (j as i64) < w[i] {
				dp[i + 1][j] = dp[i][j];
			} else {
				dp[i + 1][j] = std::cmp::max(dp[i][j], dp[i][j - (w[i] as usize)] + v[i]);
			}
		}
	}
	println!("{}", dp[n as usize][W as usize]);
}




Measured memory_bytes: 13112
#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
    string str;
    cin >> str;

    stack<int> s;
    stack<pair<int, int>> s2;

    int sum_of_area = 0;
    for (int i = 0; i < str.length(); ++i) {
        if (str[i] == '\\') {
            s.push(i);
        } else if (str[i] == '/') {
            if (s.empty())
                continue;

            int start = s.top();
            int area = i - start;
            sum_of_area += area;
            s.pop();

            if (!s2.empty()) {
                pair<int, int> prev = s2.top();
                while (prev.first > start) {
                    s2.pop();
                    area += prev.second;

                    if (s2.empty())
                        break;
                    prev = s2.top();
                }
            }
            s2.push(make_pair(start, area));
        }
    }

    vector<int> partial;
    while (!s2.empty()) {
        partial.push_back(s2.top().second);
        s2.pop();
    }
    reverse(partial.begin(), partial.end());

    cout << sum_of_area << '\n';
    cout << partial.size();
    for (int i = 0; i < partial.size(); ++i)
        cout << ' ' << partial[i];
    cout << '\n';
}



Measured memory_bytes: 3268
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int[] d = new int[n];
        {
            for (int i = 0; i < n; i++)
            {
                d[i] = int.Parse(Console.ReadLine());
            }
        }

        int answer = d.Distinct().ToList().Count();

        Console.WriteLine(answer);
    }
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int main()
{
	int n;
	int ans = 1001001001;
	int cnt = 0;
	cin >> n;
	vector<int> vec(n);
	rep(i, n) cin >> vec[i];

	rep(i, n)
	{
		cnt = 0;
		while (vec[i] % 2 == 0)
		{
			cnt++;
			vec[i] /= 2;
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return (0);
}


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

int main()
{
	int a, b, c;
	int count;
	vector<int> v;
	cin >> a >> b>> c;

	for(int n = 1; n <= c; n++){
		if((c % n) == 0)
			v.push_back(n);
	}

	count = 0;
	for(int n = 0; n < v.size(); n++){
		if(a <= v[n] && v[n] <= b)
			count++;
	}
	cout << count << endl;
}

Measured memory_bytes: 1216
#include <stdio.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

char s[]="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
ll a[110];
int main(){
	ll n;
	while(scanf("%lld",&n),n){
		rep(i,0,n)scanf("%lld",a+i);
		char t[110];
		scanf(" %s",t);
		ll len=strlen(t);
		rep(i,0,len)putchar(s[(strchr(s,t[i])-s-a[i%n]+52)%52]);
		puts("");
	}
}


Measured memory_bytes: 2104
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
using namespace std; using ll = long long; using pll = pair<ll, ll>;
using vl = vector<ll>; using vll = vector<vl>; using vpll = vector<pll>;
int ctoi(char c) {
	switch (c) {
	case '0': return 0; case '1': return 1; case '2': return 2;
	case '3': return 3; case '4': return 4; case '5': return 5;
	case '6': return 6; case '7': return 7; case '8': return 8;
	case '9': return 9;  default: return 0;
	}
}
bool pairCompare(const pll firstElof, pll secondElof)
{
	return firstElof.first > secondElof.first;
}
//**Snippetリスト**//
//rep, vin, all, iteLoop//
//gcdlcm, isPrime, eratos, divisor, modinv, bitSearch, bitList, dfs, bfs//
//dijkstra, UnionFind, COM, digitDP//
ll i, j, k, l; ll N, M, K, H, W, L, X, Y, Z;
ll MOD = 1000000007; ll INF = 9999999999999; ll ans = 0;
vl flag, color, D; vll path;
//***********//
int main() {
	cin >> N;
	if (N == 1) cout << "Hello World";
	else {
		ll A, B;
		cin >> A >> B;
		cout << A + B;
	}
}

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

signed main(void)
{
  char c;
  int ret = 0, tmp = 0;
  while((c=getchar())!=EOF)  {
    if(c >= '0' && c <= '9') tmp = tmp*10+(c-'0');
    else {
      ret += tmp;
      tmp = 0;
    }
  }
  cout << ret << endl;
  return 0;
}

Measured memory_bytes: 2984
#include <iostream>
#include <string>
using namespace std;
string s;
int main(){
	int i,n,b = 0,r = 0;
	cin >> n >> s;
	for(i=0;i<n;i++){
		if(s[i]=='B') b++;
		else r++;
	}
	if(r>b) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
 
int n, mx = 0, cnt = 0;
string s;
map<char,int> m;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>n>>s;
	for(int i=0;i<n;i++){
		m[s[i]]++;
		cnt = 0;
		bool visited[27];
		memset(visited, false, 27);
		for(int j=i+1;j<n;j++){
			if(m[s[j]] > 0 && !visited[s[j] - 96]){
				cnt++;
				visited[s[j] - 96] = true;
			}
		}
		if(cnt > mx)
			mx = cnt;
	}
	cout<<mx;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pll pair<ll,ll>
#define sll set<ll>
#define msll multiset<ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define vpl vector<pll>
#define gll greater<ll>
#define gpl greater<pll>
#define spl set<pll>
#define mspl multiset<pll>
#define lb lower_bound
#define bp __builtin_popcount
#define ub upper_bound
#define prq priority_queue
#define mp make_pair
#define pb push_back
#define mem(x,y) memset(x, y, sizeof x)
#define endl "\n"
#define sz(x) (ll)x.size()
#define sqr(x) x*x
#define rapido ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
typedef long long ll;
typedef long double ld;
ll mx=INT_MAX;
ll mn=INT_MIN;
ll MOD=1e9+7;
const ll maxs=1e7+5;
ll INF = 1e18;
const ll lg=22; 

ll fast(ll base , ll expo){
    ll res = 1;
    while(expo>=1){
        if(expo%2) res *= base;
        base *= base;
        expo /= 2;
    }
    return base;
}

void code_idhr_h(){
    ll N; cin>>N;
    cout<<N + N*N + N*N*N;
}

int main(){
    rapido;
    ll T=1; //cin>>T;
    while(T--){
        mx = INT_MIN;
        code_idhr_h();
    }
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> P;
#define INF 1500001
int n,r,d[1500][1500],qt[1500],ans=0;
vector<P>e[1500];
vector<int>p[1500][1500];
int dfs(int a,int b){
    if(b==a)return 0;
    for(int i=0;i<p[a][b].size();i++){
        if(qt[p[a][b][i]]==0)ans++;
        qt[p[a][b][i]]=1;
        dfs(a,p[a][b][i]);
    }
    return 0;
}
int main(void){
   cin>>n>>r;
   for(int i=0;i<r;i++){
       int s,t,c;
       cin>>s>>t>>c;
       s--;
       t--;
       e[s].push_back(P(t,c));
       e[t].push_back(P(s,c));
   }
   
   for(int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           d[i][j]=INF;
       }
   }
   int mc=0;
    for(int i=0;i<n;i++){
        priority_queue<P,vector<P>,greater<P> >k;
        d[i][i]=0;
        k.push(P(0,i));
        while(!k.empty()){
            int v=k.top().second,co=k.top().first;
            k.pop();
            if(d[i][v]!=co)continue;
            for(int j=0;j<e[v].size();j++){
                if(d[i][e[v][j].first]==d[i][v]+e[v][j].second)p[i][e[v][j].first].push_back(v);
                else if(d[i][e[v][j].first]>d[i][v]+e[v][j].second){
                    p[i][e[v][j].first].clear();
                    p[i][e[v][j].first].push_back(v);
                    d[i][e[v][j].first]=d[i][v]+e[v][j].second;
                    k.push(P(d[i][e[v][j].first],e[v][j].first));
                }
            }
        }
        for(int j=0;j<n;j++){
            if(mc<d[i][j]){
                mc=d[i][j];
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(d[i][j]==mc){
                dfs(i,j);
            }
        }
    }
    cout<<n-ans<<endl;
    for(int i=0;i<n;i++){
        if(qt[i]==0)cout<<i+1<<endl;
    }
}

Measured memory_bytes: 135304
#include <bits/stdc++.h>
using namespace std ;
#define int long long int
#define N 100+5
int n,W,val[N],wt[N],dp[N][100000+5];
int f(int i,int wr)
{
    if( wr == 0  ) return 0 ;
    if( wr < 0  ) return -100000000000000000 ;
    if( i<0 ) return 0 ;
    if( dp[i][wr] != -1 ) return dp[i][wr] ;
    return  dp[i][wr] = max( val[i] + f( i-1,wr-wt[i] ) , f(i-1,wr) ) ;

}
signed main()
{
    cin >> n >> W ;
    for(int i=0;i<n;i++) cin >> wt[i] >> val[i] ;
    memset( dp , -1 ,sizeof dp ) ;
    cout << f( n-1,W ) ;

    return 0 ;
}


Measured memory_bytes: 82304
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#define int long long
using namespace std;
const int maxn = 1e5+10;

int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

char s1[maxn],s2[maxn];
int w1[100],w2[100],f[maxn][30];
signed main(){
	int k,m,n,len1,len2;
	scanf("%s",s1+1);len1=strlen(s1+1);
	scanf("%s",s2+1);len2=strlen(s2+1);
	for(register int i=1;i<=len1;i++)w1[s1[i]-'a'+1]++;
	for(register int i=1;i<=len2;i++)w2[s2[i]-'a'+1]++;
	for(register int i=1;i<=26;i++){
		if(w2[i] && !w1[i]){
			puts("-1");
			return 0;
		}
	}
	for(register int i=1;i<=26;i++){
		int last=0;
		for(register int j=1;j<=len1;j++){
			//cout<<i<<" "<<s1[j]-'a'+1<<endl;
			if(s1[j]-'a'+1==i){
				f[last+1][i]=j;
				last=j;
			}
		}
		f[last+1][i]=-1;
		//cout<<i<<endl;
	}
	for(register int i=1;i<=26;i++){
		for(register int j=1;j<=len1;j++){
			if(f[j][i]==0)f[j][i]=f[j-1][i];
		}
	}
	/*
	for(register int j=1;j<=26;j++){
		for(register int i=1;i<=len1;i++){
			cout<<f[i][j]<<" ";
		}puts("");
	}*/
	int now=0,sum=0;
	for(register int i=1;i<=len2;i++){
		int x=s2[i]-'a'+1;
		if(f[now+1][x]!=-1 && f[now+1][x]!=0)now=f[now+1][x];
		else {now=f[1][x];sum++;}
		//cout<<x<<" "<<now<<endl;
	}
	//cout<<sum<<" "<<now<<endl;
	printf("%lld\n",sum*len1+now);
	return 0;
}

Measured memory_bytes: 23936
import math
PI = 4.0 * math.atan(1.0)

a, b, c = map(int, input().split())
angle = c*PI / 180.0

S = a*b*math.sin(angle) / 2.0
d = math.sqrt(a**2 + b**2 - 2.0*a*b*math.cos(angle))
L = a + b + d
h = b*math.sin(angle)

print("{:.6f}".format(S))
print("{:.6f}".format(L))
print("{:.6f}".format(h))


Measured memory_bytes: 5732
from sys import stdin
from collections import deque, defaultdict

readline = stdin.readline

def main():
    H, W = map(int, readline().rstrip().split())
    CH, CW = map(lambda x: int(x) - 1, readline().rstrip().split())
    DH, DW = map(lambda x: int(x) - 1, readline().rstrip().split())
    S = [readline().rstrip() for _ in range(H)]
    v = defaultdict(lambda : False)
    dq = deque([(0, CH, CW)])
    while dq:
        d, h, w = dq.popleft()
        # print(f'{c} : {h} : {w} : {S[h][w]}')
        if (h, w) == (DH, DW):
            print(d)
            exit()
        if v[(h, w)]:
            continue
        v[(h, w)] = True
        for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = mh + h
            nw = mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                dq.appendleft([d, nh, nw])
        for mh in range(-2, 3):
            for mw in range(-2, 3):
                if mh == mw == 0:
                    continue
                nh = mh + h
                nw = mw + w
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                    dq.append([d + 1, nh, nw])
    print(-1)

if __name__ == "__main__":
    main()


Measured memory_bytes: 235468
#include <iostream>
#include <list>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>

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

typedef long long ll;

using namespace std;
int main(){
    int N;
    cin >> N;
    ll A[100];
    ll product = 1;
    REP(i, N)
    {
    	cin >> A[i];
    	product *= A[i];
    }
    double sum = 0.0;
    REP(i, N)
    {
    	sum += 1.0 / (double)A[i];
    }
	double ans = 1.0 / sum;
	printf("%.7f\n", ans);
}


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

signed main(){
     int n, d;
    cin>>n>>d;
    int cnt = 0;
    while(n--){
        int x, y;
        cin>>x>>y;
        int var1= (x*x + y*y);
        int var2= d*d;
        if(var1 <= var2){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
#define ul unsigned long long
#define ll long long
#define ld long double


int main()
{
  ll n,rmi=LLONG_MAX,r,ccd=-LLONG_MAX;
  cin>>n;

  for (ll i = 0; i < n; i++)
  {
    cin>>r;
    ccd=max(ccd,r-rmi);
    rmi=min(rmi,r);
  }
  cout<<ccd<<endl;

  return 0;
}



Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1e18;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main(){
	int h, w, m; cin >> h >> w >> m;
	vector<P> x(h,{0,0}), y(w,{0,0});
	REP(i,h) x[i]={0,i};
	REP(i,w) y[i]={0,i};
	map<P,bool> mp;
	int a, b;
	REP(i,m){
		cin >> a >> b;
		a--; b--;
		mp[{a,b}]=1;
		x[a].first++;
		y[b].first++;
	}
	sort(ALL(x),greater<P>());
	sort(ALL(y),greater<P>());
	int mn=1;
	for(int i=0;i<h;i++){
		if(x[i].first!=x[0].first||mn==0)
			break;
		for(int j=0;j<w;j++){
			if(y[j].first!=y[0].first)
				break;
			if(mp[{x[i].second,y[j].second}]==0){
				mn=0;
				break;
			}
		}
	}
	cout << x[0].first+y[0].first-mn << endl;
	return 0;
}

Measured memory_bytes: 31512
import sys
sys.setrecursionlimit(10**5 + 1)
def main():
    global n, peso, dp

    n = int(input())
    peso = [int(x) for x in input().split()]
    dp = [-1]*(10**5 + 1)
    
    peso.append(10**9)
    peso.append(10**9)
    
    print(frog(0))
    
def frog(i):
    global n, peso, dp
    
    if i >= n - 1:
        return 0

    if dp[i] != -1:
        return dp[i]

    dp[i] = min(abs(peso[i + 1] - peso[i]) + frog(i + 1),
                abs(peso[i + 2] - peso[i]) + frog(i + 2))
    
    return dp[i]

main()

Measured memory_bytes: 163692
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 100 + 10;

int total, N;
int a[MAXN]= {0};
int st[MAXN]= {0}, ed[MAXN]= {0};
int odd[MAXN]= {0}, ocnt = 0;

int ans[MAXN]= {0}, acnt = 0;

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	total = getnum (), N = getnum ();
	for (int i = 1; i <= N; i ++) {
		a[i] = getnum ();
		if (a[i] & 1) odd[++ ocnt] = i;
	}
	if (N == 1) {
		printf ("%d\n", a[1]);
		if (total == 1) puts ("1"), puts ("1");
		else {
			puts ("2");
			printf ("1 %d\n", total - 1);
		}
		return 0;
	}
	if (ocnt > 2) {
		puts ("Impossible");
		return 0;
	}
	if (ocnt >= 1) swap (a[1], a[odd[1]]);
	if (ocnt >= 2) swap (a[N], a[odd[2]]);
	ans[++ acnt] = a[1] + 1;
	for (int i = 2; i < N; i ++) ans[++ acnt] = a[i];
	if (a[N] - 1 > 0) ans[++ acnt] = a[N] - 1;
	for (int i = 1; i <= N; i ++) {
		if (i > 1) putchar (' ');
		printf ("%d", a[i]);
	}
	printf ("\n%d\n", acnt);
	for (int i = 1; i <= acnt; i ++) {
		if (i > 1) putchar (' ');
		printf ("%d", ans[i]);
	}
	puts ("");

	return 0;
}

/*
3 2
2 1
*/

/*
6 1
6
*/

/*
55 10
1 2 3 4 5 6 7 8 9 10
*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int,int>
#define vs vector<string>
#define all(v) (v).begin(),(v).end()
#define ll long long
#define ull unsigned long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define ld long double
#define mod 1000000007
#define PI 3.141592653589793238
#define phi 1.638
#define eps 1e-9
//#define endl "\n"
using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; 


int main() 
{ 
    fastio
    int x, y, z;
    cin>>x>>y>>z;

    cout<<z<<" "<<x<<" "<<y<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  
  while (true) {
    C = C - B;
    if (C <= 0) {
      cout << "Yes" << endl;
      break;
    }
    
    A = A - D;
    if (A <= 0) {
      cout << "No" << endl;
      break;
    }
  }
  return false;
}

Measured memory_bytes: 3592
package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	num, _ := strconv.Atoi(scanString())
	return num
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func scanInts(n int) []int {
	sl := make([]int, n)
	for i := range sl {
		sl[i] = scanInt()
	}
	return sl
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n, d := scanInt(), scanInt()
	var cnt int
	for i := 0; i < n; i++ {
		x, y := scanInt(), scanInt()
		if d*d >= x*x+y*y {
			cnt++
		}
	}

	fmt.Println(cnt)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}


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

int main(){
  string w; cin >> w;
  string s;
  int cnt = 0;
  while(cin >> s){
    if(s == "END_OF_TEXT") break;
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    if(s == w) cnt++;
  }
  cout << cnt << endl;
}



Measured memory_bytes: 3224
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

LL a,b,c,na,nb,nc;
int main()
{
	get3(a,b,c);
	if(a==b&&a==c&&a%2==0)
	{
		puts("-1");
		return 0;
	}
	int ans=0;
	while(a%2==0&&b%2==0&&c%2==0)
	{
		na=(b+c)/2;
		nb=(a+c)/2;
		nc=(a+b)/2;
		a=na;b=nb;c=nc;
		ans++;
	}
	printendl(ans);
	return 0;
}

Measured memory_bytes: 256
n,a,b=map(int,input().split())
v=list(map(int,input().split()))
fact=[1]
for i in range(1,51):
    fact.append(i*fact[-1])
def cmb(n,r):
    return fact[n]//(fact[n-r]*fact[r])
v.sort(reverse=True)
print(sum(v[:a])/a)
cntv,cntr=0,0
for i in range(n):
    if i<a:
        if v[i]==v[a-1]:
            cntv+=1
    else:
        if v[i]==v[a-1]:
            cntr+=1
#print(cntv,cntr)
if cntv<a:
    print(cmb(cntv+cntr,cntv))
else:
    ans=0
    for r in range(a,min(b,cntv+cntr)+1):
        ans+=cmb(cntv+cntr,r)
        #print(ans)
    print(ans)

Measured memory_bytes: 9136
using System;
using System.Collections.Generic;
using System.Linq;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayInt();
            var N = input[0];
            var M = input[1];
            var AB = Enumerable.Repeat(new int[2], N).Select(ab => ab = ReadArrayInt()).ToArray();
            var sortAB = AB.OrderBy(ab => ab[0]).ToArray();
            var ans = 0L;
            var idx = 0;
            var day = 1;
            var pq = new PriorityQueue<int>((a, b) => b - a);
            while (day <= M)
            {
                if (idx < N && sortAB[idx][0] <= day)
                {
                    while (idx < N && sortAB[idx][0] <= day)
                    {
                        pq.Enqueue(sortAB[idx][1]);
                        idx++;
                    }
                }
                if (pq.Any())
                {
                    ans += pq.Dequeue();
                }
                day++;
            }

            Console.WriteLine(ans);
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }

    class PriorityQueue<T>
    {
        readonly List<T> heap;
        readonly Comparison<T> compare;
        int size;
        public PriorityQueue(Comparison<T> compare)
        {
            heap = new List<T>();
            this.compare = compare;
        }
        public void Enqueue(T val)
        {
            heap.Add(val);
            int i = size++;
            while (i > 0)
            {
                int p = (i - 1) >> 1;
                if (compare(heap[p], val) <= 0) break;
                heap[i] = heap[p];
                i = p;
            }
            heap[i] = val;
        }
        public T Dequeue()
        {
            T ret = heap[0];
            T x = heap[--size];
            int i = 0;
            while ((i << 1) + 1 < size)
            {
                int a = (i << 1) + 1;
                int b = (i << 1) + 2;
                if (b < size && compare(heap[b], heap[a]) < 0) a = b;
                if (compare(heap[a], x) >= 0) break;
                heap[i] = heap[a];
                i = a;
            }
            heap[i] = x;
            heap.RemoveAt(size);
            return ret;
        }
        public T Peek() { return heap[0]; }
        public int Count { get { return size; } }
        public bool Any() { return size > 0; }
    }
}

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

int main() {
	int n; cin >> n;
	const int N = 1 << n;
	multiset<int> st1;
	for(int i = 0; i < N; ++i) {
		int s; cin >> s;
		st1.insert(s);
	}
	int maxi = *st1.rbegin();
	st1.erase(st1.find(maxi));
	multiset<int> st2;
	st2.insert(maxi);
	while(st1.size()) {
		multiset<int> tmp;
		for(auto i = st2.rbegin(); i != st2.rend(); ++i) {
			int s = *i;
			auto itr = st1.lower_bound(s);
			if(itr == st1.begin()) {
				cout << "No\n";
				return 0;
			}
			itr = prev(itr);
			tmp.insert(*itr);
			st1.erase(itr);
		}
		for(int i : tmp) {
			st2.insert(i);
		}
	}
	cout << "Yes\n";
	return 0;
}

Measured memory_bytes: 18688
n = int(input())
l = [0 for _ in range(100001)]
s = 0
for a in input().split():
    l[int(a)] += 1
    s += int(a)
q = int(input())
ans = []
for i in range(q):
    b,c = map(int,input().split())
    s += (c-b)*l[b]
    ans.append(s)
    l[c] += l[b]
    l[b] = 0

for k in ans:
    print(k)

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

int main() {
	
		long long int n, x, t;
		cin>>n>>x>>t;
		
		// 20 12 6
		// 33 7  4
		if (x > n) cout<<t;
		else {
			long long int rem = n%x;	
			long long int temp = n/x;
			if (rem == 0) {
				cout<<temp*t;
			} else {
				cout<<(temp+1)*t;
			}
		}
		
	return 0;
}

Measured memory_bytes: 3644
#include<stdio.h>
int main(){

	int i,j,n,a[10000],min,max;
	long sum=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	max=a[0];	min=a[0];
	for(i=0;i<n;i++){
		if(max<a[i]){
			max=a[i];
		}else if(min > a[i]){
			min=a[i];
		}
		sum+=a[i];
	}
	printf("%d %d %ld\n",min,max,sum);
	return 0;
}

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

int main(){
  int H , N ;
  cin >> H >> N ;
  long long sum = 0 ;
  int a ;
  for(int i=0;i<N;i++){
    cin >> a ;
    sum += a ;
  }
  
  if(sum>=H) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}

/* Coding Space*/
int main(){
  string s; cin >> s;
  int a = 0, b = 0, c = 0;
  rep(i,s.size())
    if(s[i] == 'a')
      a++;
    else if(s[i] == 'b')
      b++;
    else
      c++;
  
  if(abs(a - b) >= 2 || abs(b - c) >= 2 || abs(c - a) >= 2)
    cout << "NO" << endl;
  else
    cout << "YES" << endl;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

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

int a,b;
int n,ans,s,f;

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

	cin>>a>>b>>n;
	REP(i,n) {
		cin>>s>>f;
		if((s<=a&&f>a)||(s<b&&f>=b)||(a<=s&&f<=b)) ans++;
	}
	cout<<min(1,ans)<<endl;

	return 0;
}



Measured memory_bytes: 3156
#include <cstdio>
#include <set>
#define MOD 1000000007
#define MOD2 998244353
#define MOD3 19260817
#define MOD4 19491001
using namespace std;
char s[5005];
int n;
bool check(int len)
{
 set<long long> se,se2,se3,se4;
 for(int i=1;i+len-1<=n;i++)
 {
  long long sum=0,sum2=0,sum3=0,sum4=0;
  if(i-len>0)
  {
   for(int j=i-len;j<i;j++)
    sum=(sum*97+s[j]-'a')%MOD,sum2=(sum2*97+s[j]-'a')%MOD2,sum3=(sum3*97+s[j]-'a')%MOD3,sum4=(sum4*97+s[j]-'a')%MOD4;
   se.insert(sum),se2.insert(sum2),se3.insert(sum3),se4.insert(sum4); 
  }
  sum=0,sum2=0,sum3=0,sum4=0;
  for(int j=i;j<=i+len-1;j++)
   sum=(sum*97+s[j]-'a')%MOD,sum2=(sum2*97+s[j]-'a')%MOD2,sum3=(sum3*97+s[j]-'a')%MOD3,sum4=(sum4*97+s[j]-'a')%MOD4;
  if(se.count(sum)&&se2.count(sum2)&&se3.count(sum3)&&se4.count(sum4))return true;
 }
 return false;
}
int main()
{
 scanf("%d",&n);
 scanf("%s",s+1);
 int l=0,r=n/2;
 while(l<r)
 {
  int mid=(l+r+1)>>1;
  if(check(mid))l=mid;
  else r=mid-1;
 }
 printf("%d\n",l);
 return 0;
}

Measured memory_bytes: 1152
#include<algorithm>
#include<cstdio>
#define rep(i,a) for(int i=0;i<(a);++i)

const int MAX_N = 100, MAX_W = 10000;

int N, W;
int v[MAX_N], w[MAX_N];
int dp[MAX_N+1][MAX_W+1];

int main()
{
    scanf( "%d%d", &N, &W );
    rep( i, N )
        scanf( "%d%d", v+i, w+i );

    rep( i, N ) rep( j, W+1 )
    {
        if( j-w[i] >= 0 )
            dp[i+1][j] = std::max( dp[i][j], dp[i+1][j-w[i]]+v[i] );
        else
            dp[i+1][j] = dp[i][j];
    }

    printf( "%d\n", dp[N][W] );

    return 0;
}

Measured memory_bytes: 6636
import heapq


N = int(input())
tree = {i+1:[] for i in range(N)}
route = [10**20 for i in range(N+1)]
visited = [False for i in range(N+1)]

for i in range(N-1):
    a, b, c = list(map(int, input().split()))
    tree[a].append((c, b))
    tree[b].append((c, a))

Q, K = list(map(int, input().split()))

route[K], visited[K] = 0, True
queue = tree[K]

while len(queue):
    c, r = heapq.heappop(queue)

    if not visited[r]:
         visited[r], route[r] = True, c
         for cost, next_r in tree[r]:
             if not visited[next_r]:
                 heapq.heappush(queue, (route[r]+cost, next_r))

for i in range(Q):
    x, y = list(map(int, input().split()))
    print(route[x]+route[y])


Measured memory_bytes: 61820
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
	int n; string s;
	cin >> n >> s;
	int c = 0;
	int d = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '(') {
			c++;
		}
		else {
			if (c > 0) {
				c--;
			}
			else {
				d++;
			}
		}
	}
	for (int i = 0; i < d; i++) {
		cout << '(';
	}
	cout << s;
	for (int i = 0; i < c; i++) {
		cout << ')';
	}
	cout << endl;
	return 0;
}

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

#define ll long long
#define ld long double

template <typename T>
boolean vmax(T& a, T b) {
	return (a < b) ? (a = b, true) : (false);
}

const int N = 1e5 + 5;
const ll llf = 1e17;
const int inf = (signed) (~0u >> 2);

ll gcd(ll a, ll b) {
	return (b) ? (gcd(b, a % b)) : (a);
}

typedef class Fraction {
	public:
		ll a, b;

		Fraction() : a(0), b(1) {	}
		Fraction(ll a, ll b) : a(a), b(b) {	}

		boolean operator < (Fraction B) const {
			return ((ld) a) * B.b - ((ld) b) * B.a < 0;
		}
		boolean operator > (Fraction B) const {
			return ((ld) a) * B.b - ((ld) b) * B.a > 0;
		}
} Fraction;

#define pii pair<int, int>

typedef class Item {
	public:
		int a, b, id;

		Item() {	}
		Item(int a, int b, int id) : a(a), b(b), id(id) {	}

		int maxval() const {
			return max(a, b);
		}
		boolean operator < (Item i) const {
			return maxval() < i.maxval();
		}
} Item;

int n;
vector<Item> E;
ll _presum[N], *presum;

int main() {
	scanf("%d", &n);
	ll _sum = 0;
	for (int i = 1, a, b; i <= n; i++) {
		scanf("%d%d", &a, &b);
		E.emplace_back(a, b, i);
		_sum += max(b - a, 0);
	}
	sort(E.begin(), E.end());
	Fraction ans (0, 1), I (1, 1);
	presum = _presum + 1;
	presum[-1] = 0;
	for (int i = 0; i < n; i++)
		presum[i] = presum[i - 1] + E[i].maxval();
	for (int j = 0; j < n; j++) {
		ll sum = _sum, ts;
		Item& e = E[j];
		if (e.a > e.b)
			sum += e.b - e.a;
		int l = 0, r = n - 1, mid;
#define calc(p) (presum[p] - (p >= j) * e.maxval())
		while (l <= r) {
			mid = (l + r) >> 1;
			ts = calc(mid);
			if (ts <= sum) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		Fraction tmp (sum - calc(l - 1), e.b);
		tmp = min(tmp, I);
		tmp.a += tmp.b * (l - (l > j));
		ans = max(ans, tmp);
	}
	ll g = gcd(ans.a, ans.b *= n);
	ans.a /= g;
	ans.b /= g;
	printf("%lld %lld\n", ans.a, ans.b);
	return 0;
}


Measured memory_bytes: 2292
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, a, n) for (int i = (a); i < (n); ++i)
using namespace std;
using ll = long long;
using uint = unsigned int;
const ll mod = (ll)1e9 + 7;

int main() {
  ll n, d;
  cin >> n >> d;
  int count = 0;
  rep(i, n) {
    ll x, y;
    cin >> x >> y;
    if (x * x + y * y <= d * d) count++;
  }
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var))
#define Rep(var,init,cnt) for(int (var)=(init); (var)<(int)(cnt); ++(var))
#define ran(var,vec) for(auto &(var):(vec))
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define SUM(v) accumulate(all(v),0)
#define tget(tp,idx) get<idx>(tp)
#define TF(flag) ((flag)?1:0)
#define YN(flag) cout<<(flag?"YES":"NO")<<endl;
#define Yn(flag) cout<<(flag?"Yes":"No")<<endl;
#define yn(flag) cout<<(flag?"yes":"no")<<endl;
#define Cout(v) cout<<(v)
#define COUT(v) cout<<(v)<<endl
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using ti = tuple<int,int,int>;
using tl = tuple<ll,ll,ll>;

template<typename T>
using vec = vector<T>;
template<typename T>
using mat = vector<vec<T>>;
template<typename T>
using cub = vector<mat<T>>;
template<typename T>
using val = valarray<T>;

template<typename T>
using pq = priority_queue<T>;
template<typename T>
using rpq = priority_queue<T,vec<T>,greater<T>>;

template<typename T1,typename T2>
ostream &operator<<(ostream &os, const pair<T1,T2> &p){
  os<<p.first<<" "<<p.second;
  return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is, pair<T1,T2> &p){
  is>>p.first>>p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  return os;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &v){
  for(T &in:v) is>>in;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const valarray<T> &v){
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  return os;
}

template<typename T>
istream &operator>>(istream &is, valarray<T> &v){
  for(T &in:v) is>>in;
  return is;
}

// Usual Template End ===================
// Template End =========================

constexpr int MOD=1e9+7;
locale LOCATE=locale::classic();

int main(void){
  string s; cin>>s;
  int ans=s.size()/2;
  rep(i,s.size()) ans-=TF(s[i]=='p');
  COUT(ans);
}











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

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

const int MN = 100010;

int N;
pii P[MN];
vector<pii> V;
int chk[MN];

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &P[i].first, &P[i].second);
        V.push_back(pii(P[i].first, 2 * i));
        V.push_back(pii(P[i].second, 2 * i + 1));
    }

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

    ll sum = 0;
    for(int i = 0; i < N; i++) {
        sum += V[i].first;
    }
    bool bad1 = false;
    for(int i = 1; i < N; i++) {
        if(V[i].second % 2 != V[i - 1].second % 2) {
            bad1 = true;
            break;
        }
    }

    bool bad2 = true;
    for(int i = 0; i < N; i++) {
        if(chk[ V[i].second / 2 ]) {
            bad2 = false;
            break;
        }
        chk[ V[i].second / 2 ] = 1;
    }

    if(bad1 && bad2) {
        if(V[N].second / 2 == V[N - 1].second / 2) sum += min(V[N].first - V[N - 2].first, V[N + 1].first - V[N - 1].first);
        else sum += V[N].first - V[N - 1].first;
    }
    printf("%lld", sum);
}


Measured memory_bytes: 3056
#include<bits/stdc++.h>
using namespace std;
int cnt[100010];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    long long answer = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        ++cnt[x];
        answer += x;
    }
    int q;
    cin >> q;
    while (--q > -1) {
        int a, b; 
        cin >> a >> b;
        answer -= 1LL * cnt[a] * a;
        answer += 1LL * cnt[a] * b;
        cnt[b] += cnt[a];
        cnt[a] = 0;
        cout << answer << '\n';
    }
}

Measured memory_bytes: 3972
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC diagnostic error "-std=c++14"

#define isNum(a) (a>='0'&&a<='9')
#define SP putchar(' ')
#define EL putchar('\n')
#define ri register int

template<class T>
inline void in(T&);
template<class T>
inline void out(const T&);

typedef long long ll;
using std::min;
using std::max;
using std::abs;
using std::sort;
using namespace std;

int a,b,c;

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    in(a);in(b);in(c);
    out(c%max(a,b)==0?c/max(a,b):c/max(a,b)+1);EL;
    return 0;
}

template<class T>
void in(T &Re)
{
    T k=0;
    char ch=getchar();
    int flag=1;
    while (!isNum(ch))
	{
        if (ch=='-')
		{
            flag=-1;
        }
        ch=getchar();
    }
    while (isNum(ch))
	{
        k=(k<<1)+(k<<3)+ch-'0';
        ch=getchar();
    }
    Re=flag*k;
}

template<class T>
void out(const T &Wr)
{
    if (Wr<0)
	{
        putchar('-');
        out(-Wr);
    }
	else
	{
        if (Wr<10)
		{
            putchar(Wr+'0');
        }
		else
		{
            out(Wr/10);
            putchar((Wr%10)+'0');
        }
    }
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,c;
    cin>>a>>b;
    c=(b-a)%2;
    if(a>0)
    {
        cout<<"Positive\n";
    }
    if(a<=0&&b>=0)
    {
        cout<<"Zero\n";
    }
    if(a<0&&b<0)
    {
        if(c==0)
        {
            cout<<"Negative\n";
        }
        else cout<<"Positive\n";
    }
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, X = map(int, raw_input().split())
x = map(int, raw_input().split())[::-1]

DP = [0] * (N + 1)

for i in range(N):
    DP[i + 1] = DP[i] + x[i]

ans = 10 ** 18

for i in range(1, N + 1):
    S = i * X + N * X
    for j in range(0, N + 1, i):
        cost = max(5, 3 + (j / i) * 2)
        pos = min(N, j + i)
        S += cost * (DP[pos] - DP[j])
    ans = min(S, ans)

print ans

Measured memory_bytes: 56260
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
	int n; cin >> n;
	int h[n+10];
	int cost[n+10];
	
	for(int i = 0; i < n; i++){
		cin >> h[i];
	}

	

	for(int i = 0; i < n; i++){
		if(i == 0){
			cost[0] = 0;
		} else if(i == 1){
			cost[1] = cost[0] + abs(h[1] - h[0]);
		} else {
			cost[i] = min(cost[i-1] + abs(h[i-1] - h[i]), cost[i-2] + abs(h[i-2] - h[i]));
		}
		//cout << i <<": "  <<cost[i] << endl;
	}
	cout << cost[n-1] << endl;
}

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = 100005;
vector<pair<int, ll> > g[N];
ll dist[N];

void dfs(int v, int p){
	for(auto x : g[v]){
		if(x.first == p)continue;
		dist[x.first] = dist[v] + x.second;
		dfs(x.first, v);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout<<setprecision(32);

	int n; cin>>n;
	for(int i = 1; i < n; i++){
		int u, v, w;
		cin>>u>>v>>w;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	dist[1] = 0; dfs(1, -1);
	for(int i = 1; i <= n; i++){
		cout<<(dist[i]&1)<<'\n';
	}


	return 0;
}

Measured memory_bytes: 10240
import java.util.*;

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

        int N = sc.nextInt();
        double[] x = new double[N];
        String[] u = new String[N];
        double ans = 0;

        for(int i=0; i<N; i++){
            x[i] = sc.nextDouble();
            u[i] = sc.next();
            if(u[i].equals("JPY")){
                ans += x[i];
            }
            else if(u[i].equals("BTC")){
                ans += x[i] * 380000;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 22612
I=lambda:[int(i)for i in input().split()]
F=1<<65
r=range
n,m=I()
X=set([0,F,-F])
Y=set(X)
R=[((-F,F),F),((-F,F),-F)]
H=[(F,(-F,F)),(-F,(-F,F))]
for i in r(n):a,b,c=I();R.append(((a,b),c));Y.add(c);X.add(a);X.add(b)
for i in r(m):a,b,c=I();H.append((a,(b,c)));X.add(a);Y.add(b);Y.add(c)

xdc=dict(enumerate(sorted(X)))
nx=len(xdc)
ydc=dict(enumerate(sorted(Y)))
ny=len(ydc)
 
h=dict(zip(xdc.values(),xdc.keys()))
w=dict(zip(ydc.values(),ydc.keys()))
 
V=[[0]*(nx+1+1)for i in r(ny+1+1)]
U=[i[:]for i in V]

for (a,b),c in R:U[w[c]][h[a]]+=1;U[w[c]][h[b]]+=-1
for i in r(ny+1):
 for j in r(nx):
  U[i][j+1]+=U[i][j]
        
for d,(e,f) in H:V[w[e]][h[d]]+=1;V[w[f]][h[d]]+=-1
for j in r(nx+1):
 for i in r(ny):
  V[i+1][j]+=V[i][j]

v=[[0]*(nx+1) for i in r(ny+1)]
q=[(h[0],w[0])]
v[w[0]][h[0]]=1

a=0
while q:
 cx,cy=q.pop();a+=(xdc[cx]-xdc[cx+1])*(ydc[cy]-ydc[cy+1])
 for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
  k=0;nbx=cx+dx;nby=cy+dy
  if(0<=nbx<nx)*(0<=nby<ny)*v[nby][nbx]==0:k=U[-~dy//2+cy][cx]==0 if dy!=0 else V[cy][-~dx//2+cx]==0
  if k:q.append((nbx,nby));v[nby][nbx]=1
if a>=F:a='INF'
print(a)


Measured memory_bytes: 535344
#include <cstdio>
#include <cstring>

using namespace std;

const int dy[3][13] = {
	{-1,0,0,0,1},
	{-1,-1,-1,0,0,0,1,1,1,},
	{-2,-1,-1,-1,0,0,0,0,0,1,1,1,2}},
		  dx[3][13] = {
	{0,-1,0,1,0},
	{-1,0,1,-1,0,1,-1,0,1},
	{0,-1,0,1,-2,-1,0,1,2,-1,0,1,0}},
	dnum[3] = {5,9,13};


int main(void){
	int p[10][10], x, y, size, i, j, ans1, ans2;
		memset(p,0,sizeof(p));
	while(scanf("%d%*c%d%*c%d",&x,&y,&size) != EOF){
		size--;
		for(i = 0;i < dnum[size];i++){
			if(0 <= y + dy[size][i] && y + dy[size][i] < 10 && 0 <= x + dx[size][i] && x + dx[size][i] < 10){
				p[y + dy[size][i]][x + dx[size][i]]++;
			}
		}
		ans1 = ans2 = 0;
	}
	for(i = 0;i < 10;i++){
		for(j = 0;j < 10;j++){
			if(p[i][j] == 0){
				ans1++;
			}
			if(ans2 < p[i][j]){
				ans2 = p[i][j];
			}
		}
	}
	printf("%d\n%d\n",ans1,ans2);
	return 0;
}

Measured memory_bytes: 1032
#include<bits/stdc++.h>
using namespace std;
#define int long
using pi=pair<int,int>;
signed main(){
    int n, m, c = 0, s = 0;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& i : a) cin >> i, s += i;
    sort(a.rbegin(), a.rend());
    for (int i = 0; i < m;++i){
        if (a[i] * 4 * m < s) return cout << "No", 0;
    }
    cout << "Yes";
}

Measured memory_bytes: 256
using System;
using static System.Console;
using System.Collections.Generic;
using System.Collections;

namespace Grobal
{
	class Program
	{
		static void Main(string[] args)
		{
			int a = int.Parse(ReadLine());
			int b = int.Parse(ReadLine());
			int c = 0;
			for (int i = 1; i < 4;i++)
			{
				if (a + b + i == 6) c = i;
			}
			WriteLine(c);
		}
    }
}

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


#define max_3base 59050
int main(){

    int N;
    cin >> N;

    int cnt = 0;
    for(int i = 1; i <= max_3base; i++)
    {
        int flag[3] = {0};
        int num = i;
        vector<long long> buf;
        int ans;
        while((num - 1) / 3 != 0){
            buf.push_back((num - 1) % 3);
            flag[(num - 1) % 3] = 1;
            num -= 1;
            num /= 3;
        } 
        buf.push_back((num - 1) % 3);
        flag[(num - 1) % 3] = 1;

        if (flag[0]*flag[1]*flag[2] == 0) continue;

        long long tmp = 0;
        long long amp = 1;
        for(int i = 0; i < buf.size(); i++)
        {
            tmp += (3 + (buf[i] * 2)) * amp;
            amp *= 10;
        }


        if (N < tmp) break;
        
        //cout << tmp << endl;
        cnt++;

    }

    cout << cnt << endl;


}

Measured memory_bytes: 256