akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
#define int long long int
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {0}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}
#define print(a) cout << a << endl;
#define printarr(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll MOD = 1e9+7;
const ll inf = 1e18;
const ll p = 998244353;
int fac[200005];
double powe(double x,int y) 
{ 
    if (y == 0) 
        return 1.00;
    double p = powe(x, y/2);
    p = (p * p); 
    return (y%2 == 0)? p : (x * p); 
} 
int power(int x,int y, int m) 
{ 
    if (y == 0) 
        return 1;
    int p = power(x, y/2, m) % m; 
    p = (p * p) % m; 
  
    return (y%2 == 0)? p : (x * p) % m; 
} 
int mod(int x)
 {
	if(x<0)return -x;
	else return x;
 }
 int inverse(int a, int p)
{
    return power(a, p-2, p);
}
int ncr(int n, int r, int p)
{
    if (r==0)
        return 1;
    return (fac[n]*inverse(fac[r], p) % p *
            inverse(fac[n-r], p) % p) % p;
}
 int leaves=0;
 vector<int> visited;
 vector<set<int> > adj;
 vector<int> color;
 void dfs(int s)
{    
     
     if(visited[s])return;
     visited[s]=1;
     for(set<int>::iterator i=adj[s].begin();i!=adj[s].end();i++)
     {
     	if(!visited[*i])
     	{
     	 dfs(*i);	
		}
	 }
 }
 //Don't forget to clear vectors>>;
 //i miss simpu:3)(;
signed main()
{
read(n);
readarr(a,n);
int ans[n+2][n+2];
FOR(i,0,n+1)
{
	FOR(j,0,n+1)
	ans[i][j]=0;
}
FORD(i,n,1)
{
	FOR(j,i,n)
	{
		if((j-i)%2==(n-1)%2)
		{
			ans[i][j]=max(a[i]+ans[i+1][j],a[j]+ans[i][j-1]);
		}
		else
		ans[i][j]=min(ans[i+1][j]-a[i],ans[i][j-1]-a[j]);
	}
}
cout<<ans[1][n]<<endl;
}

Measured memory_bytes: 73996
#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <utility>
#include <string>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <functional>

using namespace std;

#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define INF 114514810
#define ll long long
//#define scanf scanf_s

int a[4]; int b[4];

int main()
{
	while (cin >> a[0])
	{
		FOR(i, 1, 4) cin >> a[i];
		REP(i, 4) cin >> b[i];
		int hit = 0;
		int blow = 0;
		REP(i, 4)
		{
			if (a[i] == b[i]) hit++;
			else
			{
				REP(j, 4)
				{
					if (a[i] == b[j]) blow++;
				}
			}
		}
		cout << hit << " " << blow << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	map<string,int> m;
	m["SUN"]=7;
	m["MON"]=6;
	m["TUE"]=5;
	m["WED"]=4;
	m["THU"]=3;
	m["FRI"]=2;
	m["SAT"]=1;
	cout<<m[s]<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        long[] sum = new long[n+1];
        long mod = 1000000007;
        for(int i=0; i<n; i++) {
            a[i] = sc.nextInt();
            sum[i+1] = sum[i] + a[i];
            sum[i+1] %= mod;
        }
        long res = 0;
        for(int i=1; i<n; i++) {
            res += a[i] * sum[i];
            res %= mod;
        }
        System.out.println(res);

    }


}

Measured memory_bytes: 63164
#include<bits/stdc++.h>
#define ll long long
ll dp[3001][3001];
using namespace std;
ll solve(ll ar[],ll i,ll j)
{
    if(i>j){return 0;}
    if(i==j){return ar[i];}
    if(dp[i][j]!=-1){return dp[i][j];}
    return dp[i][j]=max(ar[i]+min(solve(ar,i+2,j),solve(ar,i+1,j-1)),ar[j]+min(solve(ar,i,j-2),solve(ar,i+1,j-1)));
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll n;
    cin>>n;
    ll ar[n],sum=0;
    for(ll i=0;i<n;++i){cin>>ar[i];sum+=ar[i];}
    memset(dp,-1,sizeof(dp));
    ll ans=solve(ar,0,n-1);
    ans=ans-sum+ans;
    cout<<ans;
}

Measured memory_bytes: 74140
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.List
import           Data.Maybe

typify2 (x:y:_) = (x, y)
typify2 _       = undefined

--Input functions with ByteString
readInt :: BS.ByteString -> Integer
readInt = fst . fromJust . BS.readInteger

readIntTuple :: BS.ByteString -> (Integer, Integer)
readIntTuple = typify2 . map readInt . BS.words

readIntList :: BS.ByteString -> [Integer]
readIntList = map readInt . BS.words

getInt :: IO Integer
getInt = readInt <$> BS.getLine

getIntList :: IO [Integer]
getIntList = readIntList <$> BS.getLine

getIntNList :: Integral a => a -> IO [[Integer]]
getIntNList n = map readIntList <$> replicateM (fromIntegral n) BS.getLine

getIntMatrix :: IO [[Integer]]
getIntMatrix = map readIntList . BS.lines <$> BS.getContents

getIntTuple :: IO (Integer, Integer)
getIntTuple = readIntTuple <$> BS.getLine

getIntNTuples :: Integral a => a -> IO [(Integer, Integer)]
getIntNTuples n = map readIntTuple <$> replicateM (fromIntegral n) BS.getLine

getIntTuples :: IO [(Integer, Integer)]
getIntTuples = map readIntTuple . BS.lines <$> BS.getContents

main = do
  num <- getInt
  print $ solve $ map fromInteger [1 .. num]

solve nums = sum [1 | x <- nums, length (show x) `mod` 2 /= 0]


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

int main(){
	int n;
	cin >> n;
	ll a, b;
	cin >> a >> b;
	rep(i, n-1){
		ll ia, ib;
		cin >> ia >> ib;
		ll as = 0;
		if(a%ia == 0){
			as = a/ia;
		}else{
			as = a/ia + 1;
		}
		ll na0 = ia*as;
		ll nb0 = ib*as;
		if(na0 < a || nb0 < b){
			na0 = 1000000000000000001;
			nb0 = 1000000000000000001;
		}
		ll bs = 0;
		if(b%ib == 0){
			bs = b/ib;
		}else{
			bs = b/ib + 1;
		}
		ll na1 = ia*bs;
		ll nb1 = ib*bs;
		if(na1 < a || nb1 < b){
			na1 = 1000000000000000001;
			nb1 = 1000000000000000001;
		}
		if(na0+nb0 < na1+nb1){
			a = na0;
			b = nb0;
		}else{
			a = na1;
			b = nb1;
		}
	}
	ll ans = a + b;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int a[N];
int main()
{
	for (int i = 1; i <= 3; i++)
	cin >> a[i];
	sort(a + 1, a + 4);
	if ((a[1] == a[2] && a[2] != a[3]) ||
		(a[1] != a[2] && a[2] == a[3]))
		cout << "Yes\n";
	else
	cout << "No\n";
}

Measured memory_bytes: 256
//#include "template.hpp"

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define MOD static_cast<int64_t>(1e18 + 7)
#define PI (3.1415926535897932384626433832795)
#define INF static_cast<int32_t>(1e9)
#define LLINF static_cast<int64_t>(1e18)
#define EPS static_cast<int32_t>(1e-9)

using ld = long double;
using ll = int64_t;
using ull = uint64_t;
using vi = vector<int>;
using vll = vector<ll>;
using pi = pair<int, int>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;
using vvvpi = vector<vvpi>;
using vvvvpi = vector<vvvpi>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using si = set<int>;
using sll = set<ll>;

int main() { //TimeMeasure _;
    ull n; cin >> n;
    vll arr(n); for (int i = 0; i < n; ++i) cin >> arr[i];

    ll count = 0;
    for (ll i = 1; i < n; ++i) {
        if (arr[i] < arr[i - 1]) {
            count += arr[i - 1] - arr[i];
            arr[i] += arr[i - 1] - arr[i];
        }
    }
    cout << count << endl;

    return 0;
}


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

#define pb push_back
#define ff first
#define ss second

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

int a;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> a;
	cout << 3 * a * a << endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}

int n, m; // number of nodes, edges

vvi edge;
vvi g;
vi prenum;
vi lowest;
vi parent;
int timer;

void lowlink_dfs(int u, int prev) {
  prenum[u] = timer;
  lowest[u] = timer;
  timer += 1;

  for (auto v : g[u]) {
    if (prenum[v] < 0) {
      parent[v] = u;
      lowlink_dfs(v, u);
      lowest[u] = min(lowest[u], lowest[v]);
    } else if (v != prev) {
      lowest[u] = min(lowest[u], prenum[v]);
    }
  }
}

void lowlink() {
  prenum.assign(n, -1);
  lowest.assign(n, 0);
  parent.assign(n, 0);
  timer = 0;
  lowlink_dfs(0, -1);
}

// call after lowlink()
set<int> ap() {
  int zero_parent = 0;
  set<int> ret;
  FOR(i, 1, n) {
    if (parent[i] == 0) {
      zero_parent += 1;
    } else if (prenum[parent[i]] <= lowest[i]) {
      ret.insert(parent[i]);
    }
  }
  if (zero_parent >= 2) {
    ret.insert(0);
  }
  return ret;
}

int main() {
  scanf("%d %d", &n, &m);
  edge.assign(m, vi(2, 0));
  g.resize(n);
  rep (i, m) {
    int s, t;
    scanf("%d %d", &s, &t);
    if (s > t) {
      swap(s, t);
    }
    edge[i][0] = s;
    edge[i][1] = t;
    g[s].push_back(t);
    g[t].push_back(s);
  }
  sort(all(edge));
  lowlink();
  auto ans = ap();
  for (auto v : ans) {
    printf("%d\n", v);
  }

  return 0;
}

Measured memory_bytes: 7324
#include <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}


signed main(){
  int n;
  cin>>n;
  vector<int>A(n),B(n),C(n);
  for(int i=0;i<n;i++) cin>>A[i];
  for(int i=0;i<n;i++) cin>>B[i];
  for(int i=0;i<n;i++) cin>>C[i];

  sort(A.begin(),A.end());
  sort(B.begin(),B.end());
  sort(C.begin(),C.end());

  int ans = 0;

  int cntAB[N]={},cntBC[N]={};
  for(int i=0;i<n;i++){
    int j = upper_bound(C.begin(),C.end(),B[i])-C.begin();
    cntBC[i] = n - j;
  }
  
  for(int i=n-1;i>=0;i--) cntBC[i] += cntBC[i+1];

  for(int i=0;i<n;i++){
    int j = upper_bound(B.begin(),B.end(),A[i]) - B.begin();
    if(j == n) continue;
    ans += cntBC[j];
  }
  cout<<ans<<endl;
    
  


  return 0;
}


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


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef vector<int> vi;

void pre(){


}

void solve(){


}
bool vis[100009];
unsigned long long d[100009];
vector<pii> g[100009];
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	int n,m;cin>>n>>m;
	rep(i,m){
		int u,v,w;
		cin>>u>>v>>w;
		u--,v--;
		g[u].pb(mp(v,w));
	}
	memset(d,-1,sizeof(d));
	repA(i,1,n-1) g[i].pb(mp(i-1,0));
	priority_queue<pli,vector<pli>,greater<pli>> q;
	q.push(mp(0,0));
	d[0] = 0;
	while(!q.empty()){
		pli z  = q.top();
		q.pop();
		if(z.snd==n-1){
			cout<<z.fst;
			exit(0);
		}
		if(vis[z.snd]) continue;
		vis[z.snd] = 1;
		trav(j,g[z.snd]){
			if(d[j.fst]>z.fst+j.snd){
				d[j.fst] = z.fst+j.snd;
				q.push(mp(d[j.fst],j.fst));
			}
		}
	}
	cout<<-1;
	return 0;
}



Measured memory_bytes: 8060
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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 main(void) {
    int N, X, Y;
    cin >> N >> X >> Y;
    X--;
    Y--;

    vector<int> ans(N);

    for (int left = 0; left < N; left++) {
        for (int right = left + 1; right < N; right++) {
            int dist = right - left;
            chmin(dist, abs(left - X) + 1 + abs(right - Y));
            // printf("(%d, %d): %d\n", left, right, dist);
            ans[dist]++;
        }
    }

    for (int i = 1; i <= N - 1; i++) {
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3616
n = int(input())
ansl = []
if n == 0:
	print(0)
	exit()
while n != 0:
	if n % 2 == 1:
		ansl.append("1")
		n -= 1
	else:
		ansl.append("0")
	n //= -2
print("".join(ansl)[::-1])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) (V).begin(),(V).end()

int main(){
	ll N, M, a, ans = 0;
	cin >> N >> M;
	priority_queue<ll> Q;
	for (int i = 0;i < N;i++) {
		cin >> a;
		Q.push(a);
	}
	for (int i = 0;i < M;i++) {
		a = Q.top();
		Q.pop();
		a /= 2;
		Q.push(a);
	}
	while (!Q.empty()) {
		a = Q.top();
		Q.pop();
		ans += a;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1400
import Data.List

main = getContents >>= putOut.formatOut.calc.formatIn
  where putOut s | null s || last s == '\n' = putStr s
                 | otherwise                = putStrLn s
  
formatIn :: String -> [[Int]]
formatIn =  map ((map (read :: String -> Int)).words).takeWhile (/= "0 0").lines

formatOut :: [Int] -> String
formatOut = unlines.map show

calc :: [[Int]] -> [Int]
calc n = map (\(x:y:_) -> length[(a, b, c) | a <- [1..x], b <- [a..x], c <- [b..x], a < b, b < c, a + b + c == y]) n

Measured memory_bytes: 4548
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int redc=0;
    int whitec=0;
    int n;
    cin>>n;
    string s;
    cin>>s;
    int white[n+5];
    int red[n+5];
    white[0]=0;
    red[0]=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='W')
        whitec++;
        else
        redc++;
        white[i+1]=whitec;
        red[i+1]=redc;
    }
    int ans=min(n-whitec,n-redc);
   /* for(int i=0;i<=n;i++)
    cout<<red[i]<<" ";
    cout<<'\n';
    for(int i=0;i<=n;i++)
    cout<<white[i]<<" ";
    cout<<'\n';*/
    int count=0;
    for(int i=0;i<redc;i++)
    {
        if(s[i]=='R')
        count++;
    }
    ans=min(ans,redc-count);
    cout<<ans;
    return 0;
}


Measured memory_bytes: 5296
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,dp[4001][4001],x1[2000],x2[2000],y11[2000],y2[2000],cnt,X,Y;
ll ans;
map<int,int> mpx,mpy,mpx2,mpy2;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>x1[i]>>y11[i]>>x2[i]>>y2[i];
        mpx[x1[i]]=0;
        mpx[x2[i]]=0;
        //mpx[x2[i]-1]=0;
        mpy[y11[i]]=0;
        mpy[y2[i]]=0;
        //mpy[y2[i]-1]=0;
    }
    for(auto x:mpx){mpx[x.first]=cnt++;mpx2[cnt-1]=x.first;}
    X=cnt;
    cnt=0;
    for(auto x:mpy){mpy[x.first]=cnt++;mpy2[cnt-1]=x.first;}
    Y=cnt;
    //for(auto x:mpy)cout<<x.first<<" "<<x.second<<endl;
    for(int i=0;i<n;i++){
        dp[mpx[x1[i]]][mpy[y11[i]]]++;
        dp[mpx[x1[i]]][mpy[y2[i]]]--;
        dp[mpx[x2[i]]][mpy[y11[i]]]--;
        dp[mpx[x2[i]]][mpy[y2[i]]]++;
    }
    /*
    for(int i=0;i<X;i++){
        for(int j=0;j<Y;j++){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    
    for(int i=0;i<X;i++){
        for(int j=0;j<Y-1;j++){
            dp[i][j+1]+=dp[i][j];
            
        }
    }
    for(int j=0;j<Y;j++){
        for(int i=0;i<X-1;i++){
            dp[i+1][j]+=dp[i][j];
        }
    }
    for(int i=0;i<X-1;i++){
        for(int j=0;j<Y-1;j++){
            //cout<<dp[i][j]<<" ";
            if(dp[i][j]>0){
                //cout<<(mpx[i+1]-mpx[i])<<" "<<mpy[j+1]<<" "<<mpy[j]<<" "<<j<<endl;
                ans+=((ll)mpx2[i+1]-(ll)mpx2[i])*((ll)mpy2[j+1]-(ll)mpy2[j]);
            }
        }
        //cout<<endl;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 128900
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
     
    int n;cin>>n;
    int a[n],ans[n]={0};
    for(int i=0;i<n;i++)cin>>a[i];
    ans[n-1]=0;
    ans[n-2]=abs(a[n-1]-a[n-2]);
    for(int i=n-3;i>=0;i--){
        ans[i]=min(ans[i+1]+abs(a[i+1]-a[i]),ans[i+2]+abs(a[i+2]-a[i]));
    }
    cout<<ans[0];
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, k, x[50], y[50], xx[50], yy[50];

int main() {
	cin >> n >> k;
	inc(i, n) { cin >> x[i] >> y[i]; xx[i] = x[i]; yy[i] = y[i]; }
	
	sort(xx, xx + n);
	sort(yy, yy + n);
	
	LL ans = 4e18;
	inc(xh, n) {
	inc(yh, n) {
	inc(xl, xh) {
	inc(yl, yh) {
		int c = 0;
		inc(i, n) {
			if(inII(x[i], xx[xl], xx[xh]) && inII(y[i], yy[yl], yy[yh])) { c++; }
		}
		if(c >= k) { setmin(ans, (xx[xh] - xx[xl]) * (yy[yh] - yy[yl])); }
	}
	}
	}
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#define INF 1e9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define NO cout<<"NO"<<endl;
#define YES cout << "YES"<<endl;
#define No cout << "No"<<endl;
#define Yes cout << "Yes"<<endl;
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


//(int)'a'は97 (int)'A'は65 (int)'1'は49
//おまじない


int main(){

	int a, b, c;
	cin >> a >> b >> c;

	if (a >= c)swap(a, c);
	if (b >= c)swap(b, c);
	if (a >= b)swap(a, b);

	cout << b * a / 2 << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
char ch[256];
int main()
{
	ch['b']='d';
	ch['d']='b';
	ch['q']='p';
	ch['p']='q';
	string s;
	cin>>s;
	int i;
	for(i=0;i<s.size();i++)
	{
		if(ch[s[i]]!=s[s.size()-1-i]) goto br;
	}
	printf("Yes\n");
	return 0;
	br:;
	printf("No\n");
	return 0;
}


Measured memory_bytes: 512
#include "bits/stdc++.h"

#define rep(a,b) for(int a = 0;a < b;a++)
#define REP(i, x, n) for(int i = x; i < n; i++)
#define P(a) cout << a << endl
#define mp(a,b) make_pair(a,b)
#define ssort(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define vP(v) for(int i = 0;i < v.size();i++){cout << v[i];if(i != v.size()-1)cout << endl;}
#define vcin(v,n) rep(i,n){int a;cin >> a;v.pb(a);}

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int dx[] = { 1, -1 , 0 , 0 };
int dy[] = { 0,  0,  1, -1 };
ll MOD = 1000000007;

long long stoi(string str) {
	long long ret;
	stringstream ss; ss << str;
	ss >> ret;
	return ret;
}

ull gcd(ull a, ull b) {
	if (b > a)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a%b);
}
void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> v(n);
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	rep(i, v[0].size()) {
		rep(j, v[v[0][i]].size()) {
			if (v[v[0][i]][j] == n-1) {
				P("POSSIBLE");
				return;
			}
		}
	}
	P("IMPOSSIBLE");
}

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


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  int big = 10*max(A, max(B, C));
  int answer;
  if (A == max(A, max(B, C))) {
    answer = big+B+C;
  }
  else if (B == max(A, max(B, C))) {
    answer = big+C+A;
  }
  else {
    answer = big+A+B;
  }
  cout << answer << endl;
}

Measured memory_bytes: 256
n,A,B,C=map(int,input().split())
l=[int(input()) for _ in range(n)]
inf = 10**9
def dfs(t,a,b,c):
    if t == n:
        if min(a,b,c)>0: return abs(a-A)+abs(b-B)+abs(c-C)-30
        else: return inf
    ret0 = dfs(t+1,a,b,c)
    ret1 = dfs(t+1,a+l[t],b,c)+10
    ret2 = dfs(t+1,a,b+l[t],c)+10
    ret3 = dfs(t+1,a,b,c+l[t])+10
    return min(ret0,ret1,ret2,ret3)

print(dfs(0,0,0,0))

Measured memory_bytes: 44124
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;


void main() {
    int x;
    scan(x);
    auto ans = (x / 500) * 1000 + (x % 500) / 5 * 5;
    writeln(ans);
}



void scan(T...)(ref T args) {
    auto line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x > arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x < arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

void yes(bool ok, string y = "Yes", string n = "No") {
    return writeln(ok ? y : n);
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <numeric>

using namespace std;
typedef long long int ll;
typedef long double ld;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }                   // 最大公約数
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };                      // 最小公倍数
ll getDigit(ll num) { return log10(num) + 1; }                         // 桁数
ll digitSum(ll n) { return (n < 10) ? n : digitSum(n / 10) + n % 10; } // 各桁の和
#define MOD 1e9 + 7
#define pb push_back
#define rep(i, n) for (ll i = 0; i < n; i++)
#define repn(i, n) for (ll i = 1; i <= n; i++)
#define repi(i, a, b) for (ll i = ll(a); i < ll(b); ++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265359

template <typename T>
void printVector(string name, vector<T> vec)
{
    cout << name << ": ";
    rep(i, vec.size())
    {
        cout << vec[i] << " ";
    }
    cout << endl;
}

void Main()
{
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    rep(i, n) cin >> p[i];
    sort(all(p));

    ll sum = 0;
    rep(i, k)
    {
        sum += p[i];
    }

    cout << sum << endl;

    return;
}

signed main(void)
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3676
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds; 

#define int long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define f first
#define s second
#define sz(x) (int)x.size()
#define endl '\n'
#define forn(i,n) for(int i=0;i<n;++i)
#define fore(i,l,r) for(int i=int(l);i<=int(r);++i)
#define rep(i,begin,end) for(__typeof(end) i=(begin);i!=(end);i++)
#define fill(a,value) memset(a,value,sizeof(a));
#define gcd(a,b) __gcd((a),(b))
#define watch1(x) cout << (x) << endl
#define watch2(x,y) cout << (x) << " " << (y) << endl
#define watch3(x,y,z) cout << (x) << " " << (y) << " " << (z) << endl
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.14159265358979323846

typedef long long ll;
typedef long double ld; 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> oset;

// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

const int mod = 998244353;
const int inf = 9e18;
const int N = 2e5 + 5;

int i,n,a[N],freq[N];

void solve(){
    cin>>n;
    for(i=2;i<=n;++i){
        cin>>a[i];
        freq[a[i]]++;
    }
    for(i=1;i<=n;++i){
        cout<<freq[i]<<endl;
    }
}

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

Measured memory_bytes: 6776
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var array = new string[n];
            for (int i = 0; i < n; i++)
            {
                array[i] = new string(Console.ReadLine().OrderBy(_ => _).ToArray());
            }

            var count = array.GroupBy(_ => _).Select(_ => Rec(_.Count() - 1)).Sum();

            Console.WriteLine(count);
        }

        static decimal Rec(int n) =>
            n == 0 ? 0 : n + Rec(n - 1);
    }
}


Measured memory_bytes: 36884
# -*- coding: utf-8 -*-
"""
Created on Wed Mar 20 15:03:44 2019

0000
Write a program which prints multiplication tables in the following format
"""

for i in range(1, 10):
    for j in range(1, 10):
        print("{0}x{1}={2}".format(i, j, i * j))
        


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

int main() {
	int N, D;
	cin >> N >> D;

	if (N % (2 * D + 1) == 0)
		cout << N / (2 * D + 1) << endl;
	else
		cout << N / (2 * D + 1) + 1 << endl;
}

Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列

using namespace std;
typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define NCK_MAX 510000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

int fcatorial(int n) {
  int ans=1;
  if (n == 0) return 1;
  FOR(i,1,n) {
    ans*=i;
  }
  return ans;
}

int main(int argc, char const *argv[]) {
  int n; std::cin >> n;
  std::vector<int> p(n,0),q(n,0),order(n,0);
  REP(i,n) std::cin >> p[i];
  REP(i,n) std::cin >> q[i];
  // 初期化
  REP(i,n) order[i] = i+1;
  int a=0,b=0,idx=0;
  int num_iter = fcatorial(n);
  REP(idx,num_iter) {
    if (p==order) a = idx;
    if (q==order) b = idx;
    std::next_permutation(order.begin(), order.end());
  }
  int ans = abs(a-b); std::cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<map>
#include<algorithm>

using namespace std;

// a^b % m
long long PowerMod(long long a, long long b, int m)
{
    long long res = 1;
    for (int i = 0; b > 0; i++) {
        if (b & 1) {
            res = (res * a) % m;
        }
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}

// a! % m
long long FactorialMod(long long a, int m)
{
    long long res = 1;
    for (int i = a; i > 0; i--) {
        res = (res * i) % m;
    }
    return res;
}

// nCr % m
long long CombinationMod(long long n, long long r, int m)
{
    if (r > n / 2) {
        r = n - r;
    }
    long long res = 1;
    for (int i = 0; i < r; i++) {
        res = (res * (n - i)) % m;
    }
    res *= PowerMod(FactorialMod(r, m), m - 2, m);
    res %= m;
    return res;
}

void PrimeFactorization(int x, vector<pair<int, int> >& y)
{
    int xrest = x;
    for (int i = 2; i < x; ) {
        if (i > xrest) {
            break;
        }
        if (xrest % i == 0) {
            y.push_back(make_pair(i, 1));
            xrest /= i;
            while (xrest % i == 0) {
                y.back().second++;
                xrest /= i;
            }
        }
        if (i == 2) {
            i++;
        } else {
            i += 2;
        }
    }
}

int main()
{
    const int MOD = 1e9 + 7;

    int N, M;
    cin >> N >> M;

    vector<pair<int, int> > v;
    PrimeFactorization(M, v);

    long long ans = 1;
    for (int i = 0; i < v.size(); i++) {
        ans *= CombinationMod(v[i].second + N - 1, v[i].second, MOD);
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#c
n,m = map(int,input().split())
k = [0]*m
s=[]
for i in range(m):
    k[i],*ss = map(int,input().split())
    s.append( ss )
p = list(map(int,input().split()))


ans=0
for i in range(2**n):
    bi = bin(i)[2:].zfill(n)
    if all( sum(int(bi[sss-1]) for sss in ss )%2 == p[j] for j,ss in enumerate(s) ):
        ans+=1
print(ans)

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

ll gcd(ll a, ll b){
    ll c;
    while(b>0){
        c=a;
        a=b;
        b=c%a;
    }
    return a;
}

int main(){
    ll n; cin >> n;
    ll ans=0;
    rep(i,n){
        ll x;
        cin >> x;
        ans=gcd(x,ans);
    }
    cout << ans << endl;
}

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

struct mint{
    static const long long MOD = 1000000007;

    long long v;

    mint() : v(0) {}
    mint(long long x){
        x = x % MOD;
        if(x < 0){ x += MOD; }
        v = x;
    }
    mint& operator+=(mint a){
        v += a.v;
        if(v >= MOD){ v -= MOD; }
        return *this;
    }
    mint& operator*=(mint a){
        v *= a.v;
        v %= MOD;
        return *this;
    }
    mint& operator-=(mint a){
        v -= a.v;
        if(v < 0){ v += MOD; }
        return *this;
    }
    mint& operator/=(mint a){
        return (*this) *= a.inv();
    }

    mint operator*(mint a) const{
        return mint(v) *= a;
    }

    mint operator+(mint a) const {
        return mint(v) += a;
    }

    mint operator-(mint a) const {
        return mint(v) -= a;
    }

    mint operator/(mint a) const {
        return mint(v) /= a;
    }

    mint pow(long long k) const {
        mint res(1),tmp(v);
        while(k){
            if(k&1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    mint inv(){return pow(MOD - 2); }

    static mint comb(long long n, int k){
        mint res(1);
        for(int i = 0; i < k; ++i){
            res *= mint(n - i);
            res /= mint(i + 1);
        }
        return res;
    }

    static mint factorial(long long n){
        mint res(1);
        for(int i = n; i > 1; --i){
            res *= mint(i);
        }
        return res;
    }

    bool operator<(const mint &a) const {
        return v < a.v;
    };
};

mint operator*(long long l, mint r){ return r * l; }

std::ostream& operator<<(std::ostream& stream, const mint& m){
    stream << m.v;
    return stream;
}

void solve(long long X, long long Y){
    if(2 * Y - X < 0 || 2 * X - Y < 0 ||
       (2 * Y - X) % 3 != 0 || (2 * X - Y) % 3 != 0){
        cout << 0 << endl;
        return;
    }

    const ll A = (2 * Y - X) / 3;
    const ll B = (2 * X - Y) / 3;

    cout << mint::comb(A + B, A) << endl;
}

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


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, S: str, T: str):
    ans = []
    for s, t in zip(S, T):
        ans.extend([s, t])
    print("".join(ans))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(N, S, T)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],id;
vector<int> e[N];
map<int,int> M;
bool vis[N];
void dfs(int x){
	vis[x]=1;
	for (int i=0;i<e[x].size();i++)
	if (!vis[e[x][i]]) dfs(e[x][i]);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[0]^=a[i];
	for (int i=1;i<=n;i++) scanf("%d",&b[i]),b[0]^=b[i];
	for (int i=0;i<=n;i++) M[a[i]]++,M[b[i]]--;
	for (int i=0;i<=n;i++)
		if (M[a[i]]) return puts("-1"),0;
	for (int i=0;i<=n;i++)
		if (!M[a[i]]) M[a[i]]=++id;
	int ans=0;
	for (int i=0;i<=n;i++)
		if (a[i]!=b[i]) e[M[a[i]]].push_back(M[b[i]]),ans++;
	for (int i=1;i<=id;i++)
		if (!vis[i]&&!e[i].empty()) dfs(i),ans++;
	if (!e[M[a[0]]].empty()) ans--;
	if (a[0]!=b[0]) ans--;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 14336
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;
using itn = int;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a); i > (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define itn int
#define double ld
#define pb push_back
#define mp make_pair
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl lcm(intl a,intl b){
    return a / gcd(a, b) * b;
}
intl digit10(intl a){
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    string s;
    cin >> s;
    rep(i,3){
        if(s[i] == '1')cout << '9';
        else if (s[i] == '9')cout << '1';
        else cout << s[i];
    }
    return 0;
}

Measured memory_bytes: 256
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, x = LI()
A = LI()
original_sum = sum(A)
for aidx in range(N-1):
    if A[aidx] + A[aidx+1] <= x:
        continue
    else:
        diff = A[aidx] + A[aidx+1] - x
        sub = min(diff, A[aidx+1])
        A[aidx+1] -= sub
        diff -= sub
        if diff > 0:
            A[aidx] -= min(A[aidx], diff)

#  print(A)
ans = original_sum - sum(A)
print(ans)


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

int main(){
  ll a,b,x;
  cin >> a >>b >> x;
  if(a%x==0){
    cout << b/x-a/x+1 <<endl;
  }
  else{
    cout << b/x-a/x <<endl;
  }
}


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

int main(){
 ll a, b, n, m;
  cin >> a >> b >> n;
  m = min(n, b-1);
  ll y = (a*m)/b;
  
  cout << y << endl;
  return 0;
}

Measured memory_bytes: 3644
#include<stdio.h>
#define min(p,q)((p)<(q)?(p):(q))

//自分より真に大きいのが7人以下
//取る点としては、nかn+1だけを考慮すればよい

int n;
int s[110],t[110];
int a[3][110],x[110];

void f(int*p){
	for(int i=0;i<n;i++){
		int cnt=0;
		for(int j=0;j<n;j++)if(p[j]>p[i])cnt++;
		t[i]=x[cnt];
	}
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",x+i);
	for(int i=0;i<n;i++)scanf("%d%d%d",a[0]+i,a[1]+i,a[2]+i);
	int ans=1000;
	for(int k=0;k<3;k++){
		for(int i=0;i<n;i++)s[i]=0;
		for(int kk=0;kk<3;kk++)if(kk!=k){
			f(a[kk]);
			for(int i=0;i<n;i++)s[i]+=t[i];
		}

		int ori=a[k][0];
		for(int i=1;i<n;i++){
			for(int d=0;d<2;d++)if(a[k][i]+d>ori){
				a[k][0]=a[k][i]+d;
				f(a[k]);
				int cnt=0;
				for(int j=0;j<n;j++)if(s[j]+t[j]>s[0]+t[0])cnt++;
				if(cnt<=7)ans=min(ans,a[k][0]-ori);
			}
		}
		a[k][0]=ori;
	}
	if(ans==1000)puts("Saiko");
	else printf("%d\n",ans);
}


Measured memory_bytes: 2140
#define S scanf
d[1001],c;main(w,n,i,C,W,b){for(;S("%d",&w),w;printf("Case %d:\n%d\n%d\n",++c,d[w],b),bzero(d,4004))for(S("%d",&n);n--;)for(i=w,S("%d,%d",&C,&W);i>=W;i--)d[i]=fmax(d[i],d[i-W]+C),b=d[i]-d[w]?b:i;}

Measured memory_bytes: 0
#include<iostream>

using namespace std;

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

int main() {
  while (true) {
    int n;
    cin >> n;
    if (n == 0) break;
    int a[n];
    rep (i, n) cin >> a[i];
    int one = 0, two = 0;
    rep (i, n) if (a[i] == 1) ++one;
    rep (i, n) if (a[i] >= 2) ++two;
    if (two == 0) cout << "NA" << endl;
    else cout << one + two + 1 << endl;
  }
}

Measured memory_bytes: 1196
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;

int main() {
  int w, d;
  while(cin >> w >> d, d||w) {
    int a[21]={}, b[21]={};
    REP(i, w) {
      int x;
      cin >> x;
      a[x]++;
    }
    REP(i, d) {
      int x;
      cin >> x;
      b[x]++;
    }
    int res = 0;
    REP(i, 21) {
      res += i*max(a[i], b[i]);
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2){
        if (num % i == 0)  return false;
    }
    return true;
}
	
int main(){
	int x;	cin >> x;
  	int tmp = x;
  	while(!IsPrime(tmp)){tmp++;}
  	cout << tmp << endl;
}

Measured memory_bytes: 256
N = int(input())
l = input().split(" ")
P = [int(n) for n in l]

# i=1は必ずOK
c = 1
min = P[0]

for i in range(1,N):
  p = P[i]
  if p<=min:
    c+=1
    min=p
    
print(c)

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

#define ll long long int

int main(){
  
  ll n,k;cin>>n>>k;
  unordered_map<ll,ll> mp;
  
  for(ll i=0;i<k;i++){
  	ll d;cin>>d;
    for(ll j=0;j<d;j++){
    	ll x;cin>>x;
      	mp[x]=i;
    }
  }  
  
  cout<<n-mp.size()<<endl;
  
	return 0;	
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
#define pi acos(-1)
#define fastIO_ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int main()
{
    fastIO_
    ll a, n, s=0;
    cin>>a>>n;
    for (ll i=0, k; i<n; i++)
    {
        cin>>k;
        s +=k;
    }
    printf("%lld", a-s <0 ? -1: a-s);
    return 0;
}

Measured memory_bytes: 3772
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 2000000
#define INFTY 1 << 30
#define parent(x) x / 2
#define left(x) x * 2
#define right(x) x * 2 + 1

int H, A[MAX + 1];

void maxHeapify(int i)
{
	int l = left(i);
	int r = right(i);

	if (l > H) return;
	else if (r > H)
	{
		if (A[i] < A[l])
		{
			int temp = A[i];
			A[i] = A[l];
			A[l] = temp;
		}
		else return;
	}
	else
	{
		if (A[i] >= A[l] && A[i] >= A[r]) return;
		int large = A[l] > A[r] ? l : r;
		int temp = A[i];
		A[i] = A[large];
		A[large] = temp;
		maxHeapify(large);
	}
}

int extract()
{
	int maxv;
	if (H < 1)
		return -INFTY;
	maxv = A[1];
	A[1] = A[H--];
	maxHeapify(1);
	return maxv;
}

void increaseKey(int i, int key)
{
	if (key < A[i])
		return;
	A[i] = key;
	while (i > 1 && A[i / 2] < A[i])
	{
		swap(A[i], A[i / 2]);
		i = i / 2;
	}
}

void insert(int key)
{
	A[++H] = -INFTY;
	increaseKey(H, key);
}

int main()
{
	int key;
	char com[10];
	while (1)
	{
		scanf("%s", com);
		if (com[0] == 'e' && com[1] == 'n')
			break;
		if (com[0] == 'i')
		{
			scanf("%d", &key);
			insert(key);
		}
		else
		{
			printf("%d\n", extract());
		}
	}
	return 0;
}


Measured memory_bytes: 6488