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

const long long MOD = 998244353;

int A[3005];
long long pow2[3005];

long long memo[3005][3005];

long long dp(int i, int j){
    if(j == 0){
        return pow2[i];
    }else if(i == 0){
        return 0;
    }else if(memo[i][j] != -1){
        return memo[i][j];
    }else{
        long long ans = 0;

        // ignore
        if(i > 0){
            ans += 2*dp(i-1, j);
        }

        // take
        if(j >= A[i-1]){
            ans += dp(i-1, j-A[i-1]);
        }

        return memo[i][j] = ans%MOD;
    }
}

int main(){
    int N, S;
    scanf("%d%d", &N, &S);

    for(int i = 0; i < N; i ++){
        scanf("%d", &A[i]);
    }

    pow2[0] = 1;
    for(int i = 1; i <= N; i ++){
        pow2[i] = 2*pow2[i-1]%MOD;
    }

    memset(memo, -1, sizeof(memo));
    printf("%lld", dp(N, S));
    return 0;
}


Measured memory_bytes: 74576
#include<cstdio>
#include<algorithm>

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

using namespace std;

typedef long long ll;

template<class T>
class segment_tree_RMQ{
	static const int N_MAX=1<<17;
	int n;
	T dat[2*N_MAX];

	T query(int l,int r,int a,int b,int u){
		if(l<=a && b<=r) return dat[u];

		T res=0;
		int c=(a+b+1)/2;
		if(l<c && a<r) res=max(res,query(l,r,a,c,2*u));
		if(l<b && c<r) res=max(res,query(l,r,c,b,2*u+1));
		return res;
	}

public:
	void build(int N,T val){
		for(n=1;n<N;n*=2);
		rep(u,2*n) dat[u]=val;
	}

	void update(int u,T v){
		u+=n;
		dat[u]=v;
		for(u/=2;u>=1;u/=2) dat[u]=max(dat[2*u],dat[2*u+1]);
	}

	T query(int l,int r){ return query(l,r,0,n,1); }
};

int main(){
	int n; scanf("%d",&n);
	int x[100000];
	rep(i,n) scanf("%d",x+i);

	static segment_tree_RMQ<ll> S;
	S.build(n+1,0);
	rep(i,n){
		ll cost=S.query(0,x[i]);
		S.update(x[i],cost+x[i]);
	}

	printf("%lld\n",(ll)n*(n+1)/2-S.query(0,n+1));

	return 0;
}

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

int main(){
 
    int N,K;
    cin>>N>>K;
    vector<int> C(N+1);
    for(int i=0;i<N;i++){
        int x;
        cin>>x;
        C[x]++;
    }
    sort(C.begin(),C.end());
    int ans=0;
    for(int i=0;i<=N-K;i++){
        ans+=C[i];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <functional>
using namespace std;
int main() {
    int n, q;
    while (cin >> n >> q) {
        set<tuple<int, int>> players;
        vector<int> memo(n, 0);
        for (int i = 0; i < q; i++) {
            int a, v;
            cin >> a >> v;
            a--;
            players.erase(make_tuple(-memo[a], a));
            memo[a] += v;
            players.insert(make_tuple(-memo[a], a));
            cout << get<1>(*players.begin()) + 1 << ' ' << -get<0>(*players.begin()) << endl;
        }
    }
    return 0;
}

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

using namespace std;

const int N = 500000;

int n;
int res;
char s[101];
int sum[101][27];
int S[27];

int main() {
	cin >> n; cin >> (s + 1);
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < 26; j++)
			sum[i][j] = sum[i - 1][j] + (s[i] - 'a' == j);
	for(int i = n; i > 1; i--) {
		int num = 0;
		S[s[i] - 'a']++;
		for(int j = 0; j < 26; j++) {
			if(S[j] > 0 && sum[i - 1][j] > 0) num++;
		}
		res = max(res, num);
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    // Here your code !
    char c;
    vector<char> ans;
    while(cin >> c){
        if(c == 'B'){
            if(ans.size())ans.pop_back();
        }else{
            ans.push_back(c);
        }
    }
    
    for(int i = 0; i < ans.size(); i++)cout << ans[i];
    cout << endl;
    
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
  int X;
  cin >> X;
  if(X==3 || X==5 || X==7)cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>

using namespace std;

int main(){

	int n;
	while(cin>>n&&n!=0){
		bool isAppeared[10001];
		int data[10001];
		fill(isAppeared,isAppeared+10001,false);
		fill(data,data+10001,0);
		//memset(isAppeared,0,sizeof(isAppeared));
		//memset(data,0,sizeof(data));
		for(int i = 1; i < n; i++){
			int r=(i*i)%n;
			isAppeared[r]=true;
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(isAppeared[i]&&isAppeared[j]){
					int ret=i-j;
					if(ret<0)
						ret+=n;
					if(((n-1)/2)<ret){
						ret=n-ret;
					}
					data[ret]++;
				}
			}
		}
		for(int i = 1; i <= ((n-1)/2); i++){
			if(data[i]!=0)
				cout<<data[i]<<endl;
		}
	}

	return 0;
}

Measured memory_bytes: 916
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
ll inf =  1e9;
typedef pair<ll,mp> mmp;

ll n;
ll a,b,c;
vector<ll> q;

vector<char> ans;
vector< set<mmp> > e;
bool flag = false;

void func(ll i,ll aa,ll bb, ll cc){
 if( flag ) return;
 if( i==n ){
  cout<<"Yes"<<endl;
  for(auto i:ans)cout<<i<<endl;
  flag = true;
  return;
 }
 if( e[i].find(mmp(aa,mp(bb,cc) ) ) != e[i].end() ) return;
 else {
  e[i].insert( mmp(aa,mp(bb,cc) ) );
 }

 if( q[i] == 1 ){//AB
  if( aa == 0 && bb == 0 ) return;
  else if( aa == 0 ){
   ans[i] = 'A';
   func(i+1,aa+1,bb-1,cc);

  }else if( bb == 0 ){
   ans[i] = 'B';
   func(i+1,aa-1,bb+1,cc);
  }else{
   ans[i] = 'A';
   func(i+1,aa+1,bb-1,cc);
   ans[i] = 'B';
   func(i+1,aa-1,bb+1,cc);
  }
 }else if( q[i] == 2 ){//BC
  if( cc == 0 && bb == 0 ) return;
  else if( cc == 0 ){
   ans[i] = 'C';
   func(i+1,aa,bb-1,cc+1);

  }else if( bb == 0 ){
   ans[i] = 'B';
   func(i+1,aa,bb+1,cc-1);
  }else{
   ans[i] = 'C';
   func(i+1,aa,bb-1,cc+1);
   ans[i] = 'B';
   func(i+1,aa,bb+1,cc-1);
  }

 }else{
  
  if( aa == 0 && cc == 0 ) return;
  else if( aa == 0 ){
   ans[i] = 'A';
   func(i+1,aa+1,bb,cc-1);

  }else if( cc == 0 ){
   ans[i] = 'C';
   func(i+1,aa-1,bb,cc+1);
  }else{
   ans[i] = 'A';
   func(i+1,aa+1,bb,cc-1);
   ans[i] = 'C';
   func(i+1,aa-1,bb,cc+1);
  }

 }

}


int main(){
 cin>>n;
 cin>>a>>b>>c;
 q = vector<ll> (n);
 ans = vector<char>(n);
 e = vector<set<mmp> >(n);
 for(ll i=0;i<n;i++){
  string s;
  cin>>s;
  if( s== "AB"){
   q[i] = 1;
  }else if( s == "BC"){
   q[i] = 2;
  }else{
   q[i] = 3;
  }
 }

 func(0,a,b,c);
  if( !flag ) cout<<"No"<<endl;



    return 0;
}


Measured memory_bytes: 24860
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;

ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

ll LCM(ll a,ll b){
    return a / GCD(a,b) * b;
}

const int MOD = 1000000007;


//void warshall_floyd(int n){
//    for(int k=0;k<n;k++){
//        for(int i=0;i<n;i++){
//            for(int j=0;j<n;j++){
//                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//            }
//        }
//    }
//}

int calc_digit(long long N) {
    int res = 0;
    while (N) {
        ++res;
        N /= 10;
    }
    return res;
}

int main() {
    ll n; cin >> n;
    int ans = INT_MAX;
    for(ll i = 1;i * i <= n;i++){
        if(n % i == 0){
            ll b = n / i;
            int f = max(calc_digit(i),calc_digit(b));
            ans = min(ans,f);
        }
    }
    cout << ans;
 }



Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
int vis[100005];
vector<int> edge[100005];
void bfs(){
    queue<int> q;
    q.push(1);vis[1]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(auto v:edge[x]){
            if(vis[v]) continue;
            q.push(v);vis[v]=x;
        }
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    bfs();
    cout<<"Yes"<<endl;
    for(int i=2;i<=n;i++){
        cout<<vis[i]<<endl;
    }
}

Measured memory_bytes: 10512
/*
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <string>
#include <cmath>
#include <numeric>

int main()
{
    long long n;
    std::cin >> n;
    std::vector<std::pair<int, int>> ba(n);

    for (long long i = 0; i < n; i++)
        std::cin >> ba[i].second >> ba[i].first;

    std::sort(ba.begin(), ba.end());

    long long sum = 0;

    for (int i = 0; i < ba.size(); i++)
    {
        sum += ba[i].second;
        if (sum > ba[i].first)
        {
            std::cout << "No" << std::endl;
            return 0;
        }
    }

    std::cout << "Yes" << std::endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>
#include<complex>

using namespace std;

#define ll long long
#define ld long double
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

const double PI=acos(-1);
const double EPS=1e-9; //うまくいかなかったらゆるめる

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;
typedef vector<pii> vp;
typedef vector<vi> vvi;

int gcd(int a, int b){if(b==0) return a;return gcd(b,a%b);}
int lcm(int a, int b){return a/gcd(a,b)*b;}


signed main(void) {
    string s,t;
    int n,a,b,c,d,e,x,y;
    cin >> n;
    switch(n%10){
        case 2:
        case 4:
        case 5:
        case 7:
        case 9:cout << "hon" << endl;break;
        case 0:
        case 1:
        case 6:
        case 8: cout << "pon" << endl;break;
        case 3:cout << "bon" << endl;break;
    }

}


Measured memory_bytes: 3132
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    Main(){
        Scanner sc = new Scanner(System.in);
        long ans = 0;
        int N = sc.nextInt();
        String S = sc.next();
        int x = 0;
        for(int i=0;i<N;i++){
            if(S.charAt(i)=='I')x++;
            else x--;
            ans = Math.max(ans,x);
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        new Main();
    }
}


Measured memory_bytes: 20692
#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 A, B;
	cin >> A >> B;
	int ans = (A-1)*(B-1);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3500
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;

/*--- Macro ---*/
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep1(i, n) for(int i=1; i<(int)n; i++)
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()

/*---  Type ---*/
typedef long long ll;

/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;

// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

// Util
int max(int a, int b, int c) {return max(a, max(b, c));}
int min(int a, int b, int c) {return min(a, min(b, c));}
ll max(ll x, ll y) {return x > y ? x : y;}
ll min(ll x, ll y) {return x < y ? x : y;}
ll max(ll a, ll b, ll c) {return max(a, max(b, c));}
ll min(ll a, ll b, ll c) {return min(a, min(b, c));}

// How to use 「map」
/*
  - 宣言
    map<{key_type}, {value_type}> salary;
  - 要素の挿入
    salary["Alice"] = 1000;
  - 要素の取得 O(logn)
    salary.at("Alice");
  - 要素の削除
    salary.erase("Alice");
  - キー検索
    salary.find("Alice"); -> true
    salary.find("Bob");   -> false
  - イテレーション
    for(auto& [key, value] : salary) {...}
 */
// -------------------------------------


// How to use 「lower_bound」, 「upper_bound」
/*
  vector<int> a = {1, 2, 3, 4, 5};
  auto iter1 = lower_bound(all(a), 3);  <- 第二引数「以上」の最小イテレータが返る
  auto iter2 = upper_bound(all(a), 3);  <- 第二引数「より大きい」最小のイテレータが返る
 */
// -------------------------------------


// How to use 「struct sort」
/*
  struct Person {
    string name;
    int age;

    Person(string _name, int _age) {
      name = _name;
      age = _age;
    }

    bool operator<(const Person &another) const {
      return age < another.age;
    }
  };

  vector<Person> people;
  people.pb(Person("Alice", 20));
  people.pb(Person("Bob", 19));
  people.pb(Person("John", 40));
  people.pb(Person("Chris", 30));
  sort(all(people));
 */
 // -------------------------------------

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



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

  cout << ceil(n / 2.0) << endl;

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include<map>
#include<set>
#include<sstream>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define mem(a,b) memset(a,b,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
using namespace std;
const int maxn=2e5+10;
ll a[maxn],sum[maxn];
map<unsigned int,ll>num;
ll ans;
int main()
{
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=0;i<=n;++i){
        if(i>=k){
            num[((sum[i-k]-(i-k))%k)]--;
        }
        if(num[(sum[i]-i)%k]){
            ans+=num[(sum[i]-i)%k];
        }
        num[(sum[i]-i)%k]++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 15872
#include<iostream>
using namespace std;
string a;
int n=0;
int main()
{
	cin>>a;
	if(a[0]!='C')n++;
	if(a[1]!='O')n++;
	if(a[2]!='D')n++;
	if(a[3]!='E')n++;
	if(a[4]!='F')n++;
	if(a[5]!='E')n++;
	if(a[6]!='S')n++;
	if(a[7]!='T')n++;
	if(a[8]!='I')n++;
	if(a[9]!='V')n++;
	if(a[10]!='A')n++;
	if(a[11]!='L')n++;
	if(a[12]!='2')n++;
	if(a[13]!='0')n++;
	if(a[14]!='1')n++;
	if(a[15]!='6')n++;
	cout<<n<<endl;
	return 0;
}


Measured memory_bytes: 256
def main():

    import itertools
    n, m = map(int,input().split())
    way_lis = []
    for _ in range(m):
        way_lis.append(list(map(int, input().split())))
    #print(way_lis)
    ans = 0

    point_lis = [x for x in range (1, n+1)]
    per_lis = list(itertools.permutations(point_lis))       #町の順列を全パターン作る
    per_1_lis = []
    for lis in per_lis:
        if lis[0] == 1:
            per_1_lis.append(lis)
    #print(per_1_lis)


    for town_set in per_1_lis:           #一つずつ町のセットをチェック
        cnt = 0
        for i in range(n-1):
            way_i = []
            #print(point_lis, point_lis[i])
            way_i.append(town_set[i])
            way_i.append(town_set[i+1]) #way_i = 町iと町i+1をつなぐ道              
            way_i.sort()        #町i/ 町i+1で小さい方を前に
            #print(way_i)
            for way in way_lis:
                #print(way_i, way, way_i==way)
                if way_i == way:
                    cnt += 1
            if cnt == 0:
                break
            elif cnt == n-1:
                ans += 1
    print(ans)
                
            



if __name__ == "__main__":
    main()

Measured memory_bytes: 46956
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,ans; 
    cin >> n;
    vector<int> A(n);
    for(int i =0; i<n;i++)
        cin >> A[i];//いつもの　配列に数字を入れる
        for (int i=0;i<n ;i++){
            for(int j=i+1;j<n;j++){
                ans += A[i]*A[j];
            }//1番目の時、２からｎ番目を足す
        }
    
cout << ans <<  endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S; cin >> S;
    int n=S.size();
    vector<int> cnt(n+1,0);
    for (int i=0;i<n;++i) cnt[i+1]=cnt[i]^(1<<(S[i]-'a'));
    vector<int> dp(n+1,INF);
    map<int,int> m;
    dp[0]=0; m[0]=0;
    for (int i=0;i<n;++i){
        if (m.count(cnt[i+1])) dp[i+1]=min(dp[i+1],m[cnt[i+1]]+1);
        for (int j=0;j<26;++j){
            int mask=cnt[i+1]^(1<<j);
            if (m.count(mask)) dp[i+1]=min(dp[i+1],m[mask]+1);
        }
        if (!m.count(cnt[i+1])) m[cnt[i+1]]=dp[i+1];
        else m[cnt[i+1]]=min(m[cnt[i+1]],dp[i+1]);
    }
    cout << dp[n] << '\n';
}

Measured memory_bytes: 11412
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aryssoncf
 */



// Taken from: https://github.com/bqi343/USACO/blob/master/Implementations/content/contest/templateShort.cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ull> vul;
typedef vector<ll> vl;
typedef vector<pi> vpi;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)
#define trav(a, x) for (auto& a: x)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

#define mp make_pair
#define pb push_back
#define f first
#define s second

const int MOD = 1e9 + 7; // 998244353; // = (119<<23)+1
const int MX = 2e5 + 5;

template<class T>
bool ckmin(T &a, const T &b) {
    return a > b ? a = b, 1 : 0;
}

template<class T>
bool ckmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());


//
// Created by aryssoncf on 28/10/2019.
//

#include <type_traits>


#include <iterator>
#include <utility>

template<typename T>
constexpr auto hasBegin(int) -> decltype(std::begin(std::declval<T>()), true) {
    return true;
}

constexpr bool hasBegin(...) {
    return false;
}

template<typename T>
using IsContainer = std::integral_constant<bool, hasBegin<T>(0)>;


#ifndef JHELPER_EXAMPLE_PROJECT_IO_HPP
#define JHELPER_EXAMPLE_PROJECT_IO_HPP

#endif //JHELPER_EXAMPLE_PROJECT_IO_HPP

template<typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &vec) {
    for (T &element: vec) {
        is >> element;
    }
    return is;
}

template<typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first;
    is >> p.second;
    return is;
}

template<class X, class Y>
std::ostream &operator<<(std::ostream &os, std::pair<X, Y> const &p) {
    return os << p.first << " " << p.second;
}

template<class Ch, class Tr, class Container>
std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os, Container const &x) {
    bool first = true;
    for (auto &y : x) {
        if (first) {
            first = false;
        } else {
            os << " ";
        }
        os << y;
    }
    return os;
}

using namespace std;

/*
PROG:
LANG: C++
*/

class A500YenCoins {
public:
    void solve(std::istream &in, std::ostream &out) {
        int k, x;
        in >> k >> x;
        bool res = k * 500 >= x;
        out << (res ? "Yes" : "No") << "\n";
    }

    void setup() {}
};


int main() {
    std::ios_base::sync_with_stdio(false);
    A500YenCoins solver;
    solver.setup();
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    in.tie(nullptr);
    out << std::fixed;
    out.precision(20);
    solver.solve(in, out);
    return 0;
}


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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;


//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h,w,n;
    cin >> h >> w >> n;
    int sr,sc;
    cin >> sr >> sc;
    string s,t;
    cin >> s >> t;

    int maxHeight = h;
    int minHeight = 1;
    int minWidth = 1;
    int maxWidth = w;
    for(int i = n-1; i >= 0; i--){
        if(t[i] == 'D') minHeight = max(1,minHeight-1);
        if(t[i] == 'L') maxWidth = min(maxWidth+1,w);
        if(t[i] == 'U') maxHeight = min(maxHeight+1,h);
        if(t[i] == 'R') minWidth = max(1,minWidth-1);

        if(s[i] == 'U') minHeight++;
        if(s[i] == 'R') maxWidth --;
        if(s[i] == 'D') maxHeight --;
        if(s[i] == 'L') minWidth ++;
        if(minWidth > maxWidth || minHeight > maxHeight){
            cout << "NO" << endl;
            return 0;
        }
    }
    if(minHeight <= sr && sr <= maxHeight &&
       minWidth <= sc && sc <= maxWidth ){
           cout << "YES" << endl;
       }else{
           cout << "NO" << endl;
       }
    return 0;
}


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

int n;
int array[100010];

bool binary_search(int key){
    int left = 0,right = n;
    int mid;
    while(left < right){
        mid = (left+right)/2;
        if(array[mid] == key){
            return true;
        }
        else if(array[mid] > key){
        right = mid;
        }
        else if(array[mid] < key){
        left = mid+1;
        }
    }
    return false;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> array[i];
    }
    int q;
    int temp;
    int ans = 0;
    cin >> q;
    for(int i = 0; i < q; i++){
        cin >> temp;
        if(binary_search(temp)) ans++; 
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3472
N = int(input())
dic_a = {}
for i in range(N):
    a= int(input())
    if a in dic_a:
        dic_a[a] +=1
        dic_a[a] = dic_a[a]%2
    else:
        dic_a[a] = 1
print(sum(list(dic_a.values())))


Measured memory_bytes: 19236
from itertools import permutations
from math import factorial
from math import sqrt
n=int(input())
l=[]
def distance(x,y):
  a=sqrt((x[0]-y[0])**2+(x[1]-y[1])**2)
  return a
def dist(l):
  d=0
  for i in range(1,n):
    d+=distance(l[i],l[i-1])
  return d
for i in range(n):
  l.append(list(map(int, input().split())))
x=list(permutations(l))
avg=0
for i in x:
    avg+=dist(i)
print(avg/factorial(n))

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

using namespace std;

int main()
{
    int a1, a2, a3;

    cin >> a1 >> a2 >> a3;

    if ((a1+a2+a3) >= 22)
    {
        cout << "bust";
    }
    else
    {
        cout << "win";
    }

    return 0;
}


Measured memory_bytes: 256
# 階乗は英語でfactrial, ifacは階乗に対する逆元
def cmb(n, k, mod, fac, ifac):
    # nCkを求める
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):  # (mod mod)の世界における割り算に従ってテーブルを作る
    # 階乗, 階乗に対する逆元のテーブルを作成する
    fac = [1, 1]  # 階乗デーブル
    ifac = [1, 1]  # 階乗に対する逆元のテーブル
    inverse = [0, 1]  # 逆元そのもののテーブル

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac


X, Y = map(int, input().split())
MOD = 1000000007
if (X+Y) % 3 != 0:
    print(0)
else:
    m = (2*X-Y)//3
    n = X - 2*m
    if n < 0 or m < 0:
        print(0)
        exit()
    fac, ifac = make_tables(MOD, (X+Y)//3)
    ans = cmb(n+m, n, MOD, fac, ifac)
    print(ans)


Measured memory_bytes: 82464
import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

ans=[0 for i in range(N)]
subtreesize=[0 for i in range(N)]

def dfs(v,pv):
    if edge[v]==[pv]:
        subtreesize[v]=1
        ans[v]+=((N-1)%2==1)
        return subtreesize[v]

    a=0
    size=1
    for nv in edge[v]:
        if nv==pv:
            continue
        else:
            size+=dfs(nv,v)
            a+=(subtreesize[nv]%2==1)

    rest=N-size
    a+=(rest%2==1)
    ans[v]=a
    subtreesize[v]=size
    return size

dfs(0,-1)
check=[1]*N
if check==ans:
    print("Second")
else:
    print("First")


Measured memory_bytes: 76576
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		int[] a  = new int[N+1];

		for(int i=0;i<M;i++) {
			a[sc.nextInt()] ++;
			a[sc.nextInt()] ++;
		}

		for(int i=1;i<=N;i++) {
			out.println(a[i]);
		}

		sc.close();

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}

}


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

using namespace std;

typedef long long ll;

const int max_sum = 4e3+403;
const int mid = max_sum>>1;
const ll mod = 1e9+7;

bool buf;
int n;
ll res;
ll dp[max_sum][max_sum];
vector<pair<int, int> > inp;

inline void divide() {
	ll c = 2, y = mod-2;
	while (y) {
		if (y&1) 
			res = (res*c) % mod;
		c = (c*c) % mod;
		y >>= 1;
	}
}

int main() {

	buf = scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		int x, y;
		buf = scanf("%d %d", &x, &y);

		inp.emplace_back(x, y);
		dp[mid-x][mid-y] ++;
		dp[mid+x][mid+y] --;
	}

	for (int i = 2; i < max_sum; i++) {
		for (int j = 2; j < max_sum; j++) {
			ll c = 0;
			if (dp[i][j] < 0) {
				c = -dp[i][j];
				dp[i][j] = 0;
			}
			dp[i][j] = (dp[i][j] + dp[i-1][j] + dp[i][j-1]) % mod;

			res = (res + c*dp[i][j]) % mod;

			int i2 = i-2, j2 = j-2;
			if (!i2 or !j2) {
				dp[i2][j2] = 1; 
				continue ;
			}
			dp[i2][j2] = dp[i2-1][j2] + dp[i2][j2-1];
			dp[i2][j2] %= mod;
		}
	}
	for (auto pa : inp) {
		res = (res - dp[2*pa.first][2*pa.second] + mod) % mod;
	}

	divide();

	printf("%lld\n", res);

	return 0;
}

Measured memory_bytes: 156440
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)n; i++)
const int MOD = 1000000007;
// long long a;
int main(){
  int N, M;
  cin >> N;
  vector<int > t(N);
  int sum = 0;
  REP(i, N){
    cin >> t[i];
    sum += t[i];
  }
  cin >> M;
  vector<int > p(M), x(M);
  REP(i, M) cin >> p[i] >> x[i];
  REP(i, M){
    cout << sum - t[p[i] - 1] + x[i] << endl;
  }
}


Measured memory_bytes: 256
#グラフ構造DFSを使う
import sys
sys.setrecursionlimit(500000)
N = int(input())
ans = [-1] * (N-1)
g = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    g[a-1].append((b-1, i))
    g[b-1].append((a-1, i))

def bfs(v, c, p):
    n_c = 1
    for i in range(len(g[v])):
        to = g[v][i][0]
        ID = g[v][i][1]
        if to == p:
            continue
        if n_c == c:
            n_c += 1
        ans[ID] = n_c
        bfs(to, n_c, v)
        n_c += 1

bfs(0, 0, -1)
print(max(ans))
for i in range(N-1):
    print(ans[i])

Measured memory_bytes: 109212
#include<iostream>
static const int MAX = 100;
using namespace std;

void trace(int A[], int N)
{
	int i;
	for(i=0; i<N; i++){
		if(i>0){
			cout << " ";
		}
		cout << A[i];
	}
	cout << endl;
}

void bubbleSort(int A[], int N)
{
	int flag, j, tmp, count;
	
	flag = 1;
	count = 0;
	
	while(flag){
		flag = 0;
		for(j=N-1; j>0; j--){
			if(A[j] < A[j-1]){
				tmp = A[j];
				A[j] = A[j-1]; 
				A[j-1] = tmp;
				
				flag = 1;
				count++;
			}
		}
	}
	
	trace(A, N);
	
	cout << count << endl;
}

int main()
{
	int N, i;
	int A[MAX];
	
	cin >> N;
	for(i=0; i<N; i++)cin >> A[i];
	
	bubbleSort(A, N);
	
	return 0;
}

Measured memory_bytes: 3068
require 'tsort'
require 'set'

class Hash
	include TSort
	alias :tsort_each_node :each_key
	def tsort_each_child(u)
		self[u].each {|v| yield v}
	end
end

loop do
	n = gets.to_i
	break if n == 0
	words = (1..n).map { gets.chomp }
	graph = {}
	(?a..?z).each {|c| graph[c] = Set.new }

	ok = true
	words.each_cons(2) do |w1, w2|
		if w1 != w2 && w1 =~ /^#{w2}/
			ok = false
			break
		end
		(0..[w1.size, w2.size].min-1).each do |i|
			next if w1[i] == w2[i]
			graph[w1[i]] << w2[i]
			break
		end
	end

	if ok
		begin
			graph.tsort
		rescue TSort::Cyclic
			ok = false
		end
	end

	puts ok ? 'yes' : 'no'
end

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

#define ll long long
#define N (ll)(2*1e5)
#define EPS (double)(1e-12)
#define M (ll)(1e9+7)

using namespace std;


int main() {
    // 176 algorithm design manual
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll n;

    cin >> n;

    vector<ll> arr(n);

    for(ll i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr.begin(), arr.end());

    ll middle = arr.size()/2;

    cout << arr[middle]-arr[middle-1] << endl;
    
    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstring>
namespace std
{
	int min(int x, int y) { return x < y ? x : y; }
	int max(int x, int y) { return x > y ? x : y; }
}

const int N(1010), M(5010);
struct edge { int next, to; } e[N];
int n, X[N], f[N], g[M], head[N], max, e_num;
inline void add_edge(int from, int to)
{
	e[++e_num] = (edge) {head[from], to};
	head[from] = e_num;
}

void dfs(int x)
{
	for (int i = head[x]; i; i = e[i].next) dfs(e[i].to);
	memset(g, 0x3f, (X[x] + 1) << 2), g[0] = 0;
	for (int i = head[x]; i; i = e[i].next)
	{
		int to = e[i].to;
		for (int j = X[x]; ~j; j--)
		{
			int t = 0x3f3f3f3f;
			if (j >= X[to]) t = std::min(t, g[j - X[to]] + f[to]);
			if (j >= f[to]) t = std::min(t, g[j - f[to]] + X[to]);
			g[j] = t;
		}
	}
	for (int i = 0; i <= X[x]; i++) f[x] = std::min(f[x], g[i]);
}

int main()
{
	scanf("%d", &n), memset(f, 0x3f, sizeof f);
	for (int i = 2, x; i <= n; i++) scanf("%d", &x), add_edge(x, i);
	for (int i = 1; i <= n; i++) scanf("%d", X + i), max = std::max(max, X[i]);
	dfs(1); puts(f[1] == 0x3f3f3f3f ? "IMPOSSIBLE" : "POSSIBLE");
	return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
max_abs_diff = 0
for i in range(N-1):
    for j in range(i+1, N):
        abs_diff = abs(A[i]- A[j])
        if max_abs_diff < abs_diff:
            max_abs_diff = abs_diff
print(max_abs_diff)

Measured memory_bytes: 38768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, n) for (int i = (n-1); i >= 0; i--)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define reab(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(),(a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;
/* END OF TEMPLATE */

int main(){
    ll N;
    cin >> N;
    vll a(N);
    rep(i, N){
        cin >> a[i];
    }
    cout << accumulate(ALL(a), 0)-N << endl;
}

Measured memory_bytes: 256
import sys

def q(i):
  print i
  sys.stdout.flush()
  s = raw_input()
  if s=="Vacant":
    sys.exit(0)
  else:
    return 0 if s=="Male" else 1

N, = map(int, raw_input().split())
S = [None]*N
l = 0
S[l] = q(l)
r = N-1
S[r] = q(r)
while True:
  m = (l+r)//2
  S[m] = q(m)
  if (m-l+S[m]-S[l])%2==0:
    l = m
  else:
    r = m

Measured memory_bytes: 4056
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class C
{
	public static void Main() => (new Solver()).Solve();
}

public class Solver
{
	public void Solve()
	{
		int N = GetInt();
		var X = GetInts(N);

		int ans = int.MaxValue;
		for(int i = 1; i <= 100; i++)
		{
			int sum = 0;
			for(int j = 0; j < N; j++)
				sum += (i - X[j]) * (i - X[j]);

			chmin(ref ans, sum);
		}
		WriteLine(ans);
	}
}

public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => Enumerable.Range(0, (int)N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(long N) => Enumerable.Range(0, (int)N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDouble()).ToArray();
	public static decimal[] GetDecimals(long N) => Enumerable.Range(0, (int)N).Select(_ => GetDecimal()).ToArray();
	public static string[] GetStrings(long N) => Enumerable.Range(0, (int)N).Select(_ => GetString()).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) < 0)
			x = y;
	}

	public static void chmin<T>(ref T x, T y) where T : IComparable<T>
	{
		if(x.CompareTo(y) > 0)
			x = y;
	}

	public static void swap<T>(ref T x, ref T y)
	{
		T tmp = x;
		x = y;
		y = tmp;
	}
}

Measured memory_bytes: 11348
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <deque>
#include <numeric>
#include <utility>
using namespace std;

#define LL long long
#define NFRAC 300000
const long long MOD = 1000000007;

LL fac[NFRAC+1];
LL ifac[NFRAC+1];

LL mpow(LL x, LL n){
    LL ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % MOD;
        x = x*x % MOD;
        n = n >> 1;
    }
    return ans;
}

LL comb(LL a, LL b){
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    LL tmp = ifac[a-b]* ifac[b] % MOD;
    return tmp * fac[a] % MOD;
}

LL perm(LL a, LL b){
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    return ifac[a-b] * fac[a] % MOD;
}

void init(){
    fac[0] = 1;
    ifac[0] = 1;
    for(LL i = 0; i<NFRAC+1; i++){
        fac[i+1] = fac[i]*(i+1) % MOD;
        ifac[i+1] = ifac[i]*mpow(i+1, MOD-2) % MOD;
    }
}

long long gcd(long long a, long long b) {
  long long _max = a > b ? a : b;
  long long _min = a > b ? b : a;
  if (!(_max%_min)) return _min;
  else return gcd(_min, _max%_min);
}
 
long long lcm(long long a, long long b) {
  return a/gcd(a,b)*b;
}

void solve(long long H, long long W, long long A, long long B){
    init();
    LL ans=0;
    for(LL i=0; i<H-A; i++){
        auto j = (i==H-A-1 ? 0 : 1);
        auto tmp = (comb(B+i, B)*comb(H+W-2-B-i-j, W-B-1-j))%MOD;
        ans = (ans + tmp)%MOD;
    }
    cout << ans << endl;
}

int main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(H, W, A, B);
    return 0;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define inf 100000000000000000
#define ll long long int
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
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 ;
	cin>>n;
	vector<ll> v1 , v2 , vec ;
	for(ll i=0,a ;i<n;i++){
		cin>>a;v1.pb(a);
	}
	for(ll i=0 ,a ;i<n;i++){
		cin>>a;v2.pb(a);
	}
	for(ll i=1;i<=n ;i++)vec.pb(i);
	ll a1 , a2 ,k=1;
	do{
		if(v1==vec)a1=k;
		if(v2==vec)a2=k;
		k++;
	}while(next_permutation(vec.begin(),vec.end()));
	cout<<abs(a1-a2)<<endl;

	return 0;
}

Measured memory_bytes: 256
W,H,N = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(N)]

top = H
btm = 0
left = 0
right = W
for x,y,a in src:
    if a == 1:
        left = max(left,x)
    elif a == 2:
        right = min(right,x)
    elif a == 3:
        btm = max(btm,y)
    else:
        top = min(top,y)
w = max(0, right-left)
h = max(0, top-btm)
print(w*h)

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

using namespace std;

int main() {
    
    //cout << ": " <<  << "\n";

    int n,m,sum=0,days=0;;

    cin >> n >> m;

    while(m--) {
        cin >> days;
        sum += days;
    }

    if(sum>n) {
        cout << -1;
    } else {
        cout << n-sum;
    }

}

Measured memory_bytes: 3636
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

constexpr int MOD_TYPE = 2;
constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9;
constexpr ll LINF = (ll)4e18;
constexpr ld PI = acos(-1.0);
constexpr ld EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";

#pragma endregion

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(30) << setiosflags(ios::fixed);

  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  int x = tx - sx;
  int y = ty - sy;
  string ans;
  rep(i, x) ans.push_back('R');
  rep(i, y) ans.push_back('U');
  rep(i, x) ans.push_back('L');
  rep(i, y) ans.push_back('D');
  ans.push_back('L');
  rep(i, y + 1) ans.push_back('U');
  rep(i, x + 1) ans.push_back('R');
  ans.push_back('D');
  ans.push_back('R');
  rep(i, y + 1) ans.push_back('D');
  rep(i, x + 1) ans.push_back('L');
  ans.push_back('U');
  cout << ans << endl;
  return 0;
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const double PI = acos(-1);



int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	ll n, k;
	cin >> n >> k;

	vector<ll> h(n);
	rep(i, n) cin >> h[i];

	sort(all(h));

	ll mi = inf;
	for (int i = 0; i <= n - k; i++) {
		chmin(mi, h[k + i - 1] - h[i]);
	}

	out(mi);

	return 0;
}

Measured memory_bytes: 1024
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

long[string] SS;

void main()
{
    auto N = readln.chomp.to!int;
    foreach (_; 0..N) {
        auto s = readln.chomp.to!(dchar[]);
        sort(s);
        auto ss = s.to!string;
        if (ss !in SS) SS[ss] = 0;
        ++SS[ss];
    }
    long r;
    foreach (_, c; SS) if (c > 1) {
        r += c * (c-1) / 2;
    }
    writeln(r);
}

Measured memory_bytes: 20476
#include <stdio.h>
 
int main(void){
  int a , b , takasa = 0;
  scanf("%d %d",&a ,&b);
  
  for(int i = 1;i < b-a;i ++){
    takasa += i;
  }
  
  printf("%d",takasa - a);
  
  return 0;
}

Measured memory_bytes: 128
#include <iostream>  // cin,cout
#include <stdio.h>   // printf,scanf (standard input/output)
#include <cmath>     // abs(x),pow(x,2)
#include <string>
#include <string.h>  // strlen, strcmp
#include <algorithm> // min,max, sort(v.begin(),v.end())
#include <vector>
#include <time.h>
using namespace std;

struct Card{
    string suit;
    int value;
};

int Func(){
    int x = 0;
    return x;
}

int main(){
    int A, B, C;
    float f;
    string s;
    
    cin >> A >> B >> C;
    //for (int i=0;i<N;i++) cin >> A[i];
    
    int D = B/A;
    
    if (D>C) cout << C << endl;
    else cout << D << endl;

    
    return 0;
}


Measured memory_bytes: 256
#include<iostream> 
#include<cstdio> 
#include<algorithm> 
#include<cmath> 
using namespace std; 
int n,a[55]; 
int main() 
{ 
	scanf("%d",&n); 
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int mx=1;
	for(int i=2;i<=n;i++)
		if(abs(a[i])>abs(a[mx])) mx=i;
	printf("%d\n",2*n);
	if(a[mx]>=0) {
		printf("%d %d\n",mx,n);
		printf("%d %d\n",mx,n);
		for(int i=1;i<n;i++) {
			printf("%d %d\n",n,i);
			printf("%d %d\n",n,n);
		}
	}
	else {
		printf("%d %d\n",mx,1);
		printf("%d %d\n",mx,1);
		for(int i=n;i>1;i--)
		{
			printf("%d %d\n",1,i);
			printf("%d %d\n",1,1);
		}
	}
	return 0;
}

Measured memory_bytes: 256
// by syu
package main

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

var in = NewScanner(os.Stdin, 0)

func main() {
	H, _ := in.Int(), in.Int()
	g := make([]string, H)
	for i := 0; i < H; i++ {
		g[i] = in.String()
	}
	g = FilterStrings(g, func(i int, bb string) bool {
		return strings.IndexByte(bb, '#') != -1
	})
	g = TransposeString(g)
	g = FilterStrings(g, func(i int, bb string) bool {
		return strings.IndexByte(bb, '#') != -1
	})
	g = TransposeString(g)
	PString(g)
}

type Scanner struct {
	*bufio.Scanner
}

func NewScanner(r io.Reader, max int) *Scanner {
	s := bufio.NewScanner(r)
	s.Split(scanWords)
	if max <= 0 {
		max = 1048576
	}
	s.Buffer([]byte{}, max)
	return &Scanner{s}
}
func (s *Scanner) String() string {
	s.Scan()
	return s.Text()
}
func (s *Scanner) Int() int {
	s.Scan()
	i, e := strconv.ParseInt(s.Text(), 10, 64)
	if e != nil {
		panic(e)
	}
	return int(i)
}
func isSpace(b byte) bool {
	return b == ' ' || b == '\n' || b == '\r' || b == '\t'
}
func scanWords(data []byte, atEOF bool) (advance int, token []byte, err error) {
	start := 0
	for start < len(data) && isSpace(data[start]) {
		start++
	}
	for i := start; i < len(data); i++ {
		if isSpace(data[i]) {
			return i + 1, data[start:i], nil
		}
	}
	if atEOF && len(data) > start {
		return len(data), data[start:], nil
	}
	return start, nil, nil
}
func FilterStrings(a []string, f func(int, string) bool) (r []string) {
	for i, x := range a {
		if f(i, x) {
			r = append(r, x)
		}
	}
	return
}
func TransposeString(slice []string) []string {
	xl := len(slice[0])
	yl := len(slice)
	result := make([]string, xl)
	for i := 0; i < xl; i++ {
		r := make([]byte, yl)
		for j := 0; j < yl; j++ {
			r[j] = slice[j][i]
		}
		result[i] = string(r)
	}
	return result
}
func Pf(f string, s ...interface{}) {
	fmt.Printf(f, s...)
}
func PString(a []string) {
	for i := 0; i < len(a); i++ {
		Pf("%s\n", a[i])
	}
}


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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

int main() {
source:
    ll n;
    cin >> n;
    ll x[n];
    rep(i, n) { cin >> x[i]; }
    ll ans = mod;
    rep(i, 101) {
        ll sum = 0;
        rep(j, n) { sum += (x[j] - i) * (x[j] - i); }
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
const ll inf = 1e18;
ll a[maxn];
int main(){
    int k,n;
    cin>>k>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    ll ans = a[n]-a[1];
    for(int i=1;i<n;i++){
        ans = min(ans,a[i]-a[1]+(a[1]+k-a[n])+a[n]-a[i+1]);
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
n, k = map(int,input().split())

ans = 0
for i in range(k, n + 2):
    min_ = i * (i - 1) // 2
    max_ = i * (2 * n + 1 - i) // 2
    #print(min_, max_, max_ - min_)
    ans += (max_ - min_ + 1)
print(ans % (pow(10, 9) + 7))


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

int main(){
    int w, a, b;
    cin >> w >> a >> b;
    if(a < b){
        if(w + a >= b && w + a <= w + b) cout << 0 << endl;
        else cout << b - (w + a) << endl;
    }else{
        if(w + b >= a && w + b <= w + a) cout << 0 << endl;
        else cout << a - (w + b) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <stack>
#include <iomanip>
#include <set>
#include <queue>
#include <unordered_map>

using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int maxn = 1e5 + 7;
const int inf = 2e9 + 7;
const ll infl = 1e18 + 7;
const long double eps = 1e-9;
const ll mod = 1e9 + 7;

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

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;
	vector<vector<char>> g(n + 2, vector<char>(m + 2, '#'));
	vector<vector<int>> dp(n + 2, vector<int>(m + 2, 0));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> g[i][j];
		}
	}
	dp[1][1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (g[i][j] == '#' || (i == 1 && j == 1)) continue;
			dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
		}
	}
	cout << dp[n][m];
	return 0;
}


Measured memory_bytes: 5248
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		double r = sc.nextDouble();
		System.out.print(String.format("%.6f",(double)r * r * (Math.PI)) + " ");
		System.out.println(String.format("%.6f",(double)r * 2 * (Math.PI)));
	}
}

Measured memory_bytes: 28024
n,k=map(int,input().split())
r,s,p=map(int,input().split())
t=list(input())

def f(a):
    if a=="r":
        return p
    elif a=="s":
        return r
    else:
        return s

ans=0
for i in range(n):
    if i<k:
        ans+=f(t[i])
    elif t[i]==t[i-k]:
        t[i]="o"
    else:
        ans+=f(t[i])
print(ans)

Measured memory_bytes: 4084