akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
#define regsiter register
#define CL fclose(stdin),fclose(stdout)
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
	long long G()
	{
		long long n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=(n<<1)+(n<<3)+ch-'0';
		return F?n:-n;
	}
}
int d[333];
const int M=1000000007;
int f[2][333][666];
int fac[333];
int invf[333];
int ex(int b,int e)
{
	int ans=1;
	for(;e;e>>=1,b=(long long)b*b%M)
		if(e&1)ans=(long long)ans*b%M;
	return ans;
}
int main()
{
	int n=io::F();
	for(register int i=1;i<=n;++i)d[i]=io::F();
	fac[0]=1;
	for(register int i=1;i<=n;++i)fac[i]=(long long)fac[i-1]*i%M;
	int fl=1;
	for(register int i=1;i<=n;++i)if(d[i]!=2)fl=0;
	if(fl)
	{
		printf("%lld\n",fac[n-1]*(long long)(M+1>>1)%M);
		return 0;
	}
	invf[n]=ex(fac[n],M-2);
	for(register int i=n-1;i>=0;--i)invf[i]=(i+1)*(long long)invf[i+1]%M;
	int(*x)[666]=f[0],(*y)[666]=f[1];
	f[0][0][0]=1;
	for(register int i=1;i<=n;++i,std::swap(x,y))
	{
		for(register int j=0;j<=i;++j)
			for(register int k=0;k<=n+n;++k)
			{
				y[j][k]=x[j][k]*(long long)invf[d[i]-1]%M;
				if(d[i]>=2&&j>=1&&k+2>=d[i])y[j][k]=(y[j][k]+x[j-1][k-d[i]+2]*(long long)invf[d[i]-2])%M;				
			}
	}
	#define register
	int ans=0;
	for(register int i=3;i<n;++i)
		for(register int j=1;j<=n+n;++j)
			ans=(ans+(long long)x[i][j]*fac[n-i-1]%M*fac[i-1]%M*invf[j-1]%M*invf[2]%M*fac[j]%M)%M;
	printf("%d\n",ans);
	return 0;
}




Measured memory_bytes: 1792
#include <iostream>
#include <cstring>
using namespace std;
int main(){
char bad[101];
cin >> bad;
int a,b;
while(bad[0]!=0&&bad[1]!='\0'){
 a=0;b=0;
 for(int i=1;i<101;i++){
      if(bad[i]=='A'){
            a++;
       }else if(bad[i]=='B'){
            b++;
        }
  }
  if(a>b){
    a++;
  }else if(b>a){
    b++;
  }
  cout << a << ' ' << b << endl;
  for(int k=0;k<101;k++){
      bad[k]='\0';
  }
  cin >> bad;
}

return 0;
}

Measured memory_bytes: 1140
#include <bits/stdc++.h>
#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)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const ll INF = mod*mod;

int main() {
  ll n;
  cin >> n;
  vector<ll> t(5);
  ll p = INF;
  rep(i, 5) {
    cin >> t[i];
    p = min(p, t[i]);
  }
  ll ans = n / p + 4;
  if (n % p != 0) ans++;
  cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

int main (int argc, char *argv[]) {
    int n;
    string list = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    while (cin>>n, n) {
        int key[n] = {};
        string str;
        for (int i = 0; i < n; ++i) {
            cin>>key[i];
        }
        cin>>str;
        for (int i = 0; i < str.length(); ++i) {
            int num = i % n;
            int target = 0;
            for (int j = 0; j < list.length(); ++j) {
                if (str[i] == list[j]) {
                    target = j;
                    break;
                }
            }
            int lt = target - key[num];
            if (lt < 0) lt += 52; 
            str[i] = list[lt];
        }
        cout<<str<<endl;
    }
    return 0;
}


Measured memory_bytes: 3164
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N;
	string S[50];
	int alphamin[26];
	rep(i,26) alphamin[i]=INF;
	vector<string> Sbubun;
	scan(N);
	rep(i,N){
		scan(S[i]);
		int alpha[26]={0};
		rep(j,S[i].size()){
			alpha[S[i][j]-'a']++;
		}
		rep(j,26){
			alphamin[j]=min(alphamin[j],alpha[j]);
		}
	}
	rep(i,26){
		rep(j,alphamin[i]){
			printf("%c",'a'+i);
		}
	}
	kaigyo;
	return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import java.io.BufferedReader;
import java.math.BigInteger;
public class Main
{
	public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
       int m=Integer.parseInt(st.nextToken());
if(n+m==15)
  System.out.println("+");
else if(n*m==15)
System.out.println("*");
else
System.out.println("x");
}
}

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

using namespace std;

const int nax = 1e5+9;
vector<int> g[nax];
vector<int> dis(nax,0);
vector<int> in(nax,0);
vector<bool> vis(nax,0);

void dfs(int a)
{
	vis[a]=true;
	for(auto b: g[a])
	{
		dis[b] =max(dis[b],dis[a]+1);
		--in[b];
		if(in[b]==0)
		{
			dfs(b);
		}
	}
}

int main()
{
	int n ,m;
	cin>>n>>m;
	int a,b;	
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		g[a].push_back(b);
		in[b]++;
	}
	

	for(int i=1;i<=n;i++)
	{
		if(in[i]==0 and !vis[i])
			dfs(i);
	}
	
	int ans = 0;
	for(int i=1;i<=n;i++)	ans = max(ans,dis[i]);

	cout<<ans;
}

Measured memory_bytes: 9600
#include <iostream>

using namespace std;

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

    int debt = 100'000;

    while (n != 0) {
        debt *= 1.05;
        if (debt % 1000 != 0) {
            debt = (debt / 1000 + 1) * 1000;
        }
        --n;
    }

    cout << debt << endl;
}

Measured memory_bytes: 3080
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <atcoder/all>

#define F first
#define S second
#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace atcoder;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3000000;
const int K = 100000;
//const int mod = 998244353;

using mint = modint998244353;

mint p[N], s[N];
pair <int, int> a[N];
mint op (mint x, mint y){
    return x + y;
}
mint e (){
    mint x = 0;
    return x;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n, k;
    cin >> n >> k;
    mint q = 0;
    segtree <mint, op, e> t0(2 * n);
    for (int i = 1; i <= n; i++){
        cin >> a[i].F;
        t0.set(a[i].F, 1);
        if (i > k)
        q += t0.prod(a[i].F + 1, n + n);
        a[i].S = max(i - k + 1, 1LL);
    }
    mint x = k;
    mint y = (x - 1) / x;
    mint ans = x * (x - 1) / 2;
    p[0] = 1;
    for (int i = 1; i <= n; i++) p[i] = p[i - 1] * y;
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + p[i];
    for (int i = 1; n - i - k + 1 > 0; i++){
        ans += s[n - i - k + 1] ;
        if (i == 1){
            ans += (x - 1) * s[n - i - k + 1];
        }
    }
    ans /= 2;
    segtree <mint, op, e> t(2 * n);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++){
        mint z = t.get(a[i].S);
        mint q = y.pow(a[i].S);
        t.set(a[i].S, q + z);
        z = t.prod(a[i].S + 1, n + n);
        z *= y.pow(998244353 - a[i].S - 1);
        ans -= z;
    }
    ans += q;
    cout << ans.val();
}


Measured memory_bytes: 39708
/*
我的心脏怦怦跳，监管者就在附近
name:
Algorithm:
writer:Lxs(cdx)
place:
nothing is impossible
*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#include<string>
#include<iostream>
#include<cmath>
#include<set>
#include<stack>
#include<queue>
#include<unistd.h>
#include<stdio.h>
#include<cstring>
#define random(a,b) (rand()%(b-a+1)+a)
using namespace std;
bool prime(int x){
	 int i;
	 if(x<2) return 0;
	 for(i=2;i*i<=x;i++){
		if(x%i==0){return 0;}
	 }
	 return 1;
}
int main()
{
	char c;
	cin>>c;cout<<char(c+1);
	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 s, i, n = sc.nextInt(), k = sc.nextInt();
		s = k;
		for(i = 1; i < n; i++){
			s *= k-1;
		}
		System.out.println(s);
	}
}

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

#define MAX 10000
#define N 101


struct node{
  int key;
  struct node *next;
  struct node *prev;
} ;
typedef struct node *NodePointer;

void Insert(int);
void Deletekey(int);
NodePointer Search(int);
void Delete(NodePointer);

NodePointer nil;

int main()
{
  int i, n, keydata;
  char c[12];
  NodePointer x;


  nil = (NodePointer)malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;
  nil->key = -1;

  scanf("%d",&n);

  for(i = 0; i < n; i++) {
    scanf("%s",c);

    if(strcmp(c,"insert") == 0) {
      scanf("%d",&keydata);
      Insert(keydata);
    }
    else if(strcmp(c,"delete") == 0) {
      scanf("%d",&keydata);
      Deletekey(keydata);
    }
    else if(strcmp(c,"deleteFirst") == 0){
      Delete(nil->next);
    }
    else {
      Delete(nil->prev);
    }
  }

  x = nil->next;
  printf("%d",x->key);
  x = x->next;
  while(x != nil) {
    printf(" %d",x->key);
    x = x->next;
  }
  printf("\n");


  x = nil->next->next;
  while(x != nil) {
    free(x->prev);
    x = x->next;
  }
  free(nil);

  return 0;
}

void Insert(int keydata)
{
  NodePointer x;

  x = (NodePointer)malloc(sizeof(struct node));

  x->key = keydata;
  
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}

void Deletekey(int keydata)
{
  NodePointer x;

  if((x = Search(keydata)) == nil) return;

  Delete(x);
}

NodePointer Search(int keydata)
{
  NodePointer x;

  x = nil->next;
  while(x != nil && x->key != keydata) {
    x = x->next;
  }
  
  return x;
}

void Delete(NodePointer x)
{
  x->prev->next = x->next;
  x->next->prev = x->prev;
  free(x);
}



Measured memory_bytes: 33052
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int w,n;
        w = scan.nextInt();
        n = scan.nextInt();
        int[] x = new int[w];
        for(int i=0;i<w;i++){
            x[i]=i+1;
        }
        String str;
        String[] num = new String[2];
        int a,b;
        a=0;
        b=0;
        for(int i=0;i<n;i++){
            str = scan.next();
            num =  str.split(",",0);
            a = Integer.parseInt(num[0]);
            b = Integer.parseInt(num[1]);
            a--;
            b--;
            int c = x[a];
            x[a]=x[b];
            x[b]=c;
        }
        for(int i=0;i<w;i++){
            System.out.println(x[i]);
        }
    }
}


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

int main() {
	string S, AKIBA[16] = { "AKIHABARA", "AKIHABAR", "AKIHABRA", "AKIHABR", "AKIHBARA", "AKIHBAR", "AKIHBRA", "AKIHBR" };
	for (int i = 0; i < 8; i++) {
		AKIBA[i + 8] = AKIBA[i].substr(1, AKIBA[i].size() - 1);
	}
	bool check = false;
	cin >> S;
	for (int i = 0; i < 16; i++) {
		if (S == AKIBA[i]) {
			check = true;
		}
	}
	if (check) cout << "YES";
	else cout << "NO";
}

Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll INF=(1LL<<60);
const ld pi=acosl((ld)1);
const ll mod = 1000000007;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"

bool solve(){
    ll n,t;cin>>n>>t;
    vector<ll>A(n);
    vector<ll>B(n);
    rep(i,n)cin>>A[i]>>B[i];
    
    vector<vector<ll>>dp1(n+1,vector<ll>(t,0));
    vector<vector<ll>>dp2(n+1,vector<ll>(t,0));

    rep(i,n)rep(j,t){
        if(t+1<t)chmax(dp1[i][j+1],dp1[i][j]);
        if(j+A[i]<t)chmax(dp1[i+1][j+A[i]],dp1[i][j]+B[i]);
        chmax(dp1[i+1][j],dp1[i][j]);
    }

    //後ろからi個
    reverse(all(A));
    reverse(all(B));
    rep(i,n)rep(j,t){
        if(t+1<t)chmax(dp2[i][j+1],dp2[i][j]);
        if(j+A[i]<t)chmax(dp2[i+1][j+A[i]],dp2[i][j]+B[i]);
        chmax(dp2[i+1][j],dp2[i][j]);
    }
    reverse(all(B));
    ll ans=0;
    rep(i,n){
        rep(j,t){
            chmax(ans,dp1[i][j]+dp2[n-i-1][t-j-1]+B[i]);
            // cout<<i<<" "<<j<<" "<<dp1[i][j]+dp2[n-i-1][t-j-1]<<endl;
        }
    }
    cout<<ans<<endl;
    
    return false;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout<<fixed;
	cout<<setprecision(30);
	return solve();
}


Measured memory_bytes: 143232
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a,b;
	a=n%10;
	n/=10;
	int ans=1;
	int tmp=1;
	while(n>0){
		b=n%10;
		n/=10;
		if(a==b) tmp++;
		else{
			ans=max(tmp,ans);
			tmp=1;
		}
		a=b;
	}
	ans=max(tmp,ans);
	if(ans>=3) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> vi;
#define endl '\n'
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rf(i,a,b) for(int i=a;i>=b;i--) 
#define fast_io ios_base::sync_with_stdio(0);
#define show(x) cout<<x<<endl;
#define pret(x) cout<<x<<endl; return 0;
#define disp(x) cout<<x<<" ";
#define let(x,y) cout<<x<<" "<<y<<endl;
ll MOD=1e9+7;
const int maxn=2e5+5;

int32_t main(){
    fast_io;
    int n;
    cin >> n;
    int a[n];
    int tot = 0;
    for (int i = 0; i < n; ++i)
    {
    	cin >> a[i];
    	tot ^= a[i];
    }
    for (int i = 0; i < n; ++i)
    {
    	disp((tot ^ a[i]));
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 5072
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {

		//??\??????????????????????????????Scanner???????????§???????????????
		Scanner scan = new Scanner(System.in);

		while(scan.hasNext()){

			//1???????????????????????????boolean2?¬????????????§??°?????¶?????????????????????
			int[][] mapp = new int[12][12];

			//12????????????????????????
			for(int i = 0; i < 12; i++ ){
				//?¬?????????????????????????
				String text = scan.next();
				//char??????????????????????????\?????????
				char[] cArray = text.toCharArray();
				//0??¨1??????????????????????????????
				for(int j = 0; j < 12; j++){
					mapp[i][j] = Integer.parseInt(String.valueOf(cArray[j]));
				}
			}
			//??¢?´¢???????????£????????°??????????????????????????°
			int count = 0;
			//?????????????????????????????????????¢??????????????????????
			for(int i = 0; i < 12; i++){
				for(int j = 0; j < 12; j++){
					//??¶?????¢?´¢?????????????????????
					if(mapp[i][j] == 1){
						IslandMapp.check(i , j , mapp);
						//????¶?????????¨?????????1???????????????0????????????
						count++;
					}
				}
			}
			//??¨???
			System.out.println(count);
		}
		scan.close();
	}
}

class IslandMapp{
	int[][] sima;
	int tate;
	int yoko;


	public IslandMapp(int i, int j, int[][] mapp) {
		this.tate = i;
		this.yoko = j;
		this.sima = mapp;
	}


	public static void check(int tate , int yoko, int[][] sima){

		sima[tate][yoko] = 0;

		if(tate+1 < 12){
			if(sima[tate+1][yoko] == 1){
				check(tate+1 , yoko , sima);
			}
		}
		if(yoko+1 < 12){
			if(sima[tate][yoko+1] == 1){
				check(tate , yoko+1 , sima);
			}
		}
		if(tate-1 > -1){
			if(sima[tate-1][yoko] == 1){
				check(tate-1 , yoko , sima);
			}
		}
		if(yoko-1 > -1){
			if(sima[tate][yoko-1] == 1){
				check(tate , yoko-1 , sima);
			}
		}
	}
}

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


int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> s(M);
  int k, t;
  rep(i, M) {
    cin >> k;
    rep(_, k) {
      cin >> t;
      t--;
      s[i].push_back(t);
    }
  }
  vector<int> p(M);
  rep(i, M) cin >> p[i];
  
  int ans = 0;
  rep(bit, 1<<N) {
    int all_light = true;
    rep(i, M) {
      int n_on = 0;
      for (int t: s[i]) if (bit>>t & 1) n_on++;
      if (n_on % 2 != p[i]) all_light = false;
    }
    if (all_light) ans++;
  }
  cout << ans << endl;  

  return 0;
}


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

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

Measured memory_bytes: 1024
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
using namespace std;
typedef long long ll;
ll const INF = 1LL << 60;

vector<ll> search(ll x, vector<vector<pair<ll, ll>>> &g) {
  priority_queue<pair<ll, ll>> q;
  vector<ll> memo(g.size(), INF);
  memo[x] = 0;
  q.push({0, x});
  while (!q.empty()) {
    ll len = q.top().first;
    ll pos = q.top().second;
    q.pop();
    if (memo[pos] < len) continue;
    for (auto next : g[pos]) {
      ll next_len = memo[pos] + next.second;
      if (next_len < memo[next.first]) {
        memo[next.first] = next_len;
        q.push({next_len, next.first});
      }
    }
  }
  return memo;
}

int main() {
  ll N;
  cin >> N;
  vector<vector<pair<ll, ll>>> g(N);
  ll a, b, c;
  for (int i = 0; i < N - 1; i++) {
    cin >> a >> b >> c;
    a--, b--;
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }
  ll Q, K;
  cin >> Q >> K;
  K--;
  vector<ll> dist = search(K, g);
  ll x, y;
  for (int i = 0; i < Q; i++) {
    cin >> x >> y;
    x--, y--;
    cout << dist[x] + dist[y] << endl;
  }
}

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

using namespace std;

#ifdef _DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> p(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }

    vector<double> s(N + 1, 0);
    for (int i = 1; i < N + 1; i++) {
        s[i] = s[i - 1] + (p[i - 1] + 1) / 2.0;
    }
    double m = 0.0;
    for (int i = 0; i + K - 1 < N; ++i) {
        m = max(m, s[i + K] - s[i]);
    }

    printf("%.9f\n", m);
}


Measured memory_bytes: 2560
#include <bits/stdc++.h> 
using namespace std;
int main() {
  int d,n,place;
  cin>>d>>n;
  int a[n];
  for(int i=0;i<n;++i){
    int x;
    cin>>x;
    a[i]=x;
  }
  int dist[n];
  for(int i=0;i<n-1;++i){
    dist[i]=a[i+1]-a[i];
  }
  dist[n-1]=min(abs(a[n-1]-dist[0]),abs(a[0]-(a[n-1]-d)));
  for(int i:dist){  }
  int maxs=-n;
  for(int i:dist){
    maxs=max(maxs,i);
  }
  int sum=0;
  for(int i:dist){
    sum+=i;
  }
  cout<<sum-maxs;
}

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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using namespace std;

using ll=long long;
using ld=long double;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const int MOD=1e9+7;

template<typename T> bool chmin(T &a,const T b){if(a>b){a=b; return true;}return false;}
template<typename T> bool chmax(T &a,const T b){if(a<b){a=b; return true;}return false;}


int main(){
    ll N; cin >> N;
    vector<ll> cnt(5);
    for(auto &x : cnt) cin >> x;

    vector<ll> a(5);
    ll ans=0, mx=0;
    for(int i=0; i<5; i++){
        if(i == 0){
            a[i]=(N+cnt[i]-1)/cnt[i];
            ans+=max(a[i], 1LL);
        } 
        else{
            a[i]=(N+cnt[i]-1)/cnt[i];
            if(a[i] <= mx) ans+=1;
            else ans+=a[i]-mx+1;
        }
        chmax(mx, a[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3600
#include <stdio.h>
int main(void){
  int x[90000],y[90000],i=0,Count=0;
	
	while(1){
		
		scanf("%d %d",&x[i],&y[i]);
		
		if(x[i]==0 && y[i]==0){
			break;
		}
		i++;
		Count++;
	}
	for(i=0;i<Count;i++){
		if(x[i]<y[i]){
			printf("%d %d\n",x[i],y[i]);
		}
		else{
			printf("%d %d\n",y[i],x[i]);
		}
	}
  
  return 0;
}

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

using _i64 = int64_t;
using _u64 = uint64_t;
using _f64 = double;

#define _for(i, start, end) for(_i64 i = (_i64)start; i < (_i64)end; ++i)
#define _rep(i, number) _for(i, 0, number)
#define _foreach(e, data) for(auto& e : data)
#define _all(data) data.begin(), data.end()

template<typename type>
_i64 _size(const type& data) { return static_cast<_i64>(data.size()); }
template<typename type, size_t size>
_i64 _size(const type (&)[size]) { return static_cast<_i64>(size); }

enum _flag : bool { able = true, disable = false };

struct _time {
    _time(_flag flag) { check = flag; if(!check) { return; } gettime(start); }
    ~_time() {
        if(!check) { return; }; gettime(end);
        _i64 elapse = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cout << endl << "Time: " << elapse << " ms" << endl;
    }
    private:
    using _timer = chrono::time_point<chrono::system_clock>;
    _timer start, end; bool check;
    void gettime(_timer& time) { time = chrono::system_clock::now(); }
};

struct _ini { _ini() { ios::sync_with_stdio(false); cin.tie(nullptr); } } _ini;

_i64 _gcd(_i64 a, _i64 b) {
    return (max(a, b) % min(a, b) != 0 ? _gcd(min(a, b), max(a, b) % min(a, b)) : min(a, b));
}

_i64 _lcm(_i64 a, _i64 b) {
    return a * b / _gcd(a, b);
}

int main() {
    {
        _time time(disable);
        _i64 a, b;
        while(cin >> a >> b) { cout << _gcd(a, b) << " " << _lcm(a, b) << endl; }
    }
    return 0;
}


Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
//#define int long long

struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout <<fixed<<setprecision(12);
        cerr <<fixed<<setprecision(12);
    }
}IoSetup;

typedef long long ll;
typedef pair < int , int >  pii;
static constexpr const signed int INF = 0x3f3f3f3f;
static constexpr const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr const signed int SMOD = 1000000007;
static constexpr const signed int NMOD = 998244353;
static constexpr const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static constexpr const signed int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T &b){return(a<b?a=b,true:false);}
template<class T>bool chmin(T &a, const T &b){return(a>b?a=b,true:false);}
inline int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int a[200200], b[200200];

signed main() {

    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) cin >> a[i];

    int cnt = 0;
    
    for(int i = n; i > 0; i--) {
        int t = 0;
        for(int j = i; j <= n; j += i) 
            t ^= b[j];
        
        if(b[i] = a[i]^t) cnt++;
    }

    cout << cnt << endl;
    for(int i = 1, c = 0; i <= n; i++) {
        if(b[i]) {
            c++;
            cout << i << " \n"[c == cnt];
        }
    }
    
  
    return 0;
}



Measured memory_bytes: 2560
package main

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

type DisjointSetUnion struct {
	n            int
	parentOrSize []int
}

func New(n int) *DisjointSetUnion {
	d := &DisjointSetUnion{
		n:            n,
		parentOrSize: make([]int, n),
	}
	for i := range d.parentOrSize {
		d.parentOrSize[i] = -1
	}
	return d
}

func (d *DisjointSetUnion) Merge(a, b int) int {
	if !(0 <= a && a < d.n) {
		panic("")
	}
	if !(0 <= b && b < d.n) {
		panic("")
	}
	x, y := d.Leader(a), d.Leader(b)
	if x == y {
		return x
	}
	if -d.parentOrSize[x] < -d.parentOrSize[y] {
		x, y = y, x
	}
	d.parentOrSize[x] += d.parentOrSize[y]
	d.parentOrSize[y] = x
	return x
}

func (d *DisjointSetUnion) Same(a, b int) bool {
	if !(0 <= a && a < d.n) {
		panic("")
	}
	if !(0 <= b && b < d.n) {
		panic("")
	}
	return d.Leader(a) == d.Leader(b)
}

func (d *DisjointSetUnion) Leader(a int) int {
	if !(0 <= a && a < d.n) {
		panic("")
	}
	if d.parentOrSize[a] < 0 {
		return a
	}
	d.parentOrSize[a] = d.Leader(d.parentOrSize[a])
	return d.parentOrSize[a]
}

func (d *DisjointSetUnion) Size(a int) int {
	if !(0 <= a && a < d.n) {
		panic("")
	}
	return -d.parentOrSize[d.Leader(a)]
}

func (d *DisjointSetUnion) Groups() [][]int {
	leaderBuf, groupSize := make([]int, d.n), make([]int, d.n)
	for i := 0; i < d.n; i++ {
		leaderBuf[i] = d.Leader(i)
		groupSize[leaderBuf[i]]++
	}
	result := make([][]int, d.n)
	for i := 0; i < d.n; i++ {
		result[i] = make([]int, 0, groupSize[i])
	}
	for i := 0; i < d.n; i++ {
		result[leaderBuf[i]] = append(result[leaderBuf[i]], i)
	}
	eraseEmpty := func(a [][]int) [][]int {
		result := make([][]int, 0, len(a))
		for i := range a {
			if len(a[i]) != 0 {
				result = append(result, a[i])
			}
		}
		return result
	}
	return eraseEmpty(result)
}

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	// Code for C - Connect Cities
	var N, M int
	fmt.Scan(&N, &M)

	d := New(N)
	sc.Split(bufio.ScanWords)
	var A, B, count int
	for i := 0; i < M; i++ {
		A, B = nextInt(), nextInt()
		if !d.Same(A-1, B-1) {
			d.Merge(A-1, B-1)
			count++
		}
	}

	fmt.Println(N - count - 1)
}


Measured memory_bytes: 3788
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#ifdef __GXX_EXPERIMENTAL_CXX0X__
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#ifdef __GXX_EXPERIMENTAL_CXX0X__
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

#include <array>

using namespace std;

int main ()
{
	string s1 , s2;
	while( cin >> s1 >> s2 )
	{
		if( s1 == "0"&&s2 == "0" )return 0;
		int a = 0;
		for( size_t i = 0; i < 4; i++ )
		{
			a += s1[i] == s2[i];
		}
		cout << a << " ";
		vector<int>d(10,0);
		for( size_t i = 0; i < 4; i++ )
		{ 
			d[s1[i] - '0']++;
		}
		int b = 0;
		for( size_t i = 0; i < 4; i++ )
		{
			if( d[s2[i] - '0'] > 0 )
			{
				b++;
				d[s2[i] - '0']--;
			}
		}
		cout << b - a << endl;
	}
}

Measured memory_bytes: 1188
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var input_C = Console.ReadLine()
                .Split(' ').Select(i => int.Parse(i)).ToArray();
            double sunuke = 0;

            for (var i = 1;i< input_C[0]+1; i++)
            {
                //if (input_C[1] / i == 0) break;
                var coin = Math.Ceiling((Math.Log((double)((double)input_C[1] / (double)i), 2)));
                if (coin < 0) coin = 0;
                sunuke += (double)((double)1 / (double)input_C[0]) * Math.Pow(0.5,coin);
                
                //Console.WriteLine(input_C[1] / i));
                //Console.WriteLine(coin);
                //Console.WriteLine(sunuke);

            }
            Console.WriteLine(sunuke);
        }
    }
}


Measured memory_bytes: 13524
N, K = map(int,input().split())

mod = 10000000007

R = N-K

def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod
 
mod = 10 ** 9 + 7
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
 
for i in range(2, 2010 + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

for i in range(1,K+1):
    cb_b = cmb(K-1,i-1,mod)
    cb_r = cmb(N-K+1,i,mod)
    ans = cb_b*cb_r % mod
    print(int(ans))

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

int main(){

  int n,m;
  int c[301],v[301],d[301],l[301];
  int vdp[301][301];
  int ddp[301][301];
  int ldp[301][301];
  string s;

  while(cin >> n >> m){

    for(int i=0;i<n;i++){
      getline(cin,s);
      getline(cin,s); //なんかエンターキー押した時バグるので重ねて書いた。
      cin >> c[i] >> v[i] >> d[i] >> l[i];
    }

    memset(vdp,0,sizeof(vdp));
    memset(ddp,0,sizeof(ddp));
    memset(ldp,0,sizeof(ldp));

    for(int i=0;i<n;i++){
      for(int j=0;j<=m;j++){
	if(j < c[i]){
	  vdp[i+1][j] = vdp[i][j];
	  ddp[i+1][j] = ddp[i][j];
	  ldp[i+1][j] = ldp[i][j];
	}

	else{
	  vdp[i+1][j] = max(vdp[i+1][j-c[i]]+v[i],vdp[i][j]);
	  ddp[i+1][j] = max(ddp[i+1][j-c[i]]+d[i],ddp[i][j]);
	  ldp[i+1][j] = max(ldp[i+1][j-c[i]]+l[i],ldp[i][j]);
	}

      }
    }

    int ans = max(vdp[n][m],max(ddp[n][m],ldp[n][m]));

    cout << ans << endl;
  }
}

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

using namespace std;

const int N = 1e5 + 7;

int n, a[N];
long long s[N];

bool solve(int who) {
	long long base = a[who];
	for (int i = 0; i < n; i++) {
		if (i == who) continue;
		if (base * 2 >= a[i]) {
			base += a[i];
		} else {
			return false;
		}
	}
	return true;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a, a + n);
	int l = 0, r = n - 1;
	while (l < r) {
		int mid = (l + r) / 2;
		if (solve(mid)) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	if (solve(l)) {
		printf("%d\n", n - l);
	} else {
		printf("0\n");
	}
	return 0;
}


Measured memory_bytes: 640
diff_max = -10**10
n = int(input())
num_min = int(input())
for i in range(n-1):
    temp = int(input())
    if temp - num_min > diff_max:
        diff_max = temp - num_min
    if temp < num_min:
        num_min = temp
    
print(diff_max)


Measured memory_bytes: 5612
import java.util.*;

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

        int n = scanner.nextInt();
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i < n; i++) {
            map.put(i, 0);
        }

        for (int i = 1; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int length = calcLength(i, j, x, y);
                map.put(length, map.get(length) + 1);
            }
        }

        for (int i = 1; i < n; i++) {
            System.out.println(map.get(i));
        }
    }

    private static int calcLength(int i, int j, int x, int y) {
        int a = j - i;
        int b = Math.abs(x - i) + 1 + Math.abs(j - y);
//        int c = Math.abs(y - i) + 1 + Math.abs(j - x);

//        return Math.min(a, Math.min(b, c));
        return Math.min(a,b );
//        if (i <= x && j >= y) {
//            return ((j - i) - (y - x)) + 1;
//        } else if (i <= x && j < y) {
//            int lengthl = j - i;
//            int lengthr = (y - j) + (x - i) + 1;
//            return Math.min(lengthl, lengthr);
//        } else if (i > x && j >= y) {
//            int lengthl = j - i;
//            int lengthr = (i - x) + (j - y) + 1;
//            return Math.min(lengthl, lengthr);
//        } else {
//            return j - i;
//        }
    }
}


Measured memory_bytes: 49176
import collections
def ma():return map(int, input().split())#a,b,c,d or n,k
def lma():return list(map(int, input().split()))#x or y
a,b=ma()
x = lma()
c = collections.Counter(x)
k = c.most_common()
if b >= len(c):
    print(0)
else:
    s=0
    for i in range(b,len(c)):
        s+=k[i][1]
    print(s)





Measured memory_bytes: 39348
#include <iostream>
#include <map>

using namespace std;

int main() {
    int k,a,b;

    cin >> k >> a >> b;

    int max = (b / k) * k;

    if (a <= max) {
        cout << "OK" << endl;
    } else {
        cout << "NG" << endl;
    }

    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int ea[N*2],eb[N*2],ec[N],tot,n;
void add(int x,int y){
	tot++;ea[tot]=y;eb[tot]=ec[x];ec[x]=tot;
}
int d[N],q[N],f[N],sum,minx;
bool die[N];
char s[N];
int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0' || ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0' && ch<='9'){
		x=x*10+ch-'0';ch=getchar();
	}
	return x*f;
}
void topsort(){
	int t=1,w=0;
	for (int i=1;i<=n;++i) if (s[i]=='B' && d[i]==1) q[++w]=i;
	while (t<=w){
		int x=q[t++];die[x]=1;
		for (int i=ec[x];i;i=eb[i]){
			if (d[ea[i]]) d[ea[i]]--;
			if (s[ea[i]]=='B' && d[ea[i]]==1 && !die[ea[i]]) q[++w]=ea[i];
		}
	}
}
int check(int x){
	return (d[x]&1)^(s[x]=='W'); 
}
int val(int x){
	if (check(x)==1) return -2;
	else return 0;
}
void dfs(int fa,int x){
	sum+=(check(x)==1)+2;
	f[x]=val(x);
	for (int i=ec[x];i;i=eb[i]){
		if (ea[i]!=fa && !die[ea[i]]){
			dfs(x,ea[i]);
			minx=min(minx,f[x]+f[ea[i]]);
			f[x]=min(f[x],f[ea[i]]+val(x));
		}
	}
}
signed main(){
	n=read();
	for (int i=1;i<n;++i){
		int x=read(),y=read();
		add(x,y);add(y,x);d[x]++;d[y]++;
	}
	scanf("%s",s+1);
	topsort();int x;
	for (x=1;x<=n;++x) if (!die[x]) break;
	if (x>n) puts("0");
	else{
		dfs(0,x);sum-=2;cout<<sum+minx<<endl;
	}
	return 0;
}

Measured memory_bytes: 7296
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int MOD = 1e9+7, MAX = 1e9, larg = 1e5, INF = -1e9;
long long A,B,C,D,E,F,G,H,I,J,K,L,N,M,O,P,Q,R,S,T,U,V,W,X,Y,Z;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;
long long sum = 0;

typedef pair<int, int> Pa;
typedef long long ll;

vector<pair<char, int>> strcompress(string S, int N){
    int count = 1;
    char c = S[0];
    vector<pair<char, int>> vec; 
	rep(i, N-1){
		if(c == S[i+1]){
			count++;
		}else{
			vec.push_back(make_pair(c, count));
			count = 1;
			c = S[i+1];
		}
	}
	vec.push_back(make_pair(c, count));
    return vec;
}


int main() {
    cin >> A >> B >> C;
    cout << max(A,max(B,C))-min(A,min(B,C));
}

Measured memory_bytes: 256
n = int(input())

li = [[0] * 9 for _ in range(9)]

for i in range(1, n + 1):
    str_i = str(i)
    top = int(str_i[0])
    bottom = int(str_i[-1])
    if bottom == 0:
        continue
    li[top-1][bottom-1] += 1

cnt = 0
for i in range(1, n + 1):
    str_i = str(i)
    top = int(str_i[0])
    bottom = int(str_i[-1])
    if bottom == 0:
        continue
    cnt += li[bottom-1][top-1]

print(cnt)


Measured memory_bytes: 3064
//
// Created by 伊東麻沙美 on 2019/10/22.
//

#include<iostream>
#include<algorithm>
#include<stdlib.h>
using namespace std;


int main() {
    int A,B;
    cin>>A>>B;

    if(A<10&&B<10){
        cout<<A*B<<endl;
    }else{
        cout<<-1<<endl;
    }
     return 0;
}



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

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

  for(int i = 1; i <= n; ++i){
    cin >> s;
    if(s == "Y") {cout << "Four" << endl; break;}
    if(i == n) { cout << "Three" << endl;}
  }
}


Measured memory_bytes: 3492
#include<bits/stdc++.h>
using namespace std;
struct _IO{_IO(){ios::sync_with_stdio(0);cin.tie(0);}}_io;
typedef long long ll; typedef long double db;
const int N = 3e5 + 5, M = 1e9 + 7;

ll dp[500][500], a[500], b[500], pw[500][500], sum[500][500];

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) cin >> b[i];
  for (int i = 1; i <= 400; i++) {
    pw[i][0] = 1;
    for (int j = 1; j <= 400; j++) {
      pw[i][j] = pw[i][j-1] * i % M;
    }
  }
  for (int i = 1; i <= 400; i++) {
    for (int j = 0; j <= 400; j++) {
      sum[i][j] = (pw[i][j] + sum[i-1][j]) % M;
    }
  }
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
      for (int k = 0; k <= j; k++) {
        dp[i][j] += dp[i-1][j-k] * (sum[b[i]][k] - sum[a[i]][k] + pw[a[i]][k]) % M;
        dp[i][j] %= M;
      }
    }
  }
  cout << (dp[n][m] + M) % M;
}


Measured memory_bytes: 8364
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int const INF = 1001001001;


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

ll n;
cin >> n;

ll p = 26;
ll q = 0;
vl ppow(13);
vl table(12);
ppow[0] = 1;
rep(i,12) {
    q += p;
    ppow[i+1] = p;
    table[i] = q;
    p *= 26;
}
ll pre = 0;
int len;
rep(i,12) {
    if(n <= table[i]) {
        len = i+1;
        if(i != 0) pre = table[i-1];
        break;
    }
}
ll d = n - pre - 1;

drep(i, len) {
   ll m = d / ppow[i];
   cout << char(m + 'a');
   d -= ppow[i] * m;
}
cout << "\n";
return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,m;
  cin >> n >> m;
  cout << (n<m?0:10) << endl;
}


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

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

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }

using pint = pair<int,int>;
const int INF = 1<<29;

int N;
vector<int> A, B;

int solve() {
    vector<vector<int>> dp((1<<N)+1, vector<int>(55, INF));
    dp[0][0] = 0;
    for (int bit = 0; bit < (1<<N); ++bit) {
        int con = 0;
        for (int i = 0; i < N; ++i) if (bit & (1<<i)) ++con;
        
        // bit に含まれない残りの要素が何番目に対応するか
        vector<pint> ords;
        int iter = con;
        for (int i = 0; i < N; ++i)
            if (!(bit & (1<<i)))
                ords.emplace_back(i, iter++);

        for (int s = 0; s <= 50; ++s) {
            if (dp[bit][s] >= INF) continue;
            for (auto p : ords) {
                // p.first: もともとの a の index
                // p.second: dp[bit][s] の状態での index
                int ns = -1;
                if (abs(p.first - con) % 2 == 0) ns = A[p.first];
                else ns = B[p.first];

                if (ns >= s) {
                    chmin(dp[bit|(1<<p.first)][ns], dp[bit][s] + abs(p.second - con));
                }
            }
        }
    }
    int res = INF;
    for (int s = 0; s <= 50; ++s) chmin(res, dp[(1<<N)-1][s]);
    if (res < INF) return res;
    else return -1;
}

int main() {
    cin >> N;
    A.resize(N), B.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];
    cout << solve() << endl;
}


Measured memory_bytes: 67968
n = int(input())

p = 0
s = 0

for i in range(n):
    a,b = [int(x) for x in input().split()]
    if i == 0:
        p,s = a,b
    else:
        if a > p:
            p,s = a,b
        else:
            pass

print(p+s)

Measured memory_bytes: 3064
#include <iostream>
#define ll long long int
using namespace std;

int calc(int a){
		int x = a;
		int count = 0;
		while(x != 0){
				count += x % 10;
				x = x / 10;
		}
		return count;
}

int main(int argc, char const* argv[])
{
	int n;
	cin >> n;
	int min = 100001;
	for(int i = 1; i < n; i++){
			int b = n - i;
			ll sum = calc(i) + calc(b);
			if(sum < min)min = sum;
	}
	cout << min << endl;
	return 0;
}


Measured memory_bytes: 256
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

def main():
    s = int(ipt())
    dp = [0]*(s+1)

    for i in range(3,s+1):
        dp[i] += 1
        for j in range(3,i-2):
            dp[i] += dp[j]
        dp[i] %= mod

    print(dp[s])
    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 75352
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <algorithm> // std::sort(begin,end)
#include <utility> // std::swap

using namespace std;
using ll = long long;

int main(int argc, char const* argv[])
{
  int n;
  cin >>n;
  cout << (n-2)*180 << endl;



  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#include <cmath>
#include <queue>
#include <iomanip>
using namespace std;

#define INF 1e18
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)

signed main() {
    int h, w; cin >> h >> w;
    vector<string> s(h); rep(i, h) cin >> s[i];
    vector<vector<int>> cnt(h, vector<int> (w));

    rep(i, h) {
        vector<int> done(w);
        rep(j, w) {
            if(s[i][j] == '#') continue;
            if(done[j]) continue;
            int l = 0;
            while(j + l < w) {
                if(s[i][j + l] == '#') break;
                l++;
            }
            rep(k, l) {
                cnt[i][j + k] += l;
                done[j + k] = 1;
            }
        }
    }

    rep(j, w) {
        vector<int> done(h);
        rep(i, h) {
            if(s[i][j] == '#') continue;
            if(done[i]) continue;
            int l = 0;
            while(i + l < h) {
                if(s[i + l][j] == '#') break;
                l++;
            }
            rep(k, l) {
                cnt[i + k][j] += l;
                done[i + k] = 1;
            }
        }
    }

    int ans = 0;
    rep(i, h) rep(j, w) ans = max(ans, cnt[i][j] - 1);

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


Measured memory_bytes: 35712
function main(input) {
    const [n,k] = input.split('\n')[0].split(' ').map(v => parseInt(v, 10));
    const h = input.split('\n')[1].split(' ');
    console.log(h.filter(v => v >= k).length);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 27724
/*
 * main.cpp
 *
 *  Created on: 2011/04/03
 *      Author: satoki
 *      22:20 ~ 22:28
 */
#include <iostream>
#include <string.h>
using namespace std;

char cStr[21];

bool input() {
  scanf("%s", cStr);
  return true;
}

void manage() {
  int i;
  char tmp;
  for (i = 0; i < (int)string(cStr).size() / 2; i++) {
    tmp = cStr[i];
    cStr[i] = cStr[string(cStr).size() - i - 1];
    cStr[string(cStr).size() - i - 1] = tmp;
  }
}

int main() {
  input();
  manage();
  printf("%s\n", cStr);
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i,a[10],x=0;
	scanf("%d",&n);
	while(n)
	{
		a[x++]=n%10;
		n/=10;
	}
	if(a[0]==a[2])
	printf("Yes");
	else
	printf("No");
}

Measured memory_bytes: 256