akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    
    cin >> n;
    
    cout << n * n * n << endl;
    
    return 0;
}

Measured memory_bytes: 256
n, x, y = gets.split.map(&:to_i)
count = Array.new(n, 0)
for i in 1..(n - 1) do
  for j in (i + 1)..n do
    d = [j - i, (x - i).abs + 1 + (j - y).abs].min
    count[d] += 1
  end
end
for k in 1...n do
  puts count[k]
end


Measured memory_bytes: 3836
use proconio::input;

fn main() {
    input! {
        n: u64,
        mut l: [u64; n]
    }

    solve(&mut l);
}

fn solve(l: &mut [u64]) {
    l.sort();

    let mut cnt = 0;
    for &x in l.iter() {
        for &y in l.iter() {
            if x >= y {
                continue;
            }
            for &z in l.iter() {
                if y >= z {
                    continue;
                }
                if x + y > z {
                    cnt += 1;
                }
            }
        }
    }
    println!("{}", cnt);
}


Measured memory_bytes: 2192
import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, x, m = I()

seen = [x]
ans = x
for i in range(1, n):
    now = seen[-1]
    next = (now * now) % m

    if next not in seen:
        seen.append(next)
        ans += next
    else:
        loop = seen[seen.index(next):]
        count = len(loop)
        total = sum(loop)
        remain = n - i
        
        q, r = remain // count, remain % count
        ans += q * total
        ans += sum(loop[:r])
        break
        
print(ans)


Measured memory_bytes: 71276
#include "bits/stdc++.h"
#define int long long
#define range(i, a, b) for(auto i = a; i < b; i++)
#define rep(i, a) range(i, 0, a)
#define all(a) (a).begin(),(a).end()
using namespace std;
//const int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
const int MOD = 1000000007;
const long double EPS = 1e-8;
using vi = vector <int>;
using vvi = vector <vi>;

std::vector<std::vector<int>> grid_bfs(const std::vector<std::string> &g, char start, char wall) {
    const int INF = 1000000000;
    using pii = std::pair<int, int>;

    int h = g.size(), w = g[0].size();
    static const auto is_valid = [&](int i, int j) {
        if (i < 0 || i >= h || j < 0 || j >= w) return false;
        if (g[i][j] == wall) return false;
        return true;
    };

    static const pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    std::queue<pii> q;
    std::vector<std::vector<int>> d(h, std::vector<int>(w, INF));

    rep(i, h) rep(j, w) {
        if (g[i][j] == start) {
            d[i][j] = 0;
            q.emplace(i, j);
        }
    }

    while (q.size()) {
        int ci, cj;
        std::tie(ci, cj) = q.front();
        q.pop();
        for (auto &v : dir) {
            int ni = ci + v.first;
            int nj = cj + v.second;
            if (is_valid(ni, nj)) {
                int nd = d[ci][cj] + 1;
                if (d[ni][nj] > nd) {
                    d[ni][nj] = nd;
                    q.emplace(ni, nj);
                }
            }
        }
    }

    return d;
}

int h, w;
vector <string> mp;
signed main() {
	cin >> h >> w;
	mp = vector <string> (h);
	int cnt = 0;
	rep (i, h) {
		cin >> mp[i];
		rep (j, w) cnt += mp[i][j] == '#';
	}
	mp[0][0] = 'o';
	vector <vector <int>> d = grid_bfs(mp, 'o', '#');
	if (d[h - 1][w - 1] == 1000000000)
		cout << -1 << endl;
	else
		cout << h * w - cnt - d[h - 1][w - 1] - 1<< endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

void swap(int *x,int *y){
	int z;
	z=*x;
	*x=*y;
	*y=z;
}

int main (){
	int i,n,x,y,z;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d %d %d",&x,&y,&z);
		if(z<x)swap(&x,&z);
		if(z<y)swap(&y,&z);
		if(x*x+y*y==z*z)printf("YES\n"); else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep2(i, s, n) for (ll i = s; i < (ll)(n); i++)
#define repr(i, n) for (ll i = n; i >= 0; i--)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define COUTF(x) cout << setprecision(15) << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin())  // 先頭文字削除
#define ALL(x) x.begin(), x.end()
#define REVERSE(x) reverse(ALL(x))
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr ll INFL = 0x3f3f3f3f3f3f3f3f;
constexpr double PI = 3.141592653589793238462643383279;
ll getDigit(ll x) {
  return x == 0 ? 1 : log10(x) + 1;
}

signed main() {
  ld A, B, X;
  cin >> A >> B >> X;
  if (A * A * B == X) {
    COUTF(0.0);
    return 0;
  }

  ld area = X / A;
  debug(area);
  ld tan;
  if (area <= 0.5 * A * B) {
    // debug(1);
    // tan = (2 * area - A * B) / (B * B);
    tan = (2 * area) / (B * B);
  } else {
    tan = (A * A) / (2 * (area - A * B));
  }
  // tan = abs(tan);
  debug(tan);
  ld ans = atanl(tan) / PI * 180;
  debug(ans);
  if (area <= 0.5 * A * B) {
    COUTF(90 - ans);
  } else {
    COUTF(90 + ans);
  }

  return 0;
}

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

int main() {
  int n; cin>>n;
  vector<int> h(n);
  for (int i=0; i<n; i++) cin>>h[i];
  int ans=0,t_ans=0,b_h=h[0];
  for (int j=1; j<n; j++){
    if (b_h>=h[j]) t_ans+=1;
    else{
      ans=max(ans,t_ans);
      t_ans=0;
    }
    b_h=h[j];
  }
  ans=max(ans,t_ans);
  cout<<ans<<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long int 
#define double /*long*/ double
#define endl '\n'
#define vll vector<ll>
#define vvll vector<vll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vppll vector<pair<pll,pll>>
#define mp make_pair
#define pb push_back
#define mapll map<ll,ll>
#define fir first
#define sec second
#define _cin ios_base::sync_with_stdio(0);  cin.tie(0);
#define fo(i,b) for(i=0;i<b;i++)
#define repa(i,a,b) for(i=a;i<b;i++)
#define repb(i,a,b) for(i=a;i>=b;i--)
#define all(x) (x).begin(), (x).end()
#define s(v) v.size()
const long long int MAX = (ll)(1e18+1);
const long long int MIN = (ll)(-1e18-1);
const long long int mod = (ll)(1e9+7);
using namespace std;

ll max(ll a,ll b,ll c) {return max(max(a, b), c);}
ll min(ll a,ll b,ll c) { return min(min(a, b), c);}
ll max(ll a,ll b) {return (a>b) ? a : b;}
ll min(ll a,ll b) {return (a<b) ? a : b;}
ll power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll power_mod(ll a, ll n, ll mod_){ ll p=1; while(n){ if(n%2){ p=(p*a)%mod_;} n/=2; a=(a*a)%mod_;} return p%mod_;}
                                                 /*Code Begins*/


int main(){
    _cin;
    // cout << setprecision(15);
    ll mn = MAX, mx = MIN;
    ll n, t, m, k, i, j,  sum=0,  prev, flag=0, cnt=0;
    ll x=0, y=0, fx, diff, tot=0, l , r;
    int TC=1;
    // cin >> TC;
while(TC--){
    cin >> n >> m;
    char a[n][m];
    fo(i,n) fo(j,m) cin >> a[i][j];
    ll dp[n+1][m+1];
    fo(i,n) fo(j,m) dp[i][j]=0;
    flag=1;
    fo(i,n){
        if(flag){
            if(a[i][0]=='.') dp[i][0]=1;
            else{
                dp[i][0]=0;
                flag=0;
            }
        }else dp[i][0]=0;
    }
    flag=1;
    fo(i,m){
        if(flag){
            if(a[0][i]=='.') dp[0][i]=1;
            else{
                dp[0][i]=0;
                flag=0;
            }
        }else dp[0][i]=0;
    }
    repa(i,1,n){
        repa(j,1,m){
          if(a[i][j]=='.')  dp[i][j] = dp[i-1][j] + dp[i][j-1];
            dp[i][j]%=mod;
        }
    }
    cout << dp[n-1][m-1];
}
 return 0;      
}

Measured memory_bytes: 9088
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let k: usize = read();
    let mut l: Vec<i32> = (0..n).map(|_| read()).collect();
    l.sort();
    l.reverse();
    println!("{}", l.iter().take(k).sum::<i32>());
}

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


Measured memory_bytes: 4352
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif

__asm__ (
	"asm_my_gcd2_in:"
	"movl $0, %edx;"
	"divl %ecx;"
	"cmpl $0, %edx;"
	"jz asm_my_gcd2_in2;"
	"asm_my_gcd2_in1:"
	"movl %ecx, %eax;"
	"movl %edx, %ecx;"
	"movl $0, %edx;"
	"divl %ecx;"
	"cmpl $0, %edx;"
	"jnz asm_my_gcd2_in1;"
	"asm_my_gcd2_in2:"
	"ret;"
);

inline int gcd(uint32_t a, uint32_t b){
	if(a==0 || b==0) return a==0?b:a;
	uint32_t ans;
	__asm__ (
	"movl %1, %%ecx;"
	"movl %2, %%eax;"
	"call asm_my_gcd2_in;"
	"movl %%ecx, %0;"
		:"=r"(ans)
		:"r"(a),"r"(b)
		:"%eax", "%ecx", "%edx", "cc"
		);
	return ans;
}

int main(void){
	int n, i;
	int a[100001];
	int l[100002], r[100002];
	scanf("%d", &n);
	for(i=1; i<=n; i++){
		scanf("%d", a+i);
	}
	l[0]=0;
	for(i=1; i<=n; i++){
		l[i] = gcd(l[i-1], a[i]);
	}
	r[n+1]=0;
	for(i=n; i>0; i--){
		r[i] = gcd(r[i+1], a[i]);
	}
	int max=0;
	for(i=1; i<=n; i++){
		int now=gcd(l[i-1], r[i+1]);
		if(now>max) max=now;
	}
	printf("%d\n", max);
}


Measured memory_bytes: 1280
#pragma GCC optimize ("Ofast")
#include "bits/stdc++.h"
	
#define PI 3.141592653589793
#define FAST ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
// Use for file I/O;
#define FIN string _fname = "paintbarn"; \
			string _is = _fname + ".in", _os = _fname + ".out"; \
			freopen(_is.c_str(), "r", stdin); \
			freopen(_os.c_str(), "w", stdout);

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

using namespace std;

const ll INF = 1e9 + 10;
const ll INF2 = 3e18 + 10;
const int MOD = 1e9 + 7;
const ld EPS = 1e-4;

const int LOGN = 19;
const int MAXN = 305;

int a[100];

int main() {
	FAST;

	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];

	vector<int> dp(k + 1, 1);
	for (int i = 1; i <= k; i++) {
		for (int j = 0; j < n; j++) {
			if (a[j] <= i) {
				if (dp[i - a[j]] == 1) {dp[i] = 0; break;} 
			}
		}
	}	

	cout << (dp[k] == 0 ? "First" : "Second");
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) begin(x), end(x)
using namespace std;
using ll = long long;
constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;
const double PI = acos(-1);
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);
}
/*-------------------------------------------*/

class UnionFind {
    vector<int> par;
    int c;

  public:
    UnionFind(int n) : par(n, -1), c(n) {}
    int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
    int size(int x) { return -par[find(x)]; }
    int count() const { return c; }
    bool same(int x, int y) { return find(x) == find(y); }
    bool unite(int x, int y) {
        if((x = find(x)) == (y = find(y))) return false;
        if(par[x] < par[y]) swap(x, y);
        par[y] += par[x];
        par[x] = y;
        return c--;
    }
};

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

    int N;
    cin >> N;
    vector<int> a(N), b(N);
    int x = 0;
    rep(i, N) {
        cin >> a[i];
        x ^= a[i];
    }
    a.push_back(x);
    x = 0;
    rep(i, N) {
        cin >> b[i];
        x ^= b[i];
    }
    b.push_back(x);

    auto aa = a, bb = b;
    sort(ALL(aa));
    sort(ALL(bb));
    if(aa != bb) {
        cout << "-1\n";
        return 0;
    }

    int e = 0;
    map<int, int> mp;
    mp[a[N]] = mp[b[N]] = 0;
    rep(i, N) if(a[i] != b[i]) {
        e++;
        mp[a[i]] = mp[b[i]] = 0;
    }

    int idx = 0;
    for(auto &&p : mp)
        p.second = idx++;

    UnionFind uf(idx);
    rep(i, N) uf.unite(mp[a[i]], mp[b[i]]);

    cout << e + uf.count() - 1 << "\n";

    return 0;
}

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

using namespace std;

int main() {
  int d;
  string message;
  cin >> d;
  if ( d == 25 )
    message = "Christmas";
  else if ( d == 24 )
    message = "Christmas Eve";
  else if ( d == 23 )
    message = "Christmas Eve Eve";
  else if ( d == 22 )
    message = "Christmas Eve Eve Eve";
  cout << message << endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

res = []
# 0 = A , 1 = B
for bit in range(2 ** n):
    if str(bin(bit)).count('1') % 2 == 1:
        continue

    odds = []
    evens = []
    for i in range(n):
        if (bit >> i) & 1:
            card = B[i]
            check = (i + 1) % 2

        else:
            card = A[i]
            check = i % 2

        if check == 1:
            odds.append([card, i+1])
        else:
            evens.append([card, i+1])

    if 0 <= len(evens) - len(odds) <= 1:
        odds.sort(reverse=True)
        evens.sort(reverse=True)
        now = 0
        pattern = []
        for _ in range(len(evens)):
            num1, idx1 = evens.pop()

            if now <= num1:
                now = num1
                pattern.append(idx1)
                if odds:
                    num2, idx2 = odds.pop()
                    if now <= num2:
                        now = num2
                        pattern.append(idx2)
                    else:
                        break

            else:
                break
        else:
            res.append(pattern)


if not res:
    print(-1)
    exit()

ans = []
for pattern in res:
    count = 0
    for i in range(n-1):
        num = pattern[i]
        check = pattern[i+1:]
        for t in check:
            if t < num:
                count += 1

    ans.append(count)

print(min(ans))

Measured memory_bytes: 64440
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	if((a==b&&c!=a)||(a==c&&b!=a)||(b==c&&a!=b))
	cout<<"Yes";
	else
	cout<<"No";
	return 0;
}

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

using namespace std;

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

char s[125252];
int n;
char mx[256];

int right(int l,int r);
int left(int l, int r){
  // hidari fumikomi
  if(l==n-1)return 0;
  int nxt = l+1;
  if(mx[s[l]] > mx[s[nxt]]){
    // step by left
    return 1+left(nxt,r);
  }else{
    return right(l,nxt);
  }
}
int right(int l, int r){
  // migi fumikomi
  if(r==n-1)return 0;
  int nxt = r+1;
  if(mx[s[nxt]] > mx[s[r]]){
    // step by right
    return 1+right(l,nxt);
  }else{
    return left(nxt,r);
  }
}

int main(){
  mx['1']=mx['4']=mx['7']=0;
  mx['2']=mx['5']=mx['8']=1;
  mx['3']=mx['6']=mx['9']=2;
  while(true){
    scanf("%s",s);
    if(s[0]=='#')break;
    n = strlen(s);
    int ans = min(left(0,-1),right(-1,0));
    printf("%d\n",ans);
  }
}

Measured memory_bytes: 3644
#include <stdio.h>
#include <string.h>
int main(void){
    char s[26];
    int i,j,k=0;
    scanf("%s",s);
    for(i=0;i<strlen(s);i++){
        for(j=0;j<strlen(s);j++){
            if(s[i]==s[j]){
                if(i==j) k+=0;
                else k++;
            }
            else k+=0;
        }
    }
    if(k==0) printf("yes\n");
    else printf("no\n");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define REP1(i,a,b) for(int i=a; i<=(int)(b); i++)
#define ALL(x) begin(x),end(x)
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef vector<int> VI;
typedef pair<int,int> PII;

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    char c;
    cin >> c;   
    if ( c<'a' ) cout << 'A';
    else cout << 'a';

    return 0;
}

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

char s[105][105];
int main() {
	int h, w; scanf("%d%d", &h, &w);
	rep(i, h)scanf("%s", s[i + 1] + 1);
	rep(i, h + 2)rep(j, w + 2) {
		if (i == 0 || j == 0 || i == h + 1 || j == w + 1)s[i][j] = '#';
	}
	rep(i, h + 2)printf("%s\n", s[i]);
}

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int a = Integer.parseInt(str[0]);
    int b = Integer.parseInt(str[1]);
    if(a==b)
      System.out.println(a);
    else if(a<b)
      System.out.println(a);
    else
      System.out.println(a-1);
  }
}

Measured memory_bytes: 32652
#include <climits>
#include<iostream>
using namespace std;
int main(){
  int h,n;
  cin >> h >>n;
  int magics[2*n];
  for(int i=0;i<n;i++){
    cin >>magics[2*i]>>magics[2*i+1];
  }
  unsigned long long* h_table;
  int _h=h+1;
  h_table=new unsigned long long[_h];
  for(int i=1;i<_h;i++){
    h_table[i]=INT_MAX;
  }
  h_table[0]=0;
  for(int i=0;i<_h;i++){
    for(int j=0;j<n;j++){
      h_table[i+magics[2*j]>h?h:i+magics[2*j]]=
        h_table[i+magics[2*j]>h?h:i+magics[2*j]]<h_table[i]+magics[2*j+1]?h_table[i+magics[2*j]>h?h:i+magics[2*j]]:h_table[i]+magics[2*j+1];
    }
  }
  cout<<h_table[h]<<endl;

}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <string>
#include <cctype>
#include <map>

using namespace std;

const int mod = 1000000007;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
#define ll long long

int main()
{
    int n;
    cin >> n;

    bool four = false;
    for (int i = 0; i < n; i++)
    {
        char s;
        cin >> s;

        if (s == 'Y')
        {
            four = true;
        }   
    }
    
    cout << (four ? "Four" : "Three") << endl;
}

Measured memory_bytes: 256
def examA():
    S = SI()
    if S in alphabet:
        ans = "a"
    else:
        ans = "A"
    print(ans)
    return

def examB():
    N, K = LI()
    P = LI()
    P.sort()
    ans = sum(P[:K])
    print(ans)
    return

def examC():
    N = I()
    ans = ""
    while(N>0):
        N -= 1
        ans += alphabet[N%26]
        N //= 26
        if N==0:
            break
    print(ans[::-1])
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(int)
    for a in A:
        D[a] += 1
    S = sum(A)
    q = I()
    ans = [0]*q
    for i in range(q):
        a, b = LI()
        if not a in D:
            ans[i] = S
            continue
        S += (b-a)*D[a]
        D[b] += D[a]
        D[a] = 0
        ans[i] = S

    for v in ans:
        print(v)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Measured memory_bytes: 22440
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    long long H[N];
    int count = 0;
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> H[i];
        if (i != 0 && H[i - 1] >= H[i])
        {
            ++ans;
            count = max(count, ans);
        }
        else
        {
            ans = 0;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 1024
N=int(input())
D=list(map(int,input().split()))
x=[0]*(10**5+1)
for d in D:
    x[d]+=1
a=0
for i in range(10**5):
    x[i+1]+=x[i]
    if x[i+1]==N//2:
        a+=1
print(a)

Measured memory_bytes: 14424
package main

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

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	s := getNextString(scanner)
	r := 0
	var ans int
	for i := 0; i < 3; i++ {
		if s[i] == 'R' {
			r++
		} else {
			if ans < r {
				ans = r
			}
			r = 0
		}
	}
	if ans < r {
		ans = r
	}
	fmt.Fprintln(writer, ans)
}


Measured memory_bytes: 1816
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod = 1000000007;

ll r(ll x, ll y) {
  if (y == 0) return 1;
  else if (y % 2 == 0) return r(x, y/2) * r(x, y/2) % mod;
  else return x * r(x, (y-1)/2) % mod * r(x, (y-1)/2) % mod;
}
  
int main() {
  int n, k;
  cin >> n >> k;
  ll m = 0;
  ll M = 0;
  for (int i = 0; i < k; i++) {
    m += i;
    M += (n - i);
  }
  ll sum = M - m + 1;
  for (int i = k; i<= n; i++) {
    m += i;
    M += (n - i);
    ll p = M - m + 1;
    sum += p;
  }
  sum %= mod;
  printf("%lld\n", sum);
} 


Measured memory_bytes: 3764
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;


int main(){
    int n =3;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a,a+n);
    cout << a[0] << " " << a[1] << " " << a[2] << endl;
    return 0;
}



Measured memory_bytes: 3096
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<float.h>
#include<tuple>
#include<string.h>
#include<iomanip>
#include<stack>
#include<queue>
#include<map>
#include<deque>

using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define ALLOF(c) (c).begin(), (c).end()
#define Pa pair<ll,ll>
const ll mod=1000000007;
const ll INF=10e12;
const ll inf=-1;
ll ABS(ll a){return max(a,-a);}


int main(void){
    ll N,X,Y;
    cin>>N>>X>>Y;
    X--;
    Y--;
    vector<ll> ans(N-1);
    rep(i,N-1) ans.at(i)=0;
    rep(i,N-1){
        for(ll j=i+1;j<N;j++){
            ll dist=min(j-i,ABS(j-Y)+ABS(X-i)+1);
            ans.at(dist-1)++;
            
        }
    }
    
    rep(i,N-1) cout<<ans.at(i)<<endl;
    return 0;
}


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

int main(){
    string s, t;
    cin >> s;
    cin >> t;
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1,0));
    rep(i,n){
        rep(j,m){
            if(s[i] == t[j]) dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1);
            else dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
        }
    }
    int l = dp[n][m];
    int p = n, q = m;
    string ans = "";
    while(l > 0){
        while(dp[p][q] == l) p--;
        ans = s[p] + ans;
        while(t[q-1] != s[p]) q--;
        l--; q--;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 35584
#include <bits/stdc++.h>
/* Uncomment only if you are not using GNU compiler->
*/
#include <map>
#include <algorithm> 
#include <vector> 
#include <string.h> 
#include <math.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <chrono> 
#include <thread> 
#include <iomanip>
/**/ 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define all(v)  v.begin(), v.end()

//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const long long MOD = 1000000007;
const long long inf = 1e18;
 
using namespace std;

int t=0;

ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}

ll power(ll x, ll n)
{
    ll res=1;
    while(n>0){
        if(n&1) res=res*x;
        x=x*x;
        n>>=1;
    }
    return res;
}

void solve()
{
    int x, y;
    cin>>x>>y;
    if(y%2==1 || y<2*x || y>4*x)
    {
        cout<<"No\n";
    }
    else
        cout<<"Yes\n";
}
 
int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("ggg.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1, tt=1;
    // cin>>t;
    while(tt<=t)
    {
        // cout<<"Case #"<<tt<<": ";
        solve();
        tt++;
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 3804
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define PN cout << endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (n-1); i >= (int)(m); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - (a)) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - (a)) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return

/*
ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
*/

/*
vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}
*/

/*
ll ncr[100][100];
ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

ll npr[100][100]={};
ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

ll nHr(int n,int r){ret nCr(n+r-1,r);}
*/

///////////////////////////////////////////////////////////////////////////



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

    rep(i,0,3)cout << s[i];
    PN;
    
    return  0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <queue>
typedef long double ll;
using namespace std;
int main()
{
    int n,m; cin >> n >> m;
    auto compare = [](ll a, ll b) {
        return a < b;
    };
    priority_queue<ll,vector<ll>,decltype(compare)> que {compare};
    for(int i=0;i<n;i++){
        int a; cin >> a;
        que.push(a);
    }
    for(int i=0;i<m;i++){
        ll x = que.top(); que.pop();
        que.push(x/2.0);
    }long long sum = 0;
    for(int i=0;i<n;i++){
        sum += (int)que.top(); que.pop();
    }
    printf("%lld\n",sum);
}




Measured memory_bytes: 2420
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)


int main(){
   long long n;
   cin >> n;
   
   vector<long long> factor;
   
   for(int i=1; i<=(long long)sqrt(n); i++){
      if(n%i==0){
         factor.push_back(i);
         if(n==i*i) break;
         factor.push_back(n/i);
      }
   }
   
   long long ans;
   if(factor.size()%2==0){
      ans = factor[factor.size()-1]+factor[factor.size()-2]-2;
   }else{
      ans = factor[factor.size()-1]*2 -2;
   }
   
   cout << ans << endl;
   
   return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
struct _IO{_IO(){ios::sync_with_stdio(0);cin.tie(0);}}_io;
typedef long long ll; typedef long double db;
const int N = 2e5 + 5, M = 1e9 + 7;

int main() {
  string s;
  cin >> s;
  s = regex_replace(s, regex("eraser"), "");
  s = regex_replace(s, regex("erase"), "");
  s = regex_replace(s, regex("dreamer"), "");
  s = regex_replace(s, regex("dream"), "");
  puts(s.size() ? "NO" : "YES");
}


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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

template<class T>
bool ChangeMax(T&a,const T&b){
  if(a >= b) return false;
  a = b;    return true;
}

template<class T>
bool ChangeMin(T&a,const T&b){
  if(a <= b) return false;
  a = b;    return true;  
}

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int h,n; cin >> h >> n;
  vector<int> v(n); cin >> v;
  int sum = 0;
  for(int i = 0; i < n; ++i)sum += v[i];
  if(sum >= h) cout << "Yes\n";
  else cout << "No\n";
  return 0;
}


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

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner scan = new Scanner(System.in);

		long n = scan.nextLong();
		int m = scan.nextInt();

		for(int i = 0;i<m;i++) {

			int a = scan.nextInt();
			n -= a;
		}


			System.out.println(n<0?-1:n);


		scan.close();
	}

}


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

int main() {
	int N, ans, input, manzoku = 0;
	cin >> N;
	vector<int> A;
	vector<int> B;
	vector<int> C;
	for (int i = 0; i < N; i++) {
		cin >> input;
		A.emplace_back(input);
	}
	A.emplace_back(21);
	for (int i = 0; i < N; i++) {
		cin >> input;
		B.emplace_back(input);
	}
	for (int i = 0; i < N - 1; i++) {
		cin >> input;
		C.emplace_back(input);
	}
	for (int i = 0; i < A.size() - 1; i++) {
		manzoku += B[A[i]-1];
		if (A[i] + 1 == A[i + 1]) {
			manzoku += C[A[i] - 1];
		}
	}
	ans = manzoku;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void){
	int a,b;
	scanf("%d",&a);
	scanf("%d",&b);
	
	if(a>b){
		printf("a > b\n");
	}else if(a<b){
		printf("a < b\n");
	}else{
		printf("a == b\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <iostream>

using namespace std;

int main(void)
{
    long long N, X, i, m[101], min=10000;

    cin >> N >> X;

    for(i=1; i<=N; i++){
        cin >> m[i];

        if(min > m[i]){
            min = m[i];
        }

        X -= m[i];
    }

    cout << N+X/min << endl;

    return 0;
}

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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
#define mem(a,b) memset(a,b,sizeof(a))
#define shutdown ios::sync_with_stdio(false)
#define MAX 10e18+1000
#define INF 0x3f3f3f3f

int m[100];

int main() {
    shutdown;
    int a;
    cin>>a;
    a=sqrt(a);
    cout<<a*a<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

#define MAXN (30)

vector<pair<int, int> > a[MAXN];

int main() {
	cout << fixed << setprecision(12);	
	int l;
	cin >> l;
	int n;
	for (int i = 20; ; i--) {
		if (l & (1 << i)) {
			n = i + 1;
			break;
		}
	}
	for (int i = 0; i < n - 1; i++) {
		a[i].push_back(make_pair(i + 1, 0));
	}
	for (int i = 0; i < n - 1; i++) {
		a[i].push_back(make_pair(i + 1, 1 << i));
	}
	int cur = (1 << (n - 1));
	for (int i = 0; i < n - 1; i++) {
		if (l & (1 << i)) {
			a[i].push_back(make_pair(n - 1, cur));
			cur += (1 << i);
		}
	}
	int m = 0;
	for (int i = 0; i < n; i++) {
		m += a[i].size();
	}
	cout << n << " " << m << endl;
	for (int i = 0; i < n; i++) {
		for (auto&e : a[i]) {
			cout << i + 1 << " " << e.first + 1 << " " << e.second << endl;
		}
	}
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

	mod& operator*=(const mod & m2) {
		x *= m2.x;
		x %= MOD;
		return *this;
	}

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

ostream &operator<<(ostream & os, const mod & m) {
	return os << m.x;
}



Measured memory_bytes: 3548
# coding: utf-8
# Your code here!
from collections import deque
import collections

n,m=map(int,input().split())
friends=[[]for _ in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)
dist=[-1 for i in range(n)]
ans=0

for j in range(n):
    if dist[j]==-1:
        dist[j]=ans
        d=deque([j])
    
        while d:
            v=d.popleft()
            for i in friends[v]:
                if dist[i]!=-1:
                    continue
                dist[i]=ans
                d.append(i)
        ans+=1   
c = collections.Counter(dist)
print(c.most_common()[0][1])

Measured memory_bytes: 57336
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int M=1e5+5;
const int N=1e9+5;
const int mod=1e9+7;
struct Matrix{
	int n,m;
	int ju[5][5];
	Matrix(){
		n=m=3;
		memset(ju,0,sizeof(ju));
		ju[1][1]=ju[2][2]=ju[0][0]=1;
	}
	Matrix(int n1,int m1){
		n=n1,m=m1;
		memset(ju,0,sizeof(ju));
	}
	int MUL(int a,int b){
		int ret=0;
		while(b){
			if((b&1))
				ret=(ret+a)%mod;
			a=(a+a)%mod;
			b>>=1;
		}
		return ret;
	}
	Matrix Se(){
		Matrix ret(n,m);
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				ret.ju[i][j]=ju[i][j];
		return ret;
	}
	Matrix operator*(const Matrix dd){
		Matrix ret(n,dd.m);
		if(dd.n!=m)
		{
			printf("Error\n");
			return ret;
		}
		for(int i=0;i<ret.n;i++)
			for(int j=0;j<ret.m;j++)
				for(int k=0;k<m;k++)
					ret.ju[i][j]=(ret.ju[i][j]+(((long long)ju[i][k])*((long long)dd.ju[k][j])%mod))%mod;
//					ret.ju[i][j]=(ret.ju[i][j]+MUL(ju[i][k],dd.ju[k][j]))%mod;
		return ret;
	}
	Matrix operator^(int p){
		Matrix ret,Self=Se();
		while(p)
		{
			if((p&1))
				ret=ret*Self;
			Self=Self*Self;
			p>>=1;
		}
		return ret;
	}
}EM(3,3),dp(1,3),ES(3,3);

int n,m;
int Si[M],E[3][3]={{1,2,1},{0,1,1},{1,2,2}};

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d",&Si[i]);
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			EM.ju[i][j]=E[i][j];
	ES=EM;
	ES.ju[2][0]=ES.ju[2][1]=0;
	ES.ju[2][2]=1;
	dp.ju[0][0]=1,dp.ju[0][1]=2,dp.ju[0][2]=1;
	for(int i=1;i<=m;i++)
	{
		dp=dp*(EM^(Si[i]-Si[i-1]-1));
		dp=dp*ES;
	}
	dp=dp*(EM^(n-Si[m]-1));
	cout<<dp.ju[0][2]<<endl;
	return 0;
}																																		

Measured memory_bytes: 640
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctype.h>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i, n) REP(i, 0, n)
#define lengthof(x) (sizeof(x) / sizeof(*(x)))
#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
//4方向ベクトル→↑←↓
int dx[] ={1,0,-1,0};
int dy[] ={0,-1,0,1};
int M,N,K;
const int MAX_M = 1010;
const int MAX_N = 1010;

char board[MAX_M][MAX_N];
char c;
int a[1010][1010];//長方形内のJの数
int b[1010][1010];//長方形内のOの数
char s[1010];
int main()
{
  scanf("%d%d%d",&M,&N,&K);
  for(int i = 1;i <=M;i++){
    scanf("%s",s+1);
    for(int j = 1;j <=N;j++){
      if(s[j] =='J'){
	a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1]+1;
	b[i][j] = b[i-1][j]+b[i][j-1]-b[i-1][j-1];
      }else if(s[j] =='O'){
	a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	b[i][j] = b[i-1][j]+b[i][j-1]-b[i-1][j-1]+1;
      }else{
	a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1];
	b[i][j] = b[i-1][j]+b[i][j-1]-b[i-1][j-1];
      }
    }
  }
  int s,t,u,v;
  for(int l = 0;l <K;l++){
    int ansJ,ansO,ansI;
    scanf("%d%d%d%d",&s,&t,&u,&v);
    s--;
    t--;
    ansJ =a[u][v]-a[s][v]-a[u][t]+a[s][t];
    ansO =b[u][v]-b[s][v]-b[u][t]+b[s][t];
    ansI =(u-s)*(v-t)-(ansJ+ansO);
    printf("%d %d %d\n",ansJ,ansO,ansI);
  }
  return 0;
}

Measured memory_bytes: 9380
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int ans1=0;
int ans2=0;
int ans3=0;
inline ll read()
{
	ans1=ans2=ans3=0;
	ll x=0,w=1;ans1=ans2=ans3=0;
	char c=getchar();ans1=ans2=ans3=0;
	while(c<'0'||c>'9')
	{ans1=ans2=ans3=0;
		if(c=='-') w=-1;ans1=ans2=ans3=0;
		c=getchar();
	}
	while(c<='9'&&c>='0')
	{ans1=ans2=ans3=0;
		x=(x<<1)+(x<<3)+c-'0';ans1=ans2=ans3=0;
		c=getchar();
	}
	return w==1?x:-x;
}

ll a[maxn],n,tot;
const ll mod=1000000007;

inline ll pw(ll a,ll b)
{
	ll ans=1,base=a;
	while(b)
	{ans1=ans2=ans3=0;
		if(b&1) ans=(ans*base)%mod;
		ans1=ans2=ans3=0;
		base=(base*base)%mod;
		ans1=ans2=ans3=0;
		b>>=1;
	}
	return ans;
}

int main()
{ans1=ans2=ans3=0;
	n=read();ans1=ans2=ans3=0;
	rep(i,1,n) a[i]=read(),tot=(tot+a[i])%mod;
	ans1=ans2=ans3=0;
	tot=(tot*tot)%mod;
	ans1=ans2=ans3=0;
	rep(i,1,n)
	{
		ans1=ans2=ans3=0;
		ll tmp=(a[i]*a[i])%mod;
		ans1=ans2=ans3=0;
		tot=(tot-tmp+mod)%mod;
	}
	ans1=ans2=ans3=0;
	ll p=pw(2,mod-2);
	ans1=ans2=ans3=0;
	tot=(tot*p)%mod;
	ans1=ans2=ans3=0;
	cout<<tot<<endl;
	ans1=ans2=ans3=0;
	return 0;
}


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

int main() {
  string s,t;
  cin >> s >> t;
  int cnt = 0;
  rep(i, s.size()){
     if(s[i] != t[i]){
       cnt++;
     }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 3872
#include <iostream>
using namespace std;
int main(void){
    int n;
    cin >> n;
    int A[n];
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    
    int count = 0;
    for(int i=0;i<n;i++){
        for(int j=n-1;j>=0;j--){
            if(A[j] < A[j-1]){
                count++;
                int tmp;
                tmp = A[j];
                A[j] = A[j-1];
                A[j-1] = tmp;
            }
        }
    }
  
    for(int i=0;i<n;i++){
        cout << A[i];
        if(i==n-1){
            cout << endl;
        }else{
            cout << " ";
        }
    }    
    cout << count << endl;

    return 0;
}



Measured memory_bytes: 2996
//#define _USE_MATH_DEFINES
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#pragma GCC diagnostic ignored "-Wmissing-declarations"
#define FINAL_OUT(x) {cout << (x) << '\n'; exit(0); }
inline int safe_mul(const int x, const int y) __attribute__ ((warn_unused_result));


int main()
{
//    freopen("in.txt","r", stdin);
//    freopen("out.txt", "w", stdout);
//    cout << fixed << setprecision(20);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;

    bool flag = s[0] == s[1] || s[1] == s[2] || s[2] == s[3];

    cout << (flag? "Bad" : "Good") << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
#include <complex>
#define CURR(P, i) (P[i])
#define NEXT(P, i) (P[(i + 1) % P.size()])

typedef complex<double> Point;
typedef vector<Point> Polygon;
struct Line : public vector<Point> {
  Line() {;}
  Line(Point a, Point b) { push_back(a); push_back(b); }
};
inline double cross(const Point& a, const Point& b){
  return imag(conj(a) * b);
}
Point crosspoint(const Line &l, const Line &m) {
  double A = cross(l[1] - l[0], m[1] - m[0]);
  double B = cross(l[1] - l[0], l[1] - m[0]);
  if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
  if (abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
  return m[0] + B / A * (m[1] - m[0]);
}
double polygonArea(const Polygon& P) {
  double A = 0;
  for (int i = 0; i < P.size(); ++i) 
    A += cross(CURR(P, i), NEXT(P, i));
  return abs(A) / 2.0;
}
double area(Line lx1, Line lx2, Line ly1, Line ly2){
  Polygon pol;
  pol.push_back(crosspoint(lx1, ly1));
  pol.push_back(crosspoint(lx2, ly1));
  pol.push_back(crosspoint(lx2, ly2));
  pol.push_back(crosspoint(lx1, ly2));
  return polygonArea(pol);
}

int main(){
  int N;
  while(cin>>N && N){
    double a[4][50] = {};
    REP(k, 4){
      REP(i, N){
        cin>>a[k][i + 1];
      }
    }
    REP(i, 4)a[i][N + 1] = 1;
    vector<Line> lx(N + 2), ly(N + 2);
    REP(i, N + 2){
      lx[i] = Line(Point(a[0][i], 0), Point(a[1][i], 1));
      ly[i] = Line(Point(0, a[2][i]), Point(1, a[3][i]));
    }
    double ans = 0;
    REP(y, N + 1)REP(x, N + 1){
      ans = max(ans, area(lx[x], lx[x + 1], ly[y], ly[y + 1]));
    }
    printf("%.6f\n", ans);
  }
  return 0;
}

Measured memory_bytes: 1268
#include <bits/stdc++.h> 
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(vec) vec.begin(), vec.end()
#define tmax(x,y,z) max((x),max((y),(z)))
#define tmin(x,y,z) min((x),min((y),(z)))
typedef long long ll;ll MM = 1000000000;ll mod = MM + 7; ll MMM=9223372036854775807;//2^63 -1
typedef vector<ll> lvec;typedef vector<double> dvec;typedef vector<string> svec;
ll GCD(ll x, ll y) {if (y == 0) return x;else return GCD(y, x % y);}
ll LCM(ll x, ll y) { return x / GCD(x, y) * y;}
//cout << fixed << setprecision(10);

int main(){
  ll n; cin>>n;
  vector<ll>odd(100001);
  vector<ll>even(100001);
  rep(i,n){
    ll t; cin>>t;
    if(i%2==0) even[t]++;
    else odd[t]++;
  }
  ll e_mode1=-1, e_mode2=-1, o_mode1=-1, o_mode2=-1;
  ll e1, o1;
  rep(i,100000){
    if(even[i]>e_mode1){
      e_mode1=even[i]; e1=i;
    }
    if(odd[i]>o_mode1){
      o_mode1=odd[i]; o1=i;
    }
  }
  rep(i,100000){
    if(even[i]>e_mode2 && i!=e1) e_mode2=even[i];
    if(odd[i]>o_mode2 && i!=o1) o_mode2=odd[i];
  }
  if(e1!=o1){
    cout<<n-e_mode1-o_mode1<<endl;
    return 0;
  }
  cout<<min(n-e_mode1-o_mode2,n-e_mode2-o_mode1)<<endl;
}

Measured memory_bytes: 1792