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

typedef long long ll;

const ll maxn = 200005;
ll h, w, a, b, ans;
ll fac[maxn], facinv[maxn], inv[maxn], mod = 1000000007;

ll c(ll n, ll k)
{
    return (((fac[n] * facinv[k]) % mod) * facinv[n-k]) % mod;
}

int main()
{
    inv[1] = 1;
    for (int i = 2; i <= maxn; i++)
    {
        inv[i] = (mod - (mod / i) * inv[mod % i] % mod) % mod;
    }
    fac[0] = fac[1] = 1;
    for (int i = 2; i <= maxn; i++)
    {
        fac[i] = (i * fac[i-1]) % mod;
    }
    facinv[0] = facinv[1] = 1;
    for (int i = 2; i <= maxn; i++)
    {
        facinv[i] = (inv[i] * facinv[i-1]) % mod;
    }

    cin >> h >> w >> a >> b;
    ans = c(h+w-2, h-1);
    for (ll i = 1; i <= b; i++)
    {
        ans -= (c(h-a+i-2, i-1) * c(a+w-i-1, a-1)) % mod;
        if (ans < 0) ans += mod;
    }
    cout << ans << endl;
    return 0;
}


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

#include <iostream>
#include <fstream>

#include <iostream>
#include "bits/stdc++.h"

using namespace std;

typedef unsigned long long ll;
typedef int                     integer;
#define int                     long long
#define ii                      pair<int,int>
#define vii                     vector<pair<int,int>>
#define vi                      vector<int>
#define vvi                     vector<vector<int>>
#define f(a,b,c)                for(int a=b;a<c;a++)
#define s(x)                    in>>x
#define s2(x,y)                 in>>x>>y
#define s3(x,y,z)               in>>x>>y>>z
#define s4(x,y,z,w)             in>>x>>y>>z>>w
#define p(x)                    out<<x<<endl
#define p2(x,y)                 out<<x<<" "<<y<<endl
#define pl(x)                   out<<x
#define p2l(x,y)                out<<x<<" "<<y
#define p1d(a,n)                for(int ix=0;ix<n;ix++) out<<a[ix]<<" "; out<<endl
#define p2d(a,n,m)              for(int ix=0;ix<n;ix++){ for(int jx=0;jx<m;jx++) out<<a[ix][jx]<<" "; out<<endl;}
#define range(v)                v.begin(),v.end()
#define w(x)                    while(x--)
#define rst(x)                  memset(x, -1, sizeof(x))
#define UNVISITED               -1
#define VISITED                 0
#define EXPLORED                2

class DCaracalVsMonster {
public:
	void solve(std::istream& in, std::ostream& out) {
        int h;
        s(h);
        int k = 0;
        int tot = 0;
        while(h!=0){
            tot+=pow(2,k);
            h/=2;
            k++;
        }
        out<<tot<<endl;
	}
};


integer main() {
	DCaracalVsMonster solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
}


Measured memory_bytes: 512
#include <stdio.h>

int main(void);

int main(void)
{
    int H, W, i, j;

    while(1){
        scanf("%d %d", &H, &W);
        if(H == 0 && W == 0){
            break;
        }

        for(i = 1; i <= H; i++){
            for(j = 1; j <= W; j++){
                if(i > 1 && i < H && j >1 && j < W){
                    printf(".");
                }
                else{
                    printf("#");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
    return(0);
}


Measured memory_bytes: 2068
#include <iostream>
#include <cstdio>
#include <cstring>
#define fre
#define DEBUG
#define ll long long
using namespace std;
const int maxn = 200005;
ll odd, even;
int main()
{
    ll n, k;
    scanf("%lld%lld", &n, &k);
    for (ll i = 1; i <= n; ++i)
    {
        if (2 * i % k == 0)
        {
            if ((2 * i / k) & 1) ++odd;
            else ++even;
        }
    }
    ll ans = odd + even + 3 * odd * (odd - 1) + 3 * even * (even - 1) + odd * (odd - 1) * (odd - 2) + even * (even - 1) * (even - 2);
    printf("%lld", ans);
}

Measured memory_bytes: 256
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
//#include <intrin.h>
#include <ctime>
#pragma endregion //#include
/////////

#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)4e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

map<pair<LL,LL>,LL > memo;
LL func(LL S,LL X){
	pair<LL,LL> dat;
	dat.first = S;
	dat.second = X;
	if( S < 0 || X < 0 ){
		return 0;
	}
	if( memo.find(dat) != memo.end() ){
		return memo[dat];
	}
	LL ret = 0;
	ret += func(S/2,X/2);
	if( S>0 && X>0 ){
		ret += func((S-1)/2,(X-1)/2);
	}
	if( S > 1 ){
		ret += func((S-2)/2,X/2);
	}
	ret %= MOD;
	return memo[dat] = ret;
}
void solve(){
	pair<LL,LL> base;
	base.first = 0;
	base.second = 0;
	memo[base] = 1;

	LL N;
	cin >> N;
	cout << func(N,N) << endl;
}
#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define ld long double
#define vi vector<vector<ll> >
using namespace std;
const int MOD=1000000007;
const int MOD2=998244353;
const ll MAX=9187201950435737471;
const int N=100005;
const int INF=1e9+7;
const long double PI=acos(-1);



void solve(int T){
    ll n;
    cin>>n;
    cout<<(n*(n+1))/2<<"\n";
}

int main() {
    fastio

    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
    }
	return 0;
}


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

using namespace std;

string solve(int n, string s, string t) {
    string ans;
    for (int len = 0; len < n; ++len) {
      ans += s[len];
      ans += t[len];
    }
    return ans;
}

int main() {
    int n;
    string s;
    string t;
    cin >> n >> s >> t;
    cout << solve(n, s, t);
}


Measured memory_bytes: 256
// @gaurav_512
#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef unordered_map<int,int> umii;
typedef unordered_map<ll,ll> umll;
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define bs(v,val) binary_search(v.begin(),v.end(),val)
#define mod 1e9+7
#define ff first
#define ss second
#define fi(n) for(int i=0;i<n;i++)
#define fj(n) for(int j=0;j<n;j++)
#define all(v) v.begin(),v.end()
#define pb push_back
#define m_p make_pair
#define endl '\n'
 
ll power(ll x, ll y, ll p)
{  
    ll res = 1;
    x = x % p;  
    if (x == 0) return 0;
    while (y > 0){  
        if (y & 1)  res = (res*x) % p;  
        y = y>>1;
        x = (x*x) % p;  
    }  
    return res;  
}
ll modInverse(ll n, ll p)
{
    return power(n, p-2, p); 
}
// ********** CODE STARTS HERE ****************//
 
 
void solve()
{
	int n;
	cin>>n;
	vi a(n+1),b(n+1),c(n+1);
	for(int i=1;i<=n;i++)	cin>>a[i]>>b[i]>>c[i];
	int dp[n+1][3];
	dp[0][0]=dp[0][1]=dp[0][2]=0;
	for(int i=1;i<=n;i++)
	{
		dp[i][0] = a[i] + max(dp[i-1][1],dp[i-1][2]);
		dp[i][1] = b[i] + max(dp[i-1][0],dp[i-1][2]);
		dp[i][2] = c[i] + max(dp[i-1][1],dp[i-1][0]);
	}
	cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
	
}
int main()

{
	fastio;
//    int T;
//    cin>>T;
//    while(T--)
        solve();
	return 0;
}

Measured memory_bytes: 5540
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 6;
const ll MOD = 1e9 + 7;

int n;
ll f[2 * N];

int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cin >> n;
  f[n] = n;
  for (int i = n + 1; i <= 2 * n; ++i) f[i] = 1;
  ll tmp = (1LL * (n - 1) * (n - 1)) % MOD;
  ll sum = n - 1;
  for (int i = n - 1; i; --i) {
    f[i] = (tmp + f[i + 1] + sum) % MOD;
    sum = sum + f[i + 2] - f[i + n + 1];
  }
  cout << f[1];
  return 0;
}

Measured memory_bytes: 15872
X = int(input())

err = 0

if X >= 2000:
    print("1")
    err = 1
else:
    for i in range(19):
        n = i + 1
        if X>= 100*n and X<= 100*n+5*n:
            print("1")
            err = 1
            break
if err == 0:
    print("0")


Measured memory_bytes: 2940
#include <stdio.h>
int c(char *p,int d){return ((26+*p-*(p+1))%26==d);}
int a(char *p){return((*p>'`')&&(*p<'{'));}
char *decode (char *inbuf, int s) {
  char *p=inbuf-1;
  while (*++p){
    if(a(p)){
      int t = *p + s;

      if (t > 'z')      *p = (char)(t - 26);
      else if (t < 'a') *p = (char)(t + 26);
      else              *p = (char)t;
    }
  }
  return (inbuf);
}

main(s){
  char b[82];
  while(fgets(b,80,stdin)){
    char *p=b-1;
    while(*++p){
      if((c(p,12))&&((c(p+1,3)&&!a(p+3))||(c(p+1,7)&&c(p+2,7)&&!a(p+4))||(c(p+1\
,25)&&c(p+2,16)&&!a(p+4)))){s='t'-*p;p+=3;break;}
    }
    printf("%s",decode(b, s));
  }
  //  return 0;
}

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

#if DEBUG
template <typename T>
void debug(const T& value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(const T& value, const Ts&... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                        \
  do {                                  \
    cerr << #__VA_ARGS__ << ": ";       \
    debug(__VA_ARGS__);                 \
    cerr << " (L" << __LINE__ << ")\n"; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define rd(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << '\n';
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define wt(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  rd(int, x);
  wt(lcm(x, 360) / x);
}


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

using namespace std;

typedef double db;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

typedef pair < db, db > pdd;
typedef pair < db, ld > pdl;
typedef pair < ld, db > pld;
typedef pair < ld, ld > ldp;

typedef pair < ll, ll > pll;
typedef pair < int, ll > pil;
typedef pair < ll, int > pli;
typedef pair < int, int > pii;

#define f first
#define s second

#define en end()
#define bg begin()

#define rev reverse
#define mp make_pair
#define pb push_back

#define y1 y1234567890
#define um unordered_map

#define all(x) x.bg, x.en
#define sz(x) (int)x.size()
#define len(x) (int)strlen(x)

#define sqr(x) ((x + 0ll) * (x))
#define sqrd(x) ((x + 0.0) * (x))

#define forn(i, n) for (int i = 1; i <= n; i++)

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

const db eps = (db)1e-9;
const db pi = acos(-1.0);

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

const int N = 1000;

int n, m, k, ans = inf, dp[N][N];
char c[N][N];
queue <pii> q;	

int f(int X){
	return (X + k - 1) / k;
}

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	//freopen(".err", "w", stderr);

	//srand(time(NULL));

	//cin.tie(NULL);
	//cout.tie(NULL);
	//ios_base::sync_with_stdio(false);

	//cout << setprecision(10) << fixed;

	cin >> n >> m >> k;

	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= m; ++j)
		dp[i][j] = inf;
	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= m; ++j){
		cin >> c[i][j];
		if(c[i][j] == 'S'){
			dp[i][j] = 0;
			q.push(mp(i, j));
		}
	}

	while(!q.empty()){
		int x = q.front().f, y = q.front().s;
		q.pop();
		if(x == 1 || y == 1 || x == n || y == m){
			cout << 1;
			return 0;
		}
		if(dp[x][y] == k)
			continue;
		for(int dir = 0; dir < 4; ++dir){
			int xa = x + dx[dir], ya = y + dy[dir];
			if(c[xa][ya] == '.' && dp[xa][ya] > dp[x][y] + 1){
				dp[xa][ya] = dp[x][y] + 1;
				q.push(mp(xa, ya));
			}
		}
	}

	for(int i = 1; i <= n; ++i)
	for(int j = 1; j <= m; ++j){
		if(dp[i][j] <= k){
			ans = min(ans, min(min(f(i - 1), f(j - 1)), min(f(n - i), f(m - j))) + 1);
		}
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 4224
/* ALDS1_11_D: Connected Components */

#include <iostream>
#include <vector>
#include <stack>
using std::vector;
using std::stack;

void grouping(int id, int group_id, int group_ids[], vector<int> sns[]) {
    stack<int> S;
    S.push(id);
    group_ids[id] = group_id;

    while(! S.empty()) {
        id = S.top();
        S.pop();
        vector<int> friends = sns[id];
        for (int i = 0; i < friends.size(); i++) {
            int friend_id = friends[i];
            if (group_ids[friend_id] < 0) {
                group_ids[friend_id] = group_id;
                S.push(friend_id);
            }
        }
    }
}

void assign_groups(int n_users, vector<int> sns[], int group_ids[]) {
    int group_id = 0;
    std::fill_n(group_ids, n_users, -1);
    for (int id = 0; id < n_users; id++) {
        if (group_ids[id] < 0) {
            grouping(id, group_id, group_ids, sns);
            group_id++;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);

    int n_users, n_relations;
    std::cin >> n_users >> n_relations;

    int id, friend_id, n_friends;
    vector<int> *sns = new vector<int>[n_users];
    for (int i = 0; i < n_relations; i++) {
        std::cin >> id >> friend_id;
        sns[id].push_back(friend_id);
        sns[friend_id].push_back(id);
    }

    int group_ids[n_users];
    assign_groups(n_users, sns, group_ids);

    int n_questions;
    std::cin >> n_questions;

    for (int i = 0; i < n_questions; i++) {
        std::cin >> id >> friend_id;
        bool same_group = group_ids[id] == group_ids[friend_id];
        std::cout << ( same_group ? "yes" : "no" ) << "\n";
    }
    return 0;
}

Measured memory_bytes: 7060
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define lli long long int
#define pb push_back
#define mp make_pair
#define fo(i,n) for(i=0;i<(n);i++)
#define endl "\n"
#define mod 1000000007

long long int i,j;
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    lli n,k;
    cin>>n>>k;
    int a[n],b[n];
    fo(i,n){cin>>a[i];b[i]=mod;}
    b[0]=0;
    b[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++){
        int t=mod;
        
        for(int l=i-1;l>i-1-k && l>=0;l--){
        // b[i]=min(abs(a[i]-a[i-1])+b[i-1],abs(a[i]-a[i-2])+b[i-2]);
        t=min(t,b[l]+abs(a[i]-a[l]));
        // cout<<t<<" ";
        }
        b[i]=t;
        // cout<<a[i]<<" "<<endl;
    }
    cout<<b[n-1];
    return 0;
}


Measured memory_bytes: 1024
H=gets.chomp.to_i
$count = 0

def monster(hp)
  $count = $count + 1
  if hp > 1 then
    newhp = hp / 2
    monster(newhp)
    monster(newhp)
  else
    # 勝利
    return
  end
end

def kougeki(hp)
  n = Math.log2(hp)
  i = 1
  $count = i
  1.upto(n) do |tmp|
    i = i * 2
    $count = $count + i
  end
end

kougeki(H)
puts $count

Measured memory_bytes: 3836
#include<bits/stdc++.h>
#define fastio     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x)     (x).begin() , (x).end()
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
typedef long long int ll;
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}


const ll mod = 1e9+7;
const double eps = 1e-9;



void solve(){
    int n=5;
    for(int i=0;i<n;i++) {
        int t;
        cin>>t;
        if(!t) {
            cout<<i+1<<"\n";
            return;
        }
    }
}





int main(){
    fastio
    int test=1;
    while(test--)
        solve();
    return 0;
}


Measured memory_bytes: 3544
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include <fstream>
#include <time.h>
#include <iterator>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;

const int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;

int cum[101];
vector<int>v;
signed main() {
	/*cin.tie(0);
	ios::sync_with_stdio(false);*/
	cum[0] = 0;
	int N; cin >> N;
	ll sum = 0;
	v.resize(N);
	REP(i, N) {
		cin >> v[i];
	}
	//VSORT(v);
	REP(i, N) {
		int x = v[i];
		cum[i + 1] = cum[i] + x;
		sum += x;
	}
	int ans = 100000000;
	REP(i, N + 1) {
		ans = min(ans, abs(sum - 2*cum[i]));
	}
	print(ans);
}


Measured memory_bytes: 256
from collections import namedtuple

Item = namedtuple('Item', 'value, weight')


def make_knapsack_resolver(num_items, max_capacity):
    dp = [[0] * (max_capacity + 1) for _ in range(num_items + 1)]
    items = [Item(*[int(x) for x in input().split()]) for _ in range(num_items)]

    def resolve():
        calc_recurrence()
        return dp[0][max_capacity]

    def calc_recurrence():
        for idx_item in range(num_items - 1, 0 - 1, -1):
            for remaining_capacity in range(1, max_capacity + 1):
                if remaining_capacity < items[idx_item].weight:
                    dp[idx_item][remaining_capacity] = dp[idx_item + 1][remaining_capacity]
                else:
                    dp[idx_item][remaining_capacity] = max(
                        dp[idx_item + 1][remaining_capacity],
                        dp[idx_item + 1][remaining_capacity - items[idx_item].weight] + items[idx_item].value
                    )

    return resolve()


if __name__ == '__main__':
    N, W = list(map(int, input().split()))
    resolver = make_knapsack_resolver(N, W)
    print(resolver)



Measured memory_bytes: 24724
#include <iostream>
#define MOD 1000000007

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    string k; cin >> k;
    int n = k.length();
    int d; cin >> d;
    long long dp[2][d];
    for (int i = 0; i < d; i++) dp[0][i] = 0;
    int pfx = 0;
    for (int i = 0; i < n; i++) {
        for (int ki = 0; ki < d; ki++) {
            dp[(i % 2) ^ 1][ki] = 0;
        }
        for (int j = 0; j < (i == n - 1 ? k[i] - '0' + 1 : k[i] - '0'); j++) {
            dp[(i % 2) ^ 1][(pfx + j) % d] += 1;
            dp[(i % 2) ^ 1][(pfx + j) % d] %= MOD;
        }
        for (int j = 0; j < 10; j++) {
            for (int ki = 0; ki < d; ki++) {
                dp[(i % 2) ^ 1][(ki + j) % d] += dp[i % 2][ki];
                dp[(i % 2) ^ 1][(ki + j) % d] %= MOD;
            }
        }
        pfx += k[i] - '0'; pfx %= d;
    }
    cout << (dp[n % 2][0] + MOD - 1) % MOD;
    return 0;
}


Measured memory_bytes: 256
def ReadMap(n, m):
  Map = {}
  for i in range(m):
    a = raw_input()
    b = list(a)
    if a.count('&')>0:
      j = a.index('&')
      PosCas = [j, i]
      b[j] = '.'
    Map[i] = b
  return Map, PosCas

def fill(SP, c1, c2):
  for x, y in SP:
    try:
      if Map[y][x] != c1: continue
    except: continue
    if x in [0, n-1] or y in [0, m-1]: return 1
    Map[y][x] = c2
    SP += [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]
  return 0

while 1:
  n, m = map(int, raw_input().split())
  if n == m == 0: break
  Map, PosCas = ReadMap(n, m)
  c = 0
  while 1:
    SP = [PosCas]
    if fill(SP, '.', '#'): break
    c += 1
    if fill(SP, '#', '.'): break
  print c

Measured memory_bytes: 12420
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define rrep(i, n) for (int i = (int)n-1; i >= 0; --i)
using namespace std;
using ll = long long;
template<typename T>
inline bool chmax(T& a, const T& b) {
    if (a < b){
        a = b;
        return true;
    }
    return false;
}
template<typename T>
inline bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T> vector<T> make_vec(size_t n) { return vector<T>(n); }
template<typename T, typename... Args> auto make_vec(size_t n, Args... args) {
    return vector<decltype(make_vec<T>(args...))>(n, make_vec<T>(args...));
}
template<typename T, typename U, typename... V>
typename enable_if<is_same<T, U>::value>::type fill_v(U& u, const V... v) { u = U(v...); }
template<typename T, typename U, typename... V>
typename enable_if<!is_same<T, U>::value>::type fill_v(U& u, const V... v) {
    for (auto& e : u) fill_v<T>(e, v...);
}

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

    int n;
    cin >> n;
    auto g = make_vec<pair<int, int>>(n, 0);
    rep(i, n-1) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    vector<int> dist1(n), dist2(n);
    auto dfs = [&](auto self, vector<int>& dist, int v, int p = -1) -> void {
        for (auto uw : g[v]) {
            int u = uw.first, w = uw.second;
            if (u == p) continue;
            dist[u] = dist[v] + w;
            self(self, dist, u, v);
        }
    };

    dfs(dfs, dist1, 0);
    int v = distance(dist1.begin(), max_element(dist1.begin(), dist1.end()));
    dist1.assign(n, 0);
    dfs(dfs, dist1, v);
    int u = distance(dist1.begin(), max_element(dist1.begin(), dist1.end()));
    dfs(dfs, dist2, u);

    rep(i, n) cout << max(dist1[i], dist2[i]) << '\n';
}



Measured memory_bytes: 3928
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n = sc.nextInt();
		int x = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		int cnt = 0;
		boolean b = true;
		for (int i = 0; i < n; i++) {
			if (x - a[i] >= 0) {
				cnt++;
				x -= a[i];
			} else {
				b = false;
				break;
			}
		}
		if (x > 0 && b) {
			cnt--;
		}
		System.out.println(cnt);
	}
}


Measured memory_bytes: 21844
#include<stdio.h>
const int N = 300;
const int M = 300;
int main()
{
	int n, m;
	while(scanf("%d %d",&n,&m))
	{
		if(n == 0 && m == n)
		{
			break;
		}
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < m; j++)
			{
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
		return 0;
} 


Measured memory_bytes: 2624
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
 
  while x % y != 0:
    z = y
    y = x % y
    x = z
  return y
 
def lcm(m,n):
  return int(m * n / gcd(m,n))
 
inputNum = list(map(int, input().split()))
a = inputNum[0]
b = inputNum[1]
 
print(lcm(a,b))

Measured memory_bytes: 3064
using System;

namespace ABC150A
{
	class Program
	{
		static void Main(string[] args)
		{
			string[] str = Console.ReadLine().Split(' ');
			int K = int.Parse(str[0]);
			int N = int.Parse(str[1]);
			Console.WriteLine(K * 500 >= N? "Yes":"No");
		}
	}
}

Measured memory_bytes: 11092
import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size, init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]


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


def II():
    return int(input())


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


N = II()

10**N-9**N-9**N+8**N

mod = 10**9+7

b = c = 1
a = 1
for i in range(N):
    a *= 10
    b *= 9
    b %= mod
    c *= 8
    c %= mod
    a %= mod

print((a-2*b+c) % mod)

#print(a, b, c)


Measured memory_bytes: 28592
# coding: utf-8
import array, bisect, collections, heapq, itertools, math, random, re, string, sys, time
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def solve(N, graph):
    # 与えられたグラフは単純かつ連結であることから、1から始める。
    used = [False] * (N + 1)
    used[1] = True
    # 1から初めて右と左両方に探索していく。
    right = []
    left = []

    next_node = 1
    while True:
        for node in graph[next_node]:
            if used[node] == False:
                used[node] = True
                next_node = node
                right.append(node)
                break
        else:
            break

    next_node = 1
    while True:
        for node in graph[next_node]:
            if used[node] == False:
                used[node] = True
                next_node = node
                left.append(node)
                break
        else:
            break

    ans = left[::-1] + [1] + right
    ans = list(map(str, ans))
    return ans


def main():
    N, M = ILI()
    graph = [[] for __ in range(N + 1)]
    for __ in range(M):
        A, B = ILI()
        graph[A].append(B)
        graph[B].append(A)
    ans = solve(N, graph)
    print(len(ans))
    print(" ".join(ans))


if __name__ == "__main__":
    main()


Measured memory_bytes: 34316
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

int main()
{
	char s[26] ,s0[26], t[26];
	int sn[26], ans=-1;
	scanf("%s", s);
	s0[0]='a';
	s0[1]='b';
	s0[2]='c';
	s0[3]='d';
	s0[4]='e';
	s0[5]='f';
	s0[6]='g';
	s0[7]='h';
	s0[8]='i';
	s0[9]='j';
	s0[10]='k';
	s0[11]='l';
	s0[12]='m';
	s0[13]='n';
	s0[14]='o';
	s0[15]='p';
	s0[16]='q';
	s0[17]='r';
	s0[18]='s';
	s0[19]='t';
	s0[20]='u';
	s0[21]='v';
	s0[22]='w';
	s0[23]='x';
	s0[24]='y';
	s0[25]='z';
	int l=(int)strlen(s);
	int k;
	if(l<26){
		for(int i=0; i<l; i++){
			t[i]=s[i];
		}
		for(k=0; k<26; k++){
			int a=0;
			for(int j=0; j<l; j++){
				if(s0[k]==s[j]){
					a=1;
				}
			}
			if(a==0){
				t[l]=s0[k];
				break;
			}
		}
		for(int i=0; i<l+1; i++){
			printf("%c", t[i]);
		}
		printf("\n");
	}else{
		for(int j=0; j<26; j++){
			for(int i=0; i<26; i++){
				if(s0[i]==s[j]){
					sn[j]=i;
				}
			}
		}
		for(k=25; k>0; k--){
			if(sn[k-1]<sn[k]){
				break;
			}
		}
		if(k==0){
			printf("%d\n", ans);
		}else{
			for(int i=0; i<k-1; i++){
				t[i]=s[i];
			}
			int m;
			for(m=25; m>=k; m--){
				if(sn[k-1]<sn[m]){
					break;
				}
			}
			t[k-1]=s[m];
			for(int i=0; i<k; i++){
				printf("%c", t[i]);
			}
			printf("\n");
			}
	}
	return 0;

}

Measured memory_bytes: 128
N , MOD = int(input()), int(1e9+7)

all_suffix = []
base = ['A', 'C', 'G', 'T']

for char1 in base:
    for char2 in base:
        for char3 in base:
            all_suffix.append(char1+char2+char3)

len_all_suffix = len(all_suffix)

def judge(last4):
    for i in range(4):
        tmp = list(last4)
        if i >= 1:
            tmp[i-1], tmp[i] = tmp[i], tmp[i-1]
        if ''.join(tmp).find('AGC') >= 0:
            return False
    return True

dp = [[0 for i in range(len_all_suffix)] for i in range(N-2)]

for i in range(len_all_suffix):
    if all_suffix[i]!='AGC' and all_suffix[i]!='GAC' and all_suffix[i]!='ACG':
        dp[0][all_suffix.index(all_suffix[i])] += 1

for i in range(1, N-2):
    for j in range(len_all_suffix):
        for char in base:
            if judge(all_suffix[j]+char):
                k = all_suffix.index(all_suffix[j][1:]+char)
                dp[i][k] += dp[i-1][j] % MOD

print(sum(dp[N-3])%MOD)


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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int n, a[100001];

int main() {
	cin >> n;
	inc(i, n) { cin >> a[i]; }
	
	/*
	sort(a, a + n);
	
	a[n] = -1;
	
	int ans = 0, p = -1, c = 0;
	inc(i, n + 1) {
		if(a[i] == p) { c++; } else { ans += (c % 2); p = a[i]; c = 0; }
	}
	
	cout << ans << endl;
	*/
	
	map<int, int> m;
	inc(i, n) { m[a[i]]++; }
	int ans = 0;
	FOR(it, m) { ans += (it -> SE) % 2; }
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
      int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
      }

int main() {
  long NUM = 1000000007;
  string S;
  cin >> S;
  vector<long> ans(13,0);
  vector<int> tenmod = {1,10,9,12,3,4};
  for(int i=0;i<S.size();i++){
    int ind = S.size() - 1 - i;
    char a = S.at(ind);
    int mod = tenmod.at(i % 6);
    if(a == '?'){
      if(i==0){
        ans = {1,1,1,1,1,1,1,1,1,1,0,0,0};
        continue;
      }
      vector<long> sub(13,0);
      for(int j=0;j<10;j++){
        int indsub = (mod * j) % 13;
        for(int k=0;k<13;k++){
	        sub.at((k+indsub)%13) += ans.at(k);
        }
      }
        for(int k=0;k<13;k++){
	        ans.at(k) = sub.at(k);
            ans.at(k) = ans.at(k) % NUM;
        }
      
    }else{
      int b = ctoi(a);
       if(i==0){
        ans = {0,0,0,0,0,0,0,0,0,0,0,0,0};
        ans.at(b) = 1;
        continue;
      }
       vector<long> sub(13,0);
       int indsub = (mod * b) % 13;
       for(int k=0;k<13;k++){
	       sub.at((k+indsub)%13) += ans.at(k);
       }
       for(int k=0;k<13;k++){
	       ans.at(k) = sub.at(k);
           ans.at(k) = ans.at(k) % NUM;
       }
    }
  }
  cout << ans.at(5) << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <stdlib.h>
#include <algorithm>
using namespace std;
long long a[100004];
int n, res;
bool cp(const long long &u, const long long &v){
	return u<v;
}
bool kt(int j){
	int i;
	long long s = a[j];
	for (i = 1; i <= n; i++)
	if (i != j)
		if (a[i] <= s * 2) s = s + a[i];
		else break;
	return s * 2 >= a[n];
}
void pro(){
	int d = 1, c = n, g;
	res = 0;
	while (d <= c){
		g = d + (c-d) / 2;
		if (kt(g) == true) {
			res = n - g + 1; c = g - 1;
		}
		else d = g + 1;
	}
}
void pro1(){
	int i;
	for (i = 1; i <= n; i++) a[i] += a[i - 1];
	for (i = n - 1; i > 0; i--)
	if (2 * a[i] < a[i + 1] - a[i]) {
		res = n - i;
		return;
	}
	res = n;
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	int i;
	for (i = 1; i <= n; i++) cin >> a[i];
	sort(a+1, a+n+1, cp);
	pro();
	cout << res;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int h, w; cin >> h >> w;
    int n = 10;
    vector<vi> C(n, vi(n));
    rep(i, n) rep(j, n) cin >> C[i][j];
    vector<vi> a(h, vi(w));
    rep(i, h) rep(j, w) cin >> a[i][j];

    vector<vi> dist = C;
    rep(k, n){
        rep(i, n){
            rep(j, n){
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int res = 0;
    rep(i, h){
        rep(j, w){
            if(a[i][j] == -1) continue;
            res += dist[a[i][j]][1];
        }
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main(){
 
 int N;
 cin >>N;
int A[N];
int rA[N];
int lA[N];

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

rA[0]=A[0];
for(int i=1; i<N;i++){
rA[i]=max(rA[i-1],A[i]);
}

lA[N-1]=A[N-1];
for(int i=N-2; i>=0;i--){
lA[i]=max(lA[i+1],A[i]);
}

cout<<lA[1]<<endl;

for(int i=1; i<N-1;i++){
cout<<max(rA[i-1],lA[i+1])<<endl;
}

cout<<rA[N-2]<<endl;

 return 0;
}

Measured memory_bytes: 3968
h,w = map(int,input().split())
lls = [list(input()) for _ in range(h)]
llt = [['#']*w for _ in range(h)]
for x in range(h):
  for y in range(w):
    if lls[x][y] == '#':
      continue
    cnt = 0
    for dx,dy in ((-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)):
      nx,ny = x+dx,y+dy
      if nx<0 or nx>=h or ny<0 or ny>=w:
        continue
      if lls[nx][ny] == '#':
        cnt += 1
    llt[x][y] = cnt
for l in llt:
  print(''.join(map(str,l)))

Measured memory_bytes: 3064
input = $stdin.read.split("\n")
input = input.slice(1, input.size - 1)
unless input.uniq.size == input.size
  puts 'No'
  exit
end

result = 'Yes'
input.each_with_index do |a, i|
  break if input.size - 1 == i
  a = a.split('')
  next_a = input[i + 1].split('')
  unless a[a.size - 1] == next_a[0]
    result = 'No'
    break
  end
end
puts result

Measured memory_bytes: 1916
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

int main(){

    size_t n, m;
    std::cin >> n >> m;

    std::vector<int> v(m);
    for(auto&& e : v){
        std::cin >> e;
    }
    
    std::sort(v.begin(), v.end());

    size_t sum = 0;
    std::priority_queue<size_t> q;
    for(size_t i = 1; i < m; i++){
        size_t diff = v.at(i) - v.at(i - 1);
        q.emplace(diff);
        sum += diff;
    }

    while(!q.empty() && n != 1){
        sum -= q.top();
        q.pop();
        n--;
    }

    std::cout << sum << std::endl;

    return 0;
}


Measured memory_bytes: 1784
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()

using namespace std;

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

  map<int, int> mp;
  for (int i = 2; i <= 13; ++i) mp[i] = i;
  mp[1] = 14;

  puts(mp[a] > mp[b] ? "Alice" : mp[a] < mp[b] ? "Bob" : "Draw");

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int f[10];
	f[a]++, f[b]++, f[c]++;
	if (f[5]==2 && f[7]==1) cout << "YES";
	else cout << "NO";
    return 0;
}

Measured memory_bytes: 256
N = int(input())
txy = [[0]*3 for _ in range(N)]
for i in range(N):
  txy[i] = list(map(int, input().split()))
flag = True
for sh in txy:
  Sxy = sh[1] + sh[2]
  if (Sxy % 2 == 0) ^ (sh[0] % 2 == 0):
    flag = False
  if sh[0] < Sxy:
    flag = False
  if not(flag):
    break
if flag:
  print("Yes")
else:
  print("No")

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

typedef pair<int,int> P;

P merge(P a,P b){
  int l=min(a.first,b.first);
  int r=max(a.second,b.second);
  return P(l,r);
}

int n,m;
vector< int > G[100001];
P t[200000];

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    t[i]=P(i,i);
  }
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    G[x].push_back(y);
  }
  for(int i=0;i<100001;i++){
    for(int j=0;j<(int)G[i].size();j++){
      int y=G[i][j];
      t[y-1]=t[y]=merge(t[y-1],t[y]);
    }
  }
  for(int i=0;i<n;i++){
    if(i)cout<<' ';
    cout<<t[i].second-t[i].first+1;
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 10132
#include <stdio.h>

int main() {
  int h, w, h_roop, w_roop;

  while(scanf("%d %d", &h, &w)) {
    if(h == 0 && w == 0) {
      break;
    } else {
      for(h_roop = 0; h_roop < h; h_roop++) {
        for(w_roop = 0; w_roop < w; w_roop++) {
          if(h_roop == 0 || h_roop == h - 1 || w_roop == 0 || w_roop == w - 1) {
            printf("#");
          } else {
            printf(".");
          }
        }
        puts("");
      }
      puts("");
    }
  }

  return 0;
}

Measured memory_bytes: 588
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
S = input()

res = 0
for i in range(N):
    s1 = S[:i]
    s2 = S[i:]
    ss1, ss2 = set(s1), set(s2)
    s = ss1&ss2
    val = len(s)
    if res < val:
        res = val

print(res)

Measured memory_bytes: 3316
from collections import defaultdict


def main():
    _ = input()
    a = [int(an) for an in input().split()]
    cnt = defaultdict(int)
    for an in a:
        cnt[an - 1] += 1
        cnt[an] += 1
        cnt[an + 1] += 1
    print(max(cnt.values()))


if __name__ == "__main__":
    main()


Measured memory_bytes: 91348
#include<stdio.h>
    
int main(){
  int a,b,d,r;
  double f;
  scanf("%d %d",&a,&b);

  d = a/b;
  r = a%b;
  f = 1.0*a/b;

  printf("%d %d %.5lf\n",d,r,f);

  return 0;
}


Measured memory_bytes: 2044
// 5/6
// 個数制限なしナップサック問題

#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>;
using Graph = vector<vector<int>>;

ll dp[400][400];
// const int INF = 1000000000;

int main() {
    int n;  // フレーズの数 < 393
    cin >> n;

    vector<int> s(n), l(n), p(n);  // 各フレーズの下限、上限、得点  < 393
    rep(i, n) cin >> s[i] >> l[i] >> p[i];

    int m;  // メロディの数  < 393
    cin >> m;

    vector<int> w(m);  // メロディの長さ  < 393 
    rep(i, m) cin >> w[i];

    int W = 393;  // メロディの長さの最大値

    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;

    rep(i, n) {
        rep(j, W + 1) {
            if (s[i] > j) {
                dp[i + 1][j] = dp[i][j];
            }
            else {
                // i番目を使わない場合で初期化
                dp[i + 1][j] = dp[i][j];

                // i番目を新しく使うときは、どの長さ（k）で使うかを分岐
                for (int k = s[i]; k <= min(l[i], j); k++) {
                    dp[i + 1][j] = max(dp[i + 1][j - k] + p[i], dp[i + 1][j]);  // マイナス１ならそれはそれで。
                }
            }
        }
    }

    bool b = true;
    
    rep(i, m) {
        if (dp[n][w[i]] == -1) b = false;
    }

    if (b) {
        rep(i, m) {
            cout << dp[n][w[i]] << endl;
        }
    } else {
        cout << -1 << endl;
    }

}


Measured memory_bytes: 4348
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    map<int, int> mp;
    int ans = 0;
    rep(i, n) {
        mp[a[i]]++;
        mp[a[i]-1]++;
        mp[a[i]+1]++;
    }
    int num = 0;
    for (auto m: mp) {
        if (m.second>num) {
            num = m.second;
        }
    }
    
    cout << num << endl;
    return 0;
}


Measured memory_bytes: 8084
N, M = map(int, input().split())
L = list(map(int, input().split()))

if N == 1:
	if L[0]%M == 0:
		print(1)
		exit()
	else:
		print(0)
		exit()

for i in range (0, N):
	L[i] = L[i]%M

count = 0

for i in range (1, N):
	L[i]= (L[i-1]+L[i])%M

L = sorted(L)

alreadythere = []
import collections

cnt = collections.Counter()
for number in L:
	cnt[number] += 1

L = set(L)

for i in L:
	if i == 0:
		K = cnt[i]
		count+=(int(K*(K-1)/2)+K)
	else:
		K = cnt[i]
		count+=int(K*(K-1)/2)

print(count)

Measured memory_bytes: 20732
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt() - 1;
		char[] c = sc.next().toCharArray();
		c[k] += 32;
		System.out.println(new String(c));
		sc.close();
	}
}


Measured memory_bytes: 21588
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("fma,avx")

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define sz(a) (int) (a).size()
#define all(a) (a).begin(), (a).end()
#define x first
#define y second

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

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

    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (i * (i + 1)) / 2;
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        if (u > v) swap(u, v);
        ans -= u * (n - v + 1);
    }
    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define BUF 50
#define INF 1<<30
using namespace std;
ll MOD = 1e9 + 7;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S;
ll ans = 0;
int main() {
	cin >> N;
	int x = 0, y = 0, t = 0;
	bool flag = 1;
	for (int i = 0; i < N; i++) {
		int T;
		cin >> T >> X >> Y;
		int tmp = T - t - abs(X - x) - abs(Y - y);
		if (tmp >= 0 && tmp % 2 == 0) {
			x = X; y = Y, t = T;
		}
		else {
			flag = 0;
			break;
		}
	}
	if (flag)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define ll long long
const int N = 1e6 + 10;
using namespace std;
int  a,b;
int main() {
    ios::sync_with_stdio(false);
    cin>>a>>b;
    int c=a-b;
    int ans=0;
    while(c>0){
        c=c-b;
        ans++;
    }
    cout<<ans+1<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int sum=0;
    for(int i=0;i<2;i++){
    if(a>b){
        sum+=a;
        a--;
    }else {
        sum+=b;
        b--;
    }
}
System.out.println(sum);
}
}

Measured memory_bytes: 23764
#include<iostream>
using namespace std;
int s[200][200];
int r,c,n;
int main()
{
	
	cin>>r>>c>>n;
	int x=1,y=1;
	

	for(int i=1;i<=n;i++)
	{
		int j;
		cin>>j;
		while(j--)
		{
			s[x][y]=i;
			if((x%2==1)&&(y!=c))
			y++;
			else if((x%2==1)&&(y==c))
			x++;
			else if((x%2==0)&&(y!=1))
			y--;
			else if((x%2==0)&&(y==1))
			x++;
		}
		
	}
	for(int i=1;i<=r;i++)
	{
		for(int j=1;j<=c;j++)
		{
		cout<<s[i][j]<<" ";
     	}
     	cout<<endl;
	}
	
	return 0;
} 

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG
#include "program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

struct UnionFind {
    vector<ll> par, s;
    UnionFind(ll n) : par(n), s(n, 1) { iota(ALL(par), 0); }
    ll find(ll x) {
        if(par[x] == x) return x;
        return par[x] = find(par[x]);
    }
    void unite(ll x, ll y) {
        x = find(x), y = find(y);
        if(x == y) return;
        if(s[x] < s[y]) par[x] = y, s[y] += s[x];
        else par[y] = x, s[x] += s[y];
    }
    bool same(int x, int y) { return find(x) == find(y); }
    ll size(int x) { return s[find(x)]; }
};

int main(void) {
    ll n, m;
    cin >> n >> m;
    vector<ll> h(n);
    REP(i, n) cin >> h[i];
    vector<vector<ll>> g(n);
    REP(i, m) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);    
    }

    ll ret = 0;
    REP(i, n) {
        bool flag = true;
        for(auto to: g[i]) {
            if(h[i] <= h[to]) flag = false;
        }
        ret += flag;
    }
    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 9728