akhauriyash/Code-Regression huggingface dataset:
//#define _GLIBCXX_DEBUG
//#pragma GCC optimize "trapv"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma optimization_level 3
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")


#define pb push_back 
#define f first
#define s second
#define min3(a, b, c) min(min(a, b), c)
#define max3(a, b, c) max(max(a, b), c)
#define all(v) v.begin(), v.end()

typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int INF = 1e9;
//const ll INF = 1e18;
const ll mod = 1000000007;
// const ll mod = 998244353;

vl fact;
void modfac(int n){
    fact.resize(n+1);
    fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = (i*fact[i-1])%mod;
    }
    return;
}
ll mpow(ll a, ll b){
    ll x = 1;
    while(b > 0){
        if(b&1){
            x = (x*a)%mod;
        }
        a = (a*a)%mod;
        b >>= 1;
    }
    return x;
}
ll madd(ll a, ll b){
    return (a+b)%mod;
}

ll msub(ll a, ll b){
    return (a - b + mod)%mod;
}
ll mmul(ll a, ll b){
    return ((a%mod)*(b%mod))%mod;
}
ll modinv(ll b){
    ll x = mpow(b, mod-2);
    return x;
}
ll mdiv(ll a, ll b){
    return mmul(a, modinv(b));
}
ll nck(ll n, ll k){
    return mdiv(fact[n], mmul(fact[n-k], fact[k]));
}
void solve(int tc){
    modfac(1e6);
    ll n;
    cin >> n;

    ll rem = mpow(8, n);
    ll rem2 = 0;
    for(int i = 1; i <= n; i++){
        rem2 = madd(rem2, mmul(nck(n, i), mpow(8, n - i)));
    }
    rem2 = mmul(rem2, 2);

    rem = madd(rem, rem2);

    cout << msub(mpow(10, n), rem) << "\n";

}

int main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    
    int tc = 1;
    //cin >> tc;
    for (int t = 0; t < tc; t++) solve(t);

    return 0;
}

Measured memory_bytes: 11048
# coding: utf-8


def solve(*args: str) -> str:
    S, T = args
    candidates = []
    for i in range(len(S)-len(T)+1):
        text = S[:i]

        for j in range(len(T)):
            if S[i+j] != T[j] and S[i+j] != '?':
                text = ''
                break
            text += T[j]

        if text:
            text += S[len(text):]
            candidates.append(text.replace('?', 'a'))

    candidates.sort()

    return candidates[0] if candidates else 'UNRESTORABLE'


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long A,B;
	cin>>A>>B;
	long i;
	if(A%B==0) cout<<-1<<endl;
	else{
		for(i=2;A*i%B==0;i++);
		cout<<A*i;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
using namespace std;
#define REP(i,a,n) for(int i = a ; i < n ; i++)
#define rep(i,n) REP(i,0,n)

typedef long long ll;

int dp[52][52];
char t[52][52];

int main(){
  int h,w;

  while(cin>>h>>w){
    rep(i,h){
      cin>>t[i];
    }

    rep(i,h) rep(j,w) dp[i][j] = INT_MAX;
    dp[0][0] = t[0][0] - '0';
    rep(i,h){
      rep(j,w){
        if(i+1 < h) dp[i+1][j] = min(dp[i+1][j],dp[i][j]+t[i+1][j]-'0');
        if(j+1 < w) dp[i][j+1] = min(dp[i][j+1],dp[i][j]+t[i][j+1]-'0');
      }
    }
    cout<<dp[h-1][w-1]<<endl;
  }
}

Measured memory_bytes: 0
N, D = map(int, input().split())
XY = [list(map(int, input().split())) for i in range(N)]

count = 0
for i in range(N):
    if (XY[i][0] ** 2 + XY[i][1] ** 2) ** (1/2) <= D:
        count += 1

print(count)


Measured memory_bytes: 45840
#include<iostream>
using namespace std;
 
int main(){
  int cost;
  cin >> cost;
  int change; 
  if (cost%1000){
  	change = 1000 - cost%1000;
  }
  else {
  	change = 0;
  }
  
  cout << change;
  
  return 0;
}

Measured memory_bytes: 3636
import collections
N = int(input())
ans = 0
ans_table = collections.defaultdict(int)
prev = []
for i in range(1, N+1):

    tmp = i
    for j in range(2, int((i**0.5//1))+1):
        if tmp % j == 0:
            count = 0
            while tmp % j == 0:
                count += 1
                tmp = tmp//j
            ans_table[j] += count
    if tmp != 1:
        ans_table[tmp] += 1

ans_list = list(ans_table.values())
ans = 1
for x in ans_list:
    ans *= (x+1)

print(ans % ((10**9) + 7))


Measured memory_bytes: 3316
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    Map<String, Integer> treeMap = new TreeMap<>();
    
    for(int i=0; i<N; i++){
      String S =sc.next();
      if(!treeMap.containsKey(S)){
        treeMap.put(S, 1);
      }else{
        treeMap.put(S, treeMap.get(S) + 1);
      }
    }
    int max = 0;
    for(String key: treeMap.keySet()){
      if(max < treeMap.get(key)){
        max = treeMap.get(key);
      }
    }
    for(String key: treeMap.keySet()){
      if(treeMap.get(key) == max){
        System.out.println(key);
      }
    }
  }
}
    

Measured memory_bytes: 79856
package main

import (
	"fmt"
	"sort"
)

func main() {
	// Code for B - 1 Dimensional World's Tale
	var N, M, X, Y int
	fmt.Scanf("%d %d %d %d", &N, &M, &X, &Y)

	x := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scanf("%d", &x[i])
	}
	sort.Sort(sort.IntSlice(x))

	y := make([]int, M)
	for i := 0; i < M; i++ {
		fmt.Scanf("%d", &y[i])
	}
	sort.Sort(sort.Reverse(sort.IntSlice(y)))

	var flag int = 0
	for Z := X + 1; Z < Y; Z++ {
		if x[N-1] < Z && y[M-1] >= Z {
			flag = 1
			break
		}
	}

	if flag == 1 {
		fmt.Println("No War")
	} else {
		fmt.Println("War")
	}
}


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

void solve(long long A, long long B, long long C, long long D)
{
    cout << (min(A, B) + min(C, D)) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long A;
    scanf("%lld", &A);
    long long B;
    scanf("%lld", &B);
    long long C;
    scanf("%lld", &C);
    long long D;
    scanf("%lld", &D);
    solve(A, B, C, D);
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import Counter
S=input().strip()
K=int(input())
C=Counter(S)

if S[0]!=S[-1]:
    A=0

    ind=1
    while ind<len(S):
        if S[ind]==S[ind-1]:
            A+=1
            ind+=2
        else:
            ind+=1

    print(A*K)

elif len(C)==1:
    print(len(S)*K//2)

else:
    front=1
    back=1

    for i in range(1,len(S)):
        if S[i]==S[i-1]:
            front+=1
        else:
            frd=i
            break

    for i in range(len(S)-2,-1,-1):
        if S[i]==S[i+1]:
            back+=1
        else:
            bcd=i
            break

    #print(frd,bcd,front,back)

    ANS=(front+back)//2*(K-1)+front//2+back//2

    ind=frd+1
    A=0

    while ind<=bcd:
        if S[ind]==S[ind-1]:
            A+=1
            ind+=2
        else:
            ind+=1

    #print(A)

    print(ANS+A*K)

    
        



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

int main(){
    int ans=0;
    int n,q;
    cin >>n;
    vector<vector<pair<int,int>>> adj(n);
    bool visit[n];
    int color[n];
    color[0]=0;

    for (int i = 0; i < n-1; i++){
        visit[i]=false;
        
        int u,v,w;
        cin>>u>>v>>w;
        --u;--v;

        adj[u].push_back(make_pair(v,w));
        adj[v].push_back(make_pair(u,w));
    }
    visit[n-1]=false;


    queue<int> que;
    que.push(0);

    while(que.size()){
        int cur=que.front();
        visit[cur]=true;
        que.pop();

        //cout << cur<<"::"<<px[cur]<< endl;//

        for (int j = 0; j < (int)adj[cur].size(); j++){
            

            int nex=adj[cur][j].first;
            if(visit[nex]==true)continue;

            //begin

            if(adj[cur][j].second % 2 == 1){

                color[nex] = (color[cur]+1)%2;
            
            }else{

                color[nex] = color[cur];
            
            }

            //end

            que.push(nex);

            //cout << cur<<"--"<<nex<< endl;//
        }
        

    }

    for (int i = 0; i < n; i++){
        cout << color[i] << '\n';
    }
    




    //cout <<fixed<<setprecision(16)<< << endl;
    //cout << ans << endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 6912
program name
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: i,ans
    character(100000):: s
    character(1):: ns

    read*, s
    ns = s(1:1)
    ans=0
    do i=2,len_trim(s)
        if (s(i:i) /= ns) then
            ans=ans+1
            ns=s(i:i)
        end if
    end do

    print'(i0)', ans
end program name

Measured memory_bytes: 700
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

struct UnionFind {
  vector<int> par; // par[i]が親を表す

  // コンストラクタ
  UnionFind(int n) {
    par = vector<int>(n);
    for (int i = 0; i < n; i++) {
      par[i] = i;
    }
  }

  // データxの根を求める
  int root(int x) {
    if (par[x] == x)
      return x;
    return par[x] = root(par[x]); // 木構造の縮約を行っている
  }

  // xとyの親が違うとき、マージする。そのときyの根がxの根の子になる
  void merge(int x, int y) {
    int rootx = root(x);
    int rooty = root(y);
    if (rootx == rooty)
      return;
    par[rooty] = rootx;
  }

  // 同じグループに属しているか
  bool isSame(int x, int y) { return root(x) == root(y); }
};

struct edge {
  int u, v, cost;
};

bool comp(const edge &e1, const edge &e2) { return e1.cost < e2.cost; }

// 最小全域木のコストを求める
int kruskal(vector<edge> &edges, const int size) {
  sort(edges.begin(), edges.end(), comp);
  UnionFind uf(size);
  int res = 0;
  for (auto e : edges) {
    if (!uf.isSame(e.u, e.v)) {
      uf.merge(e.u, e.v);
      res += e.cost;
    }
  }
  return res;
}

int main() {
  int n;
  cin >> n;
  vector<pair<int, int>> vx(n), vy(n);
  vector<edge> es;
  REP(i, n) {
    int x, y;
    cin >> x >> y;
    vx[i] = make_pair(x, i);
    vy[i] = make_pair(y, i);
  }

  sort(vx.begin(), vx.end());
  sort(vy.begin(), vy.end());

  FOR(i, 1, n) {
    es.push_back(
        {vx[i - 1].second, vx[i].second, abs(vx[i].first - vx[i - 1].first)});
    es.push_back(
        {vy[i - 1].second, vy[i].second, abs(vy[i].first - vy[i - 1].first)});
  }

  cout << kruskal(es, n) << endl;
}


Measured memory_bytes: 6388
#include<iostream>
#define MOD 1000003

using namespace std;

long long fac_dic[1000010], fac_inv_dic[1000010], inv_d[1000010];


long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod を計算する
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

void yield_fac(){
    fac_dic[0]=1;
    fac_dic[1]=1;
    fac_inv_dic[0]=0;
    fac_inv_dic[1]=1;
    inv_d[0]=1;
    inv_d[1]=1;
    for(int i=2;i<1000010;i++){
        fac_dic[i]=(fac_dic[i-1]*i)%MOD;
        fac_inv_dic[i]=modinv(fac_dic[i], MOD);
        inv_d[i]=modinv(i,MOD);
    }
}

void solve(long long tmpx, long long tmpd, long long tmpn){
    long long ans=0;
    long long xd = (tmpx * inv_d[tmpd])%MOD;
    if(tmpd==0){
        ans=modpow(tmpx, tmpn, MOD);
    }
    else{
        if(xd<= 1000003 && 1000003 <= xd+tmpn-1){
            ans=0;
        }
        else{
            ans=(((modpow(tmpd, tmpn, MOD)*fac_dic[(xd+tmpn-1)])%MOD)*fac_inv_dic[xd-1])%MOD;
        }
    }
    cout << ans << endl;
}


int main(){
    int q;
    cin >> q;
    yield_fac();
    for(int i=0;i<q;i++){
        long long tmpx, tmpd, tmpn;
        cin >> tmpx >> tmpd >> tmpn;
        solve(tmpx, tmpd, tmpn);
    }
}

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

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    string ans;
    if (a < b) {
        ans = "a < b";
    }
    else if (a > b) {
        ans = "a > b";
    }
    else {
        ans = "a == b";
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C;
  
  cin >> A >> B >> C ;
  
  //１回A円で聞くことができる
  //自分が払うのはB円
  //C回聞くと満足
  
  
  if(A > B){
    cout << 0 << endl;
  }
  else if(A < B){
    int d ;
    d = B / A ;
    if(d>C){
     cout << C << endl;
    }
    else{
     cout << d << endl; 
    }
  }
  else{
   C = B/A;
   cout << C << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <ctype.h>
#include <algorithm>
#include <cmath>

#define REP(i, n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define square(x) (x) * (x)
#define cube(x) (x) * (x) * (x)

const int INF = 1e9;

using namespace std;


int main() {
    int n;
    cin >> n;
    int a[n];
    int count = 0;
    REP(i, n) cin >> a[i];
    REP(i, n){
        int mini = i;
        for(int j = i; j < n ; j++){
            if(a[j] < a[mini])
                mini = j;
        }
        if(i != mini){
            count++;
            swap(a[i], a[mini]);
        }
    }

    REP(i, n-1) {
        cout << a[i] << " ";
    }

    cout << a[n-1] << endl << count << endl;

    return 0;
}

Measured memory_bytes: 1160
#include <iostream>


using namespace std;

int main()
{
    int k,x;
    cin>>k>>x;

    for(int i = x-k+1; i < (x+k); i++)
    {
        if (i>= (-1000000)) {
            if (i<=1000000) {
                cout << i <<endl;
            }
            
        }
        
    }
    
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();

		String S = sc.next();
		sc.close();

		int[] start = new int[N+1];
		int[] end = new int[N+1];

		Arrays.fill(start, 999999);
		Arrays.fill(end, 999999);

		int scount = 0;
		int ecount = 0;

		if(S.substring(0, 1).equals("0")){
			start[0] = 0;
			scount++;
		}
		for(int i = 0 ; i < S.length()-1; i++){
			if(S.substring(i, i+1).equals("1") && S.substring(i+1,i+2).equals("0")){
				start[scount] = i+1;
				scount++;
			}
			if(S.substring(i, i+1).equals("0") && S.substring(i+1,i+2).equals("1")){
				end[ecount] = i;
				ecount++;
			}
		}

		int ans = 0;
		int count = 0;
		for(int i = 0 ; i < S.length(); i++){
			int p = start[K+count];
			if(start[K+count] == 999999){
				p = S.length();
			}
			//System.out.println(p-i);
			if(ans < p-i){
				ans = p-i;
			}

			if(end[count] == 999999){
				break;
			}

			i = end[count];
			count++;

		}

		System.out.println(ans);

	}
}


Measured memory_bytes: 42236
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const long long mod = 1e9+7;
long long power(long long a, long long b, long long m = mod) {
    if(b < 0) {
        return power(power(a, -b), mod-2);
    }
    long long x = 1;
    while(b) {
        if(b & 1) {
            x = 1ll * x * a % m;
        }
        a = 1ll * a * a % m;
        b /= 2;
    }
    return x;
}
const int N = 4000+9;
ll f[N][N][3];
ll fs[N][3];
int a[N];
signed main() {  
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    string s; cin >> s;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'R') a[i] = 1;
        else if(s[i] == 'G') a[i] = 2;
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(a[i] != a[j]) {
                f[i][i-j][a[i]^a[j]^3]++;
                fs[i][a[i]^a[j]^3]++;
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(a[i] != a[j]) {
                ans += fs[j][a[i]] - f[j][i-j][a[i]];
            }
        }    
    }
    cout << ans << "\n";






    return 0;
    
}

Measured memory_bytes: 206648
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
    int64_t x;
    mint(int64_t x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(int64_t t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    //for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) {
        cin >> a[i];
    }

    mint ans;
    rep(i, 60) {
        ll ze = 0, on = 0;
        rep(j, n) {
            if((a[j] >> i)&1) on++;
            else ze++;
        }
        ans += mint(on)*ze*mint(2).pow(i);
    }

    cout << ans << endl;
}

Measured memory_bytes: 2560
while 1:
  try:
    c=[0]*101
    while 1:
      a,b=map(int,raw_input().split())
      if a==b==0:break
      c[a]+=1
      c[b]+=1
    c=map(lambda x:x%2,c)
    if c[1]==1==c[2] and sum(c[3:])==0:print"OK"
    else:print"NG"
  except:break

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

using namespace std;

int main() {
    int p, n;
    long long sump = 0, sumn = 0, cnt = 0;
    while (scanf("%d,%d", &p, &n) != EOF) {
        cnt++;
        sumn += n;
        sump += p * n;
    }
    cout << sump << endl;

    int aven = (int)((double)sumn / cnt + 0.5);
    cout << aven << endl;

    return 0;
}


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

public class Main
{

	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
		int number = in.nextInt();
		ArrayList<Integer> list = new ArrayList<> (number);
		for(int i = 0; i < number; i++)
		{
			list.add(in.nextInt());
		}
		int max = list.get(0);
		int sum = 0;
		for(int i = 1; i < list.size(); i++)
		{
			int temp = list.get(i);
			sum += temp;
			if(temp > max)
			{
				sum += max;
				sum -= temp;
				max = temp;
			}
		}
//		System.out.println("max is " + max);
//		System.out.println("sum is " + sum);
		if(max < sum)
			System.out.println("Yes");
		else
			System.out.println("No");
	
	}

}

Measured memory_bytes: 23636
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  T.getLine
  ps <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  let
    (_, _, k) = foldr step (Nothing, Nothing, 0) $ ps
    step p (Just p', Just p'', k) = (Just p, Just p', if (p < p' && p' < p'') || (p'' < p' && p' < p) then succ k else k)
    step p (Just p', _, _) = (Just p, Just p', 0)
    step p _ = (Just p, Nothing, 0)
  print k

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 508
import java.util.*;
 
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		if(H%3==0 || W%3==0){
			System.out.println(0);
			return;
		}
		
		int h1 = H/2;
		int h2;
		if( H%2==0 ){
			h2 = h1;
		}else{
			h2 = h1+1;
		}
		int w1 = W/2;
		int w2;
		if( W%2==0 ){
			w2 = w1;
		}else{
			w2 = w1+1;
		}
		
		
		long a1 = W/3;
		if(a1==0)a1++;
		long a2 = (W-a1)*h1;
		long a3 = (W-a1)*h2;
		long cur = Math.max(a1*H,Math.max(a2, a3)) - Math.min(a1*H, Math.min(a2,a3));
		a1++;
		if(a1 < W){
			a2 = (W-a1)*h1;
			a3 = (W-a1)*h2;
			cur = Math.min(cur, Math.max(a1*H,Math.max(a2, a3)) - Math.min(a1*H, Math.min(a2,a3)));
		}
		
		a1 = H/3;
		if(a1==0)a1++;
		a2 = (H-a1)*w1;
		a3 = (H-a1)*w2;
		cur = Math.min(cur, Math.max(a1*W,Math.max(a2, a3)) - Math.min(a1*W, Math.min(a2,a3)));
		a1++;
		if(a1 < H){
			a2 = (H-a1)*w1;
			a3 = (H-a1)*w2;
			cur = Math.min(cur, Math.max(a1*W,Math.max(a2, a3)) - Math.min(a1*W, Math.min(a2,a3)));
		}
		
		cur = Math.min(cur, Math.min(H, W));
		System.out.println(cur);
		return;
	}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
 
int	main(void)
{
	string s, t;
	cin >> s >> t;
	int ans = 0;
	for (int i = 0; i < s.size(); i++) ans += (s[i] != t[i]);
	cout << ans << endl;
	return (0);
}

Measured memory_bytes: 3816
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,k;
  cin >> n ;
  cin>> k;
  vector<int> x(n);
  for(int i = 0;i<n;i++){
    cin >> x.at(i);
  }

  int sum = 0;
  for(int xi : x){
    if(xi > k-xi){
      sum+=(k-xi)*2;
    }else{
      sum+=xi*2;
    }
  }
  cout << sum << endl;

 
}

Measured memory_bytes: 256
import bisect
def addto(a, b, d):
    if a in d:
        d[a].append(b)
    else:
        d[a] = [b]

def check(A, B, d, coef):
    M = 10**50
    for x in d[A]:
        if x not in d[B]:
            continue
        for y in d[A][x]:
            yi = bisect.bisect_left(d[B][x], y)
            if yi < len(d[B][x]):
                M = min((d[B][x][yi] - y)*coef, M)
    return M
def main():
    N = int(input())
    dx = {"U":{}, "D":{}, "R":{}, "L":{}}
    dy = {"U":{}, "D":{}, "R":{}, "L":{}}
    dxpy = {"U":{}, "D":{}, "R":{}, "L":{}}
    dxmy = {"U":{}, "D":{}, "R":{}, "L":{}}
    for _ in range(N):
        x, y, u = input().split()
        x = int(x)
        y = int(y)
        addto(x, y, dx[u])
        addto(y, x, dy[u])
        addto(x+y, y, dxpy[u])
        addto(x-y, y, dxmy[u])
    for d in [dx, dy, dxpy, dxmy]:
        for j in d:
            for k in d[j]:
                d[j][k].sort()
    M = 10 ** 50
    M = min(M, check("U", "D", dx, 5))
    M = min(M, check("R", "L", dy, 5))
    M = min(M, check("R", "D", dxmy, 10))
    M = min(M, check("U", "L", dxmy, 10))
    M = min(M, check("U", "R", dxpy, 10))
    M = min(M, check("L", "D", dxpy, 10))
    return M
x = main()
if x < 10 ** 50:
    print(x)
else:
    print('SAFE')


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

int i,n;


int number;


long long int sum=0;


int min=0;


int max=0;


scanf("%d",&n);


for(i=0;i<n;i++)


{


scanf("%d",&number);


if(i==0)


{


min = number;


max = number;


}


if(number<min) min = number;


if(number>max)max = number;


sum += number;


}


printf("%d %d %lld\n",min,max,sum);


return 0;


}

Measured memory_bytes: 1032
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string>
using namespace std;

int main() {
	string ch, x;
	int a = 0;
	cin >> ch;
	cin >> x;
	for (int i = 0;i < ch.size() && a == 0;i++) {
		if (ch[i] == x[0]) {
			for (int j = 0;j < x.size();j++) {
				int ss = i + j;
				if (ss >= ch.size())ss = ss - ch.size();
				//cout << j << ":" << x.size() << endl;
				if (ch[ss] == x[j]) {
					a = 1;
				}else {
					a = 0;
					break;
				}
			}
		}
	}
	if(a == 1)cout << "Yes" << endl;
	if (a == 0)cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 3240
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

from collections import Counter
ctr = Counter(A)
d = ctr.most_common(1)[0][0]
x = A.index(d)
y = x+1 + A[x+1:].index(d)
f = x + N-y

MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = []
for i in range(1,N+2):
    ans.append((comb(N+1,i) - comb(f,i-1)) % MOD)
print(*ans, sep='\n')

Measured memory_bytes: 33084
D, G = [int(x) for x in input().split()]
lst = [[int(x) for x in input().split()] for i in range(D)]
bit = 0
min_n = float('inf')
while bit < (1 << D):
    # print('=====')
    # print(bit)
    # print('=====')
    score = 0
    n = 0
    for i in range(D):
        if bit & (1 << i):
            score += 100 * (i + 1) * lst[i][0] + lst[i][1]
            n += lst[i][0]
    #print('素点 = ', score)
    if score < G:
        #print('~つまみぐい~')
        max_i = -1
        for i in reversed(range(D)):
            if not bit & (1 << i):
                max_i = i
                break
        #print('max_i = ', max_i)
        if max_i >= 0:
            for j in range(lst[max_i][0]):
                score += 100 * (max_i + 1)
                if score >= G:
                    n += j + 1
                    break
            if score < G:
                bit += 1
                continue
    if min_n > n:
        min_n = n
    bit += 1
print(min_n)


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

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define chmax(a,b) (a<b?(a=b,1):0)
#define chmin(a,b) (a>b?(a=b,1):0)
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
const int INF = 1<<29;
typedef long long ll;
typedef pair<int,int> pii;


typedef vector<ll> vec;
typedef vector<vec> mat;

ostream &operator<<(ostream &os, const vec &a) {
  FOR(it, a) os << setw(6) << *it << " ";
  return os;
}
ostream &operator<<(ostream &os, const mat &a) {
  FOR(it, a) os << *it << endl;
  return os;
}

vec mul(const mat &A, const vec &b, ll mod) {
  vec c(A.size());
  REP(i,A.size())
    REP(j,A[i].size())
    c[i] = (c[i] + A[i][j]*b[j]) % mod;
  return c;
}

mat mul(const mat &A, const mat &B, ll mod) {
  mat C(A.size(), vec(B[0].size()));
  REP(i,A.size())
    REP(j,B[0].size())
    REP(k,B.size())
    C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % mod;
  return C;
}

mat pow(mat A, ll n, ll mod) {
  mat B(A.size(), vec(A.size()));
  REP(i,A.size())
    B[i][i] = 1;
  while(n) {
    if (n&1) B = mul(B, A, mod);
    A = mul(A,A,mod);
    n >>= 1;
  }
  return B;
}

int main() {
  int n,m,a,b,c,t;
  while(cin>>n>>m>>a>>b>>c>>t,n) {
    vec s(n);
    REP(i,n) cin>>s[i];
    mat A(n,vec(n));
    int hoge[3] = {a,b,c};
    REP(i,n) {
      int cnt = 0;
      for (int j=i-1; j<=i+1; ++j,++cnt) {
        if (j<0||j>=n) continue;
        A[i][j] = hoge[cnt];
      }
    }
    // cout << A << endl;
    A = pow(A,t,m);
    vec ans = mul(A,s,m);
    REP(i,n) {
      if (i) cout << " ";
      cout << ans[i];
    }
    cout << endl;
  }
}

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

int main()
{
    long long a, b;
    cin >> a >> b;

    if((a+b)%2)
    {
        cout << "IMPOSSIBLE\n";
    }
    else
    {
        cout << (a+b)/2 << endl;    }
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 1e5 + 5; 
using namespace std;

int n, a[N], c[N], cnt, ans; 

template < typename T >
inline T read()
{
	T x = 0, w = 1; char c = getchar();
	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * w; 
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("cpp.in", "r", stdin); 
#endif
	n = read <int> (); 
	for(int i = 1; i <= n; i++)
	{
		a[i] = read <int> (), c[a[i]]++; 
		if(c[a[i]] == 1) ans++; 
		if(c[a[i]] >= 3) c[a[i]] -= 2; 
	}
	for(int i = 1; i <= 100000; i++)
		if(c[i] == 2) cnt++;
	while(cnt >= 3) cnt -= 2;
	if(cnt & 1) printf("%d\n", ans - 1);
	else printf("%d\n", ans); 
	return 0; 
}


Measured memory_bytes: 3976
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int gcd = gcd(a,b);
		int cnt = 0;
		int ans = 0;
			for(int i = gcd; i >= 1; i--) {
				if(a%i == 0 && b%i == 0) {
					ans = i;
					cnt ++;
					if(cnt == c) {
						System.out.println(ans);
					}
				}
				
			}
		
		sc.close();
	}
	static int gcd (int a, int b) {
		int temp;
		while((temp = a%b)!=0) {
			a = b;
			b = temp;
		}
		return b;
	}
}



Measured memory_bytes: 23380
#include <stdio.h>
#include <string.h>

int main()
{
    char str[8];

    scanf("%s", str);

    if (strlen(str) == 2) {
        printf("%s\n", str);
    } else if (strlen(str) == 3) {
        putchar(str[2]); putchar(str[1]); putchar(str[0]);
        putchar('\n');
    }

    return 0;
}


Measured memory_bytes: 128
# Aizu Problem 00174: Badminton
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def badminton(game):
    a, b = 0, 0
    for x in game[1:]:
        if x == 'A':
            a += 1
        else:
            b += 1
    if a > b:
        a += 1
    else:
        b += 1
    return a, b


while True:
    game = input().strip()
    if game[0] == '0':
        break
    a, b = badminton(game)
    print(a, b)

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }



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

  int s, w;
  cin >> s >> w;
  if(s <= w) cout << "unsafe" << endl;
  else cout << "safe" << endl;
}

Measured memory_bytes: 3640
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=100000;

int n,m,col[maxn+5],A,B;
int E,lnk[maxn+5],son[maxm*2+5],nxt[maxm*2+5];

inline void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void Dfs(int x,int now=0,int fa=0)
{
    col[x]=now;now^=1;
    for (int j=lnk[x];j;j=nxt[j])
    {
        if (col[son[j]]==-1) Dfs(son[j],now,x);
        if (col[son[j]]!=now) printf("%lld\n",(LL)n*(n-1)/2-m),exit(0);
    }
}
int main(){
    scanf("%d%d",&n,&m);
	memset(col,255,sizeof(col));
    for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    Dfs(1);for (int i=1;i<=n;i++) if (col[i]) A++; else B++;
    return printf("%lld\n",(LL)A*B-m),0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int H, W;
  cin >> H >> W;
  vector< vector<int> > c(10, vector<int>(10));
  vector< vector<int> > a(H, vector<int>(W));
  for(int i=0;i<10;i++)
    for(int j=0;j<10;j++)
      cin >> c[i][j];
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
      cin >> a[i][j];

  for(int k=0;k<10;k++)
   for(int i=0;i<10;i++)
    for(int j=0;j<10;j++)
     c[i][j] = min<ll>(c[i][j], c[i][k]+c[k][j]);

  ll ans = 0;
  for(int i=0;i<H;i++) {
    for(int j=0;j<W;j++) {
      if(a[i][j] == -1) continue;
      ans += c[a[i][j]][1];
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define MOD 998244353
#define pb push_back
#define ll long long int
#define con 1000000007
using namespace std;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll i,j,m,n,k;
    ll t;
    cin>>n;
    vector<ll> a(n);
    for(i=0;i<n;i++)
        cin>>a[i];
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    ll s=a[0];
    ll r=1;
    if(n==2)
    {
        cout<<s<<"\n";
        return 0;
    }
    for(i=1;i<n;i++)
    {   
        r++;
        s+=a[i];
        if(r==n-1)
            break;
        r++;
        s+=a[i];
        if(r==n-1)
            break;
    }
    cout<<s<<"\n";
}





Measured memory_bytes: 4776
#include<bits/stdc++.h>
using namespace std;
int main(){
int h,n;
int o=0;
cin >> h >> n;
 vector<int>a(n);
 for(int i=0;i<n;i++) cin >> a[i];
 for(int i=0;i<n;i++){
   o=o+a[i];
 }
 if(o>=h) cout << "Yes";
 else if(o<h) cout << "No";
 return 0;
}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
#define mod (int)1000000007
#define MOD (int)10000000007
#define X 1001100011100001111ll
#define M 26388279066623ll
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for0e(i, n) for (int i = 0; i <= n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
#define ll long long
#define pb emplace_back
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define in(x) scanf("%d", &x)
#define rr return 0
#define prec(n) fixed<<setprecision(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define inf (int)(1e18)
#define ini(a, i) memset(a, i, sizeof(a))
#define vi vector<int> 
#define F first
#define S second
#define pi pair<int, int>
#define ppi pair<pair<int,int> , int >
#define vii vector<pi>
const int MAXN = (int)((1e5) + 100);
int max(int a,int b){if(a>b) return a; else return b;}
int min(int a,int b){if(a<b) return a; else return b;} 
int gcd(int a,int b) { if (a == 0) return b; return gcd(b%a, a);}
int cbrt(int x){ int lo=1,hi=min(2000000ll,x);while(hi-lo>1){int mid=(lo+hi)/2;if(mid*mid*mid<x){lo=mid;}else hi=mid;}if(hi*hi*hi<=x) return hi;else return lo;} 
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int N =  (int)(1e6+5); 
// ========================================================
signed main(){
  #ifndef ONLINE_JUDGE
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  #endif
  fio;
    int n,k;
    cin>>n>>k;
    vi h(n);
    for(auto &x : h) cin>>x;
    vi dp(n,inf);
    dp[0] = 0;
    for(int i=0;i<n;i++){
        for(int j=1;j<=k;j++){
            if(i+j < n){
                dp[i+j] = min(dp[i+j], dp[i] + abs(h[i+j]-h[i]));
            }
        }
    }
    cout<<dp[n-1]<<endl;
  rr;
}



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

using namespace std;

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

int main()
{
	long long int M , N;
	while(cin >> M >> N , M || N)
	{
		vector<vector<char>>D(M , vector<char>(N));
		set<string>SS;
		string ans;
		for(size_t i = 0; i < M; i++)
		{
			for(size_t j = 0; j < N; j++)
			{
				cin >> D[i][j];
			}
		}
		for(long long int i = 0; i < M; i++)
		{
			for(long long int j = 0; j < N; j++)
			{
				long long int startx = j , starty = i;
				for(long long int k = 0; k < 8; k++)
				{
					long long int p = 1;
					string s;
					s.push_back(D[starty][startx]);
					while(!( ( startx + p*dx[k] + N * 2000 ) % N == startx && ( starty + p*dy[k] + M * 2000 ) % M == starty ))
					{
						s.push_back(D[( starty + p*dy[k] + M * 2000 ) % M][( startx + p*dx[k] + N * 2000 ) % N]);
						if(s.length() >= ans.length())
						{
							auto s2 = s;
							reverse(s2.begin() , s2.end());
							if(s2 <= s)
							{
								if(SS.find(s2) != SS.end() && ( ans.length() < s2.length() || ans > s2 ))
								{
									ans = s2;
								} else
								{
									SS.insert(s2);
								}
							}
						}
						p++;
					}
				}
			}
		}
		if(ans.length() <= 1)
		{
			cout << 0 << endl;
		} else
		{
			cout << ans << endl;
		}
	}
}

Measured memory_bytes: 13560
#include<bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
const int M = 1000000007;

long long cnt(long long n) {
    return n - n / 3 - n / 5 + n / 15;
}

long long len(long long n) {
    long long ret = (n / 3 + n / 5) * 4;
    long long l = 0, r = min(9LL, n), t = 1;
    while (l < n) {
        ret += (cnt(r) - cnt(l)) * t;
        ++t;
        l = r;
        r = min(r * 10 + 9, n);
    }
    return ret;
}

int main() {
    long long n;
    cin >> n;
    --n;
    long long ok = 0, ng = 1e18;
    while (ok + 1 < ng) {
        long long m = (ok + ng) / 2;
        if (len(m) <= n)
            ok = m;
        else
            ng = m;
    }
    string s = "";
    for (int i = 0; i < 20; ++i) {
        long long j = ok + 1 + i;
        if (!(j % 3)) s += "Fizz";
        if (!(j % 5)) s += "Buzz";
        if (j % 3 && j % 5) s += to_string(ok + 1 + i);
    }
    cout << s.substr(n - len(ok), 20) << "\n";
    return 0;
}



Measured memory_bytes: 3268
import math
temp=input().split()
N=int(temp[0])
L=int(temp[1])
T=int(temp[2])
XW=[[int(j) for j in input().split()] for i in range(N)]
count=0
for i in range(N):
	if XW[i][1]==1:
		XW[i][0]+=T
	else:
		XW[i][0]-=T
	count+=math.floor(XW[i][0]/L)
newX=[]
for i in range(N):
	newX.append(XW[i][0]%L)
newX.sort()
#print(newX)
for i in range(N):
	print(newX[(i+count)%N]%L)

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

// template {{{
#define  range(i, l, r) for (int i = (int)(l); i < (int)(r); (i) += 1)
#define rrange(i, l, r) for (int i = (int)(r) - 1; i >= (int)(l); (i) -= 1)

#define  whole(f, x, ...) ([&](decltype((x)) container) { return (f)(  begin(container),  end(container), ## __VA_ARGS__); })(x)
#define rwhole(f, x, ...) ([&](decltype((x)) container) { return (f)( rbegin(container), rend(container), ## __VA_ARGS__); })(x)

#define debug(x) cerr << "(" << __LINE__ << ")" << #x << ": " << (x) << endl

using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

// constexpr i32 mod   = 998244353;
constexpr i32 mod   = 1e9 + 7;
constexpr i32 inf   = 1001001001;
constexpr i64 infll = 1001001001001001001ll;

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

struct IoSetup { IoSetup(int x = 15){ cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(x); cerr << fixed << setprecision(x); } } iosetup;

template <typename T = i64> T input() { T x; cin >> x; return x; }

template <typename T> ostream &operator<<(ostream &os, vector<T> &v) { range(i, 0, v.size()) { 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 T1, typename T2> ostream &operator<<(ostream &os, 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> vector<T> make_vector(size_t a, T b) { return vector<T>(a, b); }
template <typename... Ts> auto make_vector(size_t a, Ts... ts) { return vector<decltype(make_vector(ts...))>(a, make_vector(ts...)); }

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
// }}}

void solver() {
    int n = input();
    vector< i64 > as(n);
    cin >> as;

    vector< i64 > cnt(100001, 0);
    for (auto a: as) cnt[a]++;

    i64 ans = whole(accumulate, as, 0ll);
    int q = input();
    while (q--) {
        i64 b = input(), c = input();
        ans -= b * cnt[b];
        ans += c * cnt[b];
        cnt[c] += cnt[b];
        cnt[b] = 0;

        cout << ans << endl;
    }
}

signed main(int argc, char *argv[]) {
    solver();
}


Measured memory_bytes: 4780
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(21);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;
int64 mod = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int64> a(n);
    vector<int64> csum(n);
    for (int i = 0; i<n; i++) {
        cin >> a[i];
    }

    int64 ans = 0;

    int64 res=0;
    for(int i=n-1; i>=0; i--) {
        csum[i] = res;
        res += a[i] % mod;
        res %= mod;
    }
    for (int i=0; i<n; i++) {
        ans += a[i] * csum[i] % mod;
    }
    ans %= mod;
    cout << ans << endl;
}

Measured memory_bytes: 5936
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var str = Console.ReadLine();
            var lss = new List<int>();
            for (int i = 0; i <= n; i++)
            {
                var ls = str.ToList();
                var ls1 = new List<char>();
                var ls2 = new List<char>();

                var dic1 = new Dictionary<char, int>();
                var dic2 = new Dictionary<char, int>();


                for (int j = 0; j < i; j++)
                {
                    ls1.Add(ls[j]);
                }
                for (int k = i; k < n; k++)
                {
                    ls2.Add(ls[k]);
                }
                foreach (var item in ls1)
                {
                    if (!dic1.ContainsKey(item))
                        dic1.Add(item, 1);
                    else
                        dic1[item]++;
                }
                foreach (var item in ls2)
                {
                    if (!dic2.ContainsKey(item))
                        dic2.Add(item, 1);
                    else
                        dic2[item]++;
                }


                var ansDic = new Dictionary<char, int>();
                foreach (var item in dic1)
                {
                    if (dic2.ContainsKey(item.Key))
                        ansDic.Add(item.Key, dic2[item.Key] + item.Value);

                }
                lss.Add(ansDic.Count);
            }
            Console.WriteLine(lss.OrderByDescending(x => x).FirstOrDefault());
            Console.ReadLine();
        }
    }
}



Measured memory_bytes: 13524
n = int(input())
*a, = map(int, input().split())

ans = a[:]

for i in range(n//2, 0, -1):
    cnt = 0
    for times in range(i, n+1, i):
        cnt += ans[times-1]
    if cnt%2 != a[i-1]:
        ans[i-1] = (ans[i-1]+1)%2

print(sum(ans))
for i in range(n):
    if ans[i] == 1:
        print(i+1, end=' ')

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

using namespace std;
using ll = long long;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()

#define READ(x) (cin >> (x))

#define WRITE_N(x) (cout << (x) << endl)
#define WRITE(x) (cout << (x))

int main() {
  // get values from input
  cin.tie(0);
  ios::sync_with_stdio(false);

  int A, B, C, K;
  cin >> A >> B >> C >> K;
  
  // main procedure
  int remain_K = K;
  int ans = 0;
  
  int taken_A = min(A, remain_K);
  remain_K -= taken_A;
  ans += taken_A;

  int taken_B = min(B, remain_K);
  remain_K -= taken_B;
  ans -= remain_K;

  // output
  WRITE_N(ans);

  return 0;
}


Measured memory_bytes: 3636
n = int(input())
l = list(map(int, input().split()))
freq = [0] * (2 * (10**5) + 5)
for i in l: freq[i] -= -1
count = 0
for i in range(2 * (10**5) + 5):
    if freq[i] >= 2:
        temp = (freq[i] * (freq[i] - 1)) // 2
        count += temp
for i in l:
    if freq[i] == 1: print(count)
    else:
        temp = freq[i] - 1
        if temp == 1: print(count - 1)
        else:
            yoyo = ((freq[i] * (freq[i] - 1)) // 2) - ((temp * (temp - 1)) // 2)
            print(count - yoyo)

Measured memory_bytes: 84688
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                sum+= gcd(i,gcd(j,k));
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int mpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = (long long) res * a % MOD;
		a = (long long) a * a % MOD;
		b >>= 1;
	}
	return res;
}

int main() {
	int n; cin >> n;
	cout << ((ll) mpow(10, n) + mpow(8, n) - 2 * mpow(9, n) + 2 * MOD) % MOD << endl;
	return 0;
}

Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int n, r, g, b, i, j, sol;
int main(){
    cin>> r >> g >> b >> n;
    for(i = 0; i * r <= n; i++){
        for(j = 0; i * r + j * g <= n; j++){
            if( (n - i * r - j * g) % b == 0 ){
                sol++;
            }
        }
    }
    cout<< sol;
}


Measured memory_bytes: 256
from collections import Counter

S = str(input())

memo = [0]
d = 0
mod = 2019


for s in S[::-1]:
    tmp = int(s) * pow(10, d, mod) % mod
    tmp = memo[-1] + tmp
    memo.append(tmp%mod)
    d += 1

c = Counter(memo)
ans = sum(v * (v-1)/2 for v in c.values())
print(int(ans))



Measured memory_bytes: 16820