akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

	map<int,int> mp;

	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if(mp[a] == 0) mp[a]++;
		else mp[a]--;
	}
	
	int ans = 0;

	for (auto it : mp) {
		if (0 < it.second) ans++;
	}

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long in;
typedef pair<in,in> ii;
#define F first
#define S second
#define sqr(x) (x)*(x)
#define pb(x) push_back(x)
#define sz(x) (in)x.size()
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rep(i,x,y) for(in i=x;i<(y);++i)
#define per(i,x,y) for(in i=y;i>=(x);--i)
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
/* start */

int main()
{
      IOS;
      string s,t;
      cin >> s >> t;
      t+=s;
      cout << t << "\n";
}

Measured memory_bytes: 256
<?php

list($N, $Y) = explode(" ", trim(fgets(STDIN)));

$MAN = 10000;
$GOSEN = 5000;
$SEN = 1000;

for($i=0; $i<=$N; $i++){
    for($j=0; $i+$j<=$N; $j++){//終了条件注意
        $c = $N - ($i + $j);
        if($i * $MAN + $j * $GOSEN + $c * $SEN == $Y){
            echo $i, " ", $j, " ", $c;
            exit;
        }
    }    
}
echo "-1 -1 -1";

?>

Measured memory_bytes: 4604
package main

import (
	"fmt"
	"math"
)

func main() {
	var N int
	fmt.Scan(&N)
	a := make([]int, N)
	for i := range a {
		fmt.Scan(&a[i])
	}
	minSum := math.MaxInt64
	for x := -100; x <= 100; x++ {
		sum := 0
		for _, y := range a {
			sum += (x - y) * (x - y)
		}
		if sum < minSum {
			minSum = sum
		}
	}
	fmt.Println(minSum)
}


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

int  main ()  { 
    int  a ,  b ; 
    cin  >>  a  >>  b ; 
    int  c  =  a  *  b ; 
    if  ( c  %  2  ==  0 )  cout  <<  "Even"  <<  endl ; 
    else  cout  <<  "Odd "  <<  endl ; 
}

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

class Problem0009
{
    static void Main(string[] args)
    {
        int[] primeCounts = new int[1000000];
        int currentCount = 0;
        for (int i = 1; i <= 999999; i++)
        {
            if (IsPrime(i))
            {
                currentCount++;
            }
            primeCounts[i] = currentCount;
        }

        foreach (int n in GetInputLines().Select(int.Parse))
        {
            Console.WriteLine(primeCounts[n]);
        }
    }

    static bool IsPrime(int n)
    {
        if (n < 2)
        {
            return false;
        }
        else
        {
            return Enumerable.Range(2, (int)Math.Sqrt(n) - 1).All(i => n % i != 0);
        }
    }

    static IEnumerable<string> GetInputLines()
    {
        string line;
        while (!string.IsNullOrEmpty(line = System.Console.ReadLine()))
        {
            yield return line;
        }
    }
}

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

int main() {
	int N;
	cin >> N;
	int d[110];
	for (int i = 0; i < N; ++i) {
		cin >> d[i];
	}

	sort(d, d + N);
	
	int count = 1;
	for (int i = 0; i < N-1; ++i) {
		if (d[i] != d[i + 1]) {
			count += 1;
		}
	}

	cout << count << endl;
}

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

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)

int main()
{
	FASTIO
	int val[4], var[3] = {0};
	rep(i,0,4) cin >> val[i];
	for(int i=0; i<3 && val[3] != 0; i++)
	{
		var[i] = (val[i] >= val[3]) ? val[3] : val[i];
		val[3] -= var[i];
	}
	cout << var[0] - var[2] << "\n"; 
	return 0;
}

Measured memory_bytes: 3648
n = gets.to_i
numbers = []
n.times { numbers << gets.to_i } 
# 使っている色の数と、それぞれの塗られている整数の最大値を格納するcolors配列
# 例えば[1, 4, 9]の場合、1まで塗られた色、4まで塗られた色、9まで塗られた色の計3色が存在する
colors = [-1]
numbers.each do |number|
  # 自身よりも小さい（ただしその中では1番大きい）番号の色を探す
  if index = colors.bsearch_index { |x| number > x }
    # 存在する場合は、自身の番号に更新する
    colors[index] = number
  else
    # 存在しない場合は、新たな色として自身の番号をcolorsに加える
    colors << number
  end
end
# 最終的な色の数を出力する
puts colors.size

Measured memory_bytes: 3764
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

struct edge {
    int from, to; ll cost;
    edge(int s, int t, ll w = 0) : from(s), to(t), cost(w) {}
};
bool tpz(vector<vector<edge>> g, VI& ans, VI& len) {
    int v = g.size(); ans.clear(), len.resize(v, 0);
    vector<int> in(v, 0);
    for (auto es : g)for (edge e : es)in[e.to]++;
    queue<int> que;
    FOR(i, 0, v)if (in[i] == 0) {
        que.push(i);
        len[i] = 1;
    }

    while (!que.empty()) {
        int now = que.front(); que.pop();
        ans.push_back(now);
        for (edge next : g[now]) {
            if (--in[next.to] == 0) {
                que.push(next.to);
                chmax(len[next.to], len[now] + 1);
            }
        }
    }
    return v == ans.size();
}

int main() {
    init();

    int n;
    cin >> n;
    vector<VI> a(n, VI(n)), wh(n, VI(n, -1));
    FOR(i, 0, n)FOR(j, 0, n - 1) {
        cin >> a[i][j];
        wh[i][--a[i][j]] = j;
    }

    vector<vector<edge>> g(n * (n - 1) / 2);
    map<pair<int, int>, int> map;
    int o = 0;
    FOR(i, 0, n)FOR(j, 0, n - 1) {
        int x = i, y = a[i][j];
        if (x > y)swap(x, y);
        if (map[{x, y}])continue;
        if ((i != 0 || j != 0) && (x == 0 && y == a[0][0]))continue;
        map[{x, y}] = o++;
    }
    FOR(i, 0, n)FOR(j, 0, n - 2) {
        int x = i, y = a[i][j], X = i, Y = a[i][j + 1];
        if (x > y)swap(x, y);
        if (X > Y)swap(X, Y);
        g[map[{ x, y }]].emplace_back(map[{ x, y }], map[{ X, Y }], 1);
    }
    
    VI ans, len;
    if (tpz(g, ans, len)) {
        int mlen = 0;
        for (int i : len)chmax(mlen, i);
        cout << mlen << "\n";
    }
    else cout << "-1\n";
}


Measured memory_bytes: 117488
# -*- coding: utf-8 -*-
i = 0
while True:
    a, b = map(int, input().split())

    if a == 0 and b == 0:
        break
    elif i != 0:
        print()

    found = False
    for y in range(a, b + 1):
        if y % 4 == 0 and (y % 100 != 0 or y % 400 == 0):
            found = True
            print(y)
    if not found:
        print('NA')
        
    i += 1

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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> VI;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;
typedef tuple<ll, ll, ll, ll, ll> t5;

#define rep(a,n) for(ll a = 0;a < n;a++)
#define repi(a,b,n) for(ll a = b;a < n;a++)

using namespace std;

static const ll INF = 1e15;

const ll mod = 1000000007;


int main() {
	ll n;
	cin >> n;
	vector<ll> as(n);
	rep(i, n)cin >> as[i];
	sort(as.begin(), as.end(), greater<ll>());
	ll ans = as[0];
	n -= 2;
	int i = 1;
	while (n > 0) {
		if (n > 1) {
			ans += as[i] * 2;
			n -= 2;
		}
		else {
			ans += as[i];
			n--;
		}
		i++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4764
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

x1, y1, x2, y2 = nm()

lx = x2-x1
ly = y2-y1

print(x2-ly)
print(y2+lx)
print(x1-ly)
print(y1+lx)

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

int main(){
  int N;
  cin>>N;
  vector<int> A(N+2);
  A.at(0)=0;
  A.at(N+1)=0;
  int yen=0;
  for(int i=1;i<=N;++i){
    cin>>A.at(i);
    yen=yen+abs(A.at(i)-A.at(i-1));
  }
  yen=yen+abs(A.at(N));

  for(int i=1;i<=N;++i){
    cout<<yen-abs(A.at(i)-A.at(i-1))-abs(A.at(i)-A.at(i+1))+abs(A.at(i+1)-A.at(i-1))<<endl;
  }
}

Measured memory_bytes: 1664
/*** akshaykumar99 ***/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using id_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update> ;
 
#define f(i,x,n) for(i=x;i<n;i++)
#define fr(i,x,n) for(i=x;i>=n;i--)
#define pu push_back           
#define pp pop_back
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SP(x) fixed<<setprecision(x)
#define IOS() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
const long long MOD = 1e9+7;
const long double PI = acos(-1);
const long long INF = INT_MAX;
const long long LINF = LLONG_MAX;
const long long N = 1e5+1;
 
typedef int ll;
typedef long double ld;  

void test_case()
{
    string s, res = "";
    cin >> s;
    ll n = s.size(),i;
    f(i,0,n)
    {
        if(s[i]!='?')
            res+=s[i];
        else
        {
            res+='D';
        }
    }
    cout << res << '\n';

}

int32_t main()
{
    IOS(); 
    
    int tc=1;
    // cin>>tc;
    while(tc--)
        test_case();
    return 0;
}

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

int main(){
  int n,k;
  string s;
  cin >> n >> k >> s;

  if(s[k-1]=='A') s[k-1]='a';
  else if(s[k-1]=='B') s[k-1]='b';
  else s[k-1]='c';

  cout << s << endl;
}

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

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

    int i_a = -1;
    int i_z = -1;
    for (size_t i = 0; i < s.size(); ++i) {
        if (i_a < 0 && s[i] == 'A') {
            i_a = i;
        } 

        if (s[i] == 'Z') {
            i_z = i;
        }
    }

    std::cout << i_z - i_a + 1 << std::endl;

    return 0;
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define rt return
using dbl = double;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

int N;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    vll a(N);
    ll S = 0;
    rep(i, N) {
        cin >> a[i];
        S += a[i];
    }

    for (ll x = max(0ll, S - N*(N - 1)); x <= S; ++x) {
        ll y = 0;
        rep(i, N) {
            y += (a[i] + x + 1) / (N + 1);
            if (y > x)break;
        }
        if (y == x) {
            cout << x << endl;
            break;
        }
    }
}


Measured memory_bytes: 256
import qualified Data.Map as MP
import Data.Maybe
import Data.List

primeFactor :: MP.Map Int Int -> Int -> MP.Map Int Int
primeFactor m n = loop n 2 m
    where
        loop :: Int -> Int -> MP.Map Int Int ->  MP.Map Int Int
        loop n i m
            | n `rem` i == 0 = inner n i m
            | i * i > n = if n /= 1 
                then
                    case MP.lookup n m of
                        Just _ -> MP.adjust (+1) n m
                        Nothing -> MP.insert n 1 m
                else m 
            | otherwise = loop n (i+1) m
        
        inner ::  Int -> Int -> MP.Map Int Int -> MP.Map Int Int
        inner n i m
            | n `rem` i == 0 =
                let
                    m' = case MP.lookup i m of
                        Just _ -> MP.adjust (+1) i m
                        Nothing -> MP.insert i 1 m
                in
                    inner (n `quot` i) i m'
            | otherwise = loop n (i+1) m

solve :: Int -> Int
solve n = loop m
    where
        m = foldl' primeFactor MP.empty [2..n] 
        mulMod a b = (a * b) `rem` (10^9+7)
        loop :: MP.Map Int Int -> Int
        loop m 
            | MP.null m = 1
            | otherwise =
                let 
                    ((_, v), m') = MP.deleteFindMin m
                in
                    mulMod (v+1) $ loop m'

main = do
    n <- readLn :: IO Int
    print $ if n == 1 then 1 else solve n


Measured memory_bytes: 1020
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fi first
#define se second

typedef long long LL;
typedef std:: pair <LL,int> pair;
const LL INF=1e15;
const int MOD=1000000007;
const int N=200005;
const int E=500005;

struct edge {int x,y; LL w; int next;} e[E];

LL cnt[2][N],dis[2][N];
int ls[N],edCnt,n;

bool vis[N];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void add_edge(int x,int y,LL w) {
	e[++edCnt]=(edge) {x,y,w,ls[x]}; ls[x]=edCnt;
	e[++edCnt]=(edge) {y,x,w,ls[y]}; ls[y]=edCnt;
}

void dijk(int st,int ed,LL *dis,LL *cnt) {
	rep(i,0,n) dis[i]=INF; dis[st]=0;
	rep(i,0,n) cnt[i]=0; cnt[st]=1;
	rep(i,0,n) vis[i]=0;
	std:: priority_queue <pair> heap;
	for (heap.push(pair(0,st));!heap.empty();) {
		pair top=heap.top(); heap.pop();
		int x=top.se;
		if (vis[x]) continue; vis[x]=1;
		for (int i=ls[x];i;i=e[i].next) {
			if (dis[x]+e[i].w<dis[e[i].y]) {
				dis[e[i].y]=dis[x]+e[i].w;
				heap.push(pair(-dis[e[i].y],e[i].y));
				cnt[e[i].y]=cnt[x];
			} else if (dis[x]+e[i].w==dis[e[i].y]) {
				cnt[e[i].y]+=cnt[x]; cnt[e[i].y]%=MOD;
			}
		}
	}
}

int main(void) {
	n=read(); int m=read();
	int st=read(),ed=read();
	rep(i,1,m) {
		int x=read(),y=read(),w=read();
		add_edge(x,y,w);
	}
	dijk(st,ed,dis[0],cnt[0]);
	dijk(ed,st,dis[1],cnt[1]);
	LL len=dis[0][ed];
	LL ans=cnt[0][ed]*(cnt[0][ed]-1)%MOD;
	rep(i,1,n) if (dis[0][i]==dis[1][i]&&dis[0][i]*2==len) {
		LL tmp=cnt[0][i]*cnt[1][i]%MOD;
		ans=(ans+MOD-tmp*(tmp-1)%MOD)%MOD;
	}
	for (int i=1;i<edCnt;i+=2) {
		int x=e[i].x,y=e[i].y; LL w=e[i].w;
		if (dis[0][x]>dis[0][y]) std:: swap(x,y);
		if (dis[0][x]+w+dis[1][y]==len&&dis[0][x]*2<len&&dis[1][y]*2<len) {
			LL tmp=cnt[0][x]*cnt[1][y]%MOD;
			ans=(ans+MOD-tmp*(tmp-1)%MOD)%MOD;
		}
	}
	ans=(ans%MOD+MOD)%MOD;
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 21460
#include<stdio.h>
#define ll long long
ll max(ll a,ll b){return a > b ? a: b;}
ll dp[111111];
int main(){
    ll n, W, i, j, ans;
    scanf("%lld%lld",&n,&W);
    ll w[n], v[n];
    for(i = 0; i < n; i++)
        scanf("%lld%lld",&w[i],&v[i]);
    for(i = 0; i < n; i++)
        for(j = W; j >= 0; j--){
            if(j + w[i] <= W)
                dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]);
        }
    ans = dp[0];
    for(i = 1; i <= W; i++)
        ans = max(ans, dp[i]);
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 896
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = []
ans = 0
m = 0
if sum(a) < sum(b):
    print(-1)
    exit()
for i in range(n):
    if a[i] < b[i]:
        ans += 1
        m += b[i] - a[i]
    else:
        l.append(a[i] - b[i])
l = list(reversed(sorted(l)))
for i in l:
    if m > 0:
        m -= i
        ans += 1
print(ans)


Measured memory_bytes: 24104
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int Y = sc.nextInt();
		int Z = sc.nextInt();
		sc.close();
		int a = Y;
		int b = X;
		int c = a;
		a = Z;
		System.out.println(a + " " + b + " " + c);
	}
}


Measured memory_bytes: 22228
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;
typedef long long ll;

const int    INF = 1000000000;
const int    MOD = 1000000007;
const double EPS = 1e-8;

int N, E, Q;
int cap[500][500];
bool used[500];
int dfs(int u, int t, int f){
    if(u == t) return f;
    used[u] = true;
    REP(v, N)if(!used[v] && cap[u][v] > 0){
        int d = dfs(v, t, min(f, cap[u][v]));
        if(d > 0){
            cap[u][v] -= d;
            cap[v][u] += d;
            return d;
        }
    }
    return 0;
}
int run(int s, int t, int f){
    memset(used, 0, sizeof used);
    return dfs(s, t, f);
}
int main(){
    while(cin >> N >> E >> Q && N){
        memset(cap, 0, sizeof cap);
        REP(_, E){
            int F, T;
            cin >> F >> T;
            F--; T--;
            cap[F][T] = 1;
            cap[T][F] = 1;
        }
        int flow = 0;
        REP(_, Q){
            int M, A, B;
            cin >> M >> A >> B;
            A--; B--;
            if(M == 1){ // add edge
                assert(cap[A][B] == 0 && cap[B][A] == 0); // assert no edge
                cap[A][B] = cap[B][A] = 1; // add edge
            }else{ // delete edge
                if(cap[A][B] == 2) swap(A, B);
                if(cap[B][A] == 2 && run(A, B, 1) == 1){ // remove cycle
                    cap[B][A] = cap[A][B] = 1;
                }
                if(cap[B][A] == 2){ // flowing 0->A->B->N-1
                    assert(flow > 0);
                    assert(run(N - 1, 0, 1) == 1); // N-1 -> 0
                    flow--;
                }
                if(cap[B][A] == 2){ // remove cycle
                    assert(run(A, B, 1) == 1);
                    cap[B][A]--;
                    cap[A][B]++;
                }
                assert(cap[A][B] == 1 && cap[B][A] == 1); // assert no flowing
                cap[A][B] = cap[B][A] = 0; // remove edge
            }
            // update flow
            while(true){
                int f = run(0, N - 1, 2);
                if(f == 0) break;
                flow += f;
            }
            cout << flow << endl;
        }
    }
    return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define MAX_N 100000
#define MAX_W 10000
typedef long long ll;

int N, K;
ll T[MAX_N];

bool isCarryAble(ll P) {
    int able_num = 0;
    rep(i, K) {
        ll sum = 0;
        while(sum + T[able_num] <= P) {
            sum += T[able_num];
            ++able_num;
            if(able_num == N) return true;
        }
    }
    return false;
}

int solveP() {
    ll left  = 0;
    ll right = MAX_N * MAX_W;
    ll mid;
    while(right - left > 1) {
        mid = (left + right) / 2;
        if(isCarryAble(mid)) right = mid;
        else                 left  = mid;
    }
    return right;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    rep(i, N) cin >> T[i];

    cout << solveP() << "\n";

    return 0;
}


Measured memory_bytes: 3940
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String stringX = sc.next();
		
		if (stringX.length() <= 2) { 
			System.out.println(0);
			System.exit(0);
		}
		
		int a = Integer.parseInt(stringX.substring(stringX.length() -2));
		int b = Integer.parseInt(stringX.substring(0,stringX.length() -2));
		
		if (a <= b*5) {
			System.out.println(1);
		}else {
			System.out.println(0);
		}
		
	
	}



}


Measured memory_bytes: 21844
#include <iostream>
using namespace std;
int main(){
    int N;
    int error=0;
    int T[100000],X[100000],Y[100000];
    cin >> N;
    T[0]=0;
    X[0]=0;
    Y[0]=0;
    int xsa;
    int ysa;
    int tsa;
    for(int i=1;i<=N;i++){
        cin >> T[i] >> X[i] >> Y[i];
    }
    for(int j=1;j<=N;j++){
        xsa=abs(X[j]-X[j-1]);
        ysa=abs(Y[j]-Y[j-1]);
        tsa=abs(T[j]-T[j-1]);
        if((xsa+ysa)>tsa){
            error++;
            break;
        }
        else if( (xsa+ysa)%2 != tsa%2){
            error++;
            break;
        }
    }
    if(error==1){
        cout << "No" << endl;
    }
    else{
        cout << "Yes" << endl;
    }
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000;
int n;
ll x[maxn + 10], y[maxn + 10];

bool comb(ll x, ll y) {
	if (y < 0 || y > x) return 0;
	return (x & y) == y;
}

bool calc(ll xx, ll yy) {
	bool ans = 0;
	for (int i = 1; i <= n; ++i)
		ans ^= comb(x[i] - xx, yy - y[i]);
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%lld%lld", &x[i], &y[i]);
	ll xx = -2e17, yy = 0;
	for (int i = 60; i >= 0; --i)
		if (calc(xx, yy | (1ll << i))) yy |= 1ll << i;
	printf("%lld", xx + yy);
}


Measured memory_bytes: 1792
N=int(input())
P=list(map(int,input().split()))

i=0
ANS=0

while i<N:
    if i+1<N and P[i]==i+1 and P[i+1]==i+2:
        ANS+=1
        i+=2

    elif P[i]==i+1:
        ANS+=1
        i+=1

    else:
        i+=1

print(ANS)


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

long long N;
long long A[305][305];
long long d[305][305];

int main(){
	cin >> N;
	bool check = true;
	for(long long i = 0; i < N; i++){
		for(long long j = 0; j < N; j++){
			cin >> A[i][j];
			d[i][j] = A[i][j];
			if(i == j && A[i][j] != 0){
				check = false;
			}
		}
	}

	if(check == false){
		cout << -1 << endl;
		return 0;
	}


	for(int k = 0; k < N; ++k){
		for(int i = 0; i < N; ++i){
			for(int j = 0; j < N; ++j){
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}

	for(int i = 0; i < N; ++i){
		for(int j = 0; j < N; ++j){
			if(d[i][j] != A[i][j]){
				cout << -1 << endl;
				return 0;
			}
		}
	}


	long long num = 0;
	for(int i = 0; i < N; ++i){
		for(int j = 0; j < N; ++j){
			bool use = true;
			for(int k = 0; k < N; ++k){
				if(k == i || k == j){
					continue;
				}
				if(d[i][j]  == d[i][k] + d[k][j]){
					use = false;
				}
			}
			if(use){
				num += d[i][j];
			}
		}
	}
	cout << num/2 << endl;
}


Measured memory_bytes: 1664
#include <iostream>
#include <stdio.h>
#include <vector> 
#include <math.h> 
using namespace std;
int main(void){
    int h, w, k; cin >> h >> w >> k;
    vector<vector<char> > m(h, vector<char>(w));
    vector<vector<char> > p(h, vector<char>(w));
    int i = 0; int j = 0; 
    int ans = 0;
    while (h > i) {
        j = 0;
        while (w > j) {
            cin >> m.at(i).at(j);
            j++;
        }
        i++;
    }
    for (int bit = 0; bit < (1<<h); ++bit) {
        for (int bit2 = 0; bit2 < (1<<w); ++bit2) {
            p = m;
            for (int i = 0; i < h; ++i) {
                if (bit & (1<<i)) { // 列挙に i が含まれるか
                    int c = 0;
                    while(c < w) {
                        p.at(i).at(c) = 'a';
                        c++;
                    }
                }
            }
            for (int i = 0; i < w; ++i) {
                if (bit2 & (1<<i)) { // 列挙に i が含まれるか
                    int c = 0;
                    while(c < h) {
                        p.at(c).at(i) = 'a';
                        c++;
                    }
                }
            }
            int count = 0;
            i = 0;
            while (h > i) {
                j = 0;
                while (w > j) {
                    if (p.at(i).at(j) == '#') count++;
                    j++;
                }
                i++;
            }
            if (count == k) ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3616
n=int(input())
a=[int(i) for i in input().split()]
flag=False
ans_flag=True
for i in range(1,n):
  if(a[i-1]>a[i]):
    for j in range(n-2,-1,-1):
      if(a[j]>a[j+1]):
        tmp=a[i-1]
        a[i-1]=a[j+1]
        a[j+1]=tmp
        flag=True
        break
  if(flag==True):
    break
for i in range(n-1):
  if(a[i]>a[i+1]):
    print("NO")
    ans_flag=False
    break
if(ans_flag==True):
  print("YES")

Measured memory_bytes: 3064
/*
 * Author: .-O_O-.
 */
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define rep0(a,b) for(int a=0;a<b;a++)
#define rep1(a,b) for(int a=1;a<=b;a++)
#define repp(a,b,c) for(int a=b;a<c;a++)
#define in insert
#define len length()
#define si size()
#define lb lower_bound
#define ub upper_bound
#define beg begin()
#define en end()
#define f first
#define s second
#define pr(a) cout<<a
#define pr2(a,b) cout<<a<<" "<<b<<"\n"
#define nx cout<<"\n"
#define int long long
// 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 << "]"<<endl;}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif
const ll mod = 1000000007;
const ll N = 105;
const ll mm = 1e+18;
void solve()
{
    int n;
    string s;
    cin>>n>>s;
    int mx=0;
    int x=0;
    rep0(i,n){
        if(s[i]=='I') x++;
        else x--;
        mx=max(mx,x);
    }
    pr(mx);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    rep1(_i,t){
        //cout<<"Case #"<<_i<<": ";
        solve();
        //nx;
    }
    return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int m,n;
  cin >> n >> m;
  int t = 1;
  REP(i,m) t *=2;
  cout << (1900*m+100*(n-m))*t << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
using namespace std;

int main(){
    int N,A,B,x,keta,m,y;
    cin>>N>>A>>B;
    long long sum=0;

    for(int n=1;n<=N;n++){
        x=n;
        y=n;
        keta=0;
        for(int k=4;k>=0;k--){
            int p=pow(10,k);
            m=y/p;
            keta+=m;
            y=y%p;
        }
        if(A<=keta&&keta<=B){
            sum+=x;
        }
    }
    cout<<sum<<endl;
    return 0;

}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val abcd = sc.next().map { it.toString().toInt() }

    println(rec(abcd.drop(1), abcd.first().toString(), abcd.first()) + "=7")
}

private fun rec(values: List<Int>, ce: String, cur: Int): String? {
    val v = values.firstOrNull() ?: return if (cur == 7) ce else null

    rec(values.drop(1), ce + "+" + v, cur + v)?.run { return this }
    rec(values.drop(1), ce + "-" + v, cur - v)?.run { return this }

    return null
}

Measured memory_bytes: 31264
l = [int(i) for i in input().split(" ")]
n = l[0]
m = l[1]
x = l[2]
y = l[3]
z_set = set(range(x+1,y+1))
if len(z_set) == 0:
    print("War")
else:
    x_max = max([int(i) for i in input().split(" ")])
    y_min = min([int(i) for i in input().split(" ")])
    x_y_set = set(range(x_max+1,y_min+1))
    if len(x_y_set & z_set) == 0:
        print("War")
    else:
        print("No War")


Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>

using namespace std;

const int MAXM=6;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<=n;i++)

int N,M;
int s[MAXM],c[MAXM];

bool ok(int x) {
  int bin[MAXM];
  int i = N;
  while(1) {
    bin[i] = x%10; 
    i--;
    x /= 10;
    if(i==0)break;
  }
  bool flag = true;
  rep(i,M) {
    if(bin[s[i]] != c[i])flag = false;
  }

  return flag;
}

int main() {
  

  cin >> N >> M;
  rep(i,M) cin >> s[i] >> c[i];


  int max_digit = 1;
  int min_digit = 1;
  if(N == 1) {
    max_digit = 10;
    min_digit = 0;
  }else{
    rep(i,N){
      max_digit *= 10;
      min_digit *= 10;
    }
    min_digit /= 10;
  }
  int k;
  for(k=min_digit;k<max_digit;k++) {
    if(ok(k)) {
      cout << k << endl;
      return 0;
    }
  }

  cout << -1 << endl;



  return 0;
}

Measured memory_bytes: 3536
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define F               first
#define S               second
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18 + 1
#define endl            '\n'
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define forI(i,a,n)     for(int i=a;i<=n;i++)
#define forD(i,a,n)     for(int i=n;i>=a;i--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
void init(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

void solve(){
    int h, w;   cin>>h>>w;
    int dp[h+1][w+1];
    char grid[h+1][w+1];
    memset(dp, 0, sizeof dp);
    forI(i, 1, h)   forI(j, 1, w){
        cin>>grid[i][j];
        if(grid[i][j] == '#')   dp[i][j] = -1;
    }

    forI(i, 1, h){
        if(dp[i][1] == -1) break;
        dp[i][1] = 1;
    }
    forI(i, 1, w){
        if(dp[1][i] == -1)    break;
        dp[1][i] = 1;
    }

    forI(i, 2, h)   forI(j, 2, w){
        if(dp[i][j] == -1)  continue;
        if(dp[i-1][j] != -1)    dp[i][j] = (dp[i][j]%mod + dp[i-1][j]%mod)%mod;
        if(dp[i][j-1] != -1)    dp[i][j] = (dp[i][j]%mod + dp[i][j-1]%mod)%mod;
    }

    cout<<dp[h][w]<<endl;
}

int32_t main(){
    init();
    // w(t) 
    solve();
    return 0;
}

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

d_list = []
for i in range(n):
    d_list.append(int(input()))

d_list = list(set(d_list))
# イメージのため 問題に回答する上でこの処理は不要
d_list = sorted(d_list, reverse = True)

ans = len(d_list)

print(ans)


Measured memory_bytes: 9072
import sys

A , B , C, X, Y = map(int,input().split())

if X >= Y:
    
    a = X * A + Y * B
    b = 2 * Y * C + (X - Y) * A
    c = 2 * X * C
    
    res = min([a,b,c])
    
if  X < Y:
    
    a = X * A + Y * B
    b = 2 * X * C + (Y - X) * B
    c = 2 * Y * C
    
    res = min([a,b,c])
print(res)

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

int main()
{
    int N;
    int L;
    cin >> N;
    cin >> L;
    vector<string> S(N);
    for(int i = 0;i < N;i++)
    {
        cin >> S[i];
    }
    sort(S.begin(),S.end());

    for(int i = 0;i < N;i++)
    {
        cout << S[i];
    }

    return 0;
    
}

Measured memory_bytes: 256
#include<cmath>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<functional>
#define INF 1e16
#define N (1000000000+7)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> Q;

ll dp[200010];

int main(void){
    string s;
    cin>>s;
    dp[0]=0;
    int n = s.length();
    for(ll i=0;i<n;i++){
        if(s[i]=='?')s[i]='D';
    }
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 3752
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int minp[N],a[N],n;
int ret[N];
int gcd(int x,int y){
  return y?gcd(y,x%y):x;
}
int main(){
  scanf("%d",&n);
  for(int i=2;i<=1000000;i++){
    for(int j=i;j<=1000000;j+=i){
      if(!minp[j])minp[j]=i;
      else minp[j]=min(minp[j],i);      
    }
  }
  int GCD=0;
  for(int i=1;i<=n;i++){
    int x;
    scanf("%d",&x);
    GCD=gcd(GCD,x);
    while(x>1){
      int mi=minp[x];
      while(minp[x]==mi)x/=minp[x];
      ret[mi]++;
    }
  }
  int flag=1;
  for(int i=1;i<=1000000;i++){
    if(ret[i]>=2){
      flag=0;
      break;
    }
  }
  if(flag){
    puts("pairwise coprime");
    exit(0);
  }
  if(GCD==1){
    puts("setwise coprime");
    exit(0);
  }
  puts("not coprime");
  return 0;
}

Measured memory_bytes: 11576
#include<stdio.h>
#define NUMBER 300
int main(void){
    int H[NUMBER],W[NUMBER],i,j,k,c=0;
    for(i=0;i<NUMBER;i++){
       scanf("%d %d",&H[i],&W[i]);
       if(H[i]==0&&W[i]==0)
         break;
       c++;
    }
    for(i=0;i<c;i++){
       for(j=0;j<H[i];j++){
          for(k=0;k<W[i];k++){
             if(j==0||j==(H[i]-1)||k==0||k==(W[i]-1))
               putchar('#');
             else
               putchar('.');
          }
       putchar('\n');
       }
    putchar('\n');
    }
    return 0;
}


Measured memory_bytes: 2052
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(
					System.in));
			String[] strArray;		
			long sum = 0;
			int num ,max, min;
			
			int n = Integer.parseInt(br.readLine());
			strArray = br.readLine().split("\\s");

			max = Integer.parseInt(strArray[0]);
			min = Integer.parseInt(strArray[0]);
			
			for (int i = 0; i < n; i++) {
				num = Integer.parseInt(strArray[i]);
				if (max < num) {
					max = num;
				} else if (min > num) {
					min = num;
				}
				sum += num;
			}
			br.close();
			System.out.println(min +" "+ max +" "+ sum);
		} catch (Exception e) {
			System.err.println(e);
		}
	}
}

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

using namespace std;

int main()
{
    int a,b,c,k,k1;
    cin>>a>>b>>c>>k;
    int sum;
    if(k>0) {
        sum+=a;
        k-=a;
        if(k<0) sum+=k;
        if(k>0) k-=b;
        if(k>0) sum-=k;
    }
    cout<<sum<<endl;
}


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

int W, H, N;
int x[110], y[110], a[110];
int l,r,b,t;

int main()
{
    cin >> W >> H >> N;

    l=0,r=W,b=0,t=H;

    for (int i = 0; i < N; i++)
    {
        cin >> x[i] >> y[i] >> a[i];
    }

    for (int i = 0; i < N; i++)
    {
        if (a[i] == 1)
        {
            if (x[i] >= l)
                l = x[i];
        }
        else if (a[i] == 2)
        {
            if (x[i] <= r)
                r = x[i];
        }
        else if (a[i] == 3)
        {
            if (y[i] >= b)
                b = y[i];
        }
        else
        {
            if (y[i] <= t)
                t = y[i];
        }
    }
    
    if(r-l<0 || t-b<-0 ) cout << 0 << endl;
    else cout << (r-l) * (t-b) << endl;

    return 0;
}


Measured memory_bytes: 256
// AOJ 2007 "Make Purse Light" (ICPC模擬国内予選 2005 Problem B)
import java.util.Scanner;

public class Main {
    static final int[] price = {10, 50, 100, 500};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = 0; // テストケースの個数
        
        while (true) {
            int pay = sc.nextInt();
            if (pay == 0) {
                break;
            }
            
            count++;
            int[] coin = new int[4]; // coin[0-3]: 10, 50, 100, 500円硬貨の枚数
            int[] result = new int[4];
            for (int i = 0; i < coin.length; i++) {
                coin[i] = sc.nextInt();
            }
            
            int total = coin[0] * 10 + coin[1] * 50 + coin[2] * 100 + coin[3] * 500;
            change(total - pay, result);
            if (count > 1) {
                System.out.println();
            }
            for (int i = 0; i < coin.length; i++) {
                int n = coin[i] - result[i];
                if (n > 0) {
                    System.out.println(price[i] + " " + n);
                }
            }
        }
    }
    
    public static void change(int total, int[] result) {
        for (int i = price.length - 1; i >= 0; i--) {
            int n = total / price[i];
            result[i] += n;
            total -= n * price[i];
        }
    }
}

Measured memory_bytes: 34136
import itertools

N, M = map(int, input().split())
bulbs = [] * M
for i in range(M):
    bulb = list(map(int, input().split()))
    del bulb[0]
    bulbs.append(bulb)
p = list(map(int, input().split()))
seqs = list(itertools.product((0, 1), repeat=N))
for i_bulbs in range(len(bulbs)):
    target = []
    for i_seqs in range(len(seqs)):
        count = 0
        for num in bulbs[i_bulbs]:
            count += seqs[i_seqs][num - 1]
        if count % 2 != p[i_bulbs]:
            target.append(i_seqs)
    for i in reversed(target):
        del seqs[i]
    if not len(seqs):
        break
print(len(seqs))


Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {
    public static void debug(String str) {
        System.out.println(str);
    }

    public static void main(String[] args) {

        String S;
        String T;

        try (Scanner sc = new Scanner(System.in)) {
            S = sc.next();
            T = sc.next();
        }
        int cnt = 0;
        if(S.charAt(0) == T.charAt(0)){
            cnt++;
        }
        if(S.charAt(1) == T.charAt(1)){
            cnt++;
        }
        if(S.charAt(2) == T.charAt(2)){
            cnt++;
        }
        System.out.println( cnt);
    }

}


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

int main()
{
    char s[4];
    cin>>s;
    if(strlen(s)==2)
        printf("%s",s);
    else
    {
        for(int i=strlen(s)-1;i>=0;i--)
            printf("%c",s[i]);
    }
    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static Pile[] P;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();

        P = new Pile[N];
        for (int i = 0; i < N; i++) {
            int size = sc.nextInt();
            P[i] = new Pile(i+1, size);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (long l : solve()) {
            pw.println(l);
        }
        pw.flush();
    }

    static long[] solve() {
        Arrays.sort(P, Comparator.<Pile>comparingInt(p -> p.size).reversed());

        long[] cnt = new long[N];

        Pile first = P[0];
        int no = first.no;
        int size = first.size;
        for (int i = 1; i < N; i++) {
            Pile p = P[i];
            if( p.size != size ) {
                int diff = size - p.size;
                cnt[no-1] += (long)diff * (i);
                size -= diff;
            }
            no = Math.min(p.no, no);
        }
        cnt[no-1] += (long)size * N;
        return cnt;
    }

    static class Pile {
        int no, size;

        public Pile(int no, int size) {
            this.no = no;
            this.size = size;
        }
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}


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

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    bool dp[1000001];
    int occ[1000001] = {0};
    fill(dp, dp + 1000001, true);
    for(int i = 0; i < n; i++) {
        occ[a[i]]++;
        if(dp[a[i]]) {
            for(int j = a[i] * 2; j <= a[n - 1]; j += a[i]) {
                dp[j] = false;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(dp[a[i]] && occ[a[i]] == 1) {
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 9012
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = s, i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = s, i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = s; i < (n); ++i)
#define VFORS(i, s, n) for(int i = s; i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = s, i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = s, i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end());

using ll = long long;
using PII = pair<int, int>;
using VI = vector<int>;
using VD = vector<double>;
using VLL = vector<ll>;
using VS = vector<string>;

const int MOD = 1000000007;
const int INF = 1000000000;

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


int main(){
    int n; cin >> n;
    string s; cin >> s;
    int cnt = 0;
    REP(i, 1000){
        string t = "000";
        t[0] = i/100 + '0';
        t[1] = (i/10 % 10) + '0';
        t[2] = i%10 + '0';
        int idx = 0;
        REP(j, n){
            if(s[j] == t[idx]) ++idx;
            if(idx == 3){
                ++cnt; break;
            }
        }
    }
    cout << cnt << "\n";
    return 0;
}


Measured memory_bytes: 384
def main():
    N = int(input())
    A = list(map(int, input().split()))

    tallest = A[0]
    ans = 0

    for height in A:
        if height < tallest:
            ans += tallest - height
        elif height > tallest:
            tallest = height

    print(ans)


if __name__ == "__main__":
    main()


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

signed main(void){ 
  
  int N;
  cin >> N; int M = 0;
  
  vector<int> vec(110,0);
  
  for(int i = 0; i < N; i++){
    int a; cin >> a; 
    vec[a]++; M = max(M,a); //直径を求める
  }
  
  bool flag = true; 
  
  if( M % 2 == 0 ){ 
    
    for(int i = M; i >= M/2; i--){ 
      
      if( i == M/2 ){  //最後だけ例外
        
        if( vec[M/2] == 0 ){ flag = false;}
        else{ vec[M/2]--; }
        
      }
      
      else{ 
        
        if( vec[i] <= 1 ){ flag = false;}
        else{ vec[i] -= 2;}
        
      }
    }//for
  }// 偶数の場合
  else{ 
    
    for(int i = M; i >= (M+1)/2; i--){ 
      
      if( vec[i] <= 1 ){ flag = false;}
      else{ vec[i] -= 2;}
      
    }
  }
  
  if(!flag){ cout << "Impossible" << endl; return 0;}
  
  //　残りの要素について、最小値以下が存在しないかを調べる
  
  int m; 
  if( M % 2 == 0 ){ m = M/2;}
  else{ m = (M+1)/2;}
  
  for(int i = 0; i <= m; i++){ 
    if( vec[i] > 0 ){ flag = false;}
  }
  
  if( !flag){ cout <<"Impossible" << endl;}
  else{ cout <<"Possible" << endl;}
  
  return 0;
}
  

Measured memory_bytes: 256
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let mut n: i64 = itr.next().unwrap().parse().unwrap();
    let mut out = Vec::new();
    if n == 0 {
        println!("0");
    } else {
        while n != 0 {
            let mut r = n % 2;
            r *= r;
            write!(out, "{}", r).ok();
            n = (n - r) / (-2);
        }
        out.reverse();
        stdout().write_all(&out).unwrap();
    }
}


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n,k;
    cin >> n >> k;
    vector<int32> p(n);
    REP(i,n)cin >> p[i];
    vector<double> q(n);
    REP(i,n)q[i] = (double)(1 + p[i]) / 2;
    double cur = 0;
    REP(i,k){
        cur += q[i];
    }
    double ans = cur;
    FOR(i,k,n){
        cur += q[i] - q[i - k];
        ans = max(ans, cur);
    }
    printf("%.12f",ans);
    return 0;
}

Measured memory_bytes: 3328
def resolve():
    N = int(input())
    P = list(map(float, input().split()))

    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(i+1):
            dp[i + 1][j + 1] += dp[i][j] * P[i]
            dp[i + 1][j] += dp[i][j] * (1.0 - P[i])

    ans = 0.0
    for j in range(N//2+1, N+1):
        ans += dp[N][j]
    print(ans)


if __name__ == "__main__":
    resolve()

Measured memory_bytes: 222684