akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  Int n;
  F f;
  G g;
  T ti;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(Int n_,F f,G g,T ti):
    f(f),g(g),ti(ti){
    init(n_);
  }
  void init(Int n_){
    n=1;
    while(n<n_) n*=2;
    dat.assign(2*n-1,ti);
  }
  void build(Int n_, vector<T> v){
    for(Int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(Int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(Int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  inline T query(Int a,Int b){
    T vl=ti,vr=ti;
    for(Int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[(l++)-1]);
      if(r&1) vr=f(dat[(--r)-1],vr);
    }
    return f(vl,vr);
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  using T = tuple<Int, Int, Int>;
  vector<T> v(n);
  map<T, Int> m;
  for(Int i=0;i<n;i++){
    Int x,y,r;
    cin>>x>>y>>r;
    v[i]=T(x+y,x-y,r);
    m[v[i]]=i;
  }
  
  sort(v.begin(),v.end(),[&](T a,T b){
      Int au,av,ar;
      tie(au,av,ar)=a;
      Int bu,bv,br;
      tie(bu,bv,br)=b;
      return atan2(av,au)<atan2(bv,bu);
    });

  for(Int i=0;i<n;i++) v.emplace_back(T(v[i]));
  for(Int i=0;i<n;i++) v.emplace_back(T(v[i]));

  using P = pair<Int, Int>;
  SegmentTree<P, P>::F f=[&](P a,P b){
    return P(min(a.first,b.first),max(a.second,b.second));};

  Int N=n*3;
  SegmentTree<P, P> seg(N,f,f,P(N,-1));
  for(Int i=0;i<N;i++) seg.update(i,P(i,i));

  auto check=[&](Int a,Int b){
    return max(abs(get<0>(v[a])-get<0>(v[b])),
	       abs(get<1>(v[a])-get<1>(v[b])))<=(get<2>(v[b]));
  };
  
  vector<Int> dp(N,N);
  for(Int i=0;i<N;i++){
    dp[i]=i;
    while(0<dp[i]&&check(dp[i]-1,i)) dp[i]=dp[dp[i]-1];
    seg.update(i,P(dp[i],dp[i]));
  }
  fill(dp.begin(),dp.end(),-1);
  for(Int i=N-1;i>=0;i--){
    dp[i]=i;
    while(dp[i]+1<N&&check(dp[i]+1,i)) dp[i]=dp[dp[i]+1];
    seg.update(i,P(dp[i],dp[i]));
  }
  
  Int flg=1;
  while(flg){
    flg=0;
    for(Int i=0;i<N;i++){
      auto a=seg.query(i,i+1);
      auto b=seg.query(a.first,a.second+1);
      flg|=(a!=b);
      seg.update(i,b);
    }
  }

  vector<Int> ans(n);
  for(Int i=0;i<n;i++){
    Int idx=m[v[i]];
    auto a=seg.query(n+i,n+i+1);
    Int k=(i-a.first+1)+(a.second-i+1)-1;
    ans[idx]=min(k,n);
  }
  
  for(Int i=0;i<n;i++) cout<<n-ans[i]<<endl;
  return 0;
}



Measured memory_bytes: 71832
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
#include <cmath>
#include <vector>
using namespace std;
#define pi M_PI

int main(){
  int n;
  cin >> n;
  
  if(1 <= n && n <= 999){
    cout << "ABC" << endl;
  }
  else if(1000 <= n && n <= 1998){
    cout << "ABD" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
	long N = 0;
	std::cin >> N;

	long ans = 0;
	for (long i = 1; i <= N; ++i)
	{
		if (i % 3 == 0)
		{
			continue;
		}
		else if (i % 5 == 0)
		{
			continue;
		}
        ans += i;
	}

	std::cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>

int main(void){

    int H1,M1,H2,M2,K,minute,ans;

    scanf("%d %d %d %d %d",&H1,&M1,&H2,&M2,&K);

    minute = (H2-H1)*60 + (M2-M1);
    if(minute - K > 0) printf("%d\n",minute-K);
    else printf("0\n");
    return 0;
}

Measured memory_bytes: 1732
times = [int(input()) for _ in range(5)]
fractions = [10 - t % 10 for t in times if t % 10 != 0]
if fractions:
    fraction = max(fractions)
else:
    fraction = 0
print(sum([(t - t % 10) + ((t % 10 + 9) // 10) * 10 for t in times]) - fraction)

Measured memory_bytes: 3060
#include <iostream>
#include <tuple>
#include <vector>
#include <array>

template <typename F>
int calc(int pos, int N, int X, int M, std::array<int, 10> &A, F const &f)
{
    if (pos == N)
    {
        return f(A);
    }
    int max = 0;
    for (int i = X; i <= M; i++)
    {
        A[pos] = i;
        max = std::max(max, calc(pos + 1, N, i, M, A, f));
    }
    return max;
}

int main()
{
    int N, M, Q;
    std::cin >> N >> M >> Q;
    std::vector<std::tuple<int, int, int, int>> constraints(Q);
    for (int i = 0; i < Q; i++)
    {
        std::cin >> std::get<0>(constraints[i]);
        std::cin >> std::get<1>(constraints[i]);
        std::cin >> std::get<2>(constraints[i]);
        std::cin >> std::get<3>(constraints[i]);
    }

    std::array<int, 10> A;
    std::cout << calc(0, N, 1, M, A, [&](std::array<int, 10> const &A) {
        int score = 0;
        for (auto const &constraint : constraints)
        {
            int a = std::get<0>(constraint) - 1;
            int b = std::get<1>(constraint) - 1;
            int c = std::get<2>(constraint);
            if (A[b] - A[a] == c)
            {
                score += std::get<3>(constraint);
            }
        }
        return score;
    }) << std::endl;
}

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

double dp[305][305][305];
double ev[305][305][305];

int main()
{
vector<int>cnt(4,0);
int n;
cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
cnt[x]++;
}
dp[cnt[1]][cnt[2]][cnt[3]]=1;
for(int k=n;k>=0;k--){
    for(int j=n;j>=0;j--){
          for(int i=n;i>=0;i--)  { if(i+j+k>n)continue;
     double p_waste=(double)(n-(i+j+k))/n,evwaste;
if(p_waste==1)continue;
evwaste=1/(1-p_waste);
     ev[i][j][k]+=dp[i][j][k]*evwaste;
     if(i>0){double p_go=((double)(i))/(i+j+k);dp[i-1][j][k]+=dp[i][j][k]*p_go;ev[i-1][j][k]+=ev[i][j][k]*p_go;}
     if(j>0){double p_go=((double)(j))/(i+j+k);dp[i+1][j-1][k]+=dp[i][j][k]*p_go;ev[i+1][j-1][k]+=ev[i][j][k]*p_go;}
     if(k>0){double p_go=((double)(k))/(i+j+k);dp[i][j+1][k-1]+=dp[i][j][k]*p_go;ev[i][j+1][k-1]+=ev[i][j][k]*p_go;}
     }
  }
}
cout<<setprecision(20)<<fixed<<ev[0][0][0];//+cnt[1]+2*cnt[2]+3*cnt[3];
}

Measured memory_bytes: 438528
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

int main() {
  
  set<char> st;
  for(int i = 0; i < 3; i++) {
    char c; cin >> c;
    st.insert(c);
  }
  if(st.size() == 1) cout << "No" << endl;
  else cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <queue>
#include <map>

using namespace std;

int main() {
    
    int n;
    cin >> n;
    vector<long long> a(n);
    long long all = 0;
    long long exceptfirst = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        all += a[i];
        if (i % 2)
        {
            exceptfirst += a[i];
        }
    }
    all /= 2;
    long long current = all - exceptfirst;
    
    for (int i = 0; i < n; ++i)
    {
        if (i == n - 1)
        {
            cout << current * 2;
            break;
        }
        cout << current * 2 << " ";
        current = a[i] - current;
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 2048
n, m = map(int, input().split())
h = list(map(int, input().split()))
delete_list =[]
for i in range(m):
    a, b = map(int, input().split())
    if h[a-1] > h[b-1]:
        delete_list.append(b)
    if h[a-1] == h[b-1]:
        delete_list.append(a)
        delete_list.append(b)
    if h[a-1] < h[b-1] :
        delete_list.append(a)

delete_list = set(delete_list)
print(n - len(delete_list))

Measured memory_bytes: 20180
#include<bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)

using namespace std;
using ll = long long;
ll x[100010];
ll dist[100010];
int main(){ _;
  int n,m;cin>>n>>m;
  REP(i,m)cin>>x[i];
  if(m<=n){
    cout<<0<<endl;
    return 0;
  }
  sort(x,x+m);
  for(int i=0;i<m-1;i++)dist[i]=x[i+1]-x[i];
  sort(dist,dist+m-1);
  cout<<accumulate(dist,dist+m-n,0)<<endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <string>
#include <set>

using namespace std;

int main() {
    int N, Y, x;
    cin >> N >> Y;
    const int max1000 = int(Y/1000);
    for(int z = 0; z <= max1000; z++) {
        for(int y = 0; y <= N-z; y++) {
            x = N - y - z;
            if(x*10000 + y*5000 + z*1000 == Y) {
                cout << x << ' ' << y << ' ' << z << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1";
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>


#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define LOWER(a,x) lower_bound(ALL(a), x) - a.begin() - 1;
#define COUNT(a,x)  upper_bound(ALL(a), x) - lower_bound(ALL(a), x);
#define MCOUNT(a,x,y) upper_bound(ALL(a), y) - lower_bound(ALL(a), x);
#define scan(x) scanf("%lld",&x);
#define inf 5555555555555555555
#define mod 1000000007
#define pi 3.14159265358979323846
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef map<ll, ll> MAP;
typedef set<ll> SET;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0, ma = 0, mi = 0;
string s;
bool flag, ok;
ll dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };
#pragma endregion
#define MAX 111111


int main(void) {
  cin >> n >> m;

  ans += min(n, m / 2);
  m -= ans * 2;
  ans += m / 4;
  cout << ans << endl;

  return 0;
}

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

using namespace std;

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

//#define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
  #define db(x) cerr << #x << " == " << x << endl
  #define dbs(x) cerr << x << endl
  #define _ << ", " <<
#else
  #define db(x) ((void)0)
  #define dbs(x) ((void)0)
#endif

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define cl(x, v) memset((x), (v), sizeof(x))
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
#define MOD 1000000007LL
#define endl '\n'
#define mdc(a, b) (__gcd((a), (b)))
#define mmc(a, b) (( (a)/__gcd((a), (b)) )*(b))

ll memo[100010][2];
vector<int> adj[100010];

ll dp(int u, int l, bool is_black){
	
	if(memo[u][is_black] != -1LL)
		return memo[u][is_black];

	ll case1 = 1LL, case2=1LL;
	
	for(int v: adj[u]){
		if(v == l)
			continue;
			
		if(is_black){
			case1 = (case1 * dp(v, u, false))%MOD;
		}else{
			case1 = (case1 * dp(v, u, false) )%MOD;
			case2 = (case2 * dp(v, u, true) )%MOD;			
		}
	}
	
	if(is_black)
		memo[u][is_black] = case1;
	else
		memo[u][is_black] = (case1 + case2)%MOD;
		
	return memo[u][is_black] ;
}

int main() {	
	memset(memo, -1, sizeof(memo));
	cin.sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;

	for(int i=1; i<n; i++){
		int a, b;
		cin >> a >> b;
		
		adj[a].PB(b);
		adj[b].PB(a);		
	}
	
	cout << dp(1, 0, false) << endl;

	return 0;	
}


Measured memory_bytes: 15616
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define MOD 1000000007
const int INF = 1LL<<30;

long long fac[100010], finv[100010], inv[100010];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < 100010; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}


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

    if(abs(n-m)>=2){
        cout<<0<<endl;
        return 0;
    }
    COMinit();
    if(n+1==m || m+1==n){
        ll ans=(fac[n]*fac[m])%MOD;
        cout<<ans<<endl;
        return 0;
    }
    ll ans=(fac[n]*fac[m])%MOD;
    //cout<<ans<<endl;
    ans=(ans*2)%MOD;
    cout<<ans<<endl;
}

Measured memory_bytes: 5980
n = int(input())
p = list(map(int, input().split()))

for i in range(n):
    p[i] -= 1

ans = 0
for i in range(n-1):
    if p[i] == i:
        ans += 1
        p[i], p[i+1] = p[i+1], p[i]

if p[n-1] == n-1:
    ans += 1
print(ans)


Measured memory_bytes: 20660
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,K = LI()
L,R = LIR(K,2)

LR = [(L[i],R[i]) for i in range(K)]
LR.sort(key=lambda x:x[0])

L = [LR[i][0] for i in range(K)]
R = [LR[i][1] for i in range(K)]

S = [0]*K

dp = [0]*N
dp[0] = 1
for i in range(N):
    for k in range(K):
        if i > R[k]:
            S[k] += dp[i-L[k]] - dp[i-R[k]-1]
            S[k] %= mod
        elif i < L[k]:
            S[k] += 0
        else:
            S[k] += dp[i-L[k]]
            S[k] %= mod
        dp[i] += S[k]
        dp[i] %= mod


print(dp[-1])

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

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

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

#define MAX 100005
#define INF 1001001001

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

  int m; cin >> m;
  vector<int> b(m);
  rep(i,m) cin >> b[i];

  vector<int> ans;
  set_intersection(a.begin(), a.end(),
  b.begin(), b.end(),
  inserter(ans, ans.end()));

  for (auto a : ans) cout << a << endl;

  return 0;
}



Measured memory_bytes: 4848
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6, mod = 1e9 + 7, inv3 = (mod + 1) / 3;
int n, f[maxn + 10][3], in;
int fac[maxn + 10], ifac[maxn + 10], inv[maxn + 10], ans;

void init() {
	f[0][0] = fac[0] = ifac[0] = 1;
	for (int i = 1; i <= maxn; ++i) {
		for (int j = 0; j < 3; ++j)
			for (int k = 0; k < 3; ++k)
				if (j != k) (f[i][j] += f[i - 1][k]) %= mod;
		fac[i] = 1ll * fac[i - 1] * i % mod;
		inv[i] = i == 1 ? 1 : mod - 1ll * (mod / i) * inv[mod % i] % mod;
		ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;
	}
}

int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = 1ll * ans * x % mod;
		y >>= 1; x = 1ll * x * x % mod;
	}
	return ans;
}

int comb(int x, int y) {
	return 1ll * fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}

int main() {
	init();
	scanf("%d", &n);
	in = fpow(fpow(3, n - 1), mod - 2);
	for (int i = 1; i <= n; ++i) {
		int pi = 1ll * comb(n, i) * f[i][1] % mod * in % mod;
		int si = 1ll * inv[i] * inv[n] % mod * inv3 % mod;
		(ans += 1ll * pi * si % mod) %= mod;
	}
	printf("%d", ans);
}


Measured memory_bytes: 23680
#include <bits/stdc++.h>
typedef long long int LL;
typedef unsigned long long int ULL;
using namespace std;

// 插入此處

LL a[300005];

LL lsum[100005], rsum[100005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < 3 * n; i++) {
        cin >> a[i];
    }
    LL sum = 0;
    priority_queue<int, vector<int>, greater<int>> lq;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        lq.push(a[i]);
    }
    lsum[0] = sum;
    for (int i = n; i < 2 * n; i++) {
        sum += a[i];
        lq.push(a[i]);
        sum -= lq.top();
        lsum[i + 1 - n] = sum;
        lq.pop();
    }
    sum = 0;
    priority_queue<int> rq;
    for (int i = 2 * n; i < 3 * n; i++) {
        sum += a[i];
        rq.push(a[i]);
    }
    rsum[0] = sum;
    for (int i = 2 * n - 1; i >= n; i--) {
        sum += a[i];
        rq.push(a[i]);
        sum -= rq.top();
        rsum[2 * n - i] = sum;
        rq.pop();
    }
    LL ans = lsum[0] - rsum[n];
    for (int i = 1; i <= n; i++) {
        ans = max(ans, lsum[i] - rsum[n - i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000
int x[MAXN+5], n, k, id;
int main()
{
	int l=1, r, tmp, ans=INT_MAX;
	scanf("%d%d", &n, &k);
	for(int i=1; i<=n; i++)
		scanf("%d", &x[i]);
	r = k;
	for(; r<=n; l++, r++)
	{
		if(x[l] < 0 && x[r] >= 0)
			ans = min(ans, x[r]-x[l]+min(abs(x[l]), x[r]));
		else if(x[l]<0 && x[r]<0)
			ans = min(ans, -x[l]);
		else
			ans = min(ans, x[r]);
	}
	cout<<ans;
}

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

int main(int argc, char *argv[])
{
    int n;
    cin >> n;

    vector<int> v;
    int buff;
    for (int i = 0; i < n; i++)
    {
        cin >> buff;
        v.push_back(buff);
    }

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

    for (int i : v)
    {
        cout << i;
        if (i != v.back())
        {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
using namespace std;
const int INF = 1001001001;
typedef long long int ll;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define re0 return 0

int npr(int n , int r){//nPr
    r = n - r;
    int sum = 1;
    int i;
    for (i=n;i>=r+1;i--)sum*=i;
    return sum;
}
int gcd(int a, int b) {//最大公約数
    if (b==0) return a;
    else return gcd(b, a%b);
}
int lcm(int a, int b) {//最小公倍数
    return a * b / gcd(a, b);
}
int digsum(int n) {//桁和
    int res = 0;
    while(n > 0) {
        //res += n%10;
        //　↑をres++;にすれば桁数
         res++;
        n /= 10;
    }
    return res;
}
bool isPrime(int x){//素数
    if(x==1)return 0;
    if(x==2)return 1;
    if(x%2==0)return 0;
    for(int i=3;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}
/*bit全探索
for (int bit = 0; bit < (1<<N); ++bit) {
}
if (bit & (1 << i)) {
}
*/


signed main(){ 
    int k;
    string s;
    cin >> k >> s;
    int n = s.length();

    if(n<=k){
        cout << s << endl;
    }else{
        string str = s.substr(0,k);
        cout << str+"..." <<endl;
    }
    re0;
}


Measured memory_bytes: 3640
<?php
 fscanf(STDIN,"%d",$n);
 $C = trim(fgets(STDIN));
 $r_count = 0;
 for($i=0;$i<$n;$i++){
   if($C[$i]=='R'){
     $r_count++;
   }
 }
 $w_count = $n-$r_count;
 $result = 0;
 for($i=0;$i<$r_count;$i++){
   if($C[$i]=='W'){
     $result++;
   }
 }
 echo $result;



Measured memory_bytes: 16436
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <cmath>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;
  int mini = inf;
  int maxi = -1;
  for(int i = 0; i < n; i++){
    int a;
    cin >> a;
    mini = min(mini, a);
    maxi = max(maxi, a);
  }
  cout << maxi - mini << endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
h = list(map(int,input().split()))
inf = float("inf")
dp = [0]*(N+1)
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(1,N-1):
    dp[i+1] = min(dp[i]+abs(h[i+1]-h[i]),dp[i-1]+abs(h[i+1]-h[i-1]))

print(dp[N-1])

Measured memory_bytes: 13928
MOD = 10**9 + 7
N = int(input())
S = input()
S2 = input()
check = []
flg = False
for i in range(N-1):
    if flg:
        check.append(2)
        flg = False
        continue
    if S[i] == S[i+1]:
        flg = True
    else:
        check.append(1)
if flg:
    check.append(2)
else:
    check.append(1)
ans = 3 if check[0] == 1 else 6
for i in range(1,len(check)):
    if check[i-1] == 1:
        ans *= 2
    elif check[i] == 2 and check[i-1] == 2:
        ans *= 3
print(ans%MOD)

Measured memory_bytes: 38256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) ((int)(x).size())
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

const int K=26;
int a[K],b[K];

signed main()
{
    REP(i,K) a[i]=b[i]=-1;
    
    string s,t; cin>>s>>t;
    bool ok=true;
    REP(i,SZ(s)){
        int x=s[i]-'a';
        int y=t[i]-'a';

        if(a[x]==-1) a[x]=y;
        else ok&=(a[x]==y);

        if(b[y]==-1) b[y]=x;
        else ok&=(b[y]==x);
    }
    cout<<(ok? "Yes":"No")<<endl;
}


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

int main() {
    cin>>code;

    int c0 = 0, c1 = 0;
    for(int i=0;i<code.length();i++) {
        if(code[i] == '0') c0++;
        else c1++;
    }
    cout<<2*min(c0, c1)<<"\n";
    return 0;
}

Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
int main(void)
{
	int a,b,c;
	cin >> a >> b >> c;
	if(a==1 && b==0 && c==0) cout << "Close" << endl;
	else if(a==0 && b==1 && c==0) cout << "Close" << endl;
	else if(a==1 && b==1 && c==0) cout << "Open" << endl;
	else if(a==0 && b==0 && c==1) cout << "Open" << endl;
	else cout << "Close" << endl;
	exit(0);
}

Measured memory_bytes: 1156
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <utility>
#include <set>
using namespace std;
typedef long long LL;
const int MaxN = 1e5;

LL n, p;
LL a[55];
LL odd;
LL even;
LL qwr(LL x, LL y)
{
	LL res = 1LL;
	while(y > 0)
	{
		if(y & 1) res = res * x;
		x = x * x;
		y = y >> 1;
	}
	return res;
}
int main()
{
	while(scanf("%lld %lld", &n, &p) != EOF)
	{
		odd = 0, even = 0;
		for(int i = 1; i <= n; i++)
		{
			scanf("%lld", &a[i]);
			if(a[i] & 1LL) odd++;
			else even++;
		}
		LL ans = 0;
		LL tmp = 0;
		if(p == 1)
		{
			tmp = qwr(2, odd) / 2;
		}
		else if(p == 0)
		{
			tmp = qwr(2, odd) / 2;
			if(odd == 0) tmp = 1;
		}
		ans = tmp * qwr(2, even);
		printf("%lld\n", ans);

		memset(a, 0, sizeof(a));
	}
	return 0;
}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
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;}

int X;int V[4];
int Y,Z;
int T[55],E[55];

double dp[55][5010];

signed main(){
    while(cin>>X>>Y>>Z,X||Y||Z){
        memset(T,0,sizeof(T));
        memset(dp,0,sizeof(dp));
        rep(i,X)cin>>V[i];
        rep(i,Z){
            int a;cin>>a;
            cin>>T[a]>>E[a];
        }

        double ans=0;

        dp[0][0]=1;
        rep(i,Y){
            for(int j=Y-1;j>=i;j--){
                rep(k,i*100+1){
                    rep(l,X){
                        int t=j+V[l];
                        int c=k;
                        chmin(t,Y);
                        if(T[t]==1){
                            t+=E[t];
                            chmin(t,Y);
                        }
                        else if(T[t]==2){
                            c+=E[t];
                        }
                        else if(T[t]==3){
                            c-=E[t];
                            if(c<0)c=0;
                        }
                        dp[t][c]+=dp[j][k]/X;
                    }
                    dp[j][k]=0;
                }
            }
        }
        rep(i,5000+1)ans+=dp[Y][i]*i;
        printf("%lld\n",(int)ans);
    }
    return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;
const ll INF=-10000000000;

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*(y/gcd(x,y));
}

//a,b x
int main(){
	ll X,Y; cin>>X>>Y;
	ll cnt=0;
	while(X<=Y){
		X*=2;
		cnt++;
	}
	cout<<cnt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c; cin >> a >> b >> c;
  if (a==b && a==c) cout << "No" << endl;
  else if (a != b && b!= c && c != a) cout << "No" << endl;
  else cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;

#define BIG_NUM 2000000000

using namespace std;

int N;

void func(){

	int minimum = BIG_NUM,num_a,num_b,num_c,tmp;

	for(int a = 0; a <= N; a += 200){
		for(int b = 0; b <= N; b += 300){
			if(a+b > N)break;
			for(int c = 0; c <= N; c += 500){
				if(a+b+c > N)break;

				if(a+b+c == N){
					num_a = a/200;
					num_b = b/300;
					num_c = c/500;
					tmp = 380*(num_a%5)+550*(num_b%4)+850*(num_c%3)+304*(num_a - num_a%5)+1870*(num_b-num_b%4)/4+748*(num_c-num_c%3);
					minimum = min(minimum,tmp);
				}
			}
		}
	}
	printf("%d\n",minimum);

}

int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 2552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100010];
ll sum[100010];
vector<ll> sum1;
vector<ll> sum2;
int n;
bool ok(int num, int x) {
  ll aa = a[n - num * 2 + 1];
  //int bb = a[n - num - 1];
  //int cc = a[n - num * 2 - 1];
  ll dd = a[n - num];
  return (ll)x - aa <= dd - (ll)x;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  int q;
  cin >> q;
  sum1.push_back(0LL);
  sum2.push_back(0LL);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (i & 1) {
      sum2.push_back(a[i]);
    } else {
      sum1.push_back(a[i]);
    }
  }
  for (int i = 1; i <= n; i++) {
    sum[i] = a[i - 1];
    sum[i] += sum[i - 1];
  }
  for (int i = 1; i < sum1.size(); i++) {
    sum1[i] += sum1[i - 1];
  }
  for (int i = 1; i < sum2.size(); i++) {
    sum2[i] += sum2[i - 1];
  }

  int aoki = n / 2, taka = n - aoki;
  while (q--) {
    int x;
    cin >> x;
    ll midr = a[aoki];
    if (x <= midr && midr - x >= x - a[0]) {
      cout << sum[n] - sum[aoki] << endl;
      continue;
    }
    int ret = 0;
    for (int i = 20; i >= 0; i--) {
      if ((ret + (1 << i)) * 2 > n) continue;
      ll left = a[n - (ret + (1 << i)) * 2];
      ll right = a[n - (ret + (1 << i))];
      if (x < left) {ret += (1 << i); continue;}
      if (x > right) continue;
      if (ok(ret + (1 << i), x)) ret += (1 << i);
    }
    ll ans = 0;
    ans += sum[n] - sum[n - ret];
    //cout << "ret " << ret << endl;
    //cout << "a " << ans << endl;
    int k = n - ret * 2;
    k /= 2;
    if (n & 1) k++;
    if (n & 1) ans += sum1[k];
    else ans += sum2[k];
    cout << ans <<endl;
  }
  return 0;
}


Measured memory_bytes: 4340
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n)
{
    for (int i = 2; i < n; i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    int x;
    cin>>x;
    while(1)
    {
        if(isPrime(x))
        {
            cout<<x;
            break;
        }
        else x++;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000000;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

//gcd,lcm,べき,二進展開
//組み合わせ、mod計算
//最短路問題、bit、union find

///////////////////////////



int main() {
	ll N, K, S;
	cin >> N >> K >> S;

	if (S == 1000000000) {
		repn(i, K) { cout << S << " "; }
		repn(i, N - K) {
			cout << 1;
			if (i != N - K) { cout << " "; }
		}
	}

	else {
		repn(i, K) { cout << S << " "; }
		repn(i, N - K) {
			cout << S+1;
			if (i != N - K) { cout << " "; }
		}
	}

	system("PAUSE");

}


Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  string s;
  cin >> s;
  if (s.size() >= 4) {
    if (s.substr(0, 4) == "YAKI") {
      cout << "Yes\n";
      return 0;
    }
  }
  cout << "No\n";
  return 0;
}


Measured memory_bytes: 256
#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;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> oset;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using ll = long long;
#define ar array 

const int nax = 1e6+5;
set<int> prime;
bool vis[nax] , vis2[nax];

void build(){
	for(int i = 2 ; i < nax ; i++){
		if(!vis[i]){
			prime.insert(i);
			for(int j = i ; j < nax ; j+=i)
				vis[j] = 1;
		}
	}
}

void test_case() {
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> c(nax);
	for(int i = 0 ; i < n ; i++){
		cin >> a[i];
		c[a[i]]++;
	}
	bool pairwise = true;
	for(int i = 2 ; i < nax ; i++) {
		int cnt = 0;
		for(int j = i ; j < nax ; j+=i){
			cnt+=c[j];
		}
		if(cnt > 1){
			pairwise = false;
		}
	}
	if(pairwise){
		cout<<"pairwise coprime\n";
		return;
	}
	int g = 0;
	for(int i = 0 ; i < n ; i++)
		g = __gcd(g,a[i]);
	if(g == 1){
		cout<<"setwise coprime\n";
		return;
	}
	cout<<"not coprime\n";	
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//build();
	//cout<<prime.size();
	int T = 1;
	//~ cin >> T;
	while(T--){
		test_case();
	}
}

// problem is easy but implement is hard for you broooo
// improveeeeeeeeeeeeeeeeee
// read carefully
// we have to check for every two pair of element in array...
 


Measured memory_bytes: 11072
# from math import factorial,sqrt,ceil
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix

# strlist = "abcdefghijklmnopqrstuvwxyz"
a,b,c = map(int,input().split())
ans = min(b//a,c)

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


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

int main() {
	char c;
	scanf("%c", &c);

	if (c == 'a' || c == 'i' ||
		c == 'u' || c == 'e' ||
		c == 'o')
		cout << "vowel" << endl;
	else
		cout << "consonant" << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a,c=0;
    cin>>a;
    if(a%10>0)
    {
        c++;
    }
    a=a/10;
    if(a%10>0)
        c++;
    a=a/10;
    if(a>0)
        c++;
    cout<<c;
    return 0;
}


Measured memory_bytes: 3616
#include <iostream>

int main(int argc, char const* argv[])
{
	int H, W;
    while(true) {
		std::cin >> H >> W;
		if (H == 0 && W == 0) break;
		for (int h = 0; h < H; h++) {
			for (int w = 0; w < W; w++) {
                if (h == 0 || h == H-1 || w == 0 || w == W-1) {
					std::cout << "#";
				} else {
					std::cout << ".";
				}
			}
			std::cout << std::endl;
		}
		std::cout << std::endl;
	}
	return 0;
}



Measured memory_bytes: 3088
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
typedef vector<int> vec;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int n,A,B,pc[10000010];
vec ans;
vec solve(int S,int x){
	assert(pc[x]&1);
	assert((S&x)==x);
	if (pc[S]==1){
		assert((x==S));
		vec v;
		v.clear();
		v.pb(0);
		v.pb(S);
		return v;
	}
	int t=-1;
	FOR(i,0,n-1) if ((x>>i)&1) t=i;
	assert((t!=-1));
	if (pc[x]>=3){
		int tt;
		FOR(j,0,n-1){
			if (!((S>>j)&1)) continue;
			if (t==j) continue;
			if ((x>>j)&1) tt=j;
		}
		vec A=solve(S^(1<<t),(1<<tt));
		vec B=solve(S^(1<<t),x^(1<<t)^(1<<tt));
		vec ans=A;
		int tmp=ans[SZ(A)-1]^(1<<t);
		FOR(i,0,SZ(B)-1) ans.pb(B[i]^tmp);
		return ans;
	}
	else{
		int tt;
		FOR(j,0,n-1){
			if (!((S>>j)&1)) continue;
			if (t==j) continue;
			tt=j;
		}
		vec A=solve(S^(1<<t),(1<<tt));
		vec B=solve(S^(1<<t),(1<<tt));
		vec ans=A;
		int tmp=ans[SZ(A)-1]^(1<<t);
		FOR(i,0,SZ(B)-1) ans.pb(B[i]^tmp);
		return ans;
	}
}
int main(){
	cin>>n>>A>>B;
	FOR(i,1,(1<<n)-1) pc[i]=pc[i>>1]+(i&1);
	B^=A;
	if (pc[B]%2==0) return puts("NO"),0;
	ans=solve((1<<n)-1,B);
	puts("YES");
	FOR(i,0,SZ(ans)-1) printf("%d ",ans[i]^A);
	return 0;
}

Measured memory_bytes: 2144
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    S = input()
    L = len(S)
    d = defaultdict(list)

    i = 0
    for s in S:
        d[s].append(i)
        i += 1

    ans = INF

    for indexs in d.values():
        last = -1
        result = 0
        for i in indexs:
            tmp = i - last - 1
            result = max(result, tmp)
            last = i
        result = max(result,L-last-1)
        ans = min(ans, result)

    if ans == 0:
        ans = '0 '
        print(ans)
    else:
        print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 65040
import Control.Monad  -- unless

balanced :: String -> Bool
balanced s = balanced' fs []
  where
    fs = filter (`elem` "()[]") s
    balanced' [] stack = stack == []
    balanced' (x:xs) stack
      | x `elem` "(["                  = balanced' xs ((closing x):stack)
      | stack /= [] && x == head stack = balanced' xs (tail stack)
      | otherwise                      = False
    closing '(' = ')'
    closing '[' = ']'

main :: IO ()
main = do
  s <- getLine
  unless (s == ".") $ do
    putStrLn . yesno . balanced $ s
    main  
  where
    yesno b = if b then "yes" else "no"

Measured memory_bytes: 4044
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<vector>
#include<bitset>
#include<cmath>
#define FOR(i,a,b) for(int i=(a); i<int(b); ++i)
#define RFOR(i,a,b) for(int i=(b)-1; i>=int(a); --i)
#define rep(i,n) FOR(i,0,n)
#define rep1(i,n) FOR(i,1,int(n)+1)
#define rrep(i, n) RFOR(i, 0, n)
#define rrep1(i, n) RFOR(i, 1, int(n) + 1)
#define all(c) begin(c), end(c)
#define al(d) d.begin(),d.end()
#define fill(n) std::setfill('0')<<std::right<<std::setw(n)
template <typename T>
using vec = std::vector<T>;
using vi = vec<int>;
using vvi = vec<vi>;
using pii = std::pair<int, int>;
using ll = long long;
using ld = long double;
using namespace std;
const int MOD = 1000000007;

template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}
template <class T>
vector<T> getv(int n){
	vector<T> vec;
	rep(i,n){
		T input;
		cin >> input;
		vec.emplace_back(input);
	}
	return vec;
}

using AdjList = vector<vector<int>>;
using Weight = int;
using Flow = int;
struct Edge {
	int src, dst;
	Weight weight;
	Flow cap;
	Edge() : src(0), dst(0), weight(0) {}
	Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;
void add_edge(Graph &g, int a, int b, Weight w = 1) {
	g[a].emplace_back(a, b, w);
	g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }
// Recieve edge(=(int,int)) as an adj list.
AdjList getadj(int N, int M){
	// Initialize all lists of the graph as a empty vector.
	vector<int> init;
	vector<vector<int>> graph(N,init);
	rep(i,M){
		int a, b;
		cin >> a >> b;
		graph[a-1].emplace_back(b-1);
		graph[b-1].emplace_back(a-1);
	}
rep(i,N){
	cout << i<< ": ";
	putv(graph[i]);
}
 
	return graph;
}
void out(bool ans){
	if(ans == true) cout << "yes" << endl;
	else cout << "no" << endl;
}
void Out(bool ans){
	if(ans == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}
void OUT(bool ans){
	if(ans == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}
ll gcd(const ll a, const ll b){
	return (b==0) ? a : gcd(b,a%b);
}
ll lcm(const ll a, const ll b){
	return a*(b/gcd(a,b));
}
ll Manhattan_dist(ll x1, ll y1, ll x2, ll y2){
	return abs(x1-x2) + abs(y1-y2);
}
// nをpで何回割れるか
ll hmt_p_divide_n(ll p, ll n){
	ll s = 0;
	while(n%p == 0){
		n /= p;
		s++;
	}
	return s;
}
int digit(ll n){
	int cntr = 0;
	while(n>0){
		n/=10;
		cntr++;
	}
	return cntr;
}


int main(){
	char b;
	cin >> b;

	// A-T, C-G
	if(b=='A') cout << 'T' << endl;
	if(b=='T') cout << 'A' << endl;
	if(b=='G') cout << 'C' << endl;
	if(b=='C') cout << 'G' << endl;
}



Measured memory_bytes: 256
#

import sys
from bisect import bisect_left, bisect_right
input=sys.stdin.readline

def main():
    N=int(input())
    #slash backslash tate yoko
    ds=[[] for i in range(400001)] #i=y-x+200000 el=x
    rs=[[] for i in range(400001)]
    us=[[] for i in range(400001)]
    ls=[[] for i in range(400001)]
    db=[[] for i in range(400001)] #i=y+x el=x
    rb=[[] for i in range(400001)]
    ub=[[] for i in range(400001)]
    lb=[[] for i in range(400001)]
    dy=[[] for i in range(200001)] #i=x el=y
    uy=[[] for i in range(200001)]
    rx=[[] for i in range(200001)] #i=y el=x
    lx=[[] for i in range(200001)]
    
    sliset=set()
    bsiset=set()
    xset=set()
    yset=set()
    for i in range(N):
        x,y,u=input().split()
        x=int(x)
        y=int(y)
        sli=y-x+200000
        bsi=y+x
        sliset.add(sli)
        bsiset.add(bsi)
        if u=="U":
            us[sli].append(x)
            ub[bsi].append(x)
            uy[x].append(y)
            xset.add(x)
        elif u=="R":
            rs[sli].append(x)
            rb[bsi].append(x)
            rx[y].append(x)
            yset.add(y)
        elif u=="D":
            ds[sli].append(x)
            db[bsi].append(x)
            dy[x].append(y)
            xset.add(x)
        else:
            ls[sli].append(x)
            lb[bsi].append(x)
            lx[y].append(x)
            yset.add(y)
    for i in range(400001):
        ds[i].sort()
        rs[i].sort()
        us[i].sort()
        ls[i].sort()
        db[i].sort()
        rb[i].sort()
        ub[i].sort()
        lb[i].sort()
    for i in range(200001):
        dy[i].sort()
        uy[i].sort()
        rx[i].sort()
        lx[i].sort()
        
    mint=2*10**8
    for sli in sliset:
        for x in us[sli]:
            usi=bisect_left(ls[sli],x)
            if len(ls[sli])>0 and usi<len(ls[sli]):
                mint=min(mint, (ls[sli][usi]-x)*10)
        for x in rs[sli]:
            rsi=bisect_left(ds[sli],x)
            if len(ds[sli])>0 and rsi<len(ds[sli]):
                mint=min(mint, (ds[sli][rsi]-x)*10)
    for bsi in bsiset:
        for x in ub[bsi]:
            ubi=bisect_right(rb[bsi],x)
            if len(rb[bsi])>0 and ubi>0:
                mint=min(mint, (x-rb[bsi][ubi-1])*10)
        for x in db[bsi]:
            dbi=bisect_left(lb[bsi],x)
            if len(lb[bsi])>0 and dbi<len(lb[bsi]):
                mint=min(mint, (lb[bsi][dbi]-x)*10)
    for y in yset:
        for x in rx[y]:
            rxi=bisect_left(lx[y],x)
            if len(lx[y])>0 and rxi<len(lx[y]):
                mint=min(mint, (lx[y][rxi]-x)*5)
    for x in xset:
        for y in uy[x]:
            uyi=bisect_left(dy[x],y)
            if len(dy[x])>0 and uyi<len(dy[x]):
                mint=min(mint, (dy[x][uyi]-y)*5)

    if mint >= 2*10**8:
        print("SAFE")
    else:
        print(mint)
                
                
    
    
    
if __name__=="__main__":
    main()


Measured memory_bytes: 309516
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define N 105
using namespace std;

int n, sz, x[N], y[N];
double PI = acos(-1.0);
double b[N];
int main()
{
	int i, j;
	cin >> n;
	for (i = 0; i < n; i++) {
		scanf ("%d %d", &x[i], &y[i]);
	}
	for (i = 0; i < n; i++) {
		sz = 0;
		for (j = 0; j < n; j++) {
			if (j == i) continue;
			b[sz++] = atan2((double)(y[j] - y[i]), (double)(x[j] - x[i]));
//			cout << b[j] << endl;
		}
		sort(b, b + sz);
		b[sz] = b[0] + 2 * PI;
		for (j = 1; j <= sz; j++) {
			if (b[j] - b[j - 1] > PI) break;
		}
		if (j <= sz) printf("%.10f\n", (double)(b[j] - b[j - 1] - PI) / (2 * PI));
		else printf("0.0000000000\n");
	}
    return 0;
}


Measured memory_bytes: 640
def f(n, m):
    s = list(input().split())
    t = list(input().split())
    dp = [[1] * (m + 1) for _ in range(n + 1)]
    for i, sk in enumerate(s):
        dpi1 = dp[i + 1] = dp[i][:]
        cs = 0
        for j, tk in enumerate(t):
            if sk == tk:
                cs = (cs + dp[i][j]) % md
            dpi1[j + 1] = (dpi1[j + 1] + cs) % md
#    for x in dp:
#        print(*x)
    print(dp[-1][-1])

md = 10 ** 9 + 7
n, m = map(int, input().split())
f(n, m)


Measured memory_bytes: 159684
#include <iostream>
	#include <fstream>
	#include <string>
	#include <vector>
	#include <map>
	#include <unordered_map>
	#include <list>
	#include <set>
	#include <algorithm>
	#include <queue>
	#include <iterator>
	#include <functional>
	#include <numeric>
	#include <cmath>
	#include <stack>
	#include <limits>
	#include <ctime>

	using namespace std;

	#define ll long long
	#define sc(n) static_cast<ll>(n)
	#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int main() {
		IO;
	#ifdef _DEBUG
		ifstream cin("In.txt");
	#endif	
		ll n, m, s, c;
		cin >> n >> m;
		string st(n, 'x');
		for (size_t i = 0; i < m; i++) {
			cin >> s >> c;
			s--;
			if (st[s] != 'x' && st[s] != ('0' + c)) {
				cout << -1 << endl;
				return 0;
			}
			st[s] = ('0' + c);
		}
		if (st[0] == '0' && n>1) {
			cout << -1 << endl;
			return 0;
		}
		if (st[0] == 'x')
			st[0] = n==1 ? '0':'1';

		for (auto& i : st) {
			if (i == 'x')
				i = '0';
		}
		cout << st << endl;
		return 0;
	}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;


typedef long long i64;
const i64 inf = (i64)1.05e18;


int main()
{
	int n;
	vector<pair<i64,pair<int,int>>> hp;

	scanf("%d", &n);
	hp.resize(n);
	for(int i = 0; i < n; ++i) {
		int h, p;
		scanf("%d%d", &h, &p);
		hp[i] = {(i64)h + p, {h, p}};
	}
	sort(hp.begin(), hp.end());

	vector<vector<i64>> dp(n + 1);
	for(auto& x : dp)
	 	x.resize(n + 1, inf);

	dp[0][0] = 0;

	for(int pos = 0; pos < n; ++pos) {

		vector<i64>& cur = dp[pos + 1];
		vector<i64>& prev = dp[pos];

		for(int sat = 0; sat <= pos + 1; ++sat) {

			i64& v = cur[sat];
			i64 h = hp[pos].second.first;
			i64 p = hp[pos].second.second;

			v = prev[sat];

			if(sat > 0) {

				i64 prev_futon = prev[sat - 1];
				if(prev_futon <= h)
					v = min(v, prev_futon + p);
			}

			//printf("%d %d -> %lld\n", pos, sat, v);
		}
	}

	int sat = 0;
	for(int i = 0; i <= n; ++i) {
		if(dp[n][i] < inf)
			sat = i;
	}

	printf("%d\n", sat);

	return 0;
}

/* waffle */


Measured memory_bytes: 195840
#include<bits/stdc++.h>
using namespace std;
#define con continue
#define bk break
#define LL long long
#define db double
#define pt cout<<'\n'
#define ms(a, b) memset((a), (b), sizeof(a))
#define mp make_pair
#define endl '\n'
int inf=2147483647;const long long ll =9223372036854775807,ninf=1000000000;const double eps = 1e-6; const long long nll =1000000000000000000;
#define sz size()
#define len(X) strlen(X)
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ULL unsigned long long
#define de cout<<"test"<<endl;
#define st system("pause");
#define F first
#define S second
class SlimeXSlimesCity
{
    public:
int merge(vector <int> population)
{

}
};
int f[305][305]={};
int num[305][305]={};
int main()
{
    int a;
    while(cin>>a){
        int no=0;
        for(int i=0;i<a;i++){
            for(int j=0;j<a;j++){
                cin>>f[i][j];
            }
        }
        for(int k=0;k<a;k++){
            for(int i=0;i<a;i++){
                for(int j=0;j<a;j++){
                    if(k!=j&&i!=k&&f[i][k]+f[k][j]<f[i][j]){
                        no=1;
                    }
                     if(k!=j&&i!=k&&f[i][k]+f[k][j]==f[i][j]){
                        num[i][j]=1;
                    }
                }
            }
        }
        if(no){
            cout<<-1<<endl;
            con;
        }
        LL ans=0;
            for(int i=0;i<a;i++){
                for(int j=i+1;j<a;j++){
              if(!num[i][j])
                ans+=f[i][j];
                }
            }
        cout<<ans<<endl;
    }

    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <tuple>
#include <cmath>
using namespace std;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;

int main(){
    int a,b;
    cin>>a>>b;
    a+=b;
    a%=24;
    cout<<a<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int k, s;
  int ans=0;

  scanf("%d %d", &k, &s);

  for (int x=0; x <= k; x++) {
    for (int y=0; y <= k; y++) {
      int z = s - x - y;
      if (z >= 0 && z <= k) {ans++;}
    }
  }


  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>
#include <cstdio>
#include <stdio.h>

typedef long long ll;

using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    cout << n/3;
}


Measured memory_bytes: 256