akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

// これだとTLE
/*
int func(int i, int D, int G, vector<int> p, vector<int> c){
    // ベースケース
    if(i==D-1){ // k:=i+1=D
        if(100*D*p.at(i)+c.at(i) < G){
            return 1e8;
        } else if(G<=0){
            return 0;
        }
        int tmp = G/(100*D);
        if(tmp*100*D != G) tmp++; // 割り切れなかったら1を足す
        if(tmp < p.at(i)){
            return tmp;
        }else{
            return p.at(i);
        }
    } else{ // 再帰ステップ
        int ans = 1e8;
        for(int j=0; j <= p.at(i); j++){
            int tmp;
            if(j < p.at(i)){
                tmp = j + func(i+1,D,G-(100*(i+1)*j),p,c);
            } else {
                tmp = j + func(i+1,D,G-(100*(i+1)*j+c.at(i)),p,c);
            }
            if(tmp<ans) ans = tmp;
        }
        return ans;
    }
}*/

int main() {
    int D,G;
    cin >> D >> G;
    vector<int> p(D),c(D);
    rep(i,D) cin >> p.at(i) >> c.at(i);

    int ans = 1e8;
    // int ansbit;
    for(int bit=0; bit < (1<<D); bit++){ // bit全探索
        int sum = 0;
        int n = 0;
        for(int i=0; i<D; i++){ 
            if(bit & (1<<i)){ // iを完全に解く
                sum += 100*(i+1)*p.at(i) + c.at(i);
                n += p.at(i);
            }
        }
        if(sum < G){
            for(int i=0; i<D; i++){
                if(!(bit & (1<<i)) ){
                    int tmp = (G-sum)/(100*(i+1));
                    if(tmp*100*(i+1) < G-sum) tmp++;
                    if(tmp < p.at(i)){
                        n += tmp;
                        sum += 100*(i+1)*tmp;
                    }
                    if(n<ans && sum >= G){
                        ans = n;
                        // ansbit = bit;
                    }
                }
            }
        }        
        if(n<ans && sum >= G){
            ans = n;
            // ansbit=bit;
        }
    }
    cout << ans << endl;
    // cout << ans << " " << bitset<8>(ansbit) << endl;
    return 0;
}


Measured memory_bytes: 256
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, K, A):
    tree = SegmentTree(300_300)
    for a in A:
        p = tree.query(max(0, a - K), min(300_300, a + K + 1))
        tree.modify(a, p + 1)
    print(tree.query(0, 300_300))

class SegmentTree:
    __slots__ = ('__n', '__d', '__f', '__e')

    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i << 1], d[i << 1 | 1])

    def get_val(self, index):
        return self.__d[index + self.__n]

    def set_val(self, index, new_value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == new_value: return
        d[i], i = new_value, i >> 1
        while i: d[i], i = f(d[i << 1], d[i << 1 | 1]), i >> 1

    def modify(self, index, value):
        self.set_val(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l + 1
            if r & 1: ans, r = f(d[r - 1], ans), r - 1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, j, n, f, d, v = self.__n, self.__n + self.__n, self.__n, self.__f, self.__d, self.__e()
        while i < j:
            if i & 1:
                nv = f(v, d[i])
                if not func(nv): break
                v, i = nv, i + 1
            i, j = i >> 1, j >> 1
        while i < n:
            nv = f(v, d[i << 1])
            if func(nv): v, i = nv, i << 1 | 1
            else: i = i << 1
        return i - n

if __name__ == '__main__':
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    main(N, K, A)


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

typedef long long ll;

const int maxn = 405;
const int maxc = 405;

typedef long long ll;

const ll mod = (ll)1e9 + 7;

ll dp[maxn][maxc];

int a[maxn],b[maxn];

ll t[maxn][maxn];


int main()
{
	
	int n,C;
	scanf("%d %d",&n,&C);
	

	for(int i = 1; i <= n; i++)
	{
		scanf("%d",&a[i]);
	}
	
	for(int i = 1; i <= n; i++)
	{
		scanf("%d",&b[i]);
	}

	for(int i = 1; i <= n; i++)
	{
		for(int j = a[i]; j <= b[i]; j++)
		{
			ll x = 1;
			for(int k = 0; k <= C; k++)
			{
				t[i][k] += x;
				t[i][k] %= mod;
				x *= j;
				x %= mod;
			}
		}
	}

	dp[0][0] = 1;
	for(int i = 1; i <= n; i++)
	{
		for(int c = 0; c <= C; c++)
		{
			for(int j = 0; j <= c; j++)
			{
				dp[i][c] += (dp[i-1][c-j] * t[i][j]) % mod;
				dp[i][c] %= mod;
			}
		}
	}
	printf("%lld\n",dp[n][C]);
	return 0;
}

Measured memory_bytes: 2816
#include <iostream>

using namespace std;

int n;
int dp[5][4001];

int main() {
    fill(dp[0], dp[5], 0);
    dp[0][0] = 1;
    for (int i = 1; i <= 4; i++) {
        for (int j = 0; j <= 4000; j++) {
            for (int k = 0; k <= 1000; k++) {
                if (j + k <= 4000)
                    dp[i][j + k] += dp[i - 1][j];
            }
        }
    }
    while (cin >> n) {
        cout << dp[4][n] << endl;
    }
}


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

int main()
{
    int k,n,m=-1;
    cin>>k>>n;
    vector<int>v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    sort(v.begin(),v.end());
    for(int i=0;i<v.size()-1;i++){
        m=max(v[i+1]-v[i],m);
    }
    int ans = min(k-m,v[n-1]-v[0]);
    cout<<ans<<endl;

}


Measured memory_bytes: 1024
n, y = map(int, input().split())

ans = [-1, -1, -1]

for i in range(n+1):
  for j in range(n-i+1):
    if (10000*i + 5000*j + 1000*(n-i-j)) == y:
      ans = [i, j, n-i-j]
      break

print(' '.join(map(str, ans)))

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	int arr[n][m];
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>arr[i][j];
		}
	}
	int a[m];
	for(int i=0;i<m;i++){
		cin>>a[i];
	}
	int sum=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			sum+=arr[i][j]*a[j];
		}
		cout<<sum<<endl;
		sum=0;
	}
	
	
	
	return 0;
}

Measured memory_bytes: 3128
import copy
def dfs(tmp):
  for i in range(n):
    if ll[tmp][i] == 1 and seen[i] == 0:
      seen[i] = 1
      dfs(i)

n,m = map(int,input().split())
ll =[[0]*n for _ in [0]*n]
edges = [list(map(int,input().split())) for _ in [0]*m]
for edge in edges:
  ll[edge[0]-1][edge[1]-1] = 1
  ll[edge[1]-1][edge[0]-1] = 1
originalll = ll.copy()
seen = [0]*n
ans = 0

for edge in edges:
  ll = copy.deepcopy(originalll)
  ll[edge[0]-1][edge[1]-1] = 0
  ll[edge[1]-1][edge[0]-1] = 0
  seen = [0]*n
  tmp = 0
  seen[tmp] = 1
  dfs(tmp)
  if sum(seen) < n:
    ans += 1
print(ans)





Measured memory_bytes: 3572
// </> : towhid1zaman

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;typedef vector<ll> vll;
#define fill(a,b) memset(a, b, sizeof (a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
#define unq(v) sort(all(v)),(v).erase(unique(all(v)),(v).end())
#define _ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int maxn = 2000100;

ll mbxp(ll x, ll n, ll m){
    ll res = 1;
    x%=m;
    while(n>0){
        if(n%2==1){
            res = (res*x)%m;
        }
        n/=2;
        x = (x*x)%m;
    }
    return res%m;
}
int main(){
        _ios;

        string s; cin >> s;
        reverse(all(s));
        ll n = s.size();
        vi a(n);
        for(ll i = 0; i<n; i++){
            a[i] = ((s[i]-'0')*mbxp(10,i,2019))%2019;
        }
        vi pref(n);
        pref[0] = a[0];
        for(ll i = 1; i<=n; i++){
            pref[i] = (pref[i-1]+a[i])%2019;
        }
        map<ll,ll>mp;
        ll ans = 0;
        for(int i = 0; i<n;i++){
            if(pref[i]==0)ans++;
            ans+=mp[pref[i]];
            mp[pref[i]]++;
        }
        cout<<ans<<endl;

return 0;
}



Measured memory_bytes: 5104
#include <stdio.h>
int main(void){
  int i,a,t[4]={};
  for(i=0;i<6;i++){
    scanf("%d",&a);
    t[a-1]++;
  }
  for(i=0;i<4;i++){
    if(t[i]==3)break;
  }
  printf("%s",(i==4)?"YES":"NO");
}

Measured memory_bytes: 128
import sys


def main():
  n, *lst = map(int, sys.stdin.read().split())
  max1 = max(lst)
  idx = lst.index(max1)
  max2 = max(lst[:idx] + lst[idx+1:])
  print('\n'.join(str(max1) if j != max1 else str(max2) for j in lst))


if __name__ == '__main__':
  main()


Measured memory_bytes: 25136
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define inf 1000000000000000000
#define bpc(x) __builtin_popcountll(x)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

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

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;

int main()
{
  FAST/**/
   
   ll arr[5];
   rep(5)
        cin>>arr[i];
   
   rep(5)
   {
       if(arr[i] == 0)
       {
           cout<<i+1;
           return 0;
       }
   }
   
   return 0;        
}  
  
          
   

Measured memory_bytes: 3536
import fractions

N = int(input())
A = [int(a) for a in input().split(" ")]

firstgcds = [0]
lastgcds = [0]
for i in range(0, N):
    firstgcds.append(fractions.gcd(firstgcds[i], A[i]))
    lastgcds.append(fractions.gcd(lastgcds[i], A[-i-1]))
ans = 0
for i in range(0, N):
    preans = fractions.gcd(firstgcds[i], lastgcds[-i-2])
    if ans < preans:
        ans = preans
if ans < firstgcds[N-1]:
    ans = firstgcds[N-1]
print(ans)


Measured memory_bytes: 99032
#include<stdio.h>
	int main() {
		char X, Y;
		scanf("%c %c", &X, &Y);
		if (X > Y) {
			printf(">\n");
		}
		else if (X < Y) {
			printf("<\n");
		}
		else {
			printf("=\n");
		}


		return 0;
	}



Measured memory_bytes: 128
#include<cstdio>

int main()
{
	int l,r,d,f=0;
	scanf("%d%d%d",&l,&r,&d);
	for(int i=l;i<=r;i++){
		if(i%d==0) f++;
	}
	printf("%d",f);
	return 0;
}

Measured memory_bytes: 1728
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<pair<ll, ll>> vpll;
typedef pair<ll, ll> pll;
#define mod 1000000007
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define yes(a) printf(a ? "yes\n" : "no\n")
#define Yes(a) printf(a ? "Yes\n" : "No\n")
#define YES(a) printf(a ? "YES\n" : "NO\n") 
const long double PI = acos(-1);
const long long INF = (1 << 30);
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}

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

  string s;
  cin >> s;
  ll len = s.size();

  ll ans = 0;
  ll cnt = 0;
  vector<ll> a(500005);
  for(ll i = 0; i < len; i++){
    if(s[i] == '<'){
      a[i] = cnt;
      cnt++;
    }else{
      a[i] = cnt;
      cnt = 0;
    }
  }
  a[len] = cnt;
  cnt = 0;
  for(ll i = len-1; i >= 0; i--){
    if(s[i] == '>'){
      a[i+1] = cnt;
      cnt++;
    }else{
      a[i+1] = max(cnt, a[i+1]);
      cnt = 0;
    }
  }
  a[0] = max(cnt, a[0]);
  for(ll i = 0; i <= len; i++){
    ans += a[i];
  }
  cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4764
import string
import sys

input = sys.stdin.readline
AL = string.ascii_lowercase


def main():
    w = input().rstrip()
    ans = "Yes"
    for s in AL:
        cnt = w.count(s)
        if cnt % 2 == 1:
            ans = "No"
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3772
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    if(n == 25) cout << "Christmas" << endl;
    else if(n == 24) cout << "Christmas Eve" << endl;
    else if(n == 23) cout << "Christmas Eve Eve" << endl;
    else if(n == 22) cout << "Christmas Eve Eve Eve" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<cstring>
#include<functional>
#include<bitset>
using namespace std;
typedef	long long int ll;

bool color[100001]; //v_maxは最大頂点数
int d[100001]; //最初に訪問した時間
int f[100001]; //探索し終えた時間
int t = 0; //時間
vector< pair<int, int> > g[100001]; //隣接リスト
int x[100001]; //人の位置

bool dfs(int u){
    color[u] = 1;
    d[u] = ++t;
    for(int i = 0; i < g[u].size(); i++){
        if(x[g[u][i].first] == 2000000001){
            x[g[u][i].first] = x[u] + g[u][i].second;
        }
        else if(x[g[u][i].first] != x[u] + g[u][i].second){
            return 0;
        }
        if(color[g[u][i].first] == 0){
            if(dfs(g[u][i].first) == 0) return 0;
        }
    }
    f[u] = ++t;
    return 1;
}

int main(){
    int n, m, l, r, d;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> l >> r >> d;
        g[l].push_back(make_pair(r,d));
        g[r].push_back(make_pair(l, -d));
    }
    memset(color, 0, sizeof(color));
    for(int i = 1; i <= n; i++){
        x[i] = 2000000001;
    }
    for(int i = 1; i <= n; i++){
        if(!color[i]){
            x[i] = 0;
            bool res = dfs(i);
            if(!res){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 12800
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        if (a == 1) {
            if (b == 2) {
                System.out.println("3");
            } else {
                System.out.println("2");
            }
        } else if (a == 2) {
            if (b == 1) {
                System.out.println("3");
            } else {
                System.out.println("1");
            }
        } else {
            if (b == 1) {
                System.out.println("2");
            } else {
                System.out.println("1");
            }
        }
    }
}


Measured memory_bytes: 20564
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;

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

	if (N >= 30) {
		cout << "Yes" << endl;
	}else {
		cout << "No" << endl;
		
	}

	return 0;
}



Measured memory_bytes: 3592
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef vector<int> VI;
ll mm=1000000000;ll MM=mm+7;
#define rep(i, n) for(int i=0;i<n;i++)
#define PI 3.141592653589793

int main(){
  int n;
  cin  >> n;
  vector<double> v(n);
  rep(i,n){
      cin >> v.at(i);
  }
  sort(v.begin(),v.end());
  double ans=(v.at(0)+v.at(1))/2;
  for(int i=2;i<n;i++){
      ans=(ans+v.at(i))/2;
  }
  cout << fixed << setprecision(7) << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

bool sum_rec(int index, vector<int> &A, int sum, int expected) {
    if (sum > expected) { return false; }
    if (index == A.size()) {
        return (sum == expected);
    }
    int new_sum = sum + A[index];
    index++;
    return sum_rec(index, A, new_sum, expected) || sum_rec(index, A, sum, expected);
}

int main() {
    int n, q;
    int i, j;
    cin >> n;
    vector<int> A(n);
    rep(i, n) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());

    cin >> q;
    int m[q];
    rep(i, q) (cin >> m[i]);
    rep(i, q) {
        int M = m[i];
        int sum = 0;
        int index = 0;
        if (sum_rec(index, A, sum, M)) {
            cout << "yes" << endl; 
        } else {
            cout << "no" << endl; 
        }
    }

    return 0;
}


Measured memory_bytes: 3156
/*
 * 1st.cpp
 *
 *  Created on: Sep 6, 2017
 *      Author: Nirav
 */


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

#define fill(a,val) memset(a, (val), sizeof a)
#define pb push_back
#define lli long long int
#define scantype int
#define endl "\n"
#define unique(x) x.erase(unique(x.begin(),x.end()), x.end())
#define sort_f(x)  sort(x.begin(),x.end());
#define sort_r(x)  sort(x.rbegin(),x.rend());

lli MOD  = 1000000007;
lli inf = 1e15;

void scan(scantype &x);
lli powermod(lli _a,lli _b,lli _m){lli _r=1;while(_b){if(_b%2==1)_r=(_r*_a)%_m;_b/=2;_a=(_a*_a)%_m;}return _r;}
lli string_to_number(string s){lli x=0; stringstream convert(s); convert>>x; return x;}
lli add(lli a,lli b){lli x = (a+b)%MOD; return x; }
lli mul(lli a,lli b){lli x = (a*b)%MOD; return x; }
lli sub(lli a,lli b){lli x = (a-b+MOD)%MOD; return x; }
lli divi(lli a,lli b){lli x = a;lli y = powermod(b,MOD-2,MOD);lli res = (x*y)%MOD;return res;}

#define N 200003



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
     lli x,t;
    cin>>x>>t;
    lli ans=x-t;
    if(ans<=0)
    {
          cout<<"0"<<endl;
    }
    else
    {
        cout<<ans<<endl;
    }
                    
	return 0;
}

void scan(scantype &x)
{
    register int c = getchar(); //for negative/positive
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = getchar());
    if(c=='-') {neg=1;c=getchar();}
    for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}









Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  std::string S;

  std::cin >> S;

  int c = 0;

  for (int i = 0, size = S.size(); i < size / 2; i ++)
    if (S[i] != S[size - 1 - i])
      c ++;

  std::cout << c << std::endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

const int mod = 1e9+7;
#define ll long long int
const double epsilon = 1e-7;

ll mi(ll x, ll y){
    if(x<y)return x;
    return y;
}
char s[200001];
char t[200001];
int lout[200001];
int rout[200001];
int uout[200001];
int dout[200001];
int main(void){
    int h, w, n;
    scanf("%d %d %d", &h, &w, &n);
    int sr, sc;
    scanf("%d %d", &sr, &sc);
    sr--;
    sc--;
    scanf("%s", &s);
    scanf("%s", &t);
    if(s[n-1] == 'L'){
        lout[n-1] = 0;
        rout[n-1] = w;
        uout[n-1] = -1;
        dout[n-1] = h;
    }
    if(s[n-1] == 'R'){
        lout[n-1] = -1;
        rout[n-1] = w-1;
        uout[n-1] = -1;
        dout[n-1] = h;
    }
    if(s[n-1] == 'U'){
        lout[n-1] = -1;
        rout[n-1] = w;
        uout[n-1] = 0;
        dout[n-1] = h;
    }
    if(s[n-1] == 'D'){
        lout[n-1] = -1;
        rout[n-1] = w;
        uout[n-1] = -1;
        dout[n-1] = h-1;
    }
    for(int i = n - 2;i >= 0;i--){
        if(t[i] == 'L'){
            lout[i] = lout[i+1];
            rout[i] = rout[i+1]+1;
            uout[i] = uout[i+1];
            dout[i] = dout[i+1];
        }
        if(t[i] == 'R'){
            lout[i] = lout[i+1]-1;
            rout[i] = rout[i+1];
            uout[i] = uout[i+1];
            dout[i] = dout[i+1];
        }
        if(t[i] == 'U'){
            lout[i] = lout[i+1];
            rout[i] = rout[i+1];
            uout[i] = uout[i+1];
            dout[i] = dout[i+1]+1;
        }
        if(t[i] == 'D'){
            lout[i] = lout[i+1];
            rout[i] = rout[i+1];
            uout[i] = uout[i+1]-1;
            dout[i] = dout[i+1];
        }
        
        if(lout[i] == -2)lout[i]++;
        if(rout[i] == w+1)rout[i]--;
        if(uout[i] == -2)uout[i]++;
        if(dout[i] == h+1)dout[i]--;
        
        if(s[i] == 'L'){
            lout[i]++;
        }
        if(s[i] == 'R'){
            rout[i]--;
        }
        if(s[i] == 'U'){
            uout[i]++;
        }
        if(s[i] == 'D'){
            dout[i]--;
        }
        if(lout[i] == w-1 || rout[i] == 0 || uout[i] == h-1 || dout == 0){
            printf("NO\n");
            return 0;
        }
    }
    //for(int i = 0;i < n;i++)printf("%d %d %d %d\n", lout[i], rout[i], uout[i], dout[i]);
    if(sc > lout[0] && sc < rout[0] && sr > uout[0] && sr < dout[0])printf("YES\n");
    else printf("NO\n");
    return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<ll,pll> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n;
vvi a;
vi b;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	a=vvi(n,vi(n-1));
	b=vi(n);
	for(int i=0;i<n;i++) for(auto &j:a[i]){
		cin>>j;
		j--;
	}
	int res=0;
	set<int> st;
	for(int i=0;i<n;i++) if(a[a[i][0]][0]==i&&i<a[i][0]) st.insert(i);
	while(b!=vi(n,n-1)){
		if(st.empty()){
			res=-1;
			break;
		}
		set<int> st_=st;
		for(auto i:st){
			st_.insert(a[i][b[i]]);
			b[a[i][b[i]]]++;
			b[i]++;
		}
		st=st_;
		st_.clear();
		for(auto i:st) if(b[i]<n-1){
			int j=a[i][b[i]];
			if(b[j]<n-1&&a[j][b[j]]==i) st_.insert(min(i,j));
		}
		st=st_;
		res++;
	}
	cout<<res<<endl;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> b(n-1);
    rep(i, n-1) cin >> b.at(i);

    int ans = b.at(0);
    for(int i = 0; i < n-2; i++) {
        ans += min(b.at(i), b.at(i+1));
    }

    ans += b.at(n-2);
    cout << ans << endl;
    return 0;
}

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

using namespace std;

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

    if (a[a.size()-1] == b[0] && b[b.size()-1] == c[0])
        cout << "YES" << endl;
    else
        cout << "NO" << endl;

    return 0;
}


Measured memory_bytes: 3544
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n;
    const int max_index = 1000000;
    int prime[max_index];

    prime[0] = 0;
    for (int i = 1; i < max_index; i++) 
        prime[i] = 1;

    for (int i = 1; i < (int)sqrt(max_index); i++) {
        if (prime[i] == 1)
            for (int j = i + 1; (i + 1) * j <= max_index; j++)
                prime[(i + 1) * j - 1] = 0;
    }

    int tmp = 0;
    for (int i = 0; i < max_index; i++) 
        (prime[i] == 0) ? (prime[i] = tmp) : prime[i] = ++tmp;
    prime[0] = 0;

    while (cin >> n) 
        cout << prime[n - 1] << endl;
    
    return 0;
}

Measured memory_bytes: 5064
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# import time
# from itertools import product,permutations,\
#     combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

mod = int(1e9+7)
# mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    x = readInt()
    for i in range(5):
        if x[i]!=i+1:
            print(i+1)
    return

if __name__=='__main__':
    main()


Measured memory_bytes: 9040
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);++i)
 
int main() {
    string A; cin >> A;
    int N = A.size();
    vector<ll> cnt(26);
    REP(i,N) {
        cnt[A[i]-'a']++;
    }
    ll ans = (ll)N*(N+1)/2;
    REP(i,26) {
        ans -= cnt[i]*(cnt[i]+1)/2;
    }
    cout << ans+1 << endl;
    return 0;
}

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

string S;

int main() {
    cin >> S;

    reverse(S.begin(), S.end());
    string new_S = S.substr(8, S.length()-8);
    reverse(new_S.begin(), new_S.end());

    cout << new_S << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> v;
    while (n != 0) {
        int d = abs(n % 2);
        v.push_back(d);
        n = (n - d) / -2;
    }

    if (v.size() == 0) {
        cout << 0 << '\n';
    } else {
        for (int i = v.size() - 1; i >= 0; --i)
            cout << v[i];
        cout << '\n';
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 1e5 + 5;
const ll OO = 1e16;
const long double EPS = 1e-6;

int n,m;
char arr[1001][1001];
int dp[1001][1001];
int solve(int i,int j){

        if(i >= n || j >= m ||  arr[i][j] == '#')
            return 0;

        if(i == n - 1 && j == m - 1)
                return 1;
        int &ret = dp[i][j];
        if(~ret)
            return ret;
        ret = solve(i + 1,j) + solve(i, j + 1);
        if(ret >= mod)
            ret -= mod;
        return ret%mod;
}
int main()
{
    ios_base::sync_with_stdio();cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; ++i)
            for(int j = 0 ; j < m; ++j)
                cin >> arr[i][j];
    memset(dp,-1,sizeof dp);
    cout << solve(0,0) << "\n";
    return 0;
}


Measured memory_bytes: 5248
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define int ll

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const N = 2e5 + 20 , inf = 2e18 + 20 ;
int n , par[N] , w[N] ;
vector <int> g[N] ;
set <pii> st[N] ;

int W ;

void dfs (int v) {
	if (!_sz(g[v])) {
		st[v].insert({0 , 0}) ;
		return ;
	}
	
	int x = g[v][0] , y = g[v][1] ;

	dfs(x) , dfs(y) ;

	for (pii p : st[x]) {
		set <pii> :: iterator it = st[y].lower_bound({W - p.S - w[x] - w[y] + 1 , -1}) ;

		if (it != st[y].begin()) {
			it -- ;
			pii q = *it ;
			
			st[v].insert({p.F + w[x] , q.S + w[y]}) ;
			st[v].insert({q.S + w[y] , p.F + w[x]}) ;
		}
	}

	int mn = inf ;
	for (set <pii> :: iterator it = st[v].begin() ; it != st[v].end() ;) {
		pii p = *it ;

		if (mn <= p.S) st[v].erase(p) ;
		mn = min(mn , p.S) ;

		it = st[v].upper_bound(p) ;
	}
}

int32_t main(){
	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;

	cin >> n ;
	for (int i = 1 ; i < n ; i ++) {
		cin >> par[i] >> w[i] ;
		par[i] -- ;
		g[par[i]].push_back(i) ;
	}

	int low = -1 , high = 1e11 ;
	while (high - low > 1) {
		W = (low + high) / 2 ;

		for (int i = 0 ; i < n ; i ++) st[i].clear() ;

		dfs(0) ;

		if (st[0].empty()) low = W ;
		else high = W ;
	}

	cout << high << '\n' ;
}


Measured memory_bytes: 90624
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
int gcd(int a,int b){if(a<b){swap(a,b);}if(b==0){return a;}return gcd(a%b,b);}
int main(void){
	int a,b,c;
	cin>>a>>b>>c;
	if(b-a==c-b){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
	return 0;
}

Measured memory_bytes: 256
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;
import java.lang.Math.*;
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        int n = in.nextInt();
        int t = in.nextInt();
        int[]cost = new int[n];
        int[]mx = new int[n];
        ArrayList<Integer> store = new ArrayList<>();
        for(int i =0;i<n;i++){
            cost[i] = in.nextInt();
        }
        int m =0;
        for(int i=n-1;i>=0;i--){
            mx[i]=m;
            m = Math.max(m,cost[i]);
        }
        for(int i =0;i<n;i++){
            store.add(mx[i]-cost[i]);
        }
        Collections.sort(store);
//        System.out.println(store);
        int need = store.get(n-1);
        int s = 0;
        for (int v:store){
            if (v==need)
                s++;
        }
        System.out.println(s);
    }
}

Measured memory_bytes: 60000
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

int main(){
	const LL mod = 1000000007LL;

	int pra[128] = {}, prs[128] = {};
	pra['|'] = 15;
	pra['&'] = 25;
	pra[')'] = 5;

	prs['|'] = 16;
	prs['&'] = 26;
	prs['~'] = 34;
	prs['('] = 4;

	string s;
	cin >> s;
	s += ')';

	vector<pii> v(1, pii('(', -1));
	v.reserve(s.size());

	for(size_t i = 0; i < s.size(); ++i){
		int c = s[i];
		if(c == 'x'){
			v.push_back(pii(1, 1));
		}
		else if(!isdigit(c)){
			if(c != '(' && c != '~'){
				while(v.size() > 1){
					int op = v[v.size() - 2].first;

					if(prs[op] < pra[c]){ break; }

					pii y = v.back();
					v.pop_back();
					v.pop_back();

					if(op == '~'){
						v.push_back(pii(y.second, y.first));
					}
					else if(op == '&'){
						pii x = v.back();
						LL tr = (LL)x.first * y.first;
						LL fl = (LL)x.first * y.second + x.second * LL(y.first + y.second);
						v.back() = pii(tr % mod, fl % mod);
					}
					else if(op == '|'){
						pii x = v.back();
						LL tr = (LL)x.second * y.first + x.first * LL(y.first + y.second);
						LL fl = (LL)x.second * y.second;
						v.back() = pii(tr % mod, fl % mod);
					}
					else{
						throw op;
					}
				}
			}
			
			if(c == ')'){
				v[v.size() - 2] = v.back();
				v.pop_back();
			}
			else{
				v.push_back(pii(c, -1));
			}
		}
	}
	
	cout << v[0].first << endl;
}

Measured memory_bytes: 7460
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1e9+7
#define PI acos(-1.0)
#define ll long long
#define INF 1000000001

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

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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int a,b;cin>>a>>b;
  if(a%3==0 || b%3==0 || (a+b)%3==0){
    P("Possible");
  }else{
    P("Impossible");
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x=0;
    char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}
int l[11],dp[310][131];
int main() {
    int n=read(),c=read(); double ans=0,t=0;
    for (int i=0;i<n;i++) l[i]=read(); sort(l,l+n);
    do  {
        memset(dp,0,sizeof(dp));
        dp[l[n-1]*n][0]=1;
        for(int i=0;i<=n*c;i++)
            for (int j=i;j<=n*c;j++)
                for (int S=0;S<(1<<n-1);S++)
                    if (i%n and !((S>>(i%n-1))&1))
                        dp[min(n*c,max(j,i+l[i%n-1]*n))][S|(1<<(i%n-1))]+=dp[j][S];
        ans+=dp[n*c][(1<<n-1)-1],t++;
    } while (next_permutation(l,l+n-1));
    printf("%0.12lf\n",(double)ans/(double)t/pow(c,n-1));
    return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.ComponentModel.DataAnnotations;
using System.Dynamic;
using System.Linq;
using System.Security.Cryptography.X509Certificates;

namespace atcorder
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            string T = Console.ReadLine();
            int n = S.Length;
            int m = 0;
            for (int i = 0; i < n; i++)
            {
                if (S.Substring(i, 1) != T.Substring(i, 1))
                {
                    m++;
                }
            }
            Console.WriteLine(m);
        }
    }
}



//文字配列の取得
//string[] strArray = Console.ReadLine().Split(' ').ToArray();
//string S = strArray[0];
//string T = strArray[1];

//文字列の取得
//string s = Console.ReadLine();

//数字配列の取得
//int[] intArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
//int H = intArray[0];
//int W = intArray[1];

//数字の取得
//int N = int.Parse(Console.ReadLine());

//リスト型(int)の取得
//List<int> A = new List<int>(Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray());

//出力
//Console.WriteLine(ans);
//Console.WriteLine("Yes");
//Console.WriteLine("No");
//Console.WriteLine(cnt);



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

int main(){
    int n;
    cin >> n;
    int a[105][105];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            a[i][j] = 0;
        }
    }
    for(int i=1; i<=n; i++){
        int u, k;
        cin >> u >> k;
        for(int j=1; j<=k; j++){
            int v;
            cin >> v;
            a[u][v] = 1;
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<n; j++){
            printf("%d ", a[i][j]);
        }
        printf("%d\n", a[i][n]);
    }
}


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

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

using ll = long long;

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

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

int main() {
  string s;
  cin>>s;
  vector<char> v;
  for(auto x:s){
    if(x=='x') continue;
    v.push_back(x);
  }
  int l = v.size();
  bool can = true;
  rep(i,l){
    if(v[i]!=v[l-1-i]){
      can=false;
      break;
    }
  }
  if(!can) cout<<-1<<endl;
  else{
    int n = 0;
    map<int,int> m;
    rep(i,(int)s.size()){
      if(s[i]=='x'){
        n++;
        m[i-n]++;
      }
    }
    for(auto x:m){
      chmax(m[x.first],m[l-2-x.first]);
      chmax(m[l-2-x.first],m[x.first]);
    }
    int cnt = 0;
    for(auto x:m){
      cnt+= x.second;
    }
    for(auto x:m){
    }
    cout<<cnt-((int)s.size()-l)<<endl;
  }
}

Measured memory_bytes: 6832
/*g++ main.cpp -o main.out*/
/*./main.out*/

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

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

int l[101];

int main()
{
    int n,x;
    cin>>n>>x;
    int ans=1,d=0;
    rer(i,1,n)
    {
        cin>>l[i];
        d+=l[i];
        if(d<=x)ans++;
    }
    cout<<ans<<endl;
    return 0;
}

























Measured memory_bytes: 256
#include <cstdio>
#include <cstring>

int main()
{
    char str[100];
    scanf("%s", str);

    int n = strlen(str);
    int a = (n - 1) / 2 - 1;
    int b = (n + 3) / 2 - 1;
    --n;

    for(int i = 0; i < a; i++)
    {
        if(str[i] != str[a - i])
        {
            printf("No");
            return 0;
        }
    }

    for(int i = b; i < n; i++)
    {
        if(str[i] != str[n - i + b])
        {
            printf("No");
            return 0;
        }
    }

    for(int i = 0; i < n / 2; i++)
    {
        if(str[i] != str[n - i])
        {
            printf("No");
            return 0;
        }
    }

    printf("Yes");
    return 0;
}

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

using namespace std;


void solve(){
    vector<int> a(5);
    for(auto& i: a) cin>>i;
    for(const auto& i: a)
        if(i==0) cout<<&i-&a[0]+1;
}


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

    // int T; cin>>T; while(T--)
        solve();
}

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

int N;
string names[14];
string use[14];
bool flg[14];
int dp[1 << 14][14];
int sc[20][20];

int samecnt(int s1, int s2){
	int ret = 0;
	int len = min(use[s1].size(), use[s2].size());
	for(int j = 0; j < len; j++){
		bool flg = true;
		for(int i = 0; i < j; i++){
			if(use[s1][use[s1].size() - j + i] != use[s2][i]){
				flg = false;
			}
		}
		if(flg) ret = j;
	}
	return ret;
}

int main(){
	while(cin >> N, N){
		for(int i = 0; i < N; i++){
			cin >> names[i];
			flg[i] = true;
		}
		int idx = 0;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(i == j) continue;
				if(names[i].find(names[j]) != string::npos){
					flg[j] = false;	
				}
			}
		}
		for(int i = 0; i < N; i++){
			if(flg[i]){
				use[idx++] = names[i];
			}
		}
		for(int i = 0; i < idx; i++){
			for(int j = 0; j < idx; j++){
				sc[i][j] = samecnt(i, j);
			}
		}
		for(int i = 0; i < (1 << idx); i++){
			for(int j = 0; j < idx; j++){
				int val = 10000000;
				int mask = 1 << j;
				if((i & mask) == 0){

				}else{
					int m2 = i & (~mask);
					if(m2 == 0){
						val = use[j].size();
					}else{
						for(int k = 0; k < idx; k++){
							int np = dp[m2][k] + use[j].size() - sc[k][j];
							val = min(val, np);	
						}
					}
				}
				dp[i][j] = val;
			}
		}
/*
		for(int i = 0; i < (1 << idx); i++){
			cout << static_cast<std::bitset<8> >(i);
			for(int j = 0; j < idx; j++){
				cout << " " << dp[i][j];
			}
			cout << endl;
		}
*/
		int ans = 10000000;
		for(int i = 0; i < idx; i++){
			ans = min(dp[(1<<idx) - 1][i], ans);	
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3916
s=input()
ans=0
for i in range(2**(len(s)-1)):
    tmp=0
    tmp_str=s[0]
    for j in range(len(s)-1):
        if i&(2**j):
            tmp+=int(tmp_str)
            tmp_str=s[j+1]
        else:
            tmp_str+=s[j+1]
    tmp+=int(tmp_str)
    ans+=tmp
print(ans)

Measured memory_bytes: 3064
// E - 1 or 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

class DisjointSet {
public:
	int size;
	vector<int> rank;
	vector<int> parent;

	DisjointSet() {}

	// 0, 1, ... size-1 をそれぞれ唯一の要素とする
	// size個の互いに素な集合を作成
	DisjointSet(int size) {
		this->size = size;
		rank.resize(size, 0);
		parent.resize(size, 0);
		for (int i=0; i<size; i++) {
			makeSet(i);
		}
	}

	// 要素がXただ一つである新しい集合を作る
	void makeSet(int x) {
		parent[x] = x;
		rank[x] = 0;
	}

	// xとyが同じ集合に属しているかを判定する
	bool same(int x, int y) {
		return findSet(x) == findSet(y);
	}

	// 指定された2つの要素x, yを合併する
	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}

	// 低い方の木を高い方の木に合併
	void link(int x, int y) {
		if (rank[x] > rank[y]) {
			parent[y] = x;
		} else {
			parent[x] = y;
			if (rank[x] == rank[y]) {
				rank[y]++;
			}
		}
	}

	// 要素xが属する集合の代表の要素を求める
	int findSet(int x) {
		if (x != parent[x]) {
			parent[x] = findSet(parent[x]);
		}
		return parent[x];
	}

	// 集合の個数を求める
	int countSet() {
		int cnt = 0;
		for (int x=0; x<size; x++) {
			if (x == parent[x]) cnt++;
		}
		return cnt;
	}
};

int main() {
	int N, M;
	cin >> N >> M;

	DisjointSet ds = DisjointSet(N);

	int X, Y, Z;
	for (int i=0; i<M; i++) {
		cin >> X >> Y >> Z;
		X--;
		Y--;
		ds.unite(X, Y);
	}

	int ans = ds.countSet();

	cout << ans << endl;

	return 0;
}

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

int main(){
  int N;
  cin >> N;
  vector<string> vecS(N);
  vector<int> vecI(N);
  vector<int> vec_ans(N);
  for(int i=0; i<N; i++){
    cin >> vecS.at(i);
    cin >> vecI.at(i);
  }
  for(int x=1; x<N+1; x++){
    vec_ans.at(x-1) = x;
  }
  int j = 0;
  while(j<N-1){
    if(vecS.at(j) > vecS.at(j+1)){
      swap(vecS.at(j), vecS.at(j+1));
      swap(vecI.at(j), vecI.at(j+1));
      swap(vec_ans.at(j), vec_ans.at(j+1));
      j = 0;
    continue;
    }
    j++;
  }
  int k=0;
  while(k<N-1){
    if(vecS.at(k) == vecS.at(k+1) && vecI.at(k) < vecI.at(k+1)){
      swap(vecI.at(k), vecI.at(k+1));
      swap(vec_ans.at(k), vec_ans.at(k+1));
      k = 0;
      continue;
    }
    k++;
  }
  for(int l=0; l<N; l++){
    cout << vec_ans.at(l) << endl;
  }
}

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

#include<string>

int main() {
	string s;

	cin >> s;

	for (int i = 0; i < s.size(); ++i) {
		if (i % 2 == 0) {
			cout << s[i];
		}
	}
	cout << endl;

	return 0;
}


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

const bool DEBUG = false;

int N;
vector<string> s;

void input() {
  cin >> N;
  s = vector<string>(N);
  for (size_t i = 0; i < N; i++) cin >> s[i];
}

int main(int argc, char const *argv[]) {
  input();

  for (size_t i = 0; i < N; i++) sort(s[i].begin(), s[i].end());
  sort(s.begin(), s.end());

  long long total = 0, count = 1;
  for (size_t i = 0; i < N; i++) {
    if (i == (N - 1) || (s[i] != s[i + 1])) {
      total += (count * (count - 1)) / 2;
      count = 1;
    } else {
      count++;
    }
  }

  cout << total << endl;

  return 0;
}


Measured memory_bytes: 7296
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int main(){
	int n,c=0,flag,f=0;
	char w[50],r;
	char x[102];
	cin>>n;
	cin>>w;
	for(int i=0;i<n;i++){
		cin>>x;
		f=0;
		int t=strlen(x);
		for(int j=0;j<strlen(x);j++){
			//cout<<"wwwww"<<endl;
			if(w[0]==x[j]){
				for(int z=1;z<t;z++){
					int www=j; flag=1;
					for(int y=1;y<strlen(w);y++){
						www+=z;
						if(www>t){
							flag=0;
							break;
						}
						if(w[y]!=x[www]){
							flag=0;
							break;
						}
					}
					if(flag==1){
						//cout<<"WWW"<<endl;
						c++;
						f=1;
						break;
					}
				}
			}
			if(f==1)break;
		}
	}
	cout<<c<<endl;
}

Measured memory_bytes: 3076
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

const int64_t MOD = 1'000'000'007L;

int64_t dpow(int64_t x, int64_t y)
{
    if (y == 0)
    {
        return 1;
    }
    if (y % 2 == 0)
    {
        return dpow(x * x % MOD, y / 2);
    }
    else
    {
        return x * dpow(x, y - 1) % MOD;
    }
}

int64_t inv(int64_t x)
{
    return dpow(x, MOD - 2);
}

int main()
{
    int64_t n, k;
    cin >> n >> k;

    vector<int64_t> a(n);
    rep(i, n)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    vector<int64_t> fact(n + 1);
    fact[0] = 1;
    rep(i, n)
    {
        fact[i + 1] = fact[i] * (i + 1) % MOD;
    }

    int64_t m = 0, M = 0;
    rep(i, n)
    {
        if (i >= k - 1)
        {
            int64_t comb = fact[i] % MOD * inv(fact[i - (k - 1)]) % MOD * inv(fact[k - 1]) % MOD;
            int64_t x = a[i];
            if (x < 0)
            {
                x = (x + MOD) % MOD;
            }
            M += x * comb % MOD;
            M %= MOD;

            int64_t y = a[n - 1 - i];
            if (y < 0)
            {
                y = (y + MOD) % MOD;
            }
            m += y * comb % MOD;
            m %= MOD;
        }
    }

    int64_t result = (M - m + MOD) % MOD;
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	string s;
	cin >> s;
	char tmp = s[0];
	int Count = 1;
	for(int i=1; i <=2; i++){
        if( s[i] == tmp ) ++Count;;
	}
	if(Count==3) cout << "No";
	else{
        cout << "Yes";
	}
 }


Measured memory_bytes: 256
#include"bits/stdc++.h"
#define int long long
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
typedef pair<int,int> P;
const int mod=1000000007;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}
void YN(bool flg){cout<<(flg?"YES":"NO")<<endl;}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<endl;}
void yn(bool flg){cout<<(flg?"yes":"no")<<endl;}
signed main(){
	char x,y;
	cin>>x>>y;
	if(x<y) cout<<'<'<<endl;
	else if(x==y) cout<<'='<<endl;
	else cout<<'>'<<endl;
}


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

#define float double
#define debug(x)// (cerr << #x << ": " << (x) << endl)

typedef long long ll;

#define int ll

using namespace std;

int32_t main() {

    int a, b, ab, x, y;
    cin >> a >> b >> ab >> x >> y;

    ll totalSum = 0;

    if(2 * ab < a + b){
        // fill with half pizzas

        totalSum += min(x, y) * ab * 2;
        debug(totalSum);

        ll m = min(x, y);
        x -= m;
        y -= m;
    }
    else{
        totalSum += min(x, y) * a;
        totalSum += min(x, y) * b;

          ll m = min(x, y);
        x -= m;
        y -= m;
    }

    debug(x);
    debug(y);

    // rest:
    int rest = max(x, y);
    int restPrice = -1;
    if(rest == x){
        restPrice = a;
    }else{
        restPrice = b;
    }

    debug(restPrice);
    debug(rest);
    debug(ab);


    if( restPrice < 2 * ab){
        // fill with restprice
        totalSum += restPrice * rest;
    }
    else{
        debug(ab * rest* 2);
        totalSum += ab * rest* 2;
    }

    cout << totalSum << endl;

}


Measured memory_bytes: 256
import sys

import bisect

# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd

import itertools

# from operator import attrgetter, itemgetter
import math

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    a = list(map(int, readline().split()))

    ans = 1
    rem = max(n - k, 0)
    ans += math.ceil(rem / (k - 1))

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 52508