akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    string s;
    cin >> s;
    int n = s.size();
    int pos = 0;
    ll ans = 0;
    while(pos < n)
    {
        ll l = 0;
        while(pos < n && s[pos] == '<')
        {
            pos++;
            l++;
        }
        if(pos == n)
        {
            ans += l*(1+l)/2;
            break;
        }
        ll r = 0;
        while(pos < n && s[pos] == '>')
        {
            pos++;
            r++;
        }
        if(l >= r)
        {
            ans += l*(1+l)/2 + (r-1)*r/2;
        }
        else
        {
            ans += r*(1+r)/2 + (l-1)*l/2;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 900
#include <bits/stdc++.h>
using namespace std;
#define what_is(x) cerr << #x << " is " << x << endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
typedef long long ll;
const int N = 1e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

int n;
int h[N];
int f[N];
int main()
{
	IOS
	cin >> n;
	for(int i=0; i<n; i++)
		cin >> h[i];
	f[0] = 0;
	f[1] = abs(h[1] - h[0]);
	for(int i=2; i<n; i++){
		f[i] = min(f[i-1] + abs(h[i]-h[i-1]), f[i-2] + abs(h[i]-h[i-2]));
	}
	cout << f[n-1] << endl;
	return 0;
}


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

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define all(x) (x).begin(), (x).end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

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

void fail() {
    cout << "NO\n";
    exit(0);
}

void go(auto& adj, vi& stones, vll& vup, int loc, int par) {
    ll tot = 0, vmax = 0;

    for (int nbr : adj[loc]) if (nbr != par) {
        go(adj, stones, vup, nbr, loc);
        tot += vup[nbr];
        vmax = max(vmax, vup[nbr]);
    }

    bool leaf = adj[loc].size() == 1;
    ll expect = leaf ? stones[loc] : 2 * stones[loc];

    if (loc == par) {
        if (tot != expect) fail();
        if (!leaf && 2 * vmax > tot) fail();
    } else {
        vup[loc] = leaf ? stones[loc] : expect - tot;
        if (vup[loc] < 0) fail();
        if (!leaf && 2 * max(vmax, vup[loc]) > expect) fail();
    }
}

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

    int N;
    cin >> N;

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

    vvi adj(N);
    for (int i = 0, u, v; i < N - 1; i++) {
        cin >> u >> v;
        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }

    vll vup(N);
    go(adj, stones, vup, 0, 0);

    cout << "YES\n";

    return 0;
}



Measured memory_bytes: 17536
#写経
#https://atcoder.jp/contests/abc170/submissions/14363499
import sys

def resolve():
    it = map(int,sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]
    
    if N == 1:
        print(1)
        return
    ax = max(A) + 1
    dp = [0] * ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
    ans = 0
    for ai in A:
        if dp[ai] == 1:
            ans += 1
    print(ans)
resolve()

Measured memory_bytes: 40028
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n=0;
  cin>>n;
  vector<int> shorui(n);
  for(int i=0;i<n;i++){
    cin>>shorui.at(i);
  }
 
  for(int i=0;i<n;i++){
    
    if(shorui.at(i)%2==0){
      if(shorui.at(i)%3!=0&&shorui.at(i)%5!=0){
        cout<<"DENIED"<<endl;
        return 0;
      }
    }
  }
  cout<<"APPROVED"<<endl;
}

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

using namespace std;

#define sz(v)           ((int)((v).size()))
#define clr(v, d)       memset(v, d, sizeof(v))
#define rep(i, v)       for(int i=0; i<sz(v); ++i)
#define lp(i, n)        for(int i=0; i<(int)(n); ++i)
#define lpi(i, j, n)    for(int i=(j); i<(int)(n); ++i)
#define lpd(i, j, n)    for(int i=(j); i>=(int)(n); --i)
#define INF             1000000000


typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;


int main()
{
	int a, b, c;
    cin >> a >> b >> c;
    cout << c - min(a-b, c);
    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

// #define OJ
#define pb push_back
#define F first
#define S second
#define N '\n'

#define WLL(t) while(t--)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define STF(i, a, b) for(size_t i = a; i < b; i++)
#define RFOR(i, a, b) for(int i = a; i >= b; i--)
#define SRF(i, a, b) for(size_t i = a;i >= b;i--)

#define ALL(v) v.begin(),v.end()
#define FPRECISE(x) cout<<fixed<<setprecision(x)
#define PRECISE(x) cout<<setprecision(x)
#define BOOL cout<<boolalpha
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)
#define MOD 1000000007

#define TO(v, type) static_cast<type>(v)
int main()
{
#ifdef OJ
	READ;
	WRITE;
#endif
	FASTIO;
	string word;
	cin>>word;
	size_t siz = word.size();
	if(word[siz-1] == 's'){
		cout<<word<<"es"<<N;
	}
	else{
		cout<<word<<"s"<<N;
	}
	return 0;
}


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

using namespace std;

int main(){
  int n;
  long long k;
  int q;
  cin >> n >> k >> q;
  vector<long long> sc(n, 0);
  for(int i = 0; i < q; i++){
  	int a;
    cin >> a;
    sc[a - 1]++;
  }
  
  for(int i = 0; i < n; i++){
  	if( (k - q + sc[i]) > 0){
    	cout<<"Yes"<<endl;
    }
    else
      	cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1408
#include<cstdio>
#include<map>
#include<queue>
using namespace std;
int co=0;
queue<int> q;
map<int,int> m;
int visited[100001],pos=0;
int main()
{
    int n,tmp;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&tmp);
        if(m.count(tmp)==0)
        {
            m[tmp]=pos;
            q.push(tmp);
            visited[pos++]=1;
        }
        else
            visited[m[tmp]]++;
    }
    while(!q.empty())
    {
        tmp=q.front();
        q.pop();
        if(visited[m[tmp]]>tmp)
            co+=visited[m[tmp]]-tmp;
        else if(visited[m[tmp]]<tmp)
            co+=visited[m[tmp]];
    }
    printf("%d",co);
}

Measured memory_bytes: 5504
/*C - Remainder Minimization 2019*/

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

int main(){

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

	int L, R;

	cin >> L >> R;

	int dif;
	int ans = 2020;

	dif = R - L;

	if(dif >= 2020){
		ans = 0;
	}
	else{


		for (int i = L; i < R; ++i)
		{
			for (int j = i + 1; j <= R; ++j)
			{
				int currAns = (i % 2019) * (j % 2019) % 2019;
					
				ans = min(ans, currAns);
				
				if (ans == 0)
					break;
			}

			if (ans == 0)
				break;
		}
	}

	cout << ans; 
	
	return 0;
}


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


// ????????????union-find tree
int P[10010];
void init(int N){
  for(int i=0; i<=N; i++){
    P[i] = i;
  }
}

int root(int a) {
  if(P[a]==a)return a; // a???root
  return (P[a] = root(P[a])); // a?????????root????±????, a????????¨??????
}
bool is_same_set(int a, int b){ // a??¨b???????????°?????????????±?????????????
  return root(a) == root(b);
}
void unite(int a, int b){ // a??¨b???????????°?????????????????¨??????
  P[root(a)] = root(b);
}
// ???????????§???union-find tree


int main(){
  int n;
  cin >> n;
  pair<int,int> E[1000010];
  int a;
  int k=0;
  int m=0;
  int S[10010], G[10010];
  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      cin >> a;
      E[k].first = a; // ????????????
      E[k].second = m; // ????????????
      S[m] = i;
      G[m] = j;
      k++;
      m++;
      
    }
  }
    
#if 0
  for(int i=0; i<n*n; i++){
    cout << E[i].first << " " << E[i].second;
    cout << " -> " << S[E[i].second] << " " << G[E[i].second] << endl;
  }
#endif


  sort(E, E+n*n);

#if 0
  cout << endl;
  for(int i=0; i<n*n; i++){
    cout << E[i].first << " " << E[i].second;
    cout << " -> " << S[E[i].second] << " " << G[E[i].second] << endl;
  }
#endif
  
  
  int T = 0; // ?£?T????????????
  init(n); // ??¢??°??????, ?????°??????????????°

  for(int i=0; i<n*n; i++){
    if(E[i].first!=-1){
      if(is_same_set(S[E[i].second],G[E[i].second])==0){
	T += E[i].first;
	unite(S[E[i].second],G[E[i].second]);
      }
    }
    
  }

  cout << T << endl;
}
  
  
  
  

Measured memory_bytes: 9048
// Problem : B - An Odd Problem
// Contest : AtCoder - AIsing Programming Contest 2020
// URL : https://atcoder.jp/contests/aising2020/tasks/aising2020_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1};
int dy1[]={1,-1,0,0};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
	int n;cin>>n;
	vi v(n);cin>>v;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if((i&1)and (v[i-1]&1))
		cnt++;
	}
	cout<<cnt;
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

    int x3 = y1 - y2 + x2;
    int y3 = -x1 + x2 + y2;
    int x4 = y2 - y3 + x3;
    int y4 = -x2 + x3 + y3;

    printf("%d %d %d %d\n", x3, y3, x4, y4);
}

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

using namespace std;

#define fcout(d) cout << fixed << setprecision(d)
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rep1(i,n) for(int (i) = 1; (i) <= (n); ++(i))
#define repU(i,bottom,ceiling) for(auto (i) = (bottom); (i) <= (ceiling); ++(i))
#define repD(i,ceiling,bottom) for(auto (i) = (ceiling); (i) >= (bottom); --(i))
#define all(v)  begin(v),end(v)
#define clr(v) fill(all(v),0)
#define l_bnd lower_bound
#define u_bnd upper_bound
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define fir first
#define sec second
#define q_ceil(n,d) ((n - 1)/(d) + 1)
#define parity(a,b) ((a)^(b) & 1LL ^ 1LL)

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

const pair<int,int> DIR[] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} };
const int INF_32 = -1 + (1 << 30);
const ll INF_64 = -1 + (1LL << 62);
const int MOD = 1e9 + 7;

void Prime_table(bool *is_prime, int n){
	fill(is_prime + 2, is_prime + n + 1, 1);
	repU(i,2,n/2) is_prime[i * 2] = 0;
	is_prime[0] = is_prime[1] = 0;
	int p = 3;
	while(p * p <= n){
		for(int t = p * 3; t <= n; t += p * 2) is_prime[t] = 0;
		p += 2;
		while(!is_prime[p]) p += 2;
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin>>n;
	bool is[1001];
	ll ans = 1;
	Prime_table(is,n);
	rep1(i,n){
		if(is[i]){
			ll t = i,u = 0;
			while(t <= n){
				u += n / t;
				t *= i;
			}
			ans *= (1 + u);
			ans %= MOD;
		}
	}
	cout<<ans<<endl;
	
	return 0;
}





Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))

count = 0
for i, pi in enumerate(p):
    if i == 0 or i == n-1:
        continue
    if p[i-1] < pi < p[i+1] or p[i-1] > pi > p[i+1]:
        count += 1
print(count)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define P 1000000007
#define ll long long
#define N (1<<17)
#define pii pair<int, int>
#define F first
#define S second

using namespace std;

int h, w;
ll d[1010][1010];
char c[1010][1010];

int main(){

	cin >> h >> w;

	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			cin >> c[i][j];
		}
	}

	d[0][0] = 1;

	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(c[i][j] == '#') continue;
			if(i>0) d[i][j] = d[i-1][j];
			if(j>0) d[i][j] = (d[i][j]+d[i][j-1])%P;
		}
	}

	cout << d[h-1][w-1] << endl;

	return 0;

}


Measured memory_bytes: 9216
object Scanner {
  private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0
  @inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
  @inline private def hasNextByte(): Boolean =
    if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else { true }
  @inline private def hasNext(): Boolean = {
    while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
    hasNextByte()
  }
  @inline private def readByte(): Byte =
    if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else { -1 }
  def next(): String = {
    if(!hasNext()) ???
    val sb = new StringBuilder; var b = readByte()
    while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
    sb.toString
  }
  def nextInt(): Int = {
    val n = nextLong()
    if (n < Int.MinValue || Int.MaxValue < n) ???
    n.toInt
  }
  def nextLong(): Long = {
    if(!hasNext()) ???
    var minus = false; var b = readByte()
    if (b == '-') { minus = true; b = readByte() }
    def go (b: Byte, n: Long = 0): Long =
      if ('0' <= b && b <= '9') { go(readByte(), n * 10 + b - '0') }
      else if (minus) { -n } else { n }
    go(b)
  }
  def nextDouble(): Double = next.toDouble
}

object Main extends App {
  val n = Scanner.nextInt()
  val v = Array.fill(n)(Scanner.nextInt())
  val c = Array.fill(n)(Scanner.nextInt())
  var result = 0
  for (i <- 0 until n){
    if ((v(i)-c(i))>0){
      result += v(i)-c(i)
    }
  }
  println(result)
}

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

using namespace std;

int main(void) {
  int temp;
  cin >> temp;
  string colors;
  cin >> colors;
  
  int n = 0;
  for (int i = 1;i < colors.size();i++) {
    if (colors[i-1] != colors[i]) n++;
  }
  
  cout << n+1 << endl;

  return 0;
}

Measured memory_bytes: 512
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 2e5+7;
long long int ar[maxn];
int main()
{
    int n;
    cin>>n;
    for(int i = 0 ; i < n ; i++){
     //   scanf("%d" , &ar[i]);
        cin>>ar[i];
    }
    for(int i = 1 ; i < n ; i++){
        ar[i] += ar[i-1];
        //ŝcout<<ar[i]<<endl;
    }
    long long int ans = 1e18;
    for(int i = 0 ; i < n-1 ; i++){
        long long int p = ar[n-1]-ar[i];
        long long int re = abs(p-ar[i]);
        ans = min(ans , re);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T&v)
{fill((T*)array,(T*)(array+N),v);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
ll DP[100005][2], a[100005], n, k, su[100005];
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> k;
  FOR(i, 0, n) cin >> a[i];
  ll s = 0;
  FOR(i, 0, k) s += a[i];
  FOR(i, k, n+1){
    su[i-k] = s;
    s += a[i] - a[i-k];
  }
  s = 0;
  FOR(i, 0, n+1){
    DP[i][0] = s;
    s += max(0ll, a[i]);
  }
  s = 0;
  FORR(i, n-1, 0){
    s += max(0ll, a[i]);
    DP[i][1] = s;
  }
  ll ans = 0;
  FOR(i, 0, n-k+1) maxs(ans, DP[i][0] + DP[i+k][1] + max(0ll, su[i]));
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3328
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int main(){
	int n,l;
	cin >> n >> l;
	int origin = 0;
	int tmp;
	int min = 100000;
	int m;
	for (int i = 1; i <= n; i++) {
		origin += (i + l - 1);
		tmp = abs(i + l - 1);
		if (min > tmp) {
			min = tmp;
			m = (i + l - 1);
		}
	}
	origin -= m;
	cout << origin;

	return 0;
}

Measured memory_bytes: 256
N = gets.to_i
C = gets.split.map{|c| [c[0], c[1].to_i]}

bubble = ->(ary) do
  swap = true
  while swap
    swap = false
    0.step(N-2) do |i|
      ary[i], ary[i+1], swap = ary[i+1], ary[i], true if ary[i][1] > ary[i+1][1]
    end
  end
  ary.map(&:join).join ' '
end

selection = ->(ary) do
  0.step(N-1) do |i|
    min = i
    i.step(N-1) do |j|
      min = j if ary[min][1] > ary[j][1]
    end
    ary[i], ary[min] = ary[min], ary[i]
  end
  ary.map(&:join).join ' '
end

b = bubble.(C.dup)
puts b
puts 'Stable'
s = selection.(C.dup)
puts s
puts (b == s ? 'Stable' : 'Not stable')


Measured memory_bytes: 6884
def solve(x,y):
    lx=len(x)
    ly=len(y)
    dp=[0]*(ly+1)
    for i in range(lx):
        bef=dp[:]
        for j in range(ly): 
            # print(str(i)+" "+str(j))
            if x[i]==y[j]:
                dp[j+1]=bef[j]+1
            elif dp[j+1]<dp[j]:
                dp[j+1]=dp[j]
    print(dp[ly])

if __name__ == "__main__":
    q=int(input())
    for i in range(q):
        x=list(input())
        y=list(input())
        solve(x,y)



Measured memory_bytes: 5636
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>

using namespace std;
typedef long long int LL;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int xcomp(vector<int>& a, vector<int>& b) {
	return a[0] < b[0];
}

int ycomp(vector<int>& a, vector<int>& b) {
	return a[1] < b[1];
}

#define XSORT(c) sort((c).begin(),(c).end(),xcomp)
#define YSORT(c) sort((c).begin(),(c).end(),ycomp)

#define ALL(x) (x).begin(),(x).end()


LL mod = 1000000007;
int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int x = c - a;
	int y = d - b;
	REP(i, y) {
		cout << "U";
	}
	REP(i, x) {
		cout << "R";
	}
	REP(i, y) {
		cout << "D";
	}
	REP(i, x) {
		cout << "L";
	}
	cout << "L";
	REP(i, y) {
		cout << "U";
	}
	cout << "U";
	cout << "R";
	REP(i, x) {
		cout << "R";
	}
	cout << "D";
	cout << "R";
	cout << "D";
	REP(i, y) {
		cout << "D";
	}
	cout << "L";
	REP(i, x) {
		cout << "L";
	}
	cout << "U";
	cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() { 
    //freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int a,b;
	cin>>a>>b;
	b=b*2+1;
	cout<<(a+b-1)/b<<endl;
    return 0; 
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static PrintWriter pw;
	static int n;

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		pw = new PrintWriter(System.out);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		HashSet<Integer>hs =  new HashSet<Integer>();
		for(int i =1;i<=n;i+=2){
			hs.add(i);
		}
		pw.println(hs.size()>=k?"YES":"NO");
		pw.flush();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}


Measured memory_bytes: 23124
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

enum{STRAIGHT,RIGHT,BACK,LEFT,HALT,N};
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};

class Robot{
public:
  int y,x,dir,cost;
  Robot(){};
  Robot(int i,int j,int d,int c):y(i),x(j),dir(d),cost(c){}
  void move(int d,int c){
    switch(d){
      case STRAIGHT:
        break;
      case RIGHT:
        dir=(dir+1)%4;
	break;
      case BACK:
        dir=(dir+2)%4;
	break;
      case LEFT:
        dir=(dir+3)%4;
	break;
    }
    y+=dy[dir];
    x+=dx[dir];
    cost+=c;
  }
  bool operator<(const Robot &r)const{return cost>r.cost;}// {}ÌOÉconstªKv
};

int w,h;
vector< vector<int> >s;
vector<int>c(N);
vector< vector< vector<int> > >visited;

bool valid(Robot r){return 0<=r.y && r.y<h && 0<=r.x && r.x<w;}

int Dijkstra(){
  priority_queue<Robot>q;
  q.push(Robot(0,0,0,0));
  while(!q.empty()){
    Robot current=q.top();
    q.pop();
    if(current.y==h-1 && current.x==w-1)return current.cost;
    visited[current.y][current.x][current.dir]=1;
    Robot next=current;
    next.move(s[current.y][current.x],0);
    if(s[current.y][current.x]!=HALT && valid(next) && visited[next.y][next.x][next.dir]==0)q.push(next);
    for(int i=0;i<4;i++){
      Robot next=current;
      next.move(i,c[i]);
      if(valid(next) && visited[next.y][next.x][next.dir]==0)q.push(next);
    }
  }
  return -1;
}

int main()
{
  while(cin>>w>>h,w|h){
    // }XÌîñðüÍ
    s.resize(h);
    for(int i=0;i<h;i++){
      s[i].resize(w);
      for(int j=0;j<w;j++){
	cin>>s[i][j];
      }
    }
    // â~ÈOÌRXgðüÍ
    for(int i=0;i<N-1;i++){
      cin>>c[i];
    }
    // ú»
    visited.resize(h);
    for(int i=0;i<h;i++){
      visited[i].resize(w);
      for(int j=0;j<w;j++){
	visited[i][j].resize(4);
	for(int k=0;k<4;k++){
	  visited[i][j][k]=0;
	}
      }
    }
    // Tõ
    cout<<Dijkstra()<<endl;
  }
}

Measured memory_bytes: 1096
a, b, m = map(int, input().split())
a_l = list(map(int, input().split()))
b_l = list(map(int, input().split()))
x_y_c = [list(map(int, input().split())) for _ in range(m)]

a_l_s = sorted(a_l)
b_l_s = sorted(b_l)

min_price = (10 ** 5) * 3
for i in range(m):
    price = a_l[x_y_c[i][0] - 1] + b_l[x_y_c[i][1] - 1] - x_y_c[i][2]
    if price < min_price:
        min_price = price

tmp = a_l_s[0] + b_l_s[0]
if tmp < min_price:
    print(tmp)
else:
    print(min_price)


Measured memory_bytes: 40488
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

readInt = fst . fromJust . BS.readInt

readIntList = map readInt . BS.words

getIntList = readIntList <$> BS.getLine

main = do
  [a, b, c] <- getIntList
  putStrLn $ if all (== a) [b, c] || (a /= b && b /= c && a /= c) then "No" else "Yes"


Measured memory_bytes: 3736
#include <stdio.h>
#include <iostream>
#include <string>
#include <math.h>
#define NUM1 2000000
#define NUM2 1999997
using namespace std;

int str2num(char s){
    if(s == 'A'){
        return 1;
    }else if(s == 'C'){
        return 2;
    }else if(s == 'G'){
        return 3;
    }else if(s == 'T'){
        return 4;
    }
    return 100;
}

char num2str(int n){
    if(n == 1){
        return 'A';
    }else if(n == 2){
        return 'C';
    }else if(n == 3){
        return 'G';
    }else if(n == 4){
        return 'T';
    }
    return 'T';
}

int str2hash(string s){
    int num = 0;
    for(int i = 0; i < s.size(); i++){
        num += str2num(s[i]) * pow(5, i);
    }
    return num;
}

string hash2str(int num){
    string s = "";
    while(num){
        s.push_back(num2str(num % 5));
        num = num / 5;
    }
    return s;
}

void insert_number(int num, int* h1){
    int k = 0;
    while(k < NUM1){
        if(h1[(num % NUM1 + k * ((num + 1) % NUM2)) % NUM1] == num){
            return;
        }else if(h1[(num % NUM1 + k * ((num + 1) % NUM2)) % NUM1] == -1){
            h1[(num % NUM1 + k * ((num + 1) % NUM2)) % NUM1] = num;
            return;
        }else{
            k++;
        }
    }
    printf("error: %d\n", num);
    return;
}

bool in_number(int num, int* h1){
    int k = 0;
    while(k < NUM1){
        if(h1[(num % NUM1 + k * ((num + 1) % NUM2)) % NUM1] == num){
            //printf("%d\n", (num % NUM1 + k * ((num + 1) % NUM2)) % NUM1);
            return true;
        }else if(h1[(num % NUM1 + k * ((num + 1) % NUM2)) % NUM1] == -1){
            return false;
        }else{
            k++;
        }
    }
    return false;
}


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

    int h1[NUM1];
    for(int i = 0; i < NUM1; i++){
        h1[i] = -1;
    }

    char command[10];
    char c_char[13];
    for(int i = 0; i < n; i++){
       scanf("%s %s", command, c_char);
       if(command[0] == 'i'){
           string s_ = c_char;
           insert_number(str2hash(s_), h1);
       }else{
           string s_ = c_char;
           if(in_number(str2hash(s_), h1)){
               printf("yes\n");
           }else{
               printf("no\n");
           }
       }
    }
}



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

int main() {
	long n,m,d;
	cin>>n;
	m=n;
	while(n!=0){
		d+=n%10;
		n/=10;
	}
	if(m%d==0){
		cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
	return 0;
}

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

int main(){
    long long n,z,w;
    cin>>n>>z>>w;
    long long a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    if(n>1)cout<<max(abs(a[n-2]-a[n-1]),abs(a[n-1]-w));
    else cout<<abs(a[0]-w);
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>
 
using namespace std;
using ll = long long;
 
void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
ll gcd(ll a, ll b){ return (b == 0) ? a : gcd(b, a % b); }
ll lcm(ll a, ll b){ return a/gcd(a, b)*b; };
 
#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Unique(a) a.erase(unique(Range(a)), a.end());
#define Reverse(c) reverse(Range(c))
#define Vec2(T, n, m, xs) vector<vector<T>> xs(n, vector<T>(m))
#define Sum(a) accumulate(Range(a), 0)
#define Cusum(T, n, xs, sxs) vector<T> sxs(n+1); For(i, n) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) for(const auto &e : xs) cout << e << " "; cout << "\n"
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")

int main(void){
    Cin(ll, n);
    Cout((n-1)/11 * 2 + (((n-1) % 11 > 5) ? 2 : 1));
}


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

int main(){
    
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a_price, b_price, ab_price, a_needed, b_needed;
    cin >> a_price >> b_price >> ab_price >> a_needed >> b_needed;
    
    if((a_price+b_price+1)/2<=ab_price){
        cout << a_price * a_needed + b_price * b_needed << endl;
    } else {
        
        ll gathered_value;
        
        if(a_needed>b_needed){
            gathered_value = ab_price * min(a_needed,b_needed) * 2 + a_price * (a_needed - b_needed);
        } else if(a_needed<b_needed){
            gathered_value = ab_price * min(a_needed,b_needed) * 2 + b_price * (b_needed - a_needed);
        } else {
            cout << ab_price * min(a_needed,b_needed) * 2 << endl;
            return 0;
        }
        
        int c = min(a_needed,b_needed);
        int d = max(a_needed,b_needed);
        
        if(a_needed > b_needed){
            for(int i = c + 1; i <= d; i++){
                ll added_value = ab_price*i*2 + a_price*(d-i);
                gathered_value = min(added_value,gathered_value);
                
            }
        } else if(b_needed > a_needed){
            for(int i = c + 1; i <= d; i++){
                ll added_value = ab_price*i*2 + b_price*(d-i);
                gathered_value = min(added_value,gathered_value);
                
            }
        }
        cout << gathered_value << endl;
    }
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,k,n) for(ll i= (ll) k;i< (ll) n;i++)
#define all(v) (v).begin(), (v).end()
#define SZ(v) (int)((v).size())
#define pb push_back
#define ft first
#define sd second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const long long INF = 1e18L + 1;
const int IINF = 1e9 + 1;

using namespace std;

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

#ifdef LOCAL
#define DBG(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define DBG(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

struct seg {
	int a, b, nr;
};

int dist(int& p, seg s) {
	DBG(s.nr, s.a, s.b, p);
	if (p < s.a) {
		int r = s.a - p;
		p = s.a;
		return r;
	}
	if (p > s.b) {
		int r = p - s.b;
		p = s.b;
		return r;
	}
	return 0;
}

ll check(vector<seg>& s1, vector<seg>& s2) {
	int n = SZ(s1);
	DBG(n);
	vector<int> used(n);
	int i = 0, j = 0;
	int g = 0, pos = 0;
	ll wyn = 0;
	rep (_, 0, n) {
		DBG(_, i, s1[i].nr, j, s2[j].nr, g, wyn);
		if (g == 0) {
			DBG(used[s1[i].nr]);
			while (used[s1[i].nr]) {
				i++;
			}
			wyn += dist(pos, s1[i]);
			used[s1[i].nr] = 1;
			g = 1 - g;
		} else {
			while (used[s2[j].nr]) {
				j++;
			}
			wyn += dist(pos, s2[j]);
			used[s2[j].nr] = 1;
			g = 1 - g;
		}
	}
	return wyn + abs(pos);
}
	

int main() {
	#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	#endif
	int n;
	cin >> n;
	vector<seg> segsl, segsr;
	rep (i, 0, n) {
		int l, r;
		cin >> l >> r;
		segsl.pb({l, r, (int)i});
		segsr.pb({l, r, (int)i});
	}
	sort(all(segsl), [] (seg x, seg y) {return x.b < y.b or (x.b == y.b and x.nr < y.nr);});
	sort(all(segsr), [] (seg x, seg y) {return x.a > y.a or (x.a == y.a and x.nr < y.nr);});
	cout << max(check(segsl, segsr), check(segsr, segsl));
}


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

#define vi vector<int>
#define vii vector<vi>
#define pi pair<int,int>
#define vpi vector<pi>
#define S second
#define F first
#define pb push_back
#define inf 1000000
#define Test int t;cin>>t;while(t--)
#define MAXN 100005
#define int long long int
#define mod 1000000007

signed main()
{
    int N,W,i,j;
    cin>>N>>W;
    int w[N],v[N];
    for(i=0;i<N;i++)
    {
      cin>>w[i]>>v[i];
    }
    int dp[N+1][W+1];
    for(i=0;i<=N;i++)
      dp[i][0] = 0;
    for(i=0;i<=W;i++)
      dp[0][i] = 0;
    for(i=1;i<=N;i++)
      for(j=1;j<=W;j++)
        {
          dp[i][j] = dp[i-1][j];
          if(j-w[i-1]>=0)
            {
              dp[i][j] = max(dp[i-1][j],v[i-1]+dp[i-1][j-w[i-1]]);
            }
        }
    cout<<dp[N][W]<<"\n";
    return 0;
}

Measured memory_bytes: 79104
# coding: utf-8
K, S = map(int, input().split())
cnt=0
for x in range(K+1):
        yz = S - x
        if yz < 0:
                break
        elif yz > 2*K:
                continue
        else:
                cnt += yz + 1 - 2 * max(0, yz - K)
print(cnt)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,L,R;
string S,T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;

int main(){
    cin>>A>>B;
    ll ans = 1;
    rep(i,A) ans *= 100;
    if(B != 100) ans *= B;
    else ans *= 101;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
typedef long long lint;
#define int lint
const int INF =1e7;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repi(i, k, n) for (int i = (k); i < (int)(n); ++i)
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define all(x) (x).begin(),(x).end()
#define pb push_back
signed main(){
    int n, l;
    cin >> n >> l;
    int sum = 0;
    int mini = INT_MAX;
    rep(i, n)
    {
        int t = l + i;
        sum += t;
        if(abs(t)<abs(mini)){
            mini = t;
        }
    }
    cout << sum - mini << endl;
    return 0;
}

Measured memory_bytes: 256
from numba import njit
@njit(cache=True)
def func(n, k, a):
    for i in range(k):
        b = []
        for i in range(n+1):
            b.append(0)
        for i in range(n):
            l = max(0, i - a[i])
            r = min(n, i + a[i] + 1)
            b[l] += 1
            b[r] -= 1
        for i in range(len(b)-1):
            b[i+1] += b[i]
        b = b[:n]
        if a == b:
            break
        else:
            a = b
    return b
if __name__ == '__main__':
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = func(n, k, a)
    for i in range(n):
        print(b[i])


Measured memory_bytes: 132112
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#include <functional>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<ll, ll, ll, ll> tlglglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
typedef unsigned int uint;
typedef unsigned long long ull;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<VV<T>>;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;
void yesno(bool ok, string yes = "Yes", string no = "No") {
    if (ok) {
        cout << yes << endl;
    } else {
        cout << no << endl;
    }
}

ll dp[3010][3010][4];
ll bo[3010][3010];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll R, C, K;
    cin >> R >> C >> K;
    REP(i, 0, K) {
        ll r, c, v;
        cin >> r >> c >> v;
        bo[r - 1][c - 1] = v;
    }
    if (bo[0][0] > 0) {
        dp[0][0][1] = bo[0][0];
    }
    REP(i, 0, R) {
        REP(j, 0, C) {
            REP(k, 0, 4) {
                if (i - 1 >= 0) {
                    dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][k]);
                    if (bo[i][j] > 0) {
                        dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][k] + bo[i][j]);
                    }
                }
                if (j - 1 >= 0) {
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k]);
                    if (bo[i][j] > 0 && k > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + bo[i][j]);
                    }
                }
            }
        }
    }
    ll ans = 0;
    REP(i, 0, 4) {
        ans = max(ans, dp[R - 1][C - 1][i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 356116
n = gets.to_i
x, y = n.times.map{gets.split.map(&:to_f)}.transpose

d = Array.new(n).map{Array.new(n, 0.0)}
for i in 0..(n-2)
  for j in (i+1)..(n-1)
    d[i][j] = d[j][i] = ((x[i]-x[j])**2 + (y[i]-y[j])**2)**(0.5)
  end
end

m = 2.0
r = n
for i in 1..(n-1)
  m *= i
  r *= i
end

ave = 0.0
for i in 0..(n-2)
  for j in (i+1)..(n-1)
    ave += d[i][j] * m
  end
end
puts ave / r

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

using namespace std;

const long long mod = 1e9 + 7ll ;

long long modpower(long long a , long long b)
{
    if(b == 0)
        return 1ll ;
    long long x = modpower(a , b / 2ll) ;
    x = (x * x) % mod ;
    if(b & 1)
        return (x * a) % mod ;
    return (x % mod) ;
}

struct combination
{
    vector<long long>fact , inv ;
    combination(int sz) : fact(sz + 1) , inv(sz + 1)
    {
        fact[0] = 1ll ;
        inv[0] = 1ll ;
        for(long long i = 1 ; i <= sz ; ++i)
        {
            fact[i] = (fact[i-1] * i) % mod ;
            inv[i] = modpower(fact[i] , mod - 2ll) ;
        }
    }
    long long choose(int n , int k) const
    {
        if(k < 0 || n < k)
            return 0 ;
        return ((((fact[n] * inv[k]) % mod) * inv[n - k]) % mod) ;
    }
};

combination comb(2e5+2) ;

int main()
{
    int n , m , a , b;
    cin>>n>>m>>a>>b ;
    int nowx = n-a ;
    long long sum = 0ll ;
    long long ans = 0ll ;
    for(int i = b+1 ; i <= m ; ++i)
    {
        long long x = (comb.choose(nowx-1ll + i-1ll , i-1ll))%mod ;
        long long y = (comb.choose(n-nowx-1+m-i , m-i)) % mod ;
        ans = (ans + ((x * y) % mod)) % mod ;
        ans = (ans % mod) ;
    }
    return cout<<ans<<"\n" , 0 ;
}


Measured memory_bytes: 3328
#include<stdio.h>

int main(void){

   int a,b;

   scanf("%d %d",&a,&b);

   if (a<b){
      printf("a < b\n");
   }
   else if (a>b){
      printf("a > b\n");
   }
   else{
      printf("a == b\n");
   }

  return 0;
}


Measured memory_bytes: 2112
import resource
import sys
sys.setrecursionlimit(20000)
f = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
n, m = map(int, input().split())
a = list(map(int, input().split()))

memo = [-1]*10100


def dp(i):
    # i本のマッチを使って作れる最大の整数
    if i < 0:
        return - 10 ** 100000
    if not (0 <= i and i < 10100):
        print(-1)
        exit()
    if memo[i] != -1:
        return memo[i]
    if i == 0:
        return 0
    ret = -10**100000
    for x in a:
        ret = max(ret, 10 * dp(i - f[x]) + x)
    memo[i] = ret
    return ret


print(dp(n))


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


vector<bool> prime(3001000);

void eratos ( int n){
	prime[2] = true; prime[0] = prime[1] = false;
	for(int i = 3; i <= n; i += 2) prime[i] = true, prime[i+1] = false;
	int limit = (int)sqrt((double)n) + 1;
	for(int i = 3; i <= limit; i += 2){
		if(!prime[i]) continue;
		for(int j = i * i, k = i * 2; j <= n; j += k) prime[j] = false;
	}
}
int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	eratos(3000000);
	VI prm;
	rep(i,300000) if(prime[i] && i%5==1) prm.push_back(i);
	int n;
	cin >> n;
	
	//dbg(sz(prm));
	const int MX = 800;
	string sq=string(MX, '0');
	rep(i,n) sq[i] ='1';
	sort(all(sq));
	do {
		int sm =0;
		rep(i, MX) if(sq[i]=='1') sm += prm[i];
		if(!prime[sm] ){
			//dbg("sm=",sm);
			rep(i, MX) if(sq[i]=='1'){ cout << prm[i] <<" ";}
			return 0;
		}
	} while ( next_permutation(all(sq)) );

	
	return 0;
}


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

int main()
{
	int n,k;
	cin >> n >> k;
	vector<int> h(n);
	for(int i=0;i<n;i++)
	cin >> h[i];
	
	vector<int> dp(n+1,INT_MAX-1);

	dp[0]=0;
	dp[1]=0;
	dp[2]=abs(h[1]-h[0]);
	// vector<int> ans;
	for(int i=3;i<=n;i++)
	{
		for(int j=i-1;j>=1&&j>=i-k;j--)
			dp[i]= min(dp[i],dp[j]+abs(h[i-1]-h[j-1]));
	
	}

	cout<<dp[n];
	return 0;


}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int a,b,c;
    int num[2009];
    
    cin>>a>>b>>c;
    rep(i,a) cin>>num[i];
    
    ll ans=abs(c-num[a-1]);
    if(a>1) chmax(ans,(ll)abs(num[a-2]-num[a-1]));
    cout1(ans)
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#include <string.h>
#include <iostream>
typedef long long ll;
using namespace std;
#define maxn 200005
char a[8];
int main()
{
    ll n,k,mau=0,mad=0,mal=0,mar=0,d=0,l=0,r=0,u=0,m=0,i,j,ans=0;
    scanf("%s",a+1);
    if(strlen(a+1)==6)
    {
        if(a[3]==a[4]&&a[5]==a[6])
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    else
    {
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,mn[2010],mx[2010],siz[2010];
vector<int> v[2010];
char s[2010];
void dfs(int np,int fath)
{
	siz[np]=(s[np]=='1');
	mx[np]=mn[np]=0;
	pair<int,int> m=make_pair(0,0);
	for(int &x:v[np])
	{
		if(x==fath)continue;
		dfs(x,np);
		siz[np]+=siz[x];
		mx[np]+=mx[x];
		m=max(m,make_pair(mn[x],mx[x]));
	}
	mn[np]=max(0,m.first-(mx[np]-m.second));
	if(fath)mn[np]+=siz[np],mx[np]+=siz[np];
}
int main()
{
	scanf("%d%s",&n,s+1);
	for(int i=1,ti,tj;i<n;i++)
	{
		scanf("%d%d",&ti,&tj);
		v[ti].push_back(tj);
		v[tj].push_back(ti);
	}
	int ans=0x3f3f3f3f;
	for(int i=1;i<=n;i++)
	{
		dfs(i,0);
		if(mx[i]&1)continue;
		if(mn[i]==0)
		{
			ans=min(ans,mx[i]/2);
//			printf("%d\n",mx[i]/2);
//			return 0;
		}
	}
	if(ans!=0x3f3f3f3f)printf("%d\n",ans);
	else puts("-1");
	return 0;
}

Measured memory_bytes: 512
def dice_and_coin(n, k):

    ans = 0

    for i in range(1, n+1):
        count = i
        counter = 0
        while count < k:
            counter += 1
            count *= 2
        ans += 1/n * (1/2**counter)

    return ans

def main():
    n, k = map(int, input().split())
    print(dice_and_coin(n, k))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
package main

import (
	"bufio"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	iv, _ := strconv.Atoi(scanString())
	return iv
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 100001), 100001*100)
}

func main() {
	n := scanInt()
	type restaurant struct {
		n    string
		p, i int
	}
	rs := make([]restaurant, n)
	for i := 0; i < n; i++ {
		rs[i].i = i + 1
		rs[i].n, rs[i].p = scanString(), scanInt()
	}

	sort.Slice(rs, func(i, j int) bool {
		if rs[i].n == rs[j].n {
			return rs[i].p > rs[j].p
		}
		return rs[i].n < rs[j].n
	})

	var wr = bufio.NewWriter(os.Stdout)
	for _, v := range rs {
		wr.WriteString(strconv.Itoa(v.i) + "\n")
	}
	wr.Flush()
}


Measured memory_bytes: 1504
#include<stdio.h>
#include<float.h>

int main(void){

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 %f\n",d, r, f);

return 0;

}

Measured memory_bytes: 636