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

int main(){
    string s;
    cin>>s;
    int n=s.size();
    long long ans=0;
    int w=0; 
    for (int i=0;i<n;i++) {
        if (s[i]=='A') {
            w++;
        } else if (s.substr(i,2)=="BC") {
            ans+=w;
            i++;
        } else {
            w=0;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int a,b;
string s;
int main()
{
	cin>>a>>s>>b;
	b--;
	for(int i=0;i<a;i++)
		if(s[i]!=s[b])
			s[i]='*';
	cout<<s<<endl;
}

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

using namespace std;
struct job {
  int time; 
  int deadline; 
};
int main(){
    int N;
    cin >> N;
    vector<job> jobs(N);

    for (int  i = 0; i < N; i++)
    {   
        cin >> jobs[i].time >> jobs[i].deadline;
    }
    
    // nameをキーに昇順でソート
    sort(jobs.begin(), jobs.end(),[](const job& x, const job& y) { return x.deadline < y.deadline;});

    int sumtime = 0;
    for(int i = 0; i < (int)jobs.size(); ++i) {
        sumtime += jobs[i].time;
        if(sumtime > jobs[i].deadline){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}

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

int main()
{
   ll n, rs = 0;
   cin >> n;
   string s;
   cin >> s;
   for(int i = 0; i < n; i++){
      if(s[i] == 'R')
          rs++;
   }
   ll ans1 = 0, ans2 = 0;
   for(int i = 0; i < rs; i++){
      if(s[i] == 'W')
          ans1++;
   }
   cout << ans1 << endl;
}

Measured memory_bytes: 3716
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <bitset>
#include <random>
#include <chrono>
#include <complex>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip> 

using namespace std;

#define sqr(x) ((x)*(x))
#define mp make_pair
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define RE(i, n) FOR(i,1,n)
#define REP(i,n) FOR(i, 0, (int)(n)-1)
#define fst first
#define snd second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef tuple<int,int,int> iii;

string to_string(string s) {
    return '"' + s + '"';
}
    
string to_string(const char* s) {
    return to_string((string) s);
}
    
string to_string(bool b) {
    return (b ? "true" : "false");
}
    
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
    
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

void fastIO() {
    cin.sync_with_stdio(false);
    cin.tie(0);
}


int XMOV[4] = {0, 0, 1, -1};
int YMOV[4] = {1, -1, 0, 0};

//#############################
const int MAXN = 1000005;
const ll MOD = (1e9)+7;
int h,w;
vector<string> g;
ll memo[2000][2000];

ll dp(int r, int c) {
    if (r < 0 || c < 0 || g[r][c] == '#')
        return 0;
    if (r == 0 && c == 0)
        return 1;
    if (memo[r][c] != -1)
        return memo[r][c];
    
    return memo[r][c] = ((dp(r-1, c)%MOD) + (dp(r, c-1)%MOD))%MOD;
}


int main() {
    string s;
    cin >> h >> w;
    for(int i = 0; i < h; i++)
        cin >> s, g.pb(s);
    memset(memo, -1, sizeof(memo));
    dp(h-1, w-1);
    cout << memo[h-1][w-1] << endl;
    return 0;
}

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

int main()
{
    int L,C,W=0;
    double x=0,y=0;
    char c;
    while(1){
        cin >> L >> c >> C;
        if(!(L||C)){
            break;
        }
        x=x+(double)L*sin(W/180.0*M_PI);
        y=y+(double)L*cos(W/180.0*M_PI);
        W+=C;
    }
    cout << (int)x << "\n" << (int)y << endl;
}

Measured memory_bytes: 1164
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
   int n; cin>>n;
   vector<int> w(n);
   for(int i=0;i<n;i++) cin>>w[i];
   int ans=1e9;
   for(int i=1;i<n;i++){
      int be=0,af=0;
      for(int j=0;j<i;j++) be+=w[j];
      for(int k=i;k<n;k++) af+=w[k];
      ans=min(ans,abs(be-af));
   }
   cout<<ans<<endl;
   return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    ll a,b;
    cin>>a>>b;
    ll ans=gcd(a,b);
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3088
using System;

namespace MF
{
    class Program
    {
        static void Main(string[] args)
        {
            var x = Console.ReadLine().Split(' ');
            var a = double.Parse(x[0]);
            var b = double.Parse(x[1]);
            var c = double.Parse(x[2]) * Math.PI / 180;
            Console.Write("{0}\n{1}\n{2}\n",
            a * b * Math.Sin(c) / 2,
            a + b + Math.Sqrt(a * a + b * b - 2 * a * b * Math.Cos(c)),
            b * Math.Sin(c));
        }
    }
}

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

int main(){
  int N, M, K;
  cin >> N >> M >> K;
  vector<int> A(N), B(M);
  long long sumb = 0;
  for(int i=0; i<N; i++){
    cin >> A.at(i);
  }
  for(int i=0; i<M; i++){
    cin >> B.at(i);
    sumb += B.at(i);
  }
  int ans = 0;
  long long time = 0;
  int index = M-1;
  for(int i=0; i<=N; i++){
    int num = i;
    if(i>0) time += A.at(i-1);
    if(time>K) break;
    while(time+sumb>K){
      sumb -= B.at(index);
      index--;
    }
    ans = max(ans,i+index+1);
  }
  cout << ans;
  return 0;
}

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

#define Need_For_Speed ios_base::sync_with_stdio;cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define mp make_pair

#define bg begin
#define en end

#define sz size()

#define fe first
#define se second

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e6 + 17, maxN = 4 * N, darr = 1e3 + 17, mod = 1e9 + 7;

int n, k;
int a[N], d[N];

int mx, g;

int gcd (int a, int b) {
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

int main () {
	Need_For_Speed;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; 
		mx = max(mx, a[i]);
	}
	g = a[1];
	for (int i = 2; i <= n; i++) {
		g = gcd(g, a[i]);
	}
	if (k <= mx && k % g == 0) {
		cout << "POSSIBLE";
	}
	else {
		cout << "IMPOSSIBLE";
	}
	return 0;
}

Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ITP1_8_C
{
    class Program
    {

        static void Main(string[] args)
        {
            var alphabet = "abcdefghijklmnopqrstuvwxyz";
            var sumOfAlphabets = new int[alphabet.Length];

            var isContinued = true;
            while (isContinued)
            {
                var input = Console.ReadLine();
                if (input == null || input.Length == 0)
                {
                    break;
                }

                input = input.ToLower();

                foreach (var n in input) 
                {
                    var index = alphabet.IndexOf(n);
                    if (0 <= index)
                    {
                        ++sumOfAlphabets[index];
                    }
                }
            }

            for (var i = 0; i < alphabet.Length; ++i)
            {
                Console.WriteLine("{0} : {1}", alphabet[i], sumOfAlphabets[i]);
            }
        }
    }
}

Measured memory_bytes: 5628
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cstring>
#include<cmath>
#include <numeric>
#include<queue>
#include<climits>
#include<cstdio>


#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
//#define INF ((LLONG_MAX) / (2))
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;
typedef pair<ll,int> LL_IP;
#define INF 1e9+7




int main(){

    string s;
    cin >> s;
    vector<int> alpha_count(26,0);
    string str = "abcdefghijklmnopqrstuvwxyz";
    int number_of_char = 0;
    int maxi = -INF;//出現頻度の最多回数

    REP(i,s.length()){
        /*文字の出現回数のカウント*/
        alpha_count[s[i]-'a']++;
    }

    REP(i,26){
        /*出現頻度の最多回数を求める*/
        maxi = max(maxi,alpha_count[i]);
        if(alpha_count[i] > 0){
            /*１回でも文字が出現しているなら出現した文字数をインクリメント*/
            number_of_char++;
        }
    }
    REP(i,26){
        /*出現頻度が最多の文字列をstrに格納*/
        if(alpha_count[i] == maxi){
            str.push_back(str[i]);
        }
    }

    int ans = INF;

    for(int i = 0;i < str.length();i++){
        /*str[i]の単一文字列にする操作をし、その操作回数を求める*/
        string tmp = s;/*作業用文字列*/
        int operation_count = 0;
        bool flag = true;//単一文字列になったらfalseになる
        if(number_of_char == 1){
            /*そもそも１文字しか現れていない場合はすでに単一文字列になっているので操作の必要なし*/
            ans = 0;
            flag = false;
        }
      
        while(flag){/*単一文字列になるまでのループ*/
            
            for(int j = 1;j < tmp.length();j++){ /*文字列末尾まで操作*/
                if(tmp[j] == str[i]){
                    /*tmp[j]とstr[i]の文字が同じならtmp[j-1]をstr[i]に置き換える*/
                    tmp[j-1] = str[i];
                }
            }
            operation_count++;
            /*str[i]で置き換え終了*/
            tmp.pop_back();/*１文字減らす操作*/
            int num = 0;
            REP(j,tmp.length()){/*tmp内にstr[i]が何文字あるかを数える*/
                if(tmp[j] == str[i]){
                    //str[i]があった
                    num++;
                }
            }
            if(num == tmp.length()){//全てstr[i]に置き換わっている
                ans = min(ans,operation_count);/*最小操作回数を更新*/
                flag = false;/*単一文字列になったのでループを終了*/
            }
        }
    }
    cout << ans << endl;

    return 0;
}

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

using namespace std; 

int n1, n2;
short dp[3001][3001];
char bt[3001][3001];

int main() {
	char a[3000], b[3000];
	cin >> a;
	cin >> b;
	n1 = strlen(a);
	n2 = strlen(b);

		
	for(int i = 0; i <= n1;i++){
		for(int j = 0;j <= n2;j++){
			if (i == 0 || j == 0){
				dp[i][j] = 0;
			}
			else{
				if (dp[i-1][j] > dp[i][j-1]){
					bt[i][j] = 0;
					dp[i][j] = dp[i-1][j];
				}
				else{
					bt[i][j] = 1;
					dp[i][j] = dp[i][j-1];
				}

				if(a[i-1] == b[j-1]) {
					if (dp[i-1][j-1] + 1 > dp[i][j]) {
						dp[i][j] = dp[i -1][j -1] + 1;
						bt[i][j] = 2;
					} 
				}

			}
		}
	}

	int answer = dp[n1][n2];

	if (answer < 1){
		cout << "";
		return 0;
	}

	vector<char> res;
	int i = n1;
	int j = n2;
	while(i > 0 && j > 0){
		if (bt[i][j] == 0){
			i--;
		}
		else if (bt[i][j] == 1){
			j--;
		}
		else if (bt[i][j] == 2){
			res.push_back(a[i-1]);
			i--;
			j--;
		}	
	}
	reverse(res.begin(), res.end());
	for(auto c : res){
		cout << c;
	}
	return 0;
}


Measured memory_bytes: 29952
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;

namespace D
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = long.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split().Select(long.Parse).ToList();

            long signCount = a.Count(x => x<0);
            long numberOfZero = a.Count(x => x == 0);

            long sumAbsA = a.Select(x => Abs(x)).ToList().Sum();

            if((signCount % 2 == 0) || numberOfZero > 0)
            {
                Console.WriteLine(sumAbsA);
            }
            else
            {
                Console.WriteLine(sumAbsA - 2*a.Select(x=>Abs(x)).Min());
            }
        }
    }
}


Measured memory_bytes: 33372
#include <stdio.h>

#define SIZE 2000000

int main() {
  setvbuf(stdout, NULL, _IOFBF, 4000);
  int A[SIZE];
  int H=0;
  int i, l, largest, tmp, n;
  char com[21], buf[20];
  buf[19]='\n';
  char *p,*c1,*c2;
  c1 = com+1;
  c2 = com+2;
  do {
    fgets(com, 20, stdin);
    if (*com == 'i') {
      n = 0;
      p = com+7;
      while (*p!='\n') {
        n = n*10+*p-'0';
        p++;
      }
      A[++H] = n;
      for (i=H; i>1 && A[i>>1]<A[i];i>>=1) {
        tmp = A[i>>1];
        A[i>>1] = A[i];
        A[i] = tmp;
      }

    } else if (*c1=='x') { // extract
      n = A[1];
      for (i=18; n>0; n/=10) buf[i--]=(n%10)+'0';
      fputs(buf+i+1, stdout);
      A[1] = A[H];
      i = 1;
      while (1) {
        l = i<<1;
        if (l < H && A[l] > A[i])        largest = l;
        else         largest = i;
        if (l+1 < H && A[l+1] > A[largest])  largest = l+1;
        if (largest == i) break;
        tmp = A[i];
        A[i] = A[largest];
        A[largest] = tmp;
        i = largest;
      }
      H--;
    }
  } while (*c2!='d');
  return 0;
}


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

int main(){

    ll n;
    ll y;
    cin >> n >> y;

    for(int i=0;i*10000<=y;i++){
        for(int j=0;j*5000+i*10000<=y;j++){
            ll t=(y-i*10000-j*5000)/1000;
            if(t+i+j==n){
                cout << i <<" "<< j <<" "<< t << endl;
                return 0;
            }
        }
    }

    cout << "-1 -1 -1" << endl;

    return 0;
}

Measured memory_bytes: 256
import std.stdio, std.conv, std.string;
import std.algorithm, std.array, std.container;
import std.numeric, std.math;
import core.bitop;

T RD(T = string)() { static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }

long mod = pow(10, 9) + 7;
long moda(long x, long y) { return (x + y) % mod; }
long mods(long x, long y) { return ((x + mod) - (y % mod)) % mod; }
long modm(long x, long y) { return (x * y) % mod; }

void main()
{
	auto N = RD!long;

	bool ans = true;
	long[2] pos;
	long lastTime;
	foreach (i; 0..N)
	{
		auto t = RD!long;
		auto x = RD!long;
		auto y = RD!long;
		auto d = abs(x - pos[0]) + abs(y - pos[1]);
		auto use_t = t - lastTime;
		if (d > use_t || (use_t - d) % 2 == 1)
		{
			ans = false;
			break;
		}
		pos = [x, y];
		lastTime = t;
	}

	writeln(ans ? "Yes" : "No");
	stdout.flush();
}

Measured memory_bytes: 1276
#include "bits/stdc++.h"
//#include <iostream>
//#include <vector>
//#include <string>
using namespace std;
#define setc cin.tie(0);ios::sync_with_stdio(0)
#define repi(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)
#define rep(i,n) repi(i,0,n)
#define repi_(i,a,b) for(int i=(a), i##_len=(b); i<=i##_len; ++i)
#define rep_(i,n) repi_(i,0,n)
#define all(x) (x).begin(),(x).end()
#define vsort(v) sort((v).begin(), (v).end())
#define gsort(v) tsort(v); reverse((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())
#define siz(v) ((int)(v).size())
#define ers(v, n) (v).erase((v).begin() + n)
#define cnt(v, n) count(all(v), n)
#define vmin(v) *min_element(v.begin(), v.end())
#define vmax(v) *max_element(v.begin(), v.end())
#define contain(q) !q.empty()
#define cont(q) !q.empty()
//#define qpop(q, a, b) a=q.back().first;b=q.back().second;q.pop()
//#define pqpop(p, a, b) a=q.top().first;b=q.top().second;q.pop()
#define el "\n"
#define sp " "
#define co(x) cout<<(x)<<el
#define coc(c, a, b) if(c)co((a));else co((b))
#define cosp(x) cout<<(x)<<' '
#define YES(c) coc(c,"YES", "NO")
#define Yes(c) coc(c,"Yes", "No")
#define yes(c) coc(c,"yes", "no")
#define POSSIBLE(c) coc(c, "POSSIBLE", "IMPOSSIBLE")
#define Possible(c) coc(c, "Possible", "Impossible")
#define possible(c) coc(c, "possible", "impossible")
#define inf INT_MAX
#define wildcard(T) numeric_limits<T>::min()

#define pb push_back
#define pq priority_queue
#define np next_permutation

#ifdef tqktmp_2
#define gc() getchar(); getchar()
#else
#define gc() 1
#endif
const unsigned int bf0 = (1 << 0);
const unsigned int bf1 = (1 << 1);
const unsigned int bf2 = (1 << 2);
const unsigned int bf3 = (1 << 3);
const unsigned int bf4 = (1 << 4);
const unsigned int bf5 = (1 << 5);
const unsigned int bf6 = (1 << 6);
const unsigned int bf7 = (1 << 7);

typedef long long lint;
typedef vector<int> ivec; typedef vector<string> svec;
typedef vector<vector<int>> ivvec;
typedef pair<int, int> P;

const int
	dx8[8] = { 0,1,1,1,0,-1,-1,-1 },
	dy8[8] = { 1,1,0,-1,-1,-1,0,1 },
	dx4[4] = { 0,1,0,-1 },
	dy4[4] = { 1,0,-1,0 };

template<class T>inline bool maxi(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>inline bool mini(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

int main() {
	setc;

	string s; cin >> s;
	bool f = 1;
	lint p;
	if (s[0] != 'A')f = 0;
	string sub = s.substr(2, s.length() - 3);
	if (cnt(sub, 'C') != 1)f = 0;
	repi(i, 1, s.length()) {
		if (s[i] != 'C' && (s[i] < 'a' || 'z' < s[i]))f = 0;
	}
	coc(f, "AC", "WA");
	gc();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define Fast_IO ios::sync_with_stdio(false);
#define int long long
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
#define mod 998244353
#define N 200005
int n;
string s;
map<int,int> a;
int work(int len)
{
	int v=0;
	for(int i=0;i<len;i++)
	{
		v=(v*2+s[i]-'0')%mod;
	}
	int ok=1;
	for(int i=len;i<n;i++)
	{
		int x=s[i%len]-'0';
		if(i/len%2) x^=1;
		if(x==s[i]-'0') continue;
		if(x>s[i]-'0') ok=0;
		break;
	}
	v=(v+ok)%mod;
	int ans=0;
	map<int,int>::iterator i;
	for(i=a.begin();i!=a.end();++i)
	{
		if(len%(i->first)==0) v=(v-i->second+mod)%mod;
	}
	a[len]=v;
	return (ans+2*v*len)%mod;
}
signed main()
{
#ifdef __LOCAL__
	freopen("in.txt","r",stdin);
#endif
	cin>>n;
	cin>>s;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
//		cout<<i<<endl;
		if(n%i==0&&n/i%2==1)
		{
			ans=(ans+work(i))%mod;
		}
	}
	cout<<ans<<endl;
#ifdef __LOCAL__
	printf("Time Used : %d\n",clock());
#endif
	return 0;
}



Measured memory_bytes: 640
def get_count(s, leader, r):
    count = 0
    
    pre_upper_pos = 0
    
    for li in leader:
        lower_pos = bisect.bisect_left(s, li - r)
        upper_pos = bisect.bisect_right(s, li)
        if pre_upper_pos < lower_pos:
            count += lower_pos - pre_upper_pos
        pre_upper_pos = upper_pos
    count += len(s) - pre_upper_pos
    
    return count

import bisect

def check(s,leader,target_x):
    if 0 == len(leader):
        if target_x < len(s):
            return 'NA'
        else:
            return 0
    min_x = len(s) - bisect.bisect_right(s, leader[-1])
    if target_x < min_x:
        return 'NA'

    l, r = 0, s[-1]
    diff = r - 1
    while True:
        m = (l + r) // 2
        x = get_count(s, leader, m)
        if target_x < x:
            l = m
        elif x <= target_x:
            r = m
        
        if diff == l - r:
            return r
        diff = l - r

import sys
f = sys.stdin

n, q = (int(i) for i in  f.readline().split())
s = [int(f.readline()) for i in range(n)]
query = [line.split() for line in f]

sort_s = sorted(s)
leader = []

for op, a in query:
    a = int(a)
    if op[0] == 'A':
        leader.append(s[a - 1]) #bisect??§??????????¶?????????????????????\?????????
        leader.sort()
    elif op[0] == 'R':
        leader.remove(s[a - 1])
    else:
        r = check(sort_s,leader,a)
        print(r)

Measured memory_bytes: 60260
/*
https://t.me/unstoppabIesoIvemachinechannel
*/
#pragma ARCENIY_KIRILLOV_POVELITEL_KROKODILOV
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC push_options
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC pop_options
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define rng(a) a.begin(),a.end()
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, n) for (int i = 0; i < n; i++)
#define per(i, n) for (int i = n - 1; i > -1; i--)
#define rer(i, x, n) for (int i = x; i < n; i++)
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef long double ld;












const int maxn = 205;
int minx[maxn];
int maxx[maxn];
bool c[maxn][maxn];
vector<int> used;
int tim = 1;
vector<vector<int> > g;
bool fl = 1;
vector<int> dp;
vector<int> cvet;
void dfs(int v,int len){
    if (!fl)
        return;
    used[v] = tim;
    dp[v] = len;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i];
        if (used[to] != tim){
            dfs(to, len + 1);
        }
        if (dp[v]%2 == dp[to]%2){
            fl = 0;
            return;
        }
    }
}
signed main(){
    int n;
    cin >> n;
    g.resize(n);
    dp.resize(n);
    cvet.resize(n);
    used.resize(n, 0);
    for (int i = 0; i < n; i++){
            string s;
            cin >> s;
        for (int j = 0; j < n; j++){
            if (s[j] == '1') g[i].pb(j);
        }
    }
    dfs(0, 0);
    if (!fl){
        cout << -1;
        return 0;
    }
    int maxx = 0;
    for (int start = 0; start < n; start++){
        tim++;
        used[start] = tim;
        queue<int> q;
        q.push(start);
        for (int i = 0; i < n; i++) cvet[i] = 0;
        cvet[start] = 1;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            maxx = max(cvet[v], maxx);
            for (int i = 0; i < g[v].size(); i++){
                int to = g[v][i];
                if (used[to] == tim) continue;
                q.push(to);
                used[to] = tim;
                cvet[to] = cvet[v] + 1;
            }
        }

    }
    cout << maxx;
}


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

int main(){
    int N;
    string A;
    cin >> N >> A;
    int count = 0;
    for (int x = 0; x < N - 2; x++){
        if (A.at(x) == 'A' && A.at(x +1) == 'B' && A.at(x +2) == 'C' )
            count++;
    }
    cout << count << endl;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
int main()
{
  int A, P;
  cin >> A >> P;
  P += A*3;

  int ApplePie = 0;
  ApplePie = P / 2;

  cout << ApplePie << endl;
  return 0;
}

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

template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last) {
  reverse(middle, last);
  return next_permutation(first , last);
}

int main() {
  int N, C; cin >> N >> C;
  auto D = vector<vector<int>>(C + 1, vector<int>(C + 1));
  for (int i = 1; i <= C; ++i) {
    for (int j = 1; j <= C; ++j) cin >> D[i][j];
  }
  auto color = vector<vector<int>>(3, vector<int>(C + 1, 0));
  auto num = vector<int>(3, 0);
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      int c; cin >> c;
      ++color[(i + j) % 3][c];
      ++num[(i + j) % 3];
    }
  }

  auto v = vector<int>(C);
  for (int i = 0; i < C; ++i) v[i] = i + 1;

  int ans = 1e9;
  do {
    auto p = num;
    int sum = 0;
    for (int i = 1; i <= C; ++i) {
      for (int j = 0; j < 3; ++j) {
        sum += D[i][v[j]] * color[j][i];
      }
    }
    ans = min(ans, sum);
  } while (next_partial_permutation(begin(v), begin(v) + 3, end(v)));
  cout << ans << endl;
  return 0;
}


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

int main()
{
    int h, w, a, b;
    cin >> h >> w >> a >> b;

    rep(i, b)
    {
        rep(j, a) cout << 0;
        for (int j = a; j < w; j++)
            cout << 1;
        cout << endl;
    }
    for (int i = b; i < h; i++)
    {
        rep(j, a) cout << 1;
        for (int j = a; j < w; j++)
            cout << 0;
        cout << endl;
    }
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF 1e9+7
#define rep(i,n) for(ll i=0;i<n;i++)
#define pii pair<int,int>
#define pll pair<ll,ll>
const int maxn = 1000000;
ll mod = INF;

ll h;
ll cnt=1;
ll ans=0;

int main(){
    cin >> h;
    
    while(h>0){
        ans+=cnt;
        h=h/2;
        cnt=cnt*2;
    }

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

Measured memory_bytes: 3636
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
#include <memory>
#include <time.h>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXIST2(s,e) (find(ALL(s),(e))!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-9;
const double PI = acos(-1.0);


typedef vector<ll> vl;
typedef vector<vl> vvl;

struct guy{
	ll l;
	int date_mask;
};
int main(){
	int n;
	while(cin>>n,n){
		vector<guy> guys(n);
		REP(i,n){
			int m;
			cin>>m>>guys[i].l;
			REP(j,m){
				int s,e;
				cin>>s>>e;
				FOR(k,s,e){
					guys[i].date_mask|=(1<<(k-6));
				}
			}
		}
		vvl dp(n+1,vl(1<<16));
		FOR(i,1,n+1){
			REP(j,1<<16){
				bool ok=true;
				REP(k,16){
					if(((guys[i-1].date_mask>>k)&1)&&((j>>k)&1)){
						ok=false;
					}
				}
				if(ok){
					dp[i][j|guys[i-1].date_mask]=max(dp[i][j|guys[i-1].date_mask],dp[i-1][j]+guys[i-1].l);
				}
				dp[i][j]=max(dp[i][j],dp[i-1][j]);
			}
		}
		ll ans=0;
		REP(i,1<<16){
			ans=max(ans,dp[n][i]);
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 53336
#include <stdio.h>
#include <string.h>

void reverse(char *S) {
	char tmp;
	int i;
	int length = strlen(S);
	for (i = 1; i <= length / 2; i++) {
		tmp = S[i - 1];
		S[i - 1] = S[length - i];
		S[length - i] = tmp;
	}
}

int main() {
	char S[3], ans[3];
	int i;
	scanf("%s", S);
	if (strlen(S) > 2)
		reverse(S);
	printf("%s", S);
	return 0;
}

Measured memory_bytes: 128
# Union Find Tree
class UnionFindTree():
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
        self.count = 0

    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i])
            self.parent[i] = group
        return group

    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]:  # rank is same
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px

            self.parent[py] = px
            self.size[px] += self.size[py]
            self.count += 1

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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(M)]

UFT = UnionFindTree(N)
for x, y, z in A:
    x -= 1
    y -= 1
    UFT.unite(x, y)
print(N - UFT.count)


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

int main(){
	ll x,k,d;
	cin >> x >> k >> d;

	ll p = x/d;
	ll ans = 0;
	ll l,r;

	if(p >= k){
		ans = abs(x - k*d);
	}
	else if(p <= -k){
		ans = abs(x + k*d);
	}
	else{
		ll diff = k-abs(p);
		if(p < 0){
			r = abs(p) + diff/2, l = diff/2;
		}
		else if(p > 0){
			l = p+diff/2, r = diff/2;
		}

		ans = abs(x + (r-l)*d);

		if(diff%2 == 1){
			ans = min(abs(ans+d), abs(ans-d));
		}

		if(p == 0){
			if(k%2 == 1){
				ans = min(abs(x+d), abs(x-d));
			}
			else{
				ans = abs(x);
			}
		}
	}

	cout << ans << "\n";
	
}

Measured memory_bytes: 3644
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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

long long N,K,ans;

int main(){
    cin>>N>>K;
    out(K*(int)pow(K-1,N-1));
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG_OUTPUT
#define DEBUG_LOG(s) cout << s << endl;
#else
#define DEBUG_LOG(s) void();
#endif

int main(){
    int n;
    cin >> n;
    n %= 10;

    if(n == 3) {
        cout << "bon" << endl;
    } else if(n == 0 or n == 1 or n == 6 or n == 8) {
        cout << "pon" << endl;
    } else {
        cout << "hon" << endl;
    }

    return 0;
}

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

int main() {
	long long int N, a[300000], count = 0;
	cin >> N;
	for (int i = 0; i < 3 * N; i++) {
		cin >> a[i];
	}
	sort(a, a + 3 * N, greater<int>());
	for (int i = 0; i < N; i++) {
		count += a[i * 2 + 1];
	}
	cout << count << endl;
}

Measured memory_bytes: 2560
n=int(input())
A=list(map(int,input().split()))
ma = max(A)
mid = ma / 2
l = 10000000000
f = 0
for i in range(n):
  if ((ma == A[i]) and (f==0)):
    f = 1
    continue
  if abs(l) > abs(A[i]-mid):
    l = A[i]-mid
print(ma, int(mid+l))


Measured memory_bytes: 14428
from fractions import gcd


def get_primes(n):
    ans = 1 if n % 2 else 2
    while n % 2 == 0:
        n //= 2
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            ans += 1
        while n % i == 0:
            n //= i
    return ans + 1 if n > 1 else ans


def solve(string):
    a, b = map(int, string.split())
    g = gcd(a, b)
    return str(get_primes(g))


if __name__ == '__main__':
    print(solve(input()))


Measured memory_bytes: 5048
#include <bits/stdc++.h> 
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(vec) vec.begin(), vec.end()
typedef long long ll;ll MM = 1000000000;ll mod = MM + 7;
ll GCD(ll x, ll y) {if (x % y == 0) return y;else return GCD(y, x % y);}
ll LCM(ll x, ll y) { return x * y / GCD(x, y);}

int main(){
  ll n,k,ans=MM,x; cin>>n>>k;
  vector<ll>v(n);
  rep(i,n) cin>>v[i];
  for(ll i=0;i<=n-k;i++){
  x=min(abs(v[i]),abs(v[i+k-1]))+v[i+k-1]-v[i];
   ans=min(ans,x);
  }    
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var a, b int
	fmt.Scan(&a, &b)

	var A, B string
	for i := 0; i < b; i++ {
		A += strconv.Itoa(a)
	}
	for i := 0; i < a; i++ {
		B += strconv.Itoa(b)
	}

	if A < B {
		fmt.Println(A)
	} else {
		fmt.Println(B)
	}
}


Measured memory_bytes: 512
fun main(arg: Array<String>) {
    val N = nextInt()
    val S1 = next()
    val S2 = next()
    val Tate = BooleanArray(N) { S1[it] == S2[it] }
    val C = LongArray(N) { n -> 
        if (n == 0) if (Tate[n]) 3 else 6
        else if (!Tate[n - 1] && !Tate[n] && S1[n - 1] == S1[n]) 1
        else if (Tate[n]) if (Tate[n - 1]) 2L else 1L
                     else if (Tate[n - 1]) 2L else 3L
    }
    val MOD = 1000000007L
    val ans = C.reduce { acc, c -> (acc * c) % MOD }
    println(ans)
}

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun listOfString() = next().split(" ")
fun listOfLong() = listOfString().map { java.lang.Long.parseLong(it) }



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

int main() {
  int N, X, Y, T, j=0;
  vector<int> P, Q, A;
  cin >> N;
  rep(i, N){
    cin >> T;
    P.push_back(T);
  }
  rep(i, N){
    cin >> T;
    Q.push_back(T);
    A.push_back(i+1);
  }
  do{
    j++;
    if(A==P) X=j;
    if(A==Q) Y=j;
  }
  while(next_permutation(A.begin(), A.end()));
  cout << abs(Y-X) << endl;
}

Measured memory_bytes: 256
h, w = list(map(int, input().split()))
graph = []
def check(s,t):
    if (0 <=  s <= w - 1) and (0 <= t <= h - 1):
        return True
    else:
        return False
def check_around(x,y):
    if check(x+1,y) and graph[y][x+1] == '#':
        return True
    if check(x,y+1) and graph[y+1][x] == '#':
        return True
    if check(x-1,y) and graph[y][x-1] == '#':
        return True
    if check(x,y-1) and graph[y-1][x] == '#':
        return True
    return False
for i in range(h):
    graph.append(list(input()))
for i in range(h):
    for j in range(w):
        if graph[i][j] == '#':
            if  not check_around(j,i):
                print("No")
                exit()
print("Yes")
            
                


Measured memory_bytes: 3064
#include <bits/stdc++.h> 
using namespace std;
#define rep(i, N) for(int i=0; i<N; i++)
typedef long long ll;
#define dump(x) cerr<<#x<<"="<<x<<endl
using P = pair<int, int>;

int main() {
    ll a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    if(a+b<=2*c){
        cout << a * x + b * y << endl;
    }
    else{
        if(x<y){
            ll tmp = 0;
            tmp = y - x;
            cout << min(x * 2 * c + tmp * b, 2 * c * y) << endl;
        }
        else{
            ll tmp = 0;
            tmp = x - y;
            cout << min(2* x * c, y * 2 * c + tmp * a) << endl;
        }
    }
    return 0;
}


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

int main(){
	// 入力受け取り
	int n, q;
	std::cin >> n >> q;
	std::vector<int> c(n);
	for(int i = 0; i < n; ++i){
		std::cin >> c[i];
		--c[i];
	}

	std::vector<int> prev(n);
	// prev[i] は， 0 <= j < i かつ c[i] == c[j] を満たす最大の j (存在しなければ -1)
	{
		std::vector<int> index(n, -1);
		for(int i = 0; i < n; ++i){
			prev[i] = index[c[i]];
			index[c[i]] = i;
		}
	}
	// デバッグ出力
	// for(int i = 0; i < n; ++i) std::cout << prev[i] << " ";
	// std::cout << std::endl;

	std::vector<int> next(n);
	// next[i] は， i < j < n かつ c[i] == c[j] を満たす最小の j (存在しなければ n)
	{
		std::vector<int> index(n, n);
		for(int i = n - 1; i >= 0; --i){
			next[i] = index[c[i]];
			index[c[i]] = i;
		}
	}
	// デバッグ出力
	// for(int i = 0; i < n; ++i) std::cout << next[i] << " ";
	// std::cout << std::endl;
	
	// 平方分割
	int blocksize = sqrt(n);
	int blocknum = n / blocksize + 1;
	std::vector<std::vector<int>> table(blocknum, std::vector<int>(blocknum));
	// table[i][j] (i < j) は，区間 [i * blocksize, j * blocksize) の種類数
	for(int i = 0; i < blocknum; ++i){
		int tmp = 0;
		for(int j = i * blocksize; j <= n; ++j){
			if(j % blocksize == 0){
				table[i][j / blocksize] = tmp;
			}
			tmp += prev[j] < i * blocksize;
		}
	}
	// デバッグ出力
	// for(int i = 0; i < blocknum; ++i){
	//	for(int j = 0; j < blocknum; ++j){
	//		std::cout << table[i][j] << " ";
	//	}
	//	std::cout << std::endl;
	// }

	for(int i = 0; i < q; ++i){
		int l, r;
		std::cin >> l >> r;
		--l;
		// [l, r) の種類数を答える
		int block_i = l / blocksize;
		int block_j = r / blocksize;
		int ans = table[block_i][block_j];
		for(int i = block_i * blocksize; i < l; ++i){
			ans -= next[i] >= block_j * blocksize;
		}
		for(int i = block_j * blocksize; i < r; ++i){
			ans += prev[i] < l;
		}
		std::cout << ans << std::endl;
	}
}


Measured memory_bytes: 11572
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
using namespace std;
typedef long long int ll;


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a; cin >> a;
    cout << a+a*a+a*a*a << endl;
}

Measured memory_bytes: 3580
# -*- coding: utf-8 -*-
if __name__ == '__main__':
    N = raw_input()
    A = map(int, raw_input().split())
    c_total = 1
    c_odd = 1
    for a in A:
        c_total *= 3
        if a % 2 == 0:
            c_odd *= 2
    print c_total - c_odd


Measured memory_bytes: 2568
N, M = map(int,input().split())
array = []
ans = []
for i in range(M):
    array.append(list(map(int, input().split()))+[i])
array.sort()
count = 1
for i in range(M):
    id_left = str(array[i][0])
    while len(id_left) < 6:
        id_left = '0' + id_left
    id_right = str(count)
    while len(id_right) < 6:
        id_right = '0' + id_right
    id = id_left + id_right
    ans.append([array[i][2],id])
    if i == M-1:
        break
    if array[i][0] != array[i+1][0]:
        count = 1
    else:
        count += 1
ans.sort()
for i in ans:
    print(i[1])

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

int n;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int seq = 0;
	bool ans = false;
	for(int i = 0; i < n; i++){
		int a, b;
		cin >> a >> b;
		seq = (a == b) ? seq + 1 : 0;
		if(seq >= 3) ans = true;
	}
	cout << (ans ? "Yes\n" : "No\n");
	return 0;
}


Measured memory_bytes: 3592
#include <cstdio>
#define F(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
int a[5]={10,10,10,10,10},n,m,s,c;
bool flag=false;
int main(){
	scanf("%d%d",&n,&m);
	F(i,1,m){
		scanf("%d%d",&s,&c);
		if(s==1&&c==0&&n>1)flag=true;
		if(s>3)flag=true;
		if(a[s]!=10&&a[s]!=c)flag=true;
		a[s]=c;
	}
	if(flag){
		printf("-1\n");
		return 0;
	}
	F(i,1,n)if(a[i]==10)a[i]=0;
	if(a[1]==0&&n!=1)a[1]=1;
	F(i,1,n)printf("%d",a[i]);
	printf("\n");
	return 0;
}


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

char S[100010] = {0};

int main()
{
    int g = 0,p = 0;
    scanf("%s",S);
    for(int i = 0; i < strlen(S); i++)
    {
        if(S[i] == 'g')
        {
            g++;
        }
        else
        {
            p++;
        }
    }
    printf("%d\n",(g - p) / 2);
}


Measured memory_bytes: 384
function main (input){
  input = input.split('');
  var a = input[0];
  var b = input[1];
  var c = input[2];
  let count = 0;
  
  if(a === '1'){
    count++;
  }
   if(b === '1'){
    count++;
  }
   if(c === '1'){
    count++;
  }
  console.log(count);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 29576
import qualified Data.ByteString.Char8 as C
import Data.List

main = C.interact $ put . sol . get

get = fmap (unfoldr (C.readInt . C.dropWhile (==' '))) . C.lines

put = C.pack . show

sol [[_,t],ts] = (t+) . sum $ zipWith ((min t .) . (-)) (tail ts) ts


Measured memory_bytes: 4988
#include<bits/stdc++.h>
#define rep(i, a, b) for(int (i)=(a);(i)<(b);(i)++)
#define drep(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)
#define MAGICLINE ios_base::sync_with_stdio(0)
#define pb push_back
#define mp make_pair
#define se second
#define fs first
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, pair<int, int> > PII;
typedef priority_queue<PII,
                       vector<PII>,
                       greater<PII> > dijQ;

const int MN = 3002;
int T[MN][MN];
short int aux[MN][MN];
stack<int> S;

int main(){
    string a, b; cin >> a >> b;
    rep(i, 0, a.size()){
        rep(j, 0, b.size()){
            if(a[i] == b[j]){
                T[i+1][j+1] = T[i][j]+1;
                aux[i+1][j+1] = 2;
            }
            else if(T[i][j+1] > T[i+1][j]){
                T[i+1][j+1] = T[i][j+1];
                aux[i+1][j+1] = 3;
            }
            else{
                T[i+1][j+1] = T[i+1][j];
                aux[i+1][j+1] = 1;
            }
        }
    }

int n = a.size(), m = b.size();

    while(n > 0 && m > 0){
        if(aux[n][m] == 2){
            S.push(n-1);
            n--; m--;
        }
        else if(aux[n][m] == 1) m--;
        else n--;
    }



    while(!S.empty()){
        cout << a[S.top()];
        S.pop();
    }
    cout << "\n";
    return 0;
}


Measured memory_bytes: 53120
n = int(input())
bfs = list(input())
s = list("ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ")
afs = []
for i in bfs:
    a = s.index(i)
    afs.append(s[a+n])
ans = "".join(afs)
print(ans)

Measured memory_bytes: 3188
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
using namespace std;

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

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long, long> PLL;
typedef long long LL;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

int d[1003];
int main(){
	int N,A,B,C;
	cin>>N>>A>>B>>C;
	
	REP(i,N)cin>>d[i];
	sort(d,d+N,greater<int>());
	int cost=A;
	int cal=C;
	double csp=(double)cal/cost;
	int cnt=0;
	while(cnt<N&&(double)(cal+d[cnt])/(cost+B)>csp){
		csp=(double)(cal+d[cnt])/(cost+B);
		cost+=B;
		cal+=d[cnt];
		cnt++;
	}
	
	cout<<(int)csp<<endl;
	return 0;
}

Measured memory_bytes: 1176
#include <iostream>
using namespace std;
int main() {
    int k, n;
    cin >> k >> n;
    int a[n+1];
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    a[n] = a[0] + k;
    int dist, max_dist = 0;
    for (int i=0; i<n; i++) {
        max_dist = max(a[i+1] - a[i], max_dist);
    }
    cout << k - max_dist << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define per(i,n) for (int i = (n)-1; i >=0; --i)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vv = vector<vi>;

int main(){
    int n,x;
    cin>>n>>x;
    vi a(n);
    rep(i,n)cin>>a[i];
    sort(a.begin(), a.end());
    
    int ans = 0;
    rep(i,n){
        if(x<a[i])break;
        x -= a[i];
        ans++;
        if(x>0 && i==n-1)ans--;
    }
    cout << ans << endl;
    return 0;
}

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

const ll logx=30;
const ll N=4e5+5;
const ll M=3e5+5;
const ll mod=1e9+7;
const ll INF=1e18+5;
const double PI = 3.14159265358979323846;

#define ints(n) scanf("%d",&n)
#define intp(n) printf("%d\n",n)
#define longs(n) scanf("%intd",&n)
#define longp(n) printf("%intd\n",n)

inline ll mul(ll a, ll b){ return (a * 1ll * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }

#define f first
#define s second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)
#define GCD(a,b) __gcd((a),(b))
#define all(v) v.begin(),v.end()
#define bits(x) __builtin_popcount(x)
#define LCM(a,b) ((a)*(b))/GCD((a),(b))
#define ms(dp,val) memset(dp,val,sizeof(dp))
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
template<typename T> T power(T x,T y,ll m){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1ll;x=(x*x)%m;}return ans%m;}

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

int main()
{
  ll n;
  string s;
  cin>>s;
  n=s.length();
  for(ll i=0;i<n-1;i++)
  {
    if(s[i]==s[i+1]){cout<<i+1<<" "<<i+2<<endl;exit(0);}
  }
  for(ll i=0;i<n-2;i++)
  {
    if(s[i]==s[i+2]){cout<<i+1<<" "<<i+3<<endl;exit(0);}
  }
  cout<<-1<<" "<<-1<<endl;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#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;
typedef pair<int,int> pii;
typedef vector<int> 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<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e8;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
	int n;
	cin>>n;
	string s;cin>>s;
	
	set<pii>se;
	rep(i,n)if(s[i]=='1'){
		pii t;t.second=i;
		while(i!=n&&s[i]=='1')i++;
		t.first=i;
		se.insert(t);
	}
	int q;
	cin>>q;
	while(q--){
		int a,b,c;cin>>a>>b>>c;
		a--;
		set<pii>::iterator it=se.upper_bound(pii(a,-inf));
		if(it==se.end()){
			if(c)se.insert(pii(b,a));
		}else if(c){
			if(it->second<a)a=it->second;
			while(1){
				if(it==se.end()||b<it->second)break;
				if(b<it->first){
					b=it->first;
					se.erase(it);
					break;
				}
				set<pii>::iterator it_t=it;
				it++;
				se.erase(it_t);
			}
			se.insert(pii(b,a));
		}else{
			bool h=false;
			pii tmp;
			if(it->second<a){
				h=true;
				tmp=pii(a,it->second);
//				se.insert(pii(a,it->second));
			}
			while(1){
				if(it==se.end()||b<=it->second)break;
				if(b<it->first){
					se.insert(pii(it->first,b));
					se.erase(it);
					break;
				}
				set<pii>::iterator it_t=it;
				it++;
				se.erase(it_t);
			}
			if(h)se.insert(tmp);
		}
//		for(set<pii>::iterator ite=se.begin();ite!=se.end();ite++)
//			cout<<ite->first<<" "<<ite->second<<endl;
//		cout<<endl;
		cout<<se.size()<<endl;
	}
}

Measured memory_bytes: 4204
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <bitset>
using namespace std;

int main(){
    long long N;
    cin >> N;
    string s = "";
    for(int i=0; i<40; i++){
        long long fac = 1LL<<i;
        if(((N+(1LL<<40)) % (2*fac)) == 0){
            s = '0' + s;
        }else{
            s = '1' + s;
            if(i%2==1)
                N += fac;
            else
                N -= fac;
        }
        if(N==0) break;
    }
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256