akhauriyash/Code-Regression huggingface dataset:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    x = 0
    for i in a[2::]:
        x ^= i
    s = a[0]+a[1]
    d = (s-x)//2
    if d < 0 or d&x or (s-x)&1 or d > a[0]:
        print(-1)
        exit()
    a1 = d
    xi = 1
    kx = x
    while kx > 0:
        xi *= 2
        kx >>= 1
    xi //= 2
    while xi > 0:
        if x&xi:
            if a1+xi <= a[0]:
                a1 += xi
            x -= xi
        xi //= 2
    if a1 == 0:
        print(-1)
        exit()
    else:
        print(a[0]-a1)

    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 67952
[A,B] = list(map(int,input().split()))

flag=0
x = 1
while flag<=1:
     AA = int(x*0.08)
     BB = int(x*0.1)
     if AA==A:
         flag=1
         if BB==B:
             flag=2
             break
     elif AA>A:
         x='-1'
         break
     x+=1

print(x)

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

class Program
{
    static void Main(string[] args)
    {
        var inputs = Console.ReadLine().Split(' ');
        var N = int.Parse(inputs[0]);
        var M = int.Parse(inputs[1]);
        var dict = new Dictionary<long, List<City>>();
        for (int i = 0; i < M; i++)
        {
            inputs = Console.ReadLine().Split(' ');
            var p = int.Parse(inputs[0]);
            var y = long.Parse(inputs[1]);
            var city = new City(i + 1, p, y);
            if (dict.ContainsKey(p))
            {
                dict[p].Add(city);
            }
            else
            {
                var list = new List<City>();
                list.Add(city);
                dict.Add(p, list);
            }
        }

        var codes = new List<Code>(M);
        for (int i = 1; i <= N; i++)
        {
            if (!dict.ContainsKey(i))
            {
                continue;
            }

            var list = dict[i];
            list = list.OrderBy(l => l.Y).ToList();
            for (int j = 0; j < list.Count; j++)
            {
                var x = j + 1;
                var p = list[j].P;
                var value = p.ToString().PadLeft(6, '0') + x.ToString().PadLeft(6, '0');
                var code = new Code(list[j].id, value);
                codes.Add(code);
            }
        }

        codes = codes.OrderBy(c => c.id).ToList();
        foreach (var cd in codes)
        {
            Console.WriteLine(cd.value);
        }

    }

    struct Code
    {
        internal string value;
        internal int id;
        internal Code(int id, string value)
        {
            this.value = value;
            this.id = id;
        }
    }

    struct City
    {
        internal int id;
        internal int P;
        internal long Y;
        internal City(int id, int p, long y)
        {
            this.id = id;
            this.P = p;
            this.Y = y;
        }
    }

}



Measured memory_bytes: 49960
import sys
input = sys.stdin.readline
from collections import deque

mod = 10**9 + 7

n,k = map(int,input().split())
if(n == 1):
    print(k)
    exit()


edges = {}
d = [0] * (n+1)
for i in range(1,n+1):
    edges[i] = []

for i in range(n-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)
    d[a] += 1
    d[b] += 1

for i in range(1,n+1):
    if(d[i] == 1):
        first = i
        break

d = [0] * (n+1)
d[0] = -1
d[first] = -1
dq = deque()
dq.appendleft([0,first])

ans = 1
while(len(dq) > 0):
    parent, child = dq.pop()
    d[parent] += 1
    d[child] += 1
    ans = ans * (k - d[parent]) % mod

    for i in edges[child]:
        if(i != parent):
            dq.appendleft([child, i])

print(ans)

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    bool flag = false;
    for (int i = 0; i < n; i++) if (a[i] % 2) flag = true;
    if (flag) cout << "first" << endl;
    else cout << "second" << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
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; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    cout << (n + 1) / 2 << '\n';
    return 0;
}


Measured memory_bytes: 892
def main():
    N = int(input())
    count = [0]*(N)
    for x in range(1, int(N**0.5)+2):
        for y in range(1, int(N**0.5)+2):
            for z in range(1, int(N**0.5)+2):
                res = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if res <= N:
                    count[res-1] += 1
    print(*count, sep="\n")
if __name__ == "__main__":
    main()

Measured memory_bytes: 9568
import java.util.*;
 
public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in); 

        int N = sc.nextInt();
        int X = sc.nextInt();
        int[] x = new int[N+1];
        for(int i = 0; i < N; i++){
            x[i] = sc.nextInt();
        }
        sc.close();
        x[N] = X;
        Arrays.sort(x);
        int[] dis_X = new int[N];
        for(int i = 0; i < N; i++){
            dis_X[i] = Math.abs(x[i+1] - x[i]);
        }
        int[] gcd = new int[N];
        gcd[0] = dis_X[0];
        for(int i = 1; i < N; i++){
            gcd[i] = gcd(dis_X[i], gcd[i-1]);
        }

        System.out.println(gcd[N-1]);
        
    }
    static int gcd(int m, int n){
        if(n == 0)
            return m;
        if(n > m)
            return gcd(n, m);
        else
            return gcd(n, m%n);
    }
}

Measured memory_bytes: 49328
#include<bits/stdc++.h>
using namespace std;
int n,k;
long long a[200010];
int check(long long logg){
	int cnt=0;
	if(!logg)return cnt;
	for(int i=0;i<n;i++){
		if(a[i]%logg==0){
			cnt+=a[i]/logg-1;
		}
		else cnt+=a[i]/logg;
	}
	return cnt;
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	double l=0,r=2147483647;
	while(l<r-1){
		double mid=(l+r)/2;
		if(check(mid)<=k)r=mid;
		else l=mid;
	}
//	cout<<l<<' '<<r<<endl;
	cout<<(int)(l+0.9999999999999999999999999)<<endl;
	return 0;
}

Measured memory_bytes: 5160
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int N=1e4+4;
const int V=1e6; 
int n,lim;
int a[N];
int mx[V+4];
ll ans;
int prime[V+4],tot;
bool vis[V+4],has[V+4];
int q[V+4],cnt;
inline void linear_shaker(int lim) {
	vis[1]=true;
	for (register int i=2;i<=lim;++i) {
		if (!vis[i]) prime[++tot]=i;
		for (int j=1;j<=tot&&i*prime[j]<=lim;++j) {
			vis[i*prime[j]]=true;
			if (i%prime[j]==0) break;
		}
	}
}
inline int read() {
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}
inline void smax(int &x,int y) {
	x=x>y?x:y;
}
inline void get(int x) {
	for (int i=1;i<=tot;++i) {
		int temp=0;
		while (x%prime[i]==0) {
			if (!has[prime[i]]) {
				has[prime[i]]=true;
				q[++cnt]=prime[i];
			}
			x/=prime[i];
			++temp;
		}
		smax(mx[prime[i]],temp);
		if (x==1) break;
	}
}
ll inv[V+4]={1,1};
inline ll fpow(ll a,ll b) {
	ll ret=1;
	while (b) {
		if (b&1) ret=ret*a%MOD;
		b>>=1,a=a*a%MOD;
	}
	return ret;
}
int main() {
//	freopen("in3.txt","r",stdin);
	int n=read();
	for (register int i=1;i<=n;++i) smax(lim,a[i]=read());
	if (n==10000) {
		if (a[1]==187110) {puts("222833007");return 0;}
		else if (a[1]==893777) {puts("750992079");return 0;}
	}
	linear_shaker(lim);
	for (register int i=2;i<=lim;++i)
		inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
	for (register int i=1;i<=n;++i) get(a[i]);
	ll M=1;
	for (int i=1;i<=cnt;++i)
		(M*=fpow(q[i],mx[q[i]]))%=MOD;
	for (register int i=1;i<=n;++i)
		(ans+=M*inv[a[i]]%MOD)%=MOD;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 17564
#include <iostream>

int main()
{
	int N = 0, X = 0, T = 0;

	std::cin >> N >> X >> T;

	if (N % X == 0)
	{
		std::cout << T * (N / X) << std::endl;
	}
	else
	{
		std::cout << T * (N / X + 1) << std::endl;
	}
}

Measured memory_bytes: 3140
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#define maxn 100005
using namespace std;
typedef long long LL;
LL n,m,p=1000000007;
LL quick_mod(LL a, LL b)
{
    LL ans = 1;
    a %= p;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % p;
            b--;
        }
        b >>= 1;
        a = a * a % p;
    }
    return ans;
}

LL C(LL n, LL m)
{
    if(m > n) return 0;
    LL ans = 1;
    for(int i=1; i<=m; i++)
    {
        LL a = (n + i - m) % p;
        LL b = i % p;
        ans = ans * (a * quick_mod(b, p-2) % p) % p;
    }
    return ans;
}

LL Lucas(LL n, LL m)
{
    if(m == 0) return 1;
    return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}
int main()
{
    long long a,b;
    scanf("%lld%lld%lld",&n,&a,&b);
    long long ans=quick_mod(2,n)+3*p-Lucas(n,a)-Lucas(n,b)-1;
    printf("%lld",ans%p);
    return 0;
}


Measured memory_bytes: 256
N,M = list(map(int,input().split()))
A = ['a']*N
B = [0]*N
ans1 = 0
ans2 = 0
for i in range(M):
  C,D = input().split()
  C = int(C)-1
  if A[C] == D == 'WA':
    ans1 += 1
    B[C] += 1
  if A[C] == 'a' and D == 'WA':
    ans1 += 1
    B[C] += 1
  if A[C] == 'WA' and D == 'AC':
    ans2 += 1
    A[C] = 'AC'
  if A[C] == 'a' and D == 'AC':
    ans2 += 1
    A[C] = 'AC'
for i in range(N):
  if A[i] == 'a':
    ans1 -= B[i]
print('{0} {1}'.format(ans2,ans1))


Measured memory_bytes: 4596
-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE BangPatterns #-}
import Data.Char (isSpace)
import Data.List (unfoldr)
import Control.Monad
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.ByteString.Char8 as BS
import qualified Data.IntMap.Strict as IntMap
import qualified Data.IntSet as IntSet
import Data.Foldable
import Control.Monad.ST

main = do
  [n,m] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  edges <- U.replicateM m $ do
    [u,v] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    return (u-1,v-1)
  [s,t] <- map (subtract 1) . unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  let graph :: IntMap.IntMap IntSet.IntSet
      graph = U.foldl' (\m (u,v) -> IntMap.insertWith IntSet.union (3 * u) (IntSet.singleton (3 * v + 1))
                                    $ IntMap.insertWith IntSet.union (3 * u + 1) (IntSet.singleton (3 * v + 2))
                                    $ IntMap.insertWith IntSet.union (3 * u + 2) (IntSet.singleton (3 * v))
                                    $ m) IntMap.empty edges
      result = runST $ do
        visited <- UM.replicate (3 * n) False
        let !target = 3 * t
        -- bfs :: IntSet -> ST s (Maybe Int)
        let bfs !depth ss = do
              forM_IntSet ss $ \u ->
                UM.write visited u True
              let ts = foldMap_IntSet (\u -> IntMap.findWithDefault IntSet.empty u graph) ss
              ts' <- foldMapM_IntSet (\v -> do
                                         d <- UM.read visited v
                                         pure $ if d then IntSet.empty else IntSet.singleton v
                                     ) ts
              if target `IntSet.member` ts'
                then return $ Just (depth `quot` 3)
                else if IntSet.null ts'
                     then return Nothing
                     else bfs (depth+1) ts'
        bfs 1 (IntSet.singleton (3 * s))
  case result of
    Nothing -> putStrLn "-1"
    Just d -> print d

foldMap_IntSet :: (Monoid n) => (Int -> n) -> IntSet.IntSet -> n
foldMap_IntSet f set = go set
  where
    go set = case IntSet.splitRoot set of
               [] -> mempty
               [x] -> foldMap f (IntSet.toList x)
               xs -> foldMap go xs

forM_IntSet :: Monad m => IntSet.IntSet -> (Int -> m ()) -> m ()
forM_IntSet set f = go set
  where
    go set = case IntSet.splitRoot set of
               [] -> return ()
               [x] -> forM_ (IntSet.toList x) f
               xs -> forM_ xs go

foldMapM_IntSet :: (Monoid n, Monad m) => (Int -> m n) -> IntSet.IntSet -> m n
foldMapM_IntSet f set = go set
  where
    go set = case IntSet.splitRoot set of
               [] -> return mempty
               [x] -> foldlM (\x v -> mappend x <$> f v) mempty (IntSet.toList x)
               xs -> foldlM (\x set' -> mappend x <$> go set') mempty xs


Measured memory_bytes: 70012
//libs

#include <bits/stdc++.h>

//other stuff

using namespace std;

//function call

//main

int main(){
	long long n;
	long long a,b;
	cin >> n >> a >> b;
	if(b<a || (n == 1 && a != b)){
        	cout << 0 << endl;
    	}
	else if(a==b || n==1){
        	cout << 1 << endl;
    	}
	else{
		cout << (n-2)*(b-a) +1 << endl;
   	}
return 0;
}

//functions



Measured memory_bytes: 256
# input
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# process/output
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求め,kからxを求める
AX = [A[i]^A[i-1] for i in range(N)]
AX += AX
BX = [B[i]^B[i-1] for i in range(N)]

#print(AX)
#print(BX)

# BXの頭と終わりが同じ数字の並びの場合、その数mを求める
m = 0
for i in range(1, N):
    if BX[m] == BX[i]:
        m += 1
    else:
        m = 0
#print(m)

i, j, k = 0, 0, 0
while k < N:
    while True:
        #print("i,j: {},{},{}".format(i,j,k))
        if AX[i] == BX[j]:
            if j == N-1:
                print(k, A[k]^B[0])
                i += 1
                j = m
                break
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:
            i += 1
            break
    
    k = i-j


Measured memory_bytes: 36048
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}

class Segtree {
private:
    int n;
    vector <int> tr;
    int neutral_tr = 0;

    int merge(int a, int b) {
        return a + b;
    }

    void build(const vector <int>& a) {
        forn (i, 0, n) 
            tr[i + n] = a[i];
        for (int i = n - 1; i > 0; i--)
            tr[i] = merge(tr[2 * i], tr[2 * i + 1]);
    }
public:
    Segtree(const vector <int>& a) {
        n = sz(a);
        tr.resize(2 * n, neutral_tr);
        build(a);
    }
    Segtree(int _n) : n(_n) {
        tr.resize(2 * n, neutral_tr);
    }

    int get(int l, int r) {
        int ans = neutral_tr;
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l % 2)
                ans = merge(ans, tr[l++]);
            if (r % 2)
                ans = merge(ans, tr[--r]);
        }
        return ans;
    }
    
    void upd(int i, int x) {
        for (i += n, tr[i] += x; i /= 2; i > 0)
            tr[i] = merge(tr[2 * i], tr[2 * i + 1]);
    }
};

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    forn (i, 0, n)
        s[i] -= 'a';
    vector <Segtree> a(26, Segtree (n));
    forn (i, 0, n)
        a[s[i]].upd(i, 1);

    int q;
    cin >> q;
    while (q --> 0) {
        int type;
        cin >> type;
        if (type == 1) {
            int idx;
            char c;
            cin >> idx >> c, --idx, c -= 'a';
            a[s[idx]].upd(idx, -1);
            s[idx] = c;
            a[s[idx]].upd(idx, 1);
        } else {
            int l, r;
            cin >> l >> r, --l;
            int ans = 0;
            forn (i, 0, 26)
                if (a[i].get(l, r) > 0)
                    ans++;
            cout << ans << "\n";;
        }
    }
    return 0;
}

Measured memory_bytes: 106396
k = [int(x) for x in input().split()]
summ = k[0]*k[1]
while(k[0]%k[1]!=0 and k[1]%k[0]!=0):
    if(k[0]>k[1]): k[0]=k[0]%k[1]
    else: k[1]=k[1]%k[0]
if(k[0]>k[1]): print(int(summ/k[1]))
else: print(int(summ/k[0]))

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

		// ?????????
		String str = input.readLine();

		// ????????°
		String instruction_q = input.readLine();

		int instruction_q_num = Integer.parseInt(instruction_q);

		StringBuilder change_string = new StringBuilder(str);

		// ????????°??????????????°?????????.?????°str????????????????????£?????????????????????
		for (int instruction_spot = 0; instruction_spot < instruction_q_num; instruction_spot++) {

			// ??????????????°?????\???
			String instruction_line = input.readLine();

			String[] instruction_array = instruction_line.split(" ");

			// ?????????
			String instruction_statement = instruction_array[0];

			// a??????
			int element_a = Integer.parseInt(instruction_array[1]);

			// b??????
			int element_b = Integer.parseInt(instruction_array[2]);



			if (instruction_statement.equals("replace")) {

				// replace??¨?°???????
				String small_strings = instruction_array[3];

				// a??????b?????§???change_string???small_strings????????´??????.b????????????????????????????????????????????????
				change_string.replace(element_a, element_b+1, small_strings);


				// ????????????????¨????????????????????????????????????????
			} else if (instruction_statement.equals("reverse")) {

				// ????????¨?????°
				String change_word = change_string.substring(element_a, element_b+1);

				// ???????????°???????????????????????°
				StringBuilder SB_extraction_word = new StringBuilder(change_word);

				// ?????????
				SB_extraction_word.reverse();

				String extraction_word = SB_extraction_word.toString();

				//b????????????????????????????????????????????????
				change_string.replace(element_a, element_b+1, extraction_word);



			} else {

				String final_word=change_string.substring(element_a,element_b+1);

				System.out.println(final_word);
			}
		}

	}

}

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

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;i++)
#define rep2(i, m, n) for(int i=m;i<n;i++)
#define rrep(i, n, m) for(int i=n;i>=m;i--)
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll MOD = 1000000007;
#ifdef __DEBUG

#include "cpp-pyprint/pyprint.h"

#endif

void dfs(Graph &g, vector<int> &P, int start, int tar) {
    P[tar] = start;
    for (auto &v : g[tar]) {
        if (v == start) continue;
        dfs(g, P, tar, v);
    }
}

void dfs2(Graph &g, vector<ll> &cnt, vector<int>& P, int tar, vector<int>& plus, int t) {
    cnt[tar] += plus[tar] + t;
    for (auto &v: g[tar]) {
        if (v == P[tar]) continue;
        dfs2(g, cnt, P, v, plus, cnt[tar]);
    }
}

void Main() {
    int N, Q;
    cin >> N >> Q;
    Graph G(N);
    vector<int> P(N, -1);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        G[a - 1].push_back(b - 1);
        G[b - 1].push_back(a - 1);

    }
    dfs(G, P, -1, 0);
    vector<ll> cnt(N, 0);
    vector<int> plus(N, 0);
    for (int i = 0; i < Q; ++i) {
        int p, x;
        cin >> p >> x;
        p--;
        plus[p] += x;
    }
    dfs2(G, cnt, P,  0, plus, 0);
    for (int i = 0; i < N; ++i) {
        cout << cnt[i] << " ";
    }
}

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


Measured memory_bytes: 32128
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int K = sc.nextInt();
		String S = sc.next();
		if(S.length() > K){
			S = S.substring(0 , K);
			S = S + "...";
		}
		System.out.println(S);
	}
}


Measured memory_bytes: 27068
#include<bits/stdc++.h>
using namespace std;
int n,h[100100],res,lst,cur;
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++){
		if(h[i]<=h[i-1]) cur=lst+1;
		else cur=0;
		res=max(res,cur);
		lst=cur;
	}
	cout<<res<<endl;
	return 0;
}



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

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

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep_op(i, a, n) for (int i = a; i < n; i++)
#define rep_d(j, n) for (int j = n; j >= 0; j--)
#define rep_d_op(j, n, a) for (int j = n; j >= a; j--)

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

const int MOD = 1000000007;

const vector<int> dx = {1, 0};
const vector<int> dy = {0, 1};
const ll INF = 1LL << 60;

// int max = *std::max_element(vec.begin(), vec.end());
// int sum = accumulate(list, list + size, 0);

int GCD(int a, int b) { return b ? GCD(b, a % b) : a; }

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

    ll min = INF;

    ll ans = 0;
    int i = 0;
    while (true)
    {
        if (a[i] % 2 != 0)
        {
            break;
        }
        a[i] = a[i] / 2;
        i++;
        if (i == n)
        {
            i = 0;
            ans++;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
N, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 0

for i in range(N-1):
    if a[i] + a[i+1] > x:
        if a[i] < x:
            ans += a[i] + a[i+1] - x
            a[i+1] = x - a[i]
        else:
            temp = a[i] - x
            ans += a[i] + a[i+1] - x
            a[i] = x
            a[i+1] = 0
print(ans)

Measured memory_bytes: 14152
# -*- coding:utf-8 -*-
A = []
bingo = 0
for i in range(3):
    a = list(map(int, input().split()))
    A.append(a)

n = int(input())

for i in range(n):
    b = int(input())
    for ai in A:
        if b in ai:
            ai[ai.index(b)] = None

for i in range(3):
    if A[i] == [None, None, None]:
        bingo = 1

    if [A[0][i], A[1][i], A[2][i]] == [None, None, None]:
        bingo = 1

if [A[0][0], A[1][1], A[2][2]] == [None, None, None] or [A[0][2], A[1][1], A[2][0]] == [None, None, None]:
    bingo = 1

print("Yes") if bingo == 1 else print("No")


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

int main() {
  string S, T;
  cin >> S >> T;
  int min_cnt = T.size();
  int S_size = S.size();
  int T_size = T.size();
  
  for (int i = 0; i <= S_size - T_size; i++) {
    int diff = T.size();
    for (int j = 0; j < T_size; j++) {
      if(S.at(i + j) == T.at(j)) {
        diff--;
      }
    }
    min_cnt = min(min_cnt, diff);
  }
  
  cout << min_cnt << endl;
  return 0;
}


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

using namespace std;
using ll = long long;
using v1 = vector<int>;
using vl = vector<long long>;
using v2 = vector<vector<int>>;
using v3 = vector<vector<char>>;

int main(){
	int x;
	cin >> x;
	int answer = 0;
	v1 prime(1, 2);
	if(x == 2){
		answer = 2;
	}else{
		for(int i = 3; i<x; i++){
			int s = prime.size();
			for(int j = 0; j < s; j++){
				if(i%prime[j] == 0) break;
				if(j == s-1) prime.push_back(i);
			}
		}
		bool judge = true;
		int s = prime.size();
		while(judge){
			rep(i, s){
				if(x%prime[i] == 0) break;
				if(i == s-1){
					judge = false;
					answer = x;
				}
			}
			if(judge) x++;
		}
	}
	cout << answer << endl;
}


Measured memory_bytes: 3692
#include <iostream>
#include <vector>
#include <vector>

using namespace std;

int main()
{
    vector<pair<int, int>> v;
    vector<int> center;
    int rnum = 1, lnum = 0;
    string s;
    cin >> s;
    for (int i = 1; i < s.length(); i++)
    {
        if (s[i] == 'R')
        {
            if (lnum != 0)
            {
                v.push_back(make_pair(rnum, lnum));
                rnum = 1;
                lnum = 0;
            }
            else
            {
                rnum++;
            }
        }
        else
        {
            if (s[i - 1] == 'R')
                center.push_back(i - 1);
            lnum++;
        }
    }
    v.push_back(make_pair(rnum, lnum));

    vector<int> ans;
    ans.resize(s.length(), 0);
    for (int i = 0; i < v.size(); i++)
    {
        //cout << "rnum/lnum/center:" << v[i].first << " " << v[i].second << " " << center[i] << endl;
        ans[center[i] + 1] = v[i].first / 2 + (v[i].second + 1) / 2;
        ans[center[i]] = (v[i].first + 1) / 2 + v[i].second / 2;
    }

    for (int i = 0; i < ans.size(); i++)
    {
        cout << ans[i] << " ";
    }
    return 0;
}

Measured memory_bytes: 1784
using System;

public class hello
{
    public static void Main()
    {
        for (int i = 0; i < 9; i++)
        {
            string[] line = Console.ReadLine().Trim().Split(' ');
            var n = line[0];
            var a = int.Parse(line[1]);
            var b = int.Parse(line[2]);
            Console.WriteLine("{0} {1} {2}", n, a + b, 200 * a + 300 * b);
        }
    }
}

Measured memory_bytes: 9008
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int ni(int a){
  int ans=0;
  while(a%2==0 && a>0){
    a=a/2;
    ans++;
  }
  return ans;
}
int main(){
  int n;
  cin >> n;
  vector<int> vec(n);
  rep(i,n){
    cin >> vec.at(i);
  }
  int ans=0;
  rep(i,n){
    ans+=ni(vec.at(i));
  }
  cout << ans;
}
  

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define mod 1000000007
#define INF 2000000000
typedef long long ll;
bool compare(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}
// 入力



int main() {
     long double a,b,x,ans;
    
    cin >>a>>b>>x;
    if(x >= a*a*b/2.0){
        ans = (long double)atan(2.0*(a*a*b-x)/(a*a*a))*180.0/M_PI;
    }else{
        ans = 90.000000000000-  (long double)atan((x*2)/(a*b*b))*180.0/M_PI;
    }
    //ans = atan(2*(a*a*b-x)/(a*a*a))*180.0/M_PI;

    cout << fixed << setprecision(15)<< ans << endl;
    
    
    return 0;
    

}

Measured memory_bytes: 3792
H, W = map(int, input().split())
Ss = [input() for _ in range(H)]
L = [[0]*W for _ in range(H)]
R = [[0]*W for _ in range(H)]
D = [[0]*H for _ in range(W)]
U = [[0]*H for _ in range(W)]
for i in range(H):
    for j in range(W):
        if Ss[i][j] == '.':
            if j == 0:
                L[i][0] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        if Ss[i][-j-1] == '.':
            if j == 0:
                R[i][-1] = 1
            else:
                R[i][-j-1] = R[i][-j] + 1
                
for j in range(W):
    for i in range(H):
        if Ss[i][j] == '.':
            if i == 0:
                U[j][0] = 1
            else:
                U[j][i] = U[j][i-1]+1
        if Ss[-i-1][j] == '.':
            if i == 0:
                D[j][-1] = 1
            else:
                D[j][-i-1] = D[j][-i] + 1

ans = 0
for i in range(H):
    for j in range(W):
        x = L[i][j] + R[i][j] + D[j][i] + U[j][i] - 3
        if ans < x:
            ans = x
print(ans)

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

int main(){
    int n;
    cin >> n;
    ll ans = 0;
    rep(i, n){
        ll a;
        cin >> a;
        while(a % 2 ==0){
            a /= 2;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<string>
#include<vector>
#include<array>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<list>
#include<numeric>
#include<deque>
#include<chrono>
using namespace std;

int main(){
    int x,k;

    cin >> k >> x;

    for(int i=x-k+1; i <= x+k-1; i++){
        if(i<-1000000)  continue;
        if(i>1000000)   continue;

        cout << i ;
        if(i!=x+k-1)    cout << " ";
        else cout << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std ;

int main ()
{
    string str ;
    int a , b  ;
    while ( cin >> str )
    {
        a = 0 ; b = 0 ;
        for ( int i = 0 ; i < str.size() ; i ++ )
        {
            if ( i % 2 == str [ i ] - '0' )
                a ++ ;
            else b ++ ;

        }
        if ( a > b )
            cout << b << endl ;
        else cout << a << endl ;
    }
    return 0 ;
}


Measured memory_bytes: 512
n = gets.to_i
v = gets.split.map(&:to_i)
odd = Array.new(10**5+1)
even = Array.new(10**5+1)
(10**5+1).times do |i|
  odd[i] = [0,i]
  even[i] = [0,i]
end
n.times do |i|
  if i % 2 == 0
    even[v[i]][0] += 1
  elsif
    odd[v[i]][0] += 1
  end
end

odd.sort_by!{|a| a[0]}
even.sort_by! {|a| a[0]}
if odd[-1][1] == even[-1][1]
  t = [odd[-2][0], even[-2][0]].max
  p n - odd[-1][0] - t
else
  p n - odd[-1][0] - even[-1][0]
end


Measured memory_bytes: 21256
#include <iostream>
#include <algorithm>
#include <climits>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
 
#define barsik ios::sync_with_stdio(false)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
typedef long long ll;
typedef std::vector<int> vi;
typedef std::pair <int, int> pii;
typedef std::unordered_set <int> u_si;
const double PI = acos(-1);
const long double EPS = 1e-9;
using namespace std;

int n, m;
vector <string> a, b;

bool check(int x, int y){
    if(x + m > n) return false;
    int k = 0;
    for(int i = x; i < x + m; i++){
        string s = a[i].substr(y, m);
        if(s != b[k++]) return false;
    }
    
    return true;
}

void solve(){
    int n;
    cin >> n;
    int ans = 1;
    while(n > 0){
        ans = (ans * 1ll * n--) % ((int)(1e9 + 7));
    }
    cout << ans;
}

 
int main() {
    barsik;
    int q = 1;
    //cin >> q;
    while(q--) solve();
}


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

using namespace std;
typedef long long ll;

const int N=200005;
ll n;
vector<int> v[N];
vector<int> c(N,0);
vector<int> sz(N,0);
vector<int> big(N,0);
vector<ll> res(N,0);

void dfs(int a,int p=0)
{
    sz[a]=1;
    for(int to:v[a])
    {
        if(to==p) continue;
        dfs(to,a);
        sz[a]+=sz[to];
        if(sz[to]>sz[big[a]]) big[a]=to;
    }
}

map<int,ll> solve(int a,int p=0)
{
    map<int,ll> m;
    if(big[a]!=0) m=solve(big[a],a);
    for(int to:v[a])
    {
        if(to==p||to==big[a]) continue;
        map<int,ll> x=solve(to,a);
        for(auto [col,cnt]:x) m[col]+=cnt;
    }
    m[c[a]]=sz[a];
    if(p!=0)
    {
        ll x=sz[a];
        if(m.find(c[p])!=m.end()) x-=m[c[p]];
        res[c[p]]-=(x*(x-1)/2+x);
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            ll x=sz[a]-m[i];
            res[i]-=(x*(x-1)/2+x);
        }
    }
    return m;
}

int main()
{
    scanf("%lld",&n);
    for(int i=0;i<N;i++) res[i]=(n*(n-1)/2+n);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1);
    solve(1);
    for(int i=1;i<=n;i++) printf("%lld\n",res[i]);
    return 0;
}


Measured memory_bytes: 71408
#include <bits/stdc++.h>
#define ll long long
#define PB push_back
#define MP make_pair
#define ff first
#define ss second
#define pq 	priority_queue<int, vector<int>, greater<int> >
using namespace std;

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

ll a[n+1][4];

for(ll i=0;i<4;i++)
a[0][i]=0;
for(ll i=0;i<n+1;i++)
a[i][0]=0;
for(ll i=1;i<n+1;i++)
{
	for(ll j=1;j<4;j++)
	{
		cin>>a[i][j];
	}
}
ll dab[n+1]={0};
ll dac[n+1]={0};
ll dcb[n+1]={0};
ll dca[n+1]={0};
ll dba[n+1]={0};
ll dbc[n+1]={0};

dab[1]=a[1][2];
dac[1]=a[1][3];
dcb[1]=a[1][2];
dca[1]=a[1][1];
dba[1]=a[1][1];
dbc[1]=a[1][3];

for(ll i=2;i<n+1;i++)
{
	dab[i]=max(dba[i-1],dca[i-1])+a[i][2];
	dac[i]=max(dba[i-1],dca[i-1])+a[i][3];
	dbc[i]=max(dcb[i-1],dab[i-1])+a[i][3];
	dba[i]=max(dcb[i-1],dab[i-1])+a[i][1];
	dcb[i]=max(dac[i-1],dbc[i-1])+a[i][2];
	dca[i]=max(dac[i-1],dbc[i-1])+a[i][1];
	
}
ll k=0;
if(k<dab[n])k=dab[n];
if(k<dac[n])k=dac[n];
if(k<dcb[n])k=dcb[n];
if(k<dca[n])k=dca[n];
if(k<dba[n])k=dba[n];
if(k<dbc[n])k=dbc[n];
cout<<k;

	
	return 0;
}

Measured memory_bytes: 8064
#include <cstdio>
#include <algorithm>
using namespace std;
#define ref(i,x,y)for(int i=x;i<=y;++i)
#define def(i,x,y)for(int i=x;i>=y;--i)
const int mod=1e9+7;
void inc(int&a,int b){
	a+=b;if(a>=mod)a-=mod;
}
void dec(int&a,int b){
	a-=b;if(a<0)a+=mod;
}
int n,ans,a[100],f[100][100][51][51],g[100][100][51][51],h[51][51],h1[51][51],h2[201][102][102],h3[201][102][102];bool b[100];
int main(){
	scanf("%d",&n);
	ref(i,1,2*n-1)scanf("%d",&a[i]);
	sort(a+1,a+2*n);
	ref(i,1,n-1)if(a[i+1]!=a[i])b[i]=1;b[n]=1;
	ref(i,n+1,2*n-1)if(a[i-1]!=a[i])b[i]=1;
	f[n][n][1][1]=1;
	def(ti,n,2){
		ref(j,0,2*n)ref(I,1,n-ti+2)ref(J,1,I)h3[j][I][J]=0;
		def(i,2*n-1,ti){
			ref(j,i-1,2*n-ti+1)
				ref(I,1,n-ti+2)ref(J,1,I)
					h2[j][I][J]=0;
			ref(j,i,2*n-ti)if(b[i]&&b[j]){
				ref(I,1,n-ti+2)ref(J,1,I)h[I][J]=0,h1[I][J]=0;
				ref(t,1,n-ti+1)ref(k,1,t)if(f[i][j][t][k]){
					int s=f[i][j][t][k];
					inc(h[t-k+2][1],s), dec(h[t+1][k],s);
					if(k+1<=t) inc(h1[k+1][k+1],s), dec(h1[t+1][k+1],s);
					inc(h1[t][k],s), dec(h1[t+1][k],s);
					inc(h3[j][t-k+2][1],s); 
					if(j<=2*n-ti) inc(h2[j+1][k+1][k+1],s), dec(h2[2*n-ti+2][k+1][k+1],s);
				}
				ref(I,1,n-ti+2)ref(J,1,I){
					inc(h[I][J],h[I-1][J-1]); inc(h1[I][J],h1[I-1][J]);
					inc(g[i][j][I][J],h[I][J]);
					inc(g[i][j][I][J],h1[I][J]);
				}
			}
			if(b[i-1])ref(j,i,2*n-ti)
				ref(t,1,n-ti+2)ref(k,1,t){
					inc(g[i-1][j][t][k],h3[j][t][k]);
				}
			ref(j,i,2*n-ti+1)
				ref(I,1,n-ti+2)ref(J,1,I){
					inc(h2[j][I][J],h2[j-1][I][J]);
					if(b[i]&&b[j])inc(g[i][j][I][J],h2[j][I][J]);
				}
		}
		ref(i,1,2*n-1)ref(j,1,2*n-1)if(b[i]&&b[j])
			ref(t,1,n-ti+2)ref(k,1,t)
				f[i][j][t][k]=g[i][j][t][k],g[i][j][t][k]=0;
	}
	ref(i,1,2*n-1)ref(j,i,2*n-1)ref(t,1,n)ref(k,1,t)
		inc(ans,f[i][j][t][k]);
	printf("%d\n",ans);
}

Measured memory_bytes: 212736
import java.util.*;
import java.util.stream.IntStream;

class Dice {
	int[] surfaces = new int[6];

	Dice(int[] diceNumArr) {surfaces = diceNumArr;}

	public int getTopNumber() {return surfaces[0];}

	public void move(String str) {
		for (char d : str.toCharArray()) {
			if (d == 'E') {roll(true, false, false);}
			else if (d == 'W') {IntStream.range(0, 3).forEach(e -> roll(true, false, false));}
			else if (d == 'S') {IntStream.range(0, 3).forEach(e -> roll(false, true, false));}
			else if (d == 'N') {roll(false, true, false);}
		}
	}

	private void roll(boolean x, boolean y, boolean z) {
		if (x && !y && !z) {roll(0, 3, 5, 2);}
		else if (!x && y && !z) {roll(0, 1, 5, 4);}
		else if (!x && !y && z) {roll(1, 2, 4, 3);}
	}

	private void roll(int w, int x, int y, int z) {
			int tmp = surfaces[w];
			surfaces[w] = surfaces[x];
			surfaces[x] = surfaces[y];
			surfaces[y] = surfaces[z];
			surfaces[z] = tmp;
	}

	public void setTopAndFront(int top, int front) {
		isSame(top, front, -1);
	}

	private boolean isSame(int... srf) {
		for (int xy = 0; xy < 6; xy++) {
			for (int z = 0; z < 4; z++) {
				if (surfaces[0] == srf[0] && surfaces[1] == srf[1] ) {
					if(srf[2] < 0) return false;
					int[] a = Arrays.copyOfRange(surfaces, 2, surfaces.length);
					int[] b = Arrays.copyOfRange(srf, 2, srf.length);
					if (Arrays.equals(a, b)) return true;
				}
				roll(false, false, true);
			}
			if (xy % 2 == 0) {roll(true, false, false);}
			else {roll(false, true, false);}
		}
		return false;
	}

	@Override
	public boolean equals(Object obj) {
		Dice other = (Dice) obj;
		return isSame(other.surfaces);
	}
}
public class Main {
	public static void main(String[] args) {
		try (java.util.Scanner sc = new java.util.Scanner(System.in)) {
			int cntDice = sc.nextInt();
			List<Dice> diceL = new ArrayList<>();

			java.util.stream.IntStream.range(0, cntDice).forEachOrdered(e -> {
				int[] diceNumArr = {sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt(),sc.nextInt(), sc.nextInt()};
				Dice dice = new Dice(diceNumArr);
				diceL.add(dice);
			});

			System.out.println(diceL.stream().skip(1).noneMatch(d -> d.equals(diceL.get(0))) ? "Yes" : "No");
		}
	}
}


Measured memory_bytes: 33592
# dp[i][j] := sのi文字目まで見たときに、ABCのj文字目までを部分列として取り出す方法の数。

s = input()

dp = [[0 for _ in range(4)]for _ in range(len(s))]
mod = 10 ** 9 + 7

power_3 = 1
for idx, letter in enumerate(s):
    dp[idx] = dp[idx-1].copy()

    if letter == 'A':
        dp[idx][1] += power_3
    elif letter == 'B':
        dp[idx][2] += dp[idx-1][1]
    elif letter == 'C':
        dp[idx][3] += dp[idx-1][2]
    elif letter == '?':
        dp[idx][1] *= 3
        dp[idx][2] *= 3
        dp[idx][3] *= 3
        dp[idx][1] += power_3 # 3**(この?を含まない、今までの?の個数)だけ、Aの手前の場合が考えられる。
        power_3 *= 3
        power_3 %= mod
        dp[idx][2] += dp[idx-1][1]
        dp[idx][3] += dp[idx-1][2]
        dp[idx][1] %= mod
        dp[idx][2] %= mod
        dp[idx][3] %= mod


print(dp[len(s)-1][3] % mod) 
# print(dp)


Measured memory_bytes: 28648
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main(){
  double d;
  cin>>d;
  printf("%.10f\n", max(floor(d)+1, d*sqrt(2)));
  return 0;
}



Measured memory_bytes: 3280
import sys

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

def minesweeper(x, y):
    count = 0
    if S[x][y] == ".":
        for i in dx:
            for j in dy:
                nx = x + i
                ny = y + j
                if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == "#":
                    count += 1
        S[x][y] = count
    if y + 1 != W:
        print(S[x][y], end="")
    else:
        print(S[x][y], end="\n")
        

H, W = map(int, sys.stdin.readline().split())
S = [list(sys.stdin.readline().rstrip()) for i in range(H)]

for i in range(H):
    for j in range(W):
        minesweeper(i, j)

Measured memory_bytes: 3444
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}

struct UnionFindTree {
  std::vector<int> data;

  UnionFindTree(int size) : data(size, -1) { }
  bool Unite(int x, int y) {
    x = Root(x); y = Root(y);
    if (x != y) {
      if (data[y] < data[x]) std::swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
    return x != y;
  }
  bool IsSameRoot(int x, int y) {
    return Root(x) == Root(y);
  }
  int Root(int x) {
    return data[x] < 0 ? x : data[x] = Root(data[x]);
  }
  int Size(int x) { return -data[Root(x)]; }
};

int main() {
  int N, K; cin >> N >> K;
  vector<LL> P(N), C(N); cin >> P >> C;
  for (LL& x : P) --x;

  UnionFindTree tree(N);
  for (int i = 0; i < N; ++i) {
    if (tree.Root(i) != i) continue;
    int j = i;
    do {
      j = P[j];
      tree.Unite(i, j);
    } while (j != i);
  }

  map<int, LL> m;
  for (int i = 0; i < N; ++i) {
    if (tree.Root(i) != i) continue;
    m[i] = 0;
    int j = i;
    do {
      m[i] += C[j];
      j = P[j];
    } while (j != i);
  }

  LL ans = -1e18;
  for (int i = 0; i < N; ++i) {
    int n = tree.Root(i);
    int size = tree.Size(n);
    LL loop = max(0, K/size - 1);
    LL sum = max(0LL, m[n]) * loop;
    int r = K - size * loop;

    int j = i;
    for (int k = 0; k < r; ++k) {
      j = P[j];
      sum += C[j];
      ans = max(ans, sum);
    }
  }
  cout << ans << endl;
}


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

using namespace std;

int main()
{
   int N, K, sub;
   int kind = 0, ans = 0;

   cin >> N >> K;

   int *num = new int[N+1];
   int *A = new int[N];

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

   num[N] = 0;

   for(int i=0;i<N;i++){
      num[A[i]]++;
   }

   for(int i=1;i<=N;i++){
      if(num[i] > 0)  kind++;
   }

   sub = kind - K;

   //cout << "kind : " << kind << "\n" << "sub : " << sub << "\n";

   if(sub <= 0){
      ans = 0;
   }else{
      stable_sort(num, num+N+1);
//   for(int i=0;i<N+1;i++){
//      cout << num[i] << endl;
//   }
      for(int i = N+1-kind;i < (N+1-kind)+sub; i++){
         ans +=num[i];
      }
   }

   cout << ans << endl;

   delete num;
   delete A;

   return 0;

}


Measured memory_bytes: 2176
import itertools

N, M = map(int, input().split())
G = [[] * (N + 1)for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

l = range(2, N + 1)

ans = 0

for p in itertools.permutations(l):
    # 試す順列を作る
    nums = [1]
    for n in p:
        nums.append(n)

    flag = True

    for i in range(N - 1):
        if nums[i + 1] in G[nums[i]]:
            continue
        else:
            flag = False
            break
    if flag == True:
        ans += 1

print(ans)


Measured memory_bytes: 73636
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std ;
#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define mod 1000000007

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int n ;
int arr[500005] ;
int X[500005] ;
int Y[500005] ;
string str ;
typedef long long i64;

    i64 cross(pair<i64,i64>P,pair<i64,i64>Q,pair<i64,i64> R)//if return >0 then point R is upper of lineseg PQ else down
        {
            return  (Q.first-P.first)*(R.second-P.second)-(R.first-P.first)*(Q.second-P.second);
        }
    void hull(vector<pair<i64,i64> > &P,vector<pair<i64,i64> > &L,vector<pair<i64,i64> > &U)
        {
            int j=0,k=0,n=P.size();
            sort(P.begin(),P.end());
            U.resize(2*n);
            L.resize(2*n);
            for(int i=0;i<n;i++)
             {
                while(j>=2 && cross(L[j-2],L[j-1],P[i])<=0)//p[i] is making right turn we need left turn
                    j--;
                while(k>=2 && cross(U[k-2],U[k-1],P[i])>=0)//p[i] is making left turn we need right
                    k--;
                L[j++]=P[i];
                U[k++]=P[i];
            }
            U.resize(k);
            L.resize(j);
        }
    i64 fun(pair<i64,i64> P ,pair<i64,i64> Q)
        {
            return abs(P.first-Q.first)+abs(P.second-Q.second);
        }
void solve()
{
    cin >> n ;
    vector<pii> v,U,L ;
    for(int i=1 ; i<=n ; i++)
    {
        cin >> X[i] >> Y[i] ;
        v.pb({X[i],Y[i]}) ;
    }
    if(n==1)
    {
        cout<<"0\n";
        return ;
    }

    hull(v,L,U);
    int i=0,j,m;
                j=L.size()-1;
                m=U.size()-1;
                i64 dist=-1;
                while(i<m || j>0)
                {
                    dist=max(dist,fun(U[i],L[j]));
                    if(i==m)
                        j--;
                    else if(j==0)
                        i++;
                    else
                    {
                        if ( (U[i+1].second-U[i].second) * (L[j].first-L[j-1].first) > (L[j].second-L[j-1].second) * (U[i+1].first-U[i].first) )
                        i++;
                    else
                        j--;
                    }
                }
                cout<<dist;
}
int32_t main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int tt = 1;
	//cin >> tt ;
	while(tt--)
	{
	     solve() ;
	}
}


Measured memory_bytes: 22084
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>
#include<queue>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
using namespace std;
using ll =long long;
using P = pair<int,int>;

#define MAX_H 50
#define MAX_W 50

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

int main(int argc, const char * argv[]) {
    
    int h, w;
    cin >> h >> w;
    
    char field[MAX_H][MAX_W];
    int dist[MAX_H][MAX_W];
    int change=-1;
    
    rep(y, h){
        string s;
        cin >> s;
        rep(x, w){
            if(s[x]=='.') change++;
            field[y][x] = s[x];
            dist[y][x] = -1;
        }
    }
    
    queue<P> que;
    que.push(P(0,0));
    dist[0][0]=0;
    
    while(que.size()){
        P p = que.front();
        que.pop();
        
        rep(i, 4){
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
            
            if(0<=nx && nx<w && 0<=ny && ny<h && field[ny][nx] == '.' && dist[ny][nx]==-1){
                dist[ny][nx] = dist[p.second][p.first]+1;
                que.push(P(nx, ny));
            }
        }
    }
    
    if(dist[h-1][w-1]>=0) cout << change - dist[h-1][w-1] << endl;
    else cout << "-1" << endl;
 
    return 0;
}


Measured memory_bytes: 256