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


void input(); template<typename First,typename... Rest> void input(First&,Rest&...);
void inputVector(); template<typename First,typename... Rest>  void inputVector(std::vector<First>&,Rest&...);
#define loop(n) for(int i = 0;i < (int)(n);++i)
#define rep(i,n) for(int i = 0;i < (int)(n);++i)


void calculate(){

}

int main(int,char**){
    std::string str;
    input(str);
    std::cout << str[0] << str.size() - 2 << str[str.size() - 1] << '\n';
}



void input(){return;}
template<typename First,typename... Rest>
void input(First &first,Rest&... rest){
    std::cin >> first;
    input(rest...);
}

void inputVector(){return;}
template<typename First,typename... Rest> 
void inputVector(std::vector<First> &first,Rest&... rest){
    int N = first.size();
    for(int i = 0;i < N;i++){
        std::cin >> first[i];
    }
    inputVector(rest...);
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    int i, N;
    long long K, k = 0;
    static long long list[100001];

    scanf("%d %lld", &N, &K);

    for ( i = 0; i < N; i++ ){
        int a, b;
        scanf("%d %d", &a, &b);
        list[a] += b;
    }

    for ( i = 1; i <= 100000; i++ ){
        if ( k + list[i] >= K ){
            printf("%d\n", i);
            break;
        }
        k += list[i];
    }
    return 0;
}

Measured memory_bytes: 896
fun main(args: Array<String>) {
    val(N, Y) = readLine()!!.split(" ").map(String::toInt)
    var res1000 = -1
    var res5000 = -1
    var res10000 = -1
    for (a in 0..N) {
        for (b in 0..N-a) {
            val c = N - a - b
            val total = a*1000 + b*5000 + c*10000
            if (total == Y) {
                res1000 = a
                res5000 = b
                res10000 = c
            }
        }
    }
    println("$res10000 $res5000 $res1000")
}

Measured memory_bytes: 37904
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <boost/xpressive/xpressive.hpp>

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;
using namespace boost;

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

  S.pop_back();
  xpressive::smatch m;
  const xpressive::sregex re = xpressive::sregex::compile("^([a-z]+)\\1");
  xpressive::regex_search(S, m, re);
  cout << m.str().length() << endl;
  return 0;
}


Measured memory_bytes: 3892
n,k=gets.strip.split.map(&:to_i)
a=gets.strip.split.map(&:to_i)
i=0
count=0
while i<n && a[i]==0
  i+=1
end
while i<n
  count+=1
  j=i
  while j<n && a[j]>0
    a[j]-=1
    j+=1
  end
  
  while i<n && a[i]==0
    i+=1
  end
end
puts count


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define ll long long int
#define F first
#define S second
#define pb push_back
#define sd(x) scanf("%d",&x)
#define sd2(x,y) scanf("%d%d",&x,&y);
#define sdl(x) scanf("%lld",&x)
#define sd2l(x,y) scanf("%lld%lld",&x,&y);
#define sz(x) (int)(x.size())
#define nax 101010
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define mp make_pair
#define pi pair<int ,int>
#define pii pair <int,pi>
using namespace std;
int main(int argc, char const *argv[])
{
  //freopen("input.txt","r",stdin);
  //freopen("output.txt","w",stdout);
  string x;
  cin >> x;
  int l = x.length();
  for(int i=1;i<=l;i++)
  {
    if((l-i) % 2 == 0)
    {
        if(x.substr(0,(l-i)/2) == x.substr((l-i)/2,(l-i)/2))
        {
          printf("%d\n",l-i);
          return 0;
        }
    }
  }
  return 0;
}
 

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define ll long long int
#define MIN(x,y) (x)>(y)?(y):(x)
#define MAX(x,y) (x)>(y)?(x):(y)
#define ABS(x) (x)>0?(x):(-x)

//ばなな

int main(void){
	const ll INF = (ll)1<<50;
	int n,m;
	scanf("%d%d",&n,&m);
	int a[m],b[m];
	ll c[m];
	for(int i=0;i<m;i++){
		scanf("%d%d%lld",&a[i],&b[i],&c[i]);
		c[i] = -c[i];
		a[i]--;
		b[i]--;
	}
	ll dist[n];
	dist[0]=0;
	for(int i=1;i<n;i++)dist[i]=INF;
	
	for(int loop=0;loop<n-1;loop++){
		for(int i=0;i<m;i++){
			if(dist[a[i]]==INF)continue;
			if(dist[b[i]] > dist[a[i]]+c[i])
			dist[b[i]] = dist[a[i]]+c[i];
		}
	}
	ll ans=dist[n-1];
	
	bool negative[n];
	for(int i=0;i<n;i++)negative[i]=false;
	for(int loop=0;loop<n;loop++){
		for(int i=0;i<m;i++){
			if(dist[a[i]]==INF)continue;
			if(dist[b[i]] >dist[a[i]]+c[i]){
				dist[b[i]]=dist[a[i]]+c[i];
				negative[b[i]]=true;
			}
			if(negative[a[i]])negative[b[i]]=true;
		}
	}
	if(negative[n-1])printf("inf");
	else printf("%lld",-ans);
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int k = scan.nextInt();
		long ans = 0;
		ans = k * (long) Math.pow(k - 1, n - 1);
		System.out.println(ans);

	}
}

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

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

  int card[4][13] = {0};

  for (int i = 0; i < N; i++) {
    char S;
    int R;
    cin >> S >> R;
    R--;
    if (S == 'S') card[0][R] = 1;
    if (S == 'H') card[1][R] = 1;
    if (S == 'C') card[2][R] = 1;
    if (S == 'D') card[3][R] = 1;
  }

  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 13; j++) {
      if (card[i][j] != 1) {
        if (i == 0) cout << 'S' << ' ' << j + 1 << endl;
        if (i == 1) cout << 'H' << ' ' << j + 1 << endl;
        if (i == 2) cout << 'C' << ' ' << j + 1 << endl;
        if (i == 3) cout << 'D' << ' ' << j + 1 << endl;
      }
    }
  }
}


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

def isPrime(x):
    if x < 2:
        return false
    if x == 2:
        return True
    return pow(2, x-1, x) == 1

s = []
for i in range(n):
    s.append(int(input()))

prime = 0
for i in s:
    if isPrime(i):
        prime += 1
print(prime)

Measured memory_bytes: 5976
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<endl
#define INF10 1001001001 
#define INF5 100000
#define EPS 1e-10

int N, M;

int g[100][100];

int ans;

set<int> dfs(int cur, int i, int j, set<int>seen) {
	seen.insert(cur);
	for (int k = 0; k < N; k++) {
		if (g[cur][k] == 0)continue;
		else if ((cur == i && k == j) || (cur == j && k == i))continue;
		else if(seen.count(k)==0) {
			seen = dfs(k, i, j, seen);
		}
	}
	if (cur == 0 && seen.size() != N)ans++;
	return seen;
}
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b; a--; b--;
		g[a][b] = 1;
		g[b][a] = 1;
	}
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (g[i][j] == 0)continue;
			else dfs(0, i, j, set<int>());
		}
	}
	cout << ans << endl;




	return 0;
}


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

using namespace std;

signed main(){
string s,t;
  cin >> s >> t;
  int sol= s.size();
  for(int i =0;i < s.size(); i++){
  	if(s[i]==t[i])
      sol--;
  }
  cout<< sol << endl;
}

Measured memory_bytes: 3916
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
const int maxn = 2000000 + 10;
const ll mod = 1000000000 + 7;
ll quick(ll a, ll n) {
    ll ans = 1;
    for (; n; n >>= 1, a = a * a % mod) {
        if (n & 1) ans = ans * a % mod;
    }
    return ans;
}
ll fac[maxn], inv[maxn], pre[maxn];
void init() {
    fac[0] = inv[0] = 1;
    for (ll i = 1; i < maxn; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    for (ll i = 1; i < maxn; i++) {
        pre[i] = (pre[i] + fac[i - 1]) % mod;
    }
    inv[maxn - 1] = quick(fac[maxn - 1], mod - 2);
    for (ll i = maxn - 2; i >= 1; i--) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}
ll r1, c1, r2, c2;

ll fun(ll k, ll n) {
    ll m = k;
    n = n + k + 1;
    return fac[n] * inv[n - m] % mod * inv[m] % mod;

}

int main() {
    init();
    cin >> r1 >> c1 >> r2 >> c2;

    ll ans = 0;
    for (ll i = c1; i <= c2; i++) {
        ans += (fun(r2, i) - fun(r1 - 1, i) + mod) % mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 47104
#include<iostream>
#include<string>
#include <vector>
#include <algorithm>
#define max(a,b) ((a < b) ? b : a)
#define min(a,b) ((a > b) ? b : a)
using namespace std;
int main() {
  // 入力
  int n;
  cin >> n;
  vector<int> v, s;
  s.push_back(0);
  
  for (int i = 1; i <= n; i++) {
    int w;
    cin >> w;
    v.push_back(w);
    s.push_back(s[i-1] + w);
  }
  
  int s1 = s[1];
  int s2 = s[n] - s[1];
  int ss = max(s1 - s2, s2 - s1);
  int smin = ss;
  for (int i = 2; i <= n-1; i++) {
    s1 = s[i];
    s2 = s[n] - s[i];
    ss = max(s1 - s2, s2 - s1);
    smin = min(smin, ss);
  }
  
  // 出力
  cout << smin << endl;
  
  return 0;
}


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

using namespace std;
using LL = long long;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e19;
const int MOD = (int)1e9 + 7;

// gcd: 最大公約数, lcm: 最小公倍数
template<typename T>
T euclidean(T a, T b){
    if(a < b) swap(a, b);
    T r = a % b;
    while(r != 0){
        a = b; b = r; r = a % b;
    }
    return b;
}
template<typename T>
T gcd(T a, T b){
    return euclidean(a, b);
}
template<typename T>
T lcm(T a, T b){
    T g = gcd(a, b);
    return a / g * b;
}

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

    int n;
    cin >> n;
    vector<int> a(n);
    REP(i, n) cin >> a[i];

    int ans = a[0];
    REP(i, n-1){
        ans = gcd(ans, a[i+1]);
    }
    cout << ans << endl;
}

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

int main(){
    long long a,b,c,d=0,e=0;
    for(int i=1;i<6;i++){
        cin>>a;
        if(a==0){cout<<i;return 0;}
    }
    cout<<'0';
    return 0;
}


Measured memory_bytes: 3616
#include<iostream>
using namespace std;
int main()
{
    int a,b,c,s;
    cin>>a>>b>>c;
    s=a+b+c;
    if(s>=22)
    {
        cout<<"bust"<<endl;
    }
    else
    {
        cout<<"win"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3484
n = int(input())
h = list(map(int, input().split(' ')))
h.reverse()
flg = True

for i in range(len(h) - 1):
    if h[i] < h[i + 1]:
        if h[i + 1] - h[i] <= 1:
            h[i + 1] -= 1
        else:
            flg = False
            break

if flg:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 14396
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
#define fi first
#define se second

void END(){
    cout<<"NO"<<endl;
    exit(0);
}

signed main(){
    int h,w,n;
    cin>>w>>h>>n;
    vector<P>v1,v2,v3,v4;
    r(i,n){
        int x,y,X,Y;
        cin>>x>>y>>X>>Y;
        if((x==0||x==w)||(y==0||y==h)){
            if((X==0||X==w)||(Y==0||Y==h)){
                r(j,2){
                    if(0<x&&x<w){
                        if(y==0)v1.push_back(P(x,i));
                        if(y==h)v3.push_back(P(-x,i));
                    }
                    else{
                        if(x==0)v4.push_back(P(-y,i));
                        if(x==w)v2.push_back(P(y,i));
                    }
                    x = X;
                    y = Y;
                }
            }
        }
    }
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    sort(v3.begin(),v3.end());
    sort(v4.begin(),v4.end());
    stack<int>st;
    set<int>ss;
    r(i,v1.size()){
        int x=v1[i].second;
        if(ss.count(x)){
            if(st.top()!=x)END();
            st.pop();
        }
        else{
            st.push(x);
            ss.insert(x);
        }
    }
    r(i,v2.size()){
        int x=v2[i].second;
        if(ss.count(x)){
            if(st.top()!=x)END();
            st.pop();
        }
        else{
            st.push(x);
            ss.insert(x);
        }
    }
    r(i,v3.size()){
        int x=v3[i].second;
        if(ss.count(x)){
            if(st.top()!=x)END();
            st.pop();
        }
        else{
            st.push(x);
            ss.insert(x);
        }
    }
    r(i,v4.size()){
        int x=v4[i].second;
        if(ss.count(x)){
            if(st.top()!=x)END();
            st.pop();
        }
        else{
            st.push(x);
            ss.insert(x);
        }
    }
    cout<<"YES"<<endl;
}

Measured memory_bytes: 8236
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
//#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

const double PI = acos(-1);
const double EPS = 1e-9;

const int MX = 100005;
const int MM = 1000000007;

struct mat{
	ll t[4][4];
	mat operator-(const mat &l){
		mat r = {};
		for(int i = 0; i <4; i++){
			for(int j = 0; j < 4; j++){
				r.t[i][j] = (t[i][j] - l.t[i][j] + MM) % MM;
			}
		}
		return r;
	}
	mat operator*(const mat &l){
		mat r = {};
		for(int k = 0; k < 4; k++){
			for(int i = 0; i < 4; i++){
				for(int j = 0; j < 4; j++){
					r.t[i][j] = (r.t[i][j] + t[i][k] * l.t[k][j]) % MM;
				}
			}
		}
		return r;
	}
};

mat DB = {{
	{0, 0, MM-1, 2},
	{0, 1, MM-1, 2},
	{0, 1, 0, 2},
	{0, 1, 0, 3}
}};

mat pw(mat A, int x){
	mat R = {};
	for(int i = 0; i < 4; i++) R.t[i][i] = 1;

	while(x){
		if( x&1 ) R = R*A;
		A = A*A; x /= 2;
	}
	return R;
}

ll get(int x){
	mat R = pw(DB, x);

	return (R.t[0][0] + R.t[0][1] + R.t[0][2] + R.t[0][3]) % MM;
}

ll A[MX], B[MX];

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	for(int i = 1; i <= M; i++) scanf("%lld", A+i); A[++M] = N;

	mat cur = {};

	for(int i = 1; i <= M; i++){
		mat R = pw(DB, A[i]) - cur;
		B[i] = (R.t[0][0] + R.t[0][1] + R.t[0][2] + R.t[0][3]) % MM;
		for(int t = 0; t < 4; t++) cur.t[t][t] = (cur.t[t][t] + B[i]) % MM;
		cur = cur * pw(DB, A[i+1] - A[i]);
	}
	printf("%lld\n", B[M]);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll int a,b,q=0,i=1;
    cin>>a >>b;
    while(i<=INT_MAX){
      if((max(a,b))*i%a==0 && max(a,b)*i%b==0){
        q=max(a,b)*i;
        break;
      }
      else{i++;continue;}
      i++;
    }
    cout<<q <<endl;
}




Measured memory_bytes: 3612
/*
    Author:zeke

    pass System Test!
    GET AC!!
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
// cout << "Case #" << index << " :IMPOSSIBLE";
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    ll d;
    cin >> d;
    V C(26);
    rep(i, 26) cin >> C[i];
    VV S(d, V(26));
    rep(i, d) { rep(j, 26) cin >> S[i][j]; }
    rep3(i,0,d){
        cout<<i%26+1<<endl;
    }
}


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


typedef long long ll;


ll *mem, *inp, dist, min_dist, N;
int k;

int main()
{
    ll i, j;
    scanf("%lld%d", &N, &k);

    mem =(ll*) malloc(N * sizeof(ll));
    inp =(ll*) malloc(N * sizeof(ll));

    for(i = 0; i<N; ++i){
        scanf("%lld", inp+i);
    }

    *(mem+N-2) = llabs(*(inp+N-2) - *(inp+N-1));

    for(i = 3; i<=k+1 && i<=N; ++i)
        *(mem+N-i) = llabs(*(inp+N-i) - *(inp+N-1));

    for(i = N-(k+2); i>=0; --i){

        min_dist = llabs(*(inp+i) - *(inp+i+1)) + *(mem+i+1);
        for(j = 2; j<=k && i+j<N; ++j){
            dist = llabs(*(inp+i) - *(inp+i+j)) + *(mem+i+j);
            if (dist < min_dist) min_dist = dist;
        }

        *(mem+i) = min_dist;
    }

    printf("%lld\n", *mem);

    return 0;
}





Measured memory_bytes: 1792
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]){
        Scanner stdIn = new Scanner(System.in);
        
        int n = stdIn.nextInt();
        //int d1 = stdIn.nextInt();
        //int x = stdIn.nextInt();
        //int num[] = new int[3];
        //String s = stdIn.next();
        //char c[] = s.toCharArray();
        //int sum = 0;
        boolean flag = false;
        //for(int i = 0; i < s.length(); i++){
        //}
        
        for(int i = 1; i < 60001; i++){
        	double d = i * 1.08;
            if((int)d == n){
                System.out.println(i);
                flag = true;
                break;
            }
        }
        
        if(!flag){
            System.out.println(":(");
        }
        
        //System.out.println();
        //System.out.print();
    }
}

Measured memory_bytes: 25172
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;

int a[100000];

int main()
{
	int n, l;
	cin >> n >> l;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
	}
	int knot = 0;
	for (int i = 0; i < n - 1; ++i) {
		int len = a[i] + a[i + 1];
		if (len >= l) {
			knot = i + 1;
			break;
		}
	}
	if (!knot) {
		cout << "Impossible\n";
	} else {
		cout << "Possible\n";
		for (int i = 1; i < knot; ++i) {
			printf("%d\n", i);
		}
		for (int i = n - 1; i > knot; --i) {
			printf("%d\n", i);
		}
		printf("%d\n", knot);
	}
	return 0;
}



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

inline void read(int&x){
	char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();
}

const int N=101000;
struct Edge{int v,nxt;}a[N<<1];
int head[N],sz[N],k[N],fa[N],d[N],v[N];
int n,m,A,B,ga,gb,_,tp;ll ans;

inline int find(int x){return d[x]?d[x]=find(d[x]):x;}

void dfs(int x,int las,int sgn){
	sz[x]=sgn,fa[x]=las;
	if(x==A)ga=sgn;
	else if(x==B)gb=sgn;
	for(int i=head[x];i;i=a[i].nxt)
		if(a[i].v!=las){
			dfs(a[i].v,x,-sgn);
			sz[x]+=sz[a[i].v];
		}
}

bool odd(){
	if(sz[1]&1)return true;
	int t=sz[1]/2;ans+=abs(t);
	for(int i=A;i;i=fa[i])sz[i]-=t;
	for(int i=B;i;i=fa[i])sz[i]-=t;
	return false;
}

bool even(){
	if(sz[1])return true;
	for(int i=A;i;i=fa[i])--k[i];
	for(int i=B;i;i=fa[i])++k[i];
	v[tp=1]=sz[1];
	for(int i=1;i<=n;++i)
		if(k[i]==1)v[++tp]=-sz[i];
		else if(k[i]==-1)v[++tp]=sz[i];
	sort(v+1,v+tp+1);
	int t=v[tp+1>>1];ans+=abs(t);
	for(int i=1;i<=n;++i)sz[i]+=k[i]*t;
	return false;
}

void init();
void print();
int main(){
	init();
	if(m<n)
		if(sz[1])puts("-1");
		else print();
	else if(ga==gb?odd():even())puts("-1");
	else print();
	return 0;
}

void print(){
	for(int i=1;i<=n;++i)
		ans+=abs(sz[i]);
	printf("%lld\n",ans);
}

void init(){
	read(n),read(m);
	int x,y;
	for(int i=0;i<m;++i){
		read(x),read(y);
		if(find(x)!=find(y)){
			d[find(x)]=find(y);
			a[++_].v=y,a[_].nxt=head[x],head[x]=_;
			a[++_].v=x,a[_].nxt=head[y],head[y]=_;
		}else A=x,B=y;
	}
	dfs(1,0,1);
}

Measured memory_bytes: 8576
MOD = 10**9+7
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        inv_t[i] == mod_inv(i)


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if a < b:
        return 0
    if factrial[0] == -1:
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


n, k = [int(_) for _ in input().split()]

for i in range(k):
    print(comb(n-k+1, i+1)*comb(k-1, i) % MOD)


Measured memory_bytes: 20852
#include<cstdio>
int a,b,ans;
int FTO(int x)
{
	if(x%10!=x/10000)return 0;
	if(x/10%10!=x/1000%10)return 0;
	return 1;
}
int main()
{
	scanf("%d%d",&a,&b);
	for(int i=a;i<=b;i++)
		if(FTO(i))
			ans++;
	printf("%d\n",ans);
}

Measured memory_bytes: 128
#include<stdio.h>
#include<stdlib.h>

int main(){
    int n,i,sum=0;
    int a[30],b[30],c[30];

    scanf("%d",&n);

    for(i=1;i<=n;i++){
        scanf("%d",a+i);
    }
    for(i=1;i<=n;i++){
        scanf("%d",b+i);
    }
    for(i=1;i<=n-1;i++){
        scanf("%d",c+i);
    }

    for(i=1;i<=n;i++){
        sum+=b[a[i]];
        if(a[i-1]==a[i]-1){
            sum+=c[a[i-1]];
        }
    }
    printf("%d\n",sum);

    return 0;
}

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

#define __STDC_FORMNT_MACROS
#define p64 PRId64

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define ALL(f, x, ...)                                                         \
    ([&] (decltype ((x)) ALL) {                                                \
        return (f) (begin (ALL), end (ALL), ##__VA_ARGS__);                    \
    }) (x)

using namespace std;
using ll = int64_t;

int main() {
    int N;
    cin >> N;
    cout << pow (N, 3) << endl;
    return 0;
}

Measured memory_bytes: 4156
// Problem : B - Battle
// Contest : AtCoder - AtCoder Beginner Contest 164
// URL : https://atcoder.jp/contests/abc164/tasks/abc164_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

#define ll long long
#define endl "\n"
#define lb "lower_bound"
#define ub "upper_bound"
#define bs "binary_search"

int dif(int a,int b){if(a > b)return a - b;else return b - a;}
int min(int a,int b){if(a > b)return b;else return a;}
int max(int a,int b){if(a > b)return a;else return b;}
int gcd(int a,int b){if(a == 0)return b;else return (a%b,b);}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int a,b,c,d,fg = 0,n = 0;
    cin>>a>>b>>c>>d;
    while(1 == 1)
    {
    	if(fg == 0)
    	{
    		fg = 1;
    		c = c - b;
    	}
    	else if(fg == 1)
    	{
    		fg = 0;
    		a = a - d; 		
    	}
    	if(a <= 0)
    	{
    		cout<<"No";
    		return 0;
    	}
    	else if(c <= 0)
    	{
    		cout<<"Yes";
    		return 0;
    	}
    }
	return 0;
}


Measured memory_bytes: 3608
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int N, Num[100005], Max, Min = 987654321, result;

int abs(int num)
{
    return num > 0 ? num : -num;
}

int main()
{
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
    {
        scanf("%d", &Num[i]);
        Max = max(Max, Num[i]);
    }
    for(int i = 0; i < N; i++)
    {
        if(Max == Num[i])
        {
            continue;
        }
        if(Min > abs(Num[i] - (Max - Num[i])))
        {
            Min = abs(Num[i] - (Max - Num[i]));
            result = Num[i];
        }
    }
    printf("%d %d", Max, result);
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
void read(int &x){
	char ch=getchar();x=0;
	for (;ch==' '||ch=='\n';ch=getchar());
	for (;ch!=' '&&ch!='\n';x=x*10+ch-'0',ch=getchar());
}
int n,a[4];
double dp[303][303][303];
bool vis[303][303][303];
double dfs(int i,int j,int k){
	if (vis[i][j][k]) return dp[i][j][k];
	vis[i][j][k]=1;
	double pos0=(double)(n-i-j-k)/(double)(n),pos1=(double)(i)/(double)(n),pos2=(double)(j)/(double)(n),pos3=(double)(k)/(double)(n);
	if (i!=0) dp[i][j][k]+=pos1*dfs(i-1,j,k);
	if (j!=0) dp[i][j][k]+=pos2*dfs(i+1,j-1,k);
	if (k!=0) dp[i][j][k]+=pos3*dfs(i,j+1,k-1);
	dp[i][j][k]=(dp[i][j][k]+1.0)/(1.0-pos0);
	return dp[i][j][k];
}
int main(){ 
	read(n);
	for (int i=1;i<=n;i++){
		int x;read(x);a[x]++;
	}
	dp[0][0][0]=0.0;vis[0][0][0]=1;
	dfs(a[1],a[2],a[3]);
	printf("%.12lf",dp[a[1]][a[2]][a[3]]);
}

Measured memory_bytes: 243968
import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

n, x0 = map(int, input().split())
x = list(map(int,input().split()))
x.append(x0)
x.sort()
xdiff = []
tmp = x[0]
for xs in x:
    if xs - tmp == 0: continue
    xdiff.append(xs-tmp)
print(gcd_list(xdiff))

Measured memory_bytes: 16308
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
	int n;
	int ma=-10000;
	int num[128][128];
	int sum[128][128]={{0}};
	scanf("%d",&n);
	n++;
	for(int i = 1; i < n; i++){
		for(int j = 1; j < n; j++){
			scanf("%d",&num[i][j]);
		}
	}
	for(int i = 1; i < n; i++){
		for(int j = 1; j < n; j++){
			sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+num[i][j];
		}
	}
	for (int i = 1; i < n; i++){
        for (int j = i; j < n; j++){
        	int res = -10000;
            for (int k = 1; k < n; k++){
                if(i == 1 && k == 1){
                	res = max(sum[j][k],res+sum[j][k]);
                }
                else if(i == 1){
                	res = max(sum[j][k]-sum[j][k-1],res+sum[j][k]-sum[j][k-1]);
                }
                else if(k == 1){
                	res = max(sum[j][k]-sum[i-1][k],res+sum[j][k]-sum[i-1][k]);
                }
                else{
                	res = max(sum[j][k]-sum[j][k-1]-sum[i-1][k]+sum[i-1][k-1],res+sum[j][k]-sum[j][k-1]-sum[i-1][k]+sum[i-1][k-1]);
                }
                ma = max(ma, res);
            }
        }
    }
	printf("%d\n",ma);
	return 0;
}

Measured memory_bytes: 1312
sx,sy,tx,ty = map(int, input().split( ))
u = ty-sy
r = tx-sx
print("R"* r+ "U"*u + "L"*r + "D"*u + "D" 
            + "R"* (r+1)+ "U"*(u+1) + "L" + "U" + "L"*(r+1) + "D"*(u+1) +"R")

Measured memory_bytes: 38384
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
q=min((a-1)%10,(b-1)%10,(c-1)%10,(d-1)%10,(e-1)%10)+1
s=((a+9)//10+(b+9)//10+(c+9)//10+(d+9)//10+(e+9)//10)*10-10+q
print(s)

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <sstream>

using namespace std;

int main() {
    char a;

    cin >> a;

    if(a == 'a' || a == 'i' || a == 'u' || a == 'e' || a == 'o' ){
        cout << "vowel" << endl;
    }
    else {
        cout << "consonant" << endl;
    }
    
    return 0;
}


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

string s;

signed main() {
  cin >> s;

  string a = "";
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'A') {
      a += "(";
    } else if (i + 1 < s.size() && s[i] == 'B' && s[i + 1] == 'C') {
      a += ")";
      i++;
    } else {
      a += "|";
    }
  }

  int ans = 0;
  stack<int> st; //(->1  )-> -1;
  for (int i = 0; i < a.size(); i++) {
    if (a[i] == '(') {

      if (st.empty()) {
        st.push(1);

      } else if (st.top() > 0) {
        int tmp = st.top();
        st.pop();
        st.push(tmp + 1);
      } else {
        st.push(1);
      }

    } else if (a[i] == ')') {

      int cnt = 0;
      if (!st.empty() && st.top() > 0) {
        cnt = st.top();
        ans += st.top();
        st.pop();
      }

      st.push(-1);
      if (cnt != 0) st.push(cnt);

    } else {
      st.push(0);
    }
  }

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


Measured memory_bytes: 2312
def solve():
    n, l = map(int, input().split())
    tastes = [l + i for i in range(n)]
    if 0 in tastes:
        return sum(tastes)
    elif all([t > 0 for t in tastes]):
        return sum(tastes) - min(tastes)
    elif all([t < 0 for t in tastes]):
        return sum(tastes) - max(tastes)


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m,x,ans;
cin>>n>>m>>x;
  int a[105];
  for(int j = 0; j<m; j++){
      cin>>a[j];
  }
  int count = 0;
    for(int i = 1; i<x; i++){
       for(int j = 0; j<m; j++){
          if(i == a[j]){
             count++;
           }
        }
    }
  
  int count2 = 0;
  
  for(int i = x; i<n; i++){
      for(int j = 0; j<m; j++){
         if(i == a[j]){
             count2++;
         }
      }
   }
  ans = min(count,count2);
  cout<<ans<<endl;
  return 0;
}
  
  

Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N=sc.nextInt(),A[]=new int[N],Ma=0;
        for(int i=0;i<N;i++){
            int t=sc.nextInt(),n=0;
          	if(t%2==1){
              	Ma=0;
              	break;
            }
            while(t%2==0){
                n++;
                 t/=2;
            }
            if(Ma==0&&n!=0){
                Ma=n;
            }
            else{
                Ma=Math.min(n,Ma);
            }
        }
        System.out.println(Ma);
    }
}

Measured memory_bytes: 35940
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n,x;
    scanf("%d%d", &n,&x);
    int l=0;
    int i,d=0,ans=0;
    if(x>0){ans++;}
    for(i=0;i<n;i++){
        scanf("%d",&l);
        if(d+l<=x){
            ans++;
        }
        d = d+l;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
/**
*
* Author: MARS
* Lang: GNU C++14
*
**/

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

#define F first
#define S second
#define ii pair < int , int >
#define LS pair < ll , string >

typedef unsigned long long ull;
typedef long double ldbl;
typedef long long ll;
typedef double dbl;

const ldbl E = 2.71828182845904523536;
const ldbl pi = acos(-1);
const dbl eps = 1e-9;
const ll mod = 1e9+7;
const ll inf = 1LL<<30;

/** /////////// ** Code ** /////////// **/

const int N=100100;

int main()
{
    ll x,y,z,k;
    cin>>x>>y>>z>>k;
    ll ans=y-x;
    if(!(k&1)) ans*=-1;
    cout<<ans;
    return 0;
}


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

using namespace std;

int main(){
  vector<long long> a (2);
  int k;
  cin >> a[0] >> a[1] >> k;
  for(int i = 0; i < k; i++){
    a[i%2] = (int)(a[i%2]/2);
    a[(i+1)%2] += a[i%2];
  }
  cout << a[0] << " " << a[1] << endl;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
a=list(map(int,input().split()))
c=0
d={}
d[1]=0
dd={}
dd[0]=1
now=1
while True:
    now=a[now-1]
    c+=1
    if now in d:
        break
    d[now]=c
    dd[c]=now
s=d[now]
if k<=s:
    print(dd[k])
    exit()
p=c-s
k-=s
k%=p
k+=s
print(dd[k])


Measured memory_bytes: 142820
N,M = gets.chomp.split.map(&:to_i)
a = readlines.map(&:chomp).map(&:to_i)
dp = [1] * (N+1)
a.each{|x| dp[x] = -1}
dp[1] = 0 if dp[1] == -1
mod = 1000000007

for i in 0..(N-2) do
    if dp[i+2] != -1
        dp[i+2] = (dp[i+1] + dp[i]) % mod
    else
        dp[i+2] = 0
    end
end

p dp[N]

Measured memory_bytes: 14076
import java.util.*;

public class Main {
	static int[] cycle, dm;
	static int enday;
	static int[][][] memo;

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

		while(true){
			int n = sc.nextInt();
			if(n == 0) break;

			cycle = new int[n];
			for(int i=0;i<n;i++) cycle[i] = sc.nextInt();

			int m = sc.nextInt();
			dm = new int[104];
			enday = Integer.MIN_VALUE;
			for(int i=0;i<m;i++) {
				int D = sc.nextInt(), M = sc.nextInt();
				if(dm[D-1] != 0) dm[D-1] = Math.min(dm[D-1], M);
				else dm[D-1] = M;
				enday = Math.max(enday, D);
			}

			memo = new int[enday][cycle.length][100];
			for(int i=0;i<enday;i++){
				for(int j=0;j<cycle.length;j++){
					Arrays.fill(memo[i][j], Integer.MAX_VALUE);
				}
			}

			System.out.println(solve(0,0,0));
		}
	}

	private static int solve(int day,int ci,int count){
		if(day == enday) return count;
		if(memo[day][ci][count] != Integer.MAX_VALUE) return memo[day][ci][count];

		int res = Integer.MAX_VALUE;

		if(dm[day] == 0 || cycle[ci] <= dm[day])
			res = Math.min(res, solve(day+1,(ci+1)%cycle.length,count));

		res = Math.min(res, solve(day+1,1%cycle.length,count+1));
		
		return memo[day][ci][count] = res;
	}
}

Measured memory_bytes: 15000
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[n];
    for (int i=0; i<n; i++){
        cin >> a[i];
    }
    for (int i=0; i<n; i++){
        int j=i-1;
        int v=a[i];
        while (j>=0 && a[j]>v){
            a[j+1]=a[j];
            j--;
            a[j+1]=v;
        }
    
        for (int i=0; i<n; i++){
            if (i==n-1){
                cout << a[i] <<endl;
            }
            else {
                cout << a[i] << " "  ;
            }
        }
    }
}


Measured memory_bytes: 3024
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(),(x).end()
typedef long long int ll;
using namespace std;
int r, s, p;
int scoreto(char c){
  if(c == 'r'){
    return p;
  }else if(c == 's'){
    return r;
  }else if(c == 'p'){
    return s;
  }
}
int main()
{
  int n, k;
  cin >> n >> k >> r >> s>> p;
  string t;
  cin >> t;
  int ans = 0;
  REP(i,k){
    string tmp;
    for(int j = 0;j < n/k + 1;j++){
      if(i + j*k < n){
	tmp = tmp + t[i + j*k];
      }else{break;}
    }
    // cout << "i = " << i << ", tmp = " << tmp << endl;
    int lentmp = tmp.size();
    REP(j,lentmp){
      int cont = 0;
      int num = 1;
      char token = tmp[j];
      while(true){
	if(tmp[j + 1] == token){
	  j++;
	  num++;
	}else{break;}
      }
      ans += (num - num/2)*scoreto(token);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 696
n,m=map(int,raw_input().split())
A=[raw_input() for j in range(n)]
B=[raw_input() for j in range(m)]
def sub(ox,oy):
  for x in xrange(m):
    for y in xrange(m):
      if A[ox+x][oy+y] != B[x][y]:
        return False
  return True
def match():
  for x in xrange(n-m+1):
    for y in xrange(n-m+1):
      if sub(x,y): return True
  return False
if match():
  print 'Yes'
else:
  print 'No'
    

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

int main(){
	int n, m;
  	cin >> n >> m;
  	dsu d(n); //atcoderのライブラリ(union-find)
  
  	rep(i, m){
    	int a, b;
      	cin >> a >> b;
      	a--; b--;
      	
      	d.merge(a, b);
    }
  
  	//int cnt = d.groups().size();
  	int cnt = 0;
  	rep(i, n) if(d.leader(i) == i) cnt++;
  	
  	cout << cnt-1 << endl;
}

Measured memory_bytes: 3828
#include <iostream>

using namespace std;

int main(){
    int a,b,c,uno,dos,tres;
    cin>>a>>b>>c;
    if(a>=b && a>=c){
        uno = a;
        if(b>=c){
            dos = b;
            tres = c;
        }
        else{
            dos = c;
            tres = b;
        }
    }
    else if(b>=a && b>=c){
        uno = b;
        if(a>=c){
            dos = a;
            tres = c;
        }
        else{
            dos = c;
            tres = a;
        }
    }
    else{
        uno = c;
        if(b>=a){
            dos = b;
            tres = a;
        }
        else{
            dos = a;
            tres = b;
        }
    }
    cout<<tres<<" "<<dos<<" "<<uno<<endl;
}


Measured memory_bytes: 3092
// abc169_d
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF (ll)(1e9)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;


map<ll, int> factorize(ll n){
    ll tmp = n;
    map<ll, int> res;
    for (ll a = 2; a * a <= n; a++) { int cnt = 0; while (tmp % a == 0){ cnt++; tmp /= a; } if (cnt > 0) res[a] = cnt; }
    if (tmp > 1) res[tmp] = 1;
    return res;
}

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    ll N;
    cin >> N;

    auto fac = factorize(N);
//    print(fac);

    ll ans = 0;
    for (auto e: fac){
        ll p = e.first;
        ll x = e.second;

        if (p == 1) continue;

        ll tmp = 0;
        int i = 1;
        while (true) {
            if (tmp + i <= x) {
                tmp += i;
                i++;
            } else {
                break;
            }
        }
        ans += i-1;
    }

    print(ans);

    return 0;
}


Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b){
    if(b == 0)
        return a;
    return gcd(b, a % b);
}

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

int main(){
    long long a, b;
    cin >> a >> b;
    cout << lcm(a, b) << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
using namespace std;
#define N 100500
#define mod 1000000007
int n,nt[N],su[N],nt2[N][3],as,dp[N];
char s[N];
int main()
{
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=1;i<=n;i++){su[i]=(su[i-1]+s[i]-'a'+1)%3;}
	nt[n+1]=n+1;nt2[n+1][0]=nt2[n+1][1]=nt2[n+1][2]=n+1;
	for(int i=n;i>=0;i--)
	{
		nt[i]=nt[i+1];nt2[i][0]=nt2[i+1][0];nt2[i][1]=nt2[i+1][1];nt2[i][2]=nt2[i+1][2];
		if(s[i]==s[i+1])nt[i]=i+1;
		nt2[i][su[i+1]]=i+1;
	}
	dp[0]=1;
	for(int i=0;i<=n;i++)
	{
		int tp=nt[i]-1;
	//	if(nt[tp]==n+1)tp=n;
		if(s[i+1]=='a')dp[nt2[tp][(2+su[i])%3]]=(dp[nt2[tp][(2+su[i])%3]]+dp[i])%mod;else dp[i+1]=(dp[i+1]+dp[i])%mod;
		if(s[i+1]=='b')dp[nt2[tp][(1+su[i])%3]]=(dp[nt2[tp][(1+su[i])%3]]+dp[i])%mod;else dp[i+1]=(dp[i+1]+dp[i])%mod;
		if(!(su[n]-su[i])%3&&i)as=(as+dp[i])%mod;
	}
	if(nt[0]==n+1)as=1;
	printf("%d\n",as);
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
#define YN(x)         cout << ((x) ? "YES" : "NO") << endl
#define Yn(x)         cout << ((x) ? "Yes" : "No") << endl
#define yn(x)         cout << ((x) ? "yes" : "no") << endl
#define absi(x)       ( ((x) >= 0) ? (x) : (-(x)) )
#define debugvec(v)   rep(i, v.size()) cerr << "L" << __LINE__ << ": " << #v << "[" << i << "] = " << v[i] << endl;
#define debugvec2(v)  cerr << "L" << __LINE__ << ": " << #v << " = { "; rep(i, v.size()) cerr << v[i] << (i + 1 == v.size() ? "" : ", "); cerr << " }" << endl;
typedef long long ll;  // 10^18 くらいまでいける

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

const ll INF = 1LL << 60;

int main(){
  int m1, d1, m2, d2;

  cin >> m1 >> d1;
  cin >> m2 >> d2;

  if (m2 == m1+1)
    cout << "1" << endl;
  else
    cout << "0" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define vec vector<ll>
#define pb push_back
#define vecit vector<ll>::iterator
#define vecp vector<pair<ll,ll> >
#define vecpit vector<pair<ll,ll> >::iterator
#define mapp map<ll,ll>
#define mapit map<ll,ll>::iterator
#define mod 1000000007
#define db double
using namespace std;
int main()
{
    ll n;
    cin>>n;
    map<string,ll>s;
    while(n--)
    {
        string x;
        cin>>x;
        s[x]++;
    }
    cout<<"AC x "<<s["AC"]<<"\n";
    cout<<"WA x "<<s["WA"]<<"\n";
    cout<<"TLE x "<<s["TLE"]<<"\n";
    cout<<"RE x "<<s["RE"]<<"\n";
}


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

int main() {
  int H, W, K; cin >> H >> W >> K;
  K--; // 0-indexed

  /* dp[h][x] : 横線がh段で、最終的に縦棒1から縦棒xにたどり着くあみだくじの数 */
  vector<vector<long long>> dp(H+1, vector<long long>(W));
  dp[0][0] = 1;

  for (int h = 0; h < H; h++) {
    /* hからh+1に行くときの横棒の置き方を全探索 */
    for (int b = 0; b < (1 << (W - 1)); b++) {
      
      /* isOK : 横棒が隣り合わない？ */
      bool isOK = true;
      for (int i = 0; i < W - 2; i++) {
        if ((b >> i) % 4 == 3) isOK = false;
      }
      if (!isOK) {
        continue;
      }

      /* 横棒を置いて位置をswap */
      int perm[W];
      for (int i = 0; i < W; i++) {
        perm[i] = i;
      }
      for (int i = 0; i < W - 1; i++) {
        if ((b >> i) & 1) {
          swap(perm[i], perm[i+1]);
        }
      }

      /* 配る */
      for (int i = 0; i < W; i++) {
        dp[h+1][perm[i]] += dp[h][i];
        dp[h+1][perm[i]] %= MOD;
      }
    }
  }
  cout << dp[H][K] << endl;
}

Measured memory_bytes: 256
/**************************************************************************
Coded by: Saba Karimi(_VINTAGE)
Institution: AIT PUNE
***************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back 
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define ld long double
#define int long long int 
#define F first 
#define S second
/**************************************************************************/
const int N = 1e5+2;
signed main()
{
    fast;
    int n,m;
    cin>>n>>m;
    vector<int> adj[n+1];
    int indegree[n+1]={};
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        indegree[v]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(indegree[i]==0)
            q.push(i);
    }
    int dp[n+1]={};
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto it:adj[u])
        {
            indegree[it]--;
            if(indegree[it] == 0)
            {
                dp[it] = max(dp[u]+1,dp[it]);
                q.push(it);
            }
        }
    }
    int mx = 0;
    for(int i=1;i<=n;i++)
        mx = max(dp[i],mx);
    cout<<mx;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()
#define all(arr) arr.begin(), arr.end()

using namespace std;

int main() {
  vector<int> v(5);
  for (auto &e : v) cin >> e;
  int k;
  cin >> k;

  for (int i = 0; i < 4; ++i) {
    for (int j = i + 1; j < 5; ++j) {
      if (abs(v.at(i) - v.at(j)) > k) {
        puts(":(");
        return 0;
      }
    }
  }

  puts("Yay!");

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

int main()
{
  int N;
  std::string S;
  std::cin >> N;
  std::cin >> S;
  if (N%2==0) {
    bool flg = true;
    for (int i=0; i<N/2; i++) {
      if (S[i] != S[N/2+i]) {
        flg = false; break;
      }
    }
    if (flg) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
  }
  else std::cout << "No" << std::endl;
  return 0;
}

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

#define rep(i, n) REP(i, 0, n)
#define REP(i,k,n) for(int i = k; i < n; i++)
#define mmax(start, end) *max_element(start, end)
#define mmin(start, end) *min_element(start, end)
#define argmax max_element
#define argmin min_element
#define push push_back
#define pop pop_back
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef string str;

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

template<class T = ll> T in() {
    T _in;
    cin >> _in;
    return _in;
}

int dp[1001][1001];

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

    string s[2];
    int len[2];
    rep(i, 2) {
        cin >> s[i];
        len[i] = s[i].size();
    }

    // 表埋め
    rep(i, len[0]+1) {
        dp[i][0] = i;
    }
    rep(j, len[1]+1) {
        dp[0][j] = j;
    }

    REP(i, 1, len[0]+1) {
        REP(j, 1, len[1]+1) {
            // if(i==2 && j==1) {
            //     cout << s[0][i-1] << " " << s[1][j-1] << endl;
            // }
            int top_left = dp[i-1][j-1];
            if(s[0][i-1] != s[1][j-1]) {
                top_left++;
            }
            int top = dp[i-1][j] + 1;
            int left = dp[i][j-1] + 1;
            dp[i][j] = min(top, min(top_left, left));
        }
    }

    // rep(i, len[0]+1) {
    //     rep(j, len[1]+1) {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << endl;

    cout << dp[len[0]][len[1]] << endl;

    return 0;
}



Measured memory_bytes: 7108