akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;cin>>n;
  vector<VI> cost(n,vector<int>(n));
  for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>cost[i][j];
  ll res=0;
  for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)res+=min(cost[i][j],cost[j][i]);
  cout<<res<<endl;
}

Measured memory_bytes: 3264
function pointsOfStamina(p, x)
   local points = 0
   for i = 1, #x do
      points = points + (x[i] - p)^2
   end
   return points
end


local n = io.read("*n")
local x = {}

for i = 1, n do
   x[i] = io.read("*n")
end

local min = {coordinate=1, points=pointsOfStamina(1, x)}
for i = 2, 100 do
   local points = pointsOfStamina(i, x)
   if points < min.points then
      min.coordinate = i
      min.points = points
   end
end

print(string.format("%d", min.points))


Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		while(true){ 
			if(n == 0)break;
			System.out.println(min(n));
			n = sc.nextInt();
		}   
	}   
	static int min(int n){
		int min = Integer.MAX_VALUE;
		for(int c = n/500 ; c >= 0 ; c--){
			for(int b = (n-c*500)/300 ; b >= 0 ; b--){
				if((n-c*500-b*300)%200 == 0){ 
					int a = (n-c*500-b*300)/200;
					int cost = cost(a, b, c); 
					if(cost < min){
						min = cost;
					}   
				}   
			}   
		}   
		return min;
	}   
	static int cost(int a, int b, int c){
		return (a%5)*380+(a/5)*5*380*8/10+(b%4)*550+(b/4)*4*550*85/100+(c%3)*850+(c/3)*3*850*88/100;
	}   
}

Measured memory_bytes: 25800
#include <bits/stdc++.h>
#define ll long long
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define PI 2 * acos(0)
#define ones(n) __builtin_popcount(n)
#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX 9000000
#define debug(x) cerr << #x << " = " << x << '\n';
#define LOOP printf("LOOP!!")
#define READ freopen("input.txt", "r", stdin)
#define PRINT freopen("output.txt", "w", stdout);
#define print(a, b) printf("Case %d: %lld\n", a, b)
#define all(x) (x).begin(), (x).end()
const ll MOD = 1e9 + 7;
using namespace std;
const int VAL = 20000000;
bool isprime[VAL + 10];

///prime storage>>
vector<ll> prime;
void primes()
{

    for (int i = 0; i <= VAL; i++)
        isprime[i] = true;

    for (int i = 3; i * i <= VAL; i++)
    {
        if (isprime[i])
        {

            for (int j = i * i; j <= VAL; j += i)
                isprime[j] = false;
        }
    }
    prime.push_back(2);
    for (int i = 3; i <= VAL; i += 2)
        if (isprime[i])
            prime.push_back(i);
}

/************MAIN_FUNCTION**********/
int main(int argc, char *argv[])
{

    string s = "ACL";

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cout << s;

    cout << '\n';

    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <map>
#include <cstdio>
#include <vector>
using namespace std;

int dfs(int p, int q, int a, int n, int t){
  if(!p) return 1;
  if(p < 0 || n == 0) return 0;
  int ret = 0;
  for(int i = t; i <= a; ++i){
    if(p*i-n*q > 0) break;
    if(p*i-q < 0) continue;
    ret += dfs((p*i-q),(q*i),a/i,n-1,i);
  }
  return ret;
}

signed main(){
  int p, q, a, n;
  while(cin >> p >> q >> a >> n, p)
    cout << dfs(p,q,a,n,1) << endl;
  return 0;
}



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define forx(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;


int main()
{
    string s,t="AC";
    cin >> s;
    if(s[0]!='A')
        t = "WA";
    int c = 0;

    forx(i,2,s.size()-1){
        if(s[i]=='C')
            c++;
        else if(s[i]<='Z')
            t = "WA";
    }

    if (s[1] <= 'Z')
        t = "WA";
    if (s[s.size()-1] <= 'Z')
        t = "WA";

    if(c!=1)
        t = "WA";
    cout << t << endl;
    return 0;
}

Measured memory_bytes: 256
icase=0
if icase==0:
    n=int(input())
    p=list(map(int,input().split()))
    icnt=0
    pi=[0]*3
    for i in range(1,n-1):
        pi=[p[i+1],p[i],p[i-1]]
        if p[i]==sum(pi)-min(pi)-max(pi):
            icnt+=1
    print(icnt)

Measured memory_bytes: 3064
h, w = list(map(int, input().split()))  #サイズ読み取り
power = [list(map(int, input().split())) for i in range(10)]  #魔力読み取り

for i in range(10):
    for j in range(10):
        for k in range(10):
            power[j][k] = min(power[j][i] + power[i][k], power[j][k])  # 三重ループで各数間の最小魔力を求める。

ans = 0
for i in range(h):
    wall = list(map(int, input().split()))  # 壁読み取り
    for item in wall:
        if item < 0:
            continue
        ans += power[item][1]  # それぞれの壁に使う魔力を求める
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include<limits.h>
#include<iomanip>
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define RALL(v) v.rbegin(),v.rend()
#define check(v) rep(i,v.size()) cout << v[i] << " ";\
cout << endl
#define INF 1e8
typedef long long ll;
using namespace std;
//オーバーフローに気をつけろよおおおおおお
//確認忘れるなよおおおおおお

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m; cin >> n >> m;
    priority_queue<int> q;
    rep(i,n) {
        int num; cin >> num;
        q.push(num);
    }
    rep(i,m) {
        int val = q.top(); q.pop();
        val/=2;
        q.push(val);
    }
    ll ans = 0;
    rep(i,n) {
        int a = q.top(); q.pop();
        ans += a;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 892
#include <bits/stdc++.h>
#define rep(i,n) for (ll i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
#define FORV(i, v) for (auto i = v.begin(); i != v.end(); i++)
using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const int INF = 1001001001;
const long long INFL = (1LL<<60);
const double eps = (1e-9);

int main() {
  int n;
  cin >> n;
  vector<ll> a(n);

  rep(i, n) cin >> a[i];
  rep(i, n) {
    if (a[i] > i) {
      cout << -1 << endl;
      return 0;
    }
    if (i > 0 && a[i-1] + 1 < a[i]) {
      cout << -1 << endl;
      return 0;
    }
  }

  int last_idx = -1;
  ll ans = 0;
  for (int i = n-1; i >= 0; i--) {
    if (a[i] == 0) continue;
    if (last_idx == i - a[i]) continue;
    last_idx = i - a[i];
    ans += a[i];
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define rep(i,x,n) for(int i=x;i<n;i++)
using ll=long long;

int main(){
    int n;cin>>n;
    int x[n],a[n];
    rep(i,0,n){
        cin>>x[i];
        a[i]=x[i];
    }
    sort(a,a+n);
    int med1=a[n/2-1];
    int med2=a[n/2];

    rep(i,0,n){
        if(x[i]<=med1) cout<<med2<<endl;
        else cout<<med1<<endl;
    }
}

Measured memory_bytes: 3712
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x1,x2,x3,x4,y1,y2,y3,y4;
		x1 = sc.nextInt(); y1 = sc.nextInt();
		x2 = sc.nextInt(); y2 = sc.nextInt();
		System.out.println();
		int X = x2 - x1;
		int Y = y2 - y1;
		if(Y < 0) {
			x4 = x1 - Y;
			y4 = y1 + X;
			x3 = x2 - Y;
			y3 = y2 + X;
		}else {
			Y = Y * (-1);
			x4 = x1 + Y;
			y4 = y1 + X;
			x3 = x2 + Y;
			y3 = y2 + X;
		}
		/*System.out.print(x1+" "); System.out.println(y1);
		System.out.print(x2+" "); System.out.println(y2);*/
		System.out.print(x3+" "); System.out.print(y3+" ");
		System.out.print(x4+" "); System.out.println(y4);
		
	}
}

Measured memory_bytes: 21844
#include "bits/stdc++.h"

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
//逆から塗っていくことを考える
//ある頂点を塗る必要がない＝ある頂点はすでにある深さ(半径)だけ他の色で塗られている
vector<vector<pi > > G;
//ある頂点に対してある深さで色を塗られているか
//ある深さで塗られていればそれ以上深い
vector<vector<bool > > filled;
//今までに参照したかどうか
vector<bool > seen;
vector<ll > ans;
vector<ll > V;
vector<ll > D;
vector<ll > C;

ll N, M, Q;
//ll d;
ll c;

void dfs(ll idx , ll depth = 0, ll from = -1){

    if(filled[idx][depth] == true){
        return;
    }

    if(ans[idx] == 0){
        ans[idx] = c;
    }

    //見た
    //seen[idx] = true;
    filled[idx][depth] = true;

    if(depth == 0) return;

    for(ll i = 0; i < G[idx].size(); i++){
        //次の行き先は？
        ll to = G[idx][i].first;
        //探査済み
        //if(seen[to] == true) continue;
        if(filled[to][depth - 1] == true) continue;

        dfs(to , depth - 1 ,idx);
    }

    return;
}

int main(){
    cin >> N >> M;
    //初期化
    G.assign(N, vector<pi >());
    filled.assign(N, vector<bool >(11, false));
    ans.assign(N, 0);
 
    //グラフ入力
    for(ll i = 0; i < M; i++){
        ll u, v, w;
        w = 0;
        cin >> u >> v;
        u--;
        v--;
        //双方向に貼りましょうね
        G[u].push_back(make_pair(v, w));
        G[v].push_back(make_pair(u, w));
    }

    //クエリ入力
    cin >> Q;
    V.assign(Q, 0);
    D.assign(Q, 0);
    C.assign(Q, 0);

    for(ll i = 0; i < Q; i++){
        cin >> V[i] >> D[i] >> C[i];
        V[i]--;
    }

    //後ろから塗っていく
    for(ll i = Q - 1; i >= 0; i--){
        seen.assign(N, false);
        //d = D[i];
        c = C[i];

        dfs(V[i], D[i]);
    }

    for(ll i = 0; i < ans.size(); i++){
        cout << ans[i] << endl;
    }
    
}

Measured memory_bytes: 18432
#include"cstdio"
int main(){
	int i,j,sum1,sum2,n;
	char a[105];
	while(~scanf("%d",&n)){
		sum1=0;sum2=0; 
		scanf("%s",a);
		for(i=0;i<n;i++){
			if(a[i]=='R')
			sum1++;
			if(a[i]=='B')
			sum2++;
		}
		if(sum1>sum2){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		}
	}
	return 0;
} 

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define ll int64_t
#define _GLIBCXX_DEBUG
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
//約数列挙(√N)
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}
//素因数分解(√N)
map< int64_t, int > prime_factor(int64_t n) {
  map< int64_t, int > ret;
  for(int64_t i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}
//素数テーブル(NloglogN)
vector< bool > prime_table(int n) {
  vector< bool > prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}
//二項係数(K)
template< typename T >
T binomial(int64_t N, int64_t K) {
  if(K < 0 || N < K) return 0;
  T ret = 1;
  for(T i = 1; i <= K; ++i) {
    ret *= N--;
    ret /= i;
  }
  return ret;
}
//二項係数テーブル(N^2)
template< typename T >
vector< vector< T > > binomial_table(int N) {
  vector< vector< T > > mat(N + 1, vector< T >(N + 1));
  for(int i = 0; i <= N; i++) {
    for(int j = 0; j <= i; j++) {
      if(j == 0 || j == i) mat[i][j] = 1;
      else mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j];
    }
  }
  return mat;
}

int main(){
  int n,m;
  cin >> n>>m;
  if(n==m){
    ll ans=1;
    rep(i,n){
      ans*=(i+1);
      ans%=1000000007;
    }
    cout << (2*ans*ans)%1000000007 << endl;
  }
  else if(n==m+1){
    ll ans=1;
    rep(i,m){
      ans*=(i+1);
      ans%=1000000007;
    }
    ans=ans*ans;
    ans%=1000000007;
    ans*=n;
    ans%=1000000007;
    cout << ans << endl;
  }
  else if(m==n+1){
    ll ans=1;
    rep(i,n){
      ans*=(i+1);
      ans%=1000000007;
    }
    ans=ans*ans;
    ans%=1000000007;
    ans*=m;
    ans%=1000000007;
    cout << ans << endl;
  }
  else
    cout << 0 << endl;
}

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

using namespace std;

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

  int N; cin>>N;
  vector<vector<int>> table(N, vector<int>(N-1));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N-1; j++) {
      int t; cin>>t;
      t--;
      table[i][j] = t;
    }
  }
  vector<int> is(N, 0);
  unordered_set<int> cands;
  auto check = [&](int x) {
    if (is[x] < N-1) {
      int o = table[x][is[x]];
      if (is[o] < N-1 and table[o][is[o]] == x) {
        cands.insert(x);
        cands.insert(o);
      }
    }
  };
  for (int i = 0; i < N; i++) {
    check(i);
  }
  int d = 0;
  while (not cands.empty()) {
    vector<bool> played(N, false);
    for (auto i : cands) {
      int o = table[i][is[i]];
      if (not played[i] and not played[o]) {
        played[i] = played[o] = true;
        ++is[i];
        ++is[o];
      }
    }
    auto ncands = cands;
    cands.clear();
    for (auto c : ncands)
      check(c);
    d++;
  }
  bool suc = true;
  for (int i = 0; i < N; i++) {
    suc &= is[i] == N-1;
  }
  cout << (suc ? d : -1) << endl;

  return 0;
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
//#include <atcoder/all>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define popcount __builtin_popcount
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
template <class T>
inline bool chmin(T &a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}

ll gcd(ll n, ll m)
{
	ll tmp;
	while (m != 0)
	{
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m)
{
	return abs(n) / gcd(n, m) * abs(m); //gl=xy
}

using namespace std;
//using namespace atcoder;

void solve(){
	string s;
	cin>>s;
	if(s.back()!='s')s+='s';
	else s+="es";
	cout<<s;	
}


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


Measured memory_bytes: 3624
#include<stdio.h>
int main(){
  long long n,a[100002],b[100002],sum=0;
  scanf("%lld",&n);
  for(int i=1;i<=n+1;i++){
  	scanf("%lld",&a[i]);
    sum+=a[i];
  }
  for(int i=1;i<=n;i++){
  	scanf("%lld",&b[i]);
    if((b[i]-a[i])>0){
      	a[i+1]-=b[i]-a[i];
      	if(a[i+1]<0){
          a[i+1]=0;
        }
      	a[i]=0;
    }
    else{
    	a[i]=a[i]-b[i];
    }
  }
  for(int j=1;j<=n+1;j++){
  	sum-=a[j];
  }
  printf("%lld",sum);
  return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

int main() {
    ll N;
    ll mod = 1000000007;
    cin >> N;

    ll ans = 1;
    FOR(i, 1, N){
        ans = (ans*i) % mod;
    }
    ans = ans%mod;
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    private static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    private static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] t = new long[n];
        for (int i = 0; i < n; i++) {
            t[i] = sc.nextLong();
        }

        long result = 1L;
        for (int i = 0; i < n; i++) {
            result = lcm(result, t[i]);
        }
        System.out.println(result);
    }

}


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

using namespace std;

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

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}
class UnionFind {
    vector<int> par, h;
public:
    UnionFind(int size) {
        par.assign(size, 0);
        h.assign(size, 0);
        REP(i, size) par[i] = i;
    }
    void unite(int u, int v) {
        u = root(u), v = root(v);
        if (u == v) return;
        if (h[u] > h[v]) {
            par[v] = u;
        }
        else if (h[u] < h[v]) {
            par[u] = v;
        }
        else {
            ++h[u];
            par[v] = u;
        }
    }
    bool isUnited(int u, int v) {
        return root(u) == root(v);
    }
    int root(int v) {
        if (par[v] == v) return v;
        return par[v] = root(par[v]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, h, w; cin >> n >> w >> h;
    vector<ll> X(n), Y(n);
    rep(i, n) {
		cin >> X[i] >> Y[i];
		--X[i], --Y[i];
	}
	vector<vector<ll>> g1(h), g2(w);
	rep(i, n) {
		g1[Y[i]].pb(i);
		g2[X[i]].pb(i);
	}
	UnionFind uf(n);
	rep(i, h) {
		rep(j, 1, g1[i].size()) {
			uf.unite(g1[i][j-1], g1[i][j]);
		}
	}
	rep(i, w) {
		rep(j, 1, g2[i].size()) {
			uf.unite(g2[i][j-1], g2[i][j]);
		}
	}
	set<ll> s;
	rep(i, n) s.insert(uf.root(i));
	ll ans = linf;
	if (s.size() == 1) {
		ans = n-1;
	}
	else {
		ans = n + s.size() - 1;
		set<ll> sl, sr, su, sd;
		rep(i, n) {
			ll id = uf.root(i);
			if (X[i] == 0) sl.insert(id);
			if (X[i] == w-1) sr.insert(id);
			if (Y[i] == 0) su.insert(id);
			if (Y[i] == h-1) sd.insert(id);
		}
		ans -= max(max(sl.size(), sr.size()), max(su.size(), sd.size()));
	}
	cout << ans << endl;
}

Measured memory_bytes: 11828
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;
#define MAX_N 100010

using P = pair<int, int>;
#define fi first
#define se second

int n, taka, aoki;
vector<P> G[100010];

// 各点への最短経路 dijkstra
int ad[MAX_N], td[MAX_N];  //頂点kから各点への距離
void dijkstra(int k, int *d) { //Gは隣接行列 G[i][j].firstが距離, secondが向かう頂点名, kはスタートする頂点
    fill(d, d+n, MAX_N); d[k] = 0;
    priority_queue< P, vector<P>, greater<P> > que;
    que.push(P(0, k));
    while (!que.empty()) {
        P p = que.top(); que.pop();
        int now = p.second;
        if (d[now] < p.first) continue;
        for (auto g:G[now]) {
            int to = g.second;
            long newd = g.first + d[now];
            if (d[to] > newd) {
                d[to] = newd;
                que.push(P(d[to], to));
            }
        }
    }
}

bool under[MAX_N] = {0}, visited[MAX_N] = {0};

void dfs(int tr, int i=aoki) {
    visited[i] = true;
    if (i == tr) under[i] = true;
    for (auto &g:G[i]) {
        if (visited[g.se]) continue;
        if (under[i]) under[g.se] = true;
        dfs(tr, g.se);
    }
}


int main() {
    cin >> n >> taka >> aoki;
    taka--; aoki--;
    for (int i=0, a, b; i<n-1; i++) {
        cin >> a >> b;
        a--; b--;
        G[a].push_back({1, b});
        G[b].push_back({1, a});
    }
    dijkstra(aoki, ad);
    dijkstra(taka, td);
    int ans = 0, tr = -1;
    for (int i=0; i<n; i++) {
        if (td[i] + ad[i] == ad[taka] && ad[i] == (ad[taka] + 2) / 2) {
            tr = i;
            break;
        }
    }
    cerr << tr << '\n';
    dfs(tr);
    for (int i=0; i<n; i++) {
        cerr << i << ' ' << under[i] << ' ' << ad[i] << '\n';
        if (under[i]) ans = max(ans, ad[i]);
    }
    cout << ans - 1 << '\n';
    return 0;
}

Measured memory_bytes: 10752
import java.util.Arrays; 
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	
	public static int[][] move_dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	
	public static boolean is_ok(int x, int y, int h, int w){
		if(x < 0 || x >= w || y < 0 || y >= h){
			return false;
		}else{
			return true;
		}
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		final int H = sc.nextInt();
		final int W = sc.nextInt();
		final int N = sc.nextInt();
		
		boolean[][][] is_visited = new boolean[H][W][N + 1];
		boolean[] get_ans = new boolean[N + 1];
		
		boolean[][] is_wall = new boolean[H][W];
		
		int[] x_pos = new int[N + 1];
		int[] y_pos = new int[N + 1];
		
		for(int i = 0; i < H; i++){
			char[] input = sc.next().toCharArray();
			
			for(int j = 0; j < W; j++){
				if(input[j] == 'S'){
					x_pos[0] = j;
					y_pos[0] = i;
				}else if('0' <= input[j] && input[j] <= '9'){
					x_pos[input[j] - '0'] = j;
					y_pos[input[j] - '0'] = i;
				}
				
				if(input[j] == 'X'){
					is_wall[i][j] = true;
				}
				
			}
		}
		
		LinkedList<Integer> x_queue = new LinkedList<Integer>();
		LinkedList<Integer> y_queue = new LinkedList<Integer>();
		LinkedList<Integer> n_queue = new LinkedList<Integer>();
		LinkedList<Integer> t_queue = new LinkedList<Integer>();
		
		x_queue.add(x_pos[0]);
		y_queue.add(y_pos[0]);
		n_queue.add(0);
		t_queue.add(0);
		
		while(!x_queue.isEmpty()){
			final int x = x_queue.poll();
			final int y = y_queue.poll();
			final int n = n_queue.poll();
			final int t = t_queue.poll();
			
			//System.out.println(x + " " + y + " " + n + " " + t);
			
			if(n >= N){
				System.out.println(t);
				break;
			}
			
			if(get_ans[n]){
				continue;
			}else if(is_visited[y][x][n]){
				continue;
			}else{
				is_visited[y][x][n] = true;
			}
			
			if(x_pos[n + 1] == x && y_pos[n + 1] == y){
				x_queue.add(x);
				y_queue.add(y);
				n_queue.add(n + 1);
				t_queue.add(t);
				
				get_ans[n] = true;
				
				continue;
			}
			
			for(int[] move : move_dir){
				final int nx = x + move[0];
				final int ny = y + move[1];
				
				if(!is_ok(nx, ny, H, W)){
					continue;
				}else if(is_wall[ny][nx]){
					continue;
				}else if(is_visited[ny][nx][n]){
					continue;
				}else if(get_ans[n]){
					continue;
				}else{
					x_queue.add(nx);
					y_queue.add(ny);
					n_queue.add(n);
					t_queue.add(t + 1);
				}
			}
			
 		}
		
	}
}

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

using namespace std;

int main() {
    int k,n;

    cin >> k >> n;
    int v[n], d[n];


    for (int i=0; i<n; i++) {
        cin >> v[i];
        if (i>0){
            d[i-1]=v[i]-v[i-1];
        }
    }

    d[n-1] =  k + v[0] - v[n-1];

    sort(d,d+n);

    cout << k - d[n-1] << endl;
    return 0;
}

Measured memory_bytes: 1792
# ABC096D - Five, Five Everywhere
def get_primes(n: int) -> list:
    # return a list of primes < n
    sieve = [1] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i :: 2 * i] = [0] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def main():
    N = int(input())
    primes = get_primes(1400)
    ans = []
    for p in primes:
        if p % 5 == 1:
            ans.append(p)
            if len(ans) == N:
                break
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ld long double
const int M = 1e9+7;

vector<int> a,b;
vector<int> ord;
vector<int> lf,ri;
stack<int> s;

int32_t main(){
	int a,b;
	cin>>a>>b;
	cout << a*b/__gcd(a,b) << endl;
	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 std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int k, s;
	cin>>k>>s;
	ll ans = 0;
	for(int i = 0; i <= k; i++)
	{
		for(int j = 0; j <= k; j++)
		{
			int z = s-i-j;
			if(z>=0&&z<=k) ans++;
		}
	}
	cout<<ans<<'\n';
}


Measured memory_bytes: 384
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int main(){
  int N;
  cin>>N;
  long long A[200000],B[200001];
  for(int i=0;i<N;i++){
    cin>>A[i];
    B[i+1]=0;
  }
  for(int i=0;i<N;i++){
    B[A[i]]++;
  }
  long long answer=0;
  for(int i=1;i<=N;i++){
    answer+=(B[i]*(B[i]-1))/2;
  }
  for(int i=0;i<N;i++){
    cout<<answer-B[A[i]]+1<<endl;
  }
  
 return 0; 
}

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

using int64 = long long;
const int64 kMod = 1000000007;

int64 pow(int64 a, int64 e) {
  int64 ret = 1;
  for (; e; e >>= 1) {
    if (e & 1)
      ret = ret * a % kMod;
    a = a * a % kMod;
  }
  return ret;
}

int main() {
  int64 n, k;
  cin >> n >> k;
  vector<int64> dp(k + 1);
  
  for (int64 x = k; x > 0; --x) {
    int64 tmp = pow(k / x, n);
    for (int64 xk = x + x; xk <= k; xk += x) {
      tmp -= dp[xk];
      if (tmp < 0)
        tmp += kMod;
    }
    dp[x] = tmp;
  }
  int64 sum = 0;
  for (int64 i = 1; i <= k; ++i) {
    sum = (sum + dp[i] * i) % kMod;
  }
  cout << sum << "\n";

  return 0;
}



Measured memory_bytes: 3620
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<cstdio>
#include<cctype>
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

  ll N;
  ll money = 1000;

  cin >> N;

  while(N > money) money = money + 1000;

  cout << money - N << endl;

  return 0;

}   


Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <deque>

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

using namespace std;

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

	s.insert(s.begin()+4, ' ');
	cout << s << endl;


	return 0;
}

Measured memory_bytes: 256
class FK:
    def __init__(self,n):
        self.table=[[0]*n for i in range(n)]
        self.n=n
    
    def add(self,x,y,f):
        self.table[x][y]=f
        
    def ford(self,s,t,f):
        self.visit[s]=True
        if s==t:
            return f
        for i in range(self.n):
            if (not self.visit[i]) and self.table[s][i]>0:
                df=self.ford(i,t,min(f,self.table[s][i]))
                if df>0:
                    self.table[s][i]-=df
                    self.table[i][s]+=df
                    return df
        return 0
    
    def flow(self,s,t):
        ans=0
        inf=10**20
        while True:
            self.visit=[False]*(self.n)
            df=self.ford(s,t,inf)
            if df==0:
                break
            ans+=df
        return ans

N=int(input())
P=[int(i) for i in input().split()]
inf=10**20
maxflow=FK(N+2)
for i in range(1,N+1):
    if P[i-1]>0:
        maxflow.add(i,N+1,P[i-1])
    else:
        maxflow.add(0,i,-P[i-1])
    for j in range(2*i,N+1,i):
        maxflow.add(i,j,inf)
ans=maxflow.flow(0,N+1)
num=sum([p for p in P if p>0])
print(num-ans)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long lint;
using namespace std;

int main(){
  int n;
  cin>>n;
  vector<char>s(n),t(n);
  rep(i,n)cin>>s.at(i);
  rep(i,n)cin>>t.at(i);
  rep(i,n)cout<<s.at(i)<<t.at(i);
  cout<<endl;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>

using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;

const LL inf=1LL<<60;
const int L=1e6;
vector<P> W[2][L];
LL buf1[2][L];
int main() {
	int n,m,s,t;
	cin >> n >> m >> s >> t;
	s--;t--;
	for(int i=0;i<m;i++){
		int u,v,a,b;
		cin >> u >> v >> a >> b;
		u--;v--;
		W[0][u].push_back(P(v,a));
		W[0][v].push_back(P(u,a));
		W[1][u].push_back(P(v,b));
		W[1][v].push_back(P(u,b));
	}
	for(int k=0;k<2;k++){
		auto dist=buf1[k];
		for(int i=0;i<n;i++){
			dist[i]=inf;
		}
		dist[s]=0;
		priority_queue<P,vector<P>,greater<P> > pq;
		pq.push(P(0,s));
		auto w=W[k];
		while(pq.size()){
			P t=pq.top();
			pq.pop();
			if(dist[t.second]<t.first){
				continue;
			}
			for(auto p:w[t.second]){
				LL d=t.first+p.second;
				LL q=p.first;
				if(d<dist[q]){
					dist[q]=d;
					pq.push(P(d,q));
				}
			}
		}
		swap(s,t);
	}
	LL init=1;
	for(int i=0;i<15;i++){
		init*=10;
	}
	//cerr << buf1[0][0] << ", " << buf1[1][0] << endl;
	{
		priority_queue<P,vector<P>,greater<P> > pq;
		for(int i=0;i<n;i++){
			pq.push(P(buf1[0][i]+buf1[1][i],i));
		}
		for(int i=0;i<n;i++){
			while(pq.top().second<i){
				pq.pop();
			}
			cout << init-pq.top().first << endl;
		}
	}

	return 0;
}



Measured memory_bytes: 66724
#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;

#define ll long long

int main(){
	int a,b,c,d;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	int flag = 0;
	if(a > c){
		if( c + d >= a){
			cout<<"Yes\n";
			flag = 1;
		}
		else if(c<b&&b<a){
			if(b +d >=a && c + d>=b){
				cout<<"Yes\n";
				flag = 1;
			} 
		}else {
			cout<<"No\n";
			flag = 1;
		}
	}else{
		if(a + d>=c) {
			cout<<"Yes\n";
			flag = 1;	
		}
		else if(a<b&&b<c){
			if(b+d>=c&&a+d>=b){
				cout<<"Yes\n";
				flag = 1;
			}
		}
	}
	if(!flag)cout<<"No\n";
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cassert>

using ll = long long;
const int maxn = 1e5+7;

ll n, m, v, p, a[maxn], pre[maxn];

bool gao(ll x) {
	ll posl = std::lower_bound(a+1, a+1+n, x)-(a);
	ll posr = std::upper_bound(a+1, a+1+n, x+m)-(a);
//	std::cout << x << ' ' << x+m << ' ' << posl << ' ' << a[posl] << ' ' << posr << ' ' << a[posr] << '\n';
	assert(posl > 0);
	assert(posr <= n+1);
	posr = std::min(posr, n-p+2);
	posl = std::min(posl, n-p+2);
	if (x+m < a[n-p+1]) {
		return false;
	}
	ll ans = (posl-1)*m+(p-1)*m;
	ans += (x+m)*(posr-posl)-(pre[posr-1]-pre[posl-1]);
//	std::cout << (posl-1+1)*m << ' ' << (p-1)*m << ' ' << (x+m)*(posr-posl) << ' ' << (pre[posr-1]-pre[posl-1]) << ' ';
//	std::cout << ans << ' ' << v*m << '\n';
//	std::cout << "----------\n";
	return ans >= (v*m);
}

int main(int argc, char *argv[]) {  
	std::ios::sync_with_stdio(false);
	std::cin.tie(0); 
	std::cin >> n >> m >> v >> p;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	std::sort(a+1, a+n+1);
	pre[0] = 0;
	for (int i = 1; i <= n; i++) {
		pre[i] = a[i] + pre[i-1];
	}
//	for (int i = 1; i <= n; i++) {
//		std::cerr << a[i] << " \n"[i==n];
//	}
//	std::cout << "----------\n";
	int res = 0;
	for (int i = 1; i <= n; i++) {
		if (gao(a[i])) {
			res++;
		}
	}
	std::cout << res << '\n';
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

//下降させていくのか、1オリジンに注意
void max_heapify(vector<int>& v,int h,int i){
  int l=2*i;int r=2*i+1;
  //左、自分、右でキーが最大のものを選ぶ
  int b;
  if(l<=h and v[l]>v[i]){b=l;}else{b=i;}
  if(r<=h and v[r]>v[b]){b=r;}
  if(b!=i){
    int k=v[i];v[i]=v[b];v[b]=k;
    max_heapify(v,h,b);
  }
}

void make_maxheap(vector<int>& v,int h){
  for(int i=floor(h/2);i>0;i--){
    max_heapify(v,h,i);
  }
}


int main(){
  int H;cin >>H;
  vector<int> v(H+1);//1オリジン
  for(int i=1;i<=H;i++){cin >> v[i];}
  make_maxheap(v,H);
  for(int i=1;i<=H;i++){
    cout <<  " " << v[i];
  }
  cout << endl;
}



Measured memory_bytes: 4544
/**
 *      purpose : AGC 9 A
 *      author  : kyomukyomupurin
 *      created : 2018-11-05 19:10:14
**/

#include <bits/stdc++.h>
using namespace std;
#define int64 long long
#define print(x) cout << (x) << '\n'

inline int64 minadd(int64 a, int64 b){
    if (a % b == 0) return 0;
    else return (b - a % b);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin >> N;
    int64 A[N] = {}; int64 B[N] = {};
    for (int i = 0; i < N; ++i){
        cin >> A[i] >> B[i];
    }

    int64 cnt = 0;
    cnt += minadd(A[N - 1], B[N - 1]);

    for (int i = N - 2; i >= 0; --i){
        A[i] += cnt;
        cnt += minadd(A[i], B[i]);
    }
    print(cnt);
    
    return 0;
}

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

#define ris   return *this
#define tmplt template<class T
#define dbgo  debug& operator<<
tmplt > struct rge { T b, e; };
tmplt > rge<T> range(T i, T j) { return rge<T>{i, j}; }
struct debug {
#ifdef LOCAL
~debug(){cerr<<endl;}
tmplt > dbgo(T x){cerr<<boolalpha<<x;ris;}
tmplt, class C > dbgo(pair<T, C> x){ris<<"("<<x.first<<", "<<x.second<<")";}
tmplt > dbgo(rge<T> x){*this<<"[";for(auto it=x.b;it!=x.e;it++){*this<<", "+2*(it==x.b)<<*it;}ris<<"]";}
tmplt > dbgo(vector<T> x){ris<<range(x.begin(),x.end());}
#else
tmplt > dbgo(const T&){ris;}
#endif
};
#define nav(...) << "[ " << #__VA_ARGS__ ": " << (__VA_ARGS__) << " ] "
using ll = long long;

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define ford(i, n) for(int i = n-1; i >= 0; i--) 

template<typename T> 
void min_self(T& a, T b) { 
    a = min(a, b); 
}
template<typename T>
void max_self(T& a, T b) { 
    a = max(a, b); 
}

int divide_stupid(int a, int b) {
    return (a+b-1)/b;
}

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

    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    forn(i, n) cin >> arr[i];
    
    int ans = 1;
    n -= k;
    while(n > 0) {
        ans++;
        n -= k - 1;
    }
    cout << ans << endl;
}













// Don't worry, you're getting better

// Read statement carefully
// Solve on paper first!
// Make your infinity big enough
// Overflows (long long)

// Author: blondie


Measured memory_bytes: 640
n,*s=open(0)
a=b=c=d=0
for t in s:
    if t[-2]=='A'and t[0]=='B':
        d+=1
    elif t[-2]=='A':
        a+=1
    elif t[0]=='B':
        b+=1
    c+=t.count('AB')
if all(i==0for i in(a,b)):
    print(c+max(0,d-1))
    exit()
elif a==b:
    print(a+c+d)
    exit()
ans=min(a,b)+c
dif=abs(a-b)
ans+=min(dif,d)
d-=min(dif,d)
print(ans+d)

Measured memory_bytes: 40944
#include<stdio.h>

int main(void){
	int i, j, n;
	scanf("%d", &n);
	int a[200000];
	for(i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	int minj, tmp;
	int cnt = 0;

	for(i = 0;i<=n-1;i++){
		minj = i;
		for(j = i;j<=n-1;j++){
			if(a[j]<a[minj]){
				minj = j;
			}
		}
		tmp = a[i];
		a[i] = a[minj];
		a[minj] = tmp;
		if(minj != i)
			cnt++;
	}
	for(i = 0;i<n-1;i++){
		printf("%d ", a[i]);
	}
	printf("%d\n", a[n-1]);
	printf("%d\n", cnt);
	return 0;
}


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

int main() {
  int N;
  int a = 0;
  int b = 0;
  cin >> N;
  vector<int> A(N);
  
  for(int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
  
  sort(A.begin(), A.end(), greater<int>() );
  
  for(int i = 0; i < N; i++) {
    if(i == 0 || i % 2 == 0) {
      a += A.at(i);
    }else{
      b += A.at(i);
    }
  }
  
  cout << a - b << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if((c+b-1)/b<=(a+d-1)/d||(c+b-1)/b-1==(a+d-1)){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
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;}


//INSERT ABOVE HERE
const int MAX = 2020;
int st[MAX][MAX]={};
signed main(){
  int x1,y1,w1,h1;
  int x2,y2,w2,h2;
  cin>>x1>>y1>>w1>>h1;
  cin>>x2>>y2>>w2>>h2;

  for(int i=y1;i<y1+h1;i++)
    for(int j=x1;j<x1+w1;j++)
      st[i][j]++;

  for(int i=y2;i<y2+h2;i++)
    for(int j=x2;j<x2+w2;j++)
      st[i][j]++;

  int cnt=0;
  for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
      cnt+=st[i][j]==1;

  cout<<cnt<<endl;
  return 0;
}



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

int main(){
  int n,k,i,j;
  cin>>n>>k;
  if(n-1<k){
    k=n-1;
  }
  int a[n],dp[n];
  for(i=0;i<n;i++){
    cin>>a[i];
  }
  dp[0]=0;
  for(i=1;i<n;i++){
    dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
    for(j=2;j<=min(k,i);j++){
      dp[i]=min(dp[i],dp[i-j]+abs(a[i-j]-a[i]));
    }
  }
  cout<<dp[n-1];
}

Measured memory_bytes: 1024
def str_replace_to_lower() -> str:
    len_str, target_index = map(int, input().split())
    word = input()
    list_of_word = list(word)
    list_of_word[target_index - 1] = list_of_word[target_index - 1].lower()

    return ''.join(list_of_word)


print(str_replace_to_lower())

Measured memory_bytes: 9140
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

puts get_i.inject(1){|res,x| res.lcm(x)}

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

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

vector<int64_t> fact, seq_inv, fact_inv;

void create_fact_mod(int num){
    fact[0] = fact[1] = 1;
    for(int i=2; i<=num; i++) fact[i] = fact[i-1] * i % MOD;
}

void create_seq_inv_mod(int num){
    seq_inv[0] = seq_inv[1] = 1;
    for(int i=2; i<=num; i++) seq_inv[i] = (MOD - MOD/i) * seq_inv[MOD%i] % MOD;
}

void create_fact_inv_mod(int num){
    fact_inv[0] = fact_inv[1] = 1;
    for(int i=2; i<=num; i++) fact_inv[i] = fact_inv[i-1] * seq_inv[i] % MOD;
}

void create_mod_tables(int num){
    fact.resize(num+1);
    seq_inv.resize(num+1);
    fact_inv.resize(num+1);
    create_fact_mod(num);
    create_seq_inv_mod(num);
    create_fact_inv_mod(num);
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

int main(){
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    create_mod_tables(1000);

    static int64_t dp[1001][1001];
    dp[A-1][0] = 1;
    for(int i=A; i<=B; i++) for(int j=0; j<=N; j++){
        add(dp[i][j], dp[i-1][j]);
        int n = N-j;
        int64_t pw = power_mod(fact_inv[i], C);
        for(int k=C; k<=D && i*k<=n; k++){
            int64_t res = comb_mod(n, i*k) * fact[i*k] % MOD * pw % MOD * fact_inv[k] % MOD;
            mul(pw, fact_inv[i]);
            add(dp[i][j+i*k], dp[i-1][j] * res);
        }
    }
    cout << dp[B][N] << endl;
    return 0;
}


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

int main()
{
    int n,i,j,x,y,sum=0;
    vector <int> t;
    cin >> n;
    int N[n];
    for(i=0;i<n;i++)
    {
        cin >> N[i];
    }
    for(i=1;i<=100;i++)
    {
        sum = 0;
        for(j=0;j<n;j++)
        {
            x = (N[j]-i);
            y = x*x;
            if(y<0)
            {
                y = y * (-1);
            }
            sum = sum + y;
        }
        t.push_back(sum);
    }
    sort(t.begin(),t.end());
    cout << t[0] << endl;
    return 0;
}

Measured memory_bytes: 256
from itertools import permutations
n= int(input())
ls = []
for i in range(n):
    a = list(map(int,input().split()))
    ls.append(a)
ans = []
for i in permutations(ls,n):
    #print(i)
    result = 0
    for j in range(n-1):
        result += (((i[j][0]-i[j+1][0])**2+(i[j][1]-i[j+1][1])**2)**(1/2))
    ans.append(result)

ans = (1/len(ans))*sum(ans)
print(ans)

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

using namespace std;

#define MOD 1000000007
#define ll long long int
#define ld long double
#define pb push_back
#define mkp make_pair
#define pii pair<int, int> 
#define pll pair<long long int, long long int>
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define fi first
#define sc second
#define eps 1e-9

string s;

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

	ll i, j, k, x, y, z, ans = 0;
	cin >> s;
	i = s.size() - 1;
	ll cc = 0;
	while (i >= 0) {
		if (s[i] == 'C' && i-1 && s[i-1] == 'B') {
			cc += 1;
			i -= 2;
		} else if (s[i] == 'A') {
			ans += cc;
			i -= 1;
		} else {
			cc = 0;
			i -= 1;
		}
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 720
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#include<random>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define rrep(i,a) for(int i=(int)a-1;i>=0;--i)
#define REP(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RREP(i,a,b) for(int i=(int)a-1;i>=b;--i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n) / gcd(n, m)*abs(m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

vector<vector<int>>g;
vector<ll>cnt;

void dfs(int v,int pre=-1){
  if(pre!=-1)cnt[v]+=cnt[pre];
  for(auto x:g[v]){
    if(x!=pre){
      dfs(x,v);
    }
  }
}

void solve(){
  int n,q;
  cin>>n>>q;
  g.resize(n);
  cnt.resize(n);
  int a,b;
  rep(i,n-1){
    cin>>a>>b;
    a--;b--;
    g[a].pb(b);
    g[b].pb(a);
  }
  while(q--){
    int p;
    ll x;
    cin>>p>>x;
    p--;
    cnt[p]+=x;
  }
  dfs(0);
  rep(i,n){
    if(i)cout<<" ";
    cout<<cnt[i];
  }
}

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


Measured memory_bytes: 24320
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp
#  Binary Search : python3
#  2018.12.08 yonezawa


#from collections import deque
#import sys
#input = sys.stdin.readline
#import cProfile

def main():
    dic = {}
    for i in range(int(input())):
        l = list(map(str,input().split()))
        if l[0] == 'insert':
            dic[l[1]] = 'yes'
        else:
            try:
                print (dic[l[1]] )
            except:
                print ('no')
if __name__ == '__main__':
   main()
#    pr = cProfile.Profile()
#    pr.runcall(main)
#    pr.print_stats()


Measured memory_bytes: 33116
N,C = map(int,input().split())
STC = [tuple(map(int,input().split())) for i in range(N)]

cs = [[] for _ in range(30)]
for s,t,c in STC:
    cs[c-1].append((s,t))

imos = [0]*(100005)
for c in cs:
    c.sort(key=lambda x:x[0])
    pt = -1
    for s,t in c:
        if s==pt:
            imos[s] += 1
        else:
            imos[s-1] += 1
        imos[t] -= 1
        pt = t
for i in range(len(imos)-1):
    imos[i+1] += imos[i]
print(max(imos))

Measured memory_bytes: 27512
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

// Graph
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
// using Graph = vector<vector<int>>;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  map<int, int> A;
  ll sum = 0;
  for (int i = 0; i < N; i++)
  {
    int a;
    cin >> a;
    sum += a;
    A[a]++;
  }
  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++)
  {
    int B, C;
    cin >> B >> C;
    ll tmp = A[B];
    sum -= B * tmp;
    sum += C * tmp;
    A[B] -= tmp;
    A[C] += tmp;
    cout << sum << endl;
  }
  return 0;
}


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

using namespace std;

const int MOD = 1e9 + 7;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	long long n;
	cin >> n;
	unordered_map<long long, long long> dp;
	dp[0] = 1;
	dp[1] = 2;
	function<long long (long long)> calc = [&] (long long x) -> long long {
		if (dp[x]) {
			return dp[x];
		}
		dp[x] = calc(x / 2) + calc((x - 1) / 2) + calc((x - 2) / 2);
		dp[x] %= MOD;
		return dp[x];
	};
	cout << calc(n) << '\n';

	return 0;
}



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


int main(){
  constexpr int INF = 1e9;
  int N;
  cin >> N;
  vector<string> S(N);
  for(int i = 0; i < N; ++i) cin >> S[i];
  vector<vector<int>> D(N,vector<int>(N,1e9));
  for(int i = 0; i < N; ++i){
    D[i][i] = 0;
    for(int j = 0; j < N; ++j){
      if(S[i][j] == '1') D[i][j] = 1;
    }
  }
  for(int k = 0; k < N; ++k){
    for(int i = 0; i < N; ++i){
      for(int j = 0; j < N; ++j){
        D[i][j] = min(D[i][j],D[i][k]+D[k][j]);
      }
    }
  }
  int s = -1, t = -1, k = 0;
  for(int i = 0; i < N; ++i){
    for(int j = 0; j < N; ++j){
      if(D[i][j] > k){
        k = D[i][j];
        s = i;
        t = j;
      }
    }
  }
  ++k;
  vector<int> K(N,-1);
  K[s] = 0;
  K[t] = k-1;
  for(int i = 0; i < N; ++i){
    int s_ = -1;
    for(int j = 0; j < N; ++j){
      if(D[s][j] >= INF){
        s_ = j;
        continue;
      }
      K[j] = D[s][j];
    }
    if(s_ < 0) break;
    s = s_;
  }
  for(int i = 0; i < N; ++i){
    for(int j = 0; j < N; ++j){
      if(S[i][j] == '0') continue;
      if(abs(K[i]-K[j]) != 1){
        cout << -1 << endl;
        return 0;
      }
    }
  }
  cout << k << endl;
}


Measured memory_bytes: 512