akhauriyash/Code-Regression huggingface dataset:
import numpy as np
import itertools
import sys
input = sys.stdin.readline  #文字列入力では注意！

N,C = map(int,input().split())
D = np.array([list(map(int,input().split()))for _ in range(C)], dtype=np.int64)
c = np.array([list(map(int,input().split()))for _ in range(N)], dtype=np.int64)
c0 = np.zeros(C)
c1 = np.zeros(C)
c2 = np.zeros(C)
for i in range(N):
    for j in range(N):
        if (i+j)%3 == 0:
            c0[c[i,j]-1] += 1
        if (i+j)%3 == 1:
            c1[c[i,j]-1] += 1
        if (i+j)%3 == 2:
            c2[c[i,j]-1] += 1
# c0~2はXの情報
lis = itertools.permutations([i for i in range(C)],3)
ans = float("inf")
for l0,l1,l2 in lis:    # l0~2はYの情報
    tmp = np.sum(D[:,l0]*c0+D[:,l1]*c1+D[:,l2]*c2, dtype=np.int64)
    ans = min(ans,tmp)
print(ans)


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

int calc(int x, int y, int a, int b) {
	if (a >= 5 && b >= 2) {
		x = x * 8 / 10;
		y = y * 8 / 10;
	}
	
	return x * a + y * b;
}

int main() {
	int N; cin >> N;
	
	for (int i = 0; i < N; ++i) {
		int x, y, a, b; cin >> x >> y >> a >> b;
		int sa = max(5 - a, 0), sb = max(2 - b, 0);
		cout << min(calc(x, y, a, b), calc(x, y, a + sa, b + sb)) << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1164
#include<stdio.h>
int main(){
  int H,W,h,w,i=1,j;
  scanf("%d%d%d%d",&H,&W,&h,&w);
  if(H%h||W%w){
    for(puts("Yes");i<=H;++i,puts("")) for(j=0;j<W;++j,printf("%d ",(i%h||j%w)?1000:-1000*(h*w-1)-1));
  }else puts("No");
  return 0;
}

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

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  
  Int n,m;
  cin>>n>>m;
  
  vector<string> s(n);
  for(Int i=1;i<n;i++) cin>>s[i];
  
  using P = pair<Int, Int>;
  vector<vector<Int> > G(n);
  for(Int i=1;i<n;i++){
    Int u,v;
    cin>>u>>v;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  vector<Int> c(n,0);
  {
    Int x=0b011;
    Int y=0b101;
    vector<Int> w({0,x&y,(x|y)^y,x,(x|y)^x,y,x^y,x|y});
    function<void(Int,Int)> dfs=[&](Int v,Int p){
      for(Int u:G[v]){
	if(u==p) continue;
	if(s[u]=="T=T&X") c[u]=c[v]&x;
	if(s[u]=="T=T&Y") c[u]=c[v]&y;
	if(s[u]=="T=T|X") c[u]=c[v]|x;
	if(s[u]=="T=T|Y") c[u]=c[v]|y;
	if(s[u]=="T=T^X") c[u]=c[v]^x;
	if(s[u]=="T=T^Y") c[u]=c[v]^y;
	dfs(u,v);
      }
    };
    dfs(0,-1);
  }
  
  map<vector<Int>, Int> ans;
  
  for(Int i=0;i<m;i++){
    Int x,y;
    cin>>x>>y;
    vector<Int> w({0,x&y,(x|y)^y,x,(x|y)^x,y,x^y,x|y});
    function<Int(Int,Int,Int)> dfs=[&](Int v,Int p,Int d){
      Int res=-1;
      for(Int u:G[v]){
	if(u==p) continue;
	Int e=dfs(u,v,!d);
	if(res<0) res=e;
	if(!d&&(w[e]>w[res]||(w[e]==w[res]&&e>res))) res=e;
	if( d&&(w[e]<w[res]||(w[e]==w[res]&&e<res))) res=e;
      }
      if(res<0) res=c[v];
      return res;
    };
    
    vector<P> v;
    for(Int i=0;i<8;i++) v.emplace_back(w[i],i);
    sort(v.begin(),v.end());
    vector<Int> u(8);
    for(Int i=0;i<8;i++) u[i]=v[i].second;
    if(!ans.count(u)) ans[u]=dfs(0,-1,0);
    cout<<w[ans[u]]<<endl;
  }
  return 0;
}



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

int main() {
  int N;
  cin >> N;
  int N2 = N;
  int sum = 0;
  for (int i = 7; i >= 0; i --) {
    int X = 1;
    for (int cnt = 0; cnt < i; cnt ++) {
      X *= 10;
    }
    int tmp = N / X;
    if (tmp > 0) {
      sum += tmp;
      N -= tmp * X;
    }
    
  }
  int x = N2 % sum;
  if (x == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int T,N;
main()
{
	cin>>T;
	for(;T--;)
	{
		cin>>N;
		vector<pair<int,pair<int,int> > >L[2];
		long ans=0;
		for(int i=0;i<N;i++)
		{
			int k,l,r;cin>>k>>l>>r;
			if(l>r)
			{
				L[0].push_back(make_pair(k,make_pair(l,r)));
			}
			else if(l<r)
			{
				L[1].push_back(make_pair(N-k,make_pair(r,l)));
			}
			else ans+=l;
		}
		for(int id=0;id<2;id++)
		{
			priority_queue<pair<int,int> >P;
			vector<vector<pair<int,int> > >tmp(N);
			for(pair<int,pair<int,int> >p:L[id])
			{
				if(p.first==0)ans+=p.second.second;
				else tmp[p.first-1].push_back(p.second);
			}
			for(int i=N;i--;)
			{
				for(pair<int,int>p:tmp[i])P.push(make_pair(p.first-p.second,p.first));
				if(i<L[id].size()&&!P.empty())
				{
					ans+=P.top().second;
					P.pop();
				}
			}
			while(!P.empty())
			{
				ans+=P.top().second-P.top().first;
				P.pop();
			}
		}
		cout<<ans<<endl;
	}
}


Measured memory_bytes: 14212
#include<bits/stdc++.h>
using namespace std;
string to_string(const string& s) {
	return '"' + s + '"';
}
string to_string(const bool b) {
	return (b ? "true" : "false");
}
string to_string(const char* s) {
	return to_string((string)s);
}
string to_string(const char c) {
	string s = "'";
	s += c;
	s += "'";
	return s;
}
template<class T, class U>
string to_string(const pair<T, U>& p) {
	string s = "(";
	s += to_string(p.first);
	s += ", ";
	s += to_string(p.second);
	s += ")";
	return s;
}
template<class T>
string to_string(const T& a) {
	bool first = true;
	string s = "{";
	for (const auto& x : a) {
		if(!first){
			s += ", ";
		}
		first = false;
		s += to_string(x);
	}
	s += "}";
	return s;
}
void debug_out() {cerr << '\n';}
template<class Head, class... Tail>
void debug_out(Head head, Tail... tail) {
	cerr << ' ' << to_string(head);
	debug_out(tail...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
using ll = long long;
using ld = long double;
const int mod = 1e9 + 7;
const int inf = 1e9 + 100;
const ll inf64 = 7e18l;
map<pair<int, int>, int> color;
vector<vector<int>> graph;
int answer = 0;
struct edge {
	int u, v;
}; 
void dfs(int a, int p = -1, int c = -1) {
	int now_c = 0;
	for (int x : graph[a]) {
		if (x != p) {
			++now_c;
			if (now_c == c) {
				++now_c;
			}
			color[{a, x}] = color[{x, a}] = now_c;
			dfs(x, a, now_c);
		}
	}
	answer = max(answer, now_c);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(20);
	int n;
	cin >> n;
	graph.resize(n);
	vector<edge> edges;
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		--u;
		--v;
		graph[u].push_back(v);
		graph[v].push_back(u);
		edges.push_back({u, v});
	}
	dfs(0);
	cout << answer << '\n';
	for (int i = 0; i < n - 1; ++i) {
		int u = edges[i].u;
		int v = edges[i].v;
		cout << color[{u, v}] << '\n';
	}
 	return 0;
}


Measured memory_bytes: 20476
import sys
import math
a, b = map(int, input().split())

ans = ('-1')

for i in range(10001):
    z8 = math.floor(i * 0.08)
    z10 = math.floor(i * 0.1)

    if z8 == a and z10 == b:
        ans = i
        break

print(ans)

Measured memory_bytes: 3060
from collections import defaultdict

N = int(input())
D = list(map(int, input().split()))

MOD = 998244353

p = defaultdict(int)
for d in D:
    p[d] += 1

if p[0] == 1 and D[0] == 0:
    ans = 1
    for i in range(N + 1):
        ans *= p[i] ** p[i + 1]
        ans %= MOD

    print(ans % MOD)

else:
    print(0)


Measured memory_bytes: 24172
/*
    問題をよく読もう！
    論理的に考えよう！
    サンプルを確認しよう!
    絶対に諦めるな！
    工夫をしろ！
    配列は少し多めにとっておく

    Twitterは終わるまでログアウト！
    （間違えて解法をツイートしてはいけないから）

*/
//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include<cstring>
//namespace
using namespace std;
//繰り返し
#define REP(i, m, n) for(int i=(int)m; i<(int)n; ++i)
#define rep(i, n) REP(i, 0, n)
//イテレータ
#define all_range(C) begin(C), end(C)
//簡略化
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
typedef pair<string,int> pst;

const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
//最大最小
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) {if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) {if(a<b) a=b;}

//関数

//最大公約数を求める
ll my_gcd(ll x, ll y) {
  ll r;

  while(y!=0) {
    r = x%y;
    x = y;
    y = r;
  }

  return x;
}

//最小公約数を求める
ll my_lcm(ll x, ll y) {

  return (x*y)/my_gcd(x,y);
}

//xのy乗を求める ※参考：10^18乗まで
ll my_pow(ll x, ll y) {
  ll sum = 1;

  while(y>0) {
    sum *= x;
  }

  return sum;
}

/*考えを書くスペース

*/
//main.cpp----------------------------
#define max_n 100

void solve();

ll a, b, c;

int main() {
  cin >> a >> b >> c;

  solve();

  return 0;
}

void solve() {

  if(a%2==0||b%2==0||c%2==0) {
    cout << 0 << endl;
  }else {
    ll min = a*b;
    chmin(min, b*c);
    chmin(min, c*a);
    cout << min << endl;
  }
}


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

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define IOS             ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)
#define loop(i,a,b)     for (ll i = a; i <= b; i++)
#define rloop(i,a,b)    for (ll i = a; i >= b; i--)
#define ms(a,x)         memset(a,x,sizeof a)
#define ll              long long int
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define rall(a)         a.rbegin(),a.rend()
#define pb              push_back
#define nl              cout<<"\n"
#define gcd(a,b)        __gcd((a),(b))
#define lcm(a,b)        ((a)*(b))/(gcd(a,b))
#define sq(a)           (a)*(a)
#define sz(a)           a.size()
#define mod             1000000007
#define PI              2*acos(0.0)

int main()
{
    IOS
    int T=1;
    //cin>>T;
    while(T--)
    {
        ll n,x,m;
        cin>>n>>x>>m;
        vector<ll>a;
        a.pb(x);
        map<ll,ll> mp;
        mp[x]++;
        int i=0;
        while(1)
        {
            if(mp[sq(a[i])%m])
            {
                loop(j,0,sz(a)-1) if(a[j]==sq(a[i])%m) {i=j;break;}
                break;
            }
            a.pb(sq(a[i])%m);
            mp[sq(a[i])%m]++;
            i++;
        }
        ll ans=0;
        loop(k,0,i-1) ans+=a[k];
        ll q=sz(a)-i;
        n-=i;
        ll qq=n/q;
        ll aa=0;
        loop(k,i,sz(a)-1) aa+=a[k];
        ans+=(aa*qq);
        if(n%q)
        {
            ll pp=n%q;
            while(pp--)
                ans+=a[i++];
        }
        cout<<ans;

    }
    return 0;
}


Measured memory_bytes: 6768
N = int(input())
r = [[int(s) for s in input().split()] for i in range(N)]

import math

def get_distance(r1, r2):
  return math.sqrt((r1[0]-r2[0])*(r1[0]-r2[0])+(r1[1]-r2[1])*(r1[1]-r2[1]))

idx = [i for i in range(N)]
import itertools
p = itertools.permutations(idx, N)

total_distance = 0.0
count = 0

for order in p:
  for i in range(N-1):
    total_distance += get_distance(r[order[i]], r[order[i+1]])
print(total_distance/math.factorial(N))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int n,w;
vector<ll> we;
vector<ll> val;
ll max(ll a,ll b)
{
    return a>b?a:b;
}

int main()
{
    cin>>n>>w;
    we.resize(n);
    val.resize(n);
    for(ll i=0;i<n;i++)
    {
        cin>>we[i];
        cin>>val[i];
    }
    vector<vector<ll> > ans(n+1,vector<ll> (w+1,0));

    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=w;j++)
        {
            if(j-we[i-1]>=0)
            ans[i][j]=(ll)max(ans[i-1][j],ans[i-1][j-we[i-1]]+val[i-1]);
            else
            ans[i][j]=ans[i-1][j];
        }
    }
    cout<<ans[n][w];
    return 0;
}

Measured memory_bytes: 80256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define eps 1e-9
#define inf 0x3f3f3f
#define mod 4999999
using namespace std;

int main() {
	speed;
    int n,a = 0,w = 0,t = 0,r = 0;
    cin >> n;
    string s;
    for (int i = 0; i < n; ++i) {
        cin >> s;
        if (s == "AC")
            a++;
        else if (s == "TLE")
            t++;
        else if (s == "WA")
            w++;
        else
            r++;
    }
    cout << "AC x " << a << "\nWA x " << w << "\nTLE x " << t << "\nRE x " << r;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

struct UnionFind {  
  vector<int> par,sizes;                     // par[i]:iの親の番号(ex)par[3]=2 : 3の親が2
  UnionFind(int n) : par(n),sizes(n,1)  {    //最初は全てが根であるとして初期化
    for(int i=0; i<n; i++){ par[i]=i; }  
  }
  int root(int x) {                       //xが属する木の根を再帰で得る:root(x)={xの木の根}
    if(par[x]==x){ return x; }
    return par[x] = root(par[x]);
  }
  void unite(int x, int y) {                 // xとyの木を併合
    int rx = root(x);                        //xの根をrx
    int ry = root(y);                        //yの根をry
    if(rx == ry){ return; }                  //xとyの根が同じ(=同じ木にある)時はそのまま
    if(sizes[rx]<sizes[ry]){ swap(rx, ry); } //xの木をおおきくする
    par[ry] = rx; 
    sizes[rx] += sizes[ry];                  //sizes[ry]はもう使わない
  }
 
  bool check(int x, int y) {                 // x,yが属する木が同じならtrueを返す
    return root(x) == root(y);
  }
  
  int size(int x){                           //xが含まれる木の大きさを返す
    return sizes[root(x)];
  }
};


int main() {
  ll n,m; cin >> n >> m;
  UnionFind tree(n);
  vector<ll> ans(m,0);
  vector<pair<ll,ll>> e;
  rep(i,m){
    int x,y; cin >> x >> y; x--; y--;
    e.emplace_back(x,y);
  }
  reverse(e.begin(),e.end());
  
  ans[m-1] = n*(n-1)/2;
  rep(i,m-1){
    ans[m-2-i] = ans[m-1-i];
    if(!tree.check(e[i].F,e[i].S)){
      ll tmp = (ll)tree.size(e[i].F)*(ll)tree.size(e[i].S);
      ans[m-2-i] -= tmp;
    }
    tree.unite(e[i].F,e[i].S);
  }
  
  rep(i,m){
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 4592
N = int(input())
S = input()

left = 0
right = 0

for letter in S:
    if letter == '(':
        left += 1
    if letter == ')':
        right += 1
        if left < right:
            S = '(' + S
            left += 1

if right < left:
    S = S + abs(right - left) * ')'
print(S)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include<cmath>
#define _GLIBCXX_DEBUG
using namespace std;

int main()
{
    long long A,B,N;
    cin>>A>>B>>N;
    long long x;
    if(N>=B){
        x=B-1;
    }
    else{
        x=N;
    }
    cout<<A*x/B;
}

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

using i64 = long long;

int cost[100005]={0};

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> v;
    for(int i=0;i<n;++i){
        cost[i] = INT_MAX;
        int h;
        cin >> h;
        v.push_back(h);
    }
    cost[0] = 0;
    for(int i=0;i<n-1;++i){
        for(int j=1;j<=k;++j){
            if(i+j < n){
                cost[i+j] = min(cost[i+j], cost[i]+abs(v[i]-v[i+j]));
            }
        }
    }

    cout << cost[n-1] << endl;

    return 0;
}


Measured memory_bytes: 1148
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
int N;//pcの数
int M;//学生の数
int r;//利用記録の数
int mae;
int sch[10010][1270];//生徒がどれだけパソコンにログインしていたか
int main(){
	while(cin>>N>>M){
		if(N==0&&M==0)
			break;
		cin>>r;
		for(int i = 0;i <=M;i++){
			for(int j = 0;j <=1260;j++){
				sch[i][j] = 0;
			}
		}
		map<pii,int> st;//学生、PC
		st.clear();
		for(int i = 0;i < r;i++){
			int t,n,m,s;//時刻t,PCn,学生m,s
			cin>>t>>n>>m>>s;
			if(s==1){
				st[pii(m,n)] = t;
			}else if(s==0){
				int mae = st[pii(m,n)];
				st.erase(pii(m,n));
				for(int j = mae;j <=t;j++){
					sch[m][j] = 1;
				}
			}
		}
		int q;
		cin>>q;
		int sum;
		for(int i = 0;i < q;i++){
			int ts,te,m;//開始、終了、学生
			cin>>ts>>te>>m;
			sum = 0;
			for(int j = ts+1;j <=te;j++){
				if(sch[m][j]&&sch[m][j-1]){
					sum++;
					//cout <<"(sum,j) = "<<sum<<" "<<j<<endl;
				}
			}
			cout <<sum<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 50348
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <vector <int> > aa;
bool cmp(vector<int>a,vector<int>b){
	return a[0]<b[0];
}
int main(){
	cin.tie(0);
	cin.sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	aa.assign(n,vector<int>(2,0));
	for(int i=0;i<n;i++){
		int a,b;
		for(int j=0;j<2;j++){
			cin>>aa[i][j];
		}
	}
	sort(aa.begin(),aa.end(),cmp);
	long long int cost=0;
	for(int i=0;i<n;i++){
		cost+= (long long int )min(m,aa[i][1])*aa[i][0];
		m-=min(m,aa[i][1]);
		if(!n) break;
	}
	cout<<cost<<endl;
}

Measured memory_bytes: 5760
#include <valarray>
#include <cstdio>
using namespace std;
typedef valarray<int>V;
int n,m;
V z;

main(){
	int i,j,a,b,c,t;
	for(;scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&t),n;){
		V x(n*n);
		V e(n*n);
		z.resize(n*n);

		x[0]=b;
		x[1]=c;
		e[0]=1;
		for(i=1;i<n-1;i++){
			x[i*n+i-1]=a;
			x[i*n+i]=b;
			x[i*n+i+1]=c;
			e[i*n+i]=1;
		}
		x[i*n+i-1]=a;
		x[i*n+i]=b;
		e[i*n+i]=1;
		for(;t;t>>=1){
			if(t&1){
				for(i=0;i<n;i++)for(j=0;j<n;j++)z[i*n+j]=((const V)e[slice(i*n,n,1)]*(const V)x[slice(j,n,n)]).sum()%m;
				e=z;
			}
			for(i=0;i<n;i++)for(j=0;j<n;j++)z[i*n+j]=((const V)x[slice(i*n,n,1)]*(const V)x[slice(j,n,n)]).sum()%m;
			x=z;
		}
		V s(n);
		for(i=0;i<n;i++)scanf("%d",&s[i]);
		for(i=0;i<n-1;i++)printf("%d ",((const V)e[slice(i*n,n,1)]*s).sum()%m);
		printf("%d\n",((const V)e[slice(i*n,n,1)]*s).sum()%m);
	}
}

Measured memory_bytes: 1088
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        vector<vector<pair<int, int>>> g(n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b, c;
                scanf("%d%d%d", &a, &b, &c);
                g[a].emplace_back(b, c);
                g[b].emplace_back(a, c);
        }
        vector<vector<pair<int, int>>> d(n);
        vector<int> far(n);
        function<void (int, int)> dfs2 = [&](int u, int prev) {
                for (auto e : g[u]) if (e.first != prev) {
                        int v = e.first;
                        dfs2(v, u);
                        far[u] = max(far[u], far[v] + e.second);
                        d[u].push_back({far[v] + e.second, v});
                }
        };
        dfs2(0, -1);
        sort(d[0].rbegin(), d[0].rend());
        function<void (int, int)> dfs3 = [&](int u, int prev) {
                for (auto e : g[u]) if (e.first != prev) {
                        int v = e.first;
                        if (d[u][0].second == v) { 
                                d[v].push_back({(u == 0 ? 0 : d[u][1].first) + e.second, u});
                        } else { 
                                d[v].push_back({d[u][0].first + e.second, u});
                        }
                        sort(d[v].rbegin(), d[v].rend());
                }
                for (auto e : g[u]) if (e.first != prev) {
                        dfs3(e.first, u);
                }
        };
        dfs3(0, -1);
        /*
        for (auto dd : d) {
                for (auto it : dd) {
                        cerr << it.first << ' ' << it.second << endl;
                }
                cerr << endl;
        }
        */
        int ans = 0;
        for (int i = 0; i < n; i ++) {
                if ((int) d[i].size() >= 2) { 
                        ans = max(ans, d[i][0].first + d[i][1].first);
                }
        }
        printf("%d\n", ans);
        return 0;
}




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

int getgcd(int n, int m)
{
    int r;
    if (n > m) {
        int t = m;
        m = n;
        n = t;
    }
    while ((r = m % n) != 0) {
        m = n;
        n = r;
    }
    return n;
}

int main() {
    int N;
    int A[100000];
    int memo[100000];
    cin>>N;

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

    memo[0]=A[0];
    for(int i=1; i<N; i++){
        memo[i]=getgcd(memo[i-1], A[i]);
    }

    cout<<memo[N-1]<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<algorithm>
#include<numeric>
#define int long long
#define all(x) x.begin(),x.end()
#define what_is(x) cerr << #x << " is " << x << endl;
const int MOD = 1e9 + 7;
using namespace std;
string abc="abcdefghijklmnopqrstuvwxyz";
#define PI 3.14159265358979323846264338327950L
int powmod(int a, int b, int MOD = MOD){
    if(!a and !b)    return 1ll;
    if(!a)    return a;
    int res = 1ll;
    b %= (MOD - 1ll), a %= MOD;
    while(b){
        if(b%2 == 1)    res = (res * a) % MOD;
        a = (a * a) % MOD;
        b /= 2;
    }
    return res;
}
int popcount(uint32_t n)
{
    n = n - ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
bool check(int n) {return (((double)sqrt(n)-floor((double)sqrt(n)))==0);}
void solve() {
   int a,b,x,y;
   cin>>a>>b>>x>>y;
    long double rad = PI * 2 * ( (long double )x / 12.0 + ((long double)y / 60.0) / 12.0 - (long double)y / 60.0);
//    cout<<rad<<" ";
//   x=x*5;
//   int dif=abs(x-y);
//   if(dif>30)
//   {
//       dif=60-dif;
//   }
//   long double ang=(dif/5)*30;
//   ang=ang*PI/180;
//   cout<<ang<<" ";
   long double ans=sqrt(a*a + b*b - 2*a*b*cosl(rad));
   cout<<fixed<<setprecision(20)<<ans;

}
int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //cout<<"Hello World"<<"\n";
    //int t;cin>>t;while(t--)
        solve();

}

Measured memory_bytes: 4140
// input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn mod_pow(mut base: u32, mut exp: u32, modulus: u32) -> u32 {
    if modulus == 1 {
        return 0;
    }
    let mut result = 1;
    base = base % modulus;
    while exp > 0 {
        if exp % 2 == 1 {
            result = result * base % modulus;
        }
        exp = exp >> 1;
        base = base * base % modulus
    }
    result
}

fn main() {
    input! {
        _s: String,
    }

    let s = _s.chars().collect::<Vec<char>>();
    let mut ans = vec![0; 2019];

    let mut v = Vec::new();
    v.reserve(s.len() + 1);

    v.push(0);
    ans[0] += 1;

    for i in 0..s.len() {
        let tmp =
            (v[i] + s[s.len() - i - 1].to_digit(10).unwrap() * mod_pow(10, i as u32, 2019)) % 2019;
        v.push(tmp);

        ans[tmp as usize] += 1;
    }

    let mut count: usize = 0;
    for m in ans {
        if m != 0 {
            count += m * (m - 1) / 2;
        }
    }

    println!("{}", count);
}


Measured memory_bytes: 3916
N,M,Q=map(int,input().split())
S=[0]*Q;t=0;d=0;A=[0]*10
for i in range(Q):
  a,b,c,d=map(int,input().split())
  S[i]=[a,b,c,d]
#print(S)
for i1 in range(1,M+1):
  for i2 in range(i1,M+1):
    for i3 in range(i2,M+1):
      for i4 in range(i3,M+1):
        for i5 in range(i4,M+1):
          for i6 in range(i5,M+1):
            for i7 in range(i6,M+1):
              for i8 in range(i7,M+1):
                for i9 in range(i8,M+1):
                  for i10 in range(i9,M+1):
                    d=0
                    A=[i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for i in range(Q):
                      if A[S[i][1]-1]-A[S[i][0]-1]==S[i][2]:
                        d=d+S[i][3]
                    t=max(t,d)
                    
print(t)

Measured memory_bytes: 9216
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define rep(i, n) for(int i=0;i<n;i++)

  
int main(){
  int n,t,a;
  cin >> n >> t >> a;
  vector<double> h(n);
  vector<double> hdif(n);
  rep(i,n){
    cin >> h.at(i);
  }
  rep(i,n){
    if(t-h.at(i)*0.006>=a) hdif.at(i)=(t-h.at(i)*0.006)-a;
    else if(t-h.at(i)*0.006<a) hdif.at(i)=a-(t-h.at(i)*0.006);
  }  
  double minn=100000000;
  rep(i,n){
    minn=min(minn,hdif.at(i));
  }
  rep(i,n){
    if(hdif.at(i)==minn) cout << i+1 << endl;
  }
}
  

Measured memory_bytes: 256
x = list(map(int, input().split()))
n = x[0]
a = x[1]
b = x[2]
s = input()


count_domestic = 0
count_oversea = 0
judge_list = []
yes = 'Yes'
no = 'No'

for i in range(n):
    candidate = s[i]
    if candidate == 'a':
        if count_domestic + count_oversea < a + b:
            judge_list.append(yes)
            count_domestic += 1
        else:
            judge_list.append(no)
    elif candidate == 'b':
        if count_domestic + count_oversea < a + b and count_oversea < b:
            judge_list.append(yes)
            count_oversea += 1
        else:
            judge_list.append(no)
    else:
        judge_list.append(no)

for j in range(len(judge_list)):
    print(judge_list[j])


Measured memory_bytes: 80044
#include<stdio.h>
#include<algorithm>
int N,T,S,A[3000],B[3000],dp[3001],i,j;
int main()
{
	scanf("%d%d%d",&N,&T,&S);
	for(i=0;i<N;++i)
		scanf("%d%d",A+i,B+i);
	for(i=0;i<N;++i)
	{
		for(j=T-B[i];j>=0;--j)
		{
			if(j<S&&S<j+B[i])continue;
			int &r=dp[j+B[i]];
			r=std::max(r,dp[j]+A[i]);
		}
	}
	printf("%d\n",*std::max_element(dp,dp+T+1));
	return 0;
}

Measured memory_bytes: 0
N,K = map(int,input().split())
A = list(map(int,input().split()))

l = 0
r = max(A)

while r-l != 1:

    m = (l+r)//2

    now = 0
    for i in range(N):
        if A[i] % m == 0:
            now += A[i] // m -1
        else:
            now += A[i] // m

    if now > K:
        l = m
    else:
        r = m

print (r)


Measured memory_bytes: 93856
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 1e5+7;
vector<int> dp(lim,0);


int main(){
    int n;
    cin>>n;
    vector<int> h(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    dp[1]=0;
    dp[2]=abs(h[2]-h[1]);

    for(int i=3;i<=n;i++){
        dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,a[50],ans=0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n-1;i++){
		if(a[i]>a[i-1] && a[i]<a[i+1] || a[i]<a[i-1] && a[i]>a[i+1])
		ans++;
	}
	cout<<ans<<endl;
  return(0);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    char c;
    ll i,n,len;
    cin>>n;
    char s[n];
    cin>>s;
    i=len=0;
    while(s[i]!='\0')
    {
        c=s[i];
        if(s[i]==c&&s[i+1]==c)
        {
            while(s[i]==c)
            {
                i++;
            }
        }
        else
        {
            i++;
        }
        len++;
    }
    cout<<len<<endl;
    return 0;
}


Measured memory_bytes: 384
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
pos = {a[i][j]: (i,j) for i in range(h) for j in range(w)}
acc = [0]*(h*w+1)
for v in range(d+1, h*w+1):
    i, j = pos[v]
    x, y = pos[v-d]
    acc[v] = acc[v-d] + abs(x-i) + abs(y-j)
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(acc[r] - acc[l])

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int64 N, M;
	cin >> N >> M;
	using PIC = pair<int64, char>;
	vector<PIC> cond(M);
	REP(i, M) {
	  cin >> cond[i].fs >> cond[i].sc;
	  cond[i].fs--;
	}
	REP(i, 100000) {
	  string s = to_string(i);
	  if (s.size() != N) continue;
	  bool ok = 1;
	  REP(j, M) {
	    if (s[cond[j].fs] != cond[j].sc) ok = 0;
	  }
	  if (ok) {
	    cout << s << endl;
	    return 0;
	  }
	}
	cout << -1 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int (i) = 0; (i) < (n); i++)
#define ll long long
using namespace std;
int main() {
  ll N = 0,ans = 0;
  cin >> N;
  vector<ll>A(N);
  rep(i,N){
    cin >> A[i];
    ans += A[i];
  }
  sort(A.begin(), A.end()); //小さい順
  bool a = false;
  rep(i,N){
    if(A[i] % 10 != 0){
      a = true;
    }
  }
  if(!a){
    cout << "0";
  }
  else{
    if(ans % 10 != 0){
      cout << ans;
      return 0;
    }
    else{
      rep(i,N){
        if(A[i] % 10 != 0){
          cout << ans - A[i];
          return 0;
        }
      }
    }
  }
}
    

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



int main(){
  
  int N;
  cin>>N;
    
  vector<int> vec(N+1);
  for(int i=1;i<=N;i++){
    cin>>vec.at(i);
  }
  
  int sta=vec.at(1);
  int kai=0;
  bool can=false;
  if(sta==2) cout<<1<<endl;
  else {
    for(int i=1;i<=N;i++){
      kai+=1;
      sta=vec.at(sta);
      if(sta==2){
      can=true;
      break;
      }
    }
    if(can) cout<<kai+1<<endl;
    else cout<<-1<<endl;
  }
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()

int R, C, K;
int arr[3300][3300];
ll dp[3300][3300][4];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> R >> C >> K;
	for (int i = 0; i < K; i++) {
		int a, b, c; cin >> a >> b >> c;
		arr[a][b] = c;
	}

	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			for (int k = 0; k < 4; k++) {
				dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k]);
				if (arr[i][j] == 0) {
					if (k == 0) {
						for (int l = 0; l < 4; l++)
							dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][l]);
					}
				}
				else {
					if (k > 0) dp[i][j][k] = max(dp[i][j][k], arr[i][j] + dp[i][j - 1][k - 1]);
					if (k == 1) {
						for (int l = 0; l < 4; l++)
							dp[i][j][k] = max(dp[i][j][k], arr[i][j] + dp[i - 1][j][l]);
					}
				}
			}

	ll ans = 0;
	for (int i = 0; i < 4; i++) ans = max(ans, dp[R][C][i]);
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 335164
#include <iostream>
#include <stack>
#include <string.h>
using namespace std;

class Node {
    
public:
    
    Node(int key){
        this->key = key;
    }
    
    ~Node(){
        prev = nullptr;
        next = nullptr;
    }
    
    int key = 0;
    Node *prev = nullptr;
    Node *next = nullptr;
    
    static void link(Node* before, Node* after){
        before->next = after;
        after->prev = before;
    }
    
};

class DoublyLinkedList {
    
public:
    
    DoublyLinkedList(){
        nil = new Node(0);
        nil->next = nil;
        nil->prev = nil;
    }
    
    ~DoublyLinkedList(){
        
        while(nil->next != nil){
            removeFirst();
        }
        delete nil;
        
        while (!nodeStock.empty()) {
            Node* n = nodeStock.top();
            nodeStock.pop();
            delete n;
        }
        
    }
    
    Node* search(int key){
        Node* n = nil;
        while(n->next != nil){
            if( n->next->key == key ) return n->next;
            n = n->next;
        }
        return nullptr;
    }
    
    void insert(int key){
        Node* n = getNewNode(key);
        Node::link(n, nil->next);
        Node::link(nil, n);
    }
    
    void remove(int key){
        Node* n = search(key);
        if(n){
            Node::link(n->prev, n->next);
            nodeStock.push(n);
        }
    }
    
    void remove(Node* n){
        if( n == nil ) return;
        Node::link(n->prev, n->next);
        nodeStock.push(n);
    }
    
    void removeFirst(){
        remove(nil->next);
    }
    
    void removeLast(){
        remove(nil->prev);
    }
    
    void print(){
        Node* n = nil;
        bool first = true;
        while(n->next != nil){
            if( !first ){
                cout << " ";
            }else{
                first = false;
            }
            cout << n->next->key;
            n = n->next;
        }
        cout << endl;
    }
    
private:
    Node* nil;
    
    stack<Node*> nodeStock;
    
    Node* getNewNode(int key){
        if(nodeStock.empty()){
            return new Node(key);
        }else{
            Node* n = nodeStock.top();
            nodeStock.pop();
            n->key = key;
            return n;
        }
    }
    
};

int main(int argc, const char * argv[]) {
    
    int n;
    scanf("%d", &n);
    
    DoublyLinkedList* dll = new DoublyLinkedList();
    
    char s[20];
    int key;
    
    for(int i=0; i<n; i++){
        
        scanf("%s", s);
        
        //insert
        if(s[0]=='i'){
            scanf("%d", &key);
            dll->insert(key);
        }else{
            //delete
            if(strlen(s)==6){
                scanf("%d", &key);
                dll->remove(key);
            }else{
                //deleteFirst
                if(s[6]=='F'){
                    dll->removeFirst();
                }else{
                    //deleteLast
                    dll->removeLast();
                }
            }
        }
        
    }
    
    dll->print();
    
    delete dll;
    
    return 0;
}




Measured memory_bytes: 42472
//FIRST THINK THEN CODE.

#include <bits/stdc++.h>
 
 
using namespace std;
 
typedef long long ll;
 
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>b;--i)
#define FOR(i,n)  for(ll i=0;i<n;i++)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define rev(p) reverse(p.begin(),p.end());
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define popcount(x) __builtin_popcountll(x)
#define sz(x) ((ll)x.size())
const ll M=1000000007;
const ll MM=998244353;
ll begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";

 
ll newmod(ll a,ll b)
 {
  return ((a%b)+b)%b;
}
 
 
ll powM(ll a,ll b,ll m )
{ 
  if(a<=0)return 0;
  a%=m;
  if(!b)return 1;
  ll ans=1LL;
  while(b)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }
 
return ans;
}


 
ll poww(ll a,ll b)
{ 
  
  ll ans=1;
  while(b)
  {
    if(b&1)ans=ans*a;
    a=a*a;
    b>>=1;
  }
 
return ans;

}

template<typename T,typename F>
void chmax( T &a,F b){
  if(b>a)a=b;
}

template<typename T,typename F>
void chmin( T &a,F b){
  if(b<a)a=b;
}


const ll N=2e5+5;

 
int main()
{ 

IOS;

ll n;cin>>n;

set<ll>s;

ll val=0;

FOR(i,n){
  ll x;cin>>x;
  s.insert((x)^(x-1));
  val=val^x;
}

ll cnt=0;


if(!val){
  cout<<0<<endl;
return 0;
}

(val);

for(ll i=29;i>=0;i--){
 //ll temp=0;
 ll x=1ll<<i;
 if(x&val){
  ll y=2*x-1;
  if(s.count(y)){
    cnt++;
    val=val^y;
  }
  else {
    cnt=-1;
    break;
  }
 }
}

if(val){
  cnt=-1;
}

d1(cnt);

//end_routine();

return 0;
 
 }

Measured memory_bytes: 3656
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <memory.h>
#include <cassert>

using namespace std;


#define all(c) ((c).begin()), ((c).end())
#define debug(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, a, b) for (int i = (int)(a); i <= (int)(b); i++)

#define mp make_pair
#define fst first
#define snd second
#define pb push_back


const double EPS = 1e-10;


typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef complex<double> P;


int w[1000][1000];
int h[1000][1000];
int dp[1000][1000];
int main() {
	for (int n; cin >> n, n != 0; ) {
		vector<string> m(n);
		rep(i, n) cin >> m[i];
		memset(w, 0, sizeof(w));
		memset(h, 0, sizeof(h));
		rep(i, n) rep(j, n) {
			if (m[i][j] == '.') {
				w[i][j] = 1;
				if (j > 0) w[i][j] += w[i][j - 1];
			}
			if (m[j][i] == '.') {
				h[j][i] = 1;
				if (i > 0) h[j][i] += h[j - 1][i];
			}
		}
		memset(dp, 0, sizeof(dp));
		int ans = 0;
		rep(i, n) {
			if (m[i][0] == '.') dp[i][0] = 1, ans = 1;
			if (m[0][i] == '.') dp[0][i] = 1, ans = 1;
		}
		REP(i, 1, n - 1) REP(j, 1, n - 1) if (m[i][j] == '.') {
			dp[i][j] = min(dp[i - 1][j - 1] + 1, min(w[i][j], h[i][j]));
			ans = max(ans, dp[i][j]);
		}
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 13000
s=gets.chomp
k=gets.chomp.to_i

a=[];
leng = s.length

indx = 0

for i in 0..leng-1 do
  j=0
  while i+j < leng && j <= k-1
    a[indx] = s[i..i+j]
    indx += 1
    j += 1
  end
end

a = a.uniq.sort


puts a[k-1]


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

#define mem(t, v)   memset ((t) , v, sizeof(t))
#define all(x)      x.begin(),x.end()
#define un(x)       x.erase(unique(all(x)), x.end())
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define sl(n)       scanf("%lld", &n)
#define sll(a,b)    scanf("%lld %lld", &a, &b)
#define slll(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
#define D(x)        cerr << #x " = " << (x) << '\n'
#define DBG         cerr << "Hi" << '\n'
#define pb          push_back
#define PI          acos(-1.00)
#define xx          first
#define yy          second
#define eps         1e-9

typedef unsigned long long int ULL;
typedef long long int LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;


inline int setBit(int N, int pos) { return N=N | (1<<pos); }
inline int resetBit(int N, int pos) { return N= N & ~(1<<pos); }
inline bool checkBit(int N, int pos) { return (bool)(N & (1<<pos)); }

//int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};
//int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1}; //Four & Eight Direction

int main()
{
//    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    string a, b;
    cin >> a >> b;
    sort(all(a));
    sort(all(b));
    reverse(all(b));
    if(a < b)
        puts("Yes");
    else
        puts("No");
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <numeric>


using std::cout;
using std::cin;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;


ll gcd(ll a, ll b) {
    while (b != 0) {
        auto tmp = a;
        a = b;
        b = tmp % a;
    }
    return a;
}



void oneCase () {
    int n;
    cin >> n;
    set<int> seen;
    while (n > 0) {
        --n;
        int a;
        cin >> a;
        if (seen.count(a) > 0) {
            cout << "NO" << "\n";
            return;
        }
        seen.insert(a);
    }
    cout << "YES" << "\n";
}




int main() {
    int t = 1;
//    cin >> t;
    while (t > 0) {
        oneCase();
        --t;
    }

    return 0;
}

Measured memory_bytes: 9600
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.IO;
using System.Linq;
using System.Diagnostics;
using System.Globalization;
using static System.Console;
using static System.Math;

namespace abc103_c
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] input = ReadLine().Split().Select(int.Parse).ToArray();

            double sum = 0;

            for(int i=0; i<input.Length; i++){
                sum += input[i]-1;
            }

            WriteLine(sum);
        }
    }
}

Measured memory_bytes: 13268
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>
#include<bitset>
#include<cassert>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long int;

const int inf = 1001001000;
const long long int Inf = 1001001001001001000;



void print(vector<vector<int>> a){
	for (int i = 0; i < a.size(); i++)
	{
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<vector<long long int>> a){
	for (int i=0;i<a.size();i++){
		for (int j=0;j<a[i].size();j++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
}

void print(vector<int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(vector<long long int> a){
    int n = a.size();
    for (int j=0;j<n;j++) {
        if (j != n-1) cout << a[j] << " ";
        else cout << a[j] << endl;
    }
}

void print(set<int> a){
	for (auto x:a)
		cout << x << " ";
	cout << endl;
}

int main()
{
	set<int> a;
	rep(i,3){
		int c;
		cin>>c;
		a.insert(c);
	}
	cout << a.size() << endl;
	

	return 0;
}

Measured memory_bytes: 3632
/// Swift5 -> Swift2.2

extension String {
    // split(separator:maxSplits:omittingEmptySubsequences:)
    func split(separator separator: Character) -> [String] {
        return self.characters.split(separator).map(String.init)
    }
}
extension Array {
    // init(repeating:count:)
    init(repeating: Element, count: Int) {
        self.init(count: count, repeatedValue: repeating)
    }
    // lastIndex(where:)
    func lastIndex(where predicate: (Element) -> Bool) -> Int? {
      	for i in stride(from: count - 1, through: 0, by: -1) {
          	if predicate(self[i]) {
              	return i
            }
        }
      	return nil
    }
}
extension Array where Element: Comparable {
    // sorted()
    func sorted() -> [Element] {
        return self.sort( { $0 < $1 } )
    }
    // max()
    func max() -> Element? {
        guard self.count > 0 else { return nil }
        return self.reduce(self.first!) { return Swift.max($0, $1) }
    }
}
extension String {
    // Sequence#enumerated()
  	// public func enumerate<Seq : SequenceType>(base: Seq) -> EnumerateSequence<Seq>
    func enumerated() -> EnumerateSequence<[Character]> {
        return Array(self.characters).enumerate()
    }
}
// stride(from:through:by:)
func stride(from start: Int, through end: Int, by stride: Int) -> StrideThrough<Int> {
    return start.stride(through: end, by: stride)
}
// stride(from:to:by)
func stride(from start: Int, to end: Int, by stride: Int) -> StrideTo<Int> {
    return start.stride(to: end, by: stride)
}

/// end


let N = Int(readLine()!)!
let W = readLine()!.split(separator: " ").map { Int($0)! }

var s1 = 0
var s2 = W.reduce(0, combine: +)
var result = Int.max
for i in stride(from: 0, to: N, by: 1) {
    s1 += W[i]
    s2 -= W[i]
    result = min(result, abs(s1 - s2))
}

print(result)


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

int main() {
  int n,k;
  cin >> n >> k;
  vector<double> kakuritu(1010);
  vector<double> atai(n);
  for(int i=0;i<n;i++){
    cin >> atai.at(i);//値入力
  }
  int x = *max_element(atai.begin(),atai.end());
  for(int j=1;j<x+1;j++){
    double kakuritu1;
    double sum;
    sum += j;
    kakuritu1 = sum/j;
    kakuritu.at(j-1) = kakuritu1;//各々の期待値をkakurituに収納
  }
  for(int i=0;i<n;i++){
    atai.at(i) = kakuritu.at(atai.at(i)-1);
  }
  double ans = 0;
  for(int i=0;i<k;i++){
    ans += atai.at(i);//先頭からkまでの足し算
  }
  double max1 = ans;
  for(int i=k;i<n;i++){
    ans = ans + atai.at(i) - atai.at(i-k);
    max1 = max(ans,max1);
  }
  cout << setprecision(10) << max1 << endl;
}

Measured memory_bytes: 1792