akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main() {
    ld n,a;
    cin >> n;
    a=n;
    n++;
    n/=1.08;
    a/=1.08;
    if ((ll)n==(ll)a){
        cout << ":(" << endl;
        return 0;
    }
    cout << (ll)n << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int n;
ll k;
ll a[200001],f[200001];
bool func(ll d){
    ll cnt=0;
    rep(i,n){
        cnt+=max(0ll,a[i]-d/f[i]);
        if(cnt>k) return false;
    }
    return true;
}
int main(){
    cin>>n>>k;
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>f[i];
    sort(a,a+n);sort(f,f+n);reverse(f,f+n);
    
    ll lb=-1,ub=1e18;
    while(ub-lb>1){
        ll mid=(ub+lb)/2;
        if(func(mid)) ub=mid;
        else lb=mid;
    }
    cout<<ub<<endl;

    return 0;
}

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

int main(){

    int n,k;
    cin >> n >> k;
    int total = 0;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        if(k-a > a){
            total += 2 * a;
        }else{
            total += 2 * (k - a);
        }
    }

    cout << total << endl;

    return 0;
}

Measured memory_bytes: 256
f :: Double -> Double -> Double -> Double
--f a b x = (if x >= a * a * b / 2 then atan (2*a*b-2*x/a) else atan (a*b*b/(2*x)))*180/pi
f a b x = (if x >= a * a * b / 2 then atan ((2*b/a)-(2*x/(a*a*a))) else atan (a*b*b/(2*x)))*180/pi
main = do
    [a,b,x] <- getLine >>= return . (map (read :: String -> Double)) . words
    putStrLn $ show $ f a b x

Measured memory_bytes: 508
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main(){
    int n, k, x, y;
    cin >> n >> k >> x >> y;
    printf("%d\n", n>k ? x*k + y*(n-k) : x*n);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int r,c;
    cin>>r>>c;
    int a[r][c];
    int x[r]={0}, y[c]={0};
    int sum=0;
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cin>>a[i][j];
            x[i]+=a[i][j];
            sum+=a[i][j];
        }
    }
    for(int i=0; i<c; i++){
        for(int j=0; j<r; j++){
            y[i]+=a[j][i];
        }
    }
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            cout<<a[i][j]<<" ";
        }
        cout<<x[i]<<endl;
    }
    for(int i=0; i<c; i++)  cout<<y[i]<<" ";
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3124
#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

typedef long long ll;

double sum(ll i){
  return (double)((double)(i * (i + 1)) / 2.0);
}

int main(){
  ll K, N, tmp;
  vector<double> E;
  cin >> N >> K;
  for (int i=0; i<N; i++){
    cin >> tmp;
    E.push_back(sum(tmp) / (double)(tmp));
  }
  double ans = 0.0;
  for (ll i=0; i<K; i++){
    ans += E[i];
  }
  double tmp2 = ans;
  for (ll i=K; i<N; i++){
    tmp2 = tmp2 - E[i - K] + E[i];
    cerr << i << " " << tmp2 << endl;
    ans = max(ans, tmp2);
  }
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}

Measured memory_bytes: 2420
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
#define ALL(x)    (x).begin(),(x).end()
#define UNIQ(c)   (c).erase(unique(ALL((c))), end((c)))
#define mp        make_pair
#define eb        emplace_back
#define REP(i, a) for (int i = 0; i < (a); i++)

int main() {
	int n;
	cin >> n;
	int wa = 0;
	int a = n;
	while (a >= 10) {
		wa += a % 10;
		a /= 10;
	}
	wa += a;
	if (n%wa == 0)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i = 0;i < (n); ++i)
#define all(v) v.begin(),v.end()
#define sort_1(v) sort(v.begin(),v.end())
#define sort_2(v) sort(v.begin(),v.end(),greater<ll>())
typedef long long ll;
typedef long double la;
using namespace std;

int main(){
    ll x;
    cin >> x;
    ll money = 100;
    ll count = 0;
    while(1){
        ll n = money*0.01;
        money += n;
        count++;
        if(money >= x){
            cout << count << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3632
#include <iostream>
int main() {
    int n, m, a[100][100], b[100];
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
        }
    }
    for (int i = 0; i < m; ++i) {
        std::cin >> b[i];
    }
    for (int i = 0, c = 0; i < n; ++i, c = 0) {
        for (int j = 0; j < m; ++j) {
            c += a[i][j] * b[j];
        }
        std::cout << c << std::endl;
    }
}



Measured memory_bytes: 3128
use proconio::input;

fn main() {
    input! {
        k: i32,
        a: i32,
        b: i32,
    }
    let mut ok = false;
    for i in a..=b {
        if i % k == 0 {
            ok = true;
        }
    }
    if ok {
        println!("OK");
    } else {
        println!("NG");
    }
}


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



int main() {
    int n, l;
    cin >> n >> l;
    string s[n];
    for(int i=0; i<n; i++) cin >> s[i];

    for(int i=1; i<n; i++) {
        int j=i;
        while(j>0 && s[j-1]>s[j]) {
            string tmp = s[j-1];
            s[j-1] = s[j];
            s[j] = tmp;
            j--;
        }
    }

    for(int i=0; i<n; i++) cout << s[i];
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Iterator;
import java.lang.Math;

class Graph1 {
	private int totalVertex;
	//adjMatrix[u][v] = 1 if there is an edge from u to v, otherwise 0
	private int[][] adjMatrix;
	//adjWeight[u][v] -- the weight of the edge from u to v if there is one
	private int[][] adjWeight;
	//if a node is settled (e.g., processed in the Dijkstra's algorithm)
	private Boolean[] ifSettled;
	int[] distances;
	public Graph1() { 
		totalVertex = 0;
	}
	public int getTotalVertex() { return totalVertex; }
	//load graph from standard input
	public void loadAdjMatrix() {
		Scanner in = new Scanner(System.in);
		totalVertex = in.nextInt();
		adjMatrix = new int[totalVertex][totalVertex];
		adjWeight = new int[totalVertex][totalVertex];
		ifSettled = new Boolean[totalVertex];
		distances = new int[totalVertex];
		distances[0] = 0;
		for(int i = 1; i < totalVertex; i++) {
			distances[i] = Integer.MAX_VALUE;
		}
		int i, j;
		for(i = 0; i < totalVertex; i ++) {
			ifSettled[i] = false;
			for(j = 0; j < totalVertex; j ++) {
				adjMatrix[i][j] = adjWeight[i][j] = 0;
			}
		}
		int u, v;
		for(i = 0; i < totalVertex; i ++) {
			//u = in.nextInt();
			//int degree = in.nextInt();
			for(j = 0; j < totalVertex; j ++) {
				v = in.nextInt();
				if(v!= -1) {
					adjMatrix[i][j] = 1;
					adjWeight[i][j] = v;
				}
			}	
		}
		in.close();
	}
	//return weight of the edge from u to v if there is one
	public int getWeight(int u, int v) {
		return adjWeight[u][v];
	}
	//return neighbors of u as a LinkedList
	public LinkedList<Integer> getNeighbors(int u) {
		LinkedList<Integer> tmp = new LinkedList<Integer>();
		for(int v = 0; v < totalVertex; v ++) {
			if(adjMatrix[u][v] == 1) tmp.add(v);
		}
		return tmp;
	}
	//return unsettled neighbors of u as a LinkedList
	public LinkedList<Integer> getUnsettledNeighbors(int u) {
		LinkedList<Integer> tmp = new LinkedList<Integer>();
		for(int v = 0; v < totalVertex; v ++) {
			if((adjMatrix[u][v] == 1) && (ifSettled[v] == false)) tmp.add(v);
		}
		return tmp;
	}
	//return the unsettled node that has the smallest dist
	public int getUnsettledNearest(int[] dist) {
		int md = Integer.MAX_VALUE;
		int mv = -1;
		int v;
		for(v = 0; v < totalVertex; v ++) {
			if((ifSettled[v] == false) && (dist[v] < md)) {
				md = dist[v];
				mv = v;
			}
		}
		return mv;
	}
	//implement the following	
	public int[] Dijkstra(int s) {
		LinkedList<Integer> unsettled = new LinkedList<Integer>();
		for(int i = 0; i < totalVertex; i++) {
			unsettled.add(i);
		}
		
		while(!unsettled.isEmpty()){
			int node = this.getUnsettledNearest(distances);
			for(Integer x : this.getUnsettledNeighbors(node)) {
				
				distances[x] = Integer.min(this.getWeight(node, x), distances[x]);
			}
			ifSettled[node] = true;
			unsettled.remove((Integer)node);
		}
		return distances;
	}
}

public class Main {
	public static void main(String[] argv) {
		Graph1 g = new Graph1();
		g.loadAdjMatrix();
		int[] dist = g.Dijkstra(0);
		int total = 0;
		for(int i = 0; i < g.getTotalVertex(); i ++) {
			total += dist[i];
		}
		System.out.println(total);
	}
}


Measured memory_bytes: 41580
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
typedef long long ll;
typedef vector<vector<ll>> vvl;
typedef vector<ll> vl;
typedef vector<vector<char>> vvc;
typedef vector<char> vc;
typedef pair<ll,ll> pll;
typedef priority_queue<string> priquest;
typedef priority_queue<string,vector<string>,greater<string>> rpriquest;
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
  return x+y-max(x,y);
}

const ll big=1000000007;
ll exp(ll x,ll y){
    if(y==0)return 1;
    if(x==1||x==0)return x;
    if(y%2==1)return (exp(x,y-1)*x);
    ll t=exp(x,y/2);
    return (t*t);
}
void chmin(ll a,ll b){
    if(a>b)a=b;
    return;
}

struct unionfind{
  vector<int> par;
  vector<ll> size;
  vector<int> rank;
  void begin(int n){
    par.resize(n,-1);
    size.resize(n,1);
    rank.resize(n,1);
  }
  int find(int x){
    if(par[x]==-1)return x;
    return par[x]=find(par[x]);
  }
  void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    if(rank[x]<rank[y])swap(x,y);//rank[x]>=rank[y]に
      par[y]=x;
      size[x]+=size[y];
    if(rank[x]==rank[y])rank[x]++;
    return;
  }
};


int main(){
  int n,k,l;cin >> n >> k >> l;
  unionfind road,train;
  road.begin(n);train.begin(n);
  rep(i,k){
    int p,q;cin >> p >> q ;p--;q--;
    road.unite(p,q);
  }
  rep(i,l){
    int r,s;cin >> r >> s;r--;s--;
    train.unite(r,s);
  }
  map<pair<int,int>,ll> ans;
  rep(i,n){
    pair<int,int> root=make_pair(road.find(i),train.find(i));
    ans[root]++;
  }
  rep(i,n){
    pair<int,int> root=make_pair(road.find(i),train.find(i));
    cout << ans[root];
    cout << (i==n-1 ? '\n' : ' ');
  }
}

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

double N;

int main() {
    cin >> N;

    double tmp = N / 1.08;

    if (floor(ceil(tmp) * 1.08) == N) cout << (int)(ceil(tmp)) << endl;
    else if (floor(floor(tmp) * 1.08) == N) cout << (int)(floor(tmp)) << endl;
    else cout << ":(" << endl;

    return 0;
}


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

using namespace std;

using int64 = long long;

string beet(string a, string b, int x)
{
  string ret = "~";
  for(int i = x; i > 0; i--) { // x 個使う
    int64 rest = x - 1LL * i * (int) a.size();
    if(rest < 0) continue;
    if(rest % b.size() == 0) {
      ret = "";
      for(int j = 0; j < i; j++) ret += a;
      for(int j = 0; j < rest / b.size(); j++) ret += b;
      break;
    }
  }
  return (ret);
}

int main()
{
  int L;
  string S, T;

  cin >> L;
  cin >> S;
  cin >> T;
  cout << min(beet(S, T, L), beet(T, S, L)) << endl;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#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 fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
typedef pair<pll, pll> P;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//

int N, K;
int x[112345];

ll solve() {
	ll res = 1ll<<60;
	
	int bou = N; // x[i]>0となる最小のi
	REP(i, N) if (x[i] > 0) { bou = i; break; }
	
	REP(i, N - K + 1) {
		if (i >= bou) break;
		
		if (bou - i >= K) chmin(res, -x[i]);
		int lea = K - (bou - i);
		
		if (lea >= 0 && bou + lea - 1 < N) chmin(res, -x[i] * 2 + x[bou + lea - 1]);
		
		if (debug) printf("bou: %d, i: %d, lea: %d\n", bou, i, lea);
	}
	
	return res;
	
}

int main() {
	cin >> N >> K;
	REP(i, N) scanf("%d", x + i);
	
	ll ans = solve();
	
	reverse(x, x + N);
	REP(i, N) x[i] = -x[i];
	
	chmin(ans, solve());
	
	cout << ans << endl;
	
	return 0;
}

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

public class Main {
	static long mod = (long)1e9+7;
	public static void main(String[] args) {
		FastScanner sc=new FastScanner();
		int n = sc.nextInt();
		int count = 0;
		boolean flag = false;
		for(int i =0; i<n; i++) {
			int s = sc.nextInt();
			int t = sc.nextInt();
			if(s==t)
				count++;
			else {
				count=0;
			}
			if(count ==3)
				flag = true;
			
		}
		
		System.out.println(flag ? "Yes" : "No");
	}
	
	static final Random random = new Random();
	
	static void sort(int[] a) {
		int n = a.length;
		for(int i =0; i<n; i++) {
			int val = random.nextInt(n);
			int cur = a[i];
			a[i] = a[val];
			a[val] = cur;
		}
		Arrays.sort(a);
	}
	
	static void sortl(long[] a) {
		int n = a.length;
		for(int i =0; i<n; i++) {
			int val = random.nextInt(n);
			long cur = a[i];
			a[i] = a[val];
			a[val] = cur;
		}
		Arrays.sort(a);
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (st == null  || !st.hasMoreTokens()) {
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		String nextLine() { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
		} 
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() { 
            return Double.parseDouble(next()); 
        } 
	}

}


Measured memory_bytes: 32848
#include<cstdio>
const int MAX = 1e5;

long K;
long num[MAX + 1] = {0};

int main() {
	int a, b, N;
	scanf("%d %ld\n", &N, &K);

	for (int i = 0; i < N; i++) {
		scanf("%d %d", &a, &b);
		num[a] += b;
	}

	for (int i = 1; i <= MAX; i++) {
		if (K <= num[i]) {
			printf("%d\n", i);
			return 0;
		}
		K -= num[i];
	}
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
#define ll long long
 ll factorial[1000009];
// we need to define a pow function to raise a to m-2
// function below calculates (a^b)%mod
ll power(ll a, ll b, ll mod){
	ll x = 1, y = a;
	while (b > 0){
		if (b%2){
			x = (x*y)%mod;
		}
		y = (y*y)%mod;
		b /= 2;
	}
	return x%mod;
}	
 
ll modular_inverse(ll n, ll mod){
	return power(n, mod-2, mod);
}
 
ll nCr(ll n, ll k, ll mod){
	return (factorial[n]*((modular_inverse(factorial[k],mod)*modular_inverse(factorial[n-k],mod))%mod))%mod;
}
    int main(){
    	factorial[0] = 1;
    	ll x,y,i,j,k,t,o,INF,s;
    	INF=1e9+7;
    	t=0;o=0;
    	for(i = 1 ; i <= 1000004 ; i++)
    		factorial[i] = (factorial[i-1]*i)%INF;
    cin>>s;
    x=s/3;
    y=0;
    for (i=1;i<=x;i++)
    {
    	y=(y+nCr(s-1-2*i,i-1,INF))%INF;
	}
	cout<<y<<endl;
}

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

int main()
{
	int A;
	long long B, N;
	scanf("%d%lld%lld", &A, &B, &N);
	
	if(B - 1 <= N)
		printf("%lld", A * (B - 1) / B);
		
	else
		printf("%lld", A * N / B);
}


Measured memory_bytes: 3832
n = gets.to_i
a  = gets.split.map(&:to_i).unshift(0)

(1..n).each do |i|
    n_str = "node #{i}: key = #{a[i]}, "
    p_str = if i == 1 then "" else "parent key = #{a[i / 2]}, " end
    l_str = if a[i * 2] then "left key = #{a[i * 2]}, " else "" end
    r_str = if a[i * 2 + 1] then "right key = #{a[i * 2 + 1]}, " else "" end
    puts n_str + p_str + l_str + r_str
end



Measured memory_bytes: 6876
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define uniq(x) (x).erase(unique(all(x)),(x).end())

int ns[3];

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

void solve(void){
    int N;
    cin >> N;
    rep(N, i) scanf("%d", &ns[i]);
    int X = gcd(gcd(ns[0], ns[1]), ns[2]);
    Rep(1, X, x) if (X % x == 0) printf("%d\n", x);
}

int main(void){
  solve();
  return 0;
}



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

using namespace std;
using ll = long long;

//container util
#define SORT(c) sort((c).begin(),(c).end())
#define all(a) (a).begin(), (a).end()

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//print
#define pv(val) cerr << #val << '=' << (val) << endl

const int INF = 1e9;

int main(void){

	int N; cin >> N;
	map<ll, ll> mp;
	ll sum = 0;
	REP(i,N){
		ll A; cin >> A;
		mp[A]++;
		sum += A;
	}

	int Q; cin >> Q;
	REP(i,Q){
		ll B, C; cin >> B >> C;
		ll cnt = mp[B];
		sum -= cnt * B;
		sum += cnt * C;
		mp[B] = 0;
		mp[C] += cnt;
		cout << sum << endl;
	}


	return 0;

}


Measured memory_bytes: 9448
#include <iostream>

int main() {
	int N, counter;

	std::cin >> N;
	for (int i = 0; i < N; i++) {
		int temp;
		std::cin >> temp;

		if (temp % 2 == 1) {
			counter++;
		}
	}

	if (counter % 2 == 1) {
		std::cout << "NO" << std::endl;
	} else {
		std::cout << "YES" << std::endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int ans=-1;
ll n;
vector <ll> a;

void mk28(ll div){
  if(n<div)return;
  if(div)a.push_back(div);
  mk28(div*10+2);
  mk28(div*10+8);
}


void saiki(ll num,int idx,int sum){
  if(num==1) ans=max(sum,ans);
  if(num<a[idx]||idx==a.size())return;
  if(num%a[idx]==0)saiki(num/a[idx],idx,sum+1);
  saiki(num,idx+1,sum);
}

int main(){
  cin>>n;
  mk28(0);
  sort(a.begin(),a.end());
  if(n>1)saiki(n,0,0);
  cout <<ans<<endl;
  return 0;
}

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

int main() {
  int h, a;
  cin >> h >> a;

  int ans = 0;
  while (h > 0){
    ans++;
    h -= a;
  }
  
  cout << ans << endl;
  return 0;
}

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

using namespace std;

int main()
{
	string s, p;

	cin >> s >> p;
	string n = s;
	n += s;

	if (n.find(p) != string::npos)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;
}



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

using lnt = long long;
using Real = long double;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(lnt i=0;i<(n);++i)
#define RANGE(i, a, b) for(lnt i=(a);i<(b);++i)
#define RREP(i, n) for(lnt i=(n)-1;i>= 0;--i)

#define ln '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define dcout cout<<fixed<<setprecision(20)
#define summon_tourist cin.tie(0);ios::sync_with_stdio(false)

constexpr int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
constexpr Real eps = 1e-9; const Real pi = acosl(-1);
constexpr lnt BIG = INT_MAX/10, BBIG = LLONG_MAX/10;

template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<class T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<class T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

using pint = pair<int, int>; using plnt = pair<lnt, lnt>;
using vint = vector<int>; using vlnt = vector<lnt>;
constexpr lnt MOD = 1e9+7;

int main(){
	summon_tourist;

	string S; cin >> S;
	int sum = 0;
	for(auto c : S){
		int d = (int)(c - '0');
		sum += d;
	}
	if(sum % 9 == 0) cout << "Yes" << ln;
	else cout << "No" << ln;
}

Measured memory_bytes: 3740
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair

int read()
{
    int v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}

char ch[501000];
int a[501000];
int n;

int main()
{
    scanf("%s", ch);
    n = strlen(ch);
    reverse(ch, ch + n);
    for (int i = 0; i < n; i++) a[i] = ch[i] - 48;
    for (int i = 0; i < n; i++)
        a[i] *= 9;
    for (int i = 0; i < n; i++)
    {
        a[i + 1] += a[i] / 10;
        a[i] %= 10;
    }
    while (a[n]) n++;
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += a[i];
    for (int i = 0; i < 10000000; i++)
    {
        if (sum <= 9 * i && sum % 9 == 0)
        {
            printf("%d\n", i);
            break;
        }
        for (int i = 0; i < n; i++)
        {
            if (i == 0) a[i] += 9, sum += 9;
            if (a[i] >= 10)
            {
                a[i + 1]++;
                a[i] -= 10;
                sum -= 9;
            } else break;
        }
        while (a[n]) n++;
    }
}


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

int main(void) {
  int count = 0, val[55], i, j, N, tmp;
  char res[10] = "YES";
  scanf("%d", &N);
  for (i = 0; i < N; i++) {
    scanf("%d", &val[i]);
  }
  for (i = 0; i < N - 1; i++) {
    if (val[i] != i + 1) {
      count++;
    }
  }
  if (count > 2) strcpy(res, "NO");
  printf("%s", res);
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;

template<class V,int ME> class BIT{
public:
	V bit[1<<ME];
	V operator()(int e){V s=0;e++;while(e)s+=bit[e-1],e-=e&-e;return s;}
	V add(int e,V v){e++; while(e<=(1<<ME))bit[e-1]+=v,e+=e&(-e);}
};
BIT<ll,20> bt;

int main(){
	int n,m; cin >> n >> m;
	vector<int> E[101010];
	for(int i=0;i<n;i++){
		int x,y; cin >> x >> y;
		E[y-x+1].push_back(x);
	}
	int mi=n;
	for(int i=1;i<=m;i++){
		int ret=0;
		for(int j=i;j<=m;j+=i){
			ret+=bt(j);
		}
		for(auto e:E[i]){
			bt.add(e,1);
			bt.add(e+i,-1);
		}
		cout << mi+ret << endl;
		mi-=E[i].size();
	}
}

Measured memory_bytes: 11264
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

const ll INF = 1ll << 60;

struct interval_t {
  int to;
  ll w;
};

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N, M;
  while (cin >> N >> M) {
    vec<interval_t, 2> intervals(N);
    for (int i = 0; i < M; i++) {
      int l, r, c;
      cin >> l >> r >> c;
      --l;
      --r;
      intervals[l].push_back({ r + 1, c });
    }
    vec<ll, 2> ed(N + 1);
    multiset<ll> minS;
    vector<ll> dp(N, INF);
    dp[0] = 0;
    for (int i = 0; i < N; i++) {
      for (ll x : ed[i]) {
        auto it = minS.find(x);
        minS.erase(it);
      }
      if (!minS.empty()) {
        dp[i] = *minS.begin();
      }
      for (auto& interval : intervals[i]) {
        ll cost = dp[i] + interval.w;
        ed[interval.to].push_back(cost);
        minS.insert(cost);
      }
    }
    ll res = dp[N - 1];
    cout << (res >= INF ? -1 : res) << endl;
  }
  return 0;
}


Measured memory_bytes: 11904
// With item k, there are two options - either:
//
// It is included in the knapsack.
// It is not included in the knapsack.
//
// Let S(n, w) be the optimal value of a knapsack of weight w using the
// first n items.  Then:
//
// S(n, w) = max(S(n-1, w), S(n-1, w-w_n) + v_n) (if w >= w_n)
// S(n, w) = S(n-1, w) (if w < w_n)
// S(0, w) = 0
// S(n, 0) = 0

#include <stdio.h>
#include <stdlib.h>

long max(long a, long b)
{
    return a > b ? a : b;
}

long solution(int N, int W, int *w, int *v)
{
    long **S;
    int i, j;
    
    S = (long **)malloc(sizeof(long *)*N);
    for (i=0; i<=N; i++)
    {
        S[i] = (long *)malloc(sizeof(long)*W);
    }
    
    for (j=0; j<=W; j++)
    {
        S[0][j] = 0L;
    }
    
    for (i=1; i<=N; i++)
    {
        int w_i, v_i;
        
        w_i = w[i-1];
        v_i = v[i-1];
        
        for (j=0; j<=W; j++)
        {
            if (j < w_i)
            {
                S[i][j] = S[i-1][j];
            }
            else
            {
                S[i][j] = max(S[i-1][j], S[i-1][j-w_i] + v_i);
            }
        }
    }
    
    return S[N][W];
}

int main(int argc, char **argv)
{
	int N, W;
	int *w;
	int *v;
	int i;
	
	scanf("%d", &N);
	scanf("%d", &W);
	
	w = (int *)malloc(sizeof(int)*N);
	v = (int *)malloc(sizeof(int)*N);
	
	for (i=0; i<N; i++)
	{
	    scanf("%d", w+i);
	    scanf("%d", v+i);
	}
	
	printf("%ld", solution(N, W, w, v));
	return 0;
}

Measured memory_bytes: 79360
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-11;

int main() {
    ll N;
    cin >> N;
    int a[N], b[N];
    a[0] = -1;
    fill(b, b + N, 0);
    for (int i = 1; i < N; i++) {
        cin >> a[i];
        a[i]--;
        b[a[i]]++;
    }
    // for (int i = 0; i < N; i++) {
    //     cout << b[i] << " ";
    // }
    // cout << endl;
    tiii c[N]; //高さ、番号、空き枠
    priority_queue<pii, vector<pii>, greater<pii> > que;
    for (int i = 0; i < N; i++) {
        c[i] = tiii(b[i], i, b[i]);
        if (b[i] == 0) {
            que.push(pii(b[i], i));
        }
    }
    while (!que.empty()) {
        pii p = que.top();
        que.pop();
        if (p.second == 0) {
            break;
        }
        int to = a[p.second];
        tiii tot = c[to];
        // cout << p.first << " " << p.second << endl;
        // cout << get<0>(c[to]) << " " << get<1>(tot) << " " << get<2>(tot) << endl;
        if (get<2>(tot) + p.first > get<0>(tot)) {
            get<0>(c[to]) = get<2>(c[to]) + p.first;
        }
        get<2>(c[to])--;
        if (get<2>(c[to]) == 0) {
            que.push(pii(get<0>(c[to]), get<1>(c[to])));
        }
    }
    ll ans = get<0>(c[0]);
    cout << ans << endl;
}


Measured memory_bytes: 3320
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true) {
			String[] strArray = br.readLine().split(" ");
			int H = Integer.parseInt(strArray[0]);
			int W = Integer.parseInt(strArray[1]);

			if (H ==0 && W == 0) {
				break;
			}
			for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					System.out.print("#");
				}
				System.out.println("");
			}
			System.out.println("");
		}
	}
}

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

int main(){
  int n,x,array[100001],kyori[100001],tmp,r;
  cin>>n>>x;
  for(int i=0;i<n;i++){
    cin>>array[i];
  }
  for(int i=0;i<n;i++){
    kyori[i]=abs(array[i]-x);
  }
  sort(kyori,kyori+n);
  for(int i=kyori[0];;i--){
    for(int j=0;j<n;j++){
      if(kyori[j]%i){
        break;
      }
      if(j==n-1){
        cout<<i<<endl;
        return 0;
      }
    }
  }
}
    

Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <vector>

using namespace std;

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

#define PB push_back
#define MP make_pair

#define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
#define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
#define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)
#define R1(a) do{scanf("%d", &(a));}while(0)
#define R2(a, b) do{scanf("%d%d", &(a), &(b));}while(0)
#define R3(a, b, c) do{scanf("%d%d%d", &(a), &(b), &(c));}while(0)
#define SV(vec) do{int s_v_;scanf("%d", &(s_v_));vec.PB(s_v_);}while(0)
#define MM(co, cim) memset((co), (cim), sizeof((co)))
#define DEB(x) cerr << ">>> " << #x << " : " << x << endl;
#define INF 1000000007

int n, a[100014];
ll dp[100014][2];

ll go (int x, int st)
{
  if (dp[x][st] != -1) return dp[x][st];
  int val = a[x] * (st ? -1 : 1);
  if (x >= n - 1) return val;
  ll res = max(-1 * val + go(x + 1, 1), val + go(x + 1, 0));
  return dp[x][st] = res;
}

int main ()
{
  R1(n);
  FOR(i, 0, n) R1(a[i]);
  MM(dp, -1);
  printf("%lld\n", go(0, 0));
  return 0;
}


Measured memory_bytes: 6912
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,l;
  cin>>n>>l;
  int mini=30000;
  int minus;
  int sum=0;
  for(int i=1;i<=n;i++){
    sum+=l+i-1;
    if(abs(l+i-1)<mini){mini=abs(l+i-1);minus=l+i-1;}
  }
  cout<<sum-minus;
}


Measured memory_bytes: 256
#ifdef __LOCAL
  #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b) {if(a<b) {a=b; return true;} return false;}
template<typename T> bool chmin(T &a,T b) {if(a>b) {a=b; return true;} return false;}
#define itn int
#define fi first
#define se second
#define intmax numeric_limits<int>::max()
#define llmax numeric_limits<ll>::max()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>=1;i--)
#define all(vec) vec.begin(),vec.end()
#define sortt(vec) sort((vec).begin(),(vec).end())
#define rsort(vec) sort((vec).rbegin(), (vec).rend())
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;
const ll lnf=1ll<<60;

int main(){
  int n; cin >> n;
  vector<int> a(n);
  vector<int> b(n);
  bool same=1;
  ll sum=0;
  rep(i,n){
    cin >> a[i] >> b[i];
    sum+=a[i];
    if(a[i]!=b[i]) same=0;
  }
  if(same){
    cout << 0 << endl;
    return 0;
  }
  int mn=intmax;
  rep(i,n){
    if(a[i]>b[i]) chmin(mn,b[i]);
  }
  cout << sum-mn << endl;
}

Measured memory_bytes: 3764
#include"bits/stdc++.h"
using namespace std;
#define LL long long

int N, M, K, ans, r, t,a[10];

string s, f;
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a[i];
	}
	int num = N-1;
	bool b;
	b = true;
	while (b) {
		num++;
		s = to_string(num);
		for (int k = 0; k < s.size(); k++) {
			for (int i = 0; i < M; i++) {
				if (s[k]-'0' ==a[i]) {
					k = s.size();
					break;
				}
			}
			if (k == s.size() - 1)b = false;
		}
	}
	cout << num<< endl;
	return 0;

}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int m_p=0,f_p=0,r_p=0,sum=0;
	while(true){
		scanf("%d %d %d" ,&m_p ,&f_p ,&r_p);
		sum=m_p+f_p;
		if(m_p==-1 && f_p==-1 && r_p==-1) break;
		if(m_p==-1 || f_p==-1) {
			printf("F\n");
		} else{
			if(sum>=80) printf("A\n");
			if(sum<80  && sum>=65) printf("B\n");
			if(sum<65 && sum>=50) printf("C\n");
			if(sum>=30 && sum<50){
				if(r_p==-1 || r_p<50){
					printf("D\n");
				}else{
					printf("C\n");
				}
			}
			if(sum<30 ) printf("F\n");

		}
	}
	return 0;
}



Measured memory_bytes: 2576
/*
 * atcoder/abc117/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

/*
 * i) N >= M : 0 移動不要
 * ii) N = M - 1 : 前の座標との距離が最小の位置にコマを配置しない。その距離が答え
 * iii) N = M - 2 : 前の座標との距離が最小の位置２つにコマを配置しない。その距離の合計が答え
 * N) 以下同じ
 */

int N, M;
vector<int> X;
vector<int> D;

void solve() {
  cin >> N >> M;
  int x;
  loop(m,0,M) {
    cin >> x;
    X.push_back(x);
  }
  sort(X.begin(), X.end());
  for (int i=0; i+1<X.size(); i++) {
    D.push_back(X[i+1] - X[i]);
  }
  sort(D.begin(), D.end());
  ll total = 0;
  for (int i=0; i<max(M-N, 0); i++) {
    total += D[i];
  }
  cout << total << endl;
}
int main() {
  // cout.precision(15);
  // cout << fixed << double

  solve();

  return 0;
}


Measured memory_bytes: 1400
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
//import std.regex;
import std.container;

void main()
{
	foreach (line; stdin.byLine) {
    int cnt[10];
    foreach (e; line.chomp) {
      cnt[e-'0']++;
    }
    int[int] res;
    foreach (i; 1..10) {
      auto tcnt = cnt.dup;
      tcnt[i]++;
      bool f1;
      foreach (j; 1..10) {
        if (tcnt[j] > 4) f1 = 1;
      }
      if (f1) continue;
      foreach (j; 1..10) {
        if (tcnt[j] < 2) continue;
        auto ttcnt = tcnt.dup;
        ttcnt[j] -= 2;
        bool f2;
        foreach (k; 1..10) {
          if (ttcnt[k] >= 3) {
            ttcnt[k] -= 3;
          }
          if (ttcnt[k] && k <= 7) {
            if (ttcnt[k] <= ttcnt[k+1] && ttcnt[k] <= ttcnt[k+2]) {
              ttcnt[k+1] -= ttcnt[k];
              ttcnt[k+2] -= ttcnt[k];
              ttcnt[k] = 0;
            }
          }
          if (ttcnt[k]) {
            f2 = 1;
            break;
          }
        }
        if (f2) continue;
        res[i]++;
        break;
      }
    }
    if (!res.keys.length) res[0]++;
    res.keys.sort.map!(to!string).join(" ").writeln;
  }
}

Measured memory_bytes: 1084
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr first
#define sc second
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int N=3e5+10;
int main()
{
    FASTINOUT;
    int x;
    cin>>x;
    string s,t;
    cin>>s>>t;
    int i=0;
    ll ans=1;
    bool b=false;
    if (s[0]==t[0]){
        ans=3;
        i=1;
    }
    else{
        ans=6;
        i=2;
        b=true;
    }
    while (i<x){
        if (s[i]==t[i]){
            if (!b){
                ans*=2;
                ans%=mod;
            }
            b=false;
            i++;
        }
        else{
            if (b)
            {
                ans*=3;
                ans%=mod;
            }
            else{
                ans*=2;
                ans%=mod;
            }
            i+=2;
            b=true;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
use proconio::{fastout, input};
use std::vec::Vec;
use std::cmp::*;

#[fastout]
fn main() {
    input! {
        n: usize,
        m: usize, 
        mut x: [i32; m],
    }

    x.sort();

    let mut section = Vec::<i32>::with_capacity(n-1);
    for i in 0..x.len()-1 {
        section.push(x[i+1] - x[i]);
    }
    section.sort_by_key(|&x| Reverse(x));

    let mut ans = *x.iter().last().unwrap() - *x.iter().next().unwrap();
    for i in 0..min(section.len(), n-1) {
        ans -= section[i];
    }

    println!("{}", ans);
}


Measured memory_bytes: 3592
import numpy as np
n,d=map(int,input().split())
x=[]
for i in range(n):
    x.append(list(map(int,input().split())))
count=0
#print(x)
y=np.array(x)
#print(y)
for i in range(n):
    for j in range(n):
        if i<j:
            s=sum((y[i]-y[j])**2)
            #print(s)
            if np.round(np.sqrt(s))**2==s:
                #print(s)
                count+=1
print(count)

Measured memory_bytes: 12420
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define MAXN maxn

using namespace std;

string s;
char res = -1;

signed main()
{
  IO;
  cin >> s;
  sort(s.begin(), s.end());
  s.erase(unique(s.begin(), s.end()), s.end());
  for (int i = 0; i < (int)s.size(); i++) {
    if (s[i] != 'a' + i) {
      res = 'a' + i;
      break;
    }
  }
  if (res == -1) {
    if (s.back() != 'z') {
      cout << (char)(s.back() + 1) << endl;
    }
    else {
      cout << "None" << endl;
    }
  }
  else {
    cout << res << endl;
  }
  return 0;
}



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

int main()
{
  int i, j, k, b, d, n, m;
  char buf[16] = {0};
  buf[15] = '\0';
  buf[14] = '\n';
  char *p;
  char *line = NULL;
  size_t linecap = 0;
  fgets(buf, 15, stdin);
  n = atoi(buf);
  int *a = (int*)malloc(sizeof(int)*n);
  getline(&line, &linecap, stdin);
  a[0] = 0;  
  i=0;
  for (p=line; *p!='\n'; p++) {
    if (*p == ' ') {
      a[++i] = *(++p)-'0';
    } else {
      a[i] = a[i] * 10 + *p - '0';
    }
  }
  fgets(buf, 15, stdin);
  m = atoi(buf)-1;
  getline(&line, &linecap, stdin);
  p=line;
  i = j = 0;
  for (b = 0; *p>='0'; b = b * 10 + *(p++) - '0');
  p++;

  while (i<n) {
    if (a[i]<b) {
      d = a[i++];
      if (d==0) {
	fputs("0\n", stdout);
      } else {
	for (k=13; d>0; k--, d/=10)   buf[k] = '0' + (d%10);
	fputs(buf+k+1, stdout);
      }
    } else if (a[i]>b) {
      if (j<m) {
	d = b;
	if (d==0) {
	  fputs("0\n", stdout);
	} else {
	  for (k=13; d>0; k--, d/=10)   buf[k] = '0' + (d%10);
	  fputs(buf+k+1, stdout);
	}
	for (b = 0; *p>='0'; b = b * 10 + *(p++) - '0');
	p++;
	j++;
      } else break;
    } else { // a[i]==b
      i++;
      if (j<m) {
	for (b = 0; *p>='0'; b = b * 10 + *(p++) - '0');
	p++;
	j++;
      } else break;
    }
    break;
  }

  while (i<n) {
    if (a[i]<b) {
      d = a[i++];
      for (k=13; d>0; k--, d/=10)   buf[k] = '0' + (d%10);
      fputs(buf+k+1, stdout);
    } else if (a[i]>b) {
      if (j<m) {
	d = b;
	for (k=13; d>0; k--, d/=10)   buf[k] = '0' + (d%10);
	fputs(buf+k+1, stdout);
	for (b = 0; *p>='0'; b = b * 10 + *(p++) - '0');
	p++;
	j++;
      } else break;
    } else { // a[i]==b
      i++;
      if (j<m) {
	for (b = 0; *p>='0'; b = b * 10 + *(p++) - '0');
	p++;
	j++;
      } else break;
    }
  }

  for (; j<=m; j++) {
    if (a[i-1]!=b) {
      d = b;
      for (k=13; d>0; k--, d/=10)   buf[k] = '0' + (d%10);
      fputs(buf+k+1, stdout);
    }
    for (b = 0; *p>='0'; b = b * 10 + *(p++) - '0');
    p++;
  }
  for (; i<n; i++) {
    if (a[i]!=b) {
      d = a[i];
      for (k=13; d>0; k--, d/=10)   buf[k] = '0' + (d%10);
      fputs(buf+k+1, stdout);
    }
  }
  return 0;
}



Measured memory_bytes: 4440
#include <bits/stdc++.h>
const int MAXN = 300005;
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;

int n;
lint a[MAXN], s[MAXN], d1[MAXN], d2[MAXN];
lint rep[MAXN];

struct cht{
	vector<pi> v;
	void clear(){ v.clear(); }
	bool bad(pi x, pi y, pi z){
		return (x.second - y.second) * (z.first - y.first) >= (y.second - z.second) * (y.first - x.first);
	}
	void add(int x, lint y){
		while(v.size() >= 2 && bad(v[v.size()-2], v.back(), pi(x, y))) v.pop_back();
		v.emplace_back(x, y);
	}
	lint query(int x){
		int s = 0, e = v.size() - 1;
		while(s != e){
			int m = (s+e)/2;
			if(v[m].first * x + v[m].second < v[m+1].first * x + v[m+1].second) s = m + 1;
			else e = m;
		}
		return v[s].first * x + v[s].second;
	}
}cht;

void solve(int l, int r){
	if(r - l <= 1) return;
	int m = (l + r) / 2;
	solve(l, m); 
	solve(m + 1, r);
	lint cur = -1e18;
	for(int j=m+1; j<=r; j++){
		cht.add(2 * j - 1, d2[j] - s[j-1] + 1ll * j * (j - 1));
	}
	for(int i=l; i<m; i++){
		cur = max(cur, d1[i] + s[i] + 1ll * i * i + cht.query(-i));
		rep[i+1] = max(rep[i+1], cur);
	}
	cht.clear();
	for(int i=l; i<=m; i++){
		cht.add(2 * i + 1, d1[i] + s[i] + 1ll * i * (i + 1));
	}
	cur = -1e18;
	for(int j=r; j>m+1; j--){
		cur = max(cur, d2[j] - s[j-1] + 1ll * j * j + cht.query(-j));
		rep[j-1] = max(rep[j-1], cur);
	}
	cht.clear();
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%lld",&a[i]);
		s[i] = s[i-1] + 2 * a[i];
	}
	for(int i=1; i<=n; i++){
		int j = i - 1;
		cht.add(2 * j - 1, d1[j] + s[j] + 1ll * j * (j - 1));
		d1[i] = max(d1[i-1], cht.query(-i) + 1ll * i * i - s[i]);
	}
	cht.clear();
	for(int i=n; i; i--){
		int j = i + 1;
		cht.add(-2 * j - 1, d2[j] + 1ll * j * (j + 1) - s[j-1]);
		d2[i] = max(d2[i+1], cht.query(i) + 1ll * i * i + s[i-1]);
	}
	cht.clear();
	fill(rep, rep + n + 1, -1e18);
	solve(0, n + 1);
	int q; scanf("%d",&q);
	while(q--){
		int x, v; scanf("%d %d",&x,&v);
		lint dap = max(rep[x] - 2 * (v - a[x]) , d1[x-1] + d2[x+1]);
		printf("%lld\n", dap / 2);
	}
}


Measured memory_bytes: 14336
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
ll A[MAX_N];
ll ans[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	ll sum = accumulate(A, A + N, 0ll);
	for(int i = 1; i < N; i += 2) {
		sum -= 2 * A[i];
	}
	sum /= 2;
	ans[0] = sum;
	for(int i = 1; i < N; i++) {
		ans[i] = A[i - 1] - ans[i - 1];
	}
	rep(i, 0, N) {
		cout << ans[i] * 2 << " ";
	}
	cout << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 6272
#include <bits/stdc++.h>
using namespace std;
int p[200005], cnt;
bool vis[200005];
int n;
int main () {
	for(int i = 2; i <= 200000; ++i) {
		if(!vis[i]) p[++cnt] = i;
		for(int j = 1; j <= cnt && i*p[j] <= 200000; ++j) {
			vis[i*p[j]] = 1;
			if(i % p[j] == 0) break;
		}
	}
	scanf("%d", &n);
	printf("%d\n", p[lower_bound(p+1,p+cnt+1,n)-p]);
}

Measured memory_bytes: 512