akhauriyash/Code-Regression huggingface dataset:
// 🐋💭
import Foundation

func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func readInt() -> Int {
    return Int(readLine()!)!
}

func readDoubles () -> [Double] {
    return readLine()!.split(separator: " ").map { Double($0)! }
}

func readDouble() -> Double{
    return Double(readLine()!)!
}
///最大公約数を返す
func gcd(_ m:Int, _ n:Int) -> Int {
    if n == 0 {return m}
    return gcd(n, m % n)
}
///最小公倍数を返す
func lcm(_ m:Int, _ n:Int) -> Int {
    return m * n / gcd(m, n)
}

///素数判定(試し割り)
func isPrime(_ x:Int) -> Bool {
    if x <= 1 || x % 2 == 0 { return false }
    if x == 2 { return true }
    for i in stride(from: 3, to: Int(ceil(sqrt(Double(x)))), by: 2){
        if x % i == 0 {
            return false
        }
    }
    return true
}

//https://program-life.com/669
///実行速度の計測
func exectionTime(action: () -> Void) {
    let startDate = Date()
    action()
    let endDate = Date()
    print(endDate.timeIntervalSince(startDate))
}

// https://melheaven.hatenadiary.jp/entry/atcoder144
///約数の配列を返す
func makeDivisors(_ n:Int) -> [Int] {
    var divisors = [Int]()
    for i in 1..<Int(pow(Double(n), 0.5)) + 1 {
        if n % i == 0{
            divisors.append(i + n / i)
        }
    }
    
    return divisors
}

//https://riptutorial.com/ja/swift/example/14738/インデックスを知らずに配列から要素を削除する
extension Array where Element: Equatable {
    
    mutating func remove(_ element: Element) {
        _ = firstIndex(of: element).flatMap {
            self.remove(at: $0)
        }
    }
}

func binarySearch(rifgt:Int, key:Int, ary:[String]) -> Int{
    var left = 0
    var right = rifgt
    
    while abs(right - left) > 1 {
        let mid = left + (right - left) / 2
        
        if Int(ary[mid])! < key {
            left = mid
            
        } else {
            right = mid
        }
    }
    return left
}

func arrangement (prev:String, ary:[String], returnVal:[String]) -> [String] {
    var returnVal = returnVal
    if ary.count == 0 {
        returnVal.append(prev)
        return returnVal
    }
    
    for s in ary {
        let wprev = prev + s
        var wary = ary
        wary.remove(s)
        returnVal = arrangement(prev: wprev, ary: wary, returnVal: returnVal)
    }
    return returnVal
}

func main() {
    let nm = readInts()
    let (n, m) = (nm[0], nm[1])
    let aryX = readInts().sorted()
    //＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿ここまで入力
    if n >= m {
        print(0)
        return
    }
    var ans = 0
    var ary = [Int](repeating: 0, count: m - 1)
    for i in 1..<m {
        ary[i - 1] = abs(aryX[i] - aryX[i - 1])
    }
    
    ary.sort(by: >)
    
    for i in n - 1..<ary.count {
        ans += ary[i]
    }
    print(ans)
}
main()


Measured memory_bytes: 18560
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 1000009
#define K 104206969
#define LL long long
#define INF 0x7fffffff
#define mymin(x,y) (x>=y?y:x)
#define mymax(x,y) (x>=y?x:y)
char input[N];
int fw[N];
int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	cin >> input;
	cout << input[0] << input[1] << input[2];
	return 0;
}


Measured memory_bytes: 3044
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int n, k;
    string s;
    cin >> n >> s >> k;
    for(int i = 0; i < n; i++){
        if(s[i] != s[k-1]) s[i] = '*';
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

        int h = sc.nextInt(), w = sc.nextInt();

        boolean[][] b = new boolean[h + 2][w + 2];

        for (int y = 0; y < h; y++) {
            String l = sc.next();
            for (int x = 0; x < w; x++) {
                b[y + 1][x + 1] = l.charAt(x) == '#';
            }
        }

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

        for (int y = 1; y <= h; y ++) for (int x = 1; x <= w; x++) if (b[y][x]) {

            boolean ch = false;
            for (int i = 0; i < 4; i ++) {
                ch |= b[y + dy[i]][x + dx[i]];
            }
            if (!ch) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");

    }
}


Measured memory_bytes: 21972
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

bool isNecessary(int);

int a[5001];
bool d[5001][5000]={false, };
int n, k;

int main() {
	scanf("%d %d", &n, &k);
	for(int i=1; i<=n; i++) 
		scanf("%d", &a[i]);		
	
	sort(a+1, a+n+1); //**
	
	int lo=1, hi=n;
	while(lo<=hi) {
		int mid=(lo+hi)/2;
		if(isNecessary(mid)) hi=mid-1;
		else lo=mid+1;
	}

	printf("%d\n", lo-1);
	return 0;
}

bool isNecessary(int idx) {
	int tmp=a[idx];
	a[idx]=0;
	memset(d, false, sizeof(d));
	d[0][0]=true;
	for(int	i=1; i<=n; i++) {
		for(int j=0; j<k; j++) {
			bool res=d[i-1][j];
			if(j-a[i]>=0) 
				res=res||d[i-1][j-a[i]];

			d[i][j]=res;
			if(k-tmp<=j && j<k && d[i][j]) {
				a[idx]=tmp;
				return true;
			}
		}
	}

	a[idx]=tmp;
	return false;
}


Measured memory_bytes: 24576
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char s[100005];
int n, ans, pre;
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) {
		if (pre != s[i]) pre = s[i], ++ans;
	} printf("%d\n", ans - 1);
	return 0;
}

Measured memory_bytes: 384
def calc_sadness(b):
    ans = 0
    for a in A:
        ans += abs(a - b)
    return ans


N = int(input())
A = []
for idx, a in enumerate(map(int, input().split())):
    A.append(a - idx - 1)
A.sort()

if N % 2 == 0:
    b = [A[N // 2]]
else:
    b = [A[N // 2 - 1], A[N // 2]]

print(min(map(calc_sadness, b)))


Measured memory_bytes: 26180
for _ in [0] * int(raw_input()):
  a, b = map(int, raw_input().split(':'))
  x = (a*60-b*11)%720
  if x>360: x=720-x
  if x<60: print 'alert'
  elif 180<=x: print 'safe'
  else: print 'warning'

Measured memory_bytes: 4196
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    N = int(input())
    S = input()

    solo_close_no = 0
    for i in range(N):
        if S[-i-1] == ")":
            solo_close_no += 1
        elif solo_close_no >= 1:
            solo_close_no -= 1
    
    solo_open_no = 0
    for i in range(N):
        if S[i] == "(":
            solo_open_no += 1
        elif solo_open_no >= 1:
            solo_open_no -= 1

    answer = "("*solo_close_no + S + ")"*solo_open_no
    print(answer)

if __name__ == "__main__":
    main()



Measured memory_bytes: 9068
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1ll<<(x))
#define inf 1000000000
#define MOD 1000000007
#define N 2000005
#define M 1000003
#define LOG 16
#define KOK 650
#define EPS 0.00001
using namespace std;

int f[N],p[N],n;

int main() {

//	freopen("input.txt","r",stdin);

	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);

	cin>>n;

	f[1]=n;

	for(int i=0;i<=M;i++) p[i]=(p[i-1]+1)%MOD;

	p[1+M]=(p[M]+n)%MOD;

	for(int i=2;i<=n;i++) {

		f[i]=(p[i-3+M]-p[i-n-2+M]+f[i-1]+(ll)(n-1)*(n-1))%MOD;
		
		p[i+M]=(p[i-1+M]+f[i])%MOD;

	}

	cout<<f[n];

}



Measured memory_bytes: 12544
#include<iostream>
#include<iomanip>
#include<vector>
#include<algorithm>
using namespace std;

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

    vector<pair<double, pair<int, int>>> items;
    for(int i = 0; i < N; ++i){
        int v, w;
        cin >> v >> w;
        items.emplace_back((double)v / (double)w, make_pair(v, w));
    }
    // 重さに対しての価値が高い順に並び変える
    sort(items.rbegin(), items.rend());

    double ans = 0;
    int weight = 0;
    for(const auto item : items){
        if(weight + item.second.second > W){
            int dif = W - weight;
            ans += (double) dif * item.first;
            weight += dif;
            break;
        } 
        else {
            ans += item.second.first;       // v
            weight += item.second.second;   // w
        }
    }

    cout << fixed << setprecision(7) << ans << endl;

    return 0;
}


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

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> a(n + 1, 0);
  while (q--) {
    int x;
    cin >> x;
    --x;
    --a[0], ++a[x];
    --a[x + 1];
  }
  for (int i = 1; i < n; i++) 
    a[i] += a[i - 1];
  for (int i = 0; i < n; i++)
    a[i] += k;
  for (int i = 0; i < n; i++) {
    if (a[i] > 0) 
      cout << "Yes\n";
    else
      cout << "No\n";
  }
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(),a.end()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forr(i,n) for(int i=int(n-1);i>=0;i--)
#define fora(i,a,b) for(int i=int(a);i<=int(b);i++)
#define forb(i,a,b) for(int i=int(a);i>=int(b);i--)
#define mod 1000000007
using namespace std;
using ll=long long int;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vii;
typedef pair<ll ,ll> pii;

void solve()
{
	ll x,k,d;
	cin>>x>>k>>d;
	x=abs(x);
	ll can=x%d;
	ll req=x/d;
	//cout<<req<<endl;
	if(req>=k)
	{
		ll ans=can+(req-k)*d;
		cout<<ans<<endl;
	}
	else
	{
		if((k-req)&1)
		{
			cout<<abs(can-d)<<endl;
		}
		else
		{
			cout<<can<<endl;
		}
	}
	
}

int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
	solve();
    return 0;
}


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

int goods[] = {100,101,102,103,104,105};

int main(){
	int x;
	cin >> x;
	vector<bool> dp(x+5, false);
	dp[0] = true;
	for(int i=0;i<=x;i++) {
		for(int j=0;j<6;j++) {
			if(i-goods[j]>=0) dp[i] = dp[i] | dp[i-goods[j]];
		}
	}
	cout << dp[x] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long LL;
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

using namespace std;
LL p = 1000000007ll;

int main(void)
{
  LL n;
  cin >> n;
  vector<LL> h(n);
  for(auto &x:h) cin >> x;
  LL answer = 0;
  LL tmp = 0;
  REP(i,n-1) {
    if(h[i] < h[i+1]) tmp = 0;
    else {
      ++tmp;
      answer = max(answer,tmp);
    }
  }
  cout << answer << endl;
  return 0;
}


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

int main(){
	int n, k;
	cin >> n >> k;
	
	int i=1;
	while(n>0){
		if(i==1) n -= k;
		else n-= (k-1);
		i++;
	}
	
	cout << i-1 << endl;
	
	return 0;
}

Measured memory_bytes: 256
s = input()
print("No" if (s.count("N") == 0 and s.count("S") > 0)\
		   or (s.count("S") == 0 and s.count("N") > 0)\
	       or (s.count("W") == 0 and s.count("E") > 0)\
		   or (s.count("E") == 0 and s.count("W") > 0)\
		   else "Yes")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

// #define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9;

vector<int> ra(MX,0);
vector<int> par(MX,0);
using P = pair<int, int>;
using ll = long long;
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int find(int x) {
    if(par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x==y) return;
    if(ra[x]<ra[y]) {
        par[x] = y;
    }else {
        par[y] = x;
        if(ra[x]==ra[y]) {
            ra[x]++;
            
        }
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

signed main(){
    int n;
    cin >> n;
    map<pair<ll,ll>,P> mp;
    int zero = 0;

    rep(i,n) {
        ll x, y;
        cin >> x >> y;
        
        if(x==0 && y == 0) {
            zero++;
            continue;
        }
        
        ll g = __gcd(x,y);
        x = x/g;
        y = y/g;

        if(y<0) x = -x, y = -y; 
        if(y == 0 && x < 0) x = -x, y = -y;
        bool rot90 = (x<=0);
        if(rot90) {
            ll tmp = x;
            x = y; y = -tmp;
        }
    
        if(rot90) mp[{x,y}].first++;
        else mp[{x,y}].second++;
    }

    mint ans = 1;
    for(auto p:mp) {
        int s = p.second.first;
        int t = p.second.second;
        mint now = 1; // 何も選ばない
        now += mint(2).pow(s) - 1; //sだけ選ぶ
        now += mint(2).pow(t) - 1; //tだけ選ぶ
        ans *= now;
    }
    ans -= 1; // 誰も選ばない

    ans += zero;
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 23424
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int,  int>;

const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

int main(){
     ll n,m;
     cin >>n >> m;
     ll ans =0;
     if(2*n>m){ans = m/2;}
     else{
         ans += n; m-=2*n;
         ans += m/4;
     }
    cout << ans << endl;
}

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

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int Amm = scan.nextInt();
		int Bmm = scan.nextInt();
		int Cmm = scan.nextInt();

		System.out.println(Amm-Bmm >= Cmm?0:Bmm+Cmm-Amm);

		scan.close();

	}

}


Measured memory_bytes: 27032
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] a = sc.next().toCharArray();
        char[] b = sc.next().toCharArray();
        char[] c = sc.next().toCharArray();

        int res = 0;

        for(int i=0; i<n; i++) {
            char x = a[i];
            char y = b[i];
            char z = c[i];
            if(x == y && y == z) continue;
            if(x == y || y == z || z == x) {
                res ++;
                continue;
            }
            res += 2;
        }

        System.out.println(res);
    }

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define ll long long
using namespace std;
//typedef vector<unsigned int>vec;
//typedef vector<ll>vec;
//typedef vector<vec> mat;
typedef pair<int, int> P;
typedef pair<ll,ll> LP;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const int INF = 1000000000;
const ll LINF = 1000000000000000000;//1e18
const ll  MOD = 1000000007;
const double PI = acos(-1.0);
const double EPS = 1e-10;

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; }
//template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    double R;
    cin >> R;
    printf("%.12lf\n", 2 * R * PI);
}


Measured memory_bytes: 3808
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n);i>0;--i)
using namespace std;

int main() {
	int n,ans=0; cin >> n;
	int count[100010] = {};
	int a[100010] = {};
	REP(i, n){
		cin >> a[i]; 
	}
	sort(a, a + 100000, greater<int>());

	REP(i, n) {
		count[i]++;
		FOR(j,i, n) {
			if (a[j] == a[j + 1]) { 
				count[i]++;
			}
			else 
				break;
		}
		if(count[i])
		i += count[i] -1;
	}

	REP(i, 100000) {
		if (count[i] < a[i])ans += count[i];
		else if (count[i] > a[i])ans += count[i] - a[i];
		if(count[i])
		i += count[i]-1;
		else break;
	}

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

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

using namespace std;

int main(void)
{
    int N;
    long long result =0;
    map<string,int> str_time;

    cin >> N;

    string s;
    for(int i;i<N;i++){
        cin >>s;
        sort(s.begin(),s.end());
        ++str_time[s];
    }
  
    long long num;
    for (auto itr = str_time.begin(); itr != str_time.end() ; itr++){
      num = itr->second;
      result += num*(num-1)/2;
    }

    cout << result << endl;

    return 0;
}

Measured memory_bytes: 11136
#include<stdio.h>
int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	int i;
	int l[55];
	for(i=0;i<n;i++)
	  scanf("%d",&l[i]);
	int x;
	for(i=0;i<n-1;i++)
	{
		if(l[i]<l[i+1])
		{
			x=l[i];
			l[i]=l[i+1];
			l[i+1]=x;
			if(i>0)
			  i-=2;
		}
	}
	int ans=0;
	for(i=0;i<k;i++)
	  ans+=l[i];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef double db;

#define fr first
#define sc second
#define pb push_back
#define rep(i,x) for(ll i=0;i<x;i++)
#define rep1(i,x) for(ll i=1;i<=x;i++)
#define rrep(i,x) for(ll i=x-1;i>=0;i--)
#define rrep1(i,x) for(ll i=x;i>0;i--)

ll n,l;
ll a[100010];
ll dp[100010];
const ll INF = 0xfffffffff;

ll rec(ll x){
	if(dp[x]!=-1) return dp[x];
	ll res=l-a[x];
	ll lef=0,rig=0;
	
	auto ok=[](ll z){return 0<=z&&z<n;};
	
	if(ok(x-1)&&a[x-1]>a[x]) lef=rec(x-1);
	if(ok(x+1)&&a[x+1]>a[x]) rig=rec(x+1);
	
	return res+max(lef,rig);
}

int main()
{
	ll ans=0;
	cin>>n>>l;
	rep(i,n) cin>>a[i];
	memset(dp,-1,sizeof(dp));
	rep(i,n) ans=max(ans,rec(i));
	cout<<ans<<endl;
}

Measured memory_bytes: 6580
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, K = map(int, input().split())
x = list(map(int, input().split()))
dp = [float("inf")] * (K + 2)
s = bl(x, 0)
l = 0
r = K - 1
if r + 1 < s:
  l = s - 1 - r
  r = s - 1
def calc(l, r):
  if x[l] * x[r] < 0:
    return min(abs(x[l]), abs(x[r])) * 2 + max(abs(x[l]), abs(x[r]))
  else:
    return max(abs(x[l]), abs(x[r]))
dp[0] = calc(l, r)
for i in range(1, K + 2):
  l += 1
  r += 1
  if l > s + 1 or r >= N:
    break
  dp[i] = calc(l, r)
print(min(dp))

Measured memory_bytes: 58736
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  map<ll, ll> mp;
  map<ll, ll> ans;
  repr(i, n, 0) {
    cin >> a[i];
    mp[a[i]] += 1;
  }

  ll total = 0;

  for (auto itr : mp) {
    ans[itr.first] = itr.second * (itr.second - 1) / 2;
    total += ans[itr.first];
  }

  for (int i = 0; i < n; ++i) {
    ll t = total - ans[a[i]] + ((mp[a[i]] - 1) * (mp[a[i]] - 2) / 2);
    cout << t << endl;
  }
}

Measured memory_bytes: 20608
def main(S, T):
    score = float('inf')
    org_length = len(S)
    part_length = len(T)

    for i in range(0, org_length - part_length + 1):
        part_str = S[i:i + part_length]

        count = 0
        for a, b in zip(part_str, T):
            if a != b:
                count+=1
        score = min(count, score)

    print(score)


if __name__ == '__main__':
    S = input()
    T = input()
    main(S, T)


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

bool f(const string& a, const string& b){
    return (strcmp(a.c_str(),b.c_str())<0);    
}

int main()
{
    int n,l;
    cin>>n>>l;
    vector<string>v;
    string s;
    for(int i=0;i<n;i++){
        cin>>s;
        v.push_back(s);
    }
    sort(v.begin(),v.end(),f);
    for(int i=0;i<n;i++)
        cout<<v[i];
    return 0;    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int mod = 1000000007;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  int ans = 0;
  rep(i, n) {
    if ((i + 1) % 2 == 1 && a[i] % 2 == 1) ans++;
  }
  cout << ans << endl;
}

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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = 1e9 + 10;
const long long LLINF = (long long)1e18 + 10;
const long long MOD = (long long)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

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

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

    int n;
    cin >> n;

    vector<int> l(n);
    int maxi = 0, maxdex = -1;
    rep(i, n){
        cin >> l[i];
        if(chmax(maxi, l[i])){
            maxdex = i;
        }
    }

    int sum = 0;
    rep(i, n){
        if(i != maxdex){
            sum += l[i];
        }
    }

    if(maxi < sum){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    H,W=map(int,readline().split())
    a=["#"*(W+2)]
    for i in range(H):
        s=readline().strip()
        s="#"+s+"#"
        a.append(s)
    a.append("#"*(W+2))
    
    for i in range(H+2):
        print(a[i])

if __name__=="__main__":
    main()

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

//型定義
typedef long long ll;

//定数
const ll INF=1e+18;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    ll Q;
    cin>>Q;
    vector<pair<ll,ll>> ans;
    ll fx=0;
    ll x=0;
    ll nx=x;
    priority_queue<ll> zenhan;
    priority_queue<ll,vector<ll>,greater<ll>> kouhan;
    ll n=0;
    REP(i,Q){
        int num;
        cin>>num;
        if(num==1){
            ll a,b;
            cin>>a>>b;
            
            if (zenhan.size() > kouhan.size()) {
                int t = zenhan.top();
                if (a >= t) {
                    kouhan.push(a);
                }
                else {
                    zenhan.pop();
                    zenhan.push(a);
                    kouhan.push(t);
                }
            }
            else {
                if (zenhan.empty()) zenhan.push(a);
                else {
                    int t = kouhan.top();
                    if (a <= t) {
                        zenhan.push(a);
                    }
                    else {
                        kouhan.pop();
                        kouhan.push(a);
                        zenhan.push(t);
                    }
                }
            }
            nx=zenhan.top();
            n++;
            fx+=abs(x-a)+b;
            if(n%2==1) fx-=abs(nx-x);
            x=nx;
        }else{
            ans.push_back(make_pair(x,fx));
        }
    }

    REP(i,ans.size()){
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }
}

Measured memory_bytes: 6424
#include "bits/stdc++.h"
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define all(V) (V).begin(), (V).end() 
using namespace std;
typedef long long ll;

int main() {fio;
	string s;
	cin >> s;
	vector <int> cnt(26, 0);
	ll sm = 0, ans = 0;
	for(int i = 0; i < 26; i++) {
		cnt[i] = count(all(s), 'a' + i);
		ans += sm * cnt[i];
		sm += cnt[i];
	}
	cout << ans + 1 << endl;
    return 0;
}

Measured memory_bytes: 3744
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n, k;
  cin >> n >> k;
  vector<i64> a(n);
  for (i64 i = 0; i < n; i++)
    cin >> a[i];
  bool ok = true;
  vector<i64> ans;
  i64 now = -1;
  for (i64 i = 0; i < k + 1; i++)
  {
    i64 pos = -1, mi = 1e9;
    for (i64 j = 0; j < n; j++)
      if (j != now && a[j] <= mi)
      {
        pos = j;
        mi = a[j];
      }
    for (i64 j = 0; j < n; j++)
      if (j != now && j != pos)
      {
        ans.push_back(j + 1);
        a[j]--;
        if (a[j] < 0)
          ok = false;
      }
    ans.push_back(pos + 1);
    a[pos]--;
    if (a[pos] < 0)
      ok = false;
    now = pos;
  }
  if (ok)
  {
    i64 size = ans.size();
    cout << size << endl;
    for (i64 i = 0; i < size; i++)
      cout << ans[i] << (i + 1 == size ? "\n" : " ");
  }
  else
    cout << "-1" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

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

		int n=sc.nextInt();
		int[] ai=new int[n];
		long sum=0;

		for (int i=0;i<n;i++) {
			ai[i]=sc.nextInt();
			sum+=ai[i];
		}

		Arrays.sort(ai);
		System.out.println(ai[0]+" "+ai[n-1]+" "+sum);
	}
}


Measured memory_bytes: 41496
package main

import (
	"fmt"
	"strings"
)

type Node struct {
	p int
	l int
	r int
}

const (
	NIL = -1
	MAX = 100005
)

var T [MAX]Node
var n int
var D [MAX]int

func main() {
	var d, v, c, l, r int
	fmt.Scan(&n)

	for i := 0; i < n; i++ {
		T[i].p = NIL
		T[i].l = NIL
		T[i].r = NIL
	}

	for i := 0; i < n; i++ {
		fmt.Scan(&v)
		fmt.Scan(&d)

		for j := 0; j < d; j++ {
			fmt.Scan(&c)
			if j == 0 {
				T[v].l = c
			} else {
				T[l].r = c
			}
			l = c
			T[c].p = v
		}
	}

	for i := 0; i < n; i++ {
		if T[i].p == NIL {
			r = i
		}
	}

	rec(r, 0)

	for i := 0; i < n; i++ {
		print(i)
	}

	return
}

func rec(u, p int) {
	D[u] = p
	if T[u].r != NIL {
		rec(T[u].r, p)
	}
	if T[u].l != NIL {
		rec(T[u].l, p+1)
	}
}

func print(u int) {
	format := "node %d: parent = %d, depth = %d, %s, %s\n"

	nodeType := ""
	if T[u].p == NIL {
		nodeType = "root"
	} else if T[u].l == NIL {
		nodeType = "leaf"
	} else {
		nodeType = "internal node"
	}

	// children := "["
	// c := T[u].l
	// count := 0
	// for c != NIL {
	// 	if count > 0 {
	// 		children += ", "
	// 	}
	// 	children += fmt.Sprintf("%d", c)

	// 	c = T[c].r
	// 	count++
	// }
	// children += "]"
	var children []string
	c := T[u].l
	for c != NIL {
		children = append(children, fmt.Sprintf("%d", c))
		c = T[c].r
	}

	fmt.Printf(format, u, T[u].p, D[u], nodeType, fmt.Sprintf("[%s]", strings.Join(children, ", ")))
}



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

using ll = long long;
const int mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int A, B, C;
    cin >> A >> B >> C;
    set<int> S;
    S.insert(A);
    S.insert(B);
    S.insert(C);
    if (S.size() == 2)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 256
h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())

tab=[[0 for i in range(w)] for q in range(h)]

cnt=0
for i in range(h):
    cnt=0
    for q in range(w):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for i in range(h):
    cnt=0
    for q in range(w-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt

print(max([max(col) for col in tab])-3)



Measured memory_bytes: 112444
#include <iostream>
#include <climits>

using namespace std;

int main () {

    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;

    long long ans = INT_MAX;
    for (int i = 0; i <= 100000; i++) {
        long long cost = (long long)(2 * C * i + A * max(0, X - i) + B * max(0, Y - i));
        ans = min(cost, ans);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
N=int(input())
happy=[[0,0,0] for i in range(N)]
for i in range(N):
    a,b,c=map(int,input().split())
    happy[i][0]=a
    happy[i][1]=b
    happy[i][2]=c
dp=[happy[0]]+[[0,0,0] for i in range(N-1)]
for i in range(1,N):
    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+happy[i][0]
    dp[i][1]=max(dp[i-1][2],dp[i-1][0])+happy[i][1]
    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+happy[i][2]
print(max(dp[N-1]))

Measured memory_bytes: 72480
s=input()
n=len(s)
for l in range(n):
    for r in range(l,n):
        s1=s[:l]
        s2=s[l:r+1]
        s3=s[r+1:]
        if s1+s3=="keyence" or s=="keyence":
            print("YES")
            exit()
print("NO")


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

using namespace std;
using ll = long long;

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> as(N);
  rep(i, N) cin >> as[i];
  vector<bool> dp(K, false);
  for (int i = 0; i <= K; i++) {
    rep(j, N) {
      if (as[j] <= i) {
        dp[i] = dp[i] | !dp[i - as[j]];
      }
    }
  }
  if (dp[K]) {
    cout << "First" << endl;
  } else {
    cout << "Second" << endl;
  }
  return 0;
}

Measured memory_bytes: 3660
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


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

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple


// 頂点は0-originとする
template <typename T>
class Dijkstra {
    struct edge { int to; T cost; };
    typedef pair<T, int> P; // <最短距離, 頂点番号>

private:
    int m_V;
    vector<vector<edge> > m_G;
public:
    const T INF = std::numeric_limits<T>::max();
    vector<int> m_prev_path; // 最短パスを辿るため

    Dijkstra(int V) : m_V(V) {
        m_G.resize(m_V);
    }

    // a -> bに片方向のエッジを張る
    void add_dir_edge(int a, int b, T cost) {
        m_G[a].push_back( edge{ b, cost } );
    }

    // a <-> bに両方向のエッジを張る
    void add_undir_edge(int a, int b, T cost) {
        add_dir_edge(a, b, cost);
        add_dir_edge(b, a, cost);
    }

    // 頂点sから各頂点までの距離を計算して返す
    vector<T> shortest_path(int s) {
        m_prev_path.clear(); m_prev_path.resize(m_V, -1);

        vector<T> d(m_V, INF);
        priority_queue<P, vector<P>, greater<P> > que;
        d[s] = 0;
        que.push(P(0, s));

        while(!que.empty()) {
            P p = que.top();
            que.pop();

            auto dist = p.first;
            auto v = p.second;
            if (d[v] < dist) continue;
            REP(i, m_G[v].size()) {
                edge e = m_G[v][i];
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    que.push(P(d[e.to], e.to));
                    m_prev_path[e.to] = v;
                }
            }
        }

        return d;
    }

    // shortest_path()が呼ばれた後に呼ばれることを期待する
    // s -> v1 -> v2 -> v3 -> t の場合、{s, v1, v2, v3, t} からなるvectorを返す
    vector<int> get_path(int t)
    {
        vector<int> path;
        for(; t != -1; t = m_prev_path[t]) path.push_back(t);
        reverse(ALL(path));
        return path;
    }

};

int main(void)
{
    cin.sync_with_stdio(false);
    ll N;
    cin >> N;

    Dijkstra<ll> dij(N);

    REP(n, N-1) {
        ll u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        dij.add_undir_edge(u, v, w);
    }

    auto res = dij.shortest_path(0);
    REP(n, N) {
        cout << ((res[n] % 2) ? 0 : 1) << endl;
    }
    return 0;
}


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

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

    int H, W; cin >> H >> W;
    vector<string> a(H);
    for (int i = 0; i < H; i++) cin >> a[i];

    vector<bool> vh(H), vw(W);
    for (int i = 0; i < H; i++) {
        bool flag = true;
        for (int j = 0; j < W; j++) {
            if (a[i][j] == '#') {
                flag = false;
                break;
            }
        }
        if (flag) vh[i] = true;
    }
    for (int j = 0; j < W; j++) {
        bool flag = true;
        for (int i = 0; i < H; i++) {
            if (a[i][j] == '#') {
                flag = false;
                break;
            }
        }
        if (flag) vw[j] = true;
    }

    for (int i = 0; i < H; i++) {
        if (vh[i]) continue;
        for (int j = 0; j < W; j++) {
            if (vw[j]) continue;
            cout << a[i][j];
        }
        cout << "\n";
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdlib>
#include<ctime>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

constexpr int num = 26;
int D;
vector<int> c(num);

vector<vector<int>> s; 

int point(vector<int> &t){
	int res = 0;
	
	vector<int> last(num);
	
	for(int i = 0; i < D; i++){
		res += s[i][t[i]];
		
		for(int j = 0; j < num; j++){
			last[j]++;
		}
		
		last[t[i]] = 0;
		
		for(int j = 0; j < num; j++){
			res -= c[j] * last[j];
		}
	}
	
	return res + 1'000'000;
}

vector<int> solve(int Z){
	vector<int> t(D);
	
	vector<int> last(num);
	
	for(int i = 0; i < D; i++){
		for(int j = 0; j < num; j++){
			cin>>s[i][j];
			if(s[i][t[i]] + last[t[i]] * last[t[i]]/Z * c[t[i]] < s[i][j] + last[j] * last[j]/Z * c[j]) {
				t[i] = j;
			}
		}
		
		for(int j = 0; j < num; j++){
			if(j == t[i]) {
				last[j] = 0;
			} else {
				last[j]++;
			}
		}
	}
	
	return t;
}

signed main(){
	cout<<fixed<<setprecision(10);
	
	vector<int> t;
	
	
	cin>>D;
	
	s.resize(D, vector<int>(num));
	t.resize(D, 0);
	
	for(int i = 0; i < num; i++){
		cin>>c[i];
	}
	
	int p = 0;
	
	// for(int i = 1; i < 10; i++){
		// vector<int> nt;
		
		// nt = solve(i);
		// int np = point(nt);
		
		// if(p < np) {
			// t = nt;
			// p = np;
		// }
	// }

	t = solve(1);
	
	for(int i = 0; i < D; i++){
		cout<<t[i]+1<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 3720
#???????????????????????????????????????
S_number = [int(i) for i in range(1, 14)]
H_number = [int(i) for i in range(1, 14)]
C_number = [int(i) for i in range(1, 14)]
D_number = [int(i) for i in range(1, 14)]

#?????°?????\???
n = int(input())

#??\???????????????????????¨??????????????????????????????????????????
for i in range(1, n + 1):
    cord = input().split()
    if cord[0] == "S":
        S_number.remove(int(cord[1]))
    elif cord[0] == "H":
        H_number.remove(int(cord[1]))
    elif cord[0] == "C":
        C_number.remove(int(cord[1]))
    elif cord[0] == "D":
        D_number.remove(int(cord[1]))

#?????£????????????????????¨???
if len(S_number) != 0:
    for i in range(len(S_number)):
        print("S {0}".format(S_number[i]))
if len(H_number) != 0:
    for i in range(len(H_number)):
        print("H {0}".format(H_number[i]))
if len(C_number) != 0:
    for i in range(len(C_number)):
        print("C {0}".format(C_number[i]))
if len(D_number) != 0:
    for i in range(len(D_number)):
        print("D {0}".format(D_number[i]))

Measured memory_bytes: 7784
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n; cin >> n;
	int f[n+1];
	memset(f, 0, sizeof(f));
	for(int i=2; i<=n; i++) {
		int t; cin >> t;
		f[t]++;
	}
	for(int i=1; i<=n; i++) cout << f[i] << endl;
}

Measured memory_bytes: 4368
use std::io::*;
use std::str::FromStr;

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

fn main() {
    let n: usize = read();
    let x: usize = read();
    let mut ans = 0;
    let mut c = 0;
    for i in 1..=n {
        let y: usize = read();
        c += y;
        if c > x {
            ans += i;
            break;
        }
    }
    println!("{}", if ans != 0 {ans} else {n+1});
}


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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s; cin>>s;
	int ret=0;
	for (int i=0; i<3; i++) 
		if (s[i]=='1')
			ret++;
	cout << ret << endl; 
	return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn

object Main extends App {

  val n = StdIn.readLine.toInt
  val seq = StdIn.readLine.split(" ").map(_.toInt).sorted.toBuffer
  seq ++= Array(0)


  val ans = {
    seq.foldLeft(0,0,0)((acc,e) => {
      // println(acc._1 + " " + acc._2 + " " + acc._3)
      if(acc._1 != e) {
       if(acc._1 != acc._2) {
         if(acc._2 < acc._1) (e, 1, acc._3 + acc._2)
         else (e, 1, acc._3 + acc._2 - acc._1)
       }
       else (e, 1, acc._3)
      } else {
        (e, acc._2+1, acc._3)
      }
    })._3
  }

  println(ans)
}

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

int main(int argc, const char * argv[]) {
    string S;
    int len;
    
    cin >> S;
    
    len = (int)S.length();
    
    cout << S[0] << len - 2 << S[len - 1] << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(arr) (int)(arr).size()
#define rng(arr) arr.begin(), arr.end()
#define show(x) cout << #x << " = " << x << endl;

using namespace std;
typedef long long int ll;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

#define Cins(T, n, xs) \
  vector<T> xs(n);     \
  for (int i = 0; i < n; ++i) cin >> xs[i]

void Main() {
  Cin(int, n);
  int all = 1, bad = 1;
  for (int i = 0; i < n; ++i) {
    Cin(int, a);
    all *= 3;
    if (a % 2 == 0) bad *= 2;
  }
  cout << all - bad << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(15);
  Main();
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18

N, M = map(int, raw_input().split())
c = [0,2,5,5,4,5,6,3,7,6]
A = sorted(map(int, raw_input().split()))

D = [0] + [-1] * N * 9
a = [0, 0] * N

for i in range(1, N + 1):
 for j in A:
  p=i-c[j]
  if min(p,D[p],D[p]+1-D[i])>=0:D[i],a[i]=D[p]+1,j

S, p = "", N
while p:S,p=S+str(a[p]),p-c[a[p]]
print S

Measured memory_bytes: 4216
#include<iostream>
#include<cstring>
#include<math.h>
#include<algorithm>
#include<numeric>

using namespace std;

long long gcd(long long  a, long long b) {
  if(a < b) return gcd(b, a);
  long long r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main(){

    long long n;
    cin >> n;

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

    long long prefix[n];
    prefix[0] = a[n-1];
    prefix[1] = a[0];
    long long sufix[n];
    sufix[n-1] = a[0];
    sufix[n-2] = a[n-1];

    for(long long i=2;i<n;i++){
        prefix[i] = gcd(prefix[i-1], a[i-1]);
        //cout << "pre_" << i << ":" << prefix[i] << endl;
    }
    for(long long i=n-3;i>=0;i--){
        sufix[i] = gcd(sufix[i+1], a[i+1]);
        //cout << "su_" << i << ":" << sufix[i] << endl;
    }

    long long ans = 1;
    for(long long i=0;i<n;i++){
        long long tmp = gcd(prefix[i],sufix[i]);
        //cout << i << ":" << tmp << endl;
        if(tmp>ans)ans = tmp;
    }

    cout << ans << endl;
}


Measured memory_bytes: 2560
n=int(input())
a=list(map(int,input().split()))
b=[]
c=[]
for i in range(n+1):
	if i==0:
		b.append(abs(a[0]))
	elif i==n:
		b.append(abs(a[-1]))
	else:
		b.append(abs(a[i]-a[i-1]))
for i in range(n):
	if i==0:
		c.append(abs(a[1]))
	elif i==n-1:
		c.append(abs(a[-2]))
	else:
		c.append(abs(a[i+1]-a[i-1]))
sum_b=sum(b)
for i in range(n):
	print(sum_b-b[i]-b[i+1]+c[i])


Measured memory_bytes: 16128
#include<cstdio>
#include<algorithm>

using namespace std;

static const int A = 1e+9 + 7;
static const int MAX_N = 50;
static const int MAX_K = 1250;
unsigned int dp[MAX_N + 1][MAX_N + 1][MAX_K + 1];
int n, k;

void solve();

int main() {
    scanf("%d %d", &n, &k);
    if (k > n * n / 2) printf("0\n");
    else {
        solve();
        printf("%u\n", dp[n][0][k]);
    }
    return 0;
}

void solve() {
    dp[1][0][0] = 1;
    dp[1][1][2] = 1;
    for (int i = 2; i <= n; i++) {
        for (int l = 0; l <= min(i * (i + 1), k) ; l++) {
            for (int j = 0; j <= n && l >= 2 * j; j++) {
                dp[i][j][l] = (2L*j+1)*dp[i-1][j][l-2*j] % A;
                if (j <= n) dp[i][j][l] += ((j+1L)*(j+1)*dp[i-1][j+1][l-2*j]) % A;
                if (j > 0) dp[i][j][l] += (dp[i-1][j-1][l-2*j]) % A;
                dp[i][j][l] %= A;
//                printf("%d %d %d: %u\n", i, j, l, dp[i][j][l]);
            }
        }
    }
}


Measured memory_bytes: 11264
n = int(input())
A = list(map(int, input().split()))
if n == 2:
  print(max(A))
else:
  A.sort(reverse=True)
  ans = A[0]
  for a in A[1:n//2]:
    ans += 2 * a
  if n % 2 == 1:
    ans += A[n//2]
  print(ans)

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};


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

  ll n,m,k;
  cin>>n>>m>>k;
  vll a(n),b(m);
  REP(i,n)cin>>a[i];
  REP(i,m)cin>>b[i];

  vll rem_a(n+1),rem_b(m+1);
  REP(i,n)rem_a[i+1]=rem_a[i]+a[i];
  REP(i,m)rem_b[i+1]=rem_b[i]+b[i];



  ll ans=0;
  REP(i,n+1){
    ll now=rem_a[i]-rem_a[0];
    if(k<now)
      continue;

    ll ok=-1;
    ll ng=m;
    while(ng-ok>1){
      ll mid=(ok+ng)/2;
      if(now+rem_b[mid+1]<=k)
        ok=mid;
      else
        ng=mid;
    }

    ans=max(ans,i+ok+1);
  }


  cout<<ans<<endl;
}



Measured memory_bytes: 9536
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>

using namespace std;

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


typedef pair<int,int> pii;

const int M = 10010;
int in1[M],in2[M],in3[M],in4[M];

int main(){
	
	while(1){
		int n,m;
		cin>>n>>m;
		if(n==0 && m==0)break;
		
		int t;
		cin>>t;
		
		rep(i,t){
			cin>>in1[i]>>in2[i]>>in3[i]>>in4[i];
		}
		
		int y;
		cin>>y;
		
		rep(i,y){
			int a,b,c;
			cin>>a>>b>>c;
			
			int pos=0;
			int diff[2000]={0};
			rep(j,t){
				if(in3[j]==c){
					if(in4[j]==0)diff[in1[j]]--;
					else diff[in1[j]]++;
				}
			}
			
			int sum[2000]={0};
			reps(j,1,2000){
				sum[j] = sum[j-1]+diff[j];
			}
			
			int cont=0;
			reps(j,a,b){
				if(sum[j]>0)cont++;
			}
			printf("%d\n",cont);
		}
	}
}

Measured memory_bytes: 1180
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ll long long
#define pii pair<int,int>


void test_case()
{
    string s;
    cin>>s;
    int q, k=0;
    cin>>q;
    while(q--) {
        int t;
        cin>>t;
        if(t==1) {
            k^=1;
        }
        else if(t==2) {
            int f;
            string c;
            cin>>f>>c;
            if(f==1) {
                if(k==1) {
                    s+=c;
                } else {
                    c+=s;
                    s=c;
                }
            } else {
                if(k==0) {
                    s+=c;
                } else {
                    c+=s;
                    s=c;
                }
            }
        }
    }
    if(k)
        reverse(s.begin(), s.end());
    cout<<s;

}

int main()
{
    fastio
//    int t;
//    cin>>t;
//    while(t--)
    test_case();
}


Measured memory_bytes: 4072
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e18;
const int MAX=200010;
int n,m;
LL a[MAX],b[MAX];
int main()
{
    int i,j,k,t;
    while(~scanf("%d",&n))
    {
        LL sum=0;
        for(i=0;i<n;i++)
            scanf("%lld",&a[i]);
        for(i=0;i<n;i++)
            scanf("%lld",&b[i]);
        for(i=0;i<n;i++)
        {
            if(b[i]-a[i]>0)
                sum+=(b[i]-a[i])/2;
            else
                sum+=b[i]-a[i];
        }
//        printf("%d\n",sum);
        if(sum>=0)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}




Measured memory_bytes: 384