akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

int main(){

    long long int n, i,ans=1;
    double dans=1;
    scanf("%lld",&n);
    long long int *arr = (long long int*)malloc(n*sizeof(long long int));
    for(i=0;i<n;i++){
        scanf("%lld",arr+i);
        if(arr[i] == 0){
            printf("%d\n",0);
            return 0;
        }
    }
    for(i=0;i<n;i++){
        
        ans *= arr[i];
        dans *= (double)arr[i];
        if(dans>1000000000000000000||ans>1000000000000000000){
            printf("%d\n",-1);
            return 0;
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 2516
s = input()

a, b, c = 0, 0, 0

for i in range(len(s)):
    if s[i] == "a":
        a += 1
    elif s[i] == "b":
        b += 1
    else:
        c += 1


def func(j, k):
    if j + 1 == k or j - 1 == k or j == k:
        return True
    else:
        return False

ab, bc, cd = False, False, False
ab = func(a, b)
bc = func(b, c)
ca = func(c, a)

if ab and bc and ca:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define pb push_back
#define mp make_pair
bool isPrime(ll n) 
{ 
    
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
   
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (ll i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
} 
int minthis(int a, int b){
if(a < b){
return a;
}
return b;
}
int maxthis(int a, int b){
if(a > b){
return a;
}
return b;
}
int gcd(int a, int b){
    if( a<0 ) a = -a;
    if( b<0 ) b = -b;
    while( b!=0 ){
        a %= b;
        if( a==0 ) return b;
        b %= a;
    }
    return a;
}
 
int findLargestDivisor(int n) 
{ 
	int max = 1;
    for (int i = 2; i < n; i++) {        
        if(n %(i) == 0) { 
            max = i;
        } 
    }
    return max;     
} 
 
 
ll power(ll x, ll y)  
{  
    ll temp;  
    if(y == 0)  
        return 1;  
    temp = power(x, y / 2);  
    if (y % 2 == 0)  
        return temp * temp;  
    else
    {  
        if(y > 0)  
            return x * temp * temp;  
        else
            return (temp * temp) / x;  
    }  
}  


void solve(){	
	ll n; 
	cin >> n;
	ll sum = 0;
	unordered_map<ll,ll> mp;
	unordered_map<ll,ll>:: iterator it;
	for(ll i = 0 ;i < n ; i++){
		ll x; cin >> x;
		mp[x]++;sum+=x;
	}
	ll x;
	cin >> x;
	while(x--){
		ll a, b;
		cin >> a >> b;
		it = mp.find(a);
		if(it == mp.end()){
			 cout << sum << "\n";
			 continue;
		 }
		sum -= it->first*it->second;
		sum += it->second*b;
		mp[b]+=it->second;
		mp.erase(it);
		cout << sum << "\n";				
	}
}
  
int main(){ 
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;    
    //cin >> t;
    while(t--){
		solve();
	}
    return 0; 
}


Measured memory_bytes: 6632
#include<bits/stdc++.h>
#define N 305
using namespace std;
char c[N];
int i,j,k,l,s,n,m,ans,f[N][N][N];
int main() {
	scanf("%s",c+1);
	n=strlen(c+1);
	scanf("%d",&m);
	for (i=1;i<=n;i++) f[i][i][0]=1;
	for (i=1;i<n;i++) {
		if (c[i]==c[i+1]) f[i][i+1][0]=2;
		else f[i][i+1][1]=2;
	}
	for (i=1;i<=n;i++) for (j=1;j+i-1<=n;j++) for (k=0;k<=m;k++) {
		int L=j-1,R=j+i;
		if (!f[L+1][R-1][k]) continue;
		if (L&&R<=n) {
			if (c[L]==c[R]) f[L][R][k]=max(f[L][R][k],f[L+1][R-1][k]+2);
			else if (k<m) f[L][R][k+1]=max(f[L][R][k+1],f[L+1][R-1][k]+2);
		}
		f[L+1][R][k]=max(f[L+1][R][k],f[L+1][R-1][k]);
		f[L][R-1][k]=max(f[L][R-1][k],f[L+1][R-1][k]);
	}
	for (i=0;i<=n;i++) for (j=1;j<=n+1;j++) for (k=0;k<=m;k++) ans=max(ans,f[i][j][k]);
	printf("%d\n",ans);
}

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

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

int main()
{
    string a, b, pass;
    cin >> a >> b;
    int size = a.size() + b.size();
    for (int i = 0; i < size; i++)
    {
        if (i % 2)
            pass += b[i / 2];
        else
            pass += a[i / 2];
    }
    cout << pass << endl;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

#n = int(input())
a,b = [int(i) for i in readline().split()]

if 1 <= a <= 9 and 1 <= b <= 9:
    print(a*b)
else:
    print(-1)


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

int main()
{
	int N, d[100] = { 0 }, c = 0;
	bool sign = false;

	cin >> N;

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

	while (sign != true) {
		sign = true;
		for (int i = 0; i < N-1; i++) {
			for (int j = i+1; j < N; j++) {
				if (d[i] == d[j]) {
					sign = false;
					int d2[100] = { 0 };

					for (int k = 0; k < j; k++)
						d2[k] = d[k];
					for (int k = j + 1; k < N; k++)
						d2[k-1] = d[k];
					N -= 1;
					for (int k = 0; k < N; k++)
						d[k] = d2[k];
				}
			}
		}
	}

	for (int i = 0; i < N; i++)
		if (d[i] > 0) c++;

	cout << c << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n) {
    Int res = 1;
    while(n > 0) {
        if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % MOD;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}

Int X[100005];
Int W[100005];
vector<Int> moved;
Int ans[100005];

int main(){
    cin.tie(0);

    Int N, L, T; cin >> N >> L >> T;
    for (int i = 0; i < N; i++){
        cin >> X[i] >> W[i];
    }

    for (int i = 0; i < N; i++){
        Int pos = X[i];
        if (W[i] == 1) pos += T;
        else pos -= T;

        if (pos < 0) pos = L + (pos%L);
        else pos %= L;
        if (pos == L) pos = 0;

        moved.push_back(pos);
    }

    Int first;
    Int first_pos;
    Int cnt = 0;
    for (int i = 0; i < N; i++){
        if (W[i] == 1){
            for (int j = i+1; j < i+N; j++){
                if (W[j%N] == 2){
                    Int a, b;
                    if(X[i] > X[j]) b = -X[j];
                    else b = L-X[j];
                    a = X[i] + T;
                    b += T;
                    cnt += (a+b)/L;
                }
            }
            first = (i+cnt)%N;
            first_pos = (X[i]+T)%L;
            break;
        }
        if (i == N-1){
            for (int j = 0; j < N; j++){
                cout << moved[j] << endl;
            }
            return 0;
        }
    }
    sort(moved.begin(), moved.end());
    for (int i = moved.size()-1; i >= 0; i--){
        if (moved[i] == first_pos){
            for (int j = 0; j < N; j++){
                ans[(first+j)%N] = moved[(i+j)%N];
            }
            break;
        }
    }
    for (int i = 0; i < N; i++) cout << ans[i] << endl;
}


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

typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define V vector<int>
#define M map<int,int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int,V,greater<int>>

#define pb(a) push_back(a)
#define mp make_pair

#define dump(x)  cout << #x << " = " << (x) << "\n";
#define COUT(x) cout<<(x)<<"\n"

int main()
{
	int n, k = 0;
	cin >> n >> k;
	vector<int> list(n);
	int ct = 0;
	REP(i, n)
	{
		int buf = 0;
		cin >> buf;
		int a = buf * 2;
		int b = abs(k - buf) * 2;
		ct += min(a, b);
	}

	COUT(ct);

	return 0;
}

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

typedef pair<int,int> P;
#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define sz(x) ((int)(x).size())
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)

const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
vector<int> f[105];
vector<int> p[105];

int dp[15][2];

int main()
{
    int n;
    cin >> n;
    int temp;
    rep(i,n)
    {
        rep(j,10)
        {
            cin >> temp;
            f[i].push_back(temp);
        }
    }
    rep(i, n)
    {
        rep(j, 11)
        {
            cin >> temp;
            p[i].push_back(temp);
        }
    }
    int ans = -INF;
    for (int i = 1; i < 1024; i++)
    {
        vector<int> counter(n);
        rep(i, n)
        {
            counter[i] = 0;
        }
        for (int j = 0; j < 10; j++)
        {
            if (i & (1 << j))
            {
                for (int k = 0; k < n; k++)
                {
                    if(f[k][j]) counter[k]++;
                }
            }
        }
        int temp=0;
        for (int i = 0; i < n; i++)
        {
            temp += p[i][counter[i]];
        }
        ans = max(temp, ans);
        
    }
    cout << ans << endl;
    
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    int n,temp;
    cin>>n;
    int arr[3];
    for(int i=0;i<3;i++)
    {
        cin>>temp;
        arr[i]=temp;
    }
    vector<int>valpre{arr[0],arr[1],arr[2]};
    vector<int>valcur(3);
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<3;j++)
        {
            cin>>temp;
            arr[j]=temp;
        }
        for(int j=0;j<3;j++)
        {
            valcur[j]=max(valpre[(j+1)%3],valpre[(j+2)%3])+arr[j];
        }
        for(int j=0;j<3;j++)
        {
            valpre[j]=valcur[j];
        }
    }
    cout<<max(valpre[0],max(valpre[1],valpre[2]));
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cassert>
using namespace std;
typedef pair<int, int> P;

int n;
P p[200000];	//(val, pos)
int ans[200000];

signed main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) {
		int x; cin >> x;
		p[i] = P(x, i);
	}
	sort(p, p + n);
	
	//n / 2番かn / 2 - 1番がメジアン
	for (i = 0; i < n; i++) {
		if (i < n / 2) ans[p[i].second] = n / 2;
		else ans[p[i].second] = n / 2 - 1;
	}
	
	for (i = 0; i < n; i++) {
		cout << p[ans[i]].first << endl;
	}
	return 0;
}

Measured memory_bytes: 4480
import java.io.{BufferedReader, InputStreamReader}

import scala.collection.mutable.ArrayBuffer

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val Array(h, n) = in.readLine().split("\\s+").map(_.toInt)
    val magicSpecs = (1 to n).map { _ =>
      in.readLine().split("\\s+").map(_.toInt) match {
        case Array(a, b) => (a, b)
      }
    }.foldLeft(new ArrayBuffer[(Int, Int)](n)) {
      case (acc, spec) => acc += spec
    }

    val dp = Array.fill[Int](h + 1)(Integer.MAX_VALUE)
    dp(0) = 0

    for {
      (a, b) <- magicSpecs
      i <- (0 to h)
    } {
      val totalMp = dp(i)
      if (totalMp != Integer.MAX_VALUE) {
        val totalDamage = Math.min(i + a, h)
        dp(totalDamage) = Math.min(dp(totalDamage), totalMp + b)
      }
    }

    System.out.println(dp(h))
  }
}


Measured memory_bytes: 30844
#include <iostream>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

const int N = 1e5 + 2;

int n, k, h[N];
long long dp[N];

long long calc(int i)
{
    if (i == n - 1)
    {
        return 0;
    }
    long long &ret = dp[i];
    if (ret != -1)
    {
        return ret;
    }
    ret = 1e9;
    for (int j = 1; j <= k; ++j)
    {
        if (i + j >= n)
        {
            break;
        }
        ret = min(ret, calc(i + j) + abs(h[i + j] - h[i]));
    }
    return ret;
}

int main()
{
    memset(dp, -1, sizeof dp);
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        cin >> h[i];
    }
    cout << calc(0) << endl;
    return 0;
}

Measured memory_bytes: 4480
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>


#define fs first
#define sc second

using namespace std;


typedef long long ll;
typedef pair<ll, ll> P;


int main(){
    int x, a;
    cin >> x >> a;
    if(x < a){
        cout << 0 << endl;
    }
    else{
        cout << 10 << endl;
    }


    return 0;
}


Measured memory_bytes: 256
def main():
    S = list(input().split())
    for x in range(len(S)): S[x] = list(S[x])
    
    for x in range(len(S)):
        if x != len(S) - 1:
            print(S[x][0], end = "")
        else:
            print(S[x][0])


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

    static int[][] m(int n){
        int[][] b = new int[n][n];
        int l = n*n,x=n>>1,y=x+1;
        for(int i = 1;i<=l;i++){
            if(x>=n)x=0;
            if(y>=n)y=0;
            while(b[y][x]>0){
                y++;x--;
                if(x<0)x=n-1;
                if(y>=n)y=0;
            }
            b[y][x] = i;
            x++;y++;
        }
        return b;
    }

    public static void main(String... args) throws Exception {
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n<1)break;
            int[][] b = m(n);
            for(int i = 0;i<n;i++) {
                for (int j = 0; j < n; j++) {
                    System.out.printf("%4d", b[i][j]);
                }
                System.out.println();
            }
        }
    }
}

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

public class Main{
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){br = new BufferedReader(new InputStreamReader(System.in));}
        public FastReader(String fileName) throws FileNotFoundException{br = new BufferedReader(new FileReader(fileName));}
        String next(){while (st == null || !st.hasMoreElements()){try{st = new StringTokenizer(br.readLine());}catch (IOException  e){e.printStackTrace();}}return st.nextToken();}
        int nextInt(){return Integer.parseInt(next());}
        long nextLong(){return Long.parseLong(next());}
        double nextDouble(){return Double.parseDouble(next());}
        char[][] readCharArray(int n,int m) {
        	String str;
        	char[][] arr = new char[n][m];
        	for(int i=0;i<n;i++) {
        		str=nextLine();
        		for(int j=0;j<n;j++) {
        			arr[i][j]=str.charAt(j);
        		}
        	}
        	return arr;
        }
        char[][] readCharArray(int n){
        	return readCharArray(n,n);
        }
        int[] readArray(int n){int[] a=new int[n];for (int i=0; i<n; i++) a[i]=nextInt();return a;}
        long[] readLongArray(int n){long[] a=new long[n];for (int i=0; i<n; i++) a[i]=nextLong();return a;}
        String nextLine(){String str = "";try{str = br.readLine();}catch (IOException e){e.printStackTrace();}return str;}
    }
    static final Random random=new Random();
    static void ruffleSort(int[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n), temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
    	FastReader st = new FastReader();
    	int n = st.nextInt();
    	int mod = 1000000007;
    	long temp1=1,temp2=1,temp3=1;
    	for(int i=0;i<n;i++) {
    		temp1 = (temp1*10)%mod;
    		temp2 = (temp2*9)%mod;
    		temp3 = (temp3*8)%mod;
    	}
    	temp1 = (temp1+temp3)%mod;
    	temp2 = (temp2*2)%mod;
    	if(temp1<temp2) temp1+=mod;
    	System.out.println(temp1-temp2);
    }
}

Measured memory_bytes: 25784
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int count2(int n) {
    int ret = 0;
    while (n > 0 && n % 2 == 0) {
        n /= 2;
        ret++;
    }
    return ret;
}

void main() {
    readint;
    auto a = readints;
    int ans = a.map!(count2).reduce!((a, b) => min(a, b));
    writeln(ans);
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(){
    int num, i,count=0;
    char *str_a,*str_b,*str_c;

    scanf("%d",&num);

    str_a = (char*)malloc(sizeof(char)*num+1);
    str_b = (char*)malloc(sizeof(char)*num+1);
    str_c = (char*)malloc(sizeof(char)*num+1);

    scanf("%s",str_a);
    scanf("%s",str_b);
    scanf("%s",str_c);

    for(i=0;i<num;++i){
        if(str_a[i]==str_b[i] && str_a[i]==str_c[i]){
            continue;
        }else if(str_a[i]==str_b[i]){
            str_c[i]=str_b[i];
            count++;
        }else if(str_b[i]==str_c[i]){
            str_a[i]=str_b[i];
            count++;
        }else if(str_c[i]==str_a[i]){
            str_b[i]=str_c[i];
            count++;
        }else{
            str_b[i]=str_a[i];
            i--;
            count++;
        }
    }
    printf("%d",count);
    return 0;
}

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

syougen=[]
for i in range(n):
    a=int(input())
    
    for _ in range(a):
        x,y = map(int,input().split())
        syougen.append([i,x-1,y])

ans = 0

for bit in range(2**n):
    
    for s in syougen:
        if (bit>>s[0])&1 == 1:
            if (bit>>s[1])&1 != s[2]:
                break
    else:
        thisans = str(bin(bit)).count("1")
        ans=max(ans,thisans)
        # print(bin(bit))
print(ans)
        

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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0, sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    int N; cin >> N;
    string W[N]; REP(i,N) cin >> W[i];
    map<string,bool> m;
    char prev = W[0][0];
    REP(i,N){
        if(prev == W[i][0] && m.find(W[i]) == m.end()){
            prev = W[i].back();
            m[W[i]] = true;
        }
        else{
            cout << "No" << en;
            return 0;
        }
    }
    cout << "Yes" << en;
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var x, n int
	fmt.Scan(&x, &n)
	m := make(map[int]bool)
	for i := 0; i < n; i++ {
		var p int
		fmt.Scan(&p)
		m[p] = true
	}
	var pi, mi int
	for i := x; i <= x+110; i++ {
		if _, ok := m[i]; !ok {
			pi = i
			break
		}
	}
	for i := x; i >= x-110; i-- {
		if _, ok := m[i]; !ok {
			mi = i
			break
		}
	}
	if abs(pi-x) < abs(mi-x) {
		fmt.Println(pi)
	} else {
		fmt.Println(mi)
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}


Measured memory_bytes: 1840
#define SORT(v) sort(v.begin(), v.end())
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>
#include <cstdarg>
#include <cstdio>
#include <numeric>

// #include "ane.cpp"

#define INF (int)1e9
#define INFLL (long long)1e18
#define NMAX 200
#define MMAX 200
#define MOD 100000
using namespace std;

// コメントアウトするとdb_printf()を実行しない
#define DEBUG

//
//  ライブラリ
//

// よく使う型のエイリアス
typedef pair<int, int> p;
typedef long long ll;

// よく使う定数[配列]
static const int di[] = {-1, 0, 1, -1, 1, -1, 0, 1};
static const int dj[] = {-1, -1, -1, 0, 0, 1, 1, 1};

// デバッグ用printf
void db_printf(const char* format, ...){
    #ifndef DEBUG
    return;
    #endif
    va_list arg;
    va_start(arg, format);
    vprintf(format, arg);  // コンソールに出力
    va_end(arg);
}

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// Union-Find Tree
class UnionFindTree{
    struct node{
        int par;
    };
    std::vector<node> T;

    public:
    void init(int num){
        T.resize(num+1);    // ignore T[0]
        for (int i = 1; i <= num; ++i)
        {
            T[i].par = i;
        }
    }
    void unite(int x, int y){
        T[find(y)].par = find(x);
    }
    int find(int x){
        if (T[x].par == x) return x;
        else return T[x].par = find(T[x].par);
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
};

//
// ライブラリ終了
//


ll N,M,K,A,B,C,D,E;
int dp[NMAX][MMAX] = {};
string s;
string ans = "";

void solve(){
    // 解答アルゴリズム
    for(auto x: s){
        if(x == '1') {
            ans += '1';
        }
        else if(x == '0'){
            ans += '0';
        }
        else if(x == 'B' && ans.size()){
            ans.erase(ans.end()-1);
        }
    }
}
void debug(){
    // デバッグ用出力
}
void answer(){
    // 解答出力
    cout << ans << endl;
}
int main(int argc, char const *argv[])
{
    // 入力の読み込み，番兵法

    // Fill(dp, -1);
    cin >> s;
    solve();
    #ifdef DEBUG
    debug();
    #endif
    answer();

    return 0;
}

Measured memory_bytes: 256
// Karm Karta ja, Phal Ki Chinta na Kar:)
#include <bits/stdc++.h>
using namespace std;
#include<stdio.h>
typedef long long int ll;
#define PI 3.14159265358979323846
int main()
{
  long double a,b,x;
  cin>>a>>b>>x;
  long double t=a*a;
  long double h=x/t;
  long double z=b/2;
  long double ang=180,res=0.5;
  if(h<=z)
  {
     long double f=2*x;
     f/=(b*b);
     f/=a;
     long double r=atan(f);

     r/=PI;
     res-=r;
     res*=180;

     cout<<setprecision(10)<<fixed<<res;

  }
  else
  {
      long double g=a/2;
      g/=(b-h);
      long double ty=atan(g);
      ty/=PI;
      res-=ty;
      res*=180;
      cout<<setprecision(10)<<fixed<<res;
  }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for (int i = 0; i < n; ++i)
#define REP(i,k,n) for (int i = k; i <= n; ++i)
#define REPR(i,k,n) for (int i = k; i >= n; --i)
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair
#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()
#define debug1(a) cout<<" "<<#a<<" : "<<a<<"\n"
#define debug2(a,b) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<"\n"
#define debug3(a,b,c) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<"\n"
#define debug4(a,b,c,d) cout<<" "<<#a<<" : "<<a<<" "<<#b<<" : "<<b<<" "<<#c<<" : "<<c<<" "<<#d<<" : "<<d<<"\n"
// #define M 421412341324321
#define MOD 998244353

signed main()
{
	// ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
	int n;
	cin>>n;
	int a[n];
	int cnt[n+1]={0};
	rep(i,n)
	{
		cin>>a[i];
		cnt[a[i]]++;
	}
	vector <int> v;
	REP(i,1,n)
	{
		if (cnt[i]>0)
		{
			v.pb(cnt[i]);
		}
	}
	sort(all(v));
	vector <int> pre(sz(v)+1,0);

	rep(i,sz(v))
	{
		pre[i+1]=pre[i]+v[i];
	}

	REP(k,1,n)
	{
		int l =0, h = n/k;
		while(l<h)
		{
			int m = (l+h+1)/2;
			int t = 0;
			int x = lower_bound(all(v),m) - v.begin();
			t+=sz(v)-x + pre[x]/m;
			if (t>=k) l = m;
			else h = m-1;
		}
		cout<<l<<"\n";
	}

}


Measured memory_bytes: 10348
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;

typedef long long ll;

const int Maxn = 100005;

int n;
int A[Maxn], B[Maxn];

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &A[i]);
	for (int i = 0; i < n; i++)
		scanf("%d", &B[i]);
	ll sum1 = 0, sum2 = 0;
	for (int i = 0; i < n; i++)
		if (B[i] > A[i]) sum1 += (B[i] - A[i]) / 2;
		else sum2 += A[i] - B[i];
	printf("%s\n", sum1 >= sum2? "Yes": "No");
	return 0;
}

Measured memory_bytes: 384
import sys

readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    s = []
    for _ in range(M):
        k, *stmp = map(int, readline().split())
        s.append(set(stmp))
    p = list(map(int, readline().split()))

    ans = 0
    for i in range(2**N):
        flag = True
        onset = []
        for j in range(N):
            if (i>>j) & 1:
                onset.append(j+1)
        onset = set(onset)
        for m in range(M):
            union = onset & s[m]
            if len(union) % 2 != p[m]:
                flag = False
                break

        if flag:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100050;
int n,c,k;
int arr[MAXN];
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>c>>k;
	for(int i=1;i<=n;i++)cin>>arr[i];
	sort(arr+1,arr+1+n);
	int l=1,r=1;
	int cur_time=arr[1];
	int cur_peo=1;
	int ans=0;
	while(r<=n){
		while(r+1<=n&&arr[r+1]-cur_time<=k&&cur_peo+1<=c){r++;cur_peo++;}
		ans++;
		l=r+1;
		r=l;
		cur_time=arr[l];
		cur_peo=1;
	}
	cout<<ans;
	return 0;
}


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

#define vi                 vector<int>
#define mem(dp,a)           memset(dp,a,sizeof dp)
#define sonic               ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb(x)               push_back(x)
#define mp(x,y)             make_pair(x,y)
#define itr(it,c)           for(auto const &it : c)
#define all(c)              c.begin(), c.end()
#define ff                  first
#define ss                  second
#define INF                 INT_MAX
#define REPl(i,a,b)          for (ll i=a;i<b;i++)
#define REPi(i,a,b)			for (ll i=a;i<b;i++)
//*******Uer-Defined Functions*********//

//*******Functions end here************//
//*******Main func starts**************//
int main()
{
    sonic;
	int s, w;
	cin >> s >> w;
	if (w >= s) cout << "unsafe"<<endl;
	else{
		cout << "safe" << endl;
	}
}
//******Main Ends here****************//


Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  int W,H;
  cin>>W>>H;
  vector<pair<ll,bool>> v;
  for(int i=0;i<W;i++){
    ll p;
    cin>>p;
    v.push_back(make_pair(p,true));
  }
  for(int i=0;i<H;i++){
    ll q;
    cin>>q;
    v.push_back(make_pair(q,false));
  }

  sort(v.begin(),v.end());

  ll ans=0;
  ll w=W+1,h=H+1;
  for(int i=0;i<v.size();i++){
    if(v[i].second==true){
      ans=ans+h*v[i].first;
      w--;
    }else{
      ans=ans+w*v[i].first;
      h--;
    }
  }

  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 6384
ct=0
N,M,C=map(int,input().split())
B=list(map(int,input().split()))
A=[list(map(int,input().split())) for l in range(N)]

for i in range(N):
    a=0
    for j in range(M):
        a+=A[i][j]*B[j]
    if a+C>0:
        ct+=1
    else:
        pass
print(ct)





Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int a[maxn],b[maxn];
int main(){
int n;
while(~scanf("%d",&n))
{
    int x;
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);

    for(int i=0;i<n;i++)
    {
        scanf("%d",&x);
        if(i%2==0)
        a[x]++;
        else
           b[x]++;
    }
    int mx=0,nx=0,my,ny;
    for(int i=1;i<maxn;i++)
    {
       if(a[i]>mx){
            mx=a[i];
            my=i;}
    }
    for(int i=1;i<maxn;i++)
    {
       if(b[i]>nx){
            nx=b[i];
            ny=i;}
    }
    if(my!=ny)
    {
     printf("%d\n",n-nx-mx);
    }
    else{
     int rnx=0;
    for(int i=1;i<maxn;i++)
    {
       if(b[i]>rnx&&i!=my){
            rnx=b[i];
              }
    }
    int rmx=0;
       for(int i=1;i<maxn;i++)
    {
       if(a[i]>rmx&&i!=my){
           rmx=a[i];
              }
    }
    printf("%d\n",min(n-mx-rnx,n-rmx-nx));
    }

}
}


Measured memory_bytes: 1024
from collections import deque
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
Gd = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    Gd[a].append(b)
    Gd[b].append(a)
cnt = 0
for a in range(1,N+1):
    for b in G[a]:
        Gd[a].remove(b)
        Gd[b].remove(a)
        hist = [0 for _ in range(N+1)]
        stack = deque([1])
        while stack:
            cur = stack.popleft()
            hist[cur]=1
            for x in Gd[cur]:
                if hist[x]==0:
                    stack.append(x)
        if sum(hist)<N:
            cnt += 1
        Gd[a].append(b)
        Gd[b].append(a)
print(cnt//2)


Measured memory_bytes: 3316
a,b=map(int,input().split())
zz=str(a)*int(b)
yy=str(b)*int(a)
# print(zz)
# print(yy)
arr=[]
arr.append(zz)
arr.append(yy)
res = min(filter(lambda s:isinstance(s, str),arr))
print(res)

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

int main(){
    int v1, v2, v3, v4, v5, d;
    cin >> v1 >> v2 >> v3 >> v4 >> v5 >> d;

    if (max({v1, v2, v3, v4, v5}) > 123 || min({v1, v2, v3, v4, v5}) < 0){
        exit(0);
    }
    if (!(v1 < v2 && v2 < v3 && v3 < v4 && v4 < v5)){
        exit(0);
    }

    if (v5 - v1 > d){
        cout << ":(" << endl;
    } else {
        cout << "Yay!" << endl;
    }
}

Measured memory_bytes: 256
//https://atcoder.jp/contests/abc098/tasks/arc098_b
//xor x^x で打ち消せる
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define FOR(i,a,b) for(int64_t i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in"); //input.txt
    std::cin.rdbuf(in.rdbuf());
#else
    cin.tie(0);
    ios::sync_with_stdio(false);
#endif
    ll N; cin>>N;
    vector<ll> an(N);
    for(auto&& a:an){
        cin>>a;
    }
    ll left=0;
    ll right=0;
    ll sum=0;
    ll xo=0;
    ll ans=0;
#if 01
    REP(l,N){
        while(right<N&&((sum+an[right]) == (xo^an[right]))){ //r動かす
            sum += an.at(right);
            xo ^= an.at(right);
            ++right;
        }
        ans += (right-l);
        sum -= an.at(l);
        xo ^= an.at(l);
    }
#else
    while(right<N){
        if (right>=N) break;
        auto a=an.at(right);
        auto n_sum = sum + a;
        auto n_xo = xo ^ a;
        if (n_sum == n_xo) {
            sum = n_sum;
            xo = n_xo;
            ++ans;
            ++right;
        } else {
            do {
                auto dv=an.at(left);
                sum -= dv;
                xo ^= dv;
                ++left;
            } while(sum != xo);
            ans += (right-left);
        }
    }
    while(right - left > 0) {
		auto dv = an.at(left);
		sum -= dv;
		xo ^= dv;
		++left;
        if (sum == xo) {
	        ans += (right - left);
        }else{
            break;
        }
	}
#endif
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
K = int(input())

def S(n):
    return n / sum(map(int, str(n)))

num = min(K, 8)
for n in range(1, num + 1):
    print(n)

d = 10
n = 10
Sn = S(10 - 1)
while num < K:
    for j in range(100):
        Snext = S(n + d - 1)
        if Snext < Sn: break

        print(n - 1)
        num += 1
        if num == K: break

        n += d
        Sn = Snext

    d *= 10
    n = (n // d + 1) * d


Measured memory_bytes: 3188
#include<algorithm>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<stack>
#include<string>
#include<deque>
#include<queue>
#include<vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll mod = 1e9+7;
const double PI = acos(-1);  // PI = 3.141593...

int main() {
    ll n;
    cin >> n;
    if(n%2 == 1) {
        cout << 0 << endl;
        return 0;
    }
    ll pow = 10;
    ll cnt = 0;
    while(pow <= n) {
        cnt += n / pow;
        pow *= 5;
    } 
    cout << cnt << endl;
    return 0;
}

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

int64_t calc(vector<int64_t> &memo, int x){
  if(x == 0){
    return memo[x] = 2;
  }else if(x == 1){
    return memo[x] = 1;
  }
  
  if(memo[x] != 0){
    return memo[x];
  }else{
    return memo[x] = calc(memo, x-2) + calc(memo, x-1);
  }
}

int main(){
  int n = 0;
  cin >> n;
  vector<int64_t> memo(n+1);
  cout << calc(memo, n) << endl;
}

Measured memory_bytes: 256
<?php
//error_reporting(0);
//$N = trim(fgets(STDIN));
list($N,$M) =  explode(" ",trim(fgets(STDIN)));
//$H =  explode(" ",trim(fgets(STDIN)));
for($i=0;$i<$N;$i++) {
  list($A,$B) =  explode(" ",trim(fgets(STDIN)));
  $m[$M-$A][]=$B;
}
$pq = new SplPriorityQueue();
$pq->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);
$res=0;
for($i=$M;$i>=0;$i--) {
  if (isset($m[$i])) {
    foreach($m[$i] as $v) {
      $pq->insert($v,$v);
    }
  }
  if ($pq->isEmpty()==false) {
    $res += $pq->extract();
  }
}
printf("%d\n",$res);


Measured memory_bytes: 59896
#define taskname "test"

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long lli;
typedef pair<int, int> pii;
const int maxn = 105;
const int lim = 4000;
const int mod = 1e9 + 7;
int n, k;

int dp[maxn][lim];

void read_input()
{
    cin >> n >> k;
}

int power(int x, int n)
{
    if(n == 0) return 1;
    int t = power(x, n / 2);
    if(n % 2 == 0) return 1LL * t * t % mod;
    else return 1LL * t * t % mod * x % mod;
}

void add(int&tar, int val)
{
    tar += val;
    if(tar >= mod) tar -= mod;
}

void solve()
{
    int total_a = k * (k + 1) / 2 * n * 1LL * power(k + 1, n - 1) % mod;
    int total_t = 0;
    fill_n(&dp[0][0], sizeof(dp) / sizeof(dp[0][0]), 0);
    for(int a = 0; a <= k; ++a)
        add(dp[n][a / n], 1);
    for(int i = n - 1; i > 0; --i)
        for(int j = 0; j < lim; ++j)
            for(int a = 0; a <= k; ++a)
            {
                if(a <= i) add(dp[i][j + (a + j) / i], dp[i + 1][j]);
                else add(dp[i][j], dp[i + 1][j]);
            }
    for(int j = 0; j < lim; ++j)
        add(total_t, j * 1LL * dp[1][j] % mod);
    cout << (total_a - total_t + mod) % mod << '\n';
}

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


Measured memory_bytes: 1920
#include<bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;

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

int Y[4]={-1,0,1,0};
int X[4]={0,1,0,-1};
string g="5555555555555555";

bool in(int a,int b){
  if(a<0 || b<0 || 4<=a || 4<=b)return false;
  return true;
}

string bfs(string s,int index){
  s[index]++;
  if(s[index]!='5')return s;

  int d[16]={};
  queue<pii> q;
  for(int i=0;i<4;i++)q.push(mp(0,mp(index,i)));

  while(!q.empty()){
    pii u=q.front();
    q.pop();

    int ny=u.s.f/4+Y[u.s.s],nx=u.s.f%4+X[u.s.s];
    if(!in(ny,nx))continue;
    int nindex=ny*4+nx;
    if(d[nindex]==u.f+1 && s[nindex]=='5')continue;
    if(s[nindex]=='5')q.push(mp(u.f+1,mp(nindex,u.s.s)));
    else {
      s[nindex]++;
      d[nindex]=u.f+1;
      if(s[nindex]=='5'){
	for(int i=0;i<4;i++)q.push(mp(u.f+1,mp(nindex,i)));
      }
    }
  }
  return s;
}

int main()
{

  int a;
  string s;

  for(int i=0;i<16;i++){
    cin>>a;
    if(a==0)s+='5';
    else s+=(a+'0');
  }

  map<string,int> m;
  queue<string> q;
  int ans=-1;
  q.push(s);
  m[s]=0;

  while(q.size()){
    string u=q.front();
    q.pop();
    int cost=m[u];

    if(5<cost)break;

    if(u==g){
      ans=cost;
      break;
    }

    for(int i=0;i<16;i++){
      string t=u;
      if(t[i]=='5')continue;
      t=bfs(t,i);

      if(m.find(t)==m.end()){
	m[t]=cost+1;
	q.push(t);
      }
    }
  }

  cout<<ans<<endl;

  return 0;
}

Measured memory_bytes: 10992
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,m,n) for (int i = m; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

/*
  delta(V v, update(V t))
  index(V v) -> int
*/
template<class V, class Delta, class Index>
vector<ll> bfs(int n, V s, Delta delta, Index index) {
  vector<ll> dist(n,-1);
  queue<V> que;
  dist[index(s)] = 0;
  que.push(s);
  while(!que.empty()) {
    V v = que.front(); que.pop();
    auto update = [&](V t) {
      if (dist[index(t)] == -1) {
        dist[index(t)] = dist[index(v)]+1;
        que.push(t);
      }
    };
    delta(v,update);
  }
  return dist;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n, u, v;
  cin >> n >> u >> v; u--; v--;
  vector<vector<int> > G(n);
  rep(i,n-1) {
    int a, b;
    cin >> a >> b; a--; b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }
  auto index = [](int v){ return v;};
  auto delta = [&](int v, auto update) {
    for (auto&& to : G[v]) {
      update(to);
    }
  };
  auto dist_t = bfs(n, u, delta, index);
  auto dist_a = bfs(n, v, delta, index);
  ll ans = 0;
  rep(i,n) {
    if (dist_t[i] < dist_a[i]) chmax(ans, dist_a[i]-1);
  }
  cout << ans << endl;
  return 0;
}

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

int n;
vector<int> a;
int ans;

template <class T>
void readVector(int n, vector<T> &v){
	for(int i=0; i<n; ++i){
		T t;
		cin >> t;
		v.push_back(t);
	}
}

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	cin >> n;
	readVector(n, a);
	sort(a.begin(), a.end());
	int p = 0;
	for(int i=1; p<n; ++i){
		if(a[p] != i) continue;
		if(p+i-1 < n && a[p+i-1] == i){
			p += i;
		}
		while(p < n && a[p] == i){
			++p;
			++ans;
		}
	}
	cout << ans << "\n";
}

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

int main(){
  int N;
  cin >> N;
  
  int x = 0;
  for (int i =0; i < N; i++){
    int l, r;
    cin >> l >> r;
    x += (r - l + 1);
  }
  cout << x << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long a[200001], sum[200001], n, x, ans;
double s;
int main()
{
	scanf("%d", &n);
	for (register long long i=1; i<=n; ++i)
	{
		scanf("%d", &a[i]);
		++sum[a[i]];
	}
	for (register long long i=1; i<=n; ++i)
		if (sum[a[i]]>=2) s+=(sum[a[i]]-1)*1.0/2;
	x=s;
	for (register long long i=1; i<=n; ++i)
	{
		ans=x-(sum[a[i]])*(sum[a[i]]-1)/2;
		ans+=(sum[a[i]]-1)*(sum[a[i]]-2)/2;
		cout << ans << endl; 
	}
	return 0;
}

Measured memory_bytes: 4736
from collections import deque
h,w = map(int,input().split())
list1 = [list(input()) for i in range(h) ]
visited = [[-1]*w for i in range(h)]
black_count = 0
for i in range(h):
	black_count += list1[i].count("#")
def bfs(maze, visited, sy, sx, gy, gx):
	queue = deque([[sy, sx]])
	visited[sy][sx] = 0
	while queue:
		y, x = queue.popleft()
		if [y, x] == [gy, gx]:
			return visited[y][x]
		for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
			new_y, new_x = y+j, x+k
			if 0 <= new_y < h and \
				0 <= new_x < w and\
				maze[new_y][new_x] == "." and \
				visited[new_y][new_x] == -1:
				
				visited[new_y][new_x] = visited[y][x] + 1
				queue.append([new_y, new_x])
	return -1

shortest = bfs(list1,visited,0,0,h-1,w-1)
if shortest == -1:
	print(-1)
	exit()
print(h*w - black_count - shortest-1) #-1はスタート地点

Measured memory_bytes: 40432
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 9999999999;
const int INFI = 2147483647;
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
  T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }


void solve(){
  int n,m; cin >>n >>m;
  vector<int> s(m), c(m);
  rep(i, m) cin >>s.at(i) >>c.at(i);

  bool zero = false;

  vector<int> num(n, -1);
  rep(i, m){
    if (s.at(i) == 1 && c.at(i) == 0) zero = true;
    if (num.at(s.at(i)-1) != -1 && num.at(s.at(i)-1) != c.at(i)){
      cout <<-1 <<endl;
      return;
    }
    num.at(s.at(i)-1) = c.at(i);
  }
  if (zero && n == 1){
    cout <<0 <<endl;
    return;
  }
  if (zero){
    cout <<-1 <<endl;
    return;
  }
  // 1桁目が0ではない
  if (n == 1){
    cout <<(num.at(0) == -1 ? 0 : num.at(0)) <<endl;
    return;
  }
  rep(i, n){
    if (i==0){
      cout <<(num.at(i) == -1 ? 1 : num.at(i));
    }else{
      cout <<(num.at(i) == -1 ? 0 : num.at(i));
    }
  }
  cout <<endl;
}

int main() {
  solve();  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(std::unique(all(x)), x.end());
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
const double PI=acos(-1);
using namespace std;
vector<int> dx={1,0,-1,0};
vector<int> dy={0,1,0,-1};
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...));
}

int main() {
    int n,t;
    cin>>n>>t;
    vector<pair<int,int>> vec(n);
    rep(i,n) {
        int a,b;
        cin>>a>>b;
        vec[i]=make_pair(a,b);
    }
    sort(all(vec));
    
    auto dp=make_vec<int>(n+10,4000);
    rep(i,n) {
        rep(w,t) {
            if(vec[i].first <= w) dp[i+1][w]=max(dp[i][w-vec[i].first]+vec[i].second, dp[i][w]);
            else dp[i+1][w]=dp[i][w];
        }
    }
    
    int ans=0;
    rep(i,n) ans=max(ans,dp[i][t-1]+vec[i].second);
    cout<<ans<<endl;
}


Measured memory_bytes: 47488
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long double PI = (acos(-1));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int ctoi(char c)
{
    switch (c)
    {
    case '0':
        return 0;
    case '1':
        return 1;
    case '2':
        return 2;
    case '3':
        return 3;
    case '4':
        return 4;
    case '5':
        return 5;
    case '6':
        return 6;
    case '7':
        return 7;
    case '8':
        return 8;
    case '9':
        return 9;
    default:
        return 0;
    }
}
int main()
{
    int a, b, k;
    cin >> a >> b >> k;
    if (b-a+1>=2*k)
    {
        for (int i = 0; i < k; i++)
        {
            cout << a + i << endl;
        }
        for (int i = k-1; i >=0; i--)
        {
            cout << b - i << endl;
        }
    }else{
        for (int i = a; i <= b; i++)
        {
            cout << i << endl;
        }
    }

    
}

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

long long calc(long long A){

    if(A <= 0) return 0;
    A ++;
    long long ans = 0;

    for(int i = 0; i < 50; i++)
    {
        long long loop = (1LL << (i + 1));
        long long cnt = (A / loop) * (loop / 2);

        cnt += max(0LL, (A % loop) - (loop / 2));
        if (cnt % 2 == 1) {
            ans += 1LL << i;
        }

    }
    return ans;

}

void solve(long long A, long long B){
    long long ans = calc(B) ^ calc(A - 1);
    cout << ans << endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256
n = int(input())
ls = list(map(int,input().split(' ')))
f=0
for i in range(0,n):
    if(ls[i]%2==0):
        if(ls[i]%3!=0 and ls[i]%5!=0):
            f=1
if(f):
    print("DENIED")
else:
    print("APPROVED")
        

Measured memory_bytes: 2940
#include<iostream>
#include<string.h>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> pii;

int main()
{
  int a,b,c;
  int i,j;

  cin>>a>>b>>c;
  int max=(a+b)*c;
  int x=a+b;
  for(i=c;i<=max;i=i+60){
    // cout<<i<<endl;
    if(i%x<=a){
      cout<<i<<endl;
      return 0;
    }
  } 

  cout<<"-1"<<endl;
}

Measured memory_bytes: 3112
#include <iostream>
#include <math.h>
#include <limits>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <map>
#include <utility>
using namespace std;
#define rep(i, n) for (int i =0; i < (int)(n); i++)
typedef pair<int, string> P;




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

    sort(s.begin(), s.end());
    if (s.at(0) == s.at(1) && s.at(2) == s.at(3)&& s.at(1) != s.at(2))cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256