akhauriyash/Code-Regression huggingface dataset:
n, m = [int(x) for x in input().split()]

temp_list = [[] for _ in range(n + 1)]
for i in range(m):
    p, y = [int(x) for x in input().split()]
    temp_list[p].append((y, i))

ans_list = [""] * m
for p in range(1, n + 1):
    temp_list[p].sort()
    for j in range(len(temp_list[p])):
        _, i = temp_list[p][j]
        ans_list[i] = "{:06}{:06}".format(p, j + 1)

for ans in ans_list:
    print(ans)

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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li table[11][11];


int main() {
	li h, w;
	cin >> h >> w;
	rep(i, 10) {
		rep(j, 10) {
			cin >> table[i][j];
		}
	}
	rep(k, 10) {
		rep(i, 10) {
			rep(j, 10) {
				table[i][j] = min(table[i][j], table[i][k] + table[k][j]);
			}
		}
	}
	li res = 0;
	rep(i, h) {
		rep(j, w) {
			li a;
			cin >> a;
			if (a >= 0) {
				res += table[a][1];
			}
		}
	}
	cout << res << endl;


	return 0;
}

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

int main(){
  int n;
  cin>>n;
  vector<int>x(n);
  for(int i=0;i<n;i++)cin>>x[i];
  ll MIN=10000000000;
  for(int i=1;i<=100;i++){
    int sum=0;
    for(int j=0;j<n;j++){
      sum+=(x[j]-i)*(x[j]-i);
    }
    if(MIN>sum)MIN=sum;
  }
  cout<<MIN<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int n, k;
long long t, s, e;
long long a[100001];
long long x[100001];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &t);
		a[i + 1] = a[i] + t;
		if (t < 0)t = 0;
		x[i + 1] = x[i] + t;
	}
	for (int i = 0; i + k <= n; i++) {
		t = x[n] - (x[i + k] - x[i]);
		s = a[i + k] - a[i];
		if (s < 0)s = 0;
		if (e < t + s)e = t + s;
	}
	printf("%lld\n", e);
}

Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
#define M 2550
#define LL long long
#define int LL
const int mo = 1e9 + 7;
int dp[52][5201][52]; // 放到第i位 在我 之前 的空位有h位.

void Add(int &res,int x) {
	res += x;
	if(res > mo) res -= mo;
	return ;
}
#define debug(x) cout << #x <<" " << x << endl;
main () {
	int n,k;
	cin >> n >> k;
	dp[1][M][0] = 1;
  	for(int i=1;i<=n;i++) {
		for(int j=0;j<=M*2;j++) {
			for(int h=i-1;h>=0;h--) {
				if(!dp[i][j][h]) continue;
				Add(dp[i+1][j][h],1LL*dp[i][j][h]*(h<<1|1)%mo); // 放自己.
				Add(dp[i+1][-2*i+j][h+1],dp[i][j][h]); // 放后面 . 且当前位不放先.
				if(h) Add(dp[i+1][j+2*i][h-1],1LL*dp[i][j][h]*h%mo*h%mo); // 放前面 且当前位放前面空出来的.
			}
		}
	}
	cout<<dp[n+1][M+k][0];
	return 0;
}

Measured memory_bytes: 107520
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define INF 1e15
#define MAX_N 1000001
#define FOR(i, a, b) for(ll i=a; i<b; i++)
#define REP(i, n) for(ll i=0; i<n; i++)
#define RER(i, n) for(ll i=n-1; i>=0; i--)
#define ALL(v) v.begin() v.end()
#define pb push_back
using namespace std;
typedef long long ll;
struct edge{ll to, cost;};
typedef pair<ll, ll> P;
ll n, q, k;
vector<edge> G[MAX_N];
ll d[MAX_N], x[MAX_N], y[MAX_N];

void dijkstra(ll s){
	priority_queue<P, vector<P>, greater<P> > que;
	fill(d, d + n + 10, INF);
	d[s] = 0;
	que.push(P(0, s));

	while(!que.empty()){
		P p = que.top(); que.pop();
		ll v = p.second;
		if(d[v] < p.first) continue;
		for(edge e: G[v]){
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

signed main(){
	cin >> n;
	REP(i, n-1){
		ll a, b, c; cin >> a >> b >> c;
		edge e1, e2;
		e1.to = a; e1.cost = c;
		e2.to = b; e2.cost = c;
		G[a].pb(e2);
		G[b].pb(e1);
	}

	cin >> q >> k;
	dijkstra(k);
	REP(i, q){
		cin >> x[i] >> y[i];
	}
	REP(i, q) cout << d[x[i]] + d[y[i]] << endl;
    return 0;
}

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

int main(){
	int n;
	int v[22],c[22];
	scanf("%d",&n);
	for(int i = 0 ; i < n ; i ++){
		scanf("%d",&v[i]);
	}
	for(int i = 0 ; i < n ; i ++){
		scanf("%d",&c[i]);
	}
	
	int ret = 0;
	for(int i = 0 ; i < n ; i ++){
		ret += max( v[i]-c[i] , 0 );
	}
	cout << ret << endl;
}

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

int n,k,h,w,a,b;
string s,t;

int main() {
  cin >> n >> h >> w;
  cout << (n-w+1)*(n-h+1) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define P 1000000007
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;

void solve() {
	ll n;
	cin >> n;
	
	ll ans = 0;
	for(ll i = 1; i <= n; i++) {
		ll m = n / i;
		ans += i * (m) * (m + 1) / 2; 
	}	
	
	cout << ans << endl;
}

int main(){
#define MULTITEST 0
#if MULTITEST   
 
    CASET {
        solve();
    }
    
#else

    solve();
    
#endif

    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
using namespace std;
 
int main()
{
    int MAX_X = 150;
    int MAX_Y = 150;
    int x,y,rectangle,ansx,ansy,i;
    int rectangles[151][151] = {0};
    bool flag = false;
     
    for (int x = 1; x <= MAX_X; x++) {
        for (int y = x + 1; y <= MAX_Y; y++) {
            rectangles[x][y] = x*x + y*y;
        }
    }
     
    while (true) {
        flag = false;
        i = 1;
        cin >> x >> y;
        if (x == 0 && y == 0) break;
        rectangle = rectangles[x][y];
         
        for (int k = 1; k < 150; k++) {
            for (int j = k+1; j <= 150; j++) {
                if (rectangle == rectangles[k][j]) {
                    if (x < k) {
                        ansx = k;
                        ansy = j;
                        flag = true;
                        break;
                    }
                }
            }
            if(flag) break;
        }
         
         
         
        while(!flag) {
            rectangle++;
            for (int k = 1; k < 150; k++) {
                for (int j = k+1; j <= 150; j++) {
                    if (rectangle == rectangles[k][j]) {
                        ansx = k;
                        ansy = j;
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }
            if(flag) break;
        }
         
        cout << ansx << " " << ansy << endl;
    }
     
    return 0;
}

Measured memory_bytes: 1256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int[] i = {s.nextInt(), s.nextInt(), s.nextInt()};
        java.util.Arrays.sort(i);
        System.out.printf("%d %d %d\n", i[0], i[1], i[2]);
    }
}

Measured memory_bytes: 17316
// Copyright 2020 yaito3014
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  string S;
  int Q;
  cin >> S;
  cin >> Q;
  bool rev = false;
  deque<char> que(begin(S),end(S));
  for (int i = 0; i < Q; ++i) {
    int T;
    cin >> T;
    if (T == 1)rev = !rev;
    else if (T == 2) {
      int F;
      char C;
      cin >> F >> C;
      if (rev)F = 3 - F;
      if (F == 1)que.push_front(C);
      else if (F == 2)que.push_back(C);
    }
  }
  if (rev)reverse(begin(que), end(que));
  for (auto& e : que)cout << e;
  cout << endl;
}


Measured memory_bytes: 976
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 1e6 + 10;
bool flag[N];

void gen_prime() {
  flag[0] = flag[1] = true;
  for (int i = 2; i < N; ++i) {
    if (flag[i]) continue;
    for (int j = i + i; j < N; j += i) {
      flag[j] = true;
    }
  }
}

int dp[N];
int main() {
  gen_prime();
  for (int i = 1; i < N; ++i) {
    dp[i] = dp[i - 1] + (!flag[i] && !flag[(i + 1) / 2]);
  }
  int cas;
  scanf("%d", &cas);
  while (cas--) {
    int L, R;
    scanf("%d%d", &L, &R);
    printf("%d\n", dp[R] - dp[L - 1]);
  }
  return 0;
}


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

int main(){
int a,b;
char op;
while(1){
cin>>a>>op>>b;
if(op=='?') break;
else if(op=='+') cout<<a+b<<endl;
else if(op=='-') cout<<a-b<<endl;
else if(op=='*') cout<<a*b<<endl;
else if(op=='/') cout<<a/b<<endl;
else break;
}
}

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

int main() {
  int N; 
  cin >> N;
  std::vector<long> a(3 * N, 0);
  for(int i = 0; i < 3 * N ; i++) cin >> a.at(i); 
  
  std::sort(a.begin(), a.end());
  long sum(0);
  
  for(int i = 0; i < N; i++)
  {
   sum += a.at(3 * N - 1 - 1 - 2 * i); 
  }
  cout << sum << endl;
}


Measured memory_bytes: 2688
package main

import (
	"fmt"
	"math"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	sum := 0.0
	for i := 1; i < n+1; i++ {
		count := 0
		for j := i; j < k; {
			j *= 2
			count++
		}
		sum += 1 / float64(n) / math.Pow(float64(2), float64(count))
	}

	fmt.Println(sum)
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
int main() {
	int h,w,n;
	cin >> h >> w >> n;
	int x, y;
	cin >> x >> y;
	int sum = 0;
	for (int i = 1; i < n; i++) {
		int c, d;
		cin >> c >> d;
		while (c - x > 0 && d - y > 0 && x + 1 <= h && y + 1 <= w) {
			sum++;
			x++;
			y++;
		}
		while (x - c > 0 && y - d > 0 && y - 1 > 0 && x - 1 > 0) {
			sum++;
			x--;
			y--;
		}
		int e = y - d;
		if (e < 0) e = 0 - e;
		sum += e;
		e = x - c;
		if (e < 0) e = 0 - e;
		sum += e;
		x = c;
		y = d;
	}
	cout << sum << endl;
}

Measured memory_bytes: 3076
S = input()
T = input()

for i in range(len(S) - len(T),-1,-1):
  for j in range(len(T)):
    if S[j + i] != "?" and S[j + i] != T[j]:
      break
  else:
    S = S.replace("?","a")
    print(S[:i] + T + S[i + len(T):])
    break
else:
  print("UNRESTORABLE")

Measured memory_bytes: 3060
import java.util.Scanner;

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

        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int a4Cnt = 0;
            int a2Cnt = 0;
            int a1Cnt = 0;
            for (int i = 0; i < n; i++) {
                int a = sc.nextInt();
                if ( a % 4 == 0 ) {
                    a4Cnt++;
                } else if ( a % 2 == 0 ) {
                    a2Cnt++;
                } else {
                    a1Cnt++;
                }
            }

            a1Cnt += a2Cnt % 2;

            if ( a1Cnt > a4Cnt + 1 ) {
                System.out.println("No");
            } else {
                System.out.println("Yes");
            }
        }
    }
}


Measured memory_bytes: 47100
#include<iostream>
#include<unordered_map>
#include<bitset>
#include<math.h>
#include<vector>
#include<set>
#include<algorithm>
#include<ctype.h>
#include<unordered_set>
#include<string>
#include<iomanip>
#include<queue>
#include<limits>
#include<map>
#include<stack>
#include<iterator>
#include<cstring>
 
#include<deque>
#define pi 3.141592653589793238
#include<chrono>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
 
#define mt make_tuple
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll T = 1, i, j;
    
    //cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        vector<ll> v(n);
        ll ans = 0;
        for(i = 0; i < n; i++){
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        for(i = 0;i < n ;i++){
            for(j = i + 1; j < n; j++){
                for(ll k = j + 1; k < n; k++){
                    if(v[i] < v[j] && v[j] < v[k])
                        if(v[i] + v[j] > v[k]){
                            ans++;
                        }
                }
            }
        }
        cout << ans;
    }
    return 0;
}

Measured memory_bytes: 3604
import java.util.Scanner;

public class Main {
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		int y = scan.nextInt();
		int box = 0;
		while(x != 0 || y != 0)
		{
			if(x > y)
			{
				box = x;
				x = y;
				y = box;
			}
			System.out.println(x + " " + y);
			x = scan.nextInt();
			y = scan.nextInt();
		}
	}
}

Measured memory_bytes: 26584
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    ll A,B,C,D; cin >> A >> B >> C >> D;
    while(true){
        C -= B;
        if(C <= 0) return "Yes";
        A -= D;
        if(A <= 0) return "No";
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<string>() << endl;
    return 0;
}


Measured memory_bytes: 3612
#include <iostream>
#include <set>

int main() {
  size_t N;

  std::cin >> N;

  std::multiset<size_t> A;

  for (size_t i=0; i<N; i++) {
    size_t a;
    std::cin >> a;
    A.insert(a);
  }

  size_t ans=0;

  while (A.size() > 1) {
    auto const max = *std::prev(A.end());
    A.erase(std::prev(A.end()));

    for (size_t sum=0x80000000; sum>1; sum>>=1) {
      if (max >= sum) break;

      auto it_tgt = A.lower_bound(sum - max);

      if (it_tgt == A.end()) continue;

      std::cerr << sum << ' '
                << max << ' '
                << *it_tgt << std::endl;

      if (*it_tgt + max == sum) {
        ans++;
        A.erase(it_tgt);
      }
    }
  }

  std::cout << ans << std::endl;

  return 0;
}


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

int main(){
    int n,k;
    cin >> n >> k;
    int num;
    for(int i=0; i<n; i++){
        cin >> num;
    }

    int ans;
    if((n-1)%(k-1)==0) ans=(n-1)/(k-1);
    else{
        ans=(n-1)/(k-1);
        ans++;
    }
    cout << ans << endl;
}

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

int main() {
    int N; cin >> N;
    int n = N % 10;
    if(n == 3){
        cout << "bon" << endl;
    } else if (n == 0 || n == 1 || n == 6 || n == 8){
        cout << "pon" << endl;
    } else {
        cout << "hon" << endl;
    }
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<< endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(ll, N, M);
  vector<pair<ll, ll>> P(N);
  each(x, P) in(x.first, x.second);
  sort(all(P));
  ll ans = 0;
  rep(i, 0, N) {
    ll cnt = min(M, P[i].second);
    ans += P[i].first * cnt;
    M -= cnt;
    if (M == 0) {
      break;
    }
  }
  print(ans);
}


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

class Main{
    public static void main(String[] args){
	BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
	try {
	    int n = Integer.valueOf(sc.readLine());
	    for(int i=0; i<n; i++){
		int up=0, down=0, k = Integer.valueOf(sc.readLine());
		String[] sp = sc.readLine().split(" ");
		int[] map = new int[k];
		for(int j=0; j<k; j++)
		    map[j] = Integer.valueOf(sp[j]);
		for(int j=0; j<k-1; j++){
		    int dif = map[j+1]-map[j];
		    if(dif>up) up = dif;
		    if(dif+down<0) down = 0-dif;
		}
		System.out.println(up+" "+down);
	    }
	}catch(Exception e){
	    System.out.println("Error");
	}
    }
}

Measured memory_bytes: 22464
#include <iostream>
#include <string>
using namespace std;
int main(){
    char a[5] = {'a', 'e', 'i', 'o', 'u',};
    char c; cin >> c;
    for(int i = 0; i < 5; i++){
        if(c == a[i]){
            puts("vowel");
            return 0;
        }
    }
    puts("consonant");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n), ans(n * n, -1);
    vector<P> d; 
    rep(i, 0, n){
        cin >> a[i]; a[i]--;
        ans[a[i]] = i + 1;
        d.push_back(P(a[i], i + 1));
    }
    sort(all(d));
    bool f = true;
    rep(i, 0, n){
        int cnt = d[i].second - 1;
        rep(j, 0, d[i].first){
            if(cnt == 0) break;            
            if(ans[j] == -1){
                cnt--;
                ans[j] = d[i].second;
            }
        }
        if(cnt != 0) f = false;
    }
    reverse(all(d));
    rep(i, 0, n){
        int cnt = n - d[i].second;
        repb(j, n * n - 1, d[i].first + 1){
            if(cnt == 0) break;            
            if(ans[j] == -1){
                cnt--;
                ans[j] = d[i].second;
            }
        }
        if(cnt != 0) f = false;
    }
    if(!f) cout << "No" << endl;
    else{
        cout << "Yes" << endl;
        for(int ii = 0; ii < ans.size(); ii++){
            if(ii) cout << ' ';
            cout << ans[ii];
        }
        cout << endl;
    }
}

Measured memory_bytes: 3200
import math
n=int(input())
sum=0
l=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n):
        sum+=math.sqrt((l[i][0]-l[j][0])**2+(l[i][1]-l[j][1])**2)
sum=sum/n
print(sum)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &&x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N;
    cin >> N;
    const double BTC = 380000;
    double ans = 0;
    REP(i, N) {
        double x;
        string u;
        cin >> x >> u;
        if (u == "BTC") ans += x * BTC;
        else ans += x;
    }
    cout << ans << endl;
    return (0^_^0);
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define oo 666666666
#define ll long long
#define ld long double

int n;
vector<int>g[100001];
ll mod = 1e9+7;
ll DP[100001][2];

ll solve(int c, int col, int p)
{
    if(DP[c][col]!=-1)return DP[c][col];
    DP[c][col]=1;
    for(auto&u:g[c])
        if(u!=p)
    {
        if(col==1)
        {
            DP[c][col]*=solve(u,0,c);
            DP[c][col]%=mod;
        }
        else
        {
            DP[c][col]*=(solve(u,0,c)+solve(u,1,c));
            DP[c][col]%=mod;
        }
    }
    return DP[c][col];
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    memset(DP, -1, sizeof DP);
    for(int i=1; i<n; i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    cout<<(solve(1,0,-1) + solve(1,1,-1))%mod;
}


Measured memory_bytes: 15616
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    long A = scan.nextLong();
    long B = scan.nextLong();
    scan.close();

    if(12.5*A < 10*(B+1) && 10*B < 12.5*(A+1)) {
      System.out.println(String.format("%.0f", 12.5*A < 10*B ? 10*B : 12.5*A));
    }
    else {
      System.out.println(-1);
    }
  }
}

Measured memory_bytes: 23764
#include<stdio.h>
#include<stdbool.h>

#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N],col[N],dpos[2*N-1],dneg[2*N-1];

bool X[N][N];

void initialize(){
    int i;
    for(i = 0; i < N; i++){
        row[i] FREE;
        col[i] = FREE;
    }
    for(i = 0; i < 2*N-1; i++){
        dpos[i] = FREE;
        dneg[i] = FREE;
    }
}

void printBoard(){
    int i,j;
    for(i = 0; i < N; i++){
        for(j = 0; j < N; j++){
            if(X[i][j]){
                if(row[i] != j) return;
            }
        }
    }
    for(i = 0; i < N; i++){
        for(j = 0; j < N; j++){
            printf("%s",row[i] == j ? "Q" : ".");
        }
        printf("\n");
    }
}

void recursive(int i){
    int j;
    if(i == N){
        printBoard();
        return;
    }

    for(j = 0;j < N; j++){
        if(NOT_FREE == col[j] || NOT_FREE == dpos[i+j] || NOT_FREE == dneg[i-j+N-1]) continue;
        row[i] = j;
        col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
        recursive(i+1);
        row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
    }
}

int main(){
    int i,j,k,r,c;
    initialize();

    for(i = 0; i < N; i++){
        for(j =0; j < N; j++) X[i][j] = false;
    }

    scanf("%d",&k);
    for(i = 0; i < k; i++){
        scanf("%d%d",&r,&c);
        X[r][c] = true;
    }

    recursive(0);

    return 0;
}


Measured memory_bytes: 2112
#include<bits/stdc++.h>
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define MOD 1000000007
#define INF 1e9
#define F first
#define S second
#define All(x) (x).begin(),(x).end()
using namespace std;
const double PI = acos(-1);
typedef long long ll;

template <class T>
class SegTree{
    int n; //葉の数(要素数)
    vector<T> data; //データ格納用
    T def; //初期値で単位元
    function<T(T,T)> operation; //区間クエリ使用
    function<T(T,T)> update; //点更新で使用

    //区間[a,b)の総和
    T _query(int a,int b,int k,int l,int r){
        if(r<=a||b<=l)return def; //範囲外だから
        if(a<=l&&r<=b)
            return data[k]; //a,l,r,bで完全に含まれる
        else {
            T c1=_query(a,b,2*k+1,l,(l+r)/2); //左の子
            T c2=_query(a,b,2*k+2,(l+r)/2,r); //右の子
            return operation(c1,c2);
        }
    }

  public:
    // _n:必要サイズ, _def:初期値かつ単位元, _operation:クエリ関数,
    // _update:更新関数
    SegTree(size_t _n,T _def,function<T(T,T)> _operation,function<T(T,T)> _update)
        :  def(_def),operation(_operation),update(_update){
            n=1;
            while(n<_n){
                n*=2;
            }
            data=vector<T>(2*n-1,def);
    }

    // 場所i(0-indexed)の値をxで更新
    void change(int i,T x){
        i+=n-1;
        data[i]=update(data[i],x);
        while(i>0){
            i=(i-1)/2;
            data[i]=operation(data[i*2+1],data[i*2+2]);
        }
    }

    //[a,b)の区間クエリを実行
    T query(int a,int b){
        return _query(a,b,0,0,n);
    }

    T operator[](int i){
        return data[i+n-1];
    }
};

int main(void){
  int N,Q;
  cin>>N>>Q;
  SegTree<ll> st(N,0,
                 [](ll a,ll b){return a+b;},
                 [](ll a,ll b){return a+b;});
  
  REP(i,Q){
    int c,x,y;
    cin>>c>>x>>y;
    if(c==0)st.change(x-1,y);
    else cout<<st.query(x-1,y)<<endl;
    //cout<<st[x-1]<<endl;
  }

  return 0;
}


Measured memory_bytes: 4976
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

class Solver {
    Scanner sc = new Scanner();

    public void Solve() {
        var N = sc.nextInt();
        var s = new string[N];
        for (int i = 0; i < N; i++) {
            s[i] = sc.next();
            var tmp = s[i].ToCharArray();
            Array.Sort(tmp);
            s[i] = new String(tmp);
        }
        var dic = new Dictionary<string, long>();

        for (int i = 0; i < N; i++) {
            if (dic.ContainsKey(s[i])) {
                dic[s[i]]++;
            } else {
                dic.Add(s[i], 1);
            }
        }

        var ans = 0L;
        foreach (var kvs in dic) {
            if (kvs.Value != 1) {
                ans += Combination.Calc(kvs.Value, 2);
            }
        }
        WriteLine(ans);
    }
    
}

class Combination {
    public static long Calc(long a, long b) {
        if (b > a - b) return Calc(a, a - b);

        long ansMul = 1;
        long ansDiv = 1;
        for (int i = 0; i < b; i++) {
            ansMul *= (a - i);
            ansDiv *= (i + 1);
        }

        return ansMul / ansDiv;
    }
}

class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}


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

int main()
{
    std::cout<<std::fixed<<std::setprecision(10);
    
    double N;
    cin >> N;
    
    vector<int> answers = vector<int>(101, 0);
    
    for (int i = 0; i < N; i++) {
        int X;
        cin >> X;
        for (int x = 0; x <= 100; x++) {
            answers[x] += (X - x) * (X - x);
        }
    }
    
    sort(answers.begin(), answers.end());

    cout << answers[0] << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int tm,n;
  while(cin >> tm,tm){
    int i,j,k;
    int t[tm];
    for(i=0;i<tm;i++) cin >> t[i];
    cin >> n;
    int m[150]={};
    fill(m,m+150,24);
    for(i=1;i<=n;i++){
      cin >> k;
      cin >> j;
      m[k]=min(m[k],j);
    }
    int inf = 1<<20;
    int dp[150][50];
    fill(dp[0],dp[149],inf);
    dp[1][0]=0;
    for(i=1;i<=100;i++){
      for(j=0;j<50;j++){
	if(dp[i][j]==inf) continue;
	dp[i+1][0]=min(dp[i+1][0],dp[i][j]+1);
	//cout <<i<<":"<<j<<":"<< t[(j+1)%tm]<<":"<<m[i]<<endl;
	if(t[(j+1)%tm]<=m[i+1]){
	  dp[i+1][(j+1)%tm]=min(dp[i+1][(j+1)%tm],dp[i][j]);
	}
      }
    }
    int o=inf;
    /*
    for(j=1;j<=n+10;j++){
      cout << j << ":";
      for(i=0;i<tm;i++) cout << dp[j][i] << (i==tm-1?"\n":" ");
    }
    */
    for(i=0;i<50;i++) o=min(o,dp[101][i]);
    cout << o << endl;
  }
  return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    string temp;
    int ac=0;
    int wa=0;
    int tle=0;
    int re=0;
    for(int i=0;i<N;i++){
        cin>>temp;
        if(temp=="AC")ac++;
        if(temp=="WA")wa++;
        if(temp=="TLE")tle++;
        if(temp=="RE")re++;
    }
    cout<<"AC x "<<ac<<endl;
    cout<<"WA x "<<wa<<endl;
    cout<<"TLE x "<<tle<<endl;
    cout<<"RE x "<<re<<endl;
    return 0;
}


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

using namespace std;

int main(void)
{
        string S;
        cin >> S;
        int length = S.size();

        if(S[0]==S[length-1])
        {
                if(length%2==0)
                {
                        cout << "First" << endl;
                        return 0;
                }
                else
                {
                        cout << "Second" << endl;
                        return 0;
                }
        }
        else
        {
                if(length%2==0)
                {
                        cout << "Second" << endl;
                        return 0;
                }
                else
                {
                        cout << "First" << endl;
                        return 0;
                }
        }
}


Measured memory_bytes: 512
#include <iostream>
#include <cctype>
#include <vector>

int main(void){
  std::string str;
  std::vector<int> vec(26,0);
  while(std::cin>>str){
    for(int i=0;i<str.size();i++){
      if(std::isupper(str[i])) str[i]=std::tolower(str[i]);
      if('a'>str[i]||'z'<str[i]) continue;
      int order=str[i]-'a';
      vec.at(order)++;
    }
  }
  for(int i=0;i<26;i++){
    std::cout<<(char)('a'+i)<<" "<<":"<<" "<<vec.at(i)<<std::endl;
  }
  return 0;
}



Measured memory_bytes: 3172
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

using namespace std;

//----------------------- Print Function ----------------------//

inline void print() {
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest) {
    cout << first << ' ';
    print(rest...);
}

template <typename T>
void print(const vector<T> &v) {
    for (auto e : v) cout << e << ' ';
    cout << endl;
}

//------------------------- Libraries -------------------------//

vector<int> ZAlgo(const string &s) {
    vector<int> Z(s.size());
    Z[0] = s.size();
    int i = 1, j = 0;
    while(i < s.size()) {
        while (i + j < s.size() && s[j] == s[i + j]) j++;
        Z[i] = j;

        if (j == 0) {
            i++;
            continue;
        }
        int k = 1;
        while (k < j && k + Z[k] < j) {
            Z[i + k] = Z[k];
            k++;
        }
        i += k;
        j -= k;
    }
    return Z;
}

//--------------------------- Solve ---------------------------//

void solve() {
    int N; cin >> N;
    string s; cin >> s;
    int ans = 0;
    for (int i = 1; i <= N; i++) {
        string tmp;
        for (int j = N-i; j < N; j++) tmp += s[j];

        vector<int> z = ZAlgo(tmp);
        for (int j = 0; j < i; j++) {
            if (j >= z[j]) ans = max(ans, z[j]);
        }
    }

    cout << ans << '\n';
}

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

    solve();

    return 0;
}

Measured memory_bytes: 3732
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		Integer a=scanner.nextInt();
		String str=scanner.next();
		if(a<3200) {
			System.out.println("red");
		}else {
			System.out.println(str);
		}
		
	}
}


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

int main() {
  int n;
  cin>>n;
  string a,b;
  cin>>a>>b;
  rep(i,n){
    cout<<a[i]<<b[i];
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
struct ST
{
  int c;
  int v[15];
};
ST b[15];
int a[15];
int n, m, x;
int f = 0;
bool judge()
{
    for(int i = 0; i < m; i++)
        if(a[i] < x)
            return false;
    return true;
}
void dfs(int sum, int up, int t)
{
    if(f == 1)
        return;
    if(sum > up)
        return;
    if(judge())
    {
        f = 1;
        return;
    }
    if(t >= n)
        return;
    dfs(sum, up, t + 1);
    if(sum + b[t].c > up)
        return;
    for(int i = 0; i < m; i++)
        a[i] += b[t].v[i];
    dfs(sum + b[t].c, up, t + 1);
    for(int i = 0; i < m; i++)
        a[i] -= b[t].v[i];
}
int main()
{

    cin >> n >> m >>x;
    int L = 0, R = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> b[i].c;
        R += b[i].c;
        for(int j = 0; j < m; j++)
            cin >> b[i].v[j];
    }
    int mid = 0;
    int ans = -1;
    while(L <= R)
    {
        mid = L + (R - L) / 2;
        f = 0;
        dfs(0, mid, 0);
        if(f == 1)
        {
            ans = mid;
            R = mid - 1;
        }
        else
            L = mid + 1;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>

int powK(int num1, int num2) {
    int ans = 1;

    for (int i = 0; i < num2; i++) {
        ans = ans * num1;
    }

    return ans;
}

void makeBinaryNum(int num, int digit, int array[digit]) {
    int copiedNum = num;

    for (int i = digit - 1; i >= 0; i--) {
        if (powK(2, i) <= copiedNum) {
            array[i] = 1;
            copiedNum -= powK(2, i);
        } else {
            array[i] = 0;
        }
    }
}

int main(void) {
    // 条件の読み込み
    int h;
    int w;
    int k;
    scanf("%d %d %d", &h,&w,&k);

    // マス目の読み込み  '.' -> 0  '#' -> 1
    int matrix[w][h];
    for (int y = 0; y < h; y++) {
        char str[256];
        scanf("%s", str);
        for (int x = 0; x < w; x++) {
            matrix[x][y] = str[x] == '#';
        }
    }

    int ans = 0;

    //チェック
    for (int numY = 0; numY < powK(2, h); numY++) {
        int binaryY[h];
        makeBinaryNum(numY, h, binaryY);

        for (int numX = 0; numX < powK(2, w); numX++) {
            int binaryX[w];
            makeBinaryNum(numX, w, binaryX);

            int result = 0;
            for (int y = 0; y < h; y++) {
                for (int x = 0; x < w; x++) {
                    result += matrix[x][y] && binaryX[x] && binaryY[y];
                }
            }

            ans += result == k;
        }
    }

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


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


int N, A[200000], best = 0, second_best = 0;

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i];
        if(A[i] > best){
            second_best = best;
            best = A[i];
        }else if(A[i] > second_best){
            second_best = A[i];
        }
    }
    for(int i = 0; i < N; i++){
        if(A[i] != best){
            cout << best << endl;
        }else{
            cout << second_best << endl;
        }
    }
}


Measured memory_bytes: 2432
//FUCKED UP FUCKED‌ UP FUCKED UP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e3+10,mod=1e9+7;

ll n,m,dp[maxn][maxn][2];
inline void add(ll&x,ll y){x+=y;if(x>=mod)x-=mod;}

int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	dp[0][0][1]=1;
	for(int i=1;i<=n;++i)dp[0][i][0]=1;
	for(int i=0;i<m;++i)for(int j=0;j<=n;++j)for(int k=0;k<2;++k){
		if(!dp[i][j][k]) continue;
		if(j) add(dp[i+1][j-1][k|(j==1)],dp[i][j][k]),add(dp[i+1][j][k|(j==1)],dp[i][j][k]);
		if(n-j) add(dp[i+1][j][k],dp[i][j][k]),add(dp[i+1][j+1][k],dp[i][j][k]);
	}
	ll ans=0;
	for(int i=0;i<=n;++i) add(ans,dp[m][i][1]);
	cout<<ans<<'\n';
}


Measured memory_bytes: 144680
N, M = map(int, input().split())
student = [tuple(map(int, input().split())) for _ in range(N)]
checkpoint = [tuple(map(int, input().split())) for _ in range(M)]

closest = {}
for s in student:
    min_dist = 'INF'
    ans = 1
    for c in checkpoint:
        dist = abs(s[0]-c[0]) + abs(s[1]-c[1])
        if min_dist == 'INF' or dist < min_dist:
            min_dist = dist
            closest[s] = ans
        ans += 1

for s in student:
    print(closest[s])
            

Measured memory_bytes: 9220
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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;}


int main() {
  int n, t;
  cin >> n >> t;
  long ans = 0;
  long last = 0;
  rep (i, n) {
    int tmp;
    cin >> tmp;
    ans += t;
    if (last > tmp) ans -= (last - tmp);
    last = t + tmp;
    // P(ans);
  }
  P(ans);
  return 0;
}

Measured memory_bytes: 256
N = int(input())
p = [int(x) for x in input().split()]

ans = 0
for i in range(N) :
    if p[i] == i+1 :
        if i == N-1 :
            p[i], p[i-1] = p[i-1], p[i]
            ans += 1
        else :
            p[i], p[i+1] = p[i+1], p[i]
            ans += 1

print(ans)


Measured memory_bytes: 13880
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)

int main() {
	ll N; cin >> N;
	string s[100];
	map<string, int>mp;
	rep(i, 0, N) {
		cin >> s[i];
		mp[s[i]]++;
	}
	ll M; cin >> M;
	string t[100];

	rep(i, 0, M) {
		cin >> t[i];
		mp[t[i]]--;
	}
	ll minV = 0;
	for (map<string, int>::iterator it = mp.begin(); it != mp.end(); it++) {
		minV = max((ll)minV, (ll)it->second);
	}
	cout << (minV < 0 ? 0 : minV) << endl;

	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;
using Graph = vector<vector<ll>>;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {
    ll N;
    cin >> N;
    ll A[N+1];
    rep(i,N+1) A[i] = 0;
    rep(i,100){
        rep(j,100){
            rep(k,100){
                ll n = (i+1)*(i+1) + (j+1)*(j+1) + (k+1)*(k+1) + (i+1)*(j+1) + (j+1)*(k+1) + (k+1)*(i+1);
                if(n<=N) A[n]++;
            }
        }
    }
    rep(i,N){
        cout << A[i+1] << endl;
    }
    return 0;
}



Measured memory_bytes: 3660
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

#define N 201000
#define ll long long
#define RG register

inline int read(){
    RG int x=0,o=1; RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=((x<<3)+(x<<1))+ch-'0',ch=getchar();
    return x*o;
}

int n,Q,A,B,lst;

#define ls (now<<1)
#define rs ((now<<1)|1)
ll sa[N<<2],sb[N<<2],rem,Min;
inline void Modify(int l,int r,int now,int pos,ll val){
	if(l==r) { sa[now]=min(sa[now],val-l),sb[now]=min(sb[now],val+l); return ; }
	int mid=l+r>>1;
	if(pos<=mid) Modify(l,mid,ls,pos,val);
	else Modify(mid+1,r,rs,pos,val);
	sa[now]=min(sa[ls],sa[rs]),sb[now]=min(sb[ls],sb[rs]);
}
inline ll Query(int l,int r,int now,int L,int R,int op){
	if(L<=l&&r<=R) return (!op)?sa[now]:sb[now];
	int mid=l+r>>1; ll ans=1e18;
	if(L<=mid) ans=min(ans,Query(l,mid,ls,L,R,op));
	if(R>mid) ans=min(ans,Query(mid+1,r,rs,L,R,op)); return ans;
}
inline void Build(int l,int r,int now){
	if(l==r) { sa[now]=1e12,sb[now]=1e12; return ; }
	int mid=l+r>>1; Build(l,mid,ls),Build(mid+1,r,rs);
	sa[now]=min(sa[ls],sa[rs]),sb[now]=min(sb[ls],sb[rs]);
}

int main(){
	n=read(),Q=read(),A=lst=read(),B=read(),Build(1,n,1),Modify(1,n,1,B,0);
	for(RG int i=1;i<=Q;++i){
		int x=read(); ll now=min(Query(1,n,1,1,x,0)+x,Query(1,n,1,x,n,1)-x)+rem;
		if(i==Q) { printf("%lld\n",min(now,Min+rem+abs(x-lst))); return 0; }
		rem+=abs(x-lst),Modify(1,n,1,lst,now-rem),Min=min(Min,now-rem),lst=x;
	}
}


Measured memory_bytes: 12672
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

constexpr ll INF = 1e15;

//1点更新,区間最小
class SegmentTree {
public:
    SegmentTree(ll n, ll value) {
        n_ = (ll)pow(2, ceil(log2(n)));
        nodes_.resize(2 * n_ - 1, value);
    }
    void update(ll x, ll v) {
        nodes_[x + n_ - 1] = min(nodes_[x + n_ - 1], v);
        for (ll i = (x + n_ - 2) / 2; ; i = (i - 1) / 2) {
            nodes_[i] = min(nodes_[2 * i + 1], nodes_[2 * i + 2]);
            if (i == 0) {
                break;
            }
        }
    }

    ll getMin(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) {
            r = n_;
        }
        if (r <= a || b <= l) {
            return INF;
        }
        if (a <= l && r <= b) {
            return nodes_[k];
        }
        ll lv = getMin(a, b, 2 * k + 1, l, (l + r) / 2);
        ll rv = getMin(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(lv, rv);
    }

private:
    //2のべき乗
    ll n_;
    vector<ll> nodes_;
};

int main() {
    ll N, M;
    cin >> N >> M;
    struct Edge {
        ll L, R, C;
    };
    vector<Edge> edges(M);
    for (ll i = 0; i < M; i++) {
        cin >> edges[i].L >> edges[i].R >> edges[i].C;
        edges[i].L--;
        edges[i].R--;
    }
    sort(edges.begin(), edges.end(), [](const Edge& lhs, const Edge& rhs){
        return lhs.L < rhs.L;
    });

    SegmentTree st(N, INF);
    ll edge_index = 0;
    for (ll i = 0; i < N - 1; i++) {
        //iから右に伸ばす
        ll curr_cost = (i == 0 ? 0 : st.getMin(i, N));

        while (edges[edge_index].L == i) {
            st.update(edges[edge_index].R, curr_cost + edges[edge_index].C);
            edge_index++;
        }
    }

    ll ans = st.getMin(N - 1, N);
    cout << (ans == INF ? -1 : ans) << endl;
}

Measured memory_bytes: 4608
import sys
input = sys.stdin.readline
N = int(input())
A = tuple(map(int,input().split()))
Q = int(input())
cnt = [0]*100005
s = sum(A)
for i in A:
    cnt[i] += 1
for i in range(Q):
    B, C = map(int,input().split())
    s += (C-B)*cnt[B]
    print(s)
    cnt[C] += cnt[B]
    cnt[B] = 0

Measured memory_bytes: 20684