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

using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
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; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

int main(){
    string s;
    cin>>s;
    if(s[0]!='k'){
        for (int i = 0; i < s.size(); i++)
        {
            if(s.substr(s.size()-7,7)=="keyence"){
                cout<<"YES"<<endl;
                return 0;
            }
        }
        cout<<"NO"<<endl;
        
    }
    else{
        for (int i = 0; i <= 7; i++)
        {
            string t=s.substr(0,i)+s.substr(s.size()-7+i,7-i);
            if(t=="keyence"){
                cout<<"YES"<<endl;
                return 0;
            }
        }
        cout<<"NO"<<endl;
        

    }
   
    



    return 0;
}
                  

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

#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i, a, b) for (int i = (a) ; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define sp system("pause")
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;

void TimeExecution() {
    cout << "\n\n===>> Time Execution: " << clock() / (double)1000 << " sec(s).";
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    /*
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    */
    string s;
    cin >> s;
    s = " " + s;
    bool ok = 1;
    FOR(i, 1, s.size() - 1)
    {
        if(i & 1)
        {
            if(s[i] != 'R' && s[i] != 'U' && s[i] != 'D')
            {
                ok = 0;
                break;
            }
        }
        if((i & 1) == 0)
        {
            if(s[i] != 'L' && s[i] != 'U' && s[i] != 'D')
            {
                ok = 0;
                break;
            }
        }
    }
    if(ok) cout << "Yes";
    else cout << "No";
    return 0;
}


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

#define ff first
#define ss second
#define mp make_pair

using namespace std;

typedef long long ll;

char s[200005];
char t[200005];

int main(){
	int n;

	scanf("%d %s %s", &n, s,t);
	
	for(int i = 0; i < n; i++)
		printf("%c%c", s[i], t[i]);

	printf("\n");


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
#define MAX 1001
#define INF 9999999

int sta_c[MAX+1][MAX+1],sta_t[MAX+1][MAX+1],cc[MAX],tt[MAX];
int n,m,a,b,c,t,k,p,q,r,mc,mt,nc,nt;
bool visit_c[MAX],visit_t[MAX];

int dijkstra(int s,int g,int ct){
    fill(cc,cc+MAX,INF); fill(visit_c,visit_c+MAX,false);
    fill(tt,tt+MAX,INF); fill(visit_t,visit_t+MAX,false);
    
    tt[s] = cc[s] = 0;
    while(true){
        mt = mc = INF;
        for(int i = 1 ; i <= m ; i++){
            if(cc[i] < mc && !visit_c[i]){
                mc = cc[i];
                nc = i;
            }
            if(tt[i] < mt && !visit_t[i]){
                mt = tt[i];
                nt = i;
            }
        }
        
        if(mc == INF && !ct) break;
        if(mt == INF && ct) break;
        
        visit_c[nc] = visit_t[nt] = true;
        
        for(int j = 1 ; j <= m ; j++){
            if(sta_c[nc][j]+cc[nc] < cc[j] && sta_c[nc][j] != INF){
                cc[j] = sta_c[nc][j]+cc[nc];
            }
            if(sta_t[nt][j]+tt[nt] < tt[j] && sta_t[nt][j] != INF){
                tt[j] = sta_t[nt][j]+tt[nt];
            }
        }
    }
    
    if(ct) return tt[g];
    return cc[g];
}

int main(){
    while(cin >> n >> m , n+m){
        fill(sta_c[0],sta_c[MAX],INF);
        fill(sta_t[0],sta_t[MAX],INF);
        while(n--){
            cin >> a >> b >> c >> t;
            
            sta_t[a][b] = sta_t[b][a] = t;
            sta_c[a][b] = sta_c[b][a] = c;
        }
        cin >> k;
        while(k--){
            cin >> p >> q >> r;
            cout << dijkstra(p,q,r) << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 9008
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const ll mod = 1000000007LL;
const ll limit = 10000000LL;

ll S, i, j, p, act, aux;
ll last, sols;

ll pows[11];

ll poww(ll a, ll b) {
    ll ans = 1;

    while (b > 0) {
        if (b & 1) ans = (ans * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }

    return ans;
}

ll cnt(ll x) {
    ll pin = 0;

    while (pows[pin] <= x) pin++;

    last = pin;
    return pin;
}

void check(ll len) {
    if (len > aux) return;

    ll val = S / len;
    ll cnt = poww(10, val) - poww(10, val - 1) + mod;
    sols += cnt - len + 1 + mod;
    sols += mod - 1;
    sols %= mod;
}

int main()
{
    //freopen("test.in","r",stdin);

    scanf("%lld", &S);

    pows[0] = 1;
    for (i = 1; i <= 10; i++) pows[i] = pows[i - 1] * 10LL;

    act = 0;
    while (act + cnt(p + 1) <= S) {
        act += last;
        p++;
    }

    for (i = 1; i < limit; i++) {
        if (act + cnt(p + 1) <= S) {
            act += last;
            p++;
        }

        if (act == S) {
            sols++;

            /*act = 0;
            for (j = i; j <= p; j++) act += cnt(j);
            if (act != S) sols--;*/
        }
        if (act == 0) break;
        act -= cnt(i);
    }

    aux = S / 8;
    sols += aux;

    for (ll d = 1; d * d <= S; d++) {
        if (S % d) continue;
        check(d);
        if (d * d != S) check(S / d);
    }

    printf("%lld", sols);

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define INF 1000000007
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2)*pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int jo(int n) {
	int ans = 1;
	rep(i, n) {
		ans *= 2;
	}
	return ans;
}

signed main() {
	int a, b, c;
	cin >> a >> b >> c;
	for (int i = a; i <= b; i++) {
		if (i - a < c || b - i < c) {
			cout << i << endl;
		}
	}
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100000
typedef struct{
  int parent,left,right;
}Node;

Node T[MAX];
int n,dep[MAX];

void print(int value){
  int i,j;
  printf("node %d: parent = %d, depth = %d, ",value,T[value].parent,dep[value]);

  if(T[value].parent==-1)printf("root, ");
  else if(T[value].left==-1)printf("leaf, ");
  else printf("internal node, ");

  printf("[");
  for(i=0,j=T[value].left;j!=-1;i++,j=T[j].right){
    if(i>0)printf(", ");
    printf("%d",j);
  }
  printf("]\n");
}

void setdep(int value,int p){
  dep[value]=p;
  if(T[value].right!=-1)setdep(T[value].right,p);
  if(T[value].left!=-1)setdep(T[value].left,p+1);
}
int main(){
  int i,j,id,k,c,left,right;
  scanf("%d",&n);
  for(i=0;i<n;i++)T[i].parent=T[i].left=T[i].right=-1;
  for(i=0l;i<n;i++){
    scanf("%d%d",&id,&k);
      for(j=0;j<k;j++){
	scanf("%d",&c);
	if(j==0)T[id].left=c;
	else T[left].right=c;
	left=c;
	T[c].parent=id;
      }
  }
  for(i=0;i<n;i++){
    if(T[i].parent==-1)right=i;
  }
  setdep(right,0);
  for(i=0;i<n;i++)print(i);
  return 0;
}

      



Measured memory_bytes: 6380
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
#include <set>
#include <tuple>

template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

// [l, r) from l to r
struct range {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr range(int l_, int r_): l(std::min<int>(l_, r_)), r(r_) {}
  constexpr itr begin() const { return l; }
  constexpr itr end() const { return r; }
};

// [l, r) from r to l
struct revrange {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr r, l;
  constexpr revrange(int l_, int r_): r(std::max<int>(l_, r_) - 1), l(l_ - 1) {}
  constexpr itr begin() const { return r; }
  constexpr itr end() const { return l; }
};

template <class T>
inline T scan() {
  T res;
  std::cin >> res;
  return res;
}

int main() {
  std::set<int> a;
  for (int i: range(0, 3)) {
    int x;
    std::cin >> x;
    a.insert(x);
  }
  std::cout << (a.size() == 2 ? "Yes" : "No") << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <time.h>
#define first fi
#define second se


using namespace std;

typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int>  P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp(db a,db b){ return sign(a - b);}
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) {  if(b & 1) res *= a,res %= c;  a *= a,a %= c,b >>= 1;  }  return res;}
ll phi(ll x) {  ll res = x;  for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = x / i * (i - 1);   while(x % i == 0) x /= i;   }  if(x > 1) res = res / x  * (x - 1);    return res;}
ll c,n,k;
int main() {
    ios::sync_with_stdio(false);
    ll a,b;
    while(cin >> a >> b >> k){
        cout << min(b / a,k) << endl;
    }
    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}



Measured memory_bytes: 256
import sys
input = sys.stdin.readline
n, ma, mb = map(int, input().split())
inf = 10000
med = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[[inf] * 401 for _ in range(401)] for _ in range(n+1)]
dp[0][0][0] = 0
for k in range(n):
    for i in range(401):
        for j in range(401):
            a, b, c = med[k]
            if i - a >= 0 and j - b >= 0:
                dp[k+1][i][j] = min(dp[k][i][j], dp[k][i-a][j-b] + c)
            else:
                dp[k+1][i][j] = dp[k][i][j]

ans = inf
for k in range(1, 401):
    if k * ma > 400 or k * mb > 400:
        break
    x, y = k * ma, k * mb
    ans = min(ans, dp[n][x][y])

print(-1 if ans == inf else ans)


Measured memory_bytes: 98012
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define pb push_back 
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
typedef long long ll;
const int INF = 100000000, mod = 1000000007;
const ll LLINF = 1LL << 50;
using namespace std;


int main() {
    ll n, k, ans = 0;
    cin >> n >> k;
    if (n <= k)cout << '0' << endl;
    else {
        for (int i = k + 1; i <= n; i++) {//b
            int routine = i - k;
            int t;
            if (k==0)t = ((n+1) / i)*routine + (n + 1) % i - 1;
            else if((n+1)%i<k)t= ((n+1) / i)*routine;
            else t = ((n + 1) / i)*routine + (n + 1) % i - k;
            ans += t;
        }
        cout << ans << endl;
    }
    return 0;
}


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

int main(){
    
    int n;
    string taro, hanako;
    int scoT=0;
    int scoH=0;
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        cin >> taro >> hanako;
        if( taro > hanako){
            scoT += 3;
        }else if(hanako > taro){
            scoH += 3;
        }else{
            scoT +=1;
            scoH +=1;
        }
    }
    
    cout << scoT << " " << scoH << endl;
    
    return 0;
}


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

int main() {
    string s;
    cin >> s;
    string res = "Yes";
    for(int i = 0;i < s.size() / 2;i++){
        if(s[i] != s[s.size() - i - 1]){
            res = "No";
            break;
        }
    }
    for(int i = 0; i < s.size() / 4; i++){
        if(s[i] != s[s.size() / 2 - i - 1]){
            res = "No";
            break;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
a = gets.to_i
puts [11,31,41,61,71,101,131,151,181,191,211,241,251,271,281,311,331,401,421,431,461,491,521,541,571,601,631,641,661,691,701,751,761,811,821,881,911,941,971,991,1021,1031,1051,1061,1091,1151,1171,1181,1201,1231,1291,1301,1321,1361,1381][0...a]*' '

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

using namespace std;

const int maxn = 300100;

int n,a,b,ans[maxn];

int main() {
  //  freopen("in.txt","r",stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>a>>b;
    if ((n<a+b-1) || (n > 1ll*a*b)) cout<<-1;
    else {
        int cur = n;
        for (int i=b;i>=1;i--) {
            if (cur-a > i-1) {
                for (int j=cur-a+1;j<=cur;j++) cout<<j<<" ";
                cur-=a;
            } else {
                for (int j=i;j<=cur;j++) cout<<j<<" ";
                cur=i-1;
                break;
            }
        }
        for (int i=cur;i>=1;i--) cout<<i<<" ";
    }
}


Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF (2e9)
#define EPS (1e-7)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
    int x, y;
    cin >> x >> y;

    cout << x + y/2 << endl;
}

Measured memory_bytes: 256
// SeeAlso: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define MAX 100000
#define NIL -1
#define MOD 1000000007

typedef int _loop_int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define debug(x) cout<<#x<<": "<<x<<endl
#define debig_vec(v) cout<<#v<<":";rep(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) rep(i, h) { rep(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> inline void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> inline void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const long long INF = 1LL<<60;

int main() {
    char s; cin >> s;
    if(isupper(s)) {
        print("A"); 
    } else {
        print("a");
    }
    return 0;
}


Measured memory_bytes: 3672
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pb push_back
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
#define ford(b,a) for(int i=b;i>=a;i--)
typedef pair<int, int> pi;
#define PI 3.14159265359
#define vi vector<int>
long long mod=1000000007;
//int count=INT_MAX;
 
struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int testcases=1;
    //cin>>testcases;
    //cout<<t;
    //scanf("%d",&t);
    //int t=testcases;
    while(testcases--){
        double d,t,s;
        cin>>d>>t>>s;
        if(d/s>t){
            cout<<"No\n";
        }
        else{
            cout<<"Yes\n";
        }
    }               

    return 0;
}

Measured memory_bytes: 3716
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<tuple>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int main() {
	int n;
	cin >> n;
	cout << 800 * n - (n / 15) * 200 << endl;
	return 0;
}


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

#define PI 3.14159265359
int main(void){
    // Your code here!
    int a,b,x;
    float theta;
    scanf("%d %d %d\n",&a,&b,&x);
    //printf("%d,%d\n",2*x,a*a*b);
    if(2*x>=a*a*b)
        theta = 90-atan2((float)a*a*a,(float)2*a*a*b-2*x) * 180 / PI;
    else
        theta = 90-atan2((float)2*x,(float)b*b*a) * 180 / PI;
    printf("%f\n",theta);
    return 0;
}


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


int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n,k;
  cin>>n>>k;
  int a[n];
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  int dp[n];
  dp[0]=0;
  dp[1]=abs(a[1]-a[0]);
  for(int i=2;i<n;i++){
     dp[i]=abs(a[i]-a[i-1])+dp[i-1];
     for(int j=max(0,i-k);j<=i-2;j++){
      dp[i]=min(dp[i],abs(a[i]-a[j])+dp[j]);
     }
  }
  cout<<dp[n-1]<<endl;




}

Measured memory_bytes: 4392
H, W = map(int, input().split())
table = []
table.append(list("_" * (W + 2)))
for _ in range(H):
    table.append(list("_" + input() + "_"))
table.append(list("_" * (W + 2)))

for h in range(1, H + 1):
    for w in range(1, W + 1):
        if table[h][w] == "#":
            continue
        count = 0
        for _h in [-1, 0, +1]:
            for _w in [-1, 0, +1]:
                if table[h + _h][w + _w] == "#":
                    count += 1
        table[h][w] = str(count)

for h in range(1, H + 1):
    print("".join(table[h]).replace("_", ""))


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

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

namespace ae86
{
	const int bufl = 1<<15;
	
	char buf[bufl],*s=buf,*t=buf;
	
	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}
	
	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 100007 , __ = _<<1;

int to[__],ne[__],he[_]={0},ecnt=1;
inline void adde(int a,int b){to[++ecnt]=b,ne[ecnt]=he[a],he[a]=ecnt;}
inline void addde(int a,int b){adde(a,b),adde(b,a);}

int n,m,dep[_]={0},du[_]={0};
vector<pair<int,int>> ans;

void dfs(int x,int ff)
{
	dep[x]=dep[ff]+1;
	for(int i=he[x];i;i=ne[i])
	{
		int b=to[i];
		if(b==ff)continue;
		if(!dep[b])dfs(b,x);
		else if(dep[b]<dep[x])ans.emplace_back(x,b),du[x]++;
	}
	if(du[x]&1)du[x]++,ans.emplace_back(x,ff);
	else if(ff)du[ff]++,ans.emplace_back(ff,x);
}

int main()
{
	n=ty(),m=ty();
	for(int i=1,a,b;i<=m;i++)a=ty(),b=ty(),addde(a,b);

	if(m&1){puts("-1");return 0;}
	dfs(1,0);
	for(auto i:ans)printf("%d %d\n",i.first,i.second);

	return 0;
}


Measured memory_bytes: 9716
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

int main(void){
  ll s;
  cin >> s;
  
  map<ll, ll> m;
  m[s] = 1;

  int n = 1;
  while (true){
    n++;
    if (s % 2)
      s = 3 * s + 1;
    else
      s = s / 2;

    if (m[s] != 0){
      break;
    }
    m[s] = 1;
  }

  cout << n << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
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;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long,long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

int main() {
    int a; cin >> a;
    cout << a + a*a + a*a*a << endl;
}

Measured memory_bytes: 3620
#include <stdio.h>
#include <stdlib.h>
int comp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}
int main() {
  int n,a[100000],ans=0,c=1,i;
  scanf("%d",&n);
  for (i=0; i<n; i++) {
    scanf("%d",&a[i]);
  }
  qsort(a, n, sizeof(int), comp);
  for (i=0; i<n; i++) {
    if (a[i]==a[i+1]) {
      c++;
    } else {
      if (c<a[i]) {
        ans+=c;
      } else if (c>a[i]) {
        ans+=c-a[i];
      }
      c=1;
    }
  }
  printf("%d\n",ans);
  return 0;
}


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

using namespace std;

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

const int MM = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e6 + 10;

int n, m;

void prework(){

}

void read(){

}

ll a[MAXN], b[MAXN];

void solve(int casi){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%lld%lld", &a[i], &b[i]);
	ll tot = 0;
	ll ans = 0;
	for(int i = n; i >= 1; i--){
		if ((tot + a[i]) % b[i] != 0){
			ll tmp = b[i] - (tot + a[i]) % b[i];
			tot += tmp;
			ans += tmp;
		}
	}
	printf("%lld\n", ans);
}

void printans(){

}


int main(){
	prework();
	int T = 1;
//	cin>>T;
	for(int i = 1; i <= T; i++){
		read();
		solve(i);
		printans();
	}
	return 0;
}




Measured memory_bytes: 1792
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef ll Def;
//typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int n;
	cin>>n;
	vp in(n);
	rep(i,n)in[i].second=i;
	rep(i,n)cin>>in[i].first;
	sort(all(in));
	int out=0;
	rep(i,n)if((in[i].second-i)%2)out++;
	cout<<out/2<<endl;
}
// 2 4 3 1
// 3 0 2 1



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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int H,W;
string S[222];

int dp[2][1<<16];
int pc[1<<16];
signed main(){
    cin.tie(0);ios_base::sync_with_stdio(0);

    for(int i=0;i<1<<16;i++)pc[i]=__builtin_popcount(i);
    cin>>H>>W;
    S[0]="";
    rep(i,H)cin>>S[i+1];

    fill_n(*dp,2*(1<<16),INT_MIN);
    dp[0][0]=0;
    int mask=(1<<W)-1;
    for(int t=0;t<H*W;t++){
            int i=t/W;
            int j=t%W;
            for(int k=0;k<(1<<W);k++){
                if(dp[t&1][k]==INT_MIN)continue;
                chmax(dp[(t+1)&1][(k<<1)&mask],dp[t&1][k]);

                int l=pc[k&((1<<j)-1)];
                if(l<S[i+1].size()){
                    int po=0;
                    if(j&&(k&1)&&S[i+1][l]==S[i+1][l-1])po++;
                    if(k>>(W-1)&1){
                        int m=S[i].size()-pc[k]+l;
                        if(S[i][m]==S[i+1][l])po++;
                    }
                    chmax(dp[(t+1)&1][((k<<1)&mask)+1],dp[t&1][k]+po*2);
                }
                dp[t&1][k]=INT_MIN;
            }

        if(j==W-1)for(int k=0;k<1<<W;k++)if(pc[k]!=S[i+1].size())dp[(t+1)&1][k]=INT_MIN;
    }

    int ans=INT_MIN;
    rep(i,1<<W)chmax(ans,dp[(H*W)&1][i]);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4716
#define _USE_MATH_DEFINES
#include <iostream>
#include <math.h>
#include <climits>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <map> 
#include <set>
#include <string>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MD = 1000000007;

/* sample input

*/

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

	int answer = 1;
	int num = 1;
	for (int i = 0; i <= 5; i++) {
		num = 1;
		for (int j = 0; j <= i; j++) {
			num *= 2;
		}
		if (num <= n) {
			answer = num;
		}
		else {
			break;
		}
	}

	cout << answer;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>

using namespace std;

int main(void)
{
	int N;
	pair<double, double> town[8];
	int perm[8];
	double p = 1;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> town[i].first >> town[i].second;
		perm[i] = i;
		p *= (i + 1);
	}

	double ans = 0;
	do {
		for (int i = 1; i < N; i++) {
			double dx = town[perm[i]].first - town[perm[i - 1]].first;
			double dy = town[perm[i]].second - town[perm[i - 1]].second;
			ans += (sqrt(pow(dx, 2.0) + pow(dy, 2.0)));
		}
	} while (next_permutation(perm, perm + N));
	

	printf("%.9f\n", ans / p);

	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(final String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		if (n % 1000 == 0) {
			System.out.println(0);
		}else {
			System.out.println(1000 - n % 1000);
		}
	}
}


Measured memory_bytes: 35756
#include<stdio.h>
  #include<string.h>
  #define LEN 100005

  typedef struct pp{
    char name[100];
    int t;
  }P;
  P Q[LEN];
  int head,tail,n;
  void enq(P x){
    Q[tail]=x;
    tail=(tail+1)%LEN;
  }
  P dequeue(){
    P x=Q[head];
    head=(head+1)%LEN;
    return x;
  }
  int min(int a,int b){
    if(a<b) return a;
    else return b;
  }
  int main(){
    int elaps=0,m,i,q;
    P u;
    scanf("%d %d",&n,&q);
    for(i=1;i<=n;i++){
      scanf("%s %d",Q[i].name,&Q[i].t);
    }
    head=1;
    tail=n+1;
    while(head != tail){
      u=dequeue();
      m=min(q,u.t);
      u.t -= m;
      elaps +=m;
      if(u.t>0) enq(u);
      else{
        printf("%s %d\n",u.name,elaps);
      }
    }
    return 0;
  }



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

int main() {
    int x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int x3, y3, x4, y4;
    x3 = y1 - y2 + x2;
    y3 = x2 - x1 + y2;
    x4 = y1 - y2 + x1;
    y4 = x2 - x1 + y1;
    cout << x3 <<" "<< y3 <<" "<< x4 <<" "<< y4 << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.ArrayDeque
import kotlin.Array
import kotlin.Boolean
import kotlin.Comparator
import kotlin.Int
import kotlin.Long
import kotlin.String

fun main(args: Array<String>) {
    val n = readInt()
    val a = readIntList()

    val q = ArrayDeque<Int>()

    for (i in 0 until n) {
        if (i % 2 == 0) q.addLast(a[i])
        else q.addFirst(a[i])
    }
    if (n % 2 != 0) {
        println(q.reversed().joinToString(separator = " "))
    } else {
        println(q.joinToString(separator = " "))
    }
}

// read
fun readString() = readLine()!!
fun readInt() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntList() = readLine()!!.split(" ").map(String::toInt)

Measured memory_bytes: 72160
#include <iostream>
#include <limits>
#include <cstdint>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <deque>
#include <stack>
#include <queue>
#include <utility> 
#include <iomanip>      // std::setprecision
using namespace std;
typedef long long int l1;
typedef long long unsigned int lu1;
typedef long double ld;
#define FIO std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// #define __gcd(a,b) __algo_gcd(a,b)
#define PI acos(-1.0)
#define pb push_back
// #define SORT(A) sort(A.begin(), A.end());
// #define REVERSE(A) reverse(A.begin(), A.end());
#define PrintArray(arr) for(int i=0;i<(int)arr.size();i++)cout<<arr[i]<<" ";cout<<endl;
#define pii pair<int,int>
#define pll pair<long long int , long long int>
#define puu pair<long long unsigned , long long unsigned>
const int MOD = 1e9+7;

int main()
{
    FIO;
    int t;
    t = 1;
    // cin>>t; 
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    for(int tc=0;tc<t;tc++)
    {   
        int n;
        cin>>n;
        vector<int> arr(n+1);
        for(int i1=1;i1<=n;i1++) cin>>arr[i1];
        vector<int> dp(n+2,0);
        dp[2] = abs(arr[2]-arr[1]);
        for(int i=3;i<=n;i++)
        {
            dp[i] = min(dp[i-2]+abs(arr[i]-arr[i-2]),dp[i-1]+abs(arr[i-1]-arr[i]));
        }
        // PrintArray(dp);
        cout<<dp[n]<<"\n";
    }
    return 0;
}

Measured memory_bytes: 1152
#include <stdio.h>

int e[101];

int main(void)
{
    int e1, e2, e3, e4;
    int i;

    scanf("%d%d%d%d", &e1, &e2, &e3, &e4);
    
    e[e1]++;
    e[e2]++;
    e[e3]++;
    e[e4]++;

    for (i = 1; i <= 100; i++){
        if (e[i] != 0 && e[i] != 2 && e[i] != 4){
            printf("no\n");
            return (0);
        }
    }

    printf("yes\n");
    return (0);
}
    



Measured memory_bytes: 2104
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N = iin()
a = iln()

count = 0
for i in range(1, N):
    if a[i-1] == a[i]:
        a[i] = 1000
        count += 1
print(count)



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

using namespace std;

int main(){
  string s;
  cin >> s;
  if(s[0] == 'a' ||s[0] == 'i' ||s[0] == 'u' ||s[0] == 'e' ||s[0] == 'o'){
    cout << "vowel" << endl;
  }
  else
    cout << "consonant" << endl;
}


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MAXN 100001

int gcd(int a, int b) {
    if(a < b) swap(a, b);
    if (b==0) return a;
    return gcd(b, a%b);
}

int main() {
    int a, p;
    cin >> a >> p;
    cout << (a*3 + p) / 2 << endl;
}



Measured memory_bytes: 256
#include <stdio.h>


int main(void)
{
    int weight[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
    int binary[10] = {0};
    int input, i, flag;

    while (scanf("%d", &input) != EOF){
        for(i = 0; i < 10; i++) binary[i] = 0;
        for(i = 0; i < 10; i++){
            binary[i] = input % 2;
            input /= 2;
            if(input == 0) break;
        }
        flag = 0;
        for(i = 0; i < 10; i++){
            if (binary[i] == 1 && flag == 0){
                flag = 1;
                printf("%d", weight[i]);
            }else if(binary[i] == 1 && flag == 1){
                printf(" %d", weight[i]);
            }
        
        }
        putchar('\n');
    }



    return (0);
}


Measured memory_bytes: 2104
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long[] a = new long[n + 1];
    a[0] = 2;
    a[1] = 1;
    for(int i = 2; i < n + 1; i++) {
      a[i] = a[i - 2] + a[i - 1];
    }
    System.out.println(a[n]);
  }
}

Measured memory_bytes: 21844
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <stack>
#include <queue>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <iomanip>
using namespace std;

#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define pb push_back

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

const int mod = 1e9 + 7;
const int mod2 = 998244353;

ll exp(ll taban, ll us, ll md) {
    ll carpan = taban % md;
	if(carpan == 0) return 0;
    ll temp = us;
    ll res = 1;
    while(temp){
        if(temp % 2) res = (res*carpan) % md;
        temp /= 2;
        carpan = (carpan*carpan) % md;
    }
    return res;
}
 
ll ebob(ll a, ll b){
    if(!a)return b;
    return ebob(b%a, a);
}

ll ekok(ll a, ll b){
    return (a*b)/ebob(a, b);
}

vector<ll> fact;
vector<ll> inv_fact;
void fact_init(int n){
	fact.resize(n+5);
	inv_fact.resize(n+5);
	fact[0] = inv_fact[0] = 1;
	for(int i = 1; i <= n; i++){
		fact[i] = (fact[i-1] * i) % mod;
		inv_fact[i] = exp(fact[i], mod-2, mod);
	}
}

ll komb(ll a, ll b){
	if(a < b) return 0;
	return fact[a] * (inv_fact[a-b] * inv_fact[b] % mod) % mod;
}

const int N = 5e3+5;

int main(){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	vector<int> vec(n);
	int top = 0;
	for(int i = 0; i < n; i++){
		cin>>vec[i];
		top ^= vec[i];
	}
	for(int i = 0; i < n; i++){
		cout<<(top ^ vec[i])<<" ";
	}
}

Measured memory_bytes: 3988
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll  pair <long long,long long>
#define ss second
#define ff first
#define inf 9223372036854775807
#define maa 1000000007
#define ld long double
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bug(x) cout << #x <<": " << x << '\n';
const ll N=200001 ;
int main()
{
   fast ;
   ll n ;
   cin>>n ;
   vector<ll>v(n) ;
   ll ans=0 ;
   for(ll i=0;i<n;i++) cin>>v[i] ;

   map<ll,ll>ma ;
   for(ll i=0;i<n;i++){
    ans+=ma[v[i]-i] ;
    ma[-i-v[i]]++ ;
   }
   cout<<ans ;

}



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

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; }

using ll = long long;
using lb = long double;
using P = pair<ll,ll>;
using graph = vector<vector<ll>>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  string S;
  cin>>S;
  int t = S.size();
  int ans = 0;
  rep(i,t-1){
    if(S[i+1]!=S[i]) ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3712
class Puzzle
  def initialize(state, direction, count=-1)
    @state = state
    @count = count
    @direction = direction
  end

  def calc_number
    nums = @state.dup
    @state.each_with_index do |x, i_x|
      @state[i_x..-1].each_with_index do |y, i_y|
        nums[i_x + i_y] -= 1 if y > x
      end
    end

    number = 0
    nums.each_with_index do |x, i_x|
      factorial = (nums.size - 1 - i_x).downto(1).inject(:*)
      number += factorial * x if factorial != nil
    end
    return number
  end

  def find_zero
    return @state.index(0)
  end

  def print_puzzle
    puts state[0..2].join(' ')
    puts state[3..5].join(' ')
    puts state[6..8].join(' ')
  end

  attr_accessor :state, :count, :direction
end

class Dictionary
  def initialize(num)
    @visited_dict = Array.new(num, 1)
    @count_dict = Array.new(num, 0)
  end

  attr_reader :visited_dict, :count_dict

  def visited?(index, direction)
    return @visited_dict[index] != 1 && @visited_dict[index] % direction == 0
  end

  def visit(puzzle)
    index = puzzle.calc_number
    direction = puzzle.direction
    count = puzzle.count
    @visited_dict[index] *= direction
    @count_dict[index] += count
  end

  def get_count(puzzle)
    return count_dict[puzzle.calc_number]
  end
end

SWAP_CHOICE = [[1, 3],    [0, 2, 4],    [1, 5], 
               [0, 4, 6], [1, 3, 5, 7], [2, 4, 8],
               [3, 7],    [4, 6, 8],    [5, 7]]

GOAL_STATE = [1, 2, 3, 4, 5, 6, 7, 8, 0]

FORWARD = 2
BACKWARD = 3

# main
init_state = []
3.times do 
  init_state.concat(gets.chomp.split.map(&:to_i))
end

queue = []
init_puzzle = Puzzle.new(init_state, FORWARD, 0)
goal_puzzle = Puzzle.new(GOAL_STATE, BACKWARD, 0)
queue << init_puzzle 
queue << goal_puzzle

dict = Dictionary.new(9.downto(1).inject(:*))
dict.visit(init_puzzle)
dict.visit(goal_puzzle)

while queue.size > 0 do
  puzzle = queue.shift
  index = puzzle.calc_number
  if dict.visited?(index, FORWARD) && dict.visited?(index, BACKWARD) then
    puts dict.count_dict[index] 
    break
  end

  zero_position = puzzle.find_zero
  swap_positions = SWAP_CHOICE[zero_position]

  swap_positions.each do |swap_pos|
    new_puzzle = Puzzle.new(puzzle.state.dup, 
                            puzzle.direction, 
                            puzzle.count + 1)
    new_puzzle.state[zero_position], new_puzzle.state[swap_pos] = 
      new_puzzle.state[swap_pos], new_puzzle.state[zero_position]
    next if dict.visited?(new_puzzle.calc_number, new_puzzle.direction)

    queue << new_puzzle
    dict.visit(new_puzzle)
  end
end

Measured memory_bytes: 16304
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int arr[200005];
long long val[200005];
struct node{
    int s,e,m;
    node *l, *r;
    long long val=-1;
    node (int _s,int _e){
        s=_s,e=_e,m=(s+e)>>1;
        if (s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void upd(int i,long long j){
        if (s==e) val=j;
        else{
            if (i<=m) l->upd(i,j);
            else r->upd(i,j);
            val=max(l->val,r->val);
        }
    }
    long long query(int i,int j){
        if (i==s && j==e) return val;
        else if (j<=m) return l->query(i,j);
        else if (m<i) return r->query(i,j);
        else return max(l->query(i,m),r->query(m+1,j));
    }
}*root;
int main(){
    scanf("%d",&n);
    for (int x=0;x<n;x++) scanf("%d",&arr[x]);
    for (int x=0;x<n;x++) scanf("%lld",&val[x]);
    root=new node(0,n);
    root->upd(0,0);
    long long ans=0;
    long long curr;
    for (int x=0;x<n;x++){
        curr=root->query(0,arr[x]-1);
        curr+=val[x];
        root->upd(arr[x],curr);
        ans=max(ans,curr);
    }
    printf("%lld\n",ans);
}


Measured memory_bytes: 21376
import sys
N=int(input())
S=sys.stdin.readline()
stat=0
count=0
for ele in S:
    if ele=='A':
            stat=1
    else:
        if stat == 1:
            if ele=='B':
                stat=2
            else:
                stat=0
        elif stat==2:
            if ele=='C':
                stat=0
                count+=1
            else:
                stat=0
print(count)

Measured memory_bytes: 3188
/**
 *    Coded by : lucky_21
 *               --------Lokesh Singh
**/

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=3005;
const int mod=1e9+7;

ll n,a[N],dp[N][N][2];
ll rec(int s,int e,bool turn){
    if(s>e) return 0;
    ll &cache=dp[s][e][turn];
    if(cache) return cache;
    return cache=(turn?min(-a[s]+rec(s+1,e,turn^1),-a[e]+rec(s,e-1,turn^1)):max(a[s]+rec(s+1,e,turn^1),a[e]+rec(s,e-1,turn^1)));
}
signed main(){
    FastIO;
    cin>>n;
    rep(i,1,n) cin>>a[i];
    cout<<rec(1,n,0);
    return 0;
}


Measured memory_bytes: 139776
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String string = sc.next();
        int count = 0;
        for (int i = 0 ; i < 6 ; i++) {
            if (string.substring(i, i + 1).equals("1")) {
                count++;
            }
        }
        System.out.println(count);
    }

}


Measured memory_bytes: 22996
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <deque>
#include <utility>
using namespace std;
typedef long long ll;
#define for1(i,n) for (ll i=0;i<(n);i++)
#define for2(i,m,n) for (ll i=(m);i<(n);i++)
#define for3(i,m,n,d) for (ll i=(m);i<(n);i+=(d))
#define INF (1LL << 60)

struct PrimeNumber {
    const ll MOD = 1000000007;  // 10**9 + 7
    ll add(ll a, ll b)
    {
        return (a + b) % MOD;
    }
    ll sub(ll a, ll b)
    {
        return (a + MOD - b) % MOD;
    }
    ll mul(ll a, ll b)
    {
        return ((a % MOD) * (b % MOD)) % MOD;
    }
    ll power(ll x, ll y)
    {
        if (y == 0) {
            return 1;
        }
        else if (y == 1) {
            return x % MOD;
        }
        else if (y % 2 == 0) {
            ll t = this->power(x, y / 2);
            return this->mul(t, t);
        }
        else {
            ll t = this->power(x, y / 2);
            return this->mul(this->mul(t, t), x);
        }
    }
    ll div(ll a, ll b)
    {
        return this->mul(a, this->power(b, MOD - 2));
    }

    #define FACTORIAL_MAX 10000
    ll memo_factorial[FACTORIAL_MAX+1];
    void init_factorial(void)
    {
        this->memo_factorial[0] = 1;
        for (ll i = 1; i <= FACTORIAL_MAX; ++i) {
            this->memo_factorial[i] = this->mul(i, this->memo_factorial[i-1]);
        }
    }
    ll factorial(ll n)
    {
        return this->memo_factorial[n];
    }
    ll combination(ll n, ll r)
    {
        ll ret = this->factorial(n);
        ret = this->div(ret, this->factorial(r));
        ret = this->div(ret, this->factorial(n-r));
        return ret;
    }
};

void solve()
{
    PrimeNumber prime;
    //prime.init_factorial();
    ll N,K;
    cin >> N >> K;
    vector<vector<ll>> to(N);
    vector<ll> cnt_edges(N);
    vector<ll> color(N, -1);
    for1(i,N-1) {
        ll a,b;
        cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    for1(i,N) {
        cnt_edges[i] = to[i].size();
    }
    ll start = 0;
    for1(i,N) {
        if (cnt_edges[i] == 1) {
            start = i;
            break;
        }
    }
    ll ans = 1;
    deque<pair<ll,ll>> q;
    q.push_back(make_pair(start,K));
    while (!q.empty()) {
        auto item = q.front();
        q.pop_front();
        ll vertex = item.first;
        ll possib = item.second;
        color[vertex] = possib;
        ans = prime.mul(ans, possib);
        ll k1 = possib - 1;
        if (k1 < K-2) {
            k1 = K-2;
        }
        for (ll t : to[vertex]) {
            if (color[t] != -1) continue;
            q.push_back(make_pair(t,k1));
            --k1;
        }
    }
    cout << ans << endl;
}

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


Measured memory_bytes: 9716
import re

n, k = map(int,input().split()) # K 回前のじゃんけんで出した手と同じ手を出すことはできない
r, s, p = map(int,input().split()) # r:goo , s:choki, p:paa
t = input()

# aaaaa
ans = 0

for i in range(k):
    tmp = t[i::k]
    tmp = re.sub('rr','rz',tmp)
    tmp = re.sub('ss','sz',tmp)
    tmp = re.sub('pp','pz',tmp)
    ans += tmp.count('r') * p + tmp.count('s') * r + tmp.count('p') * s
    # print(tmp)
print(ans)

Measured memory_bytes: 43484