akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return (b);
    }
    else
    {
        return (gcd(b, a % b));
    }
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b;
}

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

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

int main()
{
    ll n;
    cin >> n;
    vector<ll> b(n);
    ll sum = 0;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> b[i];
    }
    b[n - 1] = infll;
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            sum += b[i];
        }
        else
        {
            sum += min(b[i - 1], b[i]);
        }
    }
    cout << sum << endl;
}


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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppii;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}

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

int main(){
    bool flag=false;
    ll ans=0,sum=0;

    string s,t,u;
    int a,b;
    cin >>s>>t>>a>>b>>u;

    if(u == s){
        --a;
    }else{
        --b;
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    cout<<a<<" "<<b<<endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


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

static const int INF = (1 << 28);

int main() {
    string A;
    cin >> A;

    int N = A.size();
    vector<int> indexes[26];

    for (int i = 0; i < N; i++) {
        indexes[A[i] - 'a'].push_back(i + 1);
    }
    for (int i = 0; i < 26; i++) {
        indexes[i].push_back(N + 1);
    }

    vector<int> table(N + 2, INF);  // A_[i,N]に含まれない最小の部分列の長さ(iは1-indexed)
    table[N + 1] = 0;

    for (int i = N; i >= 0; i--) {
        for (int j = 0; j < 26; j++) {
            int idx = *upper_bound(indexes[j].begin(), indexes[j].end(), i);
            table[i] = min(table[i], table[idx] + 1);
        }
    }

    int idx = 0;
    string ans = "";
    while (idx != N + 1) {
        int nidx = -1;
        char alphabet;

        for (int i = 0; i < 26; i++) {
            int foo = *upper_bound(indexes[i].begin(), indexes[i].end(), idx);
            if (nidx < 0 or table[nidx] > table[foo]) {
                nidx = foo;
                alphabet = char('a' + i);
            }
        }
        idx = nidx;
        ans.push_back(alphabet);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2180
#include <iostream>
#include <algorithm>
#include <stdio.h>
static const int MAX = 200000;

using namespace std;

void trace(int a[], int n){
  int i;
  for(i = 0; i < n; i++){
    if(i > 0) printf(" ");
    printf("%d", a[i]);
  }
  printf("\n");
}

void insertSort(int a[], int n){
  int j, i, v;
  for(i = 1; i < n; i++){
    v = a[i];
    j = i - 1;
    while( j >= 0 && a[j] > v){
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = v;
    trace(a, n);
  }
}

int main(int argc, const char * argv[]) {
  int n, i;
  int a[MAX];
  
  scanf("%d", &n);
  for(i = 0; i < n; i++) scanf("%d", &a[i]);
  
  trace(a, n);
  insertSort(a, n);
  return 0;
}


Measured memory_bytes: 3220
N, K = map(int, input().split())
s = set()
i = 1

while i*i<=N:
    s.add(i)
    s.add(N//i)
    i += 1

l = list(s)
l.sort()
nums = []

for i in range(len(l)-1):
    le = N//l[i+1]
    ri = N//l[i]
    nums.append(ri-le)

nums.append(1)
nums.reverse()
M = len(nums)
dp = [[0]*M for _ in range(K+1)]
dp[0][0] = 1
MOD = 10**9+7

for i in range(K):
    acc = [0]
    
    for j in range(M):
        acc.append((acc[-1]+dp[i][j])%MOD)
    
    for j in range(M):
        dp[i+1][j] = nums[j]*acc[M-j]

print(sum(dp[K])%MOD)

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

int main() {
  
  int A=0, P=0;
  
  cin >> A >> P;
  
  int mul = A * 3;
  int sum = mul + P;
  int apie = sum / 2;
  
  if(apie < 1) {
    
    cout << "0" << endl;
    
  } else {
    
    cout << apie << endl;
    
  }
  
  return 0;
  
}

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

int main(){
  int K,N;
  cin >> K >> N;
  
  if(N <= 500*K) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] votes = new int[N];
		for (int i = 0; i < N; i++) {
			votes[i] = sc.nextInt();
		}
		
		Arrays.sort(votes);
		
		int totalScores = 0;
		for (int i = 0; i < N; i++) {
			totalScores += votes[i];
		}
		
		for (int i = 0; i < M; i++) {
			if (votes[N - (i + 1)] * 4 * M < totalScores) {
				System.out.println("No");
				return;			
			}
		}
		
		System.out.println("Yes");

	}
}

Measured memory_bytes: 23764
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String ans = "ai1333";
		int x = sc.nextInt();
		for(int i=0;i<x/100;i++) {
			ans += "3";
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 26316
use proconio::input;
use proconio::marker::{Bytes, Chars};
use std::cmp::{max, min};

fn main() {
    input! {
        s: String,
    }
    let mut ans = s.len() - 1;
    for c in b'a'..=b'z' {
        ans = min(ans, s.split(c as char).map(|s| s.len()).max().unwrap());
    }
    println!("{}", ans);
}


Measured memory_bytes: 2164
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

constexpr int max_n = 100005;

int N,M;
vector<int> X;

int main(){
    cin >> N >> M;
    X.resize(N);
    vector<int> modcnt(M+10,0);
    vector<int> cnt(max_n,0);
    vector<int> rem(M+10,0);
    rep(i,N){
        cin >> X[i];
        modcnt[X[i]%M]++;
        cnt[X[i]]++;
    }

    int ans = 0;
    for(int i=0;i<=M/2;i++){
        int a = i;
        int b = (M - a)%M;
        //cerr << a << " " << b << endl;
        if(a==b){
            ans += modcnt[a]/2;
            rem[a] = modcnt[a]%2;
            continue;
        }

        int c = min(modcnt[a],modcnt[b]);
        rem[a] = modcnt[a]-c;
        rem[b] = modcnt[b]-c;
        ans += c;
    }
    //cerr << modcnt << endl;
    //cerr << rem << endl;
    //cerr << "ans :  " << ans << endl;

    for(int i=0;i<M;i++){
        int r = rem[i];
        int sum = 0;
        //cerr << "i : " << i << endl;
        //cerr << "r : " << r << endl;
        for(int v = i;v < max_n; v+=M){
            //cerr << "\tv : " << v << endl;
            int p = min(r/2,cnt[v]/2);
            sum += p;
            r -= p*2;
            if(r == 0 or r == 1) break;
        }
        ans += sum;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
int main(void){
  int a,b,x,k;
  k=1;
  char op;
  while(k != 0){
  scanf("%d %c %d",&a,&op,&b);
    if(op == '?'){
      break;
    }
    if(op == '+'){
      x = a + b;
    }else if(op == '-'){
      x = a - b;
    }else if(op == '*'){
      x = a * b;
    }else if(op == '/'){
      x = a / b;
    }
    printf("%d\n",x);
    k++;
  }
  return 0;
}

Measured memory_bytes: 600
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#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, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
//#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr int MOD = 1e9 + 7; constexpr int MAX = 200020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;


void solve() {
	int K; cin >> K;
	int A[32] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
	print(A[K - 1]);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



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


int main(){
	LL H;cin >> H;
	LL tmp = 0;
	while(H!=1){
		H /= 2;
		tmp++;
	}
	LL ans = 0;
	LL res;
	for(LL i = 1;i <= tmp; i++){
		res = 1;
		rep(j,i){
			res *= 2;
		}
		ans += res;
	
	}
	ans += 1;
	cout << ans << endl;
}













Measured memory_bytes: 3612
#include <bits/stdc++.h>   
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
     
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}
/*template <typename T>
T pow(T a, ll n, T e = 1) {
    T ret = e;
    while (n) {
        if (n & 1) ret *= a;
        a *= a;
        n >>= 1;
    }
    return ret;
}
 
template <int mod>
struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long x_) {
        if ((x = x_ % mod + mod) >= mod) x -= mod;
    }
    ModInt& operator+=(ModInt rhs) {
        if ((x += rhs.x) >= mod) x -= mod;
        return *this;
    }
    ModInt& operator-=(ModInt rhs) {
        if ((x -= rhs.x) < 0) x += mod;
        return *this;
    }
    ModInt& operator*=(ModInt rhs) {
        x = (unsigned long long)x * rhs.x % mod;
        return *this;
    }
    ModInt& operator/=(ModInt rhs) {
        x = (unsigned long long)x * rhs.inv().x % mod;
        return *this;
    }
 
    ModInt operator-() const { return -x < 0 ? mod - x : -x; }
    ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }
    ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }
    ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }
    ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }
    bool operator==(ModInt rhs) const { return x == rhs.x; }
    bool operator!=(ModInt rhs) const { return x != rhs.x; }
    ModInt inv() const { return pow(*this, mod - 2); }
 
    friend ostream& operator<<(ostream& s, ModInt<mod> a) {
        s << a.x;
        return s;
    }
    friend istream& operator>>(istream& s, ModInt<mod>& a) {
        s >> a.x;
        return s;
    }
};
 
using mint = ModInt<1000000007>;
*/
using Graph = vector<vector<int>>;
Graph G;
/*------------------------------------------------------------------*/
int main(){
  ll n, k; cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  ll GCD = a[0];
  rep(i, n){
    GCD = gcd(GCD, a[i]);
  }
  rep(i, n){
    if(a[i] < k) continue;
    if((a[i] - k) % GCD == 0){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 3976
#coding:shift_jis
test = list(input().split())
for i in range(len(test)):
    test[i] = int(test[i])

if test[0] >= 10 or test[1] >= 10:
    print(-1)

elif test[0] < 1 or test[1] < 1:
    print(-1)

else:
    print(test[1] * test[0])


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

using namespace std;

#define mod 1000000007
#define sz(c)  (int) c.size()
#define all(c) c.begin(), c.end()
#define tr(container,it) for(__typeof(container.begin()) it = container.begin();it != container.end(); it++)
#define present(s,x) s.find(x) != s.end()
#define cpresent(c,x) find(all(c),x) != c.end()
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,a,b) for(int i=a; i<b;i++)
#define ini(n) scanf("%d",&n)
#define opn printf("\n")

 
#define TRACE
 
#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
 
#else
 
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)    
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)

#endif 

typedef pair<int,int> pi;
typedef vector<pi> vp;
typedef vector<vp> vvp;
typedef vector<int> vi;
typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<ll> vl;
typedef vector< vi > vvi;
typedef priority_queue<int> pq;
typedef priority_queue<int, vi , greater<int> >minpq;
typedef priority_queue<pi,vp,greater<pi> > mpq;


int main(){
	//ios_base::sync_with_stdio(false);cin.tie(NULL);
	int n;
	cin>>n;
	int a[200003];
	rep(i,n) cin>>a[i];
	ll sum =0 ;
	ll ans = 0;
	int l=0,r=0;
	for(; l<n  ; l++){
		while(r<n and ((sum+a[r]) == (sum^a[r]))){
			sum += a[r];
			r++;
		}
		ans += (r-l);
		sum -= a[l];
	}
	cout<<ans;

	
}

	

	



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

int n, w;
ll dp[102][100100];
bool vis[102][100100];
int val[102], wt[102];


int main() {
	cin >> n >> w;
	for (int i = 1; i <= n; ++i) cin >> wt[i] >> val[i];

	for (int pos = 1; pos <= n; ++pos) {
		for (int weight = 0; weight <= w; ++weight) {
			if ( weight == 0 ) {
				dp[pos][weight] = 0;
				continue;
			}

			dp[pos][weight] = dp[pos - 1][weight];
			if ( weight - wt[pos] >= 0 ) 
				dp[pos][weight] = max(
					dp[pos][weight], 
					dp[pos - 1][weight - wt[pos]] + val[pos]
				);
		}
	}

	cout << dp[n][w] << endl;
	return 0;
}


Measured memory_bytes: 78976
import java.util.Scanner

object Main {
  def main(args: Array[String]) {
    if (args.length > 0 && args(0) == "TEST") {
      println(test())
    } else {
      val input = io.Source.stdin.getLines().mkString("\n")
      println(solve(input).trim())
    }
  }

  def solve(input: String): String = {
    val sc: Scanner = new Scanner(input)
    val a,b = sc.nextInt
    var sum = 0
    for (i <- a to b) {
      val is = i.toString
      if (is(0) == is(4) && is(1) == is(3)) sum += 1
    }
    sum.toString
  }

  val tests = List(
    """11009 11332""".stripMargin -> """4""",
    """31415 92653""".stripMargin -> """612"""
  )

  def test(): String = tests.map { case (i, o) => (i.trim(), o.trim()) }
    .zipWithIndex.map {
    case ((input, outputExpect), i) =>
      val output = solve(input).trim()
      val tnum = i + 1
      s"test$tnum:" + (
        if (output == outputExpect) "Passed"
        else s"Failed\nexpect:\n$outputExpect\noutput:\n$output")
  }
    .mkString("\n")
}

Measured memory_bytes: 32840
import java.util.*;
import java.math.*;
import java.io.*;
import java.lang.*;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc=new Scanner(System.in);
        PrintWriter pw=new PrintWriter(System.out);
        int n=sc.nextInt();
        int[][] a=new int[n][3];
        for(int i=0;i<n;i++) {
            a[i][0]=sc.nextInt();
            a[i][1]=sc.nextInt();
            a[i][2]=sc.nextInt();
        }
        long[][] dp=new long[n][3];
        for(int i=0;i<n;i++) {
            if(i>0) {
                dp[i][0]=a[i][0]+Math.max(dp[i-1][1],dp[i-1][2]);
                dp[i][1]=a[i][1]+Math.max(dp[i-1][0],dp[i-1][2]);
                dp[i][2]=a[i][2]+Math.max(dp[i-1][1],dp[i-1][0]);
            }
            else {
                dp[i][0]=a[i][0];
                dp[i][1]=a[i][1];
                dp[i][2]=a[i][2];
            }
        }
        pw.println(Math.max(Math.max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]));
        pw.close();
    }
}

Measured memory_bytes: 97956
# https://atcoder.jp/contests/abc126/tasks/abc126_e
class UnionFindWithType
  attr_reader :types
  def initialize(size)
    @rank = Array.new(size) { 0 }
    @parent = Array.new(size) { |id| id }
    @types = size
  end

  def unite(id_x, id_y)
    x_parent = get_parent(id_x)
    y_parent = get_parent(id_y)
    return if x_parent == y_parent
    @types -= 1
    if @rank[x_parent] > @rank[y_parent]
      @parent[y_parent] = x_parent
    else
      @parent[x_parent] = y_parent
      @rank[y_parent] += 1 if @rank[x_parent] == @rank[y_parent]
    end
  end

  def get_parent(id_x)
    @parent[id_x] == id_x ? id_x : (@parent[id_x] = get_parent(@parent[id_x]))
  end
end


N, M = gets.split.map(&:to_i)
uf = UnionFindWithType.new(N)
M.times do
  uf.unite(*gets.split.map { |s| s.to_i - 1 }.take(2))
end
p uf.types

Measured memory_bytes: 3324
#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  ll H,W,tmp,t,res=INF_LL,s1,s2,s3;
  cin >> H >> W;
  
  for(int i=1;i<H;i++){
    t = H - i;
    s3 = i*W;
    s1 = t*(W/2);
    s2 = t*(W-W/2);
    res = min(res,max(s1,max(s2,s3))-min(s1,min(s2,s3)));

    if(t >= 2){
      s1 = W*(t/2);
      s2 = W*(t-t/2);
      res = min(res,max(s1,max(s2,s3))-min(s1,min(s2,s3)));
    }
  }
  tmp = H;
  H = W;
  W = tmp;
  for(int i=1;i<H;i++){
    t = H - i;
    s3 = i*W;
    s1 = t*(W/2);
    s2 = t*(W-W/2);
    res = min(res,max(s1,max(s2,s3))-min(s1,min(s2,s3)));

    if(t >= 2){
      s1 = W*(t/2);
      s2 = W*(t-t/2);
      res = min(res,max(s1,max(s2,s3))-min(s1,min(s2,s3)));
    }
  }
  
  cout << res << endl;
  
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}



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

int main(){
    string s;
    cin >> s;
    string ans = "No";
    if (s[0] == s[1] && s[2] == s[3] && s[1] != s[2]){
        ans = "Yes";
    }
    else if (s[0] == s[2] && s[1] == s[3] && s[2] != s[1]){
        ans = "Yes";
    }
    else if (s[0] == s[3] && s[1] == s[2] && s[3] != s[1]){    
        ans = "Yes";
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main
{
  public static void main(String args[])
  {
    Scanner in=new Scanner(System.in);
    int a=in.nextInt();
    int b=in.nextInt();
    if(a<=9 && b<=9)
    {
      System.out.println(a*b);
    }
    else
    {
      System.out.println("-1");
    }
  }
}
    

Measured memory_bytes: 35752
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

      
import sys
input=sys.stdin.readline
n,m = map(int, input().split())
ab = []
for i in range(m):
    tmp = list(map(int,input().split()))
    ab.append(tmp)
ab.reverse()

ans=[]
last=n*(n-1)//2
ans.append(last)
uf = UnionFind(n)

for i in ab:
    n1=i[0]-1
    n2=i[1]-1

    if not uf.same(n1,n2):
        s1=uf.size(n1)
        s2=uf.size(n2)
        last-=s1*s2
    ans.append(last)
    uf.union(n1,n2)

ans.reverse()
for a in ans[1:]:
    print(a)      

Measured memory_bytes: 106588
#include <algorithm>
#include <iostream>
#include <queue>
#define INF (1e9)
#define f first
#define s second
#define N 7
using namespace std;
typedef pair<int,int> P;
int bfs();
bool Check(int,int,int,int,int,int);
int w,h,data[N][N],d[N][N][N][N];
int scy,scx,swy,swx,gcy,gcx;
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
struct dat{
  int cy,cx,wy,wx;
};

int main(){
  while(1){
    cin>>w>>h;
    if(!w&&!h) break;
    for(int i=0;i<h;i++)
      for(int j=0;j<w;j++){
	cin>>data[i][j];
	if(data[i][j]==2) scy=i,scx=j;
	if(data[i][j]==3) gcy=i,gcx=j;
	if(data[i][j]==4) swy=i,swx=j;
	for(int k=0;k<h;k++)
	  for(int l=0;l<w;l++) d[i][j][k][l]=INF;
      }
    cout<<bfs()<<endl;
  }
  return 0;
}

int bfs(){
  queue<dat > Q;
  for(int i=0;i<4;i++){
    int ny=scy+dy[i],nx=scx+dx[i];
    if(ny<0||nx<0||h<=ny||w<=nx||data[ny][nx]==1) continue;
    if(!Check(swy,swx,ny,nx,scy,scx)) continue;
    Q.push((dat){scy,scx,ny,nx});
    d[scy][scx][ny][nx]=0;
  }
  /*  Q.push((dat){swy,swx,scy,scx});
      d[swy][swx][scy][scx]=0;*/
  while(!Q.empty()){
    dat t=Q.front();
    Q.pop();
    if(t.cy==gcy&&t.cx==gcx) return d[gcy][gcx][t.wy][t.wx];
    for(int i=0;i<4;i++){
      int ncy=t.cy+dy[i],ncx=t.cx+dx[i],nwy=t.cy,nwx=t.cx;
      if(ncy<0||ncx<0||h<=ncy||w<=ncx||data[ncy][ncx]==1) continue;
      if(!Check(t.wy,t.wx,nwy-dy[i],nwx-dx[i],t.cy,t.cx)) continue;
      if(d[ncy][ncx][nwy][nwx]>d[t.cy][t.cx][t.wy][t.wx]+1){
	d[ncy][ncx][nwy][nwx]=d[t.cy][t.cx][t.wy][t.wx]+1;
	Q.push((dat){ncy,ncx,nwy,nwx});
      }
    }
  }
  return -1;
}

bool Check(int sy,int sx,int gy,int gx,int xy,int xx){
  bool c[h][w];
  queue<P > Q;
  if(sy<0||sx<0||h<=sy||w<=sx||data[sy][sx]==1) return false;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++) c[i][j]=false;
  Q.push(make_pair(sy,sx));
  c[sy][sx]=true;
  while(!Q.empty()){
    P t=Q.front();
    Q.pop();
    int uy=t.f,ux=t.s;
    if(uy==gy&&ux==gx) return true;
    for(int i=0;i<4;i++){
      int ny=uy+dy[i],nx=ux+dx[i];
      if(ny<0||nx<0||h<=ny||w<=nx||data[ny][nx]==1||(ny==xy&&nx==xx)) continue;
      if(c[ny][nx]) continue;
      c[ny][nx]=true;
      Q.push(make_pair(ny,nx));
    }
  }
  return false;
}

Measured memory_bytes: 1212
#include <iostream>
#include <vector>

using namespace std;

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

int SelectionSort(int A[], int N)
{
    int sw = 0;
    for(int i=0;i<N;++i){
        int minj = i;
        for(int j=i;j<N;++j){
            if(A[j] < A[minj]) minj = j;
        }
        if(A[i]!=A[minj]){
            swap(A[i],A[minj]);
            sw++;
        }
    }
    return sw;
}

int main()
{
    int N, sw;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    sw = SelectionSort(A, N);
    Trace(A, N);
    cout << sw << endl;

    return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int main() {
	int N, L;
	cin >> N >> L;
	int S = (N - 1) * N / 2 + N * L;
	int dect = 987654321;
	for (int i = 0; i < N; i++) {
		int cand = i + L;
		if (abs(cand) < abs(dect)) {
			dect = cand;
		}
	}
	cout << (S - dect) << endl;
}

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

int main() {
  int n, m;
  cin >> n >> m;
  int l, r;
  cin >> l >> r;
  for (int i=1; i<m; i++) {
    int L, R;
    cin >> L >> R;
    l = max(l, L);
    r = min(r, R);
  }
  if (l>r) cout << 0 << endl;
  else cout << r-l+1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;

int main() {

    long N;

    cin >> N;

    // N = A * B
    // B = N / A
    
    // A , B 桁数大きい方の、最小値
    long ans = 100000000;

    double d = sqrt(N) + 10;
    //cout << "d: " << d << endl;

    for (long i = 1; i < d ; i++) {
        long a = i;

        //整数チェック
        if (N % a != 0){
            continue;
        }
        long b = N / a;

        //cout << "a: " << a << "   b: " << b << endl;
        string s_a = to_string(a);
        int k_a = s_a.size();
        string s_b = to_string(b);
        int k_b = s_b.size();

        int m = max(k_a, k_b);

        if (ans > m){
            ans = m;
        }
    }

    cout << ans << endl;

    return 0;

}

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

#define ff               first
#define ss               second
#define mp               make_pair
#define pb               push_back
#define pii              pair<int,int>
#define vi               vector<int> 
#define mii              map<int,int>
#define setbits(x)       __builtin_popcountll(x)
#define zerobits(x)      __builtin_ctzll(x)
#define mod              1000000007
#define inf              1e18
#define endl             "\n"

void h_code()
{
 #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
 #endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

void l_code()
{
 #ifndef ONLINE_JUDGE
     cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";
 #endif
}
const int N=100005;

int main() {
 //   h_code();
    int t=1;
    
    while(t--)
    {
        int h,n,temp;
        cin>>h>>n;
        long long sum=0;
        bool flag =0;
        for(int i=0;i<n;i++)
        {   cin>>temp;
            sum+=temp;
            if(sum>=h)
                {
                    flag=1;                  
                }
        
        }
        if(flag)
            cout<<"Yes";
        else
        {
            cout<<"No";
        }
        

    }
  //  l_code();
}

Measured memory_bytes: 256
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Security.Policy;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
        checked {
#if DEBUG
            MyDebugger.Test(process, "../TextFile1.txt");
            //TestCaseMaker.MakeTestCase1("../TextFile2.txt");
            //MyDebugger.Test(process, "../TextFile2.txt");
#else
            object ret = process(new StreamReader(Console.OpenStandardInput()));
            Console.WriteLine(ret);
#endif
        }
    }

    static object process(TextReader input) {
        //1000000000000001
        var n = long.Parse(input.ReadLine());

        //26進数
        var sb = new StringBuilder();

        while(n > 0) {
            //Debug.WriteLine(n);
            var x = (n % 26);
            if(x == 0){
                x = 26;
                var c = ('a' - 1) + x;
                sb.Append((char)c);
                n /= 26;
                n -= 1;
            } else {
                var c = ('a' - 1) + x;
                sb.Append((char)c);
                n /= 26;
            }
        }

        var sb2 = new StringBuilder(sb.Length);
        for(int i=0; i<sb.Length; i++) {
            sb2.Append(sb[sb.Length-i-1]);
        }

        return sb2;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        if(n == 0) return ret;
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


Measured memory_bytes: 27452
import math
n = int(input())
lis = [[0] * n for i in range(n)]
for i in range(n):
  for j in range(n):
    lis[i][j] = math.gcd(i+1,j+1)
ans = 0
for i in range(n):
  for j in range(n):
    for k in range(n):
      ans += lis[i][lis[k][j]-1]
print(ans)


Measured memory_bytes: 9304
import java.util.*;
class Main{
    int d[]={0,-1};
    void run(){
	Scanner sc=new Scanner(System.in);
	int n=sc.nextInt();
	for(int attend=0;attend<n;attend++){
	    String str=sc.next();
	    HashSet<String> hashSet=new HashSet<String>();
	    for(int i=1;i<str.length();i++){
		//System.out.println("yahoo!");
		String[] div=new String[4];
		div[0]=str.substring(0,i);
		div[1]=(new StringBuffer(div[0])).reverse().toString();
		div[2]=str.substring(i,str.length());
		div[3]=(new StringBuffer(div[2])).reverse().toString();
		for(int j=0;j<4;j++){
		    for(int k=0;k<2;k++){
			hashSet.add(div[j]+div[(j+2+k+d[j%2])%4]);
		    }
		}
	    }
	    System.out.println(hashSet.size());
	}
    }
    public static void main(String[] args){
	new Main().run();
    }
}
//imitated

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

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

typedef long long int ll;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> v(n);
  rep(i, n) { cin >> v[i]; }
  int maxx = 0;
  int summ = 0;
  queue<int> q;
  rep(i, n) {
    summ += v[i];
    q.push(v[i]);
    if (q.size() > m) {
      summ -= q.front();
      q.pop();
    }
    if (q.size() == m) {
      maxx = max(maxx, summ);
    }
  }
  maxx += m;
  double ans = maxx;
  ans /= 2;
  printf("%.10f\n", ans);
}


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

int main(){
    long long int a;
    string s;
    cin>>a>>s;
    s.erase(1,1);
    
    istringstream ss1;
    int b;
    ss1=istringstream(s);
    ss1>>b;  

    long long int ans=a*b;
    ans/=100;
    cout<<ans<<endl;
}

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

struct UF{
    vector<int> p;
    int n;

    UF(int siz){
        n = siz;
        p.resize(n, 0);
        for(int i = 0; i < n; i++)  p[i] = i;
    }

    int parent(int x){
        if(p[x] != x)   p[x] = parent(p[x]);
        return p[x];
    }

    bool same(int i, int j){
        return parent(i) == parent(j);
    }

    void unite(int x, int y){
        x = parent(x), y = parent(y);
        p[x] = y;
    }
};

int main(){
    int n, m;
    while(cin >> n >> m, n+m){
        priority_queue<pair<int,pair<int,int>>> pq;
        int a, b, w;
        while(m-- > 0){
            cin >> a >> b >> w;
            pq.push({-w, {--a, --b}});
        }
        int cnt = 0;
        UF uf(n);
        auto c = pq;
        while(!c.empty()){
            auto p = c.top();   c.pop();
            int i = p.second.first, j = p.second.second;
            if(!uf.same(i, j)){
                cnt++;
                uf.unite(i, j);
            }
        }
        if(cnt != n-1){
            cout << -1 << endl;
            continue;
        }
        int ans = 1<<30;
        int bef = 0;
        while(true){
            while(pq.size() > 0 && pq.top().first == bef)   pq.pop();
            if(pq.size() == 0)  break;
            bef = pq.top().first;
            cnt = 0;
            UF u(n);
            auto c = pq;
            int aft = bef;
            while(!c.empty() && cnt < n-1){
                auto p = c.top();   c.pop();
                int i = p.second.first, j = p.second.second;
                if(!u.same(i,j)){
                    aft = p.first;
                    u.unite(i, j);
                    cnt++;
                }
            }
            if(cnt < n-1){
                break;
            }
            ans = min(ans, bef-aft);
        }
        cout << ans << endl;
    }
    return 0;
}


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

using namespace std;
#define N 1001000
#define SIGMA 26
string S;
long long v[N], s[N];
long long ans, p;
int n, i;
int main()
{
    cin >> S;
    v[0] = 0;
    ans = 0;
    for (i = 0; i < S.size(); ++i){
        v[i + 1] = S[i] - '0';
    }
    for (i = S.size(); i > -1; --i){
        if (v[i] < 10 - v[i] || (v[i] == 10 - v[i]) && v[i - 1] < 5)
            ans += v[i];
        else{
            ++v[i - 1];
            ans += 10 - v[i];
        }
    }
    cout << ans;
    return 0;
}


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

void display(int A[], int N){
  for(int i=0;i<N;i++){
    if(i==N-1){
      cout << A[i];
    } else {
      cout << A[i] << " ";
    }
  }
  cout << endl;
}

int bubbleSort(int A[], int N){
  int counter = 0;
  int flag = 1;
  while (flag) {
    flag = 0;
    for(int j=N-1;j>=1;j--){
      if(A[j]<A[j-1]){
        int k = A[j];
        A[j] = A[j-1];
        A[j-1] = k;
        flag = 1;
        counter++;
      }
    }
  }

  return counter;
}

int main(){
  int N;
  int counter = 0;
  cin >> N;
  int res[N];
  for(int i=0;i<N;i++){
    res[i] = 0;
  }

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

  counter = bubbleSort(res, N);
  display(res, N);
  cout << counter << endl;
}



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

using namespace std;

using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
vector<vector<ll>> G;
int main() {
    ll n, m, i, j, k;
    cin >> n;
    G.resize(n);
    vector<pair<ll,ll>> vp(n-1);
    for(i=0;i<n-1;i++){
        ll a,b;
        cin >> a >> b;
        vp[i]={a-1,b-1};
        G[--a].push_back(--b);
        G[b].push_back(a);
    }
    vector<ll> v(n);
    for(i=0;i<n;i++){
        v[i] = i;
    }
    sort(v.rbegin(),v.rend(),[](const ll f,const ll s){
        return G[f].size() < G[s].size();
    });
    //cout << v[2] << endl;
    //vector<ll> col(n,0);
    map<pair<ll,ll>,ll> mp;
    queue<ll> que;
    que.push(v[0]);
    ll parent = 0;
    while(!que.empty()){
        ll p = que.front();
        que.pop();
        //cout << p << endl;
        for(ll x : G[p]) {
            if(mp[{min(p, x), max(p, x)}] != 0) parent = mp[{min(p, x), max(p, x)}];
        }
        ll now = 1;
        for(ll x : G[p]) {
            if(now==parent)now++;
            if(mp[{min(p,x),max(p,x)}]!=0)continue;
            mp[{min(p,x),max(p,x)}] = now++;
            que.push(x);
        }
    }
    cout << G[v[0]].size() << endl;
    for(i=0;i<n-1;i++){
        cout << mp[{min(vp[i].first, vp[i].second), max(vp[i].first, vp[i].second)}] << endl;
    }
    return 0;
}

Measured memory_bytes: 15104
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func
    
    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, Q, S, TD):
    def reachable(i):
        if i < 0:
            return -1
        elif i >= N:
            return 1
        for t, d in TD:
            if S[i] == t:
                if d == 'L':
                    i -= 1
                else:
                    i += 1
            if i == -1:
                return -1
            elif i == N:
                return 1
        return 0

    ans = N
    b = Bisect(lambda x: reachable(x))
    ans -= b.bisect_left(0, 0, N)
    ans -= N - b.bisect_right(0, 0, N)
    return ans



def main():
    N, Q = read_int_n()
    S = read_str()
    TD = [read_str_n() for _ in range(Q)]
    print(slv(N, Q, S, TD))

if __name__ == '__main__':
    main()


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

using namespace std;

template <class T>inline T updmax(T &a, T b) { return a = max(a, b); }
template <class T>inline T updmin(T &a, T b) { return a = min(a, b); }

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int a,b;
	cin >> a >> b;
	if((a+b)&1)cout << "IMPOSSIBLE" << "\n";
	else cout << (a+b)/2 << "\n";
	return 0;
}

Measured memory_bytes: 256
n, m, l = gets.split.map(&:to_i)
A = n.times.map{gets.split.map(&:to_i)}
B = m.times.map{gets.split.map(&:to_i)}

n.times do |i|
	_Ai = A[i]
	puts l.times.map {|j|
		m.times.map{|k| _Ai[k] * B[k][j]}.inject(&:+)
	}.join(' ')
end

Measured memory_bytes: 12404
import Control.Applicative
import Control.Monad
import Data.Function

c a b = if a < b then (a,b) else (b,a)

main :: IO ()
main = do
    fix $ \loop -> do
        [a,b] <- map read . words <$> getLine
        unless ([a,b] == [0,0]) $ do
            let r = c a b
            putStrLn $ (show $ fst r) ++ " " ++ (show $ snd r)
            loop


Measured memory_bytes: 4124
import Data.List (transpose, sort)

main = do

    [n, h] <- take 2 . map read . words <$> getLine
    sords <- sequence $ replicate n (map read . words <$> getLine) :: IO [[Int]]

    let [atks, thrs] = transpose sords
        maxDps = maximum atks
        needThrowSords = reverse . sort . filter (maxDps <) $ thrs
        attackCount
            | h <= sum needThrowSords = (+1). length . takeWhile (h >) . scanl1 (+) $ needThrowSords
            | otherwise               = 1 + length needThrowSords + (h - 1 - sum needThrowSords) `div` maxDps
        in
            print attackCount

Measured memory_bytes: 183676
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int len=s.length();
    if(s[0]==s[len-1])
    {
        if(len%2==1)
            printf("Second\n");
        else
            printf("First\n");
    }
    else
    {
        if(len%2==1)
            printf("First\n");
        else
            printf("Second\n");
    }
    return 0;
}


Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int n, m;
int c[20];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> c[i];
    }
    int M[50000];
    M[0] = 0;
    for (int i = 1; i <= n; i++) {
        M[i] = n;
        for (int j = 0; j < m; j++) {
            if (c[j] <= i) {
                M[i] = M[i] >= M[i - c[j]] + 1 ? M[i - c[j]] + 1 : M[i];
            }
        }
    }
    cout << M[n] << endl;
}


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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int main(){
  int n, x, t;
  cin >> n >> x >> t;

  int ans = (n+(x-1)) / x;
  int ans1 = ans * t;

  cout << ans1;

}

Measured memory_bytes: 3600
#pragma GCC optimize("O3")

#include<iostream>

using namespace std;
typedef unsigned int ll;

#define REP(i,n) for(ll i=0;i<n;i++)
#define MOD 1000000007 //10^9+7:合同式の法


ll s[2001],t[2001],dp[2001][2001],n,m={0};

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    REP(i,n){cin>>s[i];}
    REP(i,m){cin>>t[i];}
    REP(i,n+1){dp[i][0]=1;}
    REP(i,m+1){dp[0][i]=1;}
    REP(i,n){
        REP(j,m){
            dp[i+1][j+1]+=dp[i+1][j];
            dp[i+1][j+1]+=dp[i][j+1];
            if(s[i]!=t[j])dp[i+1][j+1]+=(MOD-dp[i][j]);
            dp[i+1][j+1]%=MOD;
        }
    }
    cout<<dp[n][m]<<"\n";
}

Measured memory_bytes: 19164
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <sstream>

struct Node
{
  int data;
  Node* parent;
  int rank;
  Node() : data(-1), parent(this), rank(0){}
  Node& operator=(int data){ this->data = data; return *this; }
  Node* Find(){
    if (this == this->parent){
      return this;
    } else {
      auto root = this->parent->Find();
      this->parent = root;
      return root;
    }
  }
  static void Union(Node& lhs, Node& rhs){
    Node* lhs_root = lhs.Find();
    Node* rhs_root = rhs.Find();
    if (lhs_root->rank > rhs_root->rank){
      rhs_root->parent = lhs_root;
    } else if (rhs_root->rank > lhs_root->rank){
      lhs_root->parent = rhs_root;
    } else if (rhs_root != lhs_root){
      lhs_root->parent = rhs_root;
      rhs_root->rank += 1;
    }
    return;
  }
};

bool is_not_space(int c){ return c != ' '; }
std::string& ltrim(std::string& str){
  str.erase(str.begin(), std::find_if(str.begin(), str.end(), is_not_space));
  return str;
}
std::string& rtrim(std::string& str){
  str.erase(std::find_if(str.rbegin(), str.rend(), is_not_space).base(), str.end());
  return str;
}
std::string trim(std::string& str){ return ltrim(rtrim(str)); }

struct Edge{
  int i,j,w;
  bool exist;
  Edge(int i,int j,int w): i(i), j(j), w(w), exist(true){ if(w==-1){ this->exist = false; } }
  int Value(){ return this->exist ? this->w : 2005; }
};
int main(void){
  std::string line;
  std::getline(std::cin, line);
  int n = std::stoi(line);
  std::vector<Node> V(n);
  std::vector<Edge> E;
  for(int i = 0; i < n; ++i){
    std::getline(std::cin, line);
    std::stringstream ss(trim(line));
    for(int j = 0; j < n; ++j){
      int w;
      ss >> w;
      E.emplace_back(i,j,w);
    }
  }
  int sum_w = 0;
  for(int remain = n-1; remain > 0;){
    auto min_elem = std::min_element(E.begin(), E.end(), [](auto& lhs, auto& rhs){ return lhs.Value() < rhs.Value(); });
    min_elem->exist = false;
    E[min_elem->j * n + min_elem->i].exist = false;
    if(V[min_elem->i].Find() != V[min_elem->j].Find()){
      Node::Union(V[min_elem->i], V[min_elem->j]);
      sum_w += min_elem->w;
      remain -= 1;
    }
  }
  std::cout << sum_w << std::endl;
  return 0;
}


Measured memory_bytes: 3292