akhauriyash/Code-Regression huggingface dataset:
from collections import deque
S = input()
Q = int(input())
li = []
for i in range(Q):
    li.append(list(input().split()))
flag = False
sq = deque(S)
for i in range(Q):
    if li[i][0] == "1":
        flag = not flag
    else:
        if (li[i][1] == "1" and not flag) or (li[i][1] == "2" and flag):
            sq.appendleft(li[i][2])
        else:
            sq.append(li[i][2])
sq = list(sq)
if flag:
    sq.reverse()
for i in range(len(sq)):
    print(sq[i], end="")

Measured memory_bytes: 124632
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <deque>
#include <queue>
#include <string>
#include <cstring>
#include <stack>

using namespace std;
typedef long long ll;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (int i = a; i < b; i++)
#define V vector

int N, M, Q;
V<V<int> > cache;
V<int> values;
ll res = 0;

void check() { 
    ll tmp = 0;
    REP(i, 0, Q) {
        if(values[cache[i][1]-1] - values[cache[i][0]-1] == cache[i][2]) tmp += cache[i][3];
    }
    res = max(res, tmp);

    return;
}

void generate(int i, int len) {
    if(len == N) {
        check();
    } else {
        REP(j, i, M+1) {
            values.PB(j);
            generate(j, len+1);
            values.pop_back();
        }
    }
    return;
} 

int main() {
    cin >> N >> M >> Q;
    V<int> a(4);
    REP(i, 0, Q) {
        cin >> a[0] >> a[1] >> a[2] >> a[3];
        cache.PB(a);
    }
    generate(1, 0);
    cout << res;
    return 0;
}



Measured memory_bytes: 3104
using System;
using System.Linq;
using System.Collections.Generic;

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            var l = Console.ReadLine().Split().Select(long.Parse).ToArray();
            long A = l[0], B = l[1];

            if ((A + B) % 2 != 0)
            {
                Console.WriteLine("IMPOSSIBLE");
                return;
            }
            long sum = (A + B) / 2;
            Console.WriteLine(sum);

        }
    }
}


Measured memory_bytes: 13396
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int main()
{
    int n;
    long long sum = 0;
    int i = 1;
    scanf("%d",&n);
    while(i<=n){
        if(i%5!=0&&i%3!=0)
            sum+=i;
            i++;
    }
    printf("%lld",sum);
    return 0;
}


Measured memory_bytes: 1736
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans, a, b, c, d, tmp, m, h, w, x, y, sum, k, q;

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

  cin >> n;
  if (n == 1)
    Cout(1);
  else {
    ans = 1;
    rrep(i, 2, n + 1) {
      ll curr = i * i;
      while (1) {
        curr *= i;
        if (curr > n) break;
      }
      curr /= i;
      if (curr > n) continue;
      ans = max(ans, curr);
    }
    Cout(ans);
  }
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	char s[105],t[105];
	scanf("%s%s",s,t);
	int f=1;
	for(int i=0;s[i]!='\0';i++) {
		if(s[i]!=t[i]){
			f=0;
			break;
		}
	}
	if(f) printf("Yes");
	else printf("No");
	return 0;
}

Measured memory_bytes: 1728
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <set>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <fstream>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  int n,m;
  cin>>n>>m;
  int a[m], b[m];
  rep(i,m) cin>>a[i]>>b[i];
  set<int> ton;
  set<int> from1;
  rep(i,m) {
    if(a[i] == 1) from1.insert(b[i]);
    if(b[i] == n) ton.insert(a[i]);
  }
  string ans = "IMPOSSIBLE";
  for(auto t: ton) {
    auto it = from1.find(t);
    if(it != from1.end()) {
      ans = "POSSIBLE";
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 11264
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,-1,0,1},dy={1,0,-1,0};



int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h,w;cin >> h >> w;
	vector<string> a(h);
	rep(i,h) cin >> a.at(i);
	vector<int> cnt(26);
	rep(i,h){
		rep(j,w){
			cnt.at(a[i][j]-'a')++;
		}
	}
	int cnt1=0,cnt2=0,cnt4=0;
	rep(i,26){
		cnt4+=cnt.at(i)-cnt.at(i)%4;
		cnt.at(i)%=4;
		cnt2+=cnt.at(i)-cnt.at(i)%2;
		cnt.at(i)%=2;
		cnt1+=cnt.at(i);
	}
	if(h%2==0 && w%2==0){
		if(cnt4==h*w) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else if(h%2==1 && w%2==1){
		if(cnt2<=h+w-2 && (cnt2-(h+w-2))%4==0 && cnt1==1) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else{
		if(h%2==1){
			if(cnt1==0 && cnt2<=w && (cnt2-w)%4==0) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
		else{
			if(cnt1==0 && cnt2<=h && (cnt2-h)%4==0) cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define mod 1000000007
#define deb(x) cout << #x << " " << x << "\n";
#define fo(i, n) for(ll i = 0; i < n; i++)
#define Fo(i, k, n) for(ll i = k; i < n; i++)
#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >
using namespace std;
using namespace __gnu_pbds;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n;
	cin >> n;
	
	if(n%10 == 3)
		cout << "bon";
	else if(n%10 == 0 || n%10 == 1 || n%10 == 6 || n%10 == 8)
		cout << "pon";
	else
		cout << "hon";
		
	return 0;
}










Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long int
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
bool find(string s)
{
	ll l=s.length();

	for(int i=0;i<l;i++)
	{
		if(s[i]!=s[l-i-1])
		return false;
	
	}
	return true;
}
int main() {
	string s;
	cin>>s;
	ll n=s.length();
	string a=s.substr(0,((n-1)/2));
	
	string b=s.substr((n+3)/2-1);
	
	if(find(a) and find(b) and find(s))
	cout<<"Yes";
	else
	cout<<"No\n";






	return 0;
}

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

int main(){
	int N; cin >> N;
	vector<int> h(N);

	for(int i = 0; i < N; ++i) cin >> h[i];

	int sum = 0;	
	int tsum = 0;
	for(int i = 0; i < N; ++i) tsum += h[i];
	while(tsum != 0){
		int l = 0, r = N-1;
		tsum = 0;
		for(int i = 0; i < N; ++i){
			if(h[i] == 0) l = i;
			else if(i == N-1 || h[i+1] == 0){
				r = i;
				int min = 1000;
				for(int j = l; j < r+1; ++j) { if(min > h[j] && h[j] != 0) min = h[j]; }
				for(int j = l; j < r+1; ++j) { if(h[j] != 0) h[j] -= min; }
				sum += min;
				// cout << "min:" << min << endl;
			}

		}
		for(int i = 0; i < N; ++i){ tsum += h[i]; }
		// cout << "sum:" <<sum << endl;
	}

	cout << sum << endl;

	return 0;
}


Measured memory_bytes: 256
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


yn = 'YNEOS'
ynflg = False
cnt = 0
ans = None

def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



N = intinput()
datas = set(mulinputs())
# datas = list(range(1000000000))

# last = len(datas) - 1
# for i in range(len(datas)>>1):
#     print(i, datas[i], datas[last-i], ynflg)
#     if datas[i] != datas[last-i]:
#         continue
#     ynflg = True
ynflg = not(len(datas) == N)

# 出力
print(yn[ynflg::2])




Measured memory_bytes: 37740
#include <cstdio>
#include <algorithm>
int main() {
    int n, legs;
    scanf("%d %d", &n, &legs);
    if (n * 4 < legs) printf("No\n");
    else {
        bool flag = false;
        for (int i = 0; i <= n; i++) {
            if (i * 2 + (n-i) * 4 == legs) {flag = true; break; }
        }
        (flag) ? printf("Yes\n") : printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 1644
#include<stdio.h>

int main(int argc, char *argv[]){
  int h, w;
  scanf("%d %d", &h, &w);
  //printf("h=%d, w=%d\n", h, w);

  char s[h][w];
  for(int i=0; i<h; i++){
    scanf("%s", s[i]);
  }

  /*
  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      printf("%c", s[i][j]);
    }
    printf("\n");
  }
  */

  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      if(s[i][j] == '.') s[i][j] = '0';
    }
  }

  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      //if(s[i][j] == '#') continue;
      if(s[i][j] == '#'){
        if(i>0 && j>0 && s[i-1][j-1]!='#') s[i-1][j-1]++;
        if(i>0 && s[i-1][j]!='#') s[i-1][j]++;
        if(i>0 && j<(w-1) && s[i-1][j+1]!='#') s[i-1][j+1]++;
        if(j>0 && s[i][j-1]!='#') s[i][j-1]++;
        if(j<(w-1) && s[i][j+1]!='#') s[i][j+1]++;
        if(i<(h-1) && j>0 && s[i+1][j-1]!='#') s[i+1][j-1]++;
        if(i<(h-1) && s[i+1][j]!='#') s[i+1][j]++;
        if(i<(h-1) && j<(w-1) && s[i+1][j+1]!='#') s[i+1][j+1]++;
        //int s_int = atoi(s[i][j]);
        //int s_int = s[i][j];
        //s[i][j] = (char)s_int;
      }
    }
  }



  for(int i=0; i<h; i++){
    for(int j=0; j<w; j++){
      printf("%c", s[i][j]);
    }
    printf("\n");
  }

  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF 1e9
#define dump(x) cerr<<#x<<"="<<x<<endl
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> P;
template <class T> void chmin(T & a, T const & b) { if (b < a) a = b; }
template <class T> void chmax(T & a, T const & b) { if (b > a) a = b; }
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
using ll = long long;
const ll mod = LLONG_MAX;

int a,b,c,d,e,k;
int main(){
  cin>>a>>b>>c>>d>>e>>k;
  if(e-a>k){
    cout<<":("<<endl;
  }else{
    cout<<"Yay!"<<endl;
  }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int z;
int main()
{
	cin>>a;
	for (int i=1;i<=a;i++)
	{
		cin>>b>>c;
		z=z+(c-b+1);
	}
	cout<<z<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__;
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N,K; cin >> N >> K;
    vector<ll> a(N);
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    ll out=LNF;
    for(int i=0;i<(1<<N);i++){
        ll cnt=0;
        ll ccc=0;
        ll hhh=0;
        for(int j=0;j<N;j++){
            if(j==0){
                cerr << "!";
                hhh=a[j];
                ccc++;
            }else if(i&(1<<j)){
                cerr << "!";
                if(hhh>=a[j]){
                    cnt += hhh-a[j]+1;
                    hhh = hhh+1;
                }else{
                    hhh = a[j];
                }
                ccc++;
            }else{
                if(hhh<a[j]) hhh = a[j];
            }
            
            cerr << hhh << "\t";
        }
        cerr << cnt << "\t" << ccc << endl;
        if(ccc<K) continue;
        if(cnt<out) out = cnt;        
    }
    cout << out << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<ll, ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
ll N,P;
map<ll,int> mp;
int main(){
    cin >> N >> P;
    if(N == 1){
        cout << P << endl;
        return 0;
    }
    ll m = P;
    for(ll i = 2; i*i <= P; i++){
        while(m % i == 0){
            mp[i]++;
            m /= i;
        }
    }
    ll ans = 1;
    for(ll i = 2; i*i <= P; i++){
        if(mp[i] >= N){
            ans *= pow(i, mp[i]/N);
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 62720
// AOJ 2548 Sugoroku
// 2018.2.5 bal4u

#include <stdio.h>

#define QMAX 10000
typedef struct { int t, s; } QUE;
QUE que[QMAX]; int qsize;

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

void min_heapify(int i)
{
	int l, r, min;
	QUE qt;

	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && que[l].t < que[i].t) min = l; else min = i;
	if (r < qsize && que[r].t < que[min].t) min = r;
	if (min != i) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		min_heapify(min);
	}
}

void deq()
{
//	if (qsize == 0) return 0;
//	*n = que[0].node, *t = que[0].t, *c = que[0].c;
	que[0] = que[--qsize];
	min_heapify(0);
}

int qmax;
void enq(int s, int t)
{
	int i, min;
	QUE qt;

	i = qsize++;	if (qsize > qmax) qmax = qsize;
	que[i].s = s, que[i].t = t;
	while (i > 0 && que[min = PARENT(i)].t > que[i].t) {
		qt = que[i], que[i] = que[min], que[min] = qt;
		i = min;
	}
}

#define INF 10000
int a[7];
int tbl[302];
int to[302][100], hi[302];
dist[302];

#define getchar_unlocked()  getchar()
int in()
{
	int n = 0;
	int c = getchar_unlocked();
	if (c == '-') {
		c = getchar_unlocked();
		do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
		while (c >= '0');
		return -n;
	}
	do n = (n<<3)+(n<<1) + (c & 0xf), c = getchar_unlocked();
	while (c >= '0');
	return n;
}
 
void dijkstra(int start, int goal)
{
	int i, s, d, e;

	for (i = 0; i <= 300; i++) dist[i] = INF;
	qsize = 0;
	dist[start] = 0;
	enq(start, 0);
	while (qsize) {
		s = que[0].s, d = que[0].t+1, deq();
		if (s == goal) break;
		for (i = 0; i < hi[s]; i++) {
			e = to[s][i];
			if (d < dist[e]) dist[e] = d, enq(e, d); 
		}
	}
}

int main()
{
	int m, i, j, s, g, ni, t;
int max = 0;
	m = in();
	for (i = 1; i <= 6; i++) a[i] = in();
	s = in(), g = in();
	for (i = 1; i <= m; i++) tbl[i] = in();

	for (i = 1; i <= m; i++) for (j = 1; j <= 6; j++) {
		ni = i - a[j];
		if (ni > 0 && ni <= m) t = ni+tbl[ni], to[t][hi[t]++] = i;
		ni = i + a[j];
		if (ni > 0 && ni <= m) t = ni+tbl[ni], to[t][hi[t]++] = i;
	}

	dijkstra(g, s);

	i = s, t = dist[i];
	while (i != g) {
		j = in();
		ni = i - a[j];
		if (ni > 0 && ni <= m && dist[ni+tbl[ni]] < t) {
			i = ni+tbl[ni], t = dist[i], puts("-1"); goto next;
		}
		ni = i + a[j];
		if (ni > 0 && ni <= m && dist[ni+tbl[ni]] < t) {
			i = ni+tbl[ni], t = dist[i], puts("1"); goto next;
		}
		puts("0");
next:	fflush(stdout);
	}
	return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define setbits(x)  __builtin_popcountll(x)
#define mod 1000000007
#define v(n) vector<int> v(n)
#define w(x) int x;cin>>x;while(x--)
#define ps(x,y) fixed<<setprecision(y)<<x
#define f(i,j,n) for(int i=j;i<=n;i++)
#define  FAST ios_base::sync_with_stdio(0);cin.tie(0);cin.tie(0);
void c_p_c(){
    ios_base::sync_with_stdio(0);cin.tie(0);cin.tie(0);
   /* #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
}
int main(){
    c_p_c();
    int n,t=0;
    cin>>n;
    v(n);
    f(i,0,n-1)
     cin>>v[i];
    if(n<=2)
     cout<<"0";
    else
   { f(i,0,n-1){
        f(j,0,n-1){
            f(k,0,n-1){
                if((v[i]+v[j])>v[k] && (v[j]+v[k])>v[i] && (v[k]+v[i])>v[j]&&v[i]<v[j]&&v[j]<v[k])
                 t++;
            }
        }
    }cout<<t;}
}   
    
    
     

     
   









Measured memory_bytes: 3636
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
vector<long long>x, y;
map<long long, int>M;
int solve(long long p) {
	if (M[p] != 0)return M[p];
	int maxn = -999999;
	int pos1 = lower_bound(x.begin(), x.end(), p) - x.begin();
	if (pos1 != x.size() && x[pos1] == p)maxn = 1;

	int pos2 = lower_bound(y.begin(), y.end(), p) - y.begin();
	if (pos2 != y.size() && y[pos1] == p)maxn = 2;

	for (int i = 0; i < x.size(); i++) {
		if (x[i] * x[i] > p)continue;
		if (x[i] >= 10000000)continue;

		if (p%x[i] == 0 && (p / x[i]) % 2 == 0) {
			int r1 = solve(x[i]);
			int r2 = solve(p / x[i]);
			maxn = max(maxn, r1 + r2);
		}
	}
	M[p] = maxn;
	return maxn;
}
int main() {
	for (int i = 1; i <= 18; i++) {
		for (int j = 0; j < (1 << i); j++) {
			string S = "";
			for (int k = 0; k < i; k++) {
				if ((j / (1 << k)) % 2 == 0)S += "2";
				if ((j / (1 << k)) % 2 == 1)S += "8";
			}
			x.push_back(stoll(S));
		}
	}
	for (int i = 254; i < 4094; i++) {
		for (int j = i + 1; j < 4094; j++) {
			y.push_back(x[i] * x[j]);
		}
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	long long n; cin >> n;
	int c = solve(n); if (c < 0)c = -1;
	cout << c << endl;
	return 0;
}

Measured memory_bytes: 72560
#include<cstdio>

int main(){
	int D, N;
	scanf("%d %d", &D, &N);
	int a = 1;
	for (int i = 0; i < D; ++i) a *= 100;
	printf("%d\n", N == 100 ? 101*a : (N*a));
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<climits>
#include<cmath>
#include<map>
#include<vector>
#define INF INT_MAX
using namespace std;

double W, H;
double S;
int  x, y;

int main(){
	cin >> W >> H >> x >> y;
	S = W*H / 2;

	printf("%lf %d\n", S, x + x == W&&y + y == H);

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)

int main()
{
	double a, b;
	cin>>a>>b;
	cout << (int)((a+b)/2.0 + 0.5) << endl;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
S = input()

# ランレングス圧縮
# (後の処理がしやすいように、常に1の区間から始まって1の区間で終わる形にする)
A = []
# 番兵
if S[0] == '0':
    A.append(0)
cnt = 1
cur = S[0]
for i, s in enumerate(S[1:], 1):
    if s != cur:
        A.append(cnt)
        cnt = 1
        cur = s
    else:
        cnt += 1
A.append(cnt)

# 例外処理
if len(A) == 1:
    print(N)
    exit()

# 番兵
if S[-1] == '0':
    A.append(0)

M = len(A)
ans = sm = sum(A[:K*2+1])
# 常に1の区間まで取った方が得なので、indexを2ずつ進める
for i in range(K*2+2, M, 2):
    # 前の0の区間と1の区間を増やす
    sm += A[i-1] + A[i]
    # 後ろの0の区間と1の区間を減らす
    if i-K*2-2 >= 0:
        sm -= A[i-K*2-2]
    if i-K*2-1 >= 0:
        sm -= A[i-K*2-1]
    ans = max(ans, sm)
print(ans)


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

using namespace std;

int main()
{
  while (true)
  {
    string s;
    cin >> s;
    if (s == "0")
      return 0;

    int sum = 0;
    for (int i = 0; i < s.length(); i++)
    {
      sum += (int)s[i] - 48;
    }

    cout << sum << endl;
  }
}

Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a;
	cin>>a;
	if(a==25)
		cout<<"Christmas";
	if(a==24)
		cout<<"Christmas Eve";
	if(a==23)
		cout<<"Christmas Eve Eve";
	if(a==22)
		cout<<"Christmas Eve Eve Eve";
	return 0;
}

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

int main(){
  int N,W;
  cin>>N>>W;
  int w[N],v[N];
  for(int i=0;i<N;i++){
    cin>>w[i]>>v[i];
  }
  
  long long int dp[N+1][W+1];
  for(int i=0;i<W+1;i++){
    dp[0][i] = 0;
  }
  
  for(int i=1;i<N+1;i++){
    for(int j=0;j<W+1;j++){      
      dp[i][j] = dp[i-1][j];
      if(j>=w[i-1]) dp[i][j] = max(dp[i][j],dp[i-1][j-w[i-1]]+v[i-1]);
    }
  }
  
  long long int ans=0;
  for(int i=0;i<W+1;i++){
    ans = max(ans,dp[N][i]);
  }
  cout << ans << endl;
}
     

Measured memory_bytes: 79104
#include<iostream>
using namespace std;
int x[200001];
int main()
{
    int n;
    bool flag=false;
    cin>>n;
    for(int t=0;t<n;t++)
    {
    cin>>x[t];	
	}
	int num=0,temp=1;
	for(int t=0;t<n;t++)
	{
		if(x[t]==temp)
		{
			num++;
			temp++;
		}
	}
    if(temp==1)
    cout<<"-1";
    else
    cout<<n-num;
}

Measured memory_bytes: 1024
import java.util.*;
import java.io.*;
import java.math.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		for(int i = 0; i < t; i++) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			
			int[] list = new int[n];
			for(int j = 0; j < n ;j++) {
				list[j] = sc.nextInt();
			}
			int sum = 0;
			ArrayList<Integer> ss = new ArrayList<Integer>(n-1);
			for(int j = 1; j < n; j++) {
				int tmp = list[j] - list[j-1];
				sum += tmp;
				ss.add(tmp);
			}
			Collections.sort(ss);
			Collections.reverse(ss);
			k = Math.min(k, ss.size()+1);
			for(int j = 1; j < k; j++) {
				sum -= ss.get(j-1);
			}
			
			System.out.println(sum);

		}
		
		
	}
}

Measured memory_bytes: 108416
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair
#define MOD (LL)(1e9+7)

LL N, K;
int A[2000];
int main(){
	cin >> N >> K;
	for(int i=0; i<N; i++) cin >> A[i];

	LL ans = 0;
	//自分たちのなかで Kグループ
	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			if(A[i] > A[j]) ans += K;
		}
	}
	//右側のグループと
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(A[i] > A[j]) ans += (K-1) * K / 2;//K-1 + K-2 + ... + 1
			ans %= MOD;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

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

int n, m;
char ch[10][10];

void solve(){
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++)scanf("%s", ch[i]+1);
	int d[10][10] = {};
	memset(d, -1, sizeof d);
	d[1][1] = (ch[1][1] == '#');
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(i!=1||j!=1){
		if(ch[i][j] == '#'){
			if(ch[i-1][j] == '#' && d[i-1][j] != -1)d[i][j] = d[i-1][j];
			if(ch[i][j-1] == '#' && d[i][j-1] != -1)d[i][j] = max(d[i][j], d[i][j-1]);
			if(d[i][j] != -1)d[i][j]++;
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(ch[i][j] == '#')d[n][m] --;
	printf("%s", d[n][m] == 0 ? "Possible" : "Impossible");
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<utility>
#include<cmath>
#include<assert.h>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<complex>
#include<bitset>

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound

int N, K;
int A[100100];
int psum[100100];//positive sum
int ksum[100100];//ksum[i]:=a[i]+a[i-1]+...+a[i-K+1];
signed main() {
    cin >> N >> K;
    int ks = 0;
    rep(i, N) {
        cin >> A[i];
        if (A[i] > 0)psum[i + 1] = psum[i] + A[i];
        else psum[i + 1] = psum[i];
        ks += A[i];
        if (i - K + 1 > 0)ks -= A[i - K];
        ksum[i] = max(ks, 0ll);
    }
    int ans = 0;
    for (int i = K - 1; i < N; ++i) {
        ans = max(ans, ksum[i] + psum[i - K + 1] + psum[N] - psum[i + 1]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {

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

        int sn = s.length();
        int tn = t.length();
        int[][] dp=new int[sn+1][tn+1];
        int[][] res=new int[sn+1][tn+1];


        for (int i = 0; i <= sn; i++) {
            for (int j = 0; j <= tn; j++) {
                if(i+1<=sn){// 0: go down
                    if(dp[i+1][j] <dp[i][j]){
                        dp[i+1][j]=dp[i][j];
                        res[i+1][j]=0;
                    }
                }
                if(j+1<=tn){// 1: go right
                    if(dp[i][j+1] <dp[i][j]){
                        dp[i][j+1]=dp[i][j];
                        res[i][j+1]=1;
                    }
                }
                if(i+1<=sn && j+1<=tn && s.charAt(i)==t.charAt(j)){//down + right
                    dp[i+1][j+1]=Math.max(dp[i+1][j+1],dp[i][j]+1);
                    res[i+1][j+1]=2;
                }
            }
        }
//        System.out.println(dp[sn][tn]);
        StringBuilder sb = new StringBuilder();
        int dir = res[sn][tn];
        while(sn>0 && tn >0){
            if(dir==0){
                sn--;
            }else if(dir==1){
                tn--;
            }else{
                sn--;tn--;
                sb.insert(0,s.charAt(sn));
           }
            dir = res[sn][tn];
        }
        System.out.println(sb.toString());
    }

}


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

const int N = 3;
const int LIMIT = 100;
int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
int limit;
int puz[N*N];
int zero;
int esti;
int MDT[N*N][N*N];

int dfs(int dep, int pre) {
	if ( esti == 0 ) return dep;
	if ( dep+esti >= limit ) return LIMIT;	

	int ret = LIMIT;
	for ( int i = 0; i < 4; i++ ) {
		if ( (i+2)%4 == pre ) continue;
		int y = zero/N, x = zero%N;
		int ny = y+dy[i], nx = x+dx[i];
		if ( ny < 0 || nx < 0 || ny >= N || nx >= N ) continue;
		int tmp[N*N];
		int tmp_zero  = zero;
		int tmp_esti = esti;		
		for ( int j = 0; j < N*N; j++ ) tmp[j] = puz[j];
		int ch_id = ny*N+nx;
		int ch_dat = puz[ch_id];		
		esti -= MDT[zero][N*N-1];
		esti -= MDT[ny*N+nx][ch_dat];
		esti += MDT[zero][ch_dat];
		esti += MDT[ny*N+nx][N*N-1];
		swap(puz[zero], puz[ch_id]);
		zero = ch_id;		
		ret = min(ret, dfs(dep+1, i));
		for ( int j = 0; j < N*N; j++ ) puz[j] = tmp[j];
		zero = tmp_zero;
		esti = tmp_esti;		
	}

	return ret;
}

int main() {
	for ( int i = 0; i < N*N; i++ ) {
		for ( int j = 0; j < N*N; j++ ) {
			MDT[i][j] = abs(i/N-j/N) + abs(i%N-j%N);            
		}
	}

	for ( int i = 0; i < N*N; i++ ) {		
		cin >> puz[i];
		if ( puz[i] == 0 ) {
			zero = i;
			puz[i] = N*N-1;			
		} else {
			puz[i]--;
		}
		esti += abs(i/N-puz[i]/N) + abs(i%N-puz[i]%N);        
	}

	for ( int i = esti; i <= LIMIT; i++ ) {
		limit = i;
		int ans = dfs(0, -1);
		if ( ans < 100 ) {
			cout << ans << endl;
			break;
		}
	}
	
	return 0;
}



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

int n, c, dp[31][1<<16 + 1];
int npt[32], cpt[31];

int rec(int idx, int now){
  if(idx == n) return 0;
  if(dp[idx][now]) return dp[idx][now];
  
  int ret = 0;
  for(int i = 0; i < c; i++){
    ret = max(ret, rec(idx+1, (now & ~cpt[i]) | npt[idx+1]) + __builtin_popcount(now & cpt[i]));
  }
  
  return dp[idx][now] = ret;

}

int main(){
  
  while(cin >> n >> c, n||c){
    
    for(int i = 0; i < n; i++){
      for(int j = 0; j < 16; j++){
	int bit; cin >> bit;
	if(bit) npt[i] |= 1;
	npt[i] <<= 1;
      } npt[i] >>= 1;
    }
    for(int i = 0; i < c; i++){
      for(int j = 0; j < 16; j++){
	int bit; cin >> bit;
	if(bit) cpt[i] |= 1;
	cpt[i] <<= 1;
      } cpt[i] >>= 1;
    }

    npt[n] = 0;
    cout << rec(0, npt[0]) << endl;
    memset(dp, 0, sizeof(dp));
    memset(npt, 0, sizeof(npt));
    memset(cpt, 0, sizeof(cpt));

  }
}

Measured memory_bytes: 17044
/*
  スタック(ALDS1_3_A)
  2018/08/26
*/

#include<stdio.h>
#include<ctype.h>

int stack[100] = {0};
int num;
int top = 0;
char s_ptr;

int main(void){
  
  do{
    scanf("%c",&s_ptr);//文字を１文字入力
    if(s_ptr != '\n'){

      /*もし数字だったら,stackに格納する*/
      if(isdigit(s_ptr))
	{
	  while(!(isspace(s_ptr)))
	    {
	      stack[top] = stack[top] * 10+ s_ptr - '0';
	      scanf("%c",&s_ptr);
	    }
	  top++;
	}
      else
	{
	  /*もし演算子だったら,以下を実行する.*/
	  if(!(isspace(s_ptr)))
	    {
	      int b = stack[--top];
	      stack[top] = 0;
	      int a = stack[--top];
	      stack[top] = 0;
	      switch(s_ptr)
		{
		case '+':
		  stack[top] = a+b;
		  break;
		case '-':
		  stack[top] = a-b;
		  break;
		case '*':
		  stack[top] = a*b;
		  break;
		}
	      top++;
	    }
	}
    }
  }while(s_ptr != '\n');//改行だったら,do~while文を抜ける

  printf("%d\n",stack[0]);
  return 0;
}


Measured memory_bytes: 2148
#include<iostream>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<cmath>
    #include<tuple>
    #include<string>
    typedef unsigned long long ll;
    #define rep(i,a,b) for(int i=(a);i<(b);i++)
    #define F first
    #define S second
    using namespace std;
    const ll INF = 1e12;
    const int i_INF = 2147483647;
     
    int main() {
      int n;
      cin>>n;
      if(n==1)cout<<"Hello World"<<endl;
      else {
        int a,b;
        cin>>a>>b;
        cout<<a+b<<endl;
      }
    }

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;
typedef long long ll;
#define INF (1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define each(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)

const int MAX_N = int(1e5);
int N;
ll M, A[MAX_N];


void solve() {
    unordered_map<ll, ll> mp;
    ll ans = 0;
    ll dp[MAX_N + 1];
    REP(i, N) {
        dp[i + 1] = (dp[i] + A[i]) % M;
        mp[dp[i + 1]]++;
    }
    each(mod, mp) {
        ans += mod.second * (mod.second - 1) / 2;
        if (mod.first == 0) ans += mod.second;
    }
    cout << ans << endl;
}

int main() {
    cin >> N >> M;
    REP(i, N) cin >> A[i];
    solve();
    return 0;
}

Measured memory_bytes: 4492
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long LL;
using namespace std;
int a[100005],tot=0;
LL sum,cc[3];
bool ok[100005];
int read()
{
	int ans=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}
	return ans*f;
} 
int main()
{
	int n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+1+n);
	for(int i=n-1;i>=1;i--){
		if(!ok[i+1]&&a[i]==a[i+1]){
			ok[i]=1;cc[++tot]=a[i];
			if(tot==2){
				sum=cc[1]*cc[2];printf("%lld",sum);break;
			}
		}
	}
	if(tot<2)printf("0");
	return 0;
} 

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

int a, b, k;

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	cin >> a >> b >> k;
	for(int i=0; i<k; ++i){
		cout << a + i << "\n";
		if(a + i == b) return 0;
	}
	for(int i=max(a+k, b-k+1); i<=b; ++i)
		cout << i << "\n";
}

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

using namespace std;

int main()
{
    double n,d,x,y,i;
    int cnt=0;

    cin >> n >> d ;

    for(i=0; i<n; i++){
        cin >> x >> y;

        if(sqrt(x*x + y*y) <= d )
            cnt++;
    }

    cout << cnt << endl;
    
    return 0;
}

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

int main()
{
    ll N, K;
    cin >> N >> K;
    int res = 1;
    ll m = K;
    while (m <= N)
    {
        res++;
        m *= K;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
using System;

namespace abc097A
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split();
            int A = int.Parse(str[0]);
            int B = int.Parse(str[1]);
            int C = int.Parse(str[2]);
            int D = int.Parse(str[3]);
            int[] src = { A, B, C };
            Array.Sort(src);
            int E = src[2] - src[1];
            int F = src[1] - src[0];
            int G = C - A;
            if (G < 0)
                G = -G;
            if ((E <= D && F <= D) || G <= D)
                Console.WriteLine("Yes");
            else
                Console.WriteLine("No");
        }
    }
}


Measured memory_bytes: 11092
#include <iostream> 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define MAX 1000001
ll prime[MAX];
#define FAST           ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define gcd __gcd
// ll rec(vector<vector<ll> >& dp,vector<ll>& arr,int n,int i,int k,int w)
// {
//   ll ans=0;
//   if(i>=n)
//     return 0;

//   if(dp[i][k]!=-1)
//     return dp[i][k];


//   if(k!=0)
//   ans=max(rec(dp,arr,n,i+1,w,w),arr[i]+rec(dp,arr,n,i+1,k-1,w));
//   else
//   ans=max(rec(dp,arr,n,i+1,k,w),rec(dp,arr,n,i+1,w,w));

//   return dp[i][k]=ans;

// }

//ll t[400008];
// void build(vector<ll>& a, int v, int tl, int tr) {
//     if (tl == tr) {
//         t[v] = a[tl];
//     } else {
//         int tm = (tl + tr) / 2;
//         build(a, v*2, tl, tm);
//         build(a, v*2+1, tm+1, tr);
//         t[v] = max(t[v*2] ,t[v*2+1]);
//     }
// }

// ll maxi(int v, int tl, int tr, int l, int r) {
//     if (l > r) 
//         return 0;
//     if (l == tl && r == tr) {
//         return t[v];
//     }
//     int tm = (tl + tr) / 2;
//     return max(maxi(v*2, tl, tm, l, min(r, tm)) ,maxi(v*2+1, tm+1, tr, max(l, tm+1), r));
// }



// void update(int v, int tl, int tr, int pos, ll new_val) {
//     if (tl == tr) {
//         t[v] = new_val;
//     } else {
//         int tm = (tl + tr) / 2;
//         if (pos <= tm)
//             update(v*2, tl, tm, pos, new_val);
//         else
//             update(v*2+1, tm+1, tr, pos, new_val);
//         t[v] = max(t[v*2] ,t[v*2+1]);
//     }
// }


struct hash_pair {
   template <class T1, class T2>
   size_t operator()(const pair<T1, T2>& p) const{
      auto hash1 = hash<T1>{}(p.first);
      auto hash2 = hash<T2>{}(p.second);
      return hash1 ^ hash2;
   }
};


int temp[1000002]={0};

void sieve()
{
  temp[1]=1;
  for(int i=2;i<1000002;i++)
  {
    if(temp[i]==0)
    { temp[i]=i;
      for(int j=i*2;j<1000002;j+=i)
      { 
        if(temp[j]==0)
        temp[j]=i;
      }
    }
  }

}

int dfs(int i,vector<vector<int> > &g,vector<int>& p,vector<int>& c)
{
  int sub=1;
  for(auto x:g[i])
  {
    if(p[i]!=x)
    {
      p[x]=i;
      sub+=dfs(x,g,p,c);
    }
  }

  return c[i]=sub;
}


int main() { 


ll n;
cin>>n;
ll dp[n+1]={0};

dp[0]=1;
dp[1]=0;
for(int i=2;i<=n;i++)
{
  for(int j=3;j<=i;j++)
  {
    dp[i]=(dp[i]+dp[i-j])%mod;
  }
}
cout<<dp[n];

return 0;
}
/*
1
4
1 2
2 3
3 4
*/


Measured memory_bytes: 3564
#include <stdio.h>

int main(void){
  int W, H, x, y, r;
  scanf("%d %d %d %d %d", &W, &H, &x, &y, &r);

  int is_horizontal = ((x - r) >= 0) && ((x + r) <= W);
  int is_vertical = ((y - r) >= 0) && ((y + r) <= H);

  if (is_horizontal && is_vertical) puts("Yes");
  else puts("No");

  return 0;
}

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

using namespace std;
typedef long long ll;

// #define DEBUG

const int maxint = 1e9;
struct timestamp;
vector<int> shortest;
vector<vector<pair<int, int>>> connective;

void djkstra(int x)
{
    vector<int> search = {x};
    vector<int> new_search;
    shortest[x] = 0;
    int v, d;
    while (!search.empty())
    {
        for (auto itr = search.begin(); itr != search.end(); itr++)
        {
            for (auto itr2 = connective[*itr].begin(); itr2 != connective[*itr].end(); itr2++)
            {
                v = itr2->first, d = itr2->second;
                if (shortest[v] > d + shortest[*itr])
                {
                    shortest[v] = d + shortest[*itr];
                    new_search.push_back(v);
                }
            }
        }
        search.clear();
        search = new_search;
        new_search.clear();
    }
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    int n, s, t, d, maxindex;
    cin >> n;
    connective.resize(n);
    for (int i = 0; i < n; i++)
    {
        shortest.push_back(maxint);
    }
    for (int i = 0; i < n - 1; i++)
    {
        cin >> s >> t >> d;
        connective[s].push_back(make_pair(t, d));
        connective[t].push_back(make_pair(s, d));
    }
    djkstra(0);

    maxindex = 0;
    for (int i = 0; i < n; i++)
    {
        if (shortest[maxindex] < shortest[i])
        {
            maxindex = i;
        }
    }

    for (int i = 0; i < n; i++)
    {
        shortest[i] = maxint;
    }

    djkstra(maxindex);
    cout << *max_element(shortest.begin(), shortest.end()) << endl;

    return 0;
}

// getline(cin,s);
// a = strtok(s, ",");  ","で分解
// for (int i = 0; i < n; i++)
// for (int j = 0; j < m; j++)


Measured memory_bytes: 9820
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
char c[4]={'E','W','N','S'};
int main(){// FastIO;
 
int n,i,j,k;cin>>n;
string s;cin>>s;
ll r=0,g=0,b=0,res=0;
for(i=0;i<n;i++)
{
	if(s[i]=='R') r++;
	else if(s[i]=='G') g++;
	else b++;
}
res=r*g*b;
for(i=0;i<n;i++)
{
	for(j=i+1;j<n;j++)
	{
		k=2*j-i;
		if(s[i]!=s[j] && k<n && s[i]!=s[k] && s[j]!=s[k]) res--;
	}
}
cout<<res;
 
	cout<<endl;

}


Measured memory_bytes: 3620
A=[]
for i in range(5):
    B=int(input())
    A.append(B)
min=1000
count=0
for j in range(5):
    if A[j]%10!=0 and A[j]%10<min:
        min=A[j]%10
        index=j
    if A[j]%10==0:
        count+=1
if count==5:
    index=0
time=0
for k in range(len(A)):
    if k!=index:
        time=time+A[k]
        if A[k]%10!=0:
            time=time+(10-A[k]%10)
    else:
        time=time+A[k]
print(time)

Measured memory_bytes: 3064
/*
      author  : nishi5451
      created : 15.08.2020 00:32:35
*/

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


int main(){
    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> c(n);
    rep(i,n) cin >> v[i];
    rep(i,n) cin >> c[i];
    int now = 0;
    rep(i,n){
        if(v[i]-c[i]>0)
            now += v[i]-c[i];
    }
    cout << now << endl;
    
    return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

string a;
int ans;

int main() {
  cin >> a;
  int l = 0, r = a.size() - 1;
  while (l < r) {
    if (a[l] == a[r]) {
      l++;
      r--;
    } else if (a[l] == 'x') {
      ans++;
      l++;
    } else if (a[r] == 'x') {
      ans++;
      r--;
    } else {
      puts("-1");
      return 0;
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vector<ll>>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double pi=3.14159265358979323846;
bool chmin(auto &a,auto b){if(a>b){a=b;return true;}return false;}
bool chmax(auto &a,auto b){if(a<b){a=b;return true;}return false;}
void outvi(vi v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
void outvvi(vvi v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}
vector<vector<P>> g;
vi ans;
void dfs(ll i,ll p,ll a){
    ll k=-1;
    rep(j,g[i].size()){
        k++;
        auto x=g[i][j];
        if(x.fi==p){
            k--;
            continue;
        }
        if(k+1<a)ans[x.se]=k+1;
        else ans[x.se]=k+2;
        dfs(x.fi,i,ans[x.se]);
    }
}
int main(){
    ll n;cin>>n;
    ans=vi(n-1);
    g=vector<vector<P>>(n);
    rep(i,n-1){
        ll a,b;cin>>a>>b;a--;b--;
        g[a].eb(b,i);
        g[b].eb(a,i);
    }
    dfs(0,-1,inf);
    ll ma=0;
    rep(i,n-1)chmax(ma,ans[i]);
    cout<<ma<<endl;
    rep(i,n-1)cout<<ans[i]<<endl;
}

Measured memory_bytes: 8832
#include <iostream>
#include<math.h>
#include<string>
#include<iomanip>
#include <limits>
#include<stdlib.h>
using namespace std;

int main()
{
long x,a,b; cin>>x>>a>>b;
if(abs(x-a)<abs(x-b)) cout<<"A";
else cout<<"B";
}


Measured memory_bytes: 3592
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

ans = sum(s)
s.sort()
if ans % 10 == 0:
    for i in range(N):
        if s[i] % 10 != 0:
            ans -= s[i]
            break
if ans % 10 == 0:
    ans = 0
print(ans)


Measured memory_bytes: 7104
n = gets.chop.to_i
a = gets.chop.split.map(&:to_i)

# sum = 0
# ans = 0
# (0..n-1).each do |l|
#   xor, sum = 0, 0
#   (l..n-1).each do |r|
#     sum += a[r]
#     xor ^= a[r]
#     ans += 1 if sum == xor
#     break if sum != xor
#   end
# end

sum = 0
xor = 0
ans = 0
l = 0
r = 0
while r < n do
  if sum + a[r] == xor ^ a[r]
    sum += a[r]
    xor ^= a[r]
    ans += r - l + 1
    r += 1
  else
    sum -= a[l]
    xor ^= a[l]
    l += 1
  end
end
p ans


Measured memory_bytes: 16652
a,b,c=map(int,input().split())
if a>=b>=c:
    print(f'{c} {b} {a}')
elif a>=c>=b:
    print(f'{b} {c} {a}')
elif b>=a>=c:
    print(f'{c} {a} {b}')
elif b>=c>=a:
    print(f'{a} {c} {b}')
elif c>=a>=b:
    print(f'{b} {a} {c}')
else:
    print(f'{a} {b} {c}')


Measured memory_bytes: 5608
/*
 　　　　　／＞　 フ
 　　　　　| 　_　 _|
 　 　　　／`ミ _x 彡
 　　 　 /　　　 　 |
 　　　 /　  ヽ　　 ?
 　／￣|　　 |　|　|
 　| (￣ヽ＿_ヽ_)_)
 　＼二つ
*/
  
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template<typename F>
inline void write(F x, char ed = '\n') {
	static short st[30];short tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
	putchar(ed);
}

template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y, 0); }

template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

const int N = 50500;
int vis[N], cnt, n, s, t;
int h[N], ne[N<<1], to[N<<1], w[N<<1]; ll dis[N], d[N<<1], tot = 1;
inline void add(int x, int y, int z, ll t) {
	ne[++tot] = h[x], to[h[x] = tot] = y, w[tot] = z, d[tot] = t;
}
inline void adde(int x, int y, int z, ll t) { add(x, y, z, t), add(y, x, 0, -t); }
const int inf = 0x3f3f3f3f;
queue<int> q;
bool spfa(void) {
	memset(dis, -0x3f, cnt * 8 + 30);
	memset(vis, 0, cnt * 4 + 30);
	q.push(s), dis[s] = 0;
	while (q.size()) {
		int x = q.front(); q.pop(); vis[x] = 0;
		for (int i = h[x]; i; i = ne[i]) {
			int y = to[i]; if (!w[i] || dis[y] >= dis[x] + d[i]) continue;
			dis[y] = dis[x] + d[i]; if (!vis[y]) vis[y] = 1, q.push(y);
		}
	}
	return dis[t] > -1e15;
}

int dfs(int x, int lim) {
	if (x == t || !lim) return lim;
	int res = 0, fl; vis[x] = 1;
	for (int i = h[x]; i; i = ne[i]) {
		int y = to[i]; if (vis[y]) continue;
		if (!w[i] || dis[y] != dis[x] + d[i]) continue;
		fl = dfs(y, min(w[i], lim));
		w[i] -= fl, w[i^1] += fl;
		res += fl, lim -= fl;
		if (!lim) return res;
	}
	return res;
}

int main() {
	read(n); cnt = 2 * n, s = ++cnt, t = ++cnt;
	int t1 = ++cnt, t2 = ++cnt, t3 = ++cnt, t4 = ++cnt;
	for (int i = 1, x, y, z;i <= n; i++) {
		read(x), read(y), read(z);
		adde(s, i, z, 0);
		adde(i, t1, inf, x + y);
		adde(i, t2, inf, x - y);
		adde(i, t3, inf, -x + y);
		adde(i, t4, inf, -x - y);
	}
	for (int i = 1, x, y, z; i <= n; i++) {
		read(x), read(y), read(z);
		adde(i + n, t, z, 0);
		adde(t1, i + n, inf, -x - y);
		adde(t2, i + n, inf, -x + y);
		adde(t3, i + n, inf, x - y);
		adde(t4, i + n, inf, x + y);
	}
	ll ans = 0;
	while (spfa()) 
		ans += dis[t] * dfs(s, inf);
	write(ans);
	return 0;
}

Measured memory_bytes: 3500