akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <deque>
#include <utility>
#include <algorithm>

int main() {
    long long n, m, a, b, c;
    std::cin >> n >> m;
    std::vector<std::deque<std::pair<long long, long long>>> g(n);
    for (auto i = 0ll; i < m; i++) {
        std::cin >> a >> b >> c;
        a--; b--;
        g[a].push_back({ b, -c });
    }

    std::vector<long long> dist(n, 1ll<<60);
    dist[0] = 0ll;

    for (auto i = 0ll; i < n - 1; i++) {
        for (auto from = 0ll; from < n; from++) {
            for (auto edge : g[from]) {
                dist[edge.first] = std::min(dist[edge.first], dist[from] + edge.second);
            }
        }
    }

    auto memo = dist[n - 1];

    for (auto i = 0ll; i < n; i++) {
        for (auto from = 0ll; from < n; from++) {
            for (auto edge : g[from]) {
                dist[edge.first] = std::min(dist[edge.first], dist[from] + edge.second);
            }
        }
    }

    if (memo == dist[n - 1]) std::cout << -dist[n - 1] << std::endl;
    else std::cout << "inf" << std::endl;

    return 0;
}

Measured memory_bytes: 896
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmpfunc(const void *a,const void *b){
    if(*(long long int*)a==*(long long int*)b)
    return 0;
    else if(*(long long int*)a>*(long long int*)b)
    return -1;
    else
    return 1;
}
long long int max(long long int a,long long int b)
{
    return a>b?a:b;
}
int main()
{
    int x,y,a,b,c;
    long long int total=0;
    scanf("%d %d %d %d %d",&x,&y,&a,&b,&c);
    long long int red[a],green[b],coulourless[c],temp[x+y+c];
    for(int i=0;i<a;i++)
    {
       scanf("%lld",&red[i]);
    }
    for(int i=0;i<b;i++)
    {
        scanf("%lld",&green[i]);
    }
    for(int i=0;i<c;i++)
    {
        scanf("%lld",&coulourless[i]);
    }
    qsort(red,a,sizeof(long long int),cmpfunc);
    qsort(green,b,sizeof(long long int),cmpfunc);
    for(int i=0;i<x;i++)
    temp[i]=red[i];
    for(int i=0;i<y;i++)
    temp[x+i]=green[i];
    for(int i=0;i<c;i++)
    temp[x+y+i]=coulourless[i];
    qsort(temp,(x+y+c),sizeof(long long int),cmpfunc);
    for(int i=0;i<x+y;i++)
    total+=temp[i];
    printf("%lld",total);
}


Measured memory_bytes: 7660
/**
*
* Author: MARC
* Lang: GNU C++14
*
**/

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define ii pair < int , int >
#define LS pair < ll , string >

typedef unsigned long long ull;
typedef long double ldbl;
typedef long long ll;
typedef double dbl;

const ldbl E = 2.71828182845904523536;
const ldbl pi = acos(-1);
const dbl eps = 1e-9;
const ll mod = 1e9+7;
const ll inf = 1LL<<30;

/** /////////// ** Code ** /////////// **/

const int N=100100;

int main()
{
    string s; cin>>s;
    for(int i=0 ; i<s.length() ; i++)
    if(s[i] == '9'){
        cout<<"Yes";
        return 0;
    }

    cout<<"No";
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
C - Lining Up
https://atcoder.jp/contests/arc066/tasks/arc066_a

"""
import sys

from collections import Counter

def solve(N, array):
    cnt = Counter(array)
    res = []
    for k, v in cnt.items():
        if k == 0 and v > 1:
            return 0
        if k != 0 and v != 2:
            return 0
        if N%2:
            if k%2:
                return 0
            res.append(v)
        else:
            if k%2 == 0:
                return 0
            res.append(v)
    ans = 1
    MOD = 10**9 + 7
    for r in res:
        ans = (ans * r) % MOD
    return ans


def main(args):
    N = int(input())
    array = [int(a) for a in input().split()]
    ans = solve(N, array)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 14812
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 100000;
int A[MAX],n;

int partition(int p,int r){
    int x = A[r];
    int i = p-1;
    for (int j = p; j <= r-1 ; j++) {
        if(A[j] <= x){
            i ++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return i + 1;
}

int main (){

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    
    int x = partition(0,n-1);
     for(int i=0; i<n; i++){
        if(i==x){
            cout << '[' << A[i] << ']';
        }
        else{
            cout << A[i];
        }
        if(i<n-1){
            cout << ' ';
        }
        else{
            cout << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1544
const bubbleSort = (n, a) => {
  let isChanged = true;
  let index = 0;
  let counter = 0;
  while (isChanged) {
    isChanged = false;
    for (let j = n - 1; j > index; j--) {
      if (a[j - 1] > a[j]) {
        let tmp = a[j - 1];
        a[j - 1] = a[j];
        a[j] = tmp;
        isChanged = true;
        counter += 1;
      }
    }
    index += 1;
  }
  console.log(a.join(" "));
  console.log(counter);
};

process.stdin.resume();
process.stdin.setEncoding("utf8");
let input_string = "";

process.stdin.on("data", chunk => {
  input_string += chunk;
});

process.stdin.on("end", () => {
  const lines = input_string.split("\n").filter(v => {
    return v !== "";
  });
  bubbleSort(lines[0], lines[1].split(" ").map(i => parseInt(i, 10)));
});



Measured memory_bytes: 15592
import sys
sys.setrecursionlimit(1000000)

N = int(input().strip())

X = {}
Y = {}
G = (X, Y)

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = []
  if y not in Y: Y[y] = []
  X[x].append(y)
  Y[y].append(x)


def dfs_visit(visited, u, i):
  if u in visited[i]: return
  visited[i].add(u)
  for v in G[i][u]:
    dfs_visit(visited, v, (i + 1) % 2)


count = 0
i = 0
while len(X) > 0:
  visited = (set(), set())
  x = X.__iter__().__next__()
  dfs_visit(visited, x, 0)

  for x in visited[0]:
    count += len(visited[1]) - len(X.pop(x))

print(count)


Measured memory_bytes: 87256
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <tuple>

using ll = long long int;
using ul = unsigned long long int;
const ll LL_MAX (1LL<<60);
const ll MOD (1000000007);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

using T = tuple<ll,ll>;
using Graph = vector<vector<T>>;

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

    ll n;
    cin >>n;

    string s (to_string(n));
    ll m = s[s.size()-1]-48;
    if (m==3)
        cout << "bon" << endl;
    else if (m==0 || m==1 || m==6 || m==8)
        cout << "pon" << endl;
    else 
        cout << "hon" << endl;

    return 0;
}


Measured memory_bytes: 3648
float x,y,v,w,x0,y0,S;
main(){
	scanf("%f,%f",&x0,&y0);
	v=x0,w=y0;
	for(;~scanf("%f,%f",&x,&y);){
		S+=(v-x)*(w+y);
		v=x,w=y;
	}
	printf("%f\n",S/2);
	exit(0);
}

Measured memory_bytes: 0
#include <stdio.h>
using namespace std;
int main(){
 int a,b,c;scanf("%d%d%d",&a,&b,&c);
  if(a+b+c!=17)return puts("NO"),0;
  else if(a*a+b*b+c*c!=99)return puts("NO"),0;
  else if(a*b*c!=175)return puts("NO"),0;
  else puts("YES");
}

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

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cout.precision(10);
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << max((a * c), max((a * d), max((b * c), (b * d)))) << endl;

	return 0;
}

Measured memory_bytes: 3684
n,m,c = list(map(int,input().split()))
a = list(map(int,input().split()))

su = 0
co = 0
for i in range(n):
    b = list(map(int,input().split()))
    for j in range(m):
        co += a[j]*b[j]
    if co + c > 0:
        su += 1
    co = 0
print(su)

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

typedef long long ll;

ll mod = 1e9 + 7, fac[((int)1e6 + 5)], v[((int)1e6 + 5)];

ll modRec(ll a, ll b) {
	if (b == 0)return 1;
	if (b % 2 == 0)return modRec((a * a) % mod, b / 2);
	return ((a % mod) * modRec((a * a) % mod, b / 2)) % mod;
}

int main() {
	fac[0] = 1, v[0] = 1;
	for (int i = 1; i <= 1e6; i++) {
		fac[i] = (i * fac[i - 1]) % mod;
		v[i] = modRec(fac[i], mod - 2);
	}
	ll h, w, a, b, ans = 0; cin >> h >> w >> a >> b;
	for (ll i = b; i < w; i++) {
		ll p = i, q = h - a - 1, r = w - i - 1, s = a - 1;
		ll x = (((fac[p + q] * v[p]) % mod) * v[q]) % mod;
		x *= (((fac[r + s] * v[r]) % mod) * v[s]) % mod;
		ans = (ans + x) % mod;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 15872
import sys

def line(n, N):
    return list(range(2*N)[n:n+N])

def convert(T):
    if T == "Red":
        return "R"
    elif T == "Blue":
        return "B"
    else:
        sys.exit()
    
def ask(question):
    print("?", end=" ")
    [print(x+1, end=" ") for x in question]
    print(flush=True)

def run(X):
    question = line(X, N)
    ask(question)
    T = input()
    visited[X] = convert(T)


N = int(input())
visited = ["*"]*2*N
Aestimated = ["*"]*2*N
L = 0
R = N
run(L)
run(R)
while True:
    M = int((L+R)/2)
    run(M)
    if visited[L] == visited[M]:
        L = M
    elif visited[R] == visited[M]:
        R = M
    if R-L == 1:
        break

Aestimated[L] = visited[L]
Aestimated[R+N-1] = visited[R]

S2 = list(range(R,R+N-1))
S1 = list(set(range(2*N)) - set(S2) - {L} - {R+N-1}) 
for s1 in S1:
    S = S2 + [s1]
    ask(S)
    T = input()
    Aestimated[s1] = convert(T)

for s2 in S2:
    S = S1 + [s2]
    ask(S)
    T = input()
    Aestimated[s2] = convert(T)

print("!", "".join(Aestimated), flush=True)


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

void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}

int main(){


    ll A, B, C;
    cin >> A >> B >> C;
    cout << B + min(A + B + 1, C) << endl;


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	string s;
	cin>>s;
	ll count=0;
	ll len=s.length();
	for(ll i=0;i<len;i++){
		if(s[i]=='x') count++;
	}
	
	if(count<=7){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
}

Measured memory_bytes: 256
n,c = map(int,input().split())
d = [list(map(int,input().split())) for i in range(c)]
s = [list(map(int,input().split())) for i in range(n)]
x = [0] * c
y = [0] * c
z = [0] * c
for i in range(n):
    for j in range(n):
        a = (i+j) % 3
        if a == 0:
            x[s[i][j]-1] += 1
        if a == 1:
            y[s[i][j]-1] += 1
        if a == 2:
            z[s[i][j]-1] += 1
ans = 10 ** 16
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and i != k and j != k:
                o = 0
                for l in range(c):
                    o += d[l][i] * x[l]
                p = 0
                for l in range(c):
                    p += d[l][j] * y[l]
                q = 0
                for l in range(c):
                    q += d[l][k] * z[l]
                ans = min(ans,o+p+q)
print(ans)

Measured memory_bytes: 11484
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    int ary[n];
    rep(i,n) cin >> ary[i];

    sort(ary, ary+n);
    int tmp = ary[0];
    int cnt = 1;
    rep(i,n)
    {
	    if (tmp != ary[i])
	    {
		cnt++;
		tmp = ary[i];
	    }
    }
    cout << cnt << endl;
}


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

namespace D
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var xy = Console.ReadLine().Trim().Split(' ').Select(long.Parse).ToArray();
            var p = (long)Math.Pow(10, 9) + 7;
            var step = (xy[0] + xy[1]);
            if ((step % 3) != 0)
            {
                Console.WriteLine(0);
                return;
            }
            var nm = step / 3;
            var n = xy[0] - nm;
            var m = xy[1] - nm;
            if (n < 0 || m < 0)
            {
                Console.WriteLine(0);
                return;
            }
            Console.WriteLine(CombinationCount((n + m), n, p));
        }

        static long PermutationCount(long n, long k, long mod)
        {
            if (n < k) throw new ArgumentException();
            var result = 1L;
            for (var i = 0; i < k; i++)
                result = (result * (n - i) % mod) % mod;
            return result;
        }

        static long CombinationCount(long n, long k, long mod)
        {
            if (n < k) throw new ArgumentException();
            k = Math.Min(k, n - k);
            var top = PermutationCount(n, k, mod);
            var bottom = PermutationCount(k, k, mod);
            return (top * Inverse(bottom, mod)) % mod;
        }

        static long Inverse(long x, long mod)
        {
            return Power(x, mod - 2, mod);
        }

        static long Power(long x, long y, long mod)
        {
            long result = 1;
            while (y > 0)
            {
                if ((y & 1) == 1) result = ((result % mod) * (x % mod)) % mod;
                x = ((x % mod) * (x % mod)) % mod;
                y >>= 1;
            }
            return result;
        }
    }
}


Measured memory_bytes: 13396
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>

using namespace std;

int main(){
	int st_len_temp=0;
	int st_begin=0;
	int ch=0;
	string st;
	getline(cin,st);
	for(int i=0;i<st.size();i++){
		st_len_temp++;
		if(st[i]==' '||st[i]==','||st[i]=='.'){
			st_len_temp--;
			if(st_len_temp>2&&st_len_temp<7){
				if(ch==1)
				printf(" ");
				for(int j=st_begin;j<i;j++){
					printf("%c",st[j]);
				}
				ch=1;
			}
			st_len_temp=0;
			st_begin=i+1;
		}
	}
	printf("\n");
}


Measured memory_bytes: 3048
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,x,y) for(int i=(int)(x);i<(int)(y);++i)
#define FORE(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define PB push_back
#define ST first
#define ND second
#define db(v...) cerr<<#v<<"="<<v<<"\n";
#define dbr(v,x,y) FORE(_I,x,y){cerr<<#v<<"["<<_I<<"]="<<v[_I]<<"\n";}
#define dba(v) int _I=0;for(auto _it:v)cerr<<#v<<"["<<_I++<<"]="<<_it<<"\n";
typedef long long ll;
typedef pair<int,int> pii;
const int INF=2e9;
const int MOD=1e9+7;
const int MAXN=1e6+7;

int ans=0;
int n,m,k,q;

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m>>k;
    cout<<k<<" "<<n<<" "<<m<<"\n";
}


Measured memory_bytes: 256
n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

an = n
bn = n
for i in range(n):
    an *= a
    an *= (a + b)
    an %= mod
    bn *= b
    bn *= (a + b)
    bn %= mod
sum_a = an
sum_b = bn
inv_ab = mod_inv(a + b, mod)
for i in range(1, n):
    an *= (n + i)
    an *= mod_inv(i, mod)
    an *= b
    an *= inv_ab
    an %= mod
    bn *= (n + i)
    bn *= mod_inv(i, mod)
    bn *= a
    bn *= inv_ab
    bn %= mod
    sum_a += an
    sum_b += bn
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q *= (a + b)
    q %= mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)

Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace ConsoleApplication2
{
    class Program
    {

        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');

            int n = int.Parse(input[0]);
            int d = int.Parse(input[1]);
            double[,] x = new double[n,d];
            for (int i = 0; i < n; i++)
            {
                input = Console.ReadLine().Split(' ');
                for (int j = 0; j < d; j++)
                {
                    x[i, j] = double.Parse(input[j]);
                }

            }
            int cnt = 0;
            for (int i = 0; i < n - 1; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    double l = 0;
                    for (int k = 0; k < d; k++)
                    {
                        l += (x[i, k] - x[j, k]) * (x[i, k] - x[j, k]);
                    }
                    l = Math.Sqrt(l);
                    if (l - (double)((int)l) < 1e-10)
                    {
                        cnt++;
                    }
                }
            }


            Console.WriteLine(cnt);
        }
    }
}

Measured memory_bytes: 13140
s = list(map(int, list(input())))
n=len(s)
ans=0

for i in range(n):
	for j in range(n-i-1):
		ans += (2**i) * (2**(n-i-j-2) * (10**j) * s[i])
	ans += (2**i)*(10**(n-i-1))*s[i]
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

int main() {
    string s;
    cin >> s;
    if(s == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;

    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod=1e9+7;
int a[1000001],n,ans,cnt;
signed main()
{
    cin>>n; 
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=60;i++){
        int cnt=0;
        for(int j=1;j<=n;j++){
            if(a[j]>>i&1) cnt++;
        }
        ans=(ans+(1LL<<i)%mod*cnt%mod*(n-cnt)%mod)%mod;
    }
    cout<<ans<<endl;
    return 0;
}


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

public class Main {

	public static void main(String[] args) throws Exception{
		// TODO ?????????????????????????????????????????????
		String str[], ans;
		int a, b;
		int d, r;
		String f;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine().split(" ");
        a = Integer.parseInt(str[0]);
        b = Integer.parseInt(str[1]);

        d = a / b;
        r = a % b;
        f = String.format("%.5f", ((double)a / (double)b));
        System.out.println(d + " " + r + " " + f);

	}

}

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

int main() {
    int k,s,l=0,c=0;
    cin>>k>>s;

    for (int i=0;i<=k;i++){
      for (int j=0 ;j<= k;j++){
      l=s-i ;
      l=l-j;
        if(0<= l && l <= k )
            c++;
      }
    }
  cout <<c<<"\n";
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <iomanip>
#include <queue>
#include <deque>
#include <sstream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <map>
#include <utility>
using namespace std;

#define s(n) scanf("%d",&n)
#define sc(n) scanf("%c",&n)
#define ss(n) scanf("%s",&n)
#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795

int facts[100005];
int factinvs[100005];

int gcdExtended(int a, int b, int *x, int *y) { //From http://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }

    int x1, y1; // To store results of recursive call
    int gcd = gcdExtended(b%a, a, &x1, &y1);

    // Update x and y using results of recursive
    // call
    *x = y1 - (b/a) * x1;
    *y = x1;

    return gcd;
}

int modinv(int a) {
	int x,y;
	gcdExtended(a, MOD,&x,&y);
	return (x%MOD+MOD)%MOD;
}

void genfacts() {
	ll num = 1;
	facts[0] = 1;
	factinvs[0] = 1;
	for(int i = 1; i <= 100003; i++) {
		num*= i;
		num = num%MOD;
		facts[i] = num;
		factinvs[i] = modinv(num);
	}
}

ll binom (int n, int k) {
	if(k > n) {
		return 0;
	}
	ll a = facts[n];
	ll b = factinvs[n-k];
	ll c = factinvs[k];
	return ((a*b)%MOD*c)%MOD;
}

int main() {
	int n;
	cin >> n;
	genfacts();
	vector<int> wasat (n+1,-1);
	int d = 0;
	for(int i = 0; i < n+1; i++) {
		int x;
		cin >> x;
		if(wasat[x] != -1) {
			d = i-wasat[x];
			break;
		} else {
			wasat[x] = i;
		}
	}
	for(int i = 1; i <= n+1; i++) {
		cout << (binom(n+1,i)-binom(n-d,i-1)+MOD)%MOD << "\n";
	}
	return 0;
}



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

const int N = 200010;
long long sum[N];
int a[N];

long long Abs(long long x) {
    if(x > 0) {
        return x;
    }
    return -x;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    long long ret = (long long) 1e18;
    for (int i = 1; i < n; i++) {
        if (Abs(sum[n] - sum[i] - sum[i]) < ret) {
            ret = Abs(sum[n] - sum[i] - sum[i]);
        }
    }
    printf("%lld\n", ret);
    return 0;
}


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

template<typename T, typename U>
using pv=vector<pair<T,U>>;
template<typename T>
using matrix=vector<vector<T>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using ilpair=pair<int,ll>;
using lipair=pair<ll,int>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;

#define PI 3.141592653589793
#define INTINF ((1<<30)-1)
#define LLINF 1LL<<60
#define MPRIME 1000000007
#define MPRIME9 998244353
#define MMPRIME (1ll<<61)-1

#define len length()
#define pushb push_back
#define fi first
#define se second

#define setpr fixed<<setprecision(15)
#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())

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 void init(T& v) {
	for(auto &a: v) cin>>a;
}
template<class T, class U>
inline void init(vector<pair<T,U>>& v) {
	for(auto &a: v) cin>>a.first>>a.second;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a;
}
template<class T, class U, class N>
inline void init(vector<pair<T,U>>& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a.first>>a.second;
}

inline void out() {
	cout<<endl;
}
template<class T, class... U>
inline void out(T a, U... alist) {
	cout<<a<<" ";
	out(forward<U>(alist)...);
}

template<class N>
void resiz(N n) {
	//empty
}
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

ll binpow(ll a, ll ex, ll p) {
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}


int N;
intvec A;
ll res;

void input() {
	cin>>N;
	init(A,N);
}

void solve() {
	sort(rall(A));
	res+=A[0];
	int r=N-2;
	for(int i=1; r>0; i++) {
		if(r==1) {
			res+=A[i];
			break;
		}
		res+=A[i]*2;
		r-=2;
	}
	cout<<res<<endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
	int t=1;
	while(t) {
		input();
		solve();
		t--;
	}
}


Measured memory_bytes: 3968
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)
 
 
void no() {
	puts("NO");
	exit(0);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	ll N;
	cin >> N;
	vector<ll>A(N);
	ll sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		sum += A[i];
	}
	if (sum % (N*(N + 1LL) / 2LL) != 0)no();
 
	ll k = sum / (N*(N + 1LL) / 2LL);
	vector<ll>x(N);
	for (int i = 0; i < N; i++) {
		ll s = A[i] - A[(i - 1 + N) % N];
		if (k - s < 0 || (k - s) % N != 0)no();
		x[i] = (k - s) / N;
	}
 
	for (int i = 0; i < N; i++) {
		A[0] -= x[N - 1 - i] * ((i+1)%N + 1);
	}
	
	puts("YES");
 
 
	return 0;
}

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

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

#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX / 100;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)

bool contain(set<char> &s, int a) { return s.find(a) != s.end(); }


//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);

typedef priority_queue<ll, vector<ll>, greater<ll>> PQ_ASK;
const int mod = 1000000007;

int main() {
    vector<string> week = {
            "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT",
    };
    string s;
    cin >> s;
    auto it = find(week.begin(), week.end(), s);
    cout << week.end() - it << endl;

}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <ccomplex>
#include <unordered_map>
#include <cstring>
#include <iostream>
#include <numeric>
#include <sstream>
#include <set>
#include <map>
#include <tuple>
#include <iomanip>

using namespace std;
#define MAX 1LL << 60
#define MOD 1000000007

typedef long long ll;

#define rep(i, s, e) for(ll i = s; i < e; i++)
#define repR(i, s, e) for(ll i = s; i > e; i--)
#define reft0(i, j) setfill('0') << setw(i) << j
#define fix(i) fixed << setprecision(i)
#define so(a) sort(begin(a), end(a))
#define soR(a) sort(begin(a), end(a), greater<ll>())
#define sum(a) accumulate(begin(a), end(a), 0)


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(){
    ll K, N;
    vector<ll> A;
    cin >> K >> N;
    rep(i, 0, N){
        ll temp;
        cin >> temp;
        A.push_back(temp);
    }
    vector<ll> diff;
    rep(i, 0, N - 1){
        diff.push_back(A[i + 1] - A[i]);
    }
    diff.push_back(A[0] + (K - A[N - 1]));

    ll ans = MAX;
    rep(i, 0, N){
        ll tempAns = K - diff[i];
        if (ans > tempAns){
            ans = tempAns;
        }
    }

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


Measured memory_bytes: 4848
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        var num = ToInt32(ReadLine());
        var ar = Array.ConvertAll(ReadLine().Split(' '), int.Parse);
        var res = 0L;
        var isEnd = false;
        while (!isEnd)
        {
            isEnd = true;
            for(var i = 0; i < num; i++)
            {
                if (i!=0&&ar[i] == 0 && ar[i - 1] != 0) res++;
                
            }
            if (ar[num-1] != 0) res++;
            for (var i = 0; i < num; i++)
                if (ar[i] != 0) { ar[i]--; isEnd = false; }
        }
        WriteLine(res);
    }
    private const string ALFA = "abcdefghijklmnopqrstuvwxyz";
    private const int MOD = 1000000007;
}


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

int main()
{
    ll h;
    cin >> h;

    ll answer = 0;
    ll monster_num = 1;
    while (h > 0)
    {
        answer += monster_num;
        monster_num *= 2;
        h = (ll)h / 2l;
    }

    if (h == 1)
    {
        answer += monster_num;
    }

    cout << answer << endl;
}

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

int main() {
	
	ll n; cin >> n;
	vector<ll> x(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		cin >> x[i];
	}
	vector<ll> x_sort;
	x_sort = x;
	sort(x_sort.begin(), x_sort.end());
	for (int i = 1; i <= n; i++) {
		if (x[i] <= x_sort[n / 2])	cout << x_sort[n / 2 + 1] << endl;
		else cout << x_sort[n / 2] << endl;
	}
	return 0;
}

Measured memory_bytes: 6320
<?php
fscanf(STDIN, "%d", $n); 
$step = trim(fgets(STDIN));
$rows = [];

while (($row = trim(fgets(STDIN))) !== '') {
  $rows[] = explode(' ', $row);
}
for ($i =0 ; $i < $n*4 ; $i++) {
if ( $step[$i] == "Y" ){
$ans = "Four";
  break;
}
else{ $ans ="Three";
}
}
echo $ans;  


Measured memory_bytes: 3828
def count_legs():
    X, Y = map(int, input().split())
    for i in range(X):
        if i * 2 + (X-i) * 4 == Y or (X-i) * 2 + i * 4 == Y:
            print('Yes')
            return True
    print('No')

if __name__ == "__main__":
    count_legs()


Measured memory_bytes: 9168
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n, k;
	scanf("%d %d", &n, &k);
	long long ansZeros = 1ll;
	int zeros = 0;
	for(int i = 1; i <= n; i++) if(i % k == 0) zeros++;
	ansZeros = 1ll * zeros * zeros * zeros;
	long long ansHalf = 0ll;
	int halves = 0;
	if(k % 2 == 0){
		for(int i = 1; i <= n; i++){
			if(i % k == (k / 2)) halves++;
		}
		ansHalf = 1ll * halves * halves * halves;
	}
	long long ans = ansZeros + ansHalf;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 256
n=int(input())
s_list=[]

for i in range(n):
    s_list.append(input())
    

c_0=s_list.count("AC")
c_1=s_list.count("WA")
c_2=s_list.count("TLE")
c_3=s_list.count("RE")

print("AC x",c_0)
print("WA x",c_1)
print("TLE x",c_2)
print("RE x",c_3)



Measured memory_bytes: 16212
N = int(input())
S = input()
alpha = [chr(i) for i in range(65,65+26)]
text = []
ans = []
for i in list(S):
    text.append(alpha.index(i))
for i in range(len(S)):
    text[i] = (text[i] + N) % 26
for i in range(len(S)):
    ans.append(alpha[text[i]])
print("".join(map(str,ans)))

Measured memory_bytes: 3316
#include <cstdio>
int main() {
	char s[105];
  int n;
  scanf("%d", &n);
  scanf("%s", s + 1);
  int cnt = 0;
  for (int i = 1; i <= n; ++i) if (s[i] == 'R') ++cnt;
  if (cnt > n - cnt) puts("Yes");
  else puts("No");
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main{
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int a = scan.nextInt();
    int b = scan.nextInt();
    if(a>b){
      System.out.println("a > b");
    }
    else if(a<b){
      System.out.println("a < b");
    } else {System.out.println("a == b");}
  }
}

Measured memory_bytes: 26064
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    int sum = 0;
    for(int i = 1; i < n; i++){
        sum += a[i];
    }
    sum -= a[0];
    for(int i = 2; i < n - 1; i += 2){
        sum -= a[i] * 2;
    }

    vector<int> ans(n);
    ans[n-1] = sum;

    rep(i, n - 1){
        int x = (n - 1 + i) % n;
        ans[(x+1)%n] = (a[x] - ans[x] / 2) * 2;
    }

    rep(i, n){
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h> 
 
#define INF (1<<31)//INT_MAX/2
#define MOD 1000000007
 
using ll  = long long;
using ull = unsigned long long;
 
int main(int argc, char *argv[])
{
    std::string s0, s1, s2;
    std::cin >> s0 >> s1 >> s2;

    std::cout << s0[0] << s1[0] << s2[0] << std::endl;
    return 0;
}

Measured memory_bytes: 256
import sys,bisect

from sys  import stdin,stdout

from bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right

from math import gcd,ceil,floor,sqrt

from collections import Counter,defaultdict,deque,OrderedDict

dx=[-1,1,0,0]
dy=[0,0,1,-1]


sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 998244353
mod = 10**9+7

def isPrime(n):
    if (n <= 1) :return False
    if (n <= 3) :return True
    if (n%2 == 0 or n%3 == 0):return False
    for i in range(5,ceil(sqrt(n))+1,6):
        if (n%i==0 or n%(i+2)==0):
            return False
    return True

def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int,stdin.readline().split()))

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")


def soe(limit):
    l=[1]*(limit+1)
    l[0]=0
    l[1]=0
    prime=[]
    for i in range(2,limit+1):
        if l[i]:
            for j in range(i*i,limit+1,i):
                l[j]=0
    
    for i in range(2,limit+1):
        if l[i]:
            prime.append(i)
    return prime

                
def gcd(a,b):
    while b:
        a=a%b
        b,a=a,b
    return a

def power(a,n):
    r=1
    while n:
        if n&1:
            r=(r*a)
        a*=a
        n=n>>1
    return r
    
def solve():
    d,t,s=mp()
    if s*t>=d:
        print('Yes')
    else:
        print('No')



for _ in range(1):
    solve()



Measured memory_bytes: 9496
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <string>
#include <queue>

typedef long long ll;
using namespace std;
const int mod = 1000000007;

static const int MAX = 5e+5 + 1;

int main() {

    vector<int> L(MAX, 0), R(MAX, 0);

    string S; cin >> S;
    int length = S.size();

    int cnt_l = 0, cnt_r = 0;
    for (int i = 0; i < length; i++) {
        int j = length - i - 1;
        if (S[i] == '<') L[i] = cnt_l++;
        else {
            L[i] = cnt_l;
            cnt_l = 0;
        }
        if (S[j] == '>') R[j+1] = cnt_r++;
        else {
            R[j+1] = cnt_r;
            cnt_r = 0;
        }
    } 
    // cout << cnt_r << ' ' << cnt_l << '\n';
    R[0] = cnt_r;
    L[length] = cnt_l;

    /*
    for (int i = 0; i < S.size() + 1; i++) {
        cout << R[i] << ' ';
    } cout << '\n';
    for (int i = 0; i < S.size() + 1; i++) {
        cout << L[i] << ' ';
    } cout << '\n';
    */
    ll ans = 0;
    for (int i = 0; i < S.size() + 1; i++) {
        ans += max(L[i], R[i]);
    }
    cout << ans << '\n';


}


Measured memory_bytes: 4740
#include<iostream>
using namespace std;
int main(){
  int r,g,b,n,num,cnt=0;
  cin >> r >> g >> b >> n;
  for(int i=0;i*r<=n;i++){
    for(int j=0;j*g+i*r<=n;j++){
      num =n-(i*r+g*j);
      if(num%b==0){
        cnt++;
      }
    }
  }
  cout << cnt << endl;
}


Measured memory_bytes: 256
import bisect, collections, copy, heapq, itertools, math, numpy, string
import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def MS(): return map(str, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
# N = I()
# A = [LI() for _ in range(N)]

a, v= MI()
b,w = MI()
t =I()
if abs(a-b) <= (v-w) * t:
    print('YES')
else:
    print('NO')

Measured memory_bytes: 27220
#include<stdio.h>

int n,A[50];

int solve (int i, int m){
 if(m==0)return 1;
 if(i>=n)return 0;
 int res =solve(i+1,m)||solve(i+1,m-A[i]);
return res;
}

int main(){
 int q,M,i;
 scanf("%d",&n);
 for(i=0;i<n;i++)scanf("%d",&A[i]);
 scanf("%d", &q);
 for(i=0;i<q;i++){
 scanf("%d",&M);
 if(solve(0,M))printf("yes\n");
 else printf("no\n");
 }
 
return 0;
 }

Measured memory_bytes: 2680
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

//  RMQ
template<class T>
class RMQ
{
    int n;
    vector<T> A;

    T q(int l, int r)
    {
        T a = min(A[l], A[r-1]);
        if ((l+1)/2 < r/2)
            a = min(a, q((l+1)/2, r/2));
        return a;
    }

public:
    RMQ(int n_)
    {
        n = 1;
        while (n < n_)
            n *= 2;
        A = vector<T>(2*n, numeric_limits<T>::max());
    }

    void set(int i, T v)
    {
        A[i+n] = v;
        for (int p=(i+n)/2; p>0; p/=2)
            A[p] = min(A[2*p], A[2*p+1]);
    }

    T query(int l, int r)
    {
        return q(l+n, r+n);
    }
};

int main()
{
    int N, E, T;
    cin>>N>>E>>T;
    vector<long long> x(N);
    for (long  long &t: x)
        cin>>t;

    vector<long long> A(N);
    A[0] = x[0]+T;

    RMQ<long long> Q1(N);   //  A[j-1]-x[j-1]-2*x[j]
    RMQ<long long> Q2(N);   //  A[j-1]-x[j-1]
 
    for (int i=1; i<N; i++)
    {
        A[i] = A[i-1]+(x[i]-x[i-1])+T;
        A[i] = min(A[i], 0LL+x[i]+(x[i]-x[0])*2+max(0LL, T-(x[i]-x[0])*2));

        int l = 0;
        int r = i;
        while (l+1<r)
        {
            int m = (l+r)/2;
            if ((x[i]-x[m])*2 > T)
                l = m;
            else
                r = m;
        }

        if (1<r)
            A[i] = min(A[i], 3*x[i] + Q1.query(1, r));
        if (r<i)
            A[i] = min(A[i], T+x[i] + Q2.query(r, i));

        Q1.set(i, A[i-1]-x[i-1]-2*x[i]);
        Q2.set(i, A[i-1]-x[i-1]);
    }
 
    cout<<A[N-1]+E-x[N-1]<<endl;
}


Measured memory_bytes: 5888
#include<iostream>
#include<cmath>
using namespace std;
typedef long long int ll;
int main()
{
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll x=a*c;
	ll y=a*d;
	ll i=b*c;
	ll j=b*d;
	ll p=max(i,j);
	ll q=max(x,y);
	cout<<max(p,q);
}

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

int main(){
    int N, A = 0;
    string S;
    cin >> N >> S;
    for(int i = 0; i < (N - 2); i++){
        if(S.at(i) == 'A' && S.at(i + 1) == 'B' && S.at(i + 2) == 'C'){
            A = A + 1;
        }
    }
    cout << A << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int l[N][N],r[N][N],n,m,ans=-1;
char c[N][N];
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>c[i];
	for(int i=0;i<n;i++)
	{
		int ji=0,last=0;
		for(int j=0;j<m;j++)
		{
			if(c[i][j]=='#')
			{
				for(int k=last;k<j;k++)l[i][k]=ji;
				ji=0;
				last=j+1;
			}
			else
				ji++;
		}
		for(int k=last;k<m;k++)l[i][k]=ji;
	}
	for(int j=0;j<m;j++)
	{
		int ji=0,last=0;
		for(int i=0;i<n;i++)
		{
			if(c[i][j]=='#')
			{
				for(int k=last;k<i;k++)r[k][j]=ji;
				ji=0;
				last=i+1;
			}
			else
				ji++;
		}
		for(int k=last;k<n;k++)r[k][j]=ji;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			if(c[i][j]=='.')
				ans=max(ans,l[i][j]+r[i][j]-1);
	cout<<ans<<endl;
	return 0;
}
/*
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#
*/


Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64

signed main() {
  int a,b;cin>>a>>b;
  int ans = 0;
  ans += max(a,b);
  if(a>b) --a;
  else --b;

  cout<<ans+max(a,b)<<endl;
  
    
}

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

using namespace std;

const int MOD=1'000'000'007;

int main(){
    long N;
    cin>>N;
    vector<long> A(N);
    for(int i=0; i<N; ++i){
        cin>>A[i];
    }

    vector<long> count(62, 0);
    for(int i=0; i<=61; ++i){
        for(int j=0; j<N; ++j){
            // cout<<A[i]<<" "<<(A[i]>>i)
            if((A[j]>>i) & long(1)){
                count[i]++;
            }
        }
    }

    long ans = 0;
    for(int i=0; i<=61; ++i){
        // cout<<count[i]<<endl;
        ans += ((((N-count[i]) * count[i]) % MOD) * ((long(1)<<i) % MOD)) % MOD;
        ans %= MOD;
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 2560
n=int(input())
s=input()
li=s.split(" ")
for i in range(len(li)):
    li[i]=int(li[i])
li.sort()
ans=(li[0]+li[1])/2
if len(li)>2:
    for i in range(2,len(li)):
        ans=(ans+li[i])/2
print(ans)

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

using namespace std;

int n, h[100005], dp[100005], k;

int main(){
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> h[i];
	}
	dp[1] = 0;
	for(int i = 2; i <= n; i++){
		dp[i] = abs(h[i] - h[i - 1]) + dp[i - 1];
		for(int j = 1; j <= k; j++){
			if(i - j != 0) dp[i] = min(dp[i - j] + abs(h[i] - h[i - j]), dp[i]);
			else break;
		}
	}
/*	for(int i = 1; i <= n; i++){
		cout << dp[i] << " ";
	}                         */
	cout << dp[n];
}

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

template<class Iterator>
int LIS(Iterator l, Iterator r){
	auto x = *l;
	pair<int, decltype(x)> p1x(1, x);
	vector<pair<int, decltype(x)>> dp(r - l, p1x);
	for(Iterator i = l; i < r; i++){
		pair<int, decltype(x)> val(0, *i);
		//lower_boundなら狭義, upper_boundなら広義の単調増加
		*upper_bound(dp.begin(), dp.end(), val) = val;
	}
	return lower_bound(dp.begin(), dp.end(), p1x) - dp.begin();
}

template<class Iterator, class Compare>
int LIS(Iterator l, Iterator r, Compare comp){
	auto x = *l;
	pair<int, decltype(x)> p1x(1, x);
	vector<pair<int, decltype(x)>> dp(r - l, p1x);
	const auto compair = [&](pair<int, decltype(x)> a, pair<int, decltype(x)> b){
		return a.first != b.first ? a.first < b.first : comp(a.second, b.second);
	};
	for(Iterator i = l; i < r; i++){
		pair<int, decltype(x)> val(0, *i);
		//lower_boundなら狭義, upper_boundなら広義の単調増加
		*lower_bound(dp.begin(), dp.end(), val, compair) = val;
	}
	return lower_bound(dp.begin(), dp.end(), p1x, compair) - dp.begin();
}

int main(){
	int N, i;
	scanf("%d", &N);
	vector<int> A(N);
	for(i = 0; i < N; i++){
		scanf("%d", &A[i]);
		A[i] = -A[i];
	}
	printf("%d\n", LIS(A.begin(), A.end()));
	return 0;
}

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

int main() {
    lint mod = 1e+9 + 7;
    lint n;
    cin >> n;
    vector<lint> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<lint> bit(60, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 60; j++) {
            if (a[i] & (1LL << j)) {
                bit[j]++;
            }
        }
    }
    lint ans = 0;
    int pow = 1;
    for (int i = 0; i < 60; i++) {
        lint comb = bit[i] * (n - bit[i]);
        comb %= mod;
        ans += comb * pow;
        ans %= mod;
        pow = (pow * 2) % mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int n,a[2005];
ll k;
ll ans;
int main() {
    scanf("%d%lld",&n,&k);
    for(int i = 1;i<=n;i++) {
        scanf("%d",&a[i]);
    } 
    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=n;j++) {
            if(i==j) continue;
            if(a[i] > a[j]) {
                if(j > i) ans = (ans + k*(k+1)/2%mod) % mod;
                else ans = (ans + k*(k-1)/2%mod) % mod;
            }
        }
    }
    printf("%lld\n",ans);
}  

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define R(x) (x)=read()
const int N = 100005;
char c[N];
int a[N],b[N];
int n,m,T;
using namespace std;
int gcd(int x,int y) {
	if(x%y==0) return y;
	else return gcd(y,x%y);
}
int read() {
	int x=0;char c=getchar();
	while((c<48||c>57)&&c!='-') c=getchar();
	if(c=='-') {c=getchar();while(c>=48&&c<=57) x=x*10-c+48,c=getchar();}
	while(c>=48&&c<=57) x=x*10+c-48,c=getchar();
	return x;
}
void init() {
	
}
int s[405][405],R,r[405],tmp[405],pd[405];
int ans=1e9;
void dfs(int now,int lim) {
	if(now==lim+1) {
		int sum=0;
		for(int i=2;i<=lim;i++)
			sum+=s[tmp[i]][tmp[i-1]];

		ans=min(ans,sum);	
		return ;
	}
	for(int i=1;i<=lim;i++) {
		if(!pd[i]) {pd[i]=1,tmp[now]=r[i];
		dfs(now+1,lim);
		pd[i]=0;
		}
	}
}
void solve() {
	memset(s,127/3,sizeof(s));
	cin>>n>>m>>R;
	for(int i=1;i<=R;i++)
		cin>>r[i];
	for(int a,b,c,i=1;i<=m;i++)
		R(a),R(b),R(c),s[a][b]=c,s[b][a]=c;
	for(int i=1;i<=n;i++)
		s[i][i]=0;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(s[i][j]>s[i][k]+s[k][j])
					s[i][j]=s[i][k]+s[k][j];
	dfs(1,R);
	cout<<ans;
	
}
int main() {
	init();
	solve();
	return 0;
}

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

// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
using namespace std;


typedef long long int ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;

#define St first
#define Nd second
#define Pb push_back
#define Mp make_pair
#define print_pair(p) cout<<p.St<<" "<<p.Nd
#define endl "\n"

#define REP(i,a,b) for(int i = a; i <= b; i++)
#define REV(i,a,b) for(int i = a; i >= b; i--)

#define AritSum(a,d,n) ((n)*(2*(a)+((n)-1)*(d)))/2
#define Log(base, num) log2(num)/log2(base)


// ************* MAIN *******************

ll N, A[100001],suffix[1000005], Max[1000001];
ll solve() {
    cin >>N;
    REP(i,0,N) cin>>A[i];
    suffix[N+1]=0;
    REV(i,N,0) suffix[i] = suffix[i+1] + A[i];
    // REP(i,0,N) {
    //     if (i > 27) Max[i] = INT_MAX;
    //     else Max[i] = min((1<<i), INT_MAX);
    // }
    if (A[0] > 0) {
        if (N==0 && A[0]==1) return 1;
        if (N==0 && A[0] > 1) return -1;
        if (N>0) return -1;
    }
    ll avai = 1, ans = 1;
    REP(i,1,N) { 
        if (A[i] > avai*2) return -1;
        ll desi = min(suffix[i], avai*2);
        ans+=desi;
        avai = desi - A[i];
    }
    return ans;
}
/*
g++ -std=c++14 -Wall -Wextra -O2 Test.cpp -o Test
*/
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    // cin>>T;
    for (int t = 1; t <= T; t++) {
        // cout << "Case #" << t << ": ";
        // solve();
        cout << solve() << endl;
    }
    return 0;
}


Measured memory_bytes: 5220