akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

typedef long long LL;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define dumpMap(m) { for (auto it: m) cout << it.first << "=>" << it.second << ' '; }

const int MOD = 1000000007;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);
    
    int H, W, N;
    cin >> H >> W >> N;

    int m = max(H, W);
    int ans = (N + m - 1) / m;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
typedef long long ll;
using namespace std;

int main(){
  int N;
  cin >> N;
  int xy[N+1][3];
  xy[0][0] = xy[0][1] = xy[0][2] = 0; 
  for(int i = 1; i <= N; ++i){
    cin >> xy[i][0] >> xy[i][1] >> xy[i][2];
  }
  bool flag = true;
  for(int i = 1; i <= N; ++i){
    int t = xy[i][0] - xy[i-1][0];
    int dis = abs(xy[i][1] - xy[i-1][1]) + abs(xy[i][2] - xy[i-1][2]);
    if(dis > t) flag = false;
    else if((t-dis)%2) flag = false;
    //    cout << "t dis :" << t << " " << dis << endl;
   }
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  ll N; cin >> N;
  ll A[N]; rep(i,N) cin >> A[i];
  ll p18 = 1; rep(i,18) p18 *= 10;
  ll result = 1;

  rep(i,N) {
    // cout << p18/A[i] << " " << result << endl;
    if (p18/A[i]<result) { result = -1; break; }
    result *= A[i];
  }
  rep(i,N) if (A[i]==0) result = 0;

  cout << result << endl;
  return 0;
}

Measured memory_bytes: 4424
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int z = sc.nextInt();

        int a = y + z;
        int b = x / a;
        int c = b*a + z;
        if (c <= x) {
            System.out.println(b);
        } else {
            System.out.println(b-1);
        }
    }

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define LL long long
#define INF 0x7FFFFFFF//or 0x3f3f3f3f ?
using namespace std;

template<class T> inline
void read(T& x) {
    int f = 1; x = 0;
    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();}
    x *= f;
}

/*============ Header Template ============*/

const int N = 100 + 5;

int n;
int a[N];
int f[10], g[10];

int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 0; i < 10; i++) f[i] = -INF;
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        int x = a[i] % 10;
        for (int j = 0; j < 10; j++) g[j] = f[j];
        for (int j = 0; j < 10; j++) {
            f[(j + x) % 10] = max(f[(j + x) % 10], g[j] + a[i]);
        }
    }
    int ans = 0;
    for (int i = 1; i < 10; i++) ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
    int c1, c5, c10, c50, c100, c500;
    cin >> c1 >> c5 >> c10 >> c50 >> c100 >> c500;
    cout << (1000<=c1+c5*5+c10*10+c50*50+c100*100+c500*500?"1":"0") << endl;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
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; }

double n;
vector<double> p(3030, 0.0);
double dp[3030][3030];

int main() {
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> p.at(i);

    dp[0][0] = 1.0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j <= i; ++j) {
            if(j == 0) dp[i+1][j] = dp[i][j] * (1.0-p.at(i));
            dp[i+1][j+1] = dp[i][j]*p.at(i) + dp[i][j+1]*(1.0-p.at(i));
        }
    }

    double ans = 0.0;
    for(int i = n; i > n/2; --i) ans += dp[(int)n][i];

    printf("%.10f\n", ans);
}

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

const int maxn = 502;

int n,m;
int d[maxn][maxn];

struct operation
{
	int x1,y1,x2,y2;

	operation(int a, int b, int c, int d) {
		x1 = a; y1 = b; x2 = c; y2 = d;
	}
};

vector<operation> ans;

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			cin >> d[i][j];
	
	int j = 0, dir = 1;
	for (int i = 0; i < n; ++i) {
		for (int steps = 0; steps < m-1; ++steps) {
			if (d[i][j]%2) {
				ans.push_back(operation(i,j,i,j+dir));

				d[i][j]--;
				d[i][j+dir]++;
			}

			j += dir;
		}

		if (d[i][j]%2 && i < n-1) {
			ans.push_back(operation(i,j,i+1,j));

			d[i][j]--;
			d[i+1][j]++;
		}

		dir = -dir;
	}

	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); ++i)
		printf("%d %d %d %d\n", ans[i].x1+1, ans[i].y1+1, ans[i].x2+1, ans[i].y2+1);

	return 0;
}

Measured memory_bytes: 5104
#!/usr/bin/env python3


def solve(s):
    n = len(s)

    if s[0] != '1':
        print(-1)
        return
    if s[-1] != '0':
        print(-1)
        return
    for i in range((n - 1) // 2):
        if s[i] != s[n - 2 - i]:
            print(-1)
            return
    edges = [(1, 2)]
    s = s[: n // 2]
    p = 1
    if 3 < n and s[1] == '1':
        p = 2
    for i in range(1, n // 2):
        edges.append((p, i + 2))
        if s[i] == '1':
            p = i + 2
    for i in range(n // 2 + 1, n):
        edges.append((p, i + 1))

    for uv in edges:
        u, v = uv
        print('{} {}'.format(u, v))


def main():
    s = input()

    solve(s)


if __name__ == '__main__':
    main()



Measured memory_bytes: 16392
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define F first
#define S second
#define OUT(x) cout << (x) << "\n"
using namespace std;
using point = pair< int,int >;
using ll = long long;

int main() {
    const int table[11] = {0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45};

    int n, f, m;
    cin >> n >> f;

    int cnt = 0;
    string str;
    map< string, int > mp;
    vector< string > vec;

    REP(i, n) {
        scanf("%d", &m);

        vec.clear();
        REP(j, m) {
            cin >> str;
            vec.push_back(str);
        }

        REP(j, m - 1) {
            FOR(k, j + 1, m) {
                string tmp = min(vec[j], vec[k]) + " " + max(vec[j], vec[k]);
                if (mp.find(tmp) == mp.end()) mp[tmp] = 1;
                else mp[tmp]++;
            }
        }

    }

    for (auto p : mp) {
        if (p.second >= f) {
            cnt++;
        }
    }
    OUT(cnt);

    for (auto p : mp) {
        if (p.second >= f) {
            OUT(p.first);
        }
    }


    return 0;
}




Measured memory_bytes: 3980
import java.util.*;

public class Main{

	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        
        if(c > a+b && 4*a*b < (c-(a+b))*(c-(a+b))){
          System.out.println("Yes");
        }else{
          System.out.println("No");
        }
        
	}
}

Measured memory_bytes: 35596
import math

M = 256
R = [[[[None]*(M+2) for i in range(16)] for j in range(16)] for k in range(16)]
for s in range(16):
    for a in range(16):
        for c in range(16):
            R[s][a][c][0] = s
            for i in range(M+1):
                R[s][a][c][i+1] = (a*R[s][a][c][i]+c)%M

while True:
    n = int(input())
    if n == 0:
        break
    v = list(map(int,input().split()))
    hmin = 1e9
    smin = 0
    amin = 0
    cmin = 0
    for s in range(16):
        for a in range(16):
            for c in range(16):
                cnt = [0]*(M+1)
                for i in range(n):
                    cnt[(v[i]+R[s][a][c][i+1])%M] += 1
                h = 0
                for x in cnt:
                    if x > 0:
                        h -= math.log2(float(x)/n)*x
                if h < hmin:
                    smin,amin,cmin,hmin = s,a,c,h
    print(smin,amin,cmin)



Measured memory_bytes: 14256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    int R,C; ll K; cin >> R >> C >> K;
    vector<vector<ll>> item(R+1,vector<ll>(C+1));
    for(int i = 0; i < K;i++){
        int r,c; ll v;
        cin >> r >> c >> v;
        r--; c--;
        item[r][c] = v;
    }
    auto dp = make_v<ll>(R+1,C+1,4);
    fill_v(dp,0);
        
    if(item[0][0]){
        dp[0][0][1] = item[0][0];
    }
    
    auto chmax = [&](ll& l,ll r){
        l = max(l,r);
    };
    for(int i = 0; i < R;i++){
        for(int j = 0; j < C;j++){
            for(int k = 0; k <= 3; k++){
                {// 横移動
                    if(j+1<C){
                        
                        chmax(dp[i][j+1][k],dp[i][j][k]);
                        if(k <= 2){
                            chmax(dp[i][j+1][k+1],dp[i][j][k]+item[i][j+1]);
                        }
                    }
                }
                {//　縦移動
                    if(i+1<R){
                        chmax(dp[i+1][j][0],dp[i][j][k]);
                        chmax(dp[i+1][j][1],dp[i][j][k]+item[i+1][j]);

                    }
                }
            }
        }
    }
    
    for(int k = 0; k <= 3;k++){
        res = max(res,dp[R-1][C-1][k]);
    }
    
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}


Measured memory_bytes: 707136
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,d[111]={},cnt=0;
  cin>>n;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    if(d[a]==0){
      cnt++;
      d[a]=1;
    }
  }
  cout<<cnt<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

	int k;
	cin >> k;
	vector<vector<int>> chess(8, vector<int>(8));
	auto ok = [&](const vector<vector<int>> &newChess) {
		REP(i, 8) {
			int cnt = 0;
			REP(j, 8) {
				cnt += newChess[i][j];
				if (cnt > 1) {
					return false;
				}
			}
		}
		REP(j, 8) {
			int cnt = 0;
			REP(i, 8) {
				cnt += newChess[i][j];
				if (cnt > 1) {
					return false;
				}
			}
		}
		REP(i, 8) {
			int cnt = 0;
			REP(j, 8) {
				if (i + j == 8) break;
				cnt += newChess[i + j][j];
				if (cnt > 1) {
					return false;
				}
			}
		}
		REP(i, 8) {
			int cnt = 0;
			REP(j, 8) {
				if (i - j < 0) break;
				cnt += newChess[i - j][j];
				if (cnt > 1) {
					return false;
				}
			}
		}
		REP(j, 8) {
			int cnt = 0;
			REP(i, 8) {
				if (j + i == 8) break;
				cnt += newChess[i][j + i];
				if (cnt > 1) {
					return false;
				}
			}
		}
		REP(j, 8) {
			int cnt = 0;
			REP(i, 8) {
				if (j + i == 8) break;
				cnt += newChess[7 - i][j + i];
				if (cnt > 1) {
					return false;
				}
			}
		}
		return true;
	};
	REP(i, k) {
		int r, c;
		cin >> r >> c;
		chess[r][c] = 1;
	}
	vector<int> v(8);
	REP(i, 8) { v[i] = i; }

	do {
		vector<vector<int>> newChess = chess;
		REP(i, 8) {
			newChess[i][v[i]] = 1;
		}
		if (ok(newChess)) {
			REP(i, 8) {
				REP(j, 8) {
					if (newChess[i][j]) {
						cout << 'Q';
					} else {
						cout << '.';
					}
				}
				cout << endl;
			}
		}
	} while (next_permutation(v.begin(), v.end()));

	return 0;
}



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

int main() {
	string S;
  int ans = 0;
	cin >> S;
	rep(i,S.size()){
    if(i % 2 != 0){//偶数
      if(S.at(i) == 'R'){
        ans++;
      }
    }else{
      if(S.at(i) == 'L'){
        ans++;
      }
    }
  }
  if(ans == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
count = input()
num = list(map(int,input().split()))
mmax= max(num)
mmax = int(mmax)
mmin = min(num)
mmin = int(mmin)
msum = sum(num)
msum = int(msum)
print('{0} {1} {2}'.format(mmin,mmax,msum))

Measured memory_bytes: 6556
import sys
input = sys.stdin.readline

def parent(i):
    return i//2

def left(i):
    return 2*i

def right(i):
    return 2*i+1

H = int(input())

# 1オリジンにするために、0番目にNoneを入れておく
A = [None] + list(map(int, input().split()))

# 1オリジンでfor文回す
for i in range(1, H+1):
    print('node ' + str(i) + ': ', end='')
    print('key = ' + str(A[i]) + ', ', end='')
    if 1 <= parent(i):
        print('parent key = ' + str(A[parent(i)]) + ', ', end='')
    if left(i) <= H:
        print('left key = ' + str(A[left(i)]) + ', ', end='')
    if right(i) <= H:
        print('right key = ' + str(A[right(i)]) + ', ', end='')
    print('')  # 改行のため


Measured memory_bytes: 5724
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define LFOR(i, a, b) for (long long int i = (a); i <= (b); i++)
#define LRFOR(i, a, b) for (long long int i = (a); i >= (b); i--)
#define MOD 1000000007
#define INF 1000000000           // 2000000000
#define LINF 1000000000000000000 // 9000000000000000000
#define DINF 1000000000000000.0
#define PI 3.14159265358979

//.size()はunsigned int　0-1をするとオーバーフローする

using namespace std;
typedef long long int ll;
typedef pair<long long int, long long int> P;

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

int main(void) {
    int n;
    double total=0;

    cin>>n;
    vector<double> v(n);
    FOR(i,0,n-1){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    double now=v[0];
    FOR(i,1,n-1){
        now=(now+v[i])/2.0;
    }
    printf("%.10lf",now);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;


int main() {
    vector<int> v(3, 0);
    cin >> v[0] >> v[1] >> v[2];
    sort(v.begin(), v.end());
    cout << v[1] - v[0] + v[2] - v[1] << endl;
}


Measured memory_bytes: 3620
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define FILE ifstream in("input.txt");ofstream out("output.txt");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

ll a,k;
vec<ll> m, who;

ll rec(ll x){
   if(who[x]!=-1) return who[x];
   ll o = 0;
   for(ll i : m){
       if(i > x) break;
       o |= rec(x-i);
   }
   return who[x] = o^1;
}

int main() {
    fast;
    cin>>a>>k;
    m = vec<ll>(a);
    for(int q=0; q<a; q++) cin>>m[q];
    who = vec<ll>(k+1, -1);
    cout<<(rec(k) ? "Second" : "First");
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N=0;
    cin >> N;
    vector<int> d(N);
    for (int i = 0; i < N; ++i) {
        cin >> d.at(i);
    }
    vector<int> num(110,0);
    for (int i = 0; i < N; ++i) {
       num.at(d.at(i))++;
    }
    int count = 0;
    for (int i = 0; i < 110; ++i) {
        if(num.at(i) > 0){
            count++;
        }
    }
    cout << count;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<climits>
#include<algorithm>
using namespace std;
 
long long d(int l, int r, const vector<long long>& v)
{
	return v[r] - v[l];
}
 
long long dLR(int l, int mid, int r, const vector<long long>& v)
{
	return abs(d(mid, r, v) - d(l, mid, v));
}
 
int main(void)
{
	int N;
	cin >> N;
 
	vector<long long> A(N+1);
	for(int i=0; i<N; i++)
		cin >> A[i+1];
 
	for(int i=0; i<N; i++)
		A[i+1] += A[i];
 
	long long ret = LLONG_MAX;
	int left, right;
	left = 0;
	right = 1;
	vector<long long> v(4, 0);
	for(int i=1; i<N; i++){
		while(left < i && dLR(0, left+1, i, A) <= dLR(0, left, i, A))
			left++;
 
		while(right < N && dLR(i, right+1, N, A) <= dLR(i, right, N, A))
			right++;
 
		v[0] = d(0, left, A);
		v[1] = d(left, i, A);
		v[2] = d(i, right, A);
		v[3] = d(right, N, A);
 
		long long diff = *max_element(v.begin(), v.end()) - *min_element(v.begin(), v.end());
		ret = min(ret, diff);
	}
 
	cout << ret << endl;
 
	return 0;
}

Measured memory_bytes: 1792
a = gets.split(" ").map{|item|item.to_i}
if a[0] >= a[1] then
    print 0
    exit
end


b = gets.split(" ").map{|item|item.to_i}.sort

if a[0] == 1 then
    print b[-1] - b[0]
    exit
end

    


l = []
(a[1]-1).times{|k|
l.push(b[k+1]-b[k])
}
l = l.sort.reverse

print b[-1] - b[0] - l[0..(a[0]-2)].inject(:+)


Measured memory_bytes: 11256
#include <iostream>
using namespace std;
int main() {
	int a,b;
	while(true){
		cin>>b;
		if(b==0){
			break;
		}
		for(int i=0;i<9;i++){
			cin>>a;
			b=b-a;
		}
		cout<<b<<endl;
	}
	return 0;
}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  string s; cin >> s;
  int n = s.size();
  char cur = s[0];
  int ans = 0;
  for (int i = 1; i < n; ++i) {
    if (s[i] != cur) {
      ++ans;
      cur = s[i];
    }
  }
  printf("%d\n", ans);
  return 0;
}


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

int main() {
  string S,T,U;
  int A,B;
  cin >> S>>T>>A>>B>>U;
  if(S==U){
    A--;
  }
  else{
    B--;
  }
  cout <<A<<" "<<B<< endl;
}

Measured memory_bytes: 256
import sys

def make_divisors(num):
    divisors = []
    for i in range(1, int(num**0.5)+1):
        if num%i == 0:
            divisors.append(i)
            if num//i != i:
                divisors.append(num//i)
    divisors.sort()
    return divisors

n, m = map(int, input().split(' '))

divisors = make_divisors(m)

for i in range(1, len(divisors)+1):
    if divisors[i*-1] * n <= m:
        print(divisors[i*-1])
        sys.exit()

Measured memory_bytes: 3188
import sys

a, b, c, k = map(int, input().split())

cnt = 0
if a < k:
    cnt += a
    k -= a
else:
    cnt += k
    print(cnt)
    sys.exit()
if b < k:
    k -= b
else:
    print(cnt)
    sys.exit()
cnt -= k
print(cnt)

Measured memory_bytes: 9188
#include <iostream>

int main()
{
    std::ios_base::sync_with_stdio(false);
    int N, ans = 0;
    std::cin >> N;
    while (N > 0) {
        ans += N % 10;
        N /= 10;
    }
    std::cout << (ans != 1 ? ans : 10) << std::endl;
    return 0;
}


Measured memory_bytes: 256
import math


N=int(input())

S=[]
T=[]
for i in range(N):
    S.append(int(input()))

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True




for i in range(N):
    
    tmp=is_prime(S[i])
    if tmp==True:
        T.append(S[i])
print(len(T))


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

const long long INF = 1e10;

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

    vector<long long> sum(N+1, 0);

    for(int i = 0; i < N; i++){
        sum[i+1] += sum[i] + a[i];
    }
  
    long long ans = INF;
    for(int i = 1; i < N; i++){
        long long now = llabs(sum[i] - (sum[sum.size()-1] - sum[i]));
        if(ans > now) ans = now;
    }
    cout << ans << endl;

}

Measured memory_bytes: 3328
import collections
N, M = map(int, input().split())

H = list(map(int, input().split()))

C = []
for i in range(M):
    A, B = map(int, input().split())
    if H[A-1] > H[B-1]:
        C.append(B-1)
    elif H[A-1] < H[B-1]:
        C.append(A-1)
    else:
        C.append(A-1)
        C.append(B-1)
        
c = collections.Counter(C)

m = len(list(c.keys()))

print(N-m)

Measured memory_bytes: 22208
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	xs := make([]int, n)
	for i := range xs {
		fmt.Scan(&xs[i])
	}
	sort.Ints(xs)

	v1, v2 := xs[n/2], xs[n/2-1]
	fmt.Println(v1 - v2)
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
#define SpeeD ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ll long long
//pair<int, int> *p=new pair<int, int>[n];
//std::vector<pair<int,int>> vp;
//v.push_back(make_pair(x,y))
//pair<int, int> p[1001];
//string *s=new string [n];
//int freq[e];
//freq[a[i]-'a']++; freq[a[i]]++;
 using namespace std;  
ll t,n,c3,sum,m,mn,k,r,avg;
std::vector<int >v,v2;
std::map<int, int> mp;
bool isPrime(int x)
{
for (int i=2;i*i<=x;i++)
if (x%i==0)
return false;
return true;
}
 
int main(void)
 
{
ll a,b;
cin>>n>>a>>b;
   ll z = (n/(a+b))*a;
   if ((n%(a+b))>=a)
   z+=a;
   else z+=n%(a+b);
   cout<<z;
    



}

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

using namespace std;

using int64 = long long;

constexpr int DEBUG = 0;

template<typename T>
vector<vector<T>> Make2DVector(int d1, int d2, T default_value) {
  return vector<vector<T>>(d1, vector<T>(d2, default_value));
}

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

  string s1, s2;
  cin >> s1 >> s2;
  int l1 = s1.length();
  int l2 = s2.length();
  vector<vector<int>> dp = Make2DVector(l1 + 1, l2 + 1, -1);
  vector<vector<pair<int, int>>> prev_table =
      Make2DVector(l1 + 1, l2 + 1, make_pair(-1, -1));
  
  dp[0][0] = 0;
  for (int i = 0; i <= l1; i++) {
    for (int j = 0; j <= l2; j++) {
      if (DEBUG) cerr << "i: " << i << " j: " << j << " " << dp[i][j] << endl;
      if (i + 1 <= l1 && dp[i + 1][j] < dp[i][j]) {
        dp[i + 1][j] = dp[i][j];
        prev_table[i + 1][j] = make_pair(i, j);
      }
      if (j + 1 <= l2 && dp[i][j + 1] < dp[i][j]) {
        dp[i][j + 1] = dp[i][j];
        prev_table[i][j + 1] = make_pair(i, j);
      }
      if (i < l1 && j < l2 &&
              s1[i] == s2[j] && dp[i + 1][j + 1] < dp[i][j] + 1) {
        dp[i + 1][j + 1] = dp[i][j] + 1;
        prev_table[i + 1][j + 1] = make_pair(i, j);
      }
    }
  }
  if (DEBUG) cerr << "DP END" << endl;

  int cur_i = l1;
  int cur_j = l2;
  string ans;
  while (cur_i > 0 || cur_j > 0) {
    int pi, pj;
    tie(pi, pj) = prev_table[cur_i][cur_j];
    if (dp[pi][pj] < dp[cur_i][cur_j]) {
      ans.push_back(s1[pi]);
    }
    tie(cur_i, cur_j) = make_tuple(pi, pj);
  }
  reverse(ans.begin(), ans.end());
  if (DEBUG) cerr << dp[l1][l2] << endl;
  cout << ans << endl;
}


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

int a[100006], b[100006];
int sa[100006], sb[100006];
int XA, XB;
vector<int>idx[100006];

int par[100006], siz[100006];
void init(int n) {
	rep(i, n) {
		par[i] = i; siz[i] = 1;
	}
}
int find(int x) {
	if (par[x] == x)return x;
	return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x), y = find(y);
	if (x == y)return;
	if (siz[x] < siz[y])swap(x, y);
	par[y] = x;
	siz[x] += siz[y];
}

signed main() {
	int n; cin >> n;
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> b[i];

	rep(i, n) {
		sa[i] = a[i];
		sb[i] = b[i];
		sa[n] ^= a[i];
		sb[n] ^= b[i];
	}
	a[n] = sa[n], b[n] = sb[n];

	sort(sa, sa + n + 1);
	sort(sb, sb + n + 1);

	rep(i, n + 1) {
		if (sa[i] != sb[i]) {
			cout << -1 << endl;
			return 0;
		}
	}
	
	int m = 0;
	rep(i, n + 1) {
		if (a[i] != b[i]||i==n) {
			sa[m] = a[i];
			sb[m] = b[i];
			m++;
		}
	}

	map<int, int>M;
	rep(i, m)M[sa[i]]++;
	int c = 0;
	for (auto itr = M.begin(); itr != M.end(); itr++) {
		M[itr->first] = c; c++;
	}
	rep(i, m) {
		sa[i] = M[sa[i]];
		sb[i] = M[sb[i]];
		idx[sa[i]].push_back(i);
	}
	init(m);
	rep(i, 100001) {
		if (idx[i].size()) {
			for (int j = 0; j < idx[i].size() - 1; j++) {
				unite(idx[i][j], idx[i][j + 1]);
			}
		}
	}
	rep(i, m) {
		unite(idx[sa[i]][0], idx[sb[i]][0]);
	}

	set<int>S;
	int ans = 0;
	rep(i, m) {
		if (S.count(find(i)))continue;
		if (find(i) == find(m - 1))ans += siz[find(i)] - 1;
		else ans += siz[find(i)] + 1;
		S.insert(find(i));
	}
	cout << ans << endl;

}


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

int main()
{
	string a, b;
	cin >> a;
	int c, d;
	c = a.size();
	while (c > d) {
		if (a.substr(0, 1) == "0") {
			b = b + '0';
		}
		else if (a.substr(0, 1) == "1") {
			b = b + '1';
		}
		else if (b.size()!= 0&&a.substr(0, 1) == "B") {
			b.erase(b.size()-1);
		}
		d = d + 1;
		a.erase(a.begin());
	}
	cout << b << endl;
}

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

#define ll long long
#define fw(p) for(int w=0;w<(p);w++)
#define fx(p) for(int x=0;x<(p);x++)
#define fy(p) for(int y=0;y<(p);y++)
#define fz(p) for(int z=0;z<(p);z++)
#define fyg(p,g) for(int y=(g);y<(p);y++)
#define fzg(p,g) for(int z=(g);z<(p);z++)
#define ce(d) cout<<d<<endl;
#define vecp(p) int aa;cin>>aa;(p).push_back(aa);
#define vecpl(p) long long aa;cin>>aa;(p).push_back(aa);
#define vecps(p) string aa;cin>>aa;(p).push_back(aa);
#define vecp2(p) cin>>aa;(p).push_back(aa);
#define vecpl2(p) long long a	b;cin>>ab;(p).push_back(ab);
#define vecps2(p) string ab;cin>>ab;(p).push_back(ab);
#define sorts(c) sort((c).begin(),(c).end());
#define reverses(c) reverse((c).begin(),(c).end());
#define vec(b) vector<int> (b);
#define vecl(b) vector<long long> (b);
#define vecs(b) vector<string> (b);
#define pb(b,a) (b).push_back((a));
#define doublece(a,b) cout<<(a)<<' '<<(b)<<endl;
#define pairs(s) vector<pair<int,int>> (s);
#define pairsp(s) int aa,bb;cin>>aa>>bb;(s).push_back(make_pair(aa,bb));
#define MOD 1000000007
#define cey ce("Yes")
#define cen ce("No")
#define ceY ce("YES")
#define ceN ce("NO")

int main()
{
string S;
	cin >> S;
	ll ans = S.size() * (S.size() - 1) / 2;

	int sum[26] = { 0, };
	fx(S.size()) {
		int i = S[x] - 'a';
		ans -= sum[i];
		sum[i]++;
	}
	ce(ans+1)
    return 0;
}



Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
char field[15][15];
void dfs(int x, int y) {
	int dx[4] = { 0,-1,0,1 };
	int dy[4] = { -1,0,1,0 };
	field[x][y] = '0';
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (0 <= nx&&nx < 12 && 0 <= ny&&ny < 12 && field[nx][ny] == '1') dfs(nx, ny);
	}
	return;
}
int main() {
	while (true) {
		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 12; j++) {
				cin >> field[i][j];
			}
		}
		if (cin.eof())break;
		int isl = 0;
		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 12; j++) {
				if (field[i][j] == '1') {
					dfs(i, j);
					isl++;
				}
			}
		}
		printf("%d\n", isl);
	}
}

Measured memory_bytes: 1132
#include <stdio.h>
#include <string.h>
#define SIZE 1000000
#define LENGTH 14
void in(char *);
int find(char *);
int h1(int);
int h2(int);
int ctoi(char);
char Hash[SIZE][LENGTH];
int main(){
  int i,num;
  char array[LENGTH],command[9];

  scanf("%d",&num);

  for(i=0;i<num;i++){
    scanf("%s",command);
    scanf("%s",array);
    if(command[0]=='i') in(array);
    else{
      if(find(array)==1) printf("yes\n");
      else printf("no\n");
    }
  }
  return 0;
}

void in(char *array){
  int i,sum=0,num=1,h;
  for(i=0;i<strlen(array);i++){
    sum+=num*(ctoi(array[i]));
    num*=5;
  }
  i=0;
  while(1){
    h=(h1(sum)+i*h2(sum))%SIZE;
      if(strcmp(Hash[h],array)==0) return;
      else if(strlen(Hash[h])==0){
	strcpy(Hash[h],array);
	return;
      }
    i++;
  }
  return;
}

int find(char *array){
  int i,sum=0,num=1,h;
  for(i=0;i<strlen(array);i++){
    sum+=num*(ctoi(array[i])); 
    num*=5;
  }
  i=0;
  while(1){
    h=(h1(sum)+i*h2(sum))%SIZE;
      if(strcmp(Hash[h],array)==0) return 1; /*found*/
      else if(strlen(Hash[h])==0) return 0; /* not found*/
    i++;
  }
  return 0;
}

int h1(int sum){
  return sum%SIZE;
}
int h2(int sum){
return 1+(sum%(SIZE-1));
}

/*convert character into value*/
int ctoi(char c){
  if(c=='A') return 1;
  else if(c=='C')return 2;
  else if(c=='G') return 3;
  else if(c=='T') return 4;
  else return 0;
}



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

#define int ll

#define pb push_back
#define all(v) (v).begin(), (v).end() 
#define sz(v) (int)((v).size())
#define fs first
#define sd second

typedef long long ll;

typedef pair < int, int > pi;
typedef pair < pi, int > ppi;

typedef vector < int > vi;
typedef vector < vector < int > > vvi;
typedef vector < pi > vpi;
typedef vector < vpi > vvpi;
typedef vector < ppi > vppi;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}

void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

double get_time() {
	return 1.0 * clock() / CLOCKS_PER_SEC;
}

const int MAX = (1 << 17), INF = 1E17;
int dp[MAX], cost[MAX];

int f(int mask) {
	if(mask == 0)
		return 0;
	if(dp[mask] > -1)
		return dp[mask];
	int ret = -INF;
	for(int submask = mask; submask > 0; submask = (submask - 1) & mask) {
		ret = max(ret, cost[submask] + f(mask ^ submask));
	}
	ret = max(ret, cost[mask]);
	return dp[mask] = ret;
}

int32_t main() {
	int n, allmask;
	cin >> n;
	allmask = (1 << n) - 1;
	vvi a(n, vi(n));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			cin >> a[i][j];
	for(int i = 0; i <= allmask; i++) {
		vi v;
		for(int j = 0; j < n; j++) {
			if(i & (1 << j)) {
				v.pb(j);
			}
		}
		for(int j = 0; j < sz(v); j++)
			for(int k = j + 1; k < sz(v); k++) {
				cost[i] += a[v[j]][v[k]];
			}
	}
	for(int mask = 1; mask <= allmask; mask++) {
		for(int ss = mask; ss > 0; ss = (ss - 1) & mask) {
			dp[mask] = max(dp[mask], cost[ss] + dp[mask ^ ss]);
		}
	}
	cout << dp[allmask];
}


Measured memory_bytes: 1280
n = int(input())
a, b = [int(item) for item in input().split()]
p = [int(item) for item in input().split()]

p1 = 0; p2 = 0; p3 = 0
for item in p:
    if item <= a:
        p1 += 1
    elif item <= b:
        p2 += 1
    else:
        p3 += 1
print(min(p1, p2, p3))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep2(i, s, n) for(int i=s; i<(n); ++i)

using namespace std;

typedef long long ll;
using pii = pair<int, int>;

static const int INTINF = (2147483647);
static const ll LLINF = (9223372036854775807);
static const int MAX = 100001;
static const ll MOD = 1000000007;


//--global--//

string make(int n){
    string str = to_string(n);
    while(str.size()<3){
        str = '0' + str;
    }
    return str;
}

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

int main(int argc, const char * argv[]) {
    //提出時、消す----//
    //--------------//
    
    int n;
    int *a;
    a = new int[MAX];
    cin >> n;
    rep(i, n){
        cin >> a[i];
    }
    int *people;
    people = new int[MAX];
    people[0] = 3;
    ll res = 1;
    rep(i, n){
        int cnt = people[a[i]];
        res *= cnt;
        people[a[i]]--;
        people[a[i]+1]++;
        res %= MOD;
    }

    cout << res << endl;
    
    return 0;
}


Measured memory_bytes: 1024
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())



def sol():
    n = int_raw()
    bs = ints_raw()
    ans =[]
    buf = list(bs)
    l = len(buf)
    while l!=0:
        #print l
        old_l = l
        for i in xrange(l,0,-1):
            b = buf[i-1]
            if b == i:
                ans.append(buf.pop(i-1))
                l = len(buf)
                break
        if old_l == l:            
            print -1
            return -1
    for a in reversed(ans):
        print a

sol()







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

using namespace std;

typedef long long int lli;
typedef vector <lli> vi;
typedef vector <vi> vvi;
typedef pair <lli, lli> pi;

int main() {
  int num1, num2;
  cin >> num1 >> num2;

  if ((num1 >= 1 and num1 <= 9) and (num2 >=1 and num2 <= 9)) {
    cout << (num1 * num2) << endl;
  } else {
    cout << "-1" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll n,m,sum=0;
	scanf("%lld%lld",&n,&m);
	ll a[m];
	for(int i=0;i<m;i++){
		scanf("%lld",&a[i]);
	}
	sort(a,a+m);
	vector<ll> v;
	for(ll i=1;i<m;i++){
		v.push_back(abs(a[i]-a[i-1]));
		sum+=abs(a[i]-a[i-1]);
	}
	sort(v.rbegin(),v.rend());
	if(n>=m)printf("0\n");
	else{
		for(ll i=0;i<n-1;i++){
		sum-=v[i];
		}
		printf("%lld",sum);
	}
}	


Measured memory_bytes: 5044
import sys
input = sys.stdin.readline


def solve():
    if "RRR" in weather:
        return 3
    elif "RR" in weather:
        return 2
    elif "R" in weather:
        return 1
    else:
        return 0
if __name__ == "__main__":
    weather = input().rstrip()
    print(solve())

Measured memory_bytes: 8884
from bisect import*
r=lambda:sorted(map(int,input().split()))
N=r()[0]
A,B,C,w,i=r(),r(),r(),[0]*(N+1),N
while i:w[i-1]=w[i]+N-bisect(C,B[i-1]);i-=1
print(sum(w[bisect(B,A[i])]for i in range(N)))


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

const int INF=1e9;

int main()
{
   int H,W; cin>>H>>W;
   vector<string> s(H);
   for(int i=0;i<H;i++) cin>>s[i];

   int ans=0;
   for(int j=0;j<W-1;j++){
      vector<vector<int>> cost(H+1,vector<int>(H+1));
      assert(j+1<W);
      for(int x=0;x<=H;x++) for(int y=0;y<=H;y++){
         if(x==0 or y==0) cost[x][y]=0;
         else cost[x][y]=cost[x-1][y-1]+(s[x-1][j]==s[y-1][j+1]);
      }
      vector<vector<int>> dp(H+1,vector<int>(H+1,INF));
      dp[H][H]=0;
      for(int x=H;x>=0;x--) for(int y=H;y>=0;y--){
         if(x+1<=H) dp[x][y]=min(dp[x][y],dp[x+1][y]+cost[x+1][y]);
         if(y+1<=H) dp[x][y]=min(dp[x][y],dp[x][y+1]+cost[x][y+1]);
      }
      ans+=dp[0][0];
   }
   cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 1200
#include <iostream>
#include <queue>
#include <functional>
#include <algorithm>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)

long long N, M[1 << 19], sum; vector<long long> S[300009];
priority_queue<long long, vector<long long>, less<long long>> Q;

int main() {
	scanf("%lld", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%lld", &M[i]);
		for (int j = 0; j < M[i]; j++) { long long v; scanf("%lld", &v); S[i].push_back(v); }
	}
	for (int i = N; i >= 1; i--) {
		for (long long j : S[i]) Q.push(j);
		if (!Q.empty()) {
			sum += Q.top();
			Q.pop();
		}
	}
	printf("%lld\n", sum);
	return 0;
}


Measured memory_bytes: 21980
# F LCS

s = input()
t = input()

dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]

ans = []

for i,_s in enumerate(s):
    for j,_t in enumerate(t):
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
        if _s == _t:
            dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j+1])

i, j = len(s), len(t)

while i>0 and j>0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans.append(s[i-1])
        i -= 1
        j -= 1

print(*(list(reversed(ans))),sep="")

Measured memory_bytes: 115036
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef vector<pair<ll,ll> > vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const int INF=1e9+7;
int main(){
  ll n,c;
  cin>>n>>c;
  vvll iwakan(c,vll(c)),color(n,vll(n));
  vll c0(c,0),c1(c,0),c2(c,0);
  rep(i,0,c){rep(j,0,c)cin>>iwakan[i][j];} 
  rep(i,0,n){rep(j,0,n){cin>>color[i][j];color[i][j]--;} }
  rep(i,0,n){
    rep(j,0,n){
      if((i+j)%3==0){c0[color[i][j]]++;}
      if((i+j)%3==1){c1[color[i][j]]++;}
      if((i+j)%3==2){c2[color[i][j]]++;}
    }
  }
  ll sum=INF;
  rep(i,0,c){//mod3=0
    rep(j,0,c){//mod3=1
      if(j!=i){
        rep(k,0,c){//mod3=2
          if(k!=i&&k!=j){
            ll tmp=0;
            rep(h,0,c){
              tmp+=iwakan[h][i]*c0[h];
              tmp+=iwakan[h][j]*c1[h];
              tmp+=iwakan[h][k]*c2[h];
            }
            sum=min(sum,tmp);
          }
        }
      }
    }
  }
  cout<<sum<<endl;
}


Measured memory_bytes: 2176
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
#include <utility>
typedef long long ll;
using namespace std;

int main(void){
  int n, i;
  string c;
  cin >> n >> c;

  vector<int> left, right;
  left.resize(n+1);
  right.resize(n+1);

  left[0] = 0;
  for(i=1;i<=n;i++){
    left[i] = left[i-1] + int(c[i-1]=='W');
  }

  right[n] = 0;
  for(i=n-1;i>=0;i--){
    right[i] = right[i+1] + int(c[i]=='R');
  }

  int ans = n;
  for(i=0;i<=n;i++){
    if(ans>max(left[i],right[i])){
      ans = max(left[i],right[i]);
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 5216
#include <bits/stdc++.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <math.h>
#include <time.h>
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)n; i++)
#define repf(i, a, b) for (ll i = (ll)a; i < (ll)b; i++)
#define repr(i, a, b) for (ll i = (ll)a; i > (ll)b; i--)
#define all(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int infi = 1147483600;
const ll infl = 1e17;
const char ENDL = '\n';

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pii> student(n), check(m);
    rep(i,n){
        int a,b;
        cin >> a >> b;
        student[i] = mp(a, b);
    }
    rep(i,m){
        int c, d;
        cin >> c >> d;
        check[i] = mp(c, d);
    }
    rep(i,n){
        int res = infi;
        int ans = 0;
        rep(j,m){
            if (res>abs(student[i].F - check[j].F) + abs(student[i].S - check[j].S)){
                res = abs(student[i].F - check[j].F) + abs(student[i].S - check[j].S);
                ans = j + 1;
            }
        }
        cout << ans << ENDL;
    }
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;cin>>s;vector<int> v(2,0);
  rep(i,s.size()) v[s[i]-'0']++;
  if(v[0]==0||v[1]==0) print(0);
  else print(2*min(v[0],v[1]));
  return 0;
}

Measured memory_bytes: 512
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x, y = map(int, read().split())

MOD = 10**9 + 7


def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5 + 1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n - 1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n - 1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD - 2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


U = 10**6
fact, fact_inv = make_fact(U, MOD)

if (x + y) % 3 != 0:
    print(0)
    exit()

a = (2 * x - y) // 3
b = (2 * y - x) // 3
if a < 0 or b < 0:
    print(0)
    exit()

answer = fact[a + b] * fact_inv[a] % MOD * fact_inv[b] % MOD
print(answer)


Measured memory_bytes: 60696
fn get_input() -> String {
    let mut word = String::new();
    std::io::stdin().read_line(&mut word).ok();
    return word.trim().to_owned();
}

fn main() {
    let (n, m) = {
        let line = get_input();
        let mut split_line = line.split_whitespace();
        let n:u32 = split_line.next().unwrap().parse().unwrap();
        let m:u32 = split_line.next().unwrap().parse().unwrap();
        (n,m)
    };

    let mut l:Vec<u32> = Vec::new();
    let mut r:Vec<u32> = Vec::new();

    for _i in 0..m {
        let (li, ri) = {
            let line = get_input();
            let mut split_line = line.split_whitespace();
            let l:u32 = split_line.next().unwrap().parse().unwrap();
            let r:u32 = split_line.next().unwrap().parse().unwrap();
            (l-1,r-1)
        };
        l.push(li);
        r.push(ri);
    }

    let mut lo = 0;
    let mut ro = n - 1;

    for i in 0..m {
        lo = std::cmp::max(lo, l[i as usize]);
        ro = std::cmp::min(ro, r[i as usize]);
    }

    let ans = if lo <= ro { ro - lo + 1 } else { 0 };

    println!("{}", ans);
}

Measured memory_bytes: 6396
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    long long a[100000];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a,a+n);
    long long sum = 0;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        sum += a[i];
        if(i==n-1){
            cnt++;
            continue;
        }
        if(sum*2 >= a[i+1]){
            cnt++;
        }else{
            cnt = 0;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 1024
//?±????????????????
#include <iostream>
#include <vector>
#include <set>
#define MAX 100000

using namespace std;

vector<int> G[MAX];
int N;
bool visited[MAX];
int prenum[MAX],parent[MAX],lowest[MAX],timer;

void dfs(int current,int pre){
    prenum[current]=lowest[current]=timer;
    timer++;
    visited[current]= true;

    int next;

    for (int i = 0; i < G[current].size(); ++i) {
        next=G[current][i];
        if (!visited[next]){
            parent[next]=current;
            dfs(next,current);
            lowest[current]=min(lowest[current],lowest[next]);
        } else if(next!=pre){
            lowest[current]=min(lowest[current],prenum[next]);
        }
    }
}

void art_points(){
    for (int i = 0; i < N; ++i) {
        visited[i]= false;
    }
    timer=1;
    dfs(0,-1);

    set<int> ap;
    int np=0;
    for (int i = 1; i < N; ++i) {
        int p=parent[i];
        if (p==0)
            np++;
        else if (prenum[p]<=lowest[i])
            ap.insert(p);
    }
    if (np>1)
        ap.insert(0);
    for (set<int>::iterator it= ap.begin();it!=ap.end(); it++) {
        cout<<(*it)<<endl;
    }
}

int main() {
    int m;
    cin>>N>>m;
    for (int i = 0; i < m; ++i) {
        int s,t;
        cin>>s>>t;
        G[s].push_back(t);
        G[t].push_back(s);
    }
    art_points();
    return 0;
}

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

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

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

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

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VI p(n);
  int ans = 0;
  rep(i,n) cin >> p[i];
  FOR(i,1,n-1){
    if( (p[i+1] > p[i] && p[i] > p[i-1]) || (p[i+1] < p[i] && p[i] < p[i-1]) ){
      ans++;
      //cerr << i << endl;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256