akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <functional>
using namespace std;

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

	vector<long long>Dsum(N + 1), Csum(N + 1);
	int d = 0;
	for (int i = 1; i <= N; i++)
	{
		Dsum[i] = Dsum[i - 1] + (S[i - 1] == 'D');
	}
	int c = 0;
	for (int i = 1; i <= N; i++)
	{
		Csum[i] = Csum[i - 1] + (S[i - 1] == 'C');
	}

	for (int i = 0; i < Q; i++)
	{
		int k; cin >> k;

		vector<long long>imos(N + 1);
		for (int j = 0; j < N; j++)
		{
			if (S[j] == 'D')
			{
				imos[j] += Csum[min(N, j + k)] - Csum[j];
			}
			else if (S[j] == 'C')
			{
				imos[j] -= Dsum[j] - Dsum[max(0, j - k + 1)];
			}

			//cerr<<j<<" "<<imos[j]<<endl;
		}

		for (int j = 1; j <= N; j++)imos[j] += imos[j - 1];

		long long ans = 0;
		for (int j = 0; j < N; j++)
		{
			if (S[j] == 'M') {
				//cerr<<j<<" "<<imos[j]<<endl;
				ans += imos[j];
			}
		}

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 24836
# -*- coding: utf-8 -*-
line = input().split(" ")
sx = int(line[0])
sy = int(line[1])
tx = int(line[2])
ty = int(line[3])

ret = []
# s->t
for _ in range(tx-sx):
    ret.append("R")
for _ in range(ty-sy):
    ret.append("U")

# t->s
for _ in range(tx-sx):
    ret.append("L")
for _ in range(ty-sy):
    ret.append("D")

# s->t
ret.append("D")
for _ in range(tx-sx+1):
    ret.append("R")
for _ in range(ty-sy+1):
    ret.append("U")
ret.append("L")

# t->s
ret.append("U")
for _ in range(tx-sx+1):
    ret.append("L")
for _ in range(ty-sy+1):
    ret.append("D")
ret.append("R")

print("".join(ret))


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main()
{ int n,k,ans=0,x;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(x<=k/2)
            ans+=x*2;
        else
            ans+=(k-x)*2;
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 256
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <random>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;
const Int INF = 1LL << 61;

Int Floor(Int a, Int b) {
    return (a - (a % b)) / b;
}

const Int alp = 26;

Int compute_score(Int D, vector<vector<Int>> s, vector<Int> c, vector<Int> &out) {
    Int score = 0;
    vector<Int> last(alp, 0);

    for (Int d = 0; d < out.size(); d++) {
        last[out[d]] = d + 1;

        for (Int i = 0; i < alp; i++) {
            score -= (d + 1 - last[i]) * c[i];
        }
        score += s[d][out[d]];
    }

    return score;
}

vector<Int> solve(Int D, vector<vector<Int>> s, vector<Int> c) {
    vector<Int> out;

    for (Int _ = 0; _ < D; _++) {
        Int max_score = -INF;
        Int best_i = 0;

        for (Int i = 0; i < alp; i++) {
            out.push_back(i);

            Int score = compute_score(D, s, c, out);
            if (max_score < score) {
                max_score = score;
                best_i = i;
            }

            out.pop_back();
        }

        out.push_back(best_i);
    }

    return out;
}

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

    Int D;
    cin >> D;
    vector<Int> c(alp);
    vector<vector<Int>> s(D, vector<Int>(alp));
    for (Int i = 0; i < alp; i++) {
        cin >> c[i];
    }
    for (Int i = 0; i < D; i++) {
        for (Int j = 0; j < alp; j++) {
            cin >> s[i][j];
        }
    }

    auto ans = solve(D, s, c);
    for (auto e : ans) {
        cout << e + 1 << endl;
    }

    return 0;
}


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

int main() {
  int n;
  cin >> n;
  
  set<char> s;
  char c;
  for(int i = 0; i < n; i++){
    cin >> c;
    s.insert(c);
  }
  string val = s.size() > 3 ? "Four" : "Three"; 
  cout << val;
}

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

int main(){
	string S;
	cin >> S;
	int K, N = S.size(), i, j;
	scanf("%d", &K);
	vector<int> A(N + 1, 0);
	for(i = 1; i <= N; i++){
		A[i] = S[i - 1] - '0';
	}
	vector<vector<int>> dp_less(N + 1, vector<int>(K + 1, 0));
	vector<vector<int>> dp_eq(N + 1, vector<int>(K + 1, 0));
	dp_eq[0][0] = 1;
	for(i = 1; i <= N; i++){
		dp_less[i][0] = 1;
		dp_eq[i][0] = 0;
		for(j = 1; j <= K; j++){
			dp_less[i][j] = dp_less[i - 1][j] + 9 * dp_less[i - 1][j - 1];
			if(A[i] > 0){
				dp_less[i][j] += dp_eq[i - 1][j] + (A[i] - 1) * dp_eq[i - 1][j - 1];
			}
			if(A[i] == 0){
				dp_eq[i][j] = dp_eq[i - 1][j];
			}
			else{
				dp_eq[i][j] = dp_eq[i - 1][j - 1];
			}
		}
	}
	printf("%d\n", dp_less[N][K] + dp_eq[N][K]);
	return 0;
}

Measured memory_bytes: 256
import java.util.*


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)

    var N: Long
    N = sc.nextLong()
    val l = Array((N).toInt()){0L}
    val r = Array((N).toInt()){0L}
    for (i in 0 until N) {
        l[(i).toInt()] = sc.nextLong()
        r[(i).toInt()] = sc.nextLong()
    }
    solve(N, l, r)
}

fun solve(N: Long, l: Array<Long>, r: Array<Long>) {
    var res = 0L
    for (i in l.indices) {
        res += r[i] - l[i] + 1
    }
    println(res)
}



Measured memory_bytes: 36012
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
#include <deque>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef map<int,int> mint;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef deque<pair<int,int>> dep;
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int inf=1e9+1000;
ll infi=1e18+100;

//x=10111;
//x<<2 = 1011100 (右シフト),x>>2 = 101 (左シフト)
//(x>>2)&1 = 101 & 001 = 1
//iビット目は、(x>>i) & 1 でわかる(x>>i)%2 でもよい
ll A,B,C,X,Y;
ll kakaku[3];

int main(){
	cin>>A>>B>>C>>X>>Y;
	
	kakaku[0]=A*X+B*Y;
	kakaku[1]=2*C*min(X,Y)+max(A*(X-min(X,Y)),B*(Y-min(X,Y)));
	kakaku[2]=2*C*max(X,Y);
	sort(kakaku,kakaku+3);
	cout<<kakaku[0]<<endl;
	
	  return 0;
  }

Measured memory_bytes: 256
N,K = list(map(int,input().split(" ")))
As = list(map(int,input().split(" ")))
ans = 0
MOD = 10 ** 9 + 7
for i in range(N): # i番目の数字
  left = 0
  right = 0
  temp = As[i]
  for j in range(0,i): #左側
    if temp <As[j]:
      left += 1
  ans += left*(K)*(K+1)//2
  ans %= MOD
  for j in range(i + 1,N):
    if temp <As[j]:
      right += 1
  ans += right*(K)*(K - 1)//2
  ans %= MOD
print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
template<class T> bool chmax(T& a,T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T& a,T b) { if (a > b) { a = b; return true; } return false; }

int main() {
    int n;
    cin >> n;
    vector<long long> a(n + 1), b(n);
    for (auto &e : a) cin >> e;
    for (auto &e : b) cin >> e;
    
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        const long long d = min(a[i], b[i]);
        ans += d;
        a[i] -= d;
        b[i] -= d;
        ans += min(a[i + 1], b[i]);
        a[i + 1] -= min(a[i + 1], b[i]);
    }
    
    cout << ans << '\n';
    
    return 0;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> C(H, vector<char>(W));
  rep(i, H) rep(j, W) cin >> C[i][j];
  
  vector<vector<char>> ans(2*H, vector<char>(W));
  rep(i, 2*H) {
    rep(j, W) {
      ans[i][j] = C[i/2][j];
      cout << ans[i][j];
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,-1,1};
char a[1010][1010];
bool vis[1010][1010];
int ans[1010][1010];
queue<pair<int,int> > q;
int main(){
	memset(ans,0,sizeof(ans));
	memset(vis,1,sizeof(vis));
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			if(a[i][j]=='#')q.push(make_pair(i,j));
			else if(a[i][j]=='.')vis[i][j]=0;
		}
	}
	while(!q.empty()){
		pair<int,int> t=q.front();
		q.pop();
		int x=t.first;
		int y=t.second;
		for(int i=0;i<4;i++){
			int ax=x+dx[i];
			int ay=y+dy[i];
			if(ax>=0&&ax<n&&ay>=0&&ay<m&&!vis[ax][ay]){
				ans[ax][ay]=ans[x][y]+1;
				vis[ax][ay]=1;
				q.push(make_pair(ax,ay));
			}
		}
	}
	int cnt=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cnt=max(cnt,ans[i][j]);
		}
	}
	cout<<cnt<<endl;
	return 0;
}

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

#define N 100000
#define N2 262144

int nnum, nnum2, nmaps[N], nmap[N], sib[N], chil[N];
int wei[N2], lazy[N2];

void buildstree(int i) {
  static int ni = nnum2 - 1;
  int c = chil[i];
  nmaps[i] = ni;
  while (c != -1) {
    buildstree(c);
    c = sib[c];
  }
  nmap[i] = ni++;
  return;
}

void updaterange(int s, int t, int i, int l, int r, int x) {
  if (s <= l && r <= t) {
    wei[i] += x;
    return;
  }
  if (t <= l || r <= s) return;
  updaterange(s, t, i * 2 + 1, l, (l + r) / 2, x);
  updaterange(s, t, i * 2 + 2, (l + r) / 2, r, x);
}

void addWeight(int i, int w) {
  updaterange(nmaps[i] - nnum2 + 1, nmap[i] - nnum2 + 2, 0, 0, nnum2, w);
}
void getSum(int i) {
  int j = i;
  int val = 0;

  while (j > 0) {
    if (wei[j] != 0) val += wei[j];
    j = (j - 1) / 2;
  }
  cout << val << endl;
}

int main() {
  int k, c, qnum, x, y, z, last;

  cin >> nnum;
  nnum2 = 1;
  while (nnum > nnum2) nnum2 *= 2;
  for (int i = 0; i < nnum2 * 2; i++) {
    wei[i] = lazy[i] = 0;
  }
  for (int i = 0; i < nnum; i++) {
    last = -1;
    cin >> k;
    for (int j = 0; j < k; j++) {
      cin >> c;
      sib[c] = last;
      last = c;
    }
    chil[i] = last;
  }

  buildstree(0);

  cin >> qnum;
  for (int i = 0; i < qnum; i++) {
    cin >> x >> y;
    if (x == 0) {
      cin >> z;
      addWeight(y, z);
    } else {
      getSum(nmap[y]);
    }
  }

  return 0;
}



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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }



int main(){
    string s;
    cin >> s;
    int tot = 0;
    int n = sz(s);
    rep(i,n) {
        int c = s[i] - '0';
        tot += c;
    }
    YesorNo(tot % 9 == 0);
}

Measured memory_bytes: 3812
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{
long long a,b,c,d,e,f;
scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
if (a>b)
{
    e=a;
    a=b;
    b=e;
}
if (c>d)
{
    e=c;
    c=d;
    d=e;
}

//if (c%2==0)
printf("%lld",a+c);
//else
//printf("%lld",c*2);
}


Measured memory_bytes: 1716
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5005,p=1000000007,inv2=(p+1)/2,inf=0x3f3f3f3f;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,cnt1,cnt2,pos1[N],pos2[N],ans;
char a[N],b[N];
int main(){
	n=read();
	scanf("%s %s",a+1,b+1);
	a[0]=b[0]='0';
	for (int i=1;i<=n;i++){
		if (a[i]!=a[i-1]) pos1[++cnt1]=i;
		if (b[i]!=b[i-1]) pos2[++cnt2]=i;
	}
	ans=0x3f3f3f3f;
	for (int d=-cnt2;d<=cnt1;d++)
	if (d%2==0){
		int x=1,y=1;
		if (d<0) y+=d;
		else x-=d;
		int t=0;
		while ((x<=cnt1)||(y<=cnt2)){
			int tx=(x<1) ? 1 : ((x<=cnt1) ? pos1[x] : (n+1));
			int ty=(y<1) ? 1 : ((y<=cnt2) ? pos2[y] : (n+1));
			t+=abs(tx-ty);
			x++;y++;
		}
		ans=min(ans,t);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val scanner = Scanner(System.`in`)
    scanner.nextInt()
    val k = scanner.nextInt()
    val s = scanner.next()
    s.forEachIndexed { i, c ->
        if ((i + 1) == k) print(c.toLowerCase())
        else print(c)
    }
}


Measured memory_bytes: 29600
using System;
using System.Linq;

public class Program
{
    private int N;
    private int[] B;

    public void Solve()
    {
        var sc = new Scanner();
        N = sc.NextInt();
        B = sc.IntArray();

        long ans = B[N-2]+B[0];

        for (int i = N - 2; i >= 1; i--)
        {
            ans += Math.Min(B[i], B[i - 1]);
        }
        Console.WriteLine(ans);
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

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

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int w[n];
    w[0]=0;
    int e[n];
    e[0]=0;
    if(s[0]=='W') w[0]++;
    else e[0]++;
    for(int i=1;i<n;i++){
        if(s[i]=='W'){
            w[i]=w[i-1]+1;
            e[i]=e[i-1];
        }
        else{
            w[i]=w[i-1];
            e[i]=e[i-1]+1;
        }
    }
    int ans=1000000;
    int count;
    for(int i=0;i<n;i++){
        count=w[i-1]+e[n-1]-e[i];
        ans=min(ans,count);
    }
    cout << ans << endl;
}

Measured memory_bytes: 2948
#include <bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323
#define ll long long int
#define vi vector <int>
#define vl vector <ll>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define MOD 1000000007
ll power(ll a, ll b) { //a^b
	ll res = 1;
	while (b > 0) {
		if (b & 1) {res = (res * a); b--;}
		a = (a * a);
		b >>= 1;
	}
	return res;
}
ll n;
ll gcd(ll a, ll b) {return (b == 0) ? a : gcd(b, a % b);}

ll dp[3001][3001][2];
vector <ll> v(3001);

ll solve(ll i,ll j,ll t){
	if(dp[i][j][t]!=10000000000000)
		return dp[i][j][t];
	if(i==j){
		return dp[i][j][t]=v[i]*(t%2==0?1:0);
	}
	if(t%2==0){
		dp[i][j][t]=max(v[i]+solve(i+1,j,1),v[j]+solve(i,j-1,1));
	}
	else{
		dp[i][j][t]=min(solve(i+1,j,0),solve(i,j-1,0));
	}
	return dp[i][j][t];
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for(ll i=0;i<2;i++){
		for(ll j=0;j<3001;j++){
			for(ll k=0;k<3001;k++)
				dp[j][k][i]=10000000000000;
		}
	}
	//cout<<dp[0][0][0]<<endl;
	cin>>n;
	ll sum=0;
	for(ll i=0;i<n;i++){
		cin>>v[i];
		sum+=v[i];
	}
	ll ans=solve(0,n-1,0);
	cout<<2*ans-sum<<"\n";
}

Measured memory_bytes: 144556
#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, a, n) for(int i=a; i<n; i++)
#define ll long long
#define all(x) begin(x), end(x)
#define toInt(x) (x - '0')
#define pll pair<ll, ll>
#define pli pair<ll, int>
// #define int long long
const int inf = 1 << 30;
#define INF 1e+9
#define MAX_V 100008


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

vector<int> binary(long long bina){
    vector<int> res;
    for (ll i = 0; bina>0 ; i++)
    {
        // ans = ans+(bina%26)*pow(10,i);
        long long n = (bina % 26 == 0) ? 26 : bina % 26;
        if(bina % 26 == 0){
          res.push_back(26);
        }else{
          res.push_back(bina%26);
        }
        bina = (bina - n)/26;
    }
    return res;
}

int main(){
  long long n;
  cin >> n;
  // n--;
  // cout << n << endl;
  vector<int> res = binary(n);
  // for (auto it:res){
  //   cout << it << endl;;
  // }
  // cout << endl;
  string s = "";
  for(int i=0; i<res.size(); i++){
    if(res[i] != 0){
      s.push_back(res[i] - 1 + 'a');
    }else{
      s.push_back('z');
    }
  }
  reverse(s.begin(), s.end());

  cout << s << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>

using namespace std;

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

  int cnt = 0;
  for(int i = 1; i <= stoi(n); i++) {
    string s = to_string(i);
    if(s.size() % 2 != 0) cnt++;
    i = stoi(s);
  }  
  cout << cnt << endl;
}

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

int main() {
	int x,y;
	int i = 1;
	do {
		cin >> x >> y;
		if ((x == 0 && y == 0) || x > 10000 || y > 10000)break;
		if(x < y)
			cout << x << " " << y << endl;
		else
			cout << y << " " << x << endl;
		i++;
	} while (i <= 3000);
	return 0;
}


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

int main() {
  string s;
  cin>>s;
  int n;
  cin>>n;
  int count=0;
  deque<char>q;
  for(int i=0;i<s.size();i++){
    q.push_back(s[i]);
  }
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    if(a==2){
      int b;
      cin>>b;
      char c;
      cin>>c;
      //cout<<b<<" "<<c<<endl;
      if(b==1&&count%2==0){
        q.push_front(c);
      }else if(b==1&&count%2==1){
        q.push_back(c);
      }else if(b==2&&count%2==0){
        q.push_back(c);
      }else if(b==2&&count%2==1){
        q.push_front(c);
      }
    }else if(a==1)count++;
  }
  if(count%2==1)reverse(q.begin(),q.end());
  //cout<<q.size()<<endl;
  for(int i=0;i<q.size();i++){
    cout<<q[i];
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 896
#include<iostream>
#define ll long long
using namespace std;
const ll mod=1e9+7;
ll mi(ll a,ll b){
	ll x=1;
	while(b){
		if(b&1) x=x*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return x;
}
int main(){
	int n;
	cin>>n;
	ll ans=(mi(10,n)-mi(9,n)-mi(9,n)+mi(8,n))%mod;
	ans=(ans+mod)%mod;
	cout<<ans<<endl;
	return 0;
}

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

int main(){
  string str;  
  cin >> str;
    
  int lc = 0;
  int max_lc = 0;
  for(int i = 0 ; i < int(str.size()) ;++i){
    if( str[i]=='A' || str[i] =='C' || str[i] =='G' || str[i]=='T'){
      lc++;
    }
    else{
      if (lc > max_lc){
        max_lc=lc;
      }
      lc=0;
    }
  }
  if (lc > max_lc){
 	max_lc=lc;
  }

 cout << max_lc;  
}

Measured memory_bytes: 256
#define D(x) cout << #x " = " << x << endl
#define DD(x, y) cout << "(" #x ", " #y ") = (" << x << ", " << y << ")" << endl
#define DDD(x, y, z) cout << "(" #x ", " #y ", " #z ") = (" << x << ", " << y << ", " << z << ")" << endl
#define DV(v) for (auto __macro_vi : v){ cout << __macro_vi << " ";} cout << endl;
#define DA(a, n) for (int __macro_i = 0; __macro_i < n; ++__macro_i) { cout << a[__macro_i] << " "; } cout << endl;
#define REP(i, n) for (int i = 0; i < n; ++i)
#define ALL(v) (v).begin(), (v).end()
#include<iostream>
#include<vector>
#include<cassert>
#include<cmath>
#include<map>

using namespace std;
using P = pair<int, int>;
vector<vector<P>> v;

int n, m;
int main()
{
    cin >> n >> m;
    v.resize(m);
    vector<int> tmp(n);
    REP(i, n) {
        cin >> tmp[i];
    }
    sort(tmp.begin(), tmp.end());
    for (auto ai : tmp) {
        int md = ai % m;
        if (v[md].size() != 0 && (*v[md].rbegin()).second == ai && (*v[md].rbegin()).first < 2) {
            (*v[md].rbegin()).first++;
        } else {
            v[md].push_back(make_pair(1, ai));
        }
    }
    int ans = 0;
    for (int md = 0; md <= m / 2; ++md) {
        if (md == 0 || md * 2 == m) {
            // D(md);
            int sm = 0; for (auto vi : v[md]) sm += vi.first;
            ans += sm / 2;
        } else {
            int r = m - md;
            sort(v[md].begin(), v[md].end());
            sort(v[r].begin(), v[r].end());
    
            int i = 0, j = 0;
            while (i < v[md].size() && j < v[r].size()) {
                ans += 1;
                v[md][i].first--;
                if (v[md][i].first == 0) i++;
                v[r][j].first--;
                if (v[r][j].first == 0) j++;
            }

            for (auto vi : v[md]) if (vi.first == 2) ans++;
            for (auto vi : v[r]) if (vi.first == 2) ans++;
        }
    }
    cout << ans << endl;
}


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

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

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

  int h, w;
  cin >> h >> w;
  int n;
  cin >> n;
  vector<int> xs(n);
  for (int i = 0; i < n; i++) {
    cin >> xs[i];
  }

  auto output = Make2DVector(h, w, -1);
  int s = 0;
  for (int i = 0; i < n; i++) {
    int t = s + xs[i];
    // Fill [s, t)
    for (int k = s; k < t; k++) {
      int r = k / w;
      int c = k % w;
      if (r % 2 == 1) c = w - 1 - c;
      output[r][c] = i + 1;
    }

    s = t;
  }

  for (int r = 0; r < h; r++) {
    for (int c = 0; c < w; c++) {
      cout << output[r][c] << " ";
    }
    cout << endl;
  }
}

Measured memory_bytes: 384
s = input()
n = int(input())

for i in range(n):
    command = list(input().split())

    if command[0] == 'replace':
        a = int(command[1])
        b = int(command[2]) + 1
        s = s[:a] + command[3] + s[b:]
    elif command[0] == 'reverse':
        a = int(command[1])
        b = int(command[2]) + 1
        s = s[:a] + s[a:b][::-1] + s[b:]
    else:
        a = int(command[1])
        b = int(command[2]) + 1
        print(s[a:b])



Measured memory_bytes: 5612
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def rank(m, f, r):
        if m == -1 or f == -1:
            return "F"
        total = m + f
        if total >= 80:
            return "A"
        if total >= 65:
            return "B"
        if total >= 50:
            return "C"
        if total >= 30:
            if r >= 50:
                return "C"
            else:
                return "D"
        return "F"

    m, f, r = map(int, input().split())
    while (m, f, r) != (-1, -1, -1):
        print(rank(m, f, r))
        m, f, r = map(int, input().split())

main()



Measured memory_bytes: 5604
#include<stdio.h>

int main(void)
{
 int a,a2,b,b2,s=0;

 scanf("%d %d",&a,&b);

 a2=a-1;

 b2=b-1;

 if(a > b && a2 > b)

 s=a+a2;

 else if(a > b && a2 < b)

 s=a+b;

 else if(a > b && a2 == b)

 s=a+b;

 else if(a < b && a < b2)

 s=b+b2;

 else if(a < b && a == b2)

 s=b+a;

 else
 s=b+a;

 printf("%d",s);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <math.h>
#include <float.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
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; }
// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
const int MOD = 1000000007;


int main(){
    int K, X; cin >> K >> X;

    vector<int> ans;
    for(int i = X-K+1; i <= X+K-1; i++){
        ans.push_back(i);
    }

    rep(i, ans.size()){
        cout << ans[i];
        if (i == ans.size()-1){
            cout << endl;
        }
        else{
            cout << " ";
        }
    }
}

Measured memory_bytes: 3644
require "bigdecimal"
require "bigdecimal/util"

def gi() gets.to_i end
def gs() gets.chomp end
def gmi() gets.split.map(&:to_i) end
def gms() gets.split.map(&:chomp) end
def YesNo1(bool, yes="Yes", no="No") puts (bool ? yes : no) end
def YESNO2(bool, yes="YES", no="NO") puts (bool ? yes : no) end

def comb(n,k)
  return nil if k > n
  result = 1
  1.upto() do |d|
    result *= n
    result /= d
    n -= 1
  end
  result
end

def perm(n,k)
  return nil if k > n
  result = 1
  k.times do
    result *= n
    n -= 1
  end
  result
end

def kaibun(str)
  str == str.reverse
end

#####
n,k = gmi
trees = []
n.times do
  trees.push(gi)
end
trees.sort!
#print trees

min = 1000000000
(n-k+1).times do |i|
  #puts i
  #puts trees[i+k-1] - trees[i]
  min = [min,trees[i+k-1] - trees[i]].min
end
puts min

Measured memory_bytes: 3760
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
# define rep(i,n) for(int i=0;i<n;i++)
void solve(){
    int n;
    cin>>n;
    vector<lli> a(n);
    rep(i,n)
    cin>>a[i];
    sort(a.begin(),a.end());
    int cnt =0 ;
    for(int i=0;i<n-2;i++){
        for(int j=i+1;j<n-1;j++){
            for(int k=j+1;k<n;k++){
                int x =a[i],y= a[j] ,z =a[k];
                if( x!=y && y!=z && z!=x &&x+y>z && y+z >x && z+x>y)
                cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    

}



int main()
{
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
}

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

int main(){
   int n; cin>>n;
   int cnt=0;
   for(int i=1;i<=n;i++){
      if(to_string(i).length()%2==1) cnt++;
   }
   cout<<cnt<<endl;
   return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>  // Including tree_order_statistics_node_update

using namespace __gnu_pbds;
using namespace std;

#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c, i) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c), x) != (c).end())
#define minei(x) min_element(x.begin(), x.end()) - (x).begin()
#define maxei(x) max_element(x.begin(), x.end()) - (x).begin()
#define LSOne(S) (S & (-S))

#define uns(v) sort((v).begin(), (v).end()), v.erase(unique(v.begin(), v.end()), v.end())
#define acusum(x) accumulate(x.begin(), x.end(), 0)
#define acumul(x) accumulate(x.begin(), x.end(), 1, multiplies<int>());
#define bits(x) __builtin_popcount(x)
#define oo INT_MAX
#define inf 1000000000
#define MAXN 1000007
#define MOD 1000000007

const double pi = acos(-1.0);
const double eps = 1e-11;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

int main() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll x;
    ll st = 100;
    ll res = 0;
    cin >> x;
    while (st < x) {
        st += (st / 100);
        res++;
    }
    cout << res << endl;

    return 0;
}


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




int main(){
    long double L;
    cin >> L;
    cout << fixed << setprecision(15) << L*L*L/27 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cmath>
#include <cstdlib>

typedef long long ll;
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

using namespace std;

int main(void) {
    int n;
    cin >> n;
    int h[n];
    REP(i, n) cin >> h[i];

    int cnt = 1;
    FOR(i, 1, n) {
        bool flag = true;
        REP(j, i) {
            if (h[j] > h[i]) flag = false;
        }
        if (flag) cnt++;
    }
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <math.h>
#include <limits>

template <typename T>
void vc(T t) {
    std::cout << t << " ";
}

template<typename T, typename... Args>
void vc(T t, Args... args) {
// recursive variadic function
    std::cout << t << " ";
    vc(args...) ;
}

const int N = 100000;

int dp[3001][3001];
void once() {
  std::string s1, s2;
  std::cin >> s1 >> s2;
  for (int i = 1; i <= s1.length(); ++i) {
    for (int j = 1; j <= s2.length(); ++j) {
      if (s1[i - 1] == s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  std::string s;
  int i = s1.length();
  int j = s2.length();
  while (i && j) {
    if (s1[i - 1] == s2[j - 1]) {
      s += s1[i - 1];
      i--;
      j--;
      continue;
    }
    if (dp[i][j] == dp[i - 1][j]) {
      i--;
    } else {
      j--;
    }
  }
  std::reverse(s.begin(), s.end());
  std::cout << s << std::endl;
}

int
main() {
  int n = 1;
  std::ios::sync_with_stdio(false);
  // std::cin >> n;
  while (n--) {
    once();
  }
}

Measured memory_bytes: 35456
#include<iostream>
#include <string.h>
#include<stdio.h>
#include <math.h>
using namespace std;

int main() {
	int N;
	string S, T, ans;
	cin >> N;

	cin >> S >> T;

	for (int i = 0; i < N; i++) {
		cout << S[i] << T[i];
	}

	cout << endl;

	return 0;
}









Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define ALL(v) v.begin(),v.end()

int main(int argc, char const *argv[])
{
    string s;
    cin >> s;
    map<char, ll> m;
    for (ll i = 0; i < s.size(); i++)
    {
        m[s[i]]++;
    }

    if (m['N'] != 0)
    {
        if (m['S'] == 0)
        {
            cout << "No" << endl;
            exit(0);
        }
    }
    if (m['S'] != 0)
    {
        if (m['N'] == 0)
        {
            cout << "No" << endl;
            exit(0);
        }
    }
    if (m['E'] != 0)
    {
        if (m['W'] == 0)
        {
            cout << "No" << endl;
            exit(0);
        }
    }
    if (m['W'] != 0)
    {
        if (m['E'] == 0)
        {
            cout << "No" << endl;
            exit(0);
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
#include<stack>
#include<string.h>
#include<list>
#include<limits>
#include<bitset>
#include<ctype.h>
#include<set>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
const ll MOD=1000000007;
const ll INF=1000000000;
const int MAX=100001;
const double EPS=1e-10;
using namespace std;
int main() {
    int n;
    cin>>n;
    vector<string> s;
    vector<string> t;
    for(int i=0;i<n;i++){
        string ss;
        cin>>ss;
        s.push_back(ss);
    }
    int ma;
    cin>>ma;
    for(int i=0;i<ma;i++){
        string ss;
        cin>>ss;
        t.push_back(ss);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        int m=0;
        for(int j=0;j<n;j++){
            if(s[j]==s[i]){
                m++;
            }
        }
        for(int j=0;j<ma;j++){
            if(s[i]==t[j]){
                m--;
            }
        }
        ans=max(ans,m);
    }
    cout<<ans<<endl;
}








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

int div(int n) {
  if (n>=0) {
    return -n/2;
  }
  else if (-n%2==0) return -n/2;
  else return ((-n)/2)+1;
}

int amari(int n) {
  if (n<0) {
    return ((-n)%2);
  }
  else return n%2;
}


int main() {
  int n;
  cin >> n;
  stack<int> s;
  if (n==0) cout << 0 << endl;
  
  while(n!=0) {
    s.push(amari(n));
    n = div(n);
    
  }
  while(!s.empty()) {
    cout << s.top();
    s.pop();
  }
}
  

Measured memory_bytes: 256
import copy
S = list(input())
s = copy.copy(S)
p = len(S) - 1
ans = 0
for i in range(2**p):
    s = copy.copy(S)
    
    for j in range(p):
        if((i >> j) & 1):
            s.insert(p - j, "+")
            
    tmp = "".join(s)
    ans += eval(tmp)

print(ans)


Measured memory_bytes: 3444
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;

int main(){

    int x,a;
    cin >> x >> a;
    if(a > x){
        cout << 0 << endl;
    } else {
        cout << 10 << endl;
    }

}

Measured memory_bytes: 3616
#include <iostream>
#include <sstream>
#include <string>

using namespace std;

constexpr int n = 10;
int L[n+2],P[n];
int main(){
  string str;
  while(getline(cin,str)){
    string tmp;
    istringstream stream(str);
    for(int i=0;getline(stream,tmp,',');++i){
      L[i] = stod(tmp);
    }
    P[0] = L[0];
    for(int i=1;i<n;++i) P[i] = P[i-1] + L[i];
    int v1 = L[n],v2 = L[n+1];

    double p = (double)P[n-1]/(v1+v2)*v1;
    
    for(int i=0;i<n;++i){
      if(p<=P[i]){
        cout << i+1 << endl;
        break;
      }
    }

  }
}

Measured memory_bytes: 3148
#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 2010
#define MOD 998244353
using namespace std;
typedef long long ll;
ll C[2*MAXN][2*MAXN],bits[2*MAXN];
int n,k;

ll count(int s,int tot){
    return C[s+tot-1][s-1]; 
}

ll solve(int i,int tot){
    int k2=min(k-i/2,(i-1)/2);
    int k1=k-k2*2-((i%2)==0);
    ll flag=1;
    ll res=0;
    for(int l=k2;l+k1>0&&l>=0;l--,flag=-flag){
        res+=flag*count(l+k1,tot)*bits[l]%MOD*C[k2][l]%MOD;
        res%=MOD;
    }
    return (res+MOD)%MOD;
}

int main(){
    SF("%d%d",&k,&n);
    int sum=0;
    bits[0]=1;
    for(int i=1;i<=4000;i++)
        bits[i]=bits[i-1]*2ll%MOD;
    C[0][0]=1;
    for(int i=1;i<=4000;i++){
        C[i][0]=1;
        for(int j=1;j<=i;j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
    }
    ll ans=0;
    for(int i=2;i<=2*k;i++){
        if(i%2==0){
            ans=(solve(i,n)+solve(i,n-1))%MOD;
        }
        else{
            ans=solve(i,n);
        }
        PF("%lld\n",ans);
    }
}


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

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

	double dp[n+1][2*n+1];
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= 2*n; j++){
			dp[i][j] = 0;
		}
	}
	dp[0][n] = 1;

	for(int i = 1; i <= n; i++){
		double p;
		cin >> p;
		dp[i][0] = dp[i-1][1] * (1 - p);
		dp[i][2*n] = dp[i-1][2*n-1] * p;
		for(int j = 1; j < 2*n; j++){
			dp[i][j] = dp[i-1][j-1] * p + dp[i-1][j+1] * (1 - p);
		}
	}

	double ans = 0;
	for(int i = n+1; i <= 2*n; i++){
		ans += dp[n][i];
	}

	printf("%2.15f\n",ans);

	return 0;
}


Measured memory_bytes: 140800
#include <iostream>
#include <cstring>
using namespace std;
char s[200002];
long long S, nr, x;

int main()
{
    cin.getline(s+1, 200002);
    nr=strlen(s+1);

    for(int i=1; i<=nr; i++)
    {
        x=s[i]-'0';
        S+=x;
    }

    if(S%9==0) cout<<"Yes";
    else cout<<"No";


    return 0;
}


Measured memory_bytes: 3724
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue> //priority_queue
#include <map>
#include <set> //multiset set<int,greater<int>>大到小
#include <vector>// ::iterator it;
#include <stack>
#include <cmath> // auto &Name : STLName  Name.
#include <utility>
#include <sstream>
#include <string>
#define mod 1000000007
#define mod9 998244353
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;
const db eps=1e-10;
const int INF = 0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+5;
using namespace std;

ll t,n,m,k;
ll dp[15][15]={0};
int main(){
    scanf("%lld",&n);
    for(int i=0;i<10;i++){
        dp[1][i]=1;
    }
    for (int i=2;i<=10;i++){
        for (int j=0;j<=9;j++){
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1];
        }
    }
    vector<int> v;
    int l=0,r=0,flag=0;
    for(int i=1;i<=10;i++){
        for(int j=1;j<10;j++){
            if(n<=dp[i][j]){
                l=i,r=j,flag=1;
                break;
            }
            n-=dp[i][j];
        }
        if(flag) break;
    }
    l--;
    v.push_back(r);
    while(l!=0){
        if(n<=dp[l][r-1]){
            r--;
            v.push_back(r);
        }else{
            n-=dp[l][r-1];
            if(n<=dp[l][r]) v.push_back(r);
            else{
                n-=dp[l][r];
                r++;
                v.push_back(r);
            }
        }
        l--;
    }
    for(int i=0;i<v.size();i++){
        printf("%d",v[i]);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 256
# your code goes here
import sys

while True:
	n = input()
	if n == 0: break
	convDict = {};
	for _ in range(n):
		src, dest = raw_input().split();
		convDict[src] = dest;

	m = input()
	for _ in range(m):
		c = raw_input().rstrip()
		if c in convDict.keys():
			c = convDict[c];
		sys.stdout.write(c)
	print

Measured memory_bytes: 9040
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	string s;cin>>s;
	if (s=="zyxwvutsrqponmlkjihgfedcba"){
		cout << -1 << endl;
		return 0;
	}
	int n = s.size();
	int index = -1;
	char m;
	vector<bool> cnt(26,false);
	if (n < 26){
		for(int i = 0; i < n; i++) {
			cnt[s[i] - 'a'] = true;
		}
		for(int i = 0; i < 26; i++) {
			if (cnt[i] == false){
				m = char('a' + i);
				break;
			}
		}
		cout << s << m << endl;
	}
	else{
		for(int i = n - 1; i >= 0; i--) {
			if (s[i] > s[i + 1]){
				cnt[s[i] - 'a'] = true;
			}
			else{
				cnt[s[i] - 'a'] = true;
				for(int j = 0; j < i; j++) {
					cout << s[j];
				}
				for(int j = 25; j >= 0; j--) {
					if (cnt[j] && s[i] - 'a' < j){
						m = char('a' + j);
					}
				}
				cout << m << endl;
				break;

			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
// Wrote after ended the contest
using System;
using System.Linq;
public class Program {
  public static void Main() {
    int N = int.Parse(Console.ReadLine());
    int[][] red = new int[N][];
    int[][] blue = new int[N][];
    for (int i = 0; i < N; i++) red[i] = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    for (int i = 0; i < N; i++) blue[i] = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    red = red.OrderByDescending(a => a[1]).ToArray();
    blue = blue.OrderBy(a => a[0]).ToArray();

    int count = 0;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (red[j] == null) continue;
        if (red[j][0] < blue[i][0] && red[j][1] < blue[i][1]) {
          count++;
          red[j] = null;
          break;
        }
      }
    }
    Console.WriteLine(count);
  }
}


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

int main() {
    int K, T;
    cin >> K >> T;
    vector<P> a(T);
    rep(i, T) {
        int tmp;
        cin >> tmp;
        a[i] = make_pair(tmp, i);
    }

    if (T == 1) {
        cout << K - 1 << endl;
        return 0;
    }

    int ans = 0;
    int pre_a = -1;
    rep(i, K) {
        sort(a.begin(), a.end(), greater<>());

        if (a[0].second != pre_a) {
            --a[0].first;
            pre_a = a[0].second;
        } else {
            if (a[1].first == 0) {
                ans = a[0].first;
                break;
            } else {
                --a[1].first;
                pre_a = a[1].second;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3544
#include<iostream>
#include<cstring> 
using namespace std; 
int main() 
{
  string b;
  cin>>b;
  int k=b.size(); 
  if(b[0]==b[k-1]) 
  { 
    if(k%2==0) cout<<"First"; 
	else cout<<"Second"; 
	return 0; 
  }
  else 
  {
   if(k%2==0) cout<<"Second"; 
   else cout<<"First"; 
   return 0; 
  }
}

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

int main(){
    int n;
    std::cin >> n;
    
    std::vector<double> v(n);
    for(int i = 0; i < n; ++i){
        std::cin >> v.at(i);
    }

    std::sort(v.begin(), v.end());

    for(int i = 1; i < n; ++i){
        v.at(i) = (v.at(i - 1) + v.at(i)) / 2.0;
    }

    std::cout << v.at(n - 1) << std::endl;

    return 0;
}

Measured memory_bytes: 888
#include "bits/stdc++.h"
using namespace std;
int main(){
    string s;
    cin >> s;
    int n=s.length(),i,j;
    long long int ans = 0, now;
    for(i=0;i< (1 << (n-1));i++){
        now=0;
        for(j=0;j<n;j++){
            now *= 10;
            now += s.at(j)-'0';
            if((i & (1<<j))){
                //前からj番目が1なら+を入れる
                ans += now;
                now = 0;
            }
        }
        ans += now;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
# coding:utf-8

import sys
import math
import time
import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength


#X = str(input()).split()
#a = [int(x) for x in input().split()]
N = int(input())
flag = 0

for i in range(math.floor(math.sqrt(N))):
  if(N%(math.floor(math.sqrt(N))-i)==0):
    a = int(N/(math.floor(math.sqrt(N))-i))
    b = math.floor(math.sqrt(N))-i
    break

ans = a+b-2
print(ans)



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

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> num(1005,0);
    
    rep(i,n) cin>>a[i];
    
    bool flag=true;
    
    rep(i,n){
        if(a[i]%2==0){
            if(a[i]%3!=0 && a[i]%5!=0){
                flag=false;
                break;
            }
        }
    }

    
    if(flag) cout<<"APPROVED"<<endl;
    else cout<<"DENIED"<<endl;
    
    return 0;
}

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

int main() {
  string s, t;
  cin >> s >> t;

  sort(s.begin(), s.end());
  sort(t.begin(), t.end(), greater<char>());

  int minSize = min(s.size(), t.size());
  bool ok = false;
  int i = 0;
  while (i < minSize) {
    if (s[i] == t[i]) {
      ++i;
      continue;
    }
    if (s[i] < t[i]) {
      ok = true;
    }
    break;
  }

  if (i == minSize && s.size() < t.size()) {
    ok = true;
  }

  if (ok) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


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

unsigned long long Euclid(unsigned long long c, unsigned long long d) {
	unsigned long long p, temp;

	if (c < d) { //c>dにする
		temp = c;
		c = d;
		d = temp;
	}

	while (1) {
		p = c % d;
		c = d;
		d = p;
		if (p == 0)	break;
	}

	return c;
}

int main() {
	unsigned long long a, b, c, d, Acount, Bcount,l;
	cin >> a >> b >> c >> d;

	//c,dの最小公倍数でa,bを割ったものが欲しい
	//そのためにc,dの最大公約数を導出する必要がある．→ユークリッドの互除法
	l=Euclid(c, d);


	Acount = (a-1) / c + (a-1) / d - (a-1) / (c*d/l);
	Bcount = b / c + b / d - b / (c * d/l);

	cout << (b-a+1)- (Bcount - Acount) << endl;
	
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#include <queue>
typedef long long ll;
typedef unsigned long long ull;
const int mod=998244353;
const int maxn=1e6+5;
const ll INF=100000000000000005;
const double eps=1e-10;
using namespace std;
ll n,m;
ll num[maxn];
ll pre[maxn],cur[maxn];
ll ABS(ll a)
{
    return a>0?a:-a;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+num[i];
    for(int i=n;i>=1;i--) cur[i]=cur[i+1]+num[i];
    ll minl=INF;
    for(int i=1;i<=n-1;i++)
        minl=min(minl,ABS(pre[i]-cur[i+1]));
    printf("%lld\n",minl);
    return 0;
}
/***
2
3 5
12
12
13
***/


Measured memory_bytes: 9984
n = int(input())
s_list = []
for i in range(n):
	s_list.append(input())

ac = 0
wa = 0
tle = 0
re = 0

for i in s_list:
	if(i == "AC"):
		ac+=1
	elif(i == "WA"):
		wa += 1
	elif(i == "TLE"):
		tle += 1
	elif(i == "RE"):
		re += 1

print("AC x " + str(ac))
print("WA x " + str(wa))
print("TLE x " + str(tle))
print("RE x " + str(re))

Measured memory_bytes: 79204
def main():
    N = int(input())
    l1 = list(map(int, input().split()))
    l2 = list(map(int, input().split()))
    res = 0
    for i in range(N):
        sum_v = sum(l1[0 : i + 1]) +  sum(l2[i:])
        if sum_v > res:
            res = sum_v
    print(res)
    



if __name__ == "__main__":
    main()

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


int main() {
    ll n;
    while(cin >> n, n){
        string b;
        cin >> b;
        ll e = 0, x = 1, s;
        for(int i=0;i<b.size();i++){
            x <<= 1;
            x += ll(b[i]-'0');
        }
        s = x;
        while((x>>e)>0){
            ll k;
            // 繰り上がりを二分探索
            ll ok=(1LL<<(e+1)), ng=0;
            while(abs(ok-ng)>1){
                ll mid = (ok+ng)/2;
                if((s+(x>>e)*mid)>>53){
                    ok = mid;
                }
                else ng = mid;
            }
            k = ok;
            if(k <= n){
                s += (x>>e)*k;
                s >>= 1;
                n -= k;
                e++;
            }
            else break;
        }
        s += (x>>e)*n;

        for(int i=11;i>=0;i--){
            cout << ((e>>i)&1LL);
        }
        for(int i=51;i>=0;i--){
            cout << ((s>>i)&1LL);
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3164