akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdint>
#include <cmath>
#include <set>
#include <algorithm>

using namespace std;

using Event = struct
{
    int64_t time;
    int kind;
    union {
        int64_t pos;
        int index;
    } v;
};

int64_t S[200'000];
int64_t T[200'000];
int64_t X[200'000];
int64_t D[200'000];

Event es[600'000];

int64_t result[200'000];

int main()
{
    int N, Q;

    cin >> N >> Q;

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

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

    for (int i = 0; i < N; i++)
    {
        es[2 * i].time = S[i] - X[i];
        es[2 * i].kind = 1;
        es[2 * i].v.pos = X[i];
        es[2 * i + 1].time = T[i] - X[i];
        es[2 * i + 1].kind = 0;
        es[2 * i + 1].v.pos = X[i];
    }

    for (int i = 0; i < Q; i++)
    {
        es[2 * N + i].time = D[i];
        es[2 * N + i].kind = 2;
        es[2 * N + i].v.index = i;
    }

    const int E = 2 * N + Q;

    sort(es, es + E, [](const Event &l, const Event &r) {
        if (l.time == r.time)
        {
            return l.kind < r.kind;
        }

        return l.time < r.time;
    });

    /*
    for (int i = 0; i < E; i++)
    {
        cout << "t=" << es[i].time << ", kind=" << es[i].kind;
        if (es[i].kind != 2)
        {
            cout << ", x=" << es[i].v.pos;
        }
        else
        {
            cout << ", idx=" << es[i].v.index;
        }
        cout << endl;
    }
    */

    set<int64_t> current;

    for (int i = 0; i < E; i++)
    {
        if (es[i].kind == 0)
        {
            current.erase(es[i].v.pos);
        }
        else if (es[i].kind == 1)
        {
            current.insert(es[i].v.pos);
        }
        else
        {
            auto iter = current.begin();
            if (iter == current.end())
            {
                result[es[i].v.index] = -1;
            }
            else
            {
                result[es[i].v.index] = *iter;
            }
        }

        /*
        cout << "{ ";
        for (auto it = current.begin(); it != current.end(); it++)
        {
            cout << *it << ", ";
        }
        cout << "}" << endl;
        */
    }

    for (int i = 0; i < Q; i++)
    {
        cout << result[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 32512
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

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

  int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

  cout << a[k-1] << endl;

}


Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#include <cassert>
using namespace std;

const int MAX_N = 18;
const int MAX_MASK = (1 << MAX_N);

inline int GetBit(int mask, int num)
{
    return (mask >> num) & 1;
}

struct TSolver
{
    int N;
    string InputString;
    string S;
    string T;

    vector<int> BitCount;
    vector<int> AfterLastBitIndex;
    vector<int> FirstEmptyBitIndex;

    void Setup()
    {
        BitCount.assign(MAX_MASK, 0);
        AfterLastBitIndex.assign(MAX_MASK, MAX_N);
        FirstEmptyBitIndex.assign(MAX_MASK, MAX_N);
        for (int mask = 0; mask < MAX_MASK; ++mask) {
            for (int i = 0; i < MAX_N; ++i) {
                BitCount[mask] += GetBit(mask, i);
            }
            for (int i = MAX_N - 1; i >= 0; --i) {
                if (GetBit(mask, i)) {
                    break;
                } else {
                    AfterLastBitIndex[mask] = i;
                }
            }
            for (int i = 0; i < MAX_N; ++i) {
                if (!GetBit(mask, i)) {
                    FirstEmptyBitIndex[mask] = i;
                    break;
                }
            }
        }
    }

    bool Read()
    {
        if (!(cin >> N)) {
            return false;
        }
        cin >> InputString;
        S = InputString.substr(0, N);
        T = InputString.substr(N, N);
        reverse(T.begin(), T.end());
        return true;
    }

    void Solve()
    {
        vector<long long> dp(1 << N, 0);
        dp[0] = 1;
        for (int mask = 0; mask < (1 << N); ++mask) {
            if (BitCount[mask] == N) {
                continue;
            }

            const auto t = T[BitCount[mask]];

            const auto rb = AfterLastBitIndex[mask];
            const auto bb = FirstEmptyBitIndex[mask];

            if (rb != bb) {
                for (int b = rb; b < N; ++b) {
                    if (S[b] == t) {
                        dp[mask | (1 << b)] += dp[mask];
                    }
                }
                if (S[bb] == t) {
                    dp[mask | (1 << bb)] += dp[mask];
                }
            } else {
                for (int b = rb; b < N; ++b) {
                    if (S[b] == t) {
                        dp[mask | (1 << b)] += 2 * dp[mask];
                    }
                }
            }
        }

        cout << dp[(1 << N) - 1] << '\n';
    }

    void TearDown()
    {
        cout.flush();
    }
};

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    TSolver solver;
    solver.Setup();
    while (solver.Read()) {
        solver.Solve();
        solver.TearDown();
    }

    return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    cout << min(n, m / 2) + max(0ll, (m - n * 2) / 4);
}


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

#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 ALL(v) v.begin(), v.end()

int64_t facctorialMethod(int64_t k){
    int64_t sum = 1;
    for (int64_t i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

int main() {

  int64_t N;
  cin >> N;
  vector<int64_t> P(N,0);
  vector<int64_t> Q(N,0);
  vector<int64_t> v(N,0);
  REP(i,N) v[i] = i+1;
  REP(i,N) cin >> P[i];
  REP(i,N) cin >> Q[i];

  int64_t a, b;
  a = 0;
  b =0 ;

  int t;
  int c = 0;
  do{
    c++;
    bool f = true;
    REP(i,N) if(v[i] != P[i]) f = false;
    if(f) a =c;
    f = true;
    REP(i,N) if(v[i] != Q[i]) f = false;
    if(f) b = c;

  }while (next_permutation(ALL(v)));

  cout << abs(a-b) << endl;
  
  

}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/10;

    static void solve(InputReader in, PrintWriter out){
        int n = in.ni(), W = in.ni();
        int[] w = new int[n];
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = in.ni();
            v[i] = in.ni();
        }
        long[][] dp = new long[n+1][100001];
        Arrays.fill(dp[0], INF);
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 100000; j++) {
                if(j-v[i-1]>=0) dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-v[i-1]]+w[i-1]);
                else dp[i][j] = dp[i-1][j];
            }
        }
        int ans = 100000;
        while(dp[n][ans]>W) ans--;
        out.println(ans);
    }

    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 126420
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define FOR(i, j, limit) for(int i=j; i< limit; ++i)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ECHO(x) cout<<x<<endl;
#define LL long long
int INF = 2147483647;
LL LINF = 9223372036854775807;
LL MOD = 1000000007;
typedef pair<int, int>P;
typedef pair<LL, LL>PL;
typedef vector<int> vi;
typedef vector<LL> vl;

char s[402][402];
bool check[402][402];
LL bl, wh;
void bfs(int i, int j, char col){
  if(check[i][j]==true) return;
  if(s[i][j]==col){
    check[i][j]=true;
    char t;
    if(s[i][j]=='#'){
      t='.';
      ++wh;
    }
    else {
      t='#';
      ++bl;
    }
    bfs(i+1, j, t);
    bfs(i-1, j, t);
    bfs(i, j+1, t);
    bfs(i, j-1, t);
  }
  else return;
}


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

  REP(i, h) REP(j, w){
    cin>>s[i+1][j+1];
    check[i+1][j+1]=false;
  }
  REP(i, h+2){
    s[i][0]='0';
    s[i][w+1]='0';
    check[i][0]=true;
    check[i][w+1]=true;
  }
  REP(j, w+2){
    s[0][j]='0';
    s[h+1][j]='0';
    check[0][j]=true;
    check[h+1][j]=true;
  }
  LL ans=0;
  REP(i, h)REP(j, w){
    bl=0;
    wh=0;
    bfs(i+1, j+1, s[i+1][j+1]);
    ans+=bl*wh;
    //cout<<bl<<wh<<" "<<ans<<endl;
  }
  cout<<ans<<endl;



  return 0;
}


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

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

    string s;
    cin >> s;
    ll n = s.size() +1;
    vector<ll> x(n,0);
    
    for (ll i = 0; i < n; i++){
        if (i == 0){
            if (s[0] == '<'){
                x[0] = max(0LL,x[0]);
                x[1] = max(1LL,x[1]);
                ll t = 1;
                ll c = 2;
                while (s[t] == '<' && t <= n-2){
                    x[t+1] = max(c,x[t+1]);
                    c++;
                    t++;
                }
            }
            continue;
        }
        if (i == n-1){
            if (s[n-2] == '>'){
                x[n-1] = max(0LL,x[n-1]);
                x[n-2] = max(1LL,x[n-2]);
                ll t = n-3;
                ll c = 2;
                while (s[t] == '>' && t >= 0){
                    x[t] = max(c,x[t]);
                    c++;
                    t--;
                }
            }
            break;
        }
        if (s[i-1] == '>' && s[i] == '<'){
            x[i+1] = max(1LL,x[i+1]);
            x[i] = max(0LL,x[i]);
            x[i-1] = max(1LL,x[i-1]);
            ll t = i-2;
            ll c = 2;
            while (s[t] == '>' && t >= 0){
                x[t] = max(c, x[t]);
                c++;
                t--;
            }
            t = i+1;
            c = 2;
            while (s[t] == '<' && t <= n-2){
                x[t+1] = max(c,x[t+1]);
                c++;
                t++;
            }
        }
        
    }

    /*for (ll i = 0; i < n; i++){
        cout << x[i] << endl;
    }*/

    ll ans = 0;
    for (ll i = 0; i < n; i++){
        ans += x[i];
    }

    cout << ans << endl;

}

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

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    int M = 0;
    for(int i = 0;i < N;i++){
        cin >> A[i];
        M = max(M, A[i]);
    }
    int d = A[0];
    for(int i = 0;i < N;i++){
        int a = d;
        int b = A[i];
        while(true){
            if(!(a%b))  break;
            int tmp = b;
            b = a%b;
            a = tmp;
        }
        d = b;
    }
    if(K <= M && !(K%d))  cout << "POSSIBLE" << endl;
    else    cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 640
N = int(input())
RP,BP = [],[]
for i in range(N):
    a,b = map(int,input().split())
    RP.append((a,b))
for i in range(N):
    c,d = map(int,input().split())
    BP.append((c,d))

Ans = 0
# 青い点をx座標で昇順ソートし、順番にみる
BP.sort()
for bp in BP:
    bx,by = bp
    # 赤い点を全探索、条件を満たすペアをリストアップする
    R_yxi = []
    for i in range(len(RP)):
        rx,ry = RP[i]
        if rx < bx and ry < by:
            R_yxi.append((ry,rx,i))
    # 条件を満たすペアが存在する場合、その中でy座標が最大のものとペアにする
    if len(R_yxi) > 0:
        R_yxi.sort(reverse=True)
        rx,ry,i = R_yxi.pop(0)
        RP.pop(i)
        Ans += 1

print(Ans)

Measured memory_bytes: 3064
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define FOR(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v),end(v)
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

using ll=long long;
using vi=std::vector<int>;
using vvi=std::vector<vi>;
using vll=std::vector<ll>;
using vvll=std::vector<vll>;
template<typename T> using vvec=std::vector<std::vector<T>>;
template<typename T>
auto make_v(size_t sz){return std::vector<T>(sz);}
template<typename T,typename... Ts>
auto make_v(size_t sz,Ts...ts){return std::vector<decltype(make_v<T>(ts...))>(sz,make_v<T>(ts...));}
template<typename T>
void fill_v(T&var,const T&x){var=x;}
template<typename V,typename T>
void fill_v(V&v,const T&x){for(auto&& w:v){fill_v(w,x);}}

template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::vector<std::vector<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<T>&v){
  int sz=v.size();s<<"\n";rep(i,sz){s<<v[i];if(i<sz-1){s<<"\t";}}s<<"\n";return s;}
template<typename T> std::ostream& operator<<(std::ostream&s,const std::deque<std::deque<T>>&v){
  for(auto&& w:v){s<<w;}return s;}
template<typename T> std::ostream& operator<<(std::ostream&s, const std::set<T>&v){
  s<<"\n";for(auto&& elm:v){s<<elm<<"\t";}s<<"\n";return s;}

inline void scan(int&a){scanf("%d",&a);}
inline void scan(ll&a){scanf("%lld",&a);}
inline void scan(char&a){scanf(" %c",&a);}
inline void scan(double&a){scanf("%lf",&a);}
inline void scan(std::string&s){char BUF[3000000];scanf(" %s",BUF);s=std::string(BUF);}
template<typename T>
inline void scan(std::vector<T>&v){for(auto&& sv:v){scan(sv);}}
template<typename First,typename...Args>
inline void scan(First&f,Args&...args){scan(f);scan(args...);}
inline void print(int a){printf("%d\n",a);}
inline void print(ll a){printf("%lld\n",a);}
inline void print(double a){printf("%.12f\n",a);}
inline void print(std::string s){std::cout<<s<<"\n";}

using namespace std;

int main() {
  int x, a;
  scan(x, a);
  int ans;
  if (x < a) {
    ans = 0;
  } else {
    ans = 10;
  }
  print(ans);
  return 0;
}


Measured memory_bytes: 888
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int W = Integer.parseInt(sc.next());
        int V = 200000;
        long[][] dp = new long[N+1][V+1];
        long INF = 1_000_000_000_000_000_000L;
        for (int i=0;i<N+1;i++) {
            for (int j=0;j<V+1;j++) {
                if (j!=0) dp[i][j] = INF;
            }
        }
        for (int i=0;i<N;i++) {
            int w = Integer.parseInt(sc.next());
            int v = Integer.parseInt(sc.next());
            for (int j=0;j<V;j++) {
                if (j+1-v>=0 && dp[i][j+1-v]!=INF) {
                    dp[i+1][j+1] = Math.min(dp[i][j+1], dp[i][j+1-v]+w);
                } else {
                    dp[i+1][j+1] = dp[i][j+1];
                }
            }
        }
        int ans = 0;
        for (int i=0;i<V+1;i++) {
            if (dp[N][i]<=W) ans = Math.max(ans, i);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 238996
#include <stdio.h>
#include <algorithm>
#include <vector>

#define ARC(i,a,b) for(int i=(a);i<(b);++i)
#define RC(i,n) ARC(i,0,n)
#define ARCH(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define RCH(i,n) ARCH(i,n,0)
#define ATH(a,b) ((a)>(b)?(a):(b))
#define OTH(a,b) ((a)<(b)?(a):(b))
#define ANTH(a,b) if(a<(b))a=(b);
#define ONTH(a,b) if(a>(b))a=(b);

int main(){
	int n, x;
	scanf("%d%d", &n, &x);
	std::vector<int> a(n);
	RC(i, n) scanf("%d", &a[i]);
	std::sort(a.begin(), a.end());
	int hoge = 0;
	RC(i, n){
		hoge += a[i];
		if(hoge > x){
			printf("%d\n", i);
			return 0;
		}
	}
	printf("%d\n", n - (hoge != x));
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define pll pair <ll, ll>
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define plll pair <pair <ll, ll>, ll>
#define pllll pair <pair <ll, ll>, pair <ll, ll> >
#define psl pair <string, ll>
#define pld pair <ld, ld>
#define all(a) a.begin(), a.end()
#define vvl vector <vector <ll> >
 
typedef long long ll;
 
typedef long double ld;
 
using namespace std;
 
const ll maxn = 20;
const ll inf = 1e18;

ll n, m, k, t;

// ll D[maxn][maxn][maxn * maxn][maxn * maxn];
map <pllll, ll> D;

ll A[maxn];

pllll cp(ll a, ll b, ll c, ll d) {
    return mp(mp(a, b), mp(c, d));
}

ll getdp(ll l, ll r, ll lm, ll rm) {
    // assert(lm < maxn * maxn && rm < maxn * maxn);
    ll q, w, e, t;
    pllll x = cp(l, r, lm, rm);
    if (r - l == 1) {
        D[x] = A[l] * lm + A[r] * rm;
        // cout << l << " " << r << " " << lm << " " << rm << " D " << D[l][r][lm][rm] << endl;
        return D[x];
    }
    if (D.find(x) != D.end()) {
        return D[x];
    }
    D[x] = inf;
    for (q = l + 1; q < r; q++) {
        ll dans = getdp(l, q, lm, lm + rm) + getdp(q, r, lm + rm, rm) - A[q] * (lm + rm);
        D[x] = min(D[x], dans);
    }
    // cout << l << " " << r << " " << lm << " " << rm << " D " << D[l][r][lm][rm] << endl;
    return D[x];
}

int main() {
    pyshnapyshnakaa;
    ll q, w, e, a, b, c, d;
    cin >> n;
    for (q = 0; q < n; q++) {
        cin >> A[q];
    }
    for (q = 0; q < maxn; q++) {
        for (w = 0; w < maxn; w++) {
            for (e = 0; e < maxn * maxn; e++) {
                for (ll i = 0; i < maxn * maxn; i++) {
                    // pllll x = cp(q, w, e, i);
                    // D[q][w][e][i] = -1;
                }
            }
        }
    }
    cout << getdp(0, n - 1, 1, 1);
    return 0;
}

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

int main() {
    int a,b,c,d,e;
    cin >> a >> b;
    c = a + b;
    d = a - b;
    e = a * b;
    int ans = max({c, d, e});
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int i,a,b,tmpnum;
	char storename,namelist[] = {'A','B','C','D','E'};
	while(1){
		tmpnum = -1;
		for(i=0;i<5;i++){
			scanf("%d%d",&a,&b);
			if (a == 0 && b ==0 ) return 0;
			if (tmpnum < a + b){
				tmpnum = a+b;
				storename = namelist[i];
			}
		}
		printf("%c %d\n",storename,tmpnum);
	}
}

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

int main()
{
    int n, input, counter=0;
    cin >> n;
    vector<int> mochi(n);
    for(int i=0; i<n; ++i)
    {
        cin >> input;
        mochi[i] = input;
    }
    sort(mochi.begin(), mochi.end());
    for(int i=0; i<n-1; ++i)
    {
        if(mochi[i] != mochi[i+1])
            ++counter;
    }
    cout << counter + 1;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(2e5) + 7;
typedef pair<int, int> pii;
const int mod = int(1e9) + 7;

int n, m, f[N], trace[N];
string s;
vector<int> ans;
deque<int> q;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n >> m >> s;
    if(s[0] == '1' || s[n] == '1') return cout << -1, 0;
    f[0] = 1; q.push_back(0);
    for(int i = 1; i <= n; ++i) {
        if(s[i] == '1') f[i] = 0, trace[i] = 0;
        else {
            while(q.size() && q.front() + m < i) q.pop_front();
            if(q.size()) f[i] = f[q.front()], trace[i] = i - q.front();
            else f[i] = 0;
            while(q.size() && f[q.back()] < f[i]) q.pop_back();
            q.push_back(i);
        }
    }
    if(f[n] == 0) cout << -1;
    else {
        int cur = n;
        while(cur != 0) {
            ans.pb(trace[cur]);
            cur = cur - trace[cur];
        }
        reverse(ans.begin(), ans.end());
        for(int x: ans) cout << x << ' ';
    }
}


Measured memory_bytes: 1868
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long ll;


int main() {
	ll n, x; cin >> n >> x;
	vector<ll> a(n), s(n + 1);
	for (ll i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	for (ll i = 0; i < n; i++) s[i + 1] += s[i] + a[i];
	ll lo = 0, hi = n + 1;
	while (hi - lo > 1) {
		ll mid = lo + (hi - lo) / 2;
		if (s[mid] <= x) lo = mid;
		else hi = mid;
	}
	if (lo == n && s[n] != x) lo--;
	cout << lo << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

int a[N];
int n, k;

bool ok(int m) {
	ll cnt = 0;
	for(int i = 0; i < n; i++) cnt += (a[i] + m - 1) / m - 1;
	return cnt <= k;
}

signed main()
{
	IO_OP;
	
	cin >> n >> k;
	for(int i = 0; i < n; i++) cin >> a[i];	
	int l = 1, r = INF;
	while(l <= r) {
		int m = (l + r) / 2;
		if(ok(m)) r = m - 1;
		else l = m + 1;
	}
	cout << l << endl;

}





Measured memory_bytes: 4388
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[int(input())-1])

Measured memory_bytes: 9040
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
using P = pair<long, long>;

typedef long long int ll;

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

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))

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

const int mod = 1000000007;

struct mint {
    ll x;
    mint(ll x=0):x(x%mod){}

    mint& operator+=(const mint a) {
        if((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint& operator-=(const mint a) {
        if((x -= mod-a.x) >= mod) x -= mod;
        return *this;
    }

    mint& operator*=(const mint a) {
        x = (x * a.x) % mod;
        return *this;
    }

    mint& operator/=(const mint a) {
        *this *= a.inv();
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }

    mint pow(ll n) const {
        mint a(*this);
        mint res = 1;
        while (n > 0) {
            if (n & 1) res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }

    mint inv() const {
        return pow(mod - 2);
    }
};

mint dp[105][4][4][4];

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

  int n;
  cin >> n;

  dp[0][0][0][0] = 1;
  dp[0][0][0][1] = 1;
  dp[0][0][0][2] = 1;
  dp[0][0][0][3] = 1;

  // t0 a1 g2 c3

  for(int i = 1; i < n; i++) {
    rep(j, 4) rep(k, 4) rep(l, 4) rep(m, 4) {
      if (k == 1 && l == 2 && m == 3) {
      } else if(k == 1 && l == 3 && m == 2) {
      } else if(k == 2 && l == 1 && m == 3) {
      } else if(j == 1 && l == 2 && m == 3) {
      } else if(j == 1 && k == 2 && m == 3) {
      } else {
        dp[i][k][l][m] += dp[i-1][j][k][l];
      }
    }
  }

  mint res = 0;
  rep(i, 4) rep(j, 4) rep(k, 4) {
    res += dp[n-1][i][j][k];
  }

  cout << res.x << endl;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;
const ll C = 1e9+7;

int main() {
    //単調増加、単調減少にならない場合は...
    int N;
    cin >> N;
    vector<ll> A(N+2);
    ll cost = 0;
    A[0] = 0, A[N+1] = 0;

    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=0; i<=N; i++) cost += abs(A[i] - A[i+1]);

    for(int i=1; i<=N; i++) {
        ll ans = cost;
        if(A[i-1] <= A[i] && A[i] <= A[i+1]) {
            cout << ans << endl;
        }
        else if(A[i-1] >= A[i] && A[i] >= A[i+1]) {
            cout << ans << endl;
        }

        else {
            ans -= min(abs(A[i-1] - A[i]), abs(A[i] - A[i+1])) * 2;
            cout << ans << endl;
        }
    }
}

Measured memory_bytes: 4040
import math

menu = [int(input()) for _ in range(5)]
num = [0, 1, 2, 3, 4]

min = float('inf')

def plus(a, b):
    c = a + b
    if (c % 10 != 0):
        c += 10 - c % 10
    return c

for index1 in num:
    for index2 in set(num) - set([index1]):
        for index3 in set(num) - set([index1, index2]):
            for index4 in set(num) - set([index1, index2, index3]):
                index5 = list((set(num) - set([index1, index2, index3, index4])))[0]
                sum = 0
                sum = plus(sum, menu[index1])
                sum = plus(sum, menu[index2])            
                sum = plus(sum, menu[index3])            
                sum = plus(sum, menu[index4])            
                sum = sum + menu[index5]
                if (sum < min):
                    min = sum

print(min)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define ALL(a) (a).begin(),(a).end()
 
using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
 
const ll MOD  = 1e9 + 7;
const ll LINF = 1LL << 60;
const int INF = 1e9 + 7;

ll n, a, b, c, d;

map<ll, ll> memo;

ll solve(ll x){
    if(x == 0)return 0;
    else if(x == 1)return d;

    if(memo.count(x))return memo[x];

    ll k[] = {2, 3, 5};
    ll cost[] = {a, b, c};

    ll res = 1e18;
    if(x < res/d)res = x*d;

    //xに近いkの倍数lと,それと同じかk大きい数r
    rep(i, 3){
        ll l = (x / k[i]) * k[i];
        ll r = ((x + k[i] - 1) / k[i]) * k[i];  

        res = min(res, llabs(l - x)*d + cost[i] + solve(l / k[i]));
        res = min(res, llabs(r - x)*d + cost[i] + solve(r / k[i]));
    }

    memo[x] = res;

    return res;
}

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

    rep(i, t){
        memo.clear();
        cin >> n >> a >> b >> c >> d;
        cout << solve(n) << endl;
    }
}

Measured memory_bytes: 4420
// AOJ 1009

#include <stdio.h>

int gcd(int a, int b)
{
        int c;
        while (b > 0) {
                c = a % b;
                a = b;
                b = c;
        }
        return a;
}

main()
{
  int x0,x1;
  while(EOF!=scanf("%d %d",&x0,&x1))
  { 
    printf("%d\n",gcd(x0,x1));
  }
  return(0);
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int main() {
  int n;
  cin >> n;
  string ans;
  if(n == 0) {
    cout << 0 << endl;
    return 0;
  }
  while(n != 0) {
    if(n % 2 == 0) {
      ans += '0';
      n /= (-2);
    }
    else {
      ans += '1';
      n = (n - 1) / (-2);
    }
  }

  reverse(ans.begin(), ans.end());
  cout << ans << endl;
}


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

int main() {
  ll x,k,d;cin>>x>>k>>d;
  ll n=abs(x)/d,ans1=abs(x)%d,ans2=abs(ans1-d);
  if(k>n){
    if((k-n)%2==1)cout<<ans2<<endl;
    else cout<<ans1<<endl;
  }
  else cout<<(ll)(abs(x)-k*d)<<endl;
}

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

typedef long long ll;

#define F for(int i = 0; i < N; i++)

int main() {

    string S;
    cin >> S;

    if(S.at(S.size()-1) == 's'){
        cout << S + "es" << endl;
    }else{
        cout << S + "s" << endl;
    }

}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (ll i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;
long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }

int main(){
    string S;
    cin >> S;
    if(S[0]=='R'&&S[1]=='R'&&S[2]=='R') cout << 3 << endl;
    else if(S[0]=='R'&&S[1]=='R') cout << 2 << endl;
    else if(S[1]=='R'&&S[2]=='R') cout << 2 << endl;
    else if(S[0]=='S'&&S[1]=='S'&&S[2]=='S') cout << 0 << endl;
    else cout << 1 << endl;
    return 0;
}


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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define w(x)            int x; cin>>x; while(x--)
#define fr(i,a,b)       for(int i = a; i < b; i++)

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

int dp[3000][3000][2];
int n;

int dequeue(vi &arr, int x, int y, int player)
{
	if (x > y) return 0;

	if (dp[x][y][player] != -1)
		return dp[x][y][player];

	if (player == 0)
		return dp[x][y][0] = max(arr[x] + dequeue(arr, x + 1, y, 1), arr[y] + dequeue(arr, x, y - 1, 1));
	else
		return dp[x][y][1] = min(dequeue(arr, x + 1, y, 0), dequeue(arr, x, y - 1, 0));
}

void solve()
{
	int total = 0;
	cin >> n;
	vi arr(n);
	fr(i, 0, n)
	{
		cin >> arr[i];
		total += arr[i];
	}
	memset(dp, -1, sizeof(dp));
	int X = dequeue(arr, 0, n - 1, 0);
	int Y = total - X;
	cout << X - Y << endl;

}

int32_t main()
{
	c_p_c();
	solve();
	return 0;
}

Measured memory_bytes: 144516
object Main {
  def main(args: Array[String]): Unit = {
    val array = Array.ofDim[Int](4, 3, 10)
    val n = scala.io.StdIn.readInt()
    for (i <- 0 until n) {
      val line = scala.io.StdIn.readLine().split(" ").map(_.toInt)
      array(line(0) - 1)(line(1) - 1)(line(2) - 1) += line(3)
    }

    for (b <- 0 until 4) {
      for (f <- 0 until 3) {
        println(" " + array(b)(f).mkString(" "))
      }
      if (b < 3) {
        println("#" * 20)
      }
    }
  }
}

Measured memory_bytes: 44168
#include<bits/stdc++.h>
using namespace std;
//size_t f = string::npos
//make pair, tuple

int main(){
      string o,e;cin >> o >> e;
      string ans = "";
      int n = min(o.length(), e.length());
      for(int i = 0;i < n;i++){
            ans += o[i];
            ans += e[i];
      }
      if(o.length() > e.length())ans += o[o.length() - 1];
      cout << ans;
}

Measured memory_bytes: 256
// In the name of God

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	if(n % 2 == 1) cout << "No";
	else {
		if( s.substr(0, n/2) == s.substr(n/2, n/2) ) cout << "Yes";
		else cout << "No";
	}
	
	return 0;
}


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

int main(){
int h,w;
  cin>>h>>w;
  vector<string> vec(h+2);
  for(int i=0;i<w+2;i++){
    vec.at(0)+="#";
    vec.at(h+1)+="#";
  }
  for(int i=1;i<h+1;i++){
    cin>>vec.at(i);
    vec.at(i)="#"+vec.at(i)+"#";
  }
  for(int i=0;i<h+2;i++){
    cout<<vec.at(i)<<endl;
  }
}


Measured memory_bytes: 256
#include<stdio.h> //binarytrees
  
int par[100001];
int sib[100001];
int deg[100001];
int n;
  
int depth(int);
int height(int);
  
int main(int argc,char *argv[]) 
{
  int i,j;
  scanf("%d", &n);
  for(i = 0; i < n; ++i) 
{
    par[i] = -1;
    sib[i] = -1;
    deg[i] = 0;
  }
  for(i = 0; i < n; ++i) 
{
    int id, left, right;
    scanf("%d %d %d", &id, &left, &right);
    if(left != -1) 
{
      par[left] = id;
      sib[left] = right;
      deg[id]++;
    }
    if(right != -1) 
{
      par[right] = id;
      sib[right] = left;
      deg[id]++;
    }
  }
  
  for(i = 0; i < n; ++i) 
{
    int dep = depth(i);
    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ",
           i, par[i], sib[i], deg[i], dep, height(i));
    if(dep == 0)
 {
      printf("root\n");
    } else if(deg[i] == 0) 
{
      printf("leaf\n");
    } else {
      printf("internal node\n");
    }
  }
  return 0;
}
 
int depth(int i) 
{
  if(par[i] == -1) return 0;
  return depth(par[i]) + 1;
}
  
int height(int i) 
{
  int j, h = 0;;
 
  for(j = 0; j < n; ++j) 
{
    if(par[j] == i) 
{
      int tmp = height(j) + 1;
      if(tmp > h) h = tmp;
    }
  }
  return h;
}

Measured memory_bytes: 620
<?php
$d=trim(fgets(STDIN));//365
$c=explode(" ",trim(fgets(STDIN)));
$i=0;
while($i<$d){
  $s[$i]=explode(" ",trim(fgets(STDIN)));
  $t=$i%26;
  echo $t+1 . "\n";
  ++$i;
}

Measured memory_bytes: 17008
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using ll = long long;
using itn = int;
using namespace std;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main(){
    int N;
    cin>>N;
    vector<ll> A(N),B(N),C(N);
    ll ans=0;
    rep(i,N) cin>>A.at(i);
    rep(i,N) cin>>B.at(i);
    rep(i,N) cin>>C.at(i);
    sort(A.begin(),A.end());
    sort(C.begin(),C.end());
    rep(i,N){
        auto a = lower_bound(A.begin(),A.end(),B.at(i));
        auto c = lower_bound(C.begin(),C.end(),B.at(i)+1);
        ll a_num=a-A.begin();
        ll c_num=C.end()-c;
        ans+=a_num*c_num;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2560
inp = input()

def isvalid(inp):
    if len(inp) < 6:
        return 'No'
    if not inp.islower():
        return 'No'
    
    if inp[2] == inp[3] and inp[4] == inp[5]:
        return 'Yes'
    return 'No'
    
print(isvalid(inp))

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

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

using ll = long long;

using namespace std;

int main() {
  in(int, n, m, X, Y);
  vector<int> x(n), y(m);
  rep(i, n) cin >> x[i];
  rep(i, m) cin >> y[i];
  if (max(X, *max_element(all(x))) < min(Y, *min_element(all(y)))) {
    out("No War");
  } else {
    out("War");
  }
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main()
{
    #ifdef TarekHasan
        //freopen("input.txt","r",stdin);
    #endif // TarekHasan
    int l,r,d; cin >> l >> r >> d;
    int counter = 0;
    for(int i=l;i<=r;i++)
    {
        if(i%d==0)
            counter++;
    }
    cout << counter << endl;
    //main();
    return 0;
}


Measured memory_bytes: 3592
/*
*  Author: windystreet
*  Date  : 2018-09-12 21:26:29
*  Motto : Think twice, code once.
*/
#include<bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define eps  1e-5
#define gcd __gcd
#define pb push_back
#define PI acos(-1.0)
#define lowbit(x) (x)&(-x)
#define bug printf("!!!!!\n");
#define mem(x,y) memset(x,y,sizeof(x))

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef unsigned long long uLL;

const int maxn = 1e5+7;
const int INF  = 1<<30;
const int mod  = 1e9+7;

set<string>s;

void solve(){
	int n,flag = 1;
	cin>>n;
	string tmp;
	string str;
	cin>>tmp;
	s.insert(tmp);
	for(int i=2;i<=n;i++){
		cin>>str;
		if(s.count(str) || tmp[tmp.size() - 1] != str[0]){
			flag = 0;
		}else{
			tmp = str;
			s.insert(tmp);
		}
	}
    if(flag){
    	cout<<"Yes\n";
    }else{
    	cout<<"No\n";
    }
    return;
}

int main()
{
//    freopen("F:\\in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    ios::sync_with_stdio(false);
    int t = 1;
    //scanf("%d",&t);
    while(t--){
    //    printf("Case %d: ",cas++);
        solve();
    }
    return 0;
}

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

using namespace std;

#ifdef DEBUG_MODE
#define DBG(n) n;
#else
#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007

typedef long long ll;

long long mod_div(long long a, long long b) {
	if (a % b == 0)return a / b;
	long long tmp = MOD - 2, c = b, ret = 1;
	while (tmp > 0) {
		if (tmp & 1) {
			ret *= c; ret %= MOD;
		}
		c *= c; c %= MOD; tmp >>= 1;
	}
	return a*ret%MOD;
}


ll dp[111111][4];

int main() {

	string str; cin >> str;

	ll tmp = 1;
	ll cou = 0;
	REP(i, str.size()) {
		if (str[i] == '?')cou++;
	}
	REP(i, cou) {
		tmp *= 3;
		tmp %= MOD;
	}

	dp[0][0] = tmp;
	REP(i, str.size()) {
		REP(j, 4) {
			if (dp[i][j]) {
				if (j < 3) {
					if (str[i] == 'A' + j) {
						dp[i + 1][j + 1] += dp[i][j];
						dp[i + 1][j + 1] %= MOD;
					}
					else if (str[i] == '?') {
						dp[i + 1][j + 1] += mod_div(dp[i][j], 3);
						dp[i + 1][j + 1] %= MOD;
					}
				}
				dp[i+1][j] += dp[i][j];
				dp[i+1][j] %= MOD;
			}
		}
	}

	cout << dp[str.size()][3] << endl;

	return 0;
}


Measured memory_bytes: 3584
N = int(input())
s = sorted([int(input()) for _ in range(N)])

all_10 = True
for i in range(N):
    if s[i] % 10 != 0:
        all_10 = False

if all_10:
    print(0)
    exit()

sum_s = sum(s)

if sum_s % 10 != 0:
    print(sum_s)
else:
    for i in range(N):
        if s[i] % 10 != 0:
            print(sum_s - s[i])
            break


Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
"""
Created on Fri May 29 21:29:28 2020

@author: naoki
"""
import fractions

N = int(input()) # 時計の個数
T = [int(input()) for i in range(N)] # 時計の針が一周する時間
T.sort() # 小さい順番にソートする
lcm = T[0] 

for i in range(1,N):
    lcm = lcm*T[i]// fractions.gcd(lcm,T[i])
print(lcm)



Measured memory_bytes: 5048
#include <bits/stdc++.h>
using namespace std;
int fact(int n)
{
  int m;

  if (n == 0)
    return 1;
  m = fact(n - 1);
  return n * m;      
}
int main(void){
  int a,b;
  double f = 0;
  cin >> a;
  vector<vector<int>> v(a,vector<int>(2));
  
  for(int i = 0;i < a;i++){
    for(int j = 0;j < 2;j++){
      cin >> v.at(i).at(j);
    }
  }
  
  for(int i = 0;i < a;i++){
    for(int j = 0;j < a;j++){
      if(i != j){
        f += sqrt(pow(v.at(i).at(0) - v.at(j).at(0),2) + pow(v.at(i).at(1) - v.at(j).at(1),2));
      }
    }
  }
  b = fact(a);
  cout << setprecision(12) << f * fact(a-1) / b;
}



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

int main(){
	int n;
	while(cin >> n, n){
		vector<int> a(n, 0), b(n, 0);
		for(int i = 0;i < n;i++)cin >> b[i];
		int ans = 0;
		while(1){
			for(int i = 0;i < n;i++)
				a[i] = count(b.begin(), b.end(), b[i]);
			if(a == b)break;
			b = a;ans++;
		}
		cout << ans << endl;
		for(int i = 0;i < n;i++)
			cout << b[i] << (i == n-1 ? "\n" : " ");
	}
	return 0;
}

Measured memory_bytes: 2984
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static string[] s_rd;
T RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * y / gcd(x, y); }

long mod = 10^^9 + 7;
//long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto N = RD;
	auto K = RD;

	writeln(N % K == 0 ? 0 : 1);
	stdout.flush();
	debug readln();
}


Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String {
            bytes
                .by_ref()
                .map(|r| r.unwrap() as char)
                .skip_while(|c| c.is_whitespace())
                .take_while(|c| !c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        n: usize,
        s: usize,
        v: [usize; n]
    }
    let d = 998244353;
    let mut ans: usize = 0;
    let mut dp = vec![0; 3001];
    for i in 0..n {
        let mut next = vec![0; 3001];
        next[v[i]] += i + 1;
        for j in 0..3001 - v[i] {
            next[j + v[i]] += dp[j];
        }
        ans = (ans + next[s] * (n - i)) % d;
        for j in 0..3001 {
            dp[j] = (dp[j] + next[j]) % d;
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;
const int mod=1e9+7;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return (ll)a*b%mod;}
int e[20];
int f[1<<16];

int main()
{
	cin >> n >> m;
	for(int i=1,u,v;i<=m;i++){
		scanf("%d%d",&u,&v);--u,--v;
		e[u]|=1<<v;
	}
	f[0]=1;
	for(int i=3;i<1<<n;i++)if((i&1)==((i&2)>>1)){
		for(int j=i;j;j=(j-1)&i)if((j&1)==((j&2)>>1)){
			int T0=j,T1=i^j,w=1;
			for(int id=0;id<n;id++)if(1&(i>>id)){
				if(1&(T0>>id)) w=mul(w,1<<(__builtin_popcount(e[id]&T1)));
				else w=mul(w,(1<<(__builtin_popcount(e[id]&T0)))-1);
			}
			f[i]=add(f[i], mul(f[T1],w));
		}
	}
	int tot=1;
	for(int i=1;i<=m;i++)tot=mul(tot,2);
	cout << sub(tot,f[(1<<n)-1]) << endl;
}


Measured memory_bytes: 768