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

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int> ;
using vl = vector<ll>;

int state[1 << 13];

int main(){
    int n,m;
    cin >> n >> m;
    int INF = 1e9;
    rep(i,1<<13){
        state[i] = INF;
    }
    state[0] = 0;
    int a,b;
    int c,pos;
    rep(i,m){
        cin >> a >> b;
        c = 0;
        rep(j,b){
            cin >> pos;
            pos--;
            c += (1 << pos);
        }
        rep(i,1<<n){
            state[i|c] = min(state[i | c],state[i]+a);
        }
    }
    if(state[(1<<n)-1] == INF){
        cout << -1 << endl;
        return 0;
    }
    
    cout << state[(1<<n)-1] << endl;
    return 0;
}

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

#define ll long long

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    
    
    int n;
    cin>>n;
    
    int cost[n+1];
    bool reachable[n+1];
    int total[n+1];
    
    for(int i = 1;i <= n; i++){
        cin>>cost[i];
        reachable[i] = false;
        total[i] = INT_MAX;
    }
    
    total[1] = 0;
    
    reachable[1] = true;
    for(int i = 1; i <= n; i++){
        if(!reachable[i])
        continue;
        if( (i+1) <= n){
            reachable[i+1] = true;
            total[i+1] = min(total[i+1], total[i] + abs(cost[i+1] - cost[i]));
        }
        
        if( (i+2) <= n){
            reachable[i+2] = true;    
            total[i+2] = min(total[i+2], total[i] + abs(cost[i+2]-cost[i]));
        }
        
    }
    
    
    cout<<total[n]<<endl;
    
    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <iterator>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <regex>
using namespace std;
using pii  = pair<int,int>;
using ll=long long;
using ld=long double;
#define pb push_back
#define mp make_pair
#define sc second
#define fr first
#define stpr setprecision
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define rep(i,n) for(ll i=0;i<(n);++i)
#define Rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define rRep(i,a,b) for(int i=a;i>=b;i--)
#define crep(i) for(char i='a';i<='z';++i)
#define psortsecond(A,N) sort(A,A+N,[](const pii &a, const pii &b){return a.second<b.second;});
#define ALL(x) (x).begin(),(x).end()
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define endl '\n'
int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}
ll gcd(ll a,ll b){return (b == 0 ? a : gcd(b, a%b));}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll MOD=1000000007;
constexpr ll INF=1000000011;
constexpr ll MOD2=998244353;
constexpr ll LINF = 1001002003004005006ll;
constexpr ld EPS=10e-8;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T> istream& operator>>(istream& is,vector<T>& v){for(auto&& x:v)is >> x;return is;}
template<typename T,typename U> istream& operator>>(istream& is, pair<T,U>& p){ is >> p.first; is >> p.second; return is;}
template<typename T,typename U> ostream& operator>>(ostream& os, const pair<T,U>& p){ os << p.first << ' ' << p.second; return os;}
template<class T> ostream& operator<<(ostream& os, vector<T>& v){
  for(auto i=begin(v); i != end(v); ++i){
    if(i !=begin(v)) os << ' ';
    os << *i;
  }
  return os;
}

int main(){
  ll N;
  cin >> N;
  ll A[200007];
  ll K=1;
  rep(i,N){
    cin >> A[i];
    if(A[i]==K){
      K++;
    }
  }
  if(K==1){
    cout << -1 <<  endl;
  }
  else{
    cout << N-K+1 << endl;
  }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char inp[200010];
ll numblacks[200010];
int n;
ll ans;
int main()
{
	scanf(" %s", inp);
	n = strlen(inp);
	for (int i = 0; i < n; i++)
	{
		if (inp[i] == 'B') numblacks[i]++;
		else ans += numblacks[i];
		numblacks[i+1] += numblacks[i];
	}
	printf("%lld\n", ans);
}

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

int main(){
    string S;
    cin>>S;
    if (S[0]==S[1]&&S[1]==S[2]){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
/* BISMILLAHIR RAHMANIR RAHIM */
#include<bits/stdc++.h>
using namespace std;
#define ll        long long
#define ull       unsigned long long
#define sd(x)     scanf("%lf", &x)
#define l0(i,n)   for(ll i=0; i<n; i++)
#define MAX       100005
#define maxn 	  200002
#define pb 		  push_back
#define mk 		  make_pair
#define endl	  "\n"
#define INF 	  1000000000
#define MOD		  1000000007
#define imie(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "


int main ()
{
		ios::sync_with_stdio(0);
		cin.tie(0);
		//CODE TONOY
		int n,r;
		scanf("%d%d",&n,&r);
		if (n<10)
		{
			int jog = 100*(10-n);
			printf("%d",r+jog);
			return 0;
		}
		printf("%d",r);
		return 0;
}  


Measured memory_bytes: 3784
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

static const int MAX = 10000;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;
static const int INFTY = (1 << 30);

int n;
vector< pair<int,int> > adj[MAX];

void dijkstra()
{
	priority_queue< pair<int, int> > PQ;
	int color[MAX];
	int d[MAX];
	for(int i=0; i<n; i++)
	{
		d[i] = INFTY;
		color[i] = WHITE;
	}

	d[0] = 0;
	PQ.push(make_pair(0,0));
	color[0] = GRAY;

	while(!PQ.empty())
	{
		pair<int, int> f = PQ.top();
		PQ.pop();
		int u = f.second;
		color[u] = BLACK;

		if(d[u] < f.first * (-1)) continue;

		for(int j=0; j<adj[u].size(); j++)
		{
			int v = adj[u][j].first;
			if(color[v] == BLACK) continue;
			if(d[v] > d[u] + adj[u][j].second)
			{
				d[v] = d[u] + adj[u][j].second;
				PQ.push(make_pair(d[v]*(-1), v));
				color[v] = GRAY;
			}
		}
	}

	for(int i=0; i<n; i++)
	{
		printf("%d %d\n",i,d[i]==INFTY ? -1:d[i]);
	}
}

int main()
{
	int k,u,v,c;

	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		scanf("%d%d", &u, &k);
		for(int j=0; j<k; j++)
		{
			scanf("%d%d", &v, &c);
			adj[u].push_back(make_pair(v,c));
		}
	}

	dijkstra();

	return 0;
}


Measured memory_bytes: 7632
#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    Edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<Edge>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reprep(i,j,w,h) rep(j,h)rep(i,w)
#define rrep(i,m, n) for(int i = m; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> a(n);rep(i,n)std::cin >> a[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sum accumulate
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<int>(n,a)));
typedef long long ll;
const int INF = 2000000000;
const long INF64 = 1000000000000000ll;
const ll MOD = 1000000007LL;
typedef unsigned int uint;
long ggd(long a, long b) {//最小公倍数，最大公約数
	if(a<b)swap(a,b);
	if (b == 0) {
		return a;			
	}
	return ggd(b, a % b);
}
int main(){
  int n,x;
  std::cin >> n>>x;
  std::vector<int> a(n);
  rep(i,n)std::cin >> a[i];
  a.pb(x);
  std::vector<int> d(n);
  sort(all(a));
  rep(i,n)d[i]=a[i+1]-a[i];
  
  int ans=d[0];
  rrep(i,1,n)ans=ggd(ans,d[i]);
  std::cout << ans << std::endl;
  
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define psi pair<string,int>
#define F first
#define S second
#define mp make_pair
using namespace std;
const int N=105;
psi p[N];int n;
map<psi,int>m;
inline bool cmp(psi a,psi b)
{
	if(a.F!=b.F)
		return a.F<b.F;
	else
		return a.S>b.S;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)cin>>p[i].F>>p[i].S,m[p[i]]=i+1;
	sort(p,p+n,cmp);
	for(int i=0;i<n;i++)
		cout<<m[p[i]]<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;
const long long MOD = 1e9 + 7;
int main() {
    long long n; cin >> n;
    vector<long long> a(n);
    rep(i, n) {
        cin >> a[i];
    }

    long long res = 0;
    for (int d = 0; d < 60; d++) {
        long long n0 = 0, n1 = 0;

        for (int i = 0; i < n; i++) {
            if ((a[i] >> d) & 1) ++n1;
            else ++n0;
        }

        long long tmp = (1LL << d) % MOD; // 2 ** d
        long long x = n0 * n1 % MOD;

        tmp = tmp * x % MOD;
        res = (res + tmp) % MOD;
    }
    cout << res << endl;
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n = sc.nextInt();
		int a = sc.nextInt();
		int[] x = new int[n+1];
		for (int i = 1; i <= n; i++) {
			x[i] = sc.nextInt();
		}
		long[][][] dp = new long[n + 1][n + 1][50 * n + 1];
		dp[0][0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				for (int k = 0; k <= 50 * n; k++) {
					if (i >= 1 && k < x[i]) {
						dp[i][j][k] = dp[i - 1][j][k];
					} else if (i >= 1 && j >= 1 && k >= x[i]) {
						dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i]];
					} else {
						dp[i][j][k] = 0;
					}
				}
			}
		}
		long ans = 0;
		for (int i = 1; i <= n; i++) {
			ans += dp[n][i][i * a];
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 84908
#include<bits/stdc++.h>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const double eps=1e-9;
const int inf=1e9;
typedef pair<int,int> P;

int n,r;
typedef pair<int,int> P;
map<int,map<int,double> > height;

bool judge(double base)
{
  for(int x=-r;x<r;x++)
    {
      double y=height[x][x+1]-base;
      if(x*x+y*y<r*r)
	{
	  return true;
	}
      if((x+1)*(x+1)+y*y < r*r)
	{
	  return true;
	}
    }
  return false;
}
int main(int argc,char const* argv[])
{
  while(cin >> r >> n && r)
    {
      height.clear();
      double lx,rx,h;
      for(int i=0;i<n;i++)
	{
	  cin >> lx >> rx >> h;
	  for(int x=lx;x<rx;x++)
	    {
	      height[x][x+1]=max(h,height[x][x+1]);
	    }
	}
      bool end=false;
      double base=-r;
      double t=0.0,step=0.0001;
      while(1)
	{
	  base+=step;
	  end=judge(base);
	  if(end) break;
	  t+=step;
	}
      cout <<fixed << setprecision(9) << t << endl;
    }
  return 0;
}



Measured memory_bytes: 3260
import java.util.*;


public class Main {
	
	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			int k = sc.nextInt();
			int max = Math.max(a, Math.max(b, c));
			int sum = max;
			for(int i = 0; i < k; i++){
				sum *= 2;
			}
			System.out.println(a + b + c + sum - max);
			
		}
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

	public static void main(String[] args) {
		new Main().doit();
	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'
#define all(a) a.begin(), a.end()
#define rev(a) reverse(all(a)
#define ld long double
const ll mod=1e9+7;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
int main() {
        ll n,m;
        cin >> n >> m;
        ll xxx=n%m,ans=xxx;
        if(xxx==0){
            cout <<0 << endl;
            return 0;
        }
        while(ans>abs(xxx-m)){
            ans=min(ans,abs(xxx-m));
            xxx=(xxx-m);
        }
        cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
d = defaultdict(lambda: 0)
for i in range(len(A)):
    d[A[i]] += 1
total = 0
for k,v in d.items():
    total += v*(v-1)//2
for a in A:
    print(total - (d[a]-1))

Measured memory_bytes: 26780
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){
    int n; cin>>n; 
    vi a(n),b(n);
    for (int &i: a) cin >> i ; 
    for (int &i: b) cin >> i ; 
    int ok = 0,s=0;
    for (int i=0;i<n;i++){
        s += max(0LL,(a[i]-b[i])*2);
        ok += max(0LL,(b[i]-a[i])/2); 
    }
    if ( ok >= s/2 ) printf("Yes\n");
    else printf("No\n");
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


Measured memory_bytes: 3696
#include <iostream>
    #include <string>
    #include <math.h>
    using namespace std;
     
    int main()
    {
    int N;
      cin >> N;
    if(N<1000){
    cout << "ABC" << endl;
  }
      else {
    cout << "ABD" << endl;
}
        return 0;
    }

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

int main() {
	int n;
	cin>>n;
	int i = 1;
	while(1) {
		int x = i;
		
		if(x % 3 == 0){
			cout<<" "<<i;
		} else {
			while(1) {
				if(x % 10 == 3) {
					cout<<" "<<i;
					break;
				}
				x /= 10;
				if (x == 0) break;
			}
		}
		if(++i > n) break;
		
	}
	cout<<endl;
	return 0;
}


Measured memory_bytes: 3104
//Created by Aminul on 7/5/2020.

import java.io.*;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = in.nextInt(), k = in.nextInt();
        long a[] = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }

        pw.println(maxProductOfKNumbers(a, n, k));

        pw.close();
    }

    static long maxProductOfKNumbers(long[] a, int n, int k) {
        shuffle(a);
        Arrays.sort(a);
        long product = 1, mod = (long) 1e9 + 7;

        if (a[n - 1] == 0 && k % 2 != 0)
            return 0;
        if (a[n - 1] <= 0 && k % 2 != 0) {
            for (int i = n - 1; i >= n - k; i--)
                product = mod(product * a[i], mod);
            return product;
        }

        int i = 0;
        int j = n - 1;
        if (k % 2 != 0) {
            product = mod(product * a[j], mod);
            j--;
            k--;
        }
        k >>= 1;
        for (int itr = 0; itr < k; itr++) {
            long leftProduct = a[i] * a[i + 1];
            long rightProduct = a[j] * a[j - 1];
            if (leftProduct > rightProduct) {
                product = mod(product * (leftProduct % mod), mod);
                i += 2;
            } else {
                product = mod(product * (rightProduct % mod), mod);
                j -= 2;
            }
        }
        return product;
    }

    public static long mod(long a, long m) {
        long A = (a % m);
        return A >= 0 ? A : A + m;
    }

    public static void shuffle(long[] a) {
        Random rnd = new Random();
        for (int i = a.length - 1; i >= 1; i--) {
            int j = rnd.nextInt(i + 1);
            long t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }


    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }
}

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

#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=1009;
const ll inf=1e9+900;

ll a[maxn][maxn];
ll h[maxn][maxn];
ll n,m;
queue<pii> qu;

void add(ll x,ll y,ll w){
    if(x<0 || x>=n || y<0 || y>=m || h[x][y]!=-1){
	return;
    }
    h[x][y]=w;
    qu.push(mp(x,y));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(h,-1,sizeof h);

    for(ll i=0;i<n;i++){
	string s;
	cin>>s;
	for(ll j=0;j<m;j++){
	    a[i][j]=s[j];
	    if(a[i][j]=='#'){
		qu.push(mp(i,j));
		h[i][j]=0;
	    }
	}
    }
    ll ans=0;
    while(qu.size()){
	ll x=qu.front().F;
	ll y=qu.front().S;
	ll w=h[x][y]+1;
	qu.pop();
	add(x+1,y,w);
	add(x-1,y,w);
	add(x,y-1,w);
	add(x,y+1,w);
	ans=w-1;
    }
    cout<<ans;
}


Measured memory_bytes: 32564
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort((x).begin(), (x).end())
#define Reverse(x) reverse((x).begin(), (x).end())
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define INF INT_MAX
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15) //15桁まで表示
#define str string
typedef std::pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<ui,ui> puu;
typedef pair<int, int> P;
typedef vector<int> vi;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a * b / gcd(a, b);};
int floor(int a,int b){return (a+b-1)/b;};
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
template<class T>inline bool chmax(T& a,T b){if(a < b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a > b){a=b;return true;}return false;};
int d[2019];
int d2[2019];
int main() {
    
    vi a(200010);
    str s;
    cin >> s;
    int n=s.length();
    int ans=0;
    rep(i,n) a[i]=s[i]-'0';
    d2[a[0]]++;
    REP(i,1,n){
        d[a[i]]++;
        rep(j,2019){
            d[(10*j+a[i])%2019]+=d2[j];
        }
        ans+=d[0];
        rep(j,2019){
            d2[j]=d[j];
            d[j]=0;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4416
#include<iostream>

using namespace std;

int main(){

  int price, money;

  while(cin >> price >> money){
    if(price == 0 && money == 0) break;

    money -= price;

    int x=0, y=0 ,z=0;

    while(money>=1000){
      money -= 1000;
      z++;
    }

    while(money >= 500){
      money -= 500;
      y++;
    }

    x = money / 100;

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

  return 0;
}

Measured memory_bytes: 0
use proconio::{input,fastout};
use std::collections::HashMap;

#[fastout]
fn main() {
  input!{n: usize};
  // 値→個数
  let mut numbers: HashMap<usize, usize> = HashMap::new();
  for _ in 1..(n+1) {
    input!{a: usize};
    let k = numbers.entry(a).or_insert(0);
    *k += 1;
  }
  let mut sum: usize = numbers.iter().map(|(k, v)| k * v).sum();
  eprintln!("{:?}", sum);
  
  input!{q: usize};
  for _ in 0..q {
    input!{b: usize, c: usize};
	sum += (c - b) * numbers.get(&b).unwrap_or(&0);
    let bc = *(numbers.get(&b).unwrap_or(&0));
    { *numbers.entry(c).or_insert(0) += bc; }
    { *numbers.entry(b).or_insert(0) = 0; }
    println!("{}", sum);
  }
}

Measured memory_bytes: 7212
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
B=nl()
C=nl()
sum=0

sum+=B[A[0]-1]
for i in range(1,N):
    option= C[A[i-1]-1] if (A[i]==A[i-1]+1) else 0
    sum+=B[A[i]-1]+option

print(sum)

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

int main(){
	float xa,ya,xb,yb,xc,yc,xd,yd;

	while(cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd){
		if( (xb-xa) * (xd-xc) + (yb-ya) * (yd-yc) == 0.0)
			cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 1216
n=int(input())

alist=[0]*(10**5+1)

A=list(map(int,input().split()))
q=int(input())

for i in A:
    alist[i]+=1
asum=sum(A)
for i in range(q):
    b,c=map(int , input().split())
    bnum=alist[b]
    asum+=bnum*(c-b)
    alist[b]=0
    alist[c]+=bnum
    print(asum)


Measured memory_bytes: 84744
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
typedef vector<int> vec;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int x,n;
LL y,sum,wei,ans;
int main(){
	cin>>n;
	FOR(i,1,n){
		cin>>x>>y;
		sum+=x*y;
		wei+=y;
	}
	ans=(sum-1)/9+wei-1;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
n,m = map(int,input().split())
lm = []
for _ in range(m):
    lm.append(tuple(map(int,input().split())))
l = lm[0][0]
r = lm[0][1]
for x in range(1,m):
    if lm[x][0] > l:
        l = lm[x][0]
    if lm[x][1] < r:
        r = lm[x][1]
    
if l > r:
    print(0)
else:
    print(r-l+1)

Measured memory_bytes: 16620
import java.util.*
import java.math.*
import java.lang.Math.*

val readString: ()->String = {readLine()!!}
val readInt: ()->Int = {readLine()!!.toInt()}
val readLong: ()->Long = {readLine()!!.toLong()}
val readIntArray: ()->IntArray = {readLine()!!.split(' ').map{it.toInt()}.toIntArray()}
val readLongArray: ()->LongArray = {readLine()!!.split(' ').map{it.toLong()}.toLongArray()}
val errPrintln: (String)->Unit = {msg -> System.err.println(msg)}
val MOD = 1e9.toLong()+7
val INF = Int.MAX_VALUE/2
val LINF = Long.MAX_VALUE/2
data class IntPair(val first: Int, val second: Int)
data class To(val idx: Int, val cost: Long)


class Bellman(val eg: Array<ArrayList<To>>, val start: Int) {
    private var dist = LongArray(0)

    var hasCycle = false
    private set

    init {
        val N = eg.size

        dist = LongArray(N){-LINF}
        dist[start] = 0L

        for (i in 0 until N) {
            var updating = false
            for (x in 0 until N)  {
                for (t in eg[x]) {
                    val y = t.idx

                    if (dist[x] + t.cost > dist[y]) {
                        dist[y] = dist[x] + t.cost
                        updating = true
                    }
                }
            }
            if (!updating) break
        }

        hasCycle = calcCycle()
    }


    private fun calcCycle(): Boolean {
        val N = eg.size
        val ndst = dist.clone()
        //for (i in 0 until N) {
            //var updating = false
            for (x in 0 until N)  {
                for (t in eg[x]) {
                    val y = t.idx
                    if (ndst[x] + t.cost > ndst[y]) {
                        ndst[y] = ndst[x] + t.cost
                        //updating = true
                    }
                }
            }
            //if (!updating) break
        //}

        //dist.forEachIndexed{ i, v ->
        //    if (v != ndst[i]) return true
        //}
        //return false
        return ndst[N-1] != dist[N-1]
    }


    fun distance(i: Int): Long {
        return if(hasCycle) LINF else dist[i]
    }
}


fun solve(eg: Array<ArrayList<To>>): Long {
    val N = eg.size

    val bm = Bellman(eg, 0)

    return bm.distance(N-1)
}


fun main(args: Array<String>) {
    val (N, M) = readIntArray()
    val eg = Array(N){ArrayList<To>()}
    for (i in 0 until M) {
        var (a, b, c) = readLongArray()
        a--;b--;
        eg[a.toInt()].add(To(b.toInt(), c))  // 有向グラフ
    }

    val ans = solve(eg)

    if (ans == LINF) println("inf")
    else println(ans)
}


Measured memory_bytes: 49412
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n,a;
  vector<int>v(1,0);
  cin >> n;
  while(n--){
    cin >> a;
    v.push_back(a);
  }
  for(int j=1;j<v.size();j++){
    int key = v[j],i = j - 1;
    while(i > 0 && v[i] > key){
      v[i+1] = v[i];
      i--;
    }
    v[i+1] = key;
    for(int j=1;j<v.size();j++){
      cout << (j==1?"":" ") << v[j];
    }
    cout << endl;
  }
}



Measured memory_bytes: 3156
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>
#include <cassert>
#include <bitset>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define EL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
using Graph = std::vector<std::vector<int> >;
const int INF = 1e17;
/* libraries */

int check(int n, int k) {
	if(k==1) return 0;
	while(n%k==0) n/=k;
	if(n%k==1) return 1;
	return 0;
}

signed main() {
	int n;
	std::cin >> n;
	// get the factors of n-1 and n
	int count=0;
	for(int x=1;x*x<=n-1;x++) {
		if((n-1)%x==0) {
			count++;
			if(x*x!=n-1) count++;
		}
	}
	count--; // for x=1
	for(int x=1;x*x<=n;x++) {
		if(n%x==0) {
			count+=check(n,x);
			if(x*x!=n) count+=check(n,n/x);
		}
	}
	print(count);

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; inline void fileio(const char* in, const char* out) { freopen(in, "r", stdin); freopen(out, "w", stdout); } 
#define TD typedef
#define forx(i,n) for(int i = 0; i < (n); ++i)
#define forxr(i,n) for(int i = (n)-1; i >= 0; --i)
TD long long ll; TD long double ld; TD pair<int,int> pii; TD pair<ll,ll> pll; TD vector<int> VI; TD vector<bool> VB; TD vector<ll> VL;
const char nl = '\n'; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fll; const ld EPS = 1e-9, PI = acos(-1);
#define ff first
#define ss second
#define all(c) c.begin(),c.end()

int main() {
  atexit([](){ cerr << "Time: " << (ld)clock() / CLOCKS_PER_SEC << nl; });
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cout << fixed << setprecision(12);
  // Emily <3
  int n; cin >> n;
  map<string, int> cnt;
  while (n--) {
    string s; cin >> s;
    cnt[s]++;
  }
  int mx = 0;
  for (auto e : cnt) {
    mx = max(mx, e.ss);
  }
  for (auto e : cnt) {
    if (e.ss == mx) {
      cout << e.ff << nl;
    }
  }
  return 0;
}



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

int main(){
    int a, b, c, tmp;
    cin >> a >> b >> c;
    if(a > b){
        tmp = a;
        a = b;
        b = tmp;
    }
    if(a > c){
        tmp = a;
        a = c;
        c = tmp;
    }
    if(b > c){
        tmp = b;
        b = c;
        c = tmp;
    }
    cout << a << " " << b << " " << c << endl;
    return 0;
}



Measured memory_bytes: 3080
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

vector <vector <int>  > g;
vector <int> val;
vector <int> inc;
vector <bool> visited;
void dfs(int s,int add);

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n=nxt(),q=nxt();
    vector <int> row;
    g.resize(n+1,row);
    for(int i=0;i<n-1;i++)
    {
        int u=nxt(),v=nxt();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    val.resize(n+1,0);
    inc.resize(n+1,0);
    while(q--)
    {
        int p=nxt(),x=nxt();
        inc[p]+=x;
    }
    visited.resize(n+1,0);
    dfs(1,0);

    for(int i=1;i<=n;i++)
        cout<<val[i]<<" ";
    cout<<endl;

    
    
    return 0;   
}

void dfs(int s,int add)
{
    val[s]+=(add+inc[s]);
    visited[s]=1;
    for(auto i: g[s])
    {
        if(!visited[i])
        {
            dfs(i,add+inc[s]);
        }
    }
}


 
 


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

/*vector<int> p(n);
cin >> p[i]*/

int main(){

    int count = 0;
    string s;
    cin >> s;

    count = s.length();

    for(int i=0; i<count; i++) cout << 'x';

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> Pi;
typedef pair<int, Pi> Pii;
#define fr first
#define sc second

int M, N, D, ns, nc, nj;
char temp['z' + 1], o;
int mas[20][20];
int go[20][20][20][20];
bool used[20][20][101];
Pi S, G;
int dy[] = { 0, 1, 0, -1 }, dx[] = { -1, 0, 1, 0 };

bool isover(int y, int x) {
	return y < 0 || y >= M || x < 0 || x >= N;
}

bool isred(int y, int x, int time, bool istate) {
	return ~mas[y][x] && !istate ^ time / mas[y][x] & 1;
}

int Dijkstra() {
	fill_n(**used, 20 * 20 * 101, false);
	priority_queue<Pii, vector<Pii>, greater<Pii> > que;
	que.push(Pii(0, S));
	while (!que.empty()) {
		Pii p = que.top();
		que.pop();
		if (p.sc == G)
			return p.fr;
		if (used[p.sc.fr][p.sc.sc][p.fr]++)
			continue;
		for (int i = 0; i < 4; i++) {
			int ny = p.sc.fr + dy[i], nx = p.sc.sc + dx[i];
			if (isover(ny, nx))
				continue;
			if (go[p.sc.fr][p.sc.sc][ny][nx] == -1)
				continue;
			int nexttime = p.fr + D + go[p.sc.fr][p.sc.sc][ny][nx];
			if (isred(ny, nx, nexttime, i & 1))
				continue;
			que.push(Pii(nexttime, Pi(ny, nx)));
		}
	}
	return -1;
}

int main() {

	for (int i = 'a', j = 1; i <= 'z'; i++, j++) {
		temp[i] = j;
	}

	while (cin >> M >> N, M) {

		fill_n(*mas, 400, -1);
		fill_n(***go, 20 * 20 * 20 * 20, 0);

		cin >> D;
		cin >> ns;
		for (int i = 0; i < ns; i++) {
			char h;
			int v, k;
			cin >> h >> o >> v >> k;
			mas[temp[h] - 1][v - 1] = k;
		}

		cin >> nc;
		for (int i = 0; i < nc; i++) {
			char h1, h2;
			int v1, v2;
			cin >> h1 >> o >> v1 >> h2 >> o >> v2;
			go[temp[h1] - 1][v1 - 1][temp[h2] - 1][v2 - 1] = -1;
			go[temp[h2] - 1][v2 - 1][temp[h1] - 1][v1 - 1] = -1;
		}

		cin >> nj;
		for (int i = 0; i < nj; i++) {
			char h1, h2;
			int v1, v2, d;
			cin >> h1 >> o >> v1 >> h2 >> o >> v2 >> d;
			go[temp[h1] - 1][v1 - 1][temp[h2] - 1][v2 - 1] = d;
			go[temp[h2] - 1][v2 - 1][temp[h1] - 1][v1 - 1] = d;
		}

		char h1, h2;
		int v1, v2;
		cin >> h1 >> o >> v1 >> h2 >> o >> v2;
		S = Pi(temp[h1] - 1, v1 - 1);
		G = Pi(temp[h2] - 1, v2 - 1);

		cout << Dijkstra() << endl;
	}
}

Measured memory_bytes: 3676
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int maxn = 1e5 + 111;
int N, M, K, f[maxn], cnt[maxn], ans[maxn];

int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

void unionset(int x, int y){
    int fx=find(x), fy=find(y);
    if (fx!=fy){
        if (cnt[fx]<cnt[fy]) cnt[fy]+=cnt[fx], f[fx]=fy;
        else cnt[fx]+=cnt[fy], f[fy]=fx;
    }
}

int main(){
    scanf("%d%d%d", &N, &M, &K);
    for (int i=1; i<=N; i++) cnt[i]=1, f[i]=i, ans[i]=N-1;
    for (int i=1; i<=M; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        ans[u]--; ans[v]--;
        unionset(u, v);
    }
    for(int i=1; i<=K; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        if (find(u)==find(v)){
            ans[u]--; ans[v]--;
        }
    }
    for (int i=1; i<=N; i++){
        int fi=find(i);
        ans[i]-=(N-cnt[fi]);
        printf("%d ", ans[i]);
    }
}



Measured memory_bytes: 2048
// Problem : C - Traveling Salesman around Lake
// Contest : AtCoder Beginner Contest 160
// URL : https://atcoder.jp/contests/abc160/tasks/abc160_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

// Author - Sumit 
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define int ll
#define ps push
#define pb emplace_back
#define INF 10000000000000LL
#define MOD 1000000007
#define mp make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)
#define repd(i,a,b) for (int i = a; i >= b; i--)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pair<int,int>>
#define itr :: iterator it
#define WL(t) while(t --)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define lower(v,x) (lower_bound(all(v),x)-v.begin())
#define upper(v,x) (upper_bound(all(v),x)-v.begin())
#define debug(x) cout << x << "\n";
#define debug2(x,y) cout << x << " " << y << "\n";
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
 
template<typename T, typename U> inline void remin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void remax(T &x, U y) { if(x < y) x = y; }
template<typename T> T pow(T a,T b, int m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
 
void solve(){
	int k,n;
	cin>>k>>n;
	int a[n];
	rep(i,0,n) cin>>a[i];
	int ans=-INF;
	rep(i,0,n-1){
		remax(ans,a[i+1]-a[i]);
	}
	// int xx=0;
	// rep(i,0,n-2) xx+=a[i+1]-a[i];
	// xx+=abs(a[n-1]-k);
	// // debug2(xx,ans);
	remax(ans,abs(a[n-1]-k)+abs(0-a[0]));
	debug(k-ans);
    
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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

int main() {
	int N;
	cin >> N;
	vector<long> a(N), b(N);
	for (long& i : a) cin >> i;
	for (long& i : b) cin >> i;
	pair<long, long> c;
	for (int i = 0; i < N; i++) {
		if (a[i] < b[i]) {
			c.first += (b[i] - a[i] + 1) / 2;
			c.second += (b[i] - a[i]) % 2;
		}
		else if (b[i] < a[i]) c.second += a[i] - b[i];
	}
	if (c.first < c.second) cout << "No";
	else cout << "Yes";
}

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

public class Main {

  public static void main(String[] args) {
    
    new Main().run();
  }

  public void run() {

    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      String op;
      String[] words;
      Tree tree = new Tree();
      StringBuilder buf = new StringBuilder();

      for(int i=0,k=0; i<n; i++,k=0){
        words = br.readLine().split(" ");
        op  = words[k++];
        if ( op.equals("insert") ) { 
          tree.insert(Integer.parseInt(words[k++]));
        }
        else {
          buf.append(tree.getRoundPath());
        }
      }

      System.out.print(buf);

    }
    catch(IOException e) {
      System.out.println("IOException!");
    }
  }
}

class Tree {

  static final BTreeNode NIL = new BTreeNode();
  BTreeNode root;
  StringBuilder buf;

  public Tree() {
    root = NIL;
    buf = new StringBuilder();
  }

  public void insert(int val) {
    BTreeNode y = NIL;
    BTreeNode x = root;
    BTreeNode z = new BTreeNode();
    z.key = val;

    while( !x.equals(NIL) ) {
      y = x;
      if( z.key < x.key )
        x = x.left;
      else
        x = x.right;
    }
    z.parent = y;

    if( y.equals(NIL) ){
      root = z;
    }
    else if( z.key < y.key )
      y.left = z;
    else
      y.right = z;
  } 
  void preParse(BTreeNode u) {
    if( !u.equals(NIL) ) {
      buf.append(" ").append(u.key);
      preParse(u.left);
      preParse(u.right);
    }
  }
  void inParse(BTreeNode u) {
    if( !u.equals(NIL) ) {
      inParse(u.left);
      buf.append(" ").append(u.key);
      inParse(u.right);
    }
  }

  String getRoundPath() {
    buf.setLength(0);

    inParse(root);
    buf.append("\n");
    preParse(root);
    buf.append("\n");

    return buf.toString();
  }
}

class BTreeNode {
  int key;
  BTreeNode parent,left,right;

  public BTreeNode() {
    this.key = -1;
    this.parent =
    this.left =
    this.right = Tree.NIL;
  }

  @Override
  public boolean equals(Object o) {
    if(o == this) return true;
    if(o == null) return false;
    if(!(o instanceof BTreeNode)) return false;

    BTreeNode node = (BTreeNode)o;
    if(!(this.key == node.key)) return false;

    return true;
  }
}


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,K;

void solve(){
    N--;
    int d=1,t=1;
    while(true){
        if(N<t*9*d)break;
        N-=t*9*d;
        d++;
        t*=10;
    }

    int tmp=N/d;
    N%=d;
    t+=tmp;
    stringstream ss;
    while(ss.str().size()<120){
        ss<<t;
        t++;
    }
    string s=ss.str();
    cout<<s.substr(N,K)<<endl;

}

signed main(){
    while(cin>>N>>K,N||K)solve();
    return 0;
}

Measured memory_bytes: 3120
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy

mod = 10 ** 9 + 7
t = time.time()



def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def main():
    A, B = iip()

    a = set(soinsuu_bunkai(A))
    b = set(soinsuu_bunkai(B))

    ans = 1 # 1の場合
    for aa in a:
        if aa in b:
            ans+=1

    print(ans)

main()

Measured memory_bytes: 3436
#include <iostream>

using namespace std;

typedef long long int elmtype;

elmtype DeleteMax(elmtype *A, int n){ // ヒープを保ちつつ最大(先頭要素)を返す関数
  elmtype max = A[0], w;
  int i, j;
  if ((--n) < 1) return max;
  A[0] = A[n];
  for (i=0; (j=i+i+1) < n; i=j){
    if (j+1 < n && A[j+1] > A[j]) j++; /* もう一つの子 */
    if (A[i] >= A[j]) break; /* 親<=子なので終了 */
    /* 親と子を交換 */
    w=A[i]; A[i]=A[j]; A[j]=w;
  }
  return max;
}

void Insert(elmtype x, elmtype *A, int n){
  elmtype w;
  A[n] = x;
  int j;
  for (int k=n; k > 0; k=j){
    j = (k-1) >> 1; /* 親 */
    if (A[j] >= A[k]) break; /* 親<=子なので終了 */
    /* 親と子を交換 */
    w=A[j]; A[j]=A[k]; A[k]=w;
  }
}

int main(){
  int N, M;
  cin >> N >> M;
  elmtype A[N], B[N], tmp, ans=0;
  for(int i=0; i<N; i++) cin >> A[i];
  for(int i=0; i<N; i++) Insert(A[i], B, i);
  for(int i=0; i<M; i++){
    tmp = DeleteMax(B, N)/2;
    Insert(tmp, B, N-1);
  }
  for(int i=0; i<N; i++) ans += B[i];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define EPS (1e-10)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0

using namespace std;

class Point
{
  public:
  double x,y;
  Point(double x = -1,double y = -1): x(x),y(y){}

  Point operator + (Point p ){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}//※イケメンに限る

  bool operator < (const Point& p) const
  {
    return x != p.x?x<p.x:y<p.y;
  }

  bool operator == (const Point& p)const
  {
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }
};

struct Segment
{
  Point p1,p2;
  Segment(Point p1 = Point(-1,-1),Point p2 = Point(-1,-1)):p1(p1),p2(p2){}
};

typedef Segment Line;
typedef vector<Point> Polygon;

struct Circle
{
  double x,y,r;
  Circle(double x=-1,double y=-1,double r=-1):x(x),y(y),r(r){}
};

double dot(Point a,Point b)
{
  return a.x*b.x + a.y*b.y;
}
double cross(Point a,Point b)
{
  return a.x*b.y - a.y*b.x;
}

double norm(Point a)
{
  return a.x*a.x+a.y*a.y;
}

double abs(Point a)
{
  return sqrt(norm(a));
}

double getDistanceLP(Line s,Point p)
{
  return abs(cross(s.p2-s.p1,p-s.p1))/abs(s.p2-s.p1);
}

double getDistanceSP(Segment s,Point p)
{
  if(dot(s.p2-s.p1,p-s.p1) < 0.0)return abs(p-s.p1);
  if(dot(s.p1-s.p2,p-s.p2) < 0.0)return abs(p-s.p2);
  return getDistanceLP(s,p);
}

bool inCircle(Circle c,Point p)
{
  return sqrt(pow(p.x-c.x,2)+pow(p.y-c.y,2)) <= c.r;
}

bool check(Circle c,Segment s)
{
  if(inCircle(c,s.p1) && inCircle(c,s.p2))return false;
  double dist = getDistanceSP(s,Point(c.x,c.y));
  return dist <= c.r;
}

int main()
{
  int n,m;
  while(cin >> n,n)
    {
      vector<Circle> vec(n);
      for(int i=0;i<n;i++)cin >> vec[i].x >> vec[i].y >> vec[i].r;
      cin >> m;
      Segment s;
      for(int i=0;i<m;i++)
	{
	  cin >> s.p1.x >> s.p1.y >> s.p2.x >> s.p2.y;
	  for(int j=0;j<n;j++)
	    {
	      if(check(vec[j],s))
		{
		  cout << "Safe" << endl;
		  goto F;
		}
	    }
	  cout << "Danger" << endl;
	F:;
	}
    }
  return 0;
}

Measured memory_bytes: 1228
#include <iostream>
using namespace std;
int array[20],n;

bool f(int m,int now,int i){
	if(now == m) return true;
	if(n <= i) return false;
	if(f(m,now + array[i],i+1)) return true;
	return f(m,now,i+1);
}
int main(){
	int q,m;
	cin >> n;
	for(int i = 0;i < n;++i){
		cin >> array[i];
	}
	cin >> q;
	for(int i = 0;i < q;++i){
		cin >> m;
		if(f(m,0,0)) cout << "yes" << endl;
		else cout << "no" << endl;
	} 
	return 0;
}

Measured memory_bytes: 1152
#include<iostream>
#include<vector>
#include<map>
#include<cstdlib>
#include<string>
#define f first
#define s second
#define mp make_pair
using namespace std;

map<pair<char,int>,int> m1;
map<char,int> m2;
vector<string> vs;

int rec(string s){
  int res=-1;
  if('0'<=s[0] && s[0]<='9')res=atoi(s.c_str());
  else {
    pair<char,int> p(s[0],rec(s.substr(2,s.length()-3)));
    if(m1.find(p)==m1.end())res=-1;
    else res=m1[p];
  }
  return res;
}

bool check(int index){
  int eq=-1;
  string s=vs[index];
  for(int i=0;i<s.length();i++)if(s[i]=='=')eq=i;
  if(eq==-1)m2[s[0]]=rec(s.substr(2,s.length()-3));
  else {
    //cout<<s.substr(2,eq-3)<<" "<<s.substr(eq+1,s.length()-eq)<<endl;
    int l=rec(s.substr(2,eq-3)),r=rec(s.substr(eq+1,s.length()-eq));
    if(l==-1 || r==-1)return false;
    if(m2[s[0]]<=l)return false;
    m1[mp(s[0],l)]=r;
  }
  return true;
}

int main()
{
  while(1){

    string s;
    vs.clear();
    while(1){
      cin>>s;
      if(s[0]=='.')break;
      vs.push_back(s);
    }

    if(vs.size()==0)break;

    int ans=0;
    m1.clear();
    m2.clear();
    for(int i=0;i<vs.size();i++){
      if(!check(i)){
	ans=i+1;
	break;
      }
    }
    cout<<ans<<endl;

  }

  return 0;
}

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

#define ll long long
#define str string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

#define vc vector<char>
#define vvc vector<vc>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvvll vector<vvll>
#define vs vector<str>
#define vvs vector<vs>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vpll vector<pll>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define repi(i, a, b) for (int i = (a); i <= int(b); i++)


using namespace std;
ll INF = LONG_LONG_MAX;
ll mod = 1000000000 + 7;

template <typename T, typename L>
void read(vector<T> & _data, L & _size, bool _shift) {
    _data.resize(_size + (ll)_shift);
    for (ll i = (ll)_shift; i < _size + (ll)_shift; i++)
        cin >> _data[i];
}

template <typename T, typename L>
void read(vector<vector<T>> & _data, L & _rows, L & _cols, bool _shiftRows, bool _shiftCols) {
    _data.resize(_rows + (ll)_shiftRows);
    for (ll i = 0; i < _rows + (ll)_shiftRows; i++)
        _data[i].resize(_cols + (ll)_shiftCols);
    for (ll i = (ll)_shiftRows; i < _rows + (ll)_shiftRows; i++)
        for (ll j = (ll)_shiftCols; j < _cols + (ll)_shiftCols; j++)
            cin >> _data[i][j];
}

template <typename T>
void write(vector<T> & _data, bool _shift) {
    for (ll i = (ll)_shift; i < _data.size(); i++)
        cout << _data[i] << " ";
    cout << endl;
}


//TODO: SOLUTION


void solve() {
    ll n; cin >> n;
    vll a; read(a, n, 0);
    sort(a.begin(), a.end());

    ll ai = a[n - 1];
    ll aj = a[0];
    ll mid = ai / 2;

    for (auto y : a) {
        if (y == ai)
            break;
        if (abs(y - mid) <= abs(aj - mid)) {
            aj = y;
        }
    }

    cout << ai << " " << aj << endl;
}


int main() {

    // TODO: Set value of this variable manually
    bool _multipleTestCases = false;

    if (_multipleTestCases) {
        ll t; cin >> t;
        while (t--)
            solve();
    }
    else {
        solve();
    }

    return 0;
}

Measured memory_bytes: 3956
#include <stdio.h>

int main() {
  char n[4];
  scanf("%s",n);
  for (int i = 0; i < 3; i++) {
    if (n[i] == '1') {
      n[i] = '9';
      continue;
    }
    if (n[i] == '9') {
      n[i] = '1';
      continue;
    }
  }
  printf("%s\n",n);
  return 0;
}


Measured memory_bytes: 128