akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <iterator>
#include <map>
#include <set>
#include <iomanip>
#include <vector>
#include <cstdint>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Graph = vector<vector<int>>;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, N) for(int i = 0; i < N; i++)
#define rep2(i, l, r) for (ll i = (ll)l; i < (ll)(r); i++)
#define INF 1000000000000000000
#define MAX 200001

const ll MOD = 1000000007;

template <typename T > inline string toString(const T &a) {ostringstream oss; oss << a; return oss.str();};

map<int,int> m;

int func(ll N,vector<ll> &A){
    vector<int> isPrime(1001,1);
    for(int i = 2; i < 1001; i++){
        if(isPrime[i] == 0) continue;
        for(int j = 2*i; j < 1001; j+=i){
            isPrime[j] = 0;
        }
    }
    int flag = 0;
    vector<int> check;
    for(int i = 2; i < 1001; i++){
        if(isPrime[i] == 1) check.push_back(i);
    }
    int s=check.size();
    rep(i,s){
        int now = check[i];
        int cnt = 0;
        for(int j = 0; j < N; j++){
            if(now > A[j]) continue;
            if(A[j]%now == 0){
                cnt++;
            }
            while(A[j]%now == 0) A[j] /= now;
        }
        m[now] = cnt;
    }
    rep(i,N){
        if(A[i] != 1) m[A[i]] += 1;
    }
    int MX = 0;
    for(auto mm:m){
        MX = max(MX, mm.second);
    }
    if(MX == N) flag = 0;
    else if(MX >= 2) flag = 1;
    else flag = 2;
    return flag;
}

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N) cin >> A[i];
    int flag = func(N,A);
    if(flag == 0){
        cout << "not coprime" << endl;
    }
    else if(flag == 1){
        cout << "setwise coprime" << endl;
    }
    else{
        cout << "pairwise coprime" << endl;
    }
}


Measured memory_bytes: 14780
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define MOD7 1000000007
#define LL_INF 1LL << 60
#define LL_MINF -1LL << 60
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const long double PI = (acos(-1));



int main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << min({a, b, c}) << ' ' <<a + b + c - min({a, b, c})-max({a,b,c}) << ' ' <<max({a,b,c}) << endl;
}


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

#define rep(i,n) for(int i = 0;i < n;++i)
#define rep2(i,n,m) for(int i = n;i < m;++i)
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;

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;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n,w=0;
    ll min = INF;
    cin >> n;
    vector<int> v(n);
    rep(i,n){
        cin >> v[i];
        if(min > v[i]){
             min = v[i];
             w++;
        }
    }
    cout << w <<endl;
    cout << endl;
    return 0;
}

Measured memory_bytes: 1024
// abc152_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N, M;
    cin >> N >> M;

    if (N == M){
        print("Yes");
    } else {
        print("No");
    }



    return 0;
}


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

int main(){
    int n, m, l;
    cin >> n >> m >> l;
    if (n < m && m < l) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <cstring>

using namespace std;

const int INF = 1e9 + 7;

int n;
vector<array<int, 3>> happy;
int dp[100000][4];

int dfs(int now, int before){
    if(now == n) return 0;
    if(~dp[now][before]) return dp[now][before];
    int res = 0;
    for(int i = 0; i < 3; i++){
        if(before == i) continue;
        res = max(res, happy[now][i] + dfs(now + 1, i));
    }
    return dp[now][before] = res;
}

int main(){
    cin >> n;
    happy.resize(n);
    memset(dp, -1, sizeof dp);
    for(auto&& i : happy){
        for(auto&& j : i){
            cin >> j;
        }
    }
    cout << dfs(0, 3) << "\n";
}


Measured memory_bytes: 10752
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node{
  unsigned int key;
  struct node *next;
  struct node *prev;
};

typedef struct node * NodePointer;

NodePointer nil;

NodePointer listSearch(int key){
  /* your code */
  NodePointer cur = nil->next;
  while( cur != nil && cur->key != key){
    cur = cur->next;
  }
  return cur;
}

void init(){
  nil = malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
}

void printList(){
  NodePointer cur = nil->next;
  int isf = 1;
  while(1){
    if ( cur == nil ) break;
    if ( isf == 0)  printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
    isf = 0;
  }
  printf("\n");
}

void deleteNode(NodePointer t){
  /* your code */
  if ( t == nil ) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

void deleteFirst(){
  NodePointer t = nil->next;
  if ( t == nil ) return;
  deleteNode(t);
}

void deleteLast(){
  /* your code */
  NodePointer t = nil->prev;
  if ( t == nil ) return;
  deleteNode(t);
}

void delete(int key){
  /* your code */
  deleteNode(listSearch(key));
}


void insert(int key){
  NodePointer x;
  x = malloc(sizeof(struct node));
  x->key = key;

  /* 

   your code 


  */
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

int main(){
  int key, n, i;
  int size = 0;
  char com[20];
  int np = 0, nd = 0;
  scanf("%d", &n);
  init();
  for ( i = 0; i < n; i++ ){
    scanf("%s%d", com, &key);
    if ( com[0] == 'i' ) {insert(key); np++; size++;}
    else if ( com[0] == 'd' ) {
      if (strlen(com) > 6){
	if ( com[6] == 'F' ) deleteFirst();
	else if ( com[6] == 'L' ) deleteLast();
      } else {
	delete(key); nd++; 
      }
      size--;
    }
  }

  printList();
  return 0;
}



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

int N,D,sum;
long long A,B;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>N>>D;
	for(int i = 1;i <= N;i++){
		cin>>A>>B;
		if(sqrt((A * A) + (B * B)) <= D) sum++;
	}
	cout<<sum<<endl;
}


Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const long long MOD=1000000007;
const long double Pi=acos(-1);
long long nature(long long a){//絶対値を返す
  if(a>=0){return(a);}
  else{return(-1*a);}
}
ll mod_pow(ll x,ll y){//x^yを返す//計算量は0(log(y))
  ll tmp=x,res=1;
  while(y){
    if(y%2){res=res*tmp%MOD;}
    y>>=1;
    tmp=tmp*tmp%MOD;
  }
  return res;
}
vector<long long> fact, fact_inv, inv;
void init_nCk(int n){
    fact.resize(n+54);
    fact_inv.resize(n+54);
    inv.resize(n+54);
    fact[0]=1;
    fact[1]=1;
    fact_inv[0]=1;
    fact_inv[1]=1;
    inv[1]=1;
    for(int i=2;i<n+54;i++){
        fact[i]=(fact[i-1]*i)%MOD;
        inv[i]=MOD-(inv[MOD%i]*(MOD/i))%MOD;
        fact_inv[i]=(fact_inv[i-1]*inv[i])%MOD;
    }
}
int nCk(int n,int k){
    return fact[n]*((fact_inv[k]*fact_inv[n-k])%MOD)%MOD;
}
int main(){
  #define int long long
  int N;
  cin>>N;
  vector<int> x(N);
  vector<int> y(N);
  for(int i=0;i<N;i++){
    int a,b;
    cin>>a>>b;
    x.at(i)=a-b;
    y.at(i)=a+b;
  }
  int mx=10000000000;
  int my=10000000000;
  int Mx=-10000000000;
  int My=-10000000000;
  for(int i=0;i<N;i++){
    mx=min(mx,x.at(i));
    my=min(my,y.at(i));
    Mx=max(Mx,x.at(i));
    My=max(My,y.at(i));
  }
  cout<<max(Mx-mx,My-my)<<endl;
}

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

#define MAX 100

int d[MAX], f[MAX], t = 0, M[MAX][MAX] = {}, n;

void dfs(){
    int seen[MAX] = {};
    rep(i, n){
        if(seen[i]) continue;
        stack<int> todo;
        seen[i] = 1;
        todo.push(i);
        t++;
        d[i] = t;
        while(!todo.empty()){
            int m = todo.top();
            rep(j, n + 1){
                if(j == n){
                    todo.pop();
                    t++;
                    f[m] = t;
                    break;
                }
                if(M[m][j] && !seen[j]){
                    todo.push(j);
                    t++;
                    d[j] = t;
                    seen[j] = 1;
                    break;
                }
            }
        }
    }
}

int main(){
    cin >> n;
    rep(i, n){
        int l, p;
        cin >> l >> p;
        rep(j, p){
            int q;
            cin >> q;
            M[l - 1][q - 1] = 1;
        }
    }
    dfs();
    
    rep(i, n){
        cout << i + 1 << " " << d[i] << " " << f[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
    int n;
    cin>>n;
    ll arr[n];
    for(int i=0; i<n; i++) cin>>arr[i];
    ll ans = 0;
    for(int i=1; i<n; i++) {
        int x = max((ll)0, arr[i-1] - arr[i]);
        arr[i] += x;
        ans += x;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 5156
#include<iostream>
#include<algorithm>
#include<vector>

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

using namespace std;

int main(){

  int n,k,x,sum=0;
  vector<int> l;

  cin>>n>>k;

  REP(i,n){
    cin>>x;
    l.push_back(x);
  }

  sort(l.begin(),l.end(),greater<int>());

  REP(i,k){
    sum+=l[i];
  }
 
  cout<<sum<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
	int a, b, c;
	int i, count = 0;

	scanf("%d %d %d", &a, &b, &c);
	for (i = a; i <= b; i++){
		if (c%i == 0){
			count++;
		}
	}
	printf("%d\n", count);

	return 0;
}

Measured memory_bytes: 596
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;
int n,q;
string s;
void solve()
{
    int k;
    cin>>k;
    int d,m,dm,ses;
    ses=d=m=dm=0;
    f(i,1,n)
    {
       if(i-k>=1)
       {
          if(s[i-k]=='D')dm-=m,d--;
          else if(s[i-k]=='M')m--;
       }
       if(s[i]=='D')d++;
       else if(s[i]=='M')m++,dm+=d;
       else if(s[i]=='C')ses+=dm;
    }
    cout<<ses<<endl;
}
 main()

{
    fast
    cin>>n>>s>>q;
    s="#"+s;
    while(q--)
    {
        solve();
    }
    return 0;

}





































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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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 (a>b) { a=b; return 1; } return 0; }

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin>>S;
    int N = S.size();
    int ans=0;
    int cur=0;
    rep(i,N){
        if (S[i]=='R') cur++;
        else cur=0;
        chmax(ans,cur);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3632
function Main(input) {
  // input = input.replace(/\n/g, ' ');
  // input = input.split(" ");
  input = input.split("");
  if(input[0]==input[1] && input[1]==input[2]){
    console.log("No");
  }else{
    console.log("Yes");
  }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
/*   ꧁༒☬महाकाल☬༒꧂ ꧁༒ঔमहाकालঔ༒꧂
                   
                   ঔৣ۝महाकालᴳᵒᵈ۝ঔৣ            
 
 */ 
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//template <typename T, typename cmp=less<T>> using oset =tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long 
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define _it iterator
#define all(_x) _x.begin(),_x.end()
#define f first
#define s second
#define pb push_back
void mahakal(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	freopen("error.txt","w",stderr);
	#endif
}
int main(){
	//mahakal(),fast;
	
	ll n , m ,mm,nn;
	cin>> nn >> mm ;
	if(nn==1 || mm==1 ){
		cout<<1<<endl;
		return 0;
	}
	n=max(nn , mm );
	m=min(nn,mm);
	ll st=(n-1)/2 +1 ;
	ll nd = (n-2)/2 +1 ;
	ll ans = (ll)ceil(m/2.0) * st + (m/2) * nd;
	cout<<ans<<endl;  

	return 0;
}

Measured memory_bytes: 256
x,n = map(int, input().split())
st = set(list(map(int, input().split())))
incr = 0
ans = 0
while True:
    now = x - incr
    if now not in st:
        ans = now
        break
    now = x + incr
    if now not in st:
        ans = now
        break
    incr += 1
print(ans)

Measured memory_bytes: 8976
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <cstring>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
template< typename T >
struct edge {
    int src, to;
    T cost;

    edge(int to, T cost) : src(-1), to(to), cost(cost) {}

    edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

    edge &operator=(const int &x) {
        to = x;
        return *this;
    }

    operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
pair< T, int > dfs(const WeightedGraph< T > &g, int idx, int par) {
    pair< T, int > ret(0, idx);
    for(auto &e : g[idx]) {
        if(e.to == par) continue;
        auto cost = dfs(g, e.to, idx);
        cost.first += e.cost;
        ret = max(ret, cost);
    }
    return ret;
}

template< typename T >
T tree_diameter(const WeightedGraph< T > &g) {
    auto p = dfs(g, 0, -1);
    auto q = dfs(g, p.second, -1);
    return (q.first);
}

signed main() {
    int N;
    cin >> N;
    WeightedGraph< int > g(N);
    for(int i = 1; i < N; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        g[x].emplace_back(y, 1);
        g[y].emplace_back(x, 1);
    }

    int d = tree_diameter(g);

    if (d % 3 == 1) {
        cout << "Second" << endl;
    } else {
        cout << "First" << endl;
    }

    return 0;
}

Measured memory_bytes: 33024
from collections import deque
def RRS(N, P, q):
    end = []
    P_deq = deque(P)
    now = 0
    while(len(P_deq) != 0):
        P_n, P_t = P_deq.popleft()
        if P_t > q:
            P_t -= q
            now += q
            P_deq.append([P_n, P_t])
        else:
            now += P_t
            end.append([P_n, now])
    for p in end:
        print(*p)
    return 0

if __name__ == '__main__':
    N, q = map(int, input().split())
    A = [None]*N
    for i in range(N):
        p, t = map(str, input().split())
        A[i] = [p, int(t)]
    RRS(N, A, q)



Measured memory_bytes: 19580
#include <functional>
#include <iomanip>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include<complex>
#include <numeric>
#include <string>
#include<iostream>
#include <fstream>
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include<cmath>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <sstream>
using namespace std;
const double PI = acos(-1.0);
const double  EPS = 1e-11;
typedef long long ll;
//freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
void fast()
{
	std::ios_base::sync_with_stdio(0);
}
int main()
{
	int n;
	cin >> n;
	vector<int>arr(n);
	vector<int>temp(n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
		temp[i]= arr[i];
	}
	sort(arr.begin(), arr.end());
	int ind1 = arr[(n / 2) - 1], ind2 = arr[(n / 2)];
	for (int i = 0; i < n; i++)
	{
		if (temp[i] <= ind1)
		{
			cout << ind2<< endl;
		}
		else
		{
			cout << ind1  << endl;
		}
	}
	return 0;
}

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

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

    int H[N];

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

    int count = 1;
    
    for (int i = 1; i < N; i++)
    {
        bool visible = true;
        for (int j = 0; j < i; j++)
        {
            if (H[j] > H[i])
            {
                visible = false;
                
            }
        }
        if (visible == true)
        {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The Value Of " << #val << " is : " << val << '\n';
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 2e5+5;
ll n, k, arr[nax];
set<ll>s;
vector<ll>store;
vector<ll>cnt(nax);
bool vis[nax];
	
int main(){
	IOS
	cin >> n >> k;
	for(int i=0;i<n;i++){
		cin >> arr[i];
		cnt[arr[i]]++;
		s.insert(arr[i]);
	}
	for(int i=0;i<n;i++){
		if(vis[arr[i]]) continue;
		vis[arr[i]]=1;
		store.pb(cnt[arr[i]]);
	}
	sort(store.begin(), store.end());
	ll ans=0, sais=s.size();
	if(sais<=k){
		cout << 0 << '\n';
		return 0;
	}
	for(int i=0;i<(sais-k);i++){
		ans+=store[i];
	}
	cout << ans << '\n';
}


Measured memory_bytes: 17892
def main():

    N = int(input())
    B = list(map(int, input().split()))
    total = 0
    A = [0] * N
    A[0] = B[0]
    total += A[0]
    for i in range(1, N - 1):
        A[i] = min(B[i], B[i - 1])
        total += A[i]
    A[N - 1] = B[N - 2]
    total += A[N - 1]
    print(total)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

int main() {
  int n;
  std::vector<int> l(100);

  std::cin >> n;
  for(int i = 0; i < n; ++i) {
    std::cin >> l[i];
  }

  std::sort(l.begin(), l.begin()+n);

  std::cout << ((l[n-1] < std::accumulate(l.begin(), l.begin()+n-1, 0)) ? "Yes" : "No") << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N (long long)(1e9 + 7)
#define MAX 500000
using namespace std;

long long factorial[MAX] = {0}, finverse[MAX] = {0},
          inverse[MAX] = {0};

void smodfact() {
  factorial[0] = factorial[1] = 1;
  finverse[0] = finverse[1] = 1;
  inverse[1] = 1;
  for(int i = 2; i < MAX; ++i) {
    factorial[i] = factorial[i - 1] * i % N;
    inverse[i] = N - (inverse[N % i] * (N / i)) % N;
    finverse[i] = finverse[i - 1] * inverse[i] % N;
  }
}

long long calccomb(long long n, long long k) {
  if(n == k && n == 0) return 1;
  if(n < 0 || k < 0 || n < k) return 0;
  return factorial[n] * finverse[k] % N * finverse[n - k] %
         N;
}

long long n, m;

long long solve();

int main() {
  smodfact();
  cin >> n >> m;
  if(n < m) swap(n, m);
  cout << solve() << endl;
  return 0;
}

long long solve() {
  if(n - m > 1) return 0;
  long long ans = 0;
  ans = factorial[n] * factorial[m] % N;
  if(n == m) return 2 * ans % N;
  return ans;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N, 0);
  int x;
  rep(i, N-1){
    cin >> x;
    x--;
    vec.at(x)++;
  }
  rep(i, N){
   cout << vec.at(i) << endl; 
  }
  return 0;
}

Measured memory_bytes: 3996
#template
def inputlist(): return [int(j) for j in input().split()]
from collections import Counter
#template
#issueから始める
N = int(input())
s = list(input())
ans = -1
for i in range(N):
    lif = s[:i]
    lib = s[i:]
    cf= list(Counter(lif).keys())
    cb= list(Counter(lib).keys())
    k = len(cf) + len(cb) - len(set(cf+cb))
    ans = max(ans,k)
print(ans)

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

int main() {
	long long h, w;
	cin >> h >> w;
	if (h == 1 || w == 1) {
		cout << 1 << endl;
		return 0;
	}
	long long h1 = (w + 1) / 2;
	long long h2 = w / 2;
	long long w1 = (h + 1) / 2;
	long long w2 = h / 2;
	cout << h1 * w1 + h2 * w2 << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 10000
typedef pair<int,int> P;

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

int main(){
    int h,w;
    cin >> h >> w;
    char s[100][100];
    int dist[100][100];

    rep(i,h){
        rep(j,w){
            cin >> s[i][j];
            dist[i][j]=INF;
            if(s[i][j]=='#')numWall++;
        }
    }

    queue<P> que;
    que.push(P(0,0));
    dist[0][0]=1;
    while(que.size()){
        P p=que.front();que.pop();
        if(p.first==h-1 && p.second==w-1){
            break;
        }
        rep(i,4){
            int nx=p.first+dx[i],ny=p.second+dy[i];
            if(0<=nx && nx<h && 0<=ny && ny<w && s[nx][ny]!='#' && dist[nx][ny]==INF){
                dist[nx][ny]=dist[p.first][p.second]+1;
                que.push(P(nx,ny));
            }
        }
    }

    ans=h*w-(numWall+dist[h-1][w-1]);
    if(dist[h-1][w-1]==INF)ans=-1;
    cout << ans << endl;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  int ans = 0;
  for (int i = 1; i * i <= m; i++) {
    if (m % i == 0) {
      if ((m / i) * n <= m) {
        ans = m / i;
        break;
      } else if (i * n <= m) {
        ans = i;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x,note=0x3f;
}a[100005]; 
int main()
{ 
    int n,ans=1;
    cin>>n; 
    for(int i=1;i<=n;i++)
	{
        cin>>a[i].x;
    }
    a[1].note=2;
    for(int i=2;i<=n;i++)
	{
        if(a[i-1].note==0)
		{
            if(a[i].x>a[i-1].x) a[i].note=2,ans++;
              else a[i].note=0;
        }
		else if(a[i-1].note==1)
		{
            if(a[i].x>=a[i-1].x) a[i].note=1;
              else a[i].note=2,ans++;
        }
		else if(a[i-1].note==2)
		{
            if(a[i].x<a[i-1].x) a[i].note=0;
              else if(a[i].x==a[i-1].x) a[i].note=2;
                else a[i].note=1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,_4,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n,s) for (int i=a;s>0?i<n:i>n;i+=s)
#define rep(...) _overload3(__VA_ARGS__,per,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
const int inf = 1e9+10, mod = 1e9+7; const long long llinf = 1e18;
// head

int main(){
  int n,a=0,b=0 ;
  int A,B;
  cin >> n >> A >> B;
  string s;
  cin >> s;
  rep(i,s.size()){
    if (s[i] == 'a' and a+b<A+B){a ++;cout << "Yes" << endl;}
    else if (s[i] == 'b' and a+b < A+B and b < B){ b++ ;cout << "Yes" << endl;} 
    else cout << "No" << endl;
  }
}

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

using ll = long long;

ll modpow(ll a, ll n, ll mod) {
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret = ret * a % mod;
	a = a * a % mod;
	n >>= 1;
  }
  return ret;
}

ll modnCk(ll n, ll k, ll mod) {
  ll ret = 1, x = 1, y = 1;
  for (ll i=0; i<k; i++) {
    x *= n - i;
	x = x % mod;
	
	y *= k - i;
	y = y % mod;
  }
  ret = modpow(y, mod - 2, mod) % mod;
  ret = x * ret % mod;
  return ret;
}

int main() {
  ll mod = 1e9+7;
  ll n, a, b;
  cin >> n >> a >> b;
  ll ans;
  ans = modpow(2, n, mod) - 1;
  ans -= modnCk(n, a, mod) + modnCk(n, b, mod);
  cout << (ans % mod + mod) % mod << endl;
  return 0;
}


Measured memory_bytes: 384
package main

import (
	"bufio"
	"os"
	"strconv"
	"fmt"
)

var scanner = bufio.NewScanner(os.Stdin)


func nextInt() int {
	scanner.Scan()
	i, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func count(ints []int, target int) int {
	var ret int
	for _, v := range ints {
		if v == target {
			ret++
		}
	}
	return ret
}
func main() {
	scanner.Split(bufio.ScanWords)
	n := nextInt()
	a := make([]int, n)
	for i := range a {
		a[i] = nextInt()
	}
	q := nextInt()
	for i := 0; i < q; i++ {
		b := nextInt()
		e := nextInt()
		k := nextInt()
		fmt.Printf("%d\n", count(a[b:e], k))
	}
}


Measured memory_bytes: 1136
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits> 
int main()
{
    long X;
    std::cin >> X;
    std::cout << (X/500)*1000+(X-(X/500)*500)/5*5 << std::endl;
    return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>
#include<cmath>
#include<iomanip>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
typedef long long ll;
int main() {
	int N;
	ll H, W;
	cin >> N >> H >> W;
	vector<ll>A(N), B(N);
	ll ans = 0;
	rep(i, N) {
		cin >> A[i] >> B[i];
	}
	rep(i, N) {
		ans += min(A[i] / H, B[i] / W);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	var sc = bufio.NewScanner(os.Stdin)
	maxSize := 300000 * 2
	buf := make([]byte, maxSize)
	sc.Buffer(buf, maxSize)
	n := scanLineInt(sc)
	s := scanLineStr(sc)

	var count int
	for i := 0; i < n; i++ {
		if s[i] == 'E' {
			count++
		}
	}

	result := count
	for i := 0; i < n; i++ {
		if s[i] == 'E' {
			count--
		}
		if i > 0 && s[i-1] == 'W' {
			count++
		}
		result = min(result, count)
	}
	fmt.Println(result)
}

func scanLineStr(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func scanLineInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}


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

int main() {
  string s,t; cin>>s>>t;
  int ans=0;
  for(int i=0; i<s.length(); i++) {
    if(s[i]!=t[i]) ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3916
from collections import deque
K = int(input())

que = deque(list(range(1, 10)))

c = 0
while len(que):
    x = que.popleft()
    c += 1
    for m in range(max(0, x % 10 - 1), min(9, x % 10 + 1) + 1):
        que.append(10*x+m)
    
    if c == K:
        print(x)
        break    

Measured memory_bytes: 47580
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
ll MOD=1000000007;
int inf=1000000000;
ll INF=10000000000000000;
int main(){
    int n;
    cin >> n;
    vector<int> a(0);
    int t;
    cin >> t;
    a.push_back(t);
    rep(i,n-1){
        cin >> t;
        if (t==a.at(a.size()-1)) continue;
        a.push_back(t);
    }
    ll ans=1;
    map<int,ll> m;
    rep(i,a.size()){
        int k=a.at(i);
        auto it=m.find(k);
        if (it==m.end()) m[k]=ans;
        else {
            ll u=m[k];
            m[k]=(m[k]+ans)%MOD;
            ans=(ans+u)%MOD;
        }
        //cout << ans << endl;
    }
    cout << ans << endl;
}

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

int main() {
   int p, q, r;
   cin >> p >> q >> r;
   int ans = p + q + r - max({p, q, r});
   cout << ans << endl;
   return 0;
}

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

using namespace std;
vector<long long> factors;
#define ll long long


#define pii pair<int,int>
#define pll pair<ll,ll>
#define _ <<'\n'
#define __ << ' '
#define all(x) (x).begin(), (x).end()
#define gcd __gcd
int IT_MAX = 1 << 17;
int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const double ERR = 1e-10;
#define szz(x) (int)(x).size()
#define IOS ios_base::sync_with_stdio(false); cout.tie(0);cin.tie(0);
#define flush fflush(stdout)

ll mod(ll a, ll m)
{ return (a + (abs(a) / m) * m + m) % m; }

//****************************don't use int!!!!!!!****************************//
//***************************code starts here!!!!!****************************//

struct elem
{
	int use = 0;
	ll val;
};

ll check_s(ll a, ll b, ll c, vector<elem> vec)
{
	ll as = 0, bs = 0, cs = 0;
	ll ac = 0, bc = 0, cc = 0;
	bool checka = false;
	bool checkb = false;
	bool checkc = false;
	for (int i = 0; i < vec.size(); ++i)
	{
		if (vec[i].use == 1)
		{
			as += vec[i].val;
			++ac;
			checka = true;
		} else if (vec[i].use == 2)
		{
			bs += vec[i].val;
			++bc;
			checkb = true;
		} else if (vec[i].use == 3)
		{
			cs += vec[i].val;
			++cc;
			checkc = true;
		}
	}
	if(checka && checkb && checkc)
	return 10 * (ac - 1) + 10 * (bc - 1) + 10 * (cc - 1) + abs(a - as) + abs(b - bs) + abs(c - cs);
	else{
		return LL_INF;
	}
}

ll f_min(ll a,ll b, ll c, vector<elem> vec, int pos){
	if(pos == vec.size()){
		return check_s(a,b,c,vec);
	}else{
		ll mn= LL_INF;
		for(int i = 0; i < 4; ++i){
			vec[pos].use = i;
			ll temp = f_min(a,b,c,vec,pos+1);
			if(temp < mn){
				mn = temp;
			}
		}
		return mn;
	}
}

int main()
{
	IOS

	ll a, b, c;
	ll n;
	cin >> n;
	cin >> a >> b >> c;
	vector<elem> l(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> l[i].val;
	}

	cout << f_min(a,b,c,l,0);

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  long long n;
  long long a,b,t,x=0,y=0;
  long long ans=99999999999;
  cin>>n;
  


  for(long long i=1;i*i<=n;++i){
    if(n%i>0)continue;

    x=y=0;
    
    a =i;
    
    while(a){
      a/=10;
      x++;
    }
    
    b=n/i;

    
    while(b){
      b/=10;
      y++;
    }
    if(x>y)t=x;
    else t=y;
    
    if(t<ans) ans=t;
  }
  cout <<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
    int A[3][3];
    int a[3][3];
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            cin >> A[i][j];
            a[i][j] = 0;//not open
        }
    }
    int N;
    cin >> N;
    int b[N];
    for(int i = 0; i < N; i++){
        cin >> b[i];
    }
    for(int k = 0; k < N; k++){
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(A[i][j] == b[k]){
                    a[i][j] = 1;//open
                }
            }
        }
    }

    //check
    bool check = false;
    for(int i = 0; i < 3; i++){
        if(a[i][0] == 1 && a[i][1] == 1 && a[i][2] == 1){
            check = true;
        }
    }
    for(int i = 0; i < 3; i++){
        if(a[0][i] == 1 && a[1][i] == 1 && a[2][i] == 1){
            check = true;
        }
    }

    if(a[1][1] == 1 && a[2][2] == 1 && a[0][0] == 1){
        check = true;
    }
    if(a[0][2] == 1 && a[1][1] == 1 && a[2][0] == 1){
        check = true;
    }

    cout << ((check)?"Yes":"No") << endl;




}

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

bool flag[20][20]={false};
char mass[20][20]={'0'};
int cnt=0;

bool solve(int y,int x)
{
	if(flag[y][x]) return false;
	else flag[y][x]=true;
	
	if(mass[y][x-1]=='1' && !flag[y][x-1]) solve(y,x-1);
	if(!flag[y][x+1] && mass[y][x+1]=='1') solve(y,x+1);
	if(!flag[y+1][x] && mass[y+1][x]=='1') solve(y+1,x);

	return true;
}

int main()
{
	while(cin>>mass[0]){
		for(int i=1;i<12;i++) cin>>mass[i];

		for(int i=0;i<12;i++){
			for(int j=0;j<12;j++){
				if(mass[i][j]=='1' && solve(i,j)) cnt++;
			}
		}

		for(int i=0;i<20;i++){
			for(int j=0;j<20;j++){
				flag[i][j]=false;
			}
		}

		cout<<cnt<<endl;

		cnt=0;
	}
	return 0;
}

		

Measured memory_bytes: 1144
//
// Created by yuu on 2019-08-18.
//

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <math.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <iomanip>

using namespace std;

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

    double temp = 0;

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

    cout<<std::setprecision(10)<<1.0/temp<<endl;


    return 0;
}

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

typedef long long ll;
const int N = 16, mod = 1000000007;
int n, m, a[N], f[N + 1][1 << N], fac[(1 << N) + 1], inv[(1 << N) + 1];
int C(int x, int y) {return x < y || y < 0 ? 0 : (ll) fac[x] * inv[y] % mod * inv[x - y] % mod;}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d", &a[i]);
  }
  fac[0] = fac[1] = 1;
  inv[0] = inv[1] = 1;
  for (int i = 2; i <= 1 << n; i++) {
    fac[i] = (ll) fac[i - 1] * i % mod;
    inv[i] = mod - (ll) mod / i * inv[mod % i] % mod;
  }
  for (int i = 2; i <= 1 << n; i++) {
    inv[i] = (ll) inv[i] * inv[i - 1] % mod;
  }
  sort(a, a + m, greater<int>());
  f[0][0] = 1;
  for (int i = 0; i < m; i++) {
    for (int s = 0; s < 1 << n; s++) if (f[i][s]) {
      f[i + 1][s] = (f[i + 1][s] + f[i][s]) % mod;
      for (int j = 0; j < n; j++) if (!(s >> j & 1)) {
        f[i + 1][s | 1 << j] = (f[i + 1][s | 1 << j] + (ll) f[i][s] * C((1 << n) - a[i] - s, (1 << j) - 1) % mod * fac[1 << j]) % mod;
      }
    }
  }
  int ans = 0;
  for (int s = 0; s < 1 << n; s++) if (f[m][s]) {
    ans = (ans + (ll) (__builtin_parity(s) ? mod - 1 : 1) * f[m][s] % mod * fac[(1 << n) - s - 1]) % mod;
  }
  ans = (ll) ans * (1 << n) % mod;
  printf("%d\n", ans);
}


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

#include <set>
#include <iterator>
using namespace std;
// using namespace __gnu_pbds;


#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)
#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define INF (ll)1e17
#define matrix vector<vector<ll> >

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )
#define maxbits 9
#define maxmask (1ll<<maxbits)
// typedef tree<pll, null_type, less<pll>, rb_tree_tag,
//              tree_order_statistics_node_update>
//     new_data_set;
const int  N=1e6 +10, M=(ll)1e9+1 ;
const int mod =(ll)1e9+7 ,sz=5, MAX=(ll)1e6+10;
string fir="Monocarp",sec="Bicarp";

void work(){
	ll n;
	cin >> n;
	string s;
	cin >> s;
	ll ans=0;
	ll r,g,b;
	r=(s[0]=='R');
	g=(s[0]=='G');
	b=(s[0]=='B');
	ll tot_r,tot_g,tot_b;
	tot_r=tot_b=tot_g=0;
	// tot_r=r;
	// tot_g=g;
	// tot_b=b;
	for(ll i=0;i<n;i++){
		for(ll j=1;j<=4000;j++){
			ll l=i-j,r=i+j;
			if(l<0 || r>=n)
				break;
			if(s[l]!=s[i] && s[i]!=s[r] && s[l]!=s[r])
				ans--;
		}

		tot_r+=(s[i]=='R');
		tot_g+=(s[i]=='G');
		tot_b+=(s[i]=='B');
	}

	// cout << tot_r << " " << tot_g << " " << tot_b << "\n";

	for(ll i=1;i<n-1;i++){
		if(s[i]=='R')
			ans+=b*(tot_g-g)+g*(tot_b-b);
		else if(s[i]=='G')
			ans+=r*(tot_b-b)+b*(tot_r-r);
		else 
			ans+=r*(tot_g-g)+g*(tot_r-r);

		r+=(s[i]=='R');
		g+=(s[i]=='G');
		b+=(s[i]=='B');
	}

	cout << ans;
}

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

	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	// precomp();
	ll t;
	// cin >> t;
	t=1;
	while(t--){
	        work();
	
	}

	return 0;
}
	

Measured memory_bytes: 3664
#include<bits/stdc++.h>
#define eps 1e-9
#define MOD 1000000007;
#define INV_10 299473306;
using namespace std;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int k, pos=0, l;
	cin >> k;
	vector<string>v;
	for(char c='1'; c <= '9'; c++)
	{
		string s="";
		s+=c;
		v.push_back(s);
	}
	while(v.size() < k)
	{
		l=v.size();
		for(int i = pos; i < l; i++)
		{
			string s=v[i];
			if(s!="0")
			    ;
			if(s.back()!='0')
			{
				s+=(char)(s.back()-1);
				v.push_back(s);
				s.pop_back();
			}
			s+=(char)(s.back());
				v.push_back(s);
			s.pop_back();
			if(s.back()!='9')
			{
				s+=(char)(s.back()+1);
				v.push_back(s);
				s.pop_back();
			}
		}
		pos=l;
	}
	cout << v[k-1] << '\n';
}

Measured memory_bytes: 13936
from operator import itemgetter


class UnionFindTree():
    def __init__(self, N):
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def __root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.__root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.__root(a)
        r2 = self.__root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.__root(a) == self.__root(b)

    def size(self, a):
        return self.__size[self.__root(a)]

    def groups(self):
        groups = {}
        for k in self.__parent_of.keys():
            r = self.__root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N = int(input())
    X = [None] * N
    Y = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        X[i] = (x, i)
        Y[i] = (y, i)
    X.sort(key=itemgetter(0))
    Y.sort(key=itemgetter(0))
    adj = [None] * (2*N - 2)
    for i in range(N-1):
        adj[2*i] = (X[i+1][0] - X[i][0], X[i][1], X[i+1][1])
        adj[2*i+1] = (Y[i+1][0] - Y[i][0], Y[i][1], Y[i+1][1])
    adj.sort(key=itemgetter(0))
    uft = UnionFindTree(N)
    ans = 0
    for pair in adj:
        cost, a, b = pair
        if not uft.is_same(a, b):
            uft.unite(a, b)
            ans += cost
        if uft.size(a) == N:
            break
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 136920
#include<iostream>   
#include<cstdio>  
#include<algorithm>
#include<queue>
#include<map>
#include<string>
using namespace std;
const int row = 4;
const int maxx = 16;
const int LIMIT = 100;
struct Puzzle {
    int f[maxx], space, MD;
};

const int dx[4] = { 0, -1, 0, 1 };
const int dy[4] = { 1, 0, -1 ,0 };
const char dir[4] = { 'r','u','l','d' };
int MDT[maxx][maxx];

Puzzle state;
int limit;
int path[LIMIT];

int getAllMD(Puzzle pz) {
    int sum = 0;
    for (int i = 0; i < maxx; i++) {
        if (pz.f[i] != maxx)
            sum += MDT[i][pz.f[i] - 1];
    }
    return sum;
}

bool isSolved() {
    for (int i = 0; i < maxx; i++)
        if (state.f[i] != i + 1)
            return false;
    return true;
}

bool dfs(int depth, int prev) {

    if (state.MD == 0)
        return true;

    // 如果当前的深度加上启发值超过了限制，则进行剪枝
    if (depth + state.MD > limit)
        return false;

    int sx = state.space / row;
    int sy = state.space % row;

    Puzzle tmp;
    for (int r = 0; r < 4; r++) {
        int tx = sx + dx[r];
        int ty = sy + dy[r];
        if (tx < 0 || ty < 0 || tx >= row || ty >= row)
            continue;
        if (max(prev, r) - min(prev, r) == 2)
            continue;
        tmp = state;
        // 计算曼哈顿距离的差值，同时交换拼图
        state.MD -= MDT[tx * row + ty][state.f[tx * row + ty] - 1];
        state.MD += MDT[sx * row + sy][state.f[tx * row + ty] - 1];
        swap(state.f[tx * row + ty], state.f[sx * row + sy]);
        state.space = tx * row + ty;
        if (dfs(depth + 1, r)) {
            path[depth] = r;
            return true;
        }
        state = tmp;
    }
    return false;
}

string iterative_deepening(Puzzle in) {
    // 初始状态的曼哈顿距离
    in.MD = getAllMD(in);
    for (limit = in.MD; limit <= LIMIT; limit++) {
        state = in;
        if (dfs(0, -100)) {
            string ans = "";
            for (int i = 0; i < limit; i++)
                ans += dir[path[i]];
            return ans;
        }
    }
    return "unsolvable";
}

int main()
{
    for (int i = 0; i < maxx; i++) {
        for (int j = 0; j < maxx; j++) {
            MDT[i][j] = abs(i / row - j / row) + abs(i % row - j % row);
        }
    }
    Puzzle in;
    for (int i = 0; i < maxx; i++) {
        cin >> in.f[i];
        if (in.f[i] == 0) {
            in.f[i] = maxx;
            in.space = i;
        }
    }
    string ans = iterative_deepening(in);
    printf("%d\n", ans.size());
    return 0;
}



Measured memory_bytes: 3336
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000

int N, M, numCC;
vector<int> adj[MAXN + 3];
bool visited[MAXN + 3];

void DFS(int u) {
    visited[u] = true;
    for (auto v: adj[u]) {
        if (visited[v] == false)
            DFS(v);
    }
}

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

    for (int i = 1; i <= M; i++) {
        int X, Y, Z;
        cin >> X >> Y >> Z;

        adj[X].push_back(Y);
        adj[Y].push_back(X);
    }

    memset(visited, false, sizeof(visited));

    numCC = 0;
    for (int i = 1; i <= N; i++) {
        if (visited[i] == false) {
            numCC += 1;
            DFS(i);
        }
    }

    cout << numCC << endl;
}


Measured memory_bytes: 8960
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll modpow(ll x, ll n){
    ll res = 1;
    ll mul = x;
    while(n){
        if(n % 2) res = res * mul % MOD;
        mul = mul * mul % MOD;
        n /= 2;
    }
    return res;
}

struct Combination
{
    int maxn;
    vector<ll> fmemo;
    vector<ll> imemo;
    vector<ll> ifmemo;
    
    Combination(int maxn) : maxn(maxn){
        fmemo.resize(maxn + 1);
        imemo.resize(maxn + 1);
        ifmemo.resize(maxn + 1);
        for(ll i = 1; i <= maxn; i++){
            imemo[i] = modpow(i, MOD - 2);
        }
    }

    ll fact(ll n){
        if(n == 0) return 1;
        if(fmemo[n]) return fmemo[n];
        return fmemo[n] = n * fact(n - 1) % MOD;
    }

    ll ifact(ll n){
        if(n == 0) return 1;
        if(ifmemo[n]) return ifmemo[n];
        return ifmemo[n] = imemo[n] * ifact(n - 1) % MOD;
    }

    ll com(ll n, ll k){
        if(k > n) return 0;
        if(k == n || k == 0) return 1;
        return (fact(n) * ifact(k) % MOD) * ifact(n - k) % MOD;
    }
};

int main()
{
    ll r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;
    Combination com(2000003);
    ll ans = 0;
    for(int i = r1 + 1; i <= r2 + 1; i++) ans = (ans + com.com(c2 + i, i)) % MOD;
    for(int j = 1; j <= c1; j++) ans = (ans + MOD - com.com(r2 + j, j)) % MOD;
    for(int i = 1; i <= r1; i++) ans = (ans + com.com(c1 + i - 1, i)) % MOD;
    cout << ans << endl;
}

Measured memory_bytes: 93952
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
inline char tc(void){
	static char fl[10000],*A=fl,*B=fl;
	return A==B&&(B=(A=fl)+fread(fl,1,10000,stdin),A==B)?EOF:*A++;
}
inline int read(void){
	int a=0;char c;
	while((c=tc())<'0'||c>'9');
	while(c>='0'&&c<='9')a=a*10+c-'0',c=tc();
	return a;
}
int mx,n,a[52],b[52],mp[52][52];
ll ans;
bool dfs(int x,int y){
	if(x==b[y])return 1;
	bool ans=0;
	for(int i=b[y];i<x;++i)
		if(mp[x][i]){
			ans|=dfs(i,y);
			if(ans)break;
		}
	return ans;
}
int main(void){
	register int i,j;
	n=read();
	for(i=1;i<=n;++i)a[i]=read(),mx=max(mx,a[i]);
	for(i=1;i<=n;++i)b[i]=read();
	for(i=1;i<=mx;++i)
		for(j=1;j<=mx;++j)
			mp[i][i%j]+=1;
	for(j=1;j<=n;++j)
		if(!dfs(a[j],j)){
			puts("-1");
			return 0;
		}
	for(i=mx;i;--i){
		for(j=1;j<=mx;++j)
			mp[j][j%i]-=1;
		bool b=1;
		for(j=1;j<=n;++j)
			if(!dfs(a[j],j)){
				b=0;break;
			}
		if(b==0){
			for(j=1;j<=mx;++j)
				mp[j][j%i]+=1;
			ans+=1ll<<i;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

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

int main() {
int N ;
  cin >> N ;
  vector<int> vec(N);

  for (int i = 0; i < N; i++)
    cin >> vec.at(i);
  
  sort(vec.begin(), vec.end()) ;
  reverse(vec.begin(), vec.end()) ;
  int A, B;
  A = 0;
  B = 0;
  for(int i = 0; i < N; i+=2)
    A += vec.at(i);
  for(int i = 1; i < N; i+=2)
    B += vec.at(i);
  
 cout << A -B << endl;
}

Measured memory_bytes: 384