akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  string s; cin >> s;
  int w; cin >> w;

  string ans="";
  rep(i,s.size()){
    if(i%w==0) ans+=s[i];
  }

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


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

using namespace std;

int main() {
	int n;
	cin>>n;
	int x;
	cin>>x;
	int *a=new int[n];
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	long long int temp_sum=0;
	for(int i=0;i<n;i++){
		temp_sum+=a[i];
	}
	if(temp_sum==x){
		cout<<n<<endl;
	}else{
		temp_sum=0;
		bool full=true;
		for(int i=0;i<n;i++){
			temp_sum+=a[i];
			if(temp_sum>x){
				cout<<i<<endl;
				full=false;
				break;
			}
		}
		if(full){
			cout<<n-1<<endl;
		}
	}
	delete[] a;

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();

		int ans = Math.max(A+B, Math.max(A-B, A*B));

		System.out.println(ans);
	}
}



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

int main() {
  int N;
  int ap, bp = 0;
  cin >> N;
  vector<int> a(N);
  for(int i = 0; i < N; i++) {
    cin >> a.at(i);
  }
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());
  for(int i = 0; i < N; i++) {
    if(i%2 == 0) {
      ap += a.at(i);
    }
    else {
      bp += a.at(i);
    }
  }
  cout << ap- bp << endl;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map { it.toInt() }
    val x = readLine()!!.split(' ').map { it.toInt() }.sorted()

    val distances = IntArray(m) {0}
    var prev = x[0]
    var ans = x[x.size-1] - x[0]
    repeat(m) {
        val dist = x[it] - prev
        distances[it] = dist
        prev = x[it]
    }
    distances.sortDescending()


    repeat(Math.min(n-1,m)) {
        ans -= distances[it]
    }
    println(ans)
}


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

using namespace std;

int main()
{
	int N;
	cin >> N;
	vector<int> a(N);
	for (auto &x : a) {
		cin >> x;
	}

	int ans = 0;
	for (auto x : a) {
		for (; x % 2 == 0; x /= 2) {
			++ans;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <functional>
#include <random>
#include <time.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
int main() {
	ll c[4][4];
	for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)cin >> c[i][j];
	for (int i = -200; i <= 200; i++) {
		for (int j = -200; j <= 200; j++) {
			for (int k = -200; k <= 200; k++) {
				ll a[4], b[4];
				a[1] = i, a[2] = j, a[3] = k;
				b[1] = c[1][1] - a[1];
				b[2] = c[2][2] - a[2];
				b[3] = c[3][3] - a[3];
				bool f = 1;
				for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++) {
					if (a[i] + b[j] != c[i][j]) {
						f = 0;
						break;
					}
				}
				if (f) {
					cout << "Yes" << endl;
					return 0;
				}
			}
		}
	}
	cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().strip()

def main():
    N, Y = map(int,input().split())

    for a in range(N+1):
        for b in range(N+1):
            if N-a-b>=0:
                c = N-a-b
            else:
                break
            if 10000*a+5000*b+1000*c == Y:
                print(a,b,c);exit()
    print(-1,-1,-1)

main()

Measured memory_bytes: 3060
#include <cstdio>
#include <algorithm>    
#include <iostream>
#include <vector>
#include <queue>
// #include <map>
#include <iomanip>
#include <cstring>
#include <cmath>
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
typedef long double LD;
typedef unsigned int uii;
typedef pair<int,int> pii;
typedef unsigned long long uLL; 
typedef vector<int> vii; 
const int maxn = 5000;
char s[maxn], t[maxn];
int d[maxn][maxn];
pii r[maxn][maxn];

int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> (s + 1) >> (t + 1);
	int n = strlen(s + 1), m = strlen(t + 1);
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			if(s[i] == t[j]){
				d[i][j] = d[i - 1][j - 1] + 1;
				r[i][j] = pii(-1, -1);
			} else {
				// d[i][j] = max(d[i - 1][j], d[i][j - 1]);
				if(d[i - 1][j] > d[i][j - 1]){
					d[i][j] = d[i - 1][j];
					r[i][j] = pii(-1, 0);
				} else {
					d[i][j] = d[i][j - 1];
					r[i][j] = pii(0, -1);
				}
			}
		}
	}
	string res;
	int x = n, y = m;
	while(x > 0 && y > 0){
		// cout << x << ' ' << y << endl;
		pii t = r[x][y];
		if(t == pii(-1, -1)){
			res.push_back(s[x]);
		}
		x += t.first;
		y += t.second;
	}
	reverse(all(res));
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 177792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  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 *= a.x) %= mod;
    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 pow(ll t) const {
    if(!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if(t & 1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
};

struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for(int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for(int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) {
    if(k < 0 || k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

string n;
combination c(100);

ll f(int i, int k, bool smaller) {
  if(k == 0) return 1;
  if(i == n.size()) return 0;
  if(smaller) return c(n.size() - i, k).x * pow(9, k);
  if(n[i] == '0') return f(i + 1, k, false);
  return f(i + 1, k, true) + (n[i] - '1') * f(i + 1, k - 1, true) +
         f(i + 1, k - 1, false);
}

int main() {
  int k;
  cin >> n >> k;
  cout << f(0, k, false) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
long long read(){
    long long x=0,y=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')y=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*y;
}
long long a[2000010];
long long st[2000010];
long long l[2000010],r[2000010];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    a[i]=read();
	int top=0;
	for(int i=1;i<=n;i++) l[i]=0,r[i]=n+1;
	for(int i=1;i<=n;i++){
		while(top&&a[st[top]]>=a[i]) r[st[top--]]=i;
		l[i]=st[top];
		st[++top]=i;
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
	    ans+=(long long)((r[i]-i)*(i-l[i])*a[i]);
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 14080
Option Infer On
Imports System.Collections.Generic
Imports System.Console
Imports System.Math

Module Program
    Sub Main()
        Dim N As Integer = NextInt()
        Dim M As Integer = NextInt()

        Dim students = New Integer(N - 1, 1) {}
        Dim checkPoints = New Integer(M - 1, 1) {}

        For i = 0 To N - 1
            students(i, 0) = NextInt()
            students(i, 1) = NextInt()
        Next

        For i = 0 To M - 1
            checkPoints(i, 0) = NextInt()
            checkPoints(i, 1) = NextInt()
        Next

        For i = 0 To UBound(students)
            Dim index = -1
            Dim value = Integer.MaxValue
            For j = 0 To UBound(checkPoints)
                Dim x1 = students(i, 0)
                Dim y1 = students(i, 1)
                Dim x2 = checkPoints(j, 0)
                Dim y2 = checkPoints(j, 1)
                Dim Calc_result = Calc(x1, x2, y1, y2)

                If Calc_result < value Then
                    index = j
                    value = Calc_result
                End If
            Next
            WriteLine(index + 1)
        Next
    End Sub

    Function Calc(x1 As Integer, x2 As Integer,
                  y1 As Integer, y2 As Integer) As Integer
        Return Abs(x1 - x2) + Abs(y1 - y2)
    End Function

    Function NextInt() As Integer
        Return CInt(NextString())
    End Function

    Function NextString() As String
        Dim result As New List(Of Char)
        Do
            Dim tmp = Read()
            If tmp < 0 Then Exit Do
            Dim nextChar = Chr(tmp)

            If Not Char.IsWhiteSpace(nextChar) Then
                result.Add(nextChar)
            ElseIf nextChar <> vbCr Then
                Exit Do
            End If
        Loop
        Return New String(result.ToArray())
    End Function

End Module


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

int main() {
  int N,X1,X2,X3,X4;
  cin>>N;
  X1=N/1000;
  X2=(N-X1*1000)/100;
  X3=(N-X1*1000-X2*100)/10;
  X4=(N-X1*1000-X2*100-X3*10)/1;
  if(X2==X3){if(X2==X1||X2==X4){cout<<"Yes"<<endl;} else{cout<<"No"<<endl;}}
  else{cout<<"No"<<endl;}
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
long long mod = 1000000007;
long long powmod(long long x, long long y){
    long long res = 1;
    for(long long i = 0; i < y; i++){
        res = res*x%mod;
    }
    return res;
}
int main() {
    long long N;
    cin >> N;
    long long ans;
    ans = powmod(10, N) - powmod(9, N) - powmod(9, N) + powmod(8, N);
    ans %= mod;
    ans = (ans + mod) % mod;
    cout << ans << endl;
    
    return 0;
}


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

int main(void) {
    int N;
    cin >> N;
    vector< int > a(N + 1);
    for (int i = 0; i < N; ++i) {
        cin >> a[i + 1];
    }
    vector< int > ans(N + 1);
    int min = (N + 1) / 2;
    int max = N;
    while (min > 0) {
        for (int i = max; i >= min; --i) {
            int count = 0;
            int num = i;
            for (int j = 2; num * j <= N; ++j) {
                count += ans[num * j];
            }
            ans[i] = (count % 2 == a[i]) ? 0 : 1;
        }
        max = min - 1;
        min = min / 2;
    }
    vector< int > v;
    int count = 0;
    for (int i = 0; i < N; ++i) {
        if (ans[i + 1] == 1) {
            ++count;
            v.push_back(i + 1);
        }
    }
    printf("%d\n", count);
    for (int i = 0; i < count - 1; ++i) {
        printf("%d ", v[i]);
    }
    if (count > 0) {
        printf("%d\n", v[count - 1]);
    }
    return 0;
}


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x)  for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
inline void read(int &x){
	x=0;char ch=getchar();int f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}x*=f;
}
inline void judge(){
	freopen("table.in","r",stdin);
	freopen("table.out","w",stdout);
}
const int maxn=100005;
typedef long long i64;
int num,n,m,head[maxn],t[maxn<<1],ne[maxn<<1],v[maxn<<1];
inline void addedge(int x,int y,int z){
	ne[++num]=head[x];head[x]=num;t[num]=y;v[num]=z;
}
bool vis[maxn];
int cnt[4],d[maxn],T;
bool godie=0;
inline void dfs(int x,int l){
	vis[x]=1;d[x]=l;cnt[l]++;
	forE(i,x)if(!vis[t[i]]){
		dfs(t[i],(l+v[i])%3);T++;
	}else{
		if((l+v[i])%3!=d[t[i]])godie=1;T++;
	}
}i64 ans=0;
int main(){
//	judge();
	read(n);read(m);
	rep(i,1,n)head[i]=-1;
	rep(i,1,m){
		int x,y;read(x);read(y);
		addedge(x,y,1);
		addedge(y,x,2);
	}
	rep(i,1,n){
		if(vis[i])continue;memset(cnt,0,sizeof(cnt));godie=0;T=0;
		dfs(i,0);i64 sum=cnt[0]+cnt[1]+cnt[2];
		if(godie){
			ans+=sum*sum;continue;	
		}else{
			if(cnt[0]&&cnt[1]&&cnt[2]){
				ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[0]*cnt[2]+1ll*cnt[1]*cnt[2];
			}else{
				ans+=T/2;
			}
		}
	}cout<<ans<<endl;
}

Measured memory_bytes: 4992
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		int W = scan.nextInt();
		int H = scan.nextInt();
		int x = scan.nextInt();
		int y = scan.nextInt();
		int r = scan.nextInt();

		boolean result1 = (x+r) <= 0 ? false : W >= (x+r) ? true : false;
		boolean result2 = (y+r) <= 0 ? false : H >= (y+r) ? true : false;

		if(result1 & result2){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}

		scan.close();

	}
}

Measured memory_bytes: 26416
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
typedef long long ll;
const int INF = 100000000, mod = 1000000007;
const ll LLINF = 1LL << 50;
using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    string c = a + b;
    int num = stoi(c);
    int h = sqrt(num);
    if (num%h == 0)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
li = list(map(int,input().split()))
n=li[0]
ans = 0
for i in range(1,n+1):
    if i%2==0:
        continue
    count = 0
    for j in range(1,i+1):
        if i%j==0:
            count+=1
    if count == 8:
        #print(i)
        ans+=1
print(ans)

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

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

ll gcd(ll a, ll b) {
  return b != 0 ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

int main(){
    ll a,b;
    cin>>a>>b;
    out(lcm(a,b));
    
    
}


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

using namespace std;

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

    bool flag = true;
    for (int i = 0; i < s.length(); ++i) {
        if (i % 2 == 0 and s[i] == 'L') flag = false;
        if (i % 2 != 0 and s[i] == 'R') flag = false;
    }

    cout << (flag ? "Yes" : "No") << endl;
    return 0;
}


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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int A,B,C; cin>>A>>B>>C;
	for (int i=0; i<B; i++)
		if(i*A%B==C) { cout << "YES" << endl; return 0; }
	cout << "NO" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <set>
#define fr(i,b,e) for(int i=(b); i<(e); ++i)
#define all(x) (x).begin(),(x).end()

using namespace std;
typedef long int li;
typedef long long ll;

int chk(vector<int> a){
    int n=a.size();
    fr(i,0,n){
        cout << a.at(i);
    }
    cout << endl;
}

int gcd(int a,int b){ //a>b
    int tmp=a%b;
    a=b;
    b=tmp;
    if(b!=0){
        return gcd(a,b);
    }else{
        return a;
    }
}

ll power(ll a,ll n){
    if(n==1){
        return a;
    }
    else if(n&1==1){
        --n;
        return power(a,n)*a;
    }else{
        n=n>>1;
        return power(a,n)*power(a,n);
    }
}

int main(void){
    int n;
    cin >> n ;
    vector<int> in(n);

    fr(i,0,n){
        cin >> in.at(i);
    }
    
    fr(i,0,n){
        if(in.at(i)%2==1){
            in.at(i)=0;
        }
    }

    fr(i,0,n){
        if(in.at(i)%3==0){
            in.at(i)=0;
        }
    }

    fr(i,0,n){
        if(in.at(i)%5==0){
            in.at(i)=0;
        }
    }

    int sum=0;
    fr(i,0,n){
        sum+=in.at(i);
    }
    if(sum==0){
        cout << "APPROVED" << endl;
    }else{
        cout << "DENIED" << endl;
    }
}

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

int main()
{
  int n;
  cin >> n;
  
  vector<int> dp(3);
  for(int day = 0;day < n; ++day)
  {
      vector<int> c(3);
      for(int i=0;i<3;++i)
      {
          cin >> c[i];
      }
      vector<int> new_dp(3, 0);
      for(int i=0;i<3;++i)
      {
          for(int j=0;j<3;++j)
          {
              if(i != j)
              {
                  new_dp[j] = max(new_dp[j], dp[i] + c[j]);
              }
          }
      }
      dp = new_dp;
  }
  cout << max(dp[0], max(dp[1], dp[2])) << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int A = in.nextInt();
            int B = in.nextInt();
            int C = in.nextInt();
            int D = in.nextInt();
            System.out.println(Math.max(0, Math.min(B, D) - Math.max(A, C)));
        }
    }
}


Measured memory_bytes: 27084
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

int main(int argc, char *argv[])
{
  int A, B, v = 0, ans = 0;
  cin >> A >> B;

  for (int i = A; i <= B; i++) {
    int tmp[5], vv = i;
    for (int j = 0; j < 5; j++) {
      tmp[j] = vv % 10;
      vv /= 10;
    }

    if ((tmp[0] == tmp[4]) && (tmp[1] == tmp[3])) ans++;
  }
  printf("%d\n", ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long ul;
// for文短縮類
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
// iteratorのbeginとendをまとめて渡す
#define ALL(x) (x).begin(), (x).end()
//略
#define PB push_back  // vectorヘの挿入
#define MP make_pair  // pairのコンストラクタ
#define F first       // pairの一つ目の要素
#define S second      // pairの二つ目の要素
//出力
#define COUT(x) cout << (x) << endl
#define SCOUT(x) cout << (x) << " "
#define ENDL cout << endl
/************ Combination wtih MOD ************
const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];
// preprocess for some tables
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;
  }
}
// combination
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;
}
*******************************************************/
int main(int argc, char *argv[]) {
  // input高速化。cinとcoutの結合解除。scanfとprintfは使えない。
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  ll a;
  cin >> a;
  cout << a + pow(a, 2) + pow(a, 3) << endl;
}

Measured memory_bytes: 4176
#include<stdio.h>
int main(){

  int d,a,s=0;
  while(scanf("%d",&d)!=EOF){
    s=0;

  for(a=0;a<600/d-1;++a){
    s+=d*(a+1)*d*(a+1)*d;
      }
  printf("%d\n",s);
  }
 return 0;
}

Measured memory_bytes: 596
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    if v.iter().sum::<usize>() >= 22 {
        println!("bust");
    } else {
        println!("win");
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 4352
from copy import deepcopy as cp
h,w,k=map(int,input().split())
l=[list(input()) for _ in range(h)]

cnt=0
for i in range(2**h):
  for j in range(2**w):
    tmp=cp(l)
    for b in range(h):
      if (i>>b)&1:
        tmp[b]=['.']*w
    for b in range(w):
      if (j>>b)&1:
        for c in range(h):
          tmp[c][b]='.'
    black=0
    for r in tmp:
      black+=r.count('#')
    if black==k:
      cnt+=1
print(cnt)

Measured memory_bytes: 74412
#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <utility>
using namespace std;
using ll = long long;
using P = pair<int,int>;

const int di[]={-1, 0, 1, 0};
const int dj[]={ 0,-1, 0, 1};

int main(){
    int H,W;
    cin>>H>>W;
    int Ch,Cw;
    cin>>Ch>>Cw;
    int Dh,Dw;
    cin>>Dh>>Dw;
    Ch--; Cw--; Dh--; Dw--;
    vector<string> S(H);
    for(int i=0; i<H; ++i) cin>>S[i];

    //01-BFS
    vector<vector<int>> dist(H,vector<int>(W,1e9));
    deque<P> q;
    dist[Ch][Cw]=0;
    q.emplace_back(Ch,Cw);
    while(!q.empty()){
        int i = q.front().first;
        int j = q.front().second;
        q.pop_front();
        int d = dist[i][j];
        for(int n=0; n<4; ++n){
            int ni=i+di[n], nj=j+dj[n];
            if(ni<0 || ni>=H || nj<0 || nj>=W) continue;
            if(S[ni][nj]=='#') continue;
            if(dist[ni][nj] <= d) continue;
            dist[ni][nj] = d;
            q.emplace_front(ni,nj);
        }
        for(int ei=-2; ei<=2; ++ei){
            for(int ej=-2; ej<=2; ++ej){
                int ni=i+ei, nj=j+ej;
                if(ni<0 || ni>=H || nj<0 || nj>=W) continue;
                if(S[ni][nj]=='#') continue;
                if(dist[ni][nj] <= d+1) continue;
                dist[ni][nj] = d+1;
                q.emplace_back(ni,nj);
            }
        }
    }
    int ans = dist[Dh][Dw];
    if(ans==1e9) ans=-1;
    cout<<ans<<endl;
}

Measured memory_bytes: 9516
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 10 ;
int a[N] , b[N] ;
struct node
{
	int x , y , c ;
}c[N] ;
int main()
{
	 int n , m , k ;
	 scanf("%d%d%d" , &n , &m , &k) ;
	 for(int i = 1; i <= n ;i ++) scanf("%d" , &a[i]) ;
	 for(int i = 1; i <= m ;i ++) scanf("%d" , &b[i]) ;
   int ans = 1000000000 ;
	 for(int i = 1; i <= k ;i ++)
	 {
		 int x , y , c ;
		 scanf("%d%d%d" , &x , &y , &c) ;
		 ans = min(ans , a[x] + b[y] - c) ;
	 }
	 sort(a + 1 , a + n + 1) ;
	 sort(b + 1 , b + m + 1) ;
	 ans = min(ans , a[1] + b[1]) ;
	 cout << ans << endl ;
	 return 0 ;
}


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

int main() {
  
  int a, b, c, d;

  cin >> a >> b >> c >> d;

  if((a + b) > (c + d))
    cout << "Left" << endl;
  if((a + b) < (c + d))
    cout << "Right" << endl;
  if((a + b) == (c + d))
    cout << "Balanced" << endl;
    
}

Measured memory_bytes: 256
#include <iostream>

bool dfs(int a, int b, int c, int k) {
  if (b > a && c > b)
    return true;
  if (k == 0)
    return false;
  --k;
  return dfs(a * 2, b, c, k) || dfs(a, b * 2, c, k) || dfs(a, b, c * 2, k);
}

int main(int argc, char *argv[]) {
  int a, b, c, k;
  std::cin >> a >> b >> c >> k;
  std::cout << (dfs(a, b, c, k) ? "Yes" : "No") << std::endl;
}


Measured memory_bytes: 3100
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#include"debug_deque.hpp"
#define vector DebugDeque
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

struct Stuple {
    int s; int t; int c;
    using type = tuple<int, int, int>;
    Stuple(int s, int t, int c): s(s), t(t), c(c){ }
    operator tuple<int, int, int> () const { return make_tuple(s, t, c); }
    bool operator < (const Stuple& e) const { return type(*this) < type(e); }
    ostream& operator >> (ostream& out) const { prints(type(*this)); return out; }
    // bool operator < (const Stuple& e) const { return tie(s, t, c) < tie(e.s, e.t, e.c); }
    // ostream& operator >> (ostream& out) const { prints(tie(s, t, c)); return out; }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, c;
    cin >> n >> c;
    // set<tuple<int, int, int>> stcs;
    set<Stuple> stcs;
    for(int i = 0; i < n; i++){
        int s, t, c;
        cin >> s >> t >> c;
        stcs.emplace(s, t, c);
    }
    int ans = 0;
    prints(stcs);
    while(stcs.size()){
        ans++;
        auto next = stcs;
        int time = -1, channel = -1;
        for(auto& stc : stcs){
            // if(time + (channel != get<2>(stc)) <= get<0>(stc)){
            //     time = get<1>(stc);
            //     channel = get<2>(stc);
            //     next.erase(stc);
            // }
            // get<0>(stc.data) = 1;
            // decltype(auto) a = get<0>(stc.data);
            // a = 1;
            // stc.t = 1;
            if(time + (channel != stc.c) <= stc.s){
                time = stc.t;
                channel = stc.c;
                next.erase(stc);
            }
        }
        next.swap(stcs);
    }
    cout << ans << '\n';
}


Measured memory_bytes: 14848
n = int(input())
l = list(map(int, input().split()))
ans = 0
l = sorted(l)
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[i] != l[j] != l[k] != l[i]:
                if l[i] + l[j] > l[k]:
                    ans += 1
print(ans)


Measured memory_bytes: 9168
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
#define iter(v,ite) for(auto ite=(v).begin();ite!=(v).end();ite++)
#define mimunum(v,x) distance((v).begin(),lower_bound((v).begin(),(v).end(),x))


int n;
lli dat[100005];
int main(void){
	scanf("%d",&n);
	rep(i,n)scanf("%lld",&dat[i]);
	
	lli ans=LINF;
	rep(t,2){
		lli rs=0;
		lli na=0;
		int s=1;
		if(t)s*=-1;
		
		rep(i,n){
			rs += dat[i];
			if(s*rs<=0){
				na += abs(rs - s);
				rs = s;
			}
			s *= -1;
		}
		ans = min(ans,na);
	}
	printf("%lld\n",ans);
	return 0;
}






Measured memory_bytes: 1024
#LIS
n=int(input())
lists=[0]*n
for i in range(n):
    lists[i]=int(input())
import bisect
counter=0
lislist=[lists[-1]]
for i in range(2,n+1):
    a=lists[-i]
    index=bisect.bisect_right(lislist,a)
    if index<len(lislist):
        lislist[index]=a

    elif index==len(lislist):
        lislist.append(a)

print(len(lislist))


Measured memory_bytes: 50392
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    for(int i=0;i<S.size();i++){
            S[i] = S[i] + N;
            if(S[i]>'Z'){
                S[i] = 64 + (S[i]-'Z');
            }
    }
    cout << S << endl;
    return 0;
}

Measured memory_bytes: 3636
# coding: utf-8
# Your code here!


k,a,b = [int(i) for i in input().split()]

if b - 2 <= a:
    print(1+k)
else:
    d = b-a
    ans=a
    k-= a-1
    if k <= 0:
        print(1+k+a-1)
    else:
        if k%2==0:
            print(ans + d*k//2)
        else:
            print(ans + 1+d*(k//2))
        


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 1000000007;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define sz(x) ((int)(x).size())


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

    int n;
    cin >> n;
    vi a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    vi b(n);
    vi ans;
    for(int i = n-1; i >= 0; i--){
        int count = 0;
        for(int j = i; j < n; j+=i+1){
            count += b[j];
        }
        if(count%2 != a[i]) ans.push_back(i), b[i]=1;
    }
    cout << sz(ans) << "\n";
    for(int i = 0; i < sz(ans); i++) cout << ans[i]+1 << " ";
    cout << "\n";
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<string.h>
using namespace std;
#define pb push_back
#define all(v) v. begin(),v. end()
#define  rep(i,n,v) for(i=n;i<v;i++)
#define per(i,n,v) for(i=n;i>v;i--)
#define ff first 
#define ss second 
#define pp pair<ll,ll>
#define ll  long long
#define endl '\n'
void solve()
{
  ll n, a,m=0,b=1, c,k=0, i, j,l=1e9+7;
  string s, r, y;
  getline(cin,s);
  cout<<s[0];
   rep(i,1,s.length())
   {
     if(s[i-1]==' ') cout<<s[i];
   }
   cout<<endl;
}
int main()
{
 ios_base::sync_with_stdio(false);
  cin. tie(0);cout. tie(0);
    ll t=1;
   //cin>>t;
    while(t--)
    {
      solve();
    }
    return 0;
}

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

using namespace std;
const int N=500+7;
struct Node{
    int ind,val;
}node[N];
int a[N*N];
int cmp(Node a,Node b)
{
    return a.ind<b.ind;
}
int main()
{
    int n;
    memset(a,0,sizeof(a));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&node[i].ind);
        node[i].val=i;
    }
    sort(node+1,node+n+1,cmp);
    int flag=1,top=1;
    for(int i=1;i<=n&&flag;i++)
    {
        int ind=node[i].ind,val=node[i].val;
        a[ind]=val;
        for(int j=1;j<=val-1;j++)
        {
            while(a[top]) top++;
            a[top]=val;
        }
        if(top>ind)
        {
            flag=0;break;
        }
    }

    for(int i=1;flag&&i<=n;i++)
    {
        int ind=node[i].ind,val=node[i].val;
        for(int j=1;j<=n-val;j++)
        {
            while(a[top]) top++;
            if(top<ind)
            {
                flag=0;break;
            }
            a[top]=val;
        }
    }
    if(flag)
    {
        puts("Yes");
        for(int i=1;i<=n*n;i++)
            printf("%d%c",a[i],i==n*n?'\n':' ');
    }
    else
        puts("No");
    return 0;
}


Measured memory_bytes: 2176
#include <bits/stdc++.h> 
using namespace std;
///////////////////////////////////////////
const long long int INF = INT32_MAX;
const long long int Mod = 1000000007;
const long long int mod = 100000;//10^5
using ll = long long int; //long long int は64bit
using ci = const int; using vi = vector<int>; using Vi = vector<long long int>; using pii = pair<int,int>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(int i=0;i<N;i++)
#define np nullptr
template<class T>bool chmax(T &former, const T &b) { if (former<=b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define fill(x,num) memset(x,num,sizeof(x));
typedef vector<vector<ll> > matrix;
//       cin.tie(0);ios::sync_with_stdio(false);
void cinit(){cin.tie(0);ios::sync_with_stdio(false);}
//////////////////////////^^ *Emile ^^^//////////////////////////////////////////////////////

int main(){
	ll n,h,w;
	cin>>n>>h>>w;
	cout<<(n-h+1)*(n-w+1)<<endl;
	return 0;
}

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

int N;
const int INT_MAX = 100100;
string s[INT_MAX];
std::set<string> c;
std::map<std::string, long long int> res;

int main()
{

  cin >> N;
  long long int ans = 0;

  for (int i = 0; i < N; i++) {
    string s;
    cin >> s;
    std::sort(s.begin(), s.end());

    if (res.find(s) == res.end()) { // not found
      res.insert(std::make_pair(s, 0));
    } else {
      res[s]++;
    }
  }
  
  for(auto itr = res.begin(); itr != res.end(); ++itr) {
    if (itr->second != 0) {
      long long int temp = itr->second * ( itr->second + 1) / 2;
      ans += temp;
    } else if (itr->second == 1) {
      ans += 1;
    }
  }

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

Measured memory_bytes: 13952
package main

import "fmt"

func main() {
	var a, b, c, d int
	fmt.Scan(&a, &b, &c, &d)
	for{
		c -= b

		if c <= 0{
			fmt.Println("Yes")
			break
		}

		a -= d

		if a <= 0{
			fmt.Println("No")
			break
		}
	}

}

Measured memory_bytes: 1752
#include<bits/stdc++.h>
#define pi acos(-1)
#define ll long long
#define pii pair<ll,ll>
#define debug(a) cout<<a<<'\n'
#define maxn 100009 /// leave to tomorrow anything that can be done today
#define MOD 1000000007
#define F first
#define S second
#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define per(i, b, a) for(ll i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (ll)(x).size()
using namespace std;
const ll INF = 1e17 + 9;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll x,y;
    cin>>x>>y;
    if(y%2){
        cout<<"No\n";
        return 0;
    }
    ll yact=y/2;
    int cont=0;
    while(yact+cont>x && yact>1){
        yact-=2;
        cont++;
    }
    if(yact+cont==x)cout<<"Yes\n";
    else cout<<"No\n";
    return 0;   
}   

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	int n;
	cin >> n;
	//vector<long long> a(n);
	priority_queue<long long, vector<long long>, greater<long long>> q;
	for (int i = 0; i < n; i++) {
		//cin >> a[i];
		long long a;
		cin >> a;
		q.push(a);
	}

	while (q.size() >= 2) {
		long long tmp0 = q.top();
		q.pop();
		long long tmp1 = q.top();
		q.pop();
		long long r = tmp1 % tmp0;
		tmp1 = r;
		if (r != 0)
			q.push(r);
		q.push(tmp0);
	}
	cout << q.top() << endl;
	return 0;
}

Measured memory_bytes: 4328
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int M = 1000000007;

int h, w;

int frm(int i, int j) {
    if (i >= w * 2)
        return frm(i % (w * 2), j);
    if (i == 0)
        return j;
    if ((i + j) & 1)
        return i + j < w ? i + j : frm(i + j - w, w - 1);
    else
        return i <= j ? j - i : frm(i - j - 1, 0);
}

void swap(vector<int>& p, int i, int j) {
    int t = p[i];
    p[i] = p[j];
    p[j] = t;
}

int main() {
    int n;
    cin >> h >> w >> n;
    vector<P> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end());
    vector<int> p(w);
    for (int i = 0; i < w; ++i) {
        p[i] = i;
    }
    for (P i : v) {
        swap(p, frm(i.first - 1, i.second - 1), frm(i.first - 1, i.second));
    }
    vector<int> ans(w);
    for (int i = 0; i < w; ++i) {
        ans[p[frm(h, i)]] = i + 1;
    }
    for (int i : ans) {
        cout << i << "\n";
    }
    return 0;
}

Measured memory_bytes: 6004
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <typeinfo>
using namespace std;

int main(){
    string str; cin >> str;
    int n = str.size();
    vector<string> v;
    for(int i=0; i<n; ++i) v.push_back(str.substr(i, 1));
    long res = 0;
    
    for(int i=0; i<(1<<(n-1)); ++i){
        string sn= v[0]; // 数字部分列を保持
        
        for(int j=0; j<n-1; ++j){
            if(i & (1<<j)){
                res += stol(sn);
                sn = "";
            }
            sn += v[j+1];
        }
        res +=stol(sn);
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
while True:
    try:
        hit = 0
        blow = 0
        hit_idx = []
        s = list(map(int, input().split()))
        t = list(map(int, input().split()))
        for i in range(4):
            if s[i] == t[i]:
                hit_idx.append(i) 
        hit = len(hit_idx)                                
        for i in hit_idx[::-1]:     # reverse order
            s = s[:i] + s[(i+1):]
            t = t[:i] + t[(i+1):]
        for c in s:
            if c in t:
                blow += 1
                                
        print("%d %d" % (hit,blow)) 
    except:
        break

Measured memory_bytes: 7496
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define N 500010
 
//FenwickTree↓
int dat[N];
void init(){
    rep(i,N)dat[i]=0;
}
void add(int i,int x){
    for(;i<N;i+=i&-i)dat[i]+=x;
}
int sum(int i){
    int res=0;
    for(;i>0;i-=i&-i)res+=dat[i];
    return res;
}
int rangesum(int l,int r){//[l,r]
    return sum(r)-sum(l-1);
}
//FenwickTree↑
 
int a[N];
vector<int> ql[N],qid[N];
int ans[N];
 
int n,q,c[N];
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>c[i];
    rep(i,q){
        int l,r;
        cin>>l>>r;
        ql[r].push_back(l);
        qid[r].push_back(i);
    }
    init();
    for(int i=1;i<=n;i++)a[i]=0;
    for(int i=1;i<=n;i++){
        if(a[c[i]]>0)add(a[c[i]],-1);
        add(i,+1);
        a[c[i]]=i;
        rep(j,ql[i].size()){
            ans[qid[i][j]]=rangesum(ql[i][j],i);
        }
    }
    rep(i,q)cout<<ans[i]<<"\n";
}

Measured memory_bytes: 52944
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=998244353;
inline int addmod(int x)
{
	return x>=mod?x-mod:x;
}
inline int submod(int x)
{
	return x<0?x+mod:x;
}
int n,m,f[305][605][305],g[605][305],h[605][305],a[100005],at;
char s[100005];
int main()
{
	scanf("%s%d",s+1,&m);
	n=strlen(s+1);
	int las=0;
	for(int i=1;i<=n;i++)
		if(s[i]=='0')
		{
			a[++at]=i-las-1;
			las=i;
		}
	a[++at]=n-las;
	m=min(m,n);
	f[0][0][0]=1;
/*	printf("at=%d\n",at);
	for(int i=1;i<=at;i++)
		printf("%d ",a[i]);
	printf("\n");*/
	for(int i=0;i<at;i++)
	{
		memset(h,0,sizeof(h));
		for(int j=0;j<=2*n;j++)
			for(int k=0;k<=n;k++)
			{
				g[j][k]=f[i][j][k];
				if(k)
				{
					h[j+1][k-1]=addmod(h[j+1][k-1]+f[i][j][k]);
					if(k>a[i+1]) h[j+a[i+1]+1][k-a[i+1]-1]=submod(h[j+a[i+1]+1][k-a[i+1]-1]-f[i][j][k]);
				}
				/*for(int l=0;l<=n;l++)
				{
					if(k+l-a[i+1]<0) continue;
					int &v=f[i+1][j+abs(l-a[i+1])][k+l-a[i+1]];
					v=addmod(v+f[i][j][k]);
				}*/
			}
		for(int j=1;j<=2*n;j++)
			for(int k=1;k<=n;k++)
				g[j][k]=addmod(g[j][k]+g[j-1][k-1]);
		for(int j=1;j<=2*n;j++)
			for(int k=0;k<=n;k++)
				h[j][k]=addmod(h[j][k]+h[j-1][k+1]);
		for(int j=0;j<=2*n;j++)
			for(int k=0;k<=n;k++)
				f[i+1][j][k]=addmod(h[j][k]+g[j][k]);
	}
	/*for(int i=0;i<=at;i++)
		for(int j=0;j<=2*n;j++)
			for(int k=0;k<=n;k++)
				if(f[i][j][k])
				{
					printf("i=%d,j=%d,k=%d,f=%d\n",i,j,k,f[i][j][k]);
				}*/
	int ans=0;
	for(int i=0;i<=m;i++)
		ans=addmod(ans+f[at][2*i][0]);
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 218428
n = int(input())
a = list(map(int,input().split()))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

def search(x):
    l = [1 if i >= x else -1 for i in a]
    c = [n]
    for i in range(n):
        c.append(c[-1]+l[i])

    count = 0
    bit = Bit(2*n+1)
    for i in c:
        count += bit.sum(i+1)
        bit.add(i,1)
    
    return x,count

k = (n*(n+1)/2+1)//2
le = 0
ri = max(a)+1

while ri > le + 1:
    m = (ri+le)//2
    ans,count = search(m)

    if count >= k:
        le = m
    else:
        ri = m
print(le)


Measured memory_bytes: 175348
#include<iostream>
#include<list>
#include<vector>
#include<queue>
using namespace std;

class Vertex{
  int connection;
  int name;
  list<Vertex*> v_list;
  Vertex(int n):connection(0),name(n){}
  friend class Graph;
};

class Graph{
  vector<Vertex*> graph;
public:
  Graph(int size){
    graph.resize(size);
    for(int i=0;i<size;i++){
      graph[i]=new Vertex(i);
    }
  }

  ~Graph(){
    for(int i=0;i<(int)graph.size();i++){
      delete graph[i];
    }
  }

  void addEdge(int from,int to){
    graph[from]->v_list.push_back(graph[to]);
    graph[to]->connection++;
  }

  bool check(){
    queue<Vertex*> q;
    vector<Vertex*> vec;
    Vertex *v;

    for(int i=0;i<(int)graph.size();i++){
      if(graph[i]->connection==0) q.push(graph[i]);
    }

    while(!q.empty()){
      v=q.front();
      q.pop();
      vec.push_back(v);
      for(list<Vertex*>::iterator it=v->v_list.begin();it!=v->v_list.end();it++){
	Vertex* w=*it;
	if((--w->connection)==0){
	  q.push(w);
	}
      }
    }

    if(vec.size()==graph.size())
      return false;
    else
      return true;

  }

};

int main(){
  int v=0;
  int e=0;
  cin>>v>>e;
  Graph graph(v);
  for(int i=0;i<e;i++){
    int from,to;
    cin>>from>>to;
    graph.addEdge(from,to);
  }
  cout<<graph.check()<<endl;
  return 0;
}

Measured memory_bytes: 1252
n,m,R=list(map(int,input().split()))
r=list(map(int,input().split()))
dp=[[float("INF")]*n for i in range(n)]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  dp[a-1][b-1]=c
  dp[b-1][a-1]=c
for i in range(n):
  dp[i][i]=0
for k in range(n):
  for i in range(n):
    for j in range(n):
      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
from itertools import permutations
per=list(permutations(r,R))
ans=float("INF")
for tup in per:
  ans_kouho=0
  for i in range(R-1):
    ans_kouho=ans_kouho+dp[tup[i]-1][tup[i+1]-1]
  ans=min(ans,ans_kouho)
print(ans)

    
    

Measured memory_bytes: 81520
#include <bits/stdc++.h>
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) { os << "[ "; 
	for(auto v:V)os << v << " "; return os << "]";
}
template<class T> ostream& operator<<(ostream &os, set<T> S){ os << "{ "; 
	for(auto s:S) os<<s<<" ";  return os<<"}"; 
}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
	return os<<"("<<P.first<<","<< P.second << ")";
}
template<class L, class R> ostream& operator<<(ostream &os, map<L,R> M) {
	os<<"{ ";for(auto m:M)os<<"("<<m.F<<":"<<m.S<<")";
	return os<<"}";
}
#define cerr cout
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define I insert 
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define For(i,n) for(int i=0;i<(int)n;++i)
#define Rev(i,n) for(int i=(int)n-1;i>=0;--i)
#define Rep(i,n) for(int i=1;i<=(int)n;++i)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef vector<pii> vpii;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)


int main(){
	fio; cout<<fixed<<setprecision(25);	
	string s , t; cin >> s >> t;
	int ans = 0;
	for(int i = 0;i < s.size() ; ++i)
	ans += (s[i] != t[i]);
	cout << ans << endl;	





	return 0;
}


Measured memory_bytes: 3736
N = int(input())

a = list(map(int, input().split())) 

a.sort()

#print (a)

a = [-2] + a + [-8]

lst = []
count = 1
for i in range(1,N+2):
    if a[i] == a[i-1]:
        count += 1
    else:
        lst += [[a[i-1], count]]
        count = 1

# print (lst)

ans = 0
lst += [[-10,0], [-20,0]]
# print (lst)
for i in range(0, len(lst)-2):
    count = lst[i][1]
    if lst[i][0] + 1 == lst[i+1][0]:
        count += lst[i+1][1]
        if lst[i][0] +2 == lst[i+2][0]:
            count += lst[i+2][1]
    ans = max(ans, count)

print (ans)





Measured memory_bytes: 13964
<?php
  

$n = trim(fgets(STDIN));

for($i=0; $i<$n; $i++){
  list($a, $b) = explode(' ', trim(fgets(STDIN)));
  $s[$i] = $a;
  $t[$i] = $b;
}

$x = trim(fgets(STDIN));

for($i=0; $i<$n; $i++){
  if ($s[$i] == $x) $xnum = $i;
}

$ans = 0;
for($i=0; $i<$n; $i++){
  if ($i > $xnum) $ans += $t[$i];
}

echo $ans;

  
?>

Measured memory_bytes: 4728
#include<stdio.h>

int dp[111111];

int get_min(int a,int b){
	if(a < b)return a;
	else return b;
}

int main(){
	
	int n,i,tmp;
	
	scanf("%d",&n);
	
	for(i = 0;i < 111111;i++){
		dp[i] = 1000000000;
	}
	
	dp[0] = 0;
	
	for(i = 0;i < 111111;i++){
		tmp = 1;
		while(i + tmp < 111111){
			dp[i+tmp] = get_min(dp[i+tmp],dp[i]+1);
			tmp *= 6;
		}
		tmp = 9;
		while(i + tmp < 111111){
			dp[i+tmp] = get_min(dp[i+tmp],dp[i]+1);
			tmp *= 9;
		}
	}
	
	printf("%d\n",dp[n]);
	
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main() {
  int n, C;
  int d[30][30], pre[3][30], c[505][505];
  cin >> n >> C;
  rep(i, C) rep(j, C) cin >> d[i][j];
  rep(i, n) rep(j, n) cin >> c[i][j], c[i][j]--;

  rep(col, C) rep(i, n) rep(j, n) pre[(i + j) % 3][col] += d[c[i][j]][col];

  int ans = 1 << 30;
  rep(c0, C) rep(c1, C) rep(c2, C) if (!(c0 == c1 || c0 == c2 || c1 == c2))
      ans = min(ans, pre[0][c0] + pre[1][c1] + pre[2][c2]);

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

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

int main(){
	int n=0;
	string str;
	while(cin >> str){
		for(int i=0;i<str.size();i++){
			if(str[i] != str[str.size()-(i+1)]) break;
			if(i == str.size()-1) n+=1;
		}
	}
	cout << n << endl;
	return 0;
}

Measured memory_bytes: 0
/**
 * StructureProgramming.cpp
 * Create:20180420
 * Description:入力された数値nまでの
 * 3の倍数と、１の位が3となる数値を表記する。
 */
#include <iostream>

/**
 * 表記関数
 * @param n 判定対象数値
 */
void call(int i){
  int n = i;
  if (n % 3 == 0) {
    std::cout << " " << i;
  } else {
    while (n > 0) {
      if (n % 10 == 3){
        std::cout << " " << i;
        break;
      }
      n /= 10;
    }
  }
}

int main(int argc, char* argv[]){
  int n;

  std::cin >> n;

  for (int i = 3; i <= n; i++){
    call(i);
  }

  std::cout << std::endl;

  return 0;
}


Measured memory_bytes: 3096
n = int(input())

def f(x, y, z):
    return x**2 + y**2 + z**2 + x*y + y*z + z*x
lst = [0 for i in range(n)]
for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            num = f(i, j, k)
            if num <= n:
                lst[num-1] += 1

for i in lst:
    print(i)

Measured memory_bytes: 69316