akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FOR(i,j,n,m) for(int i=j;i<n;i+=m)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define mkp make_pair
#define pb push_back
#define pob pop_back
#ifdef cold66
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.F<<","<<_p.S<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}

template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

const ll MAXn=1e5+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=(ll)1e18;

int main(){
  IOS();
  ll n;
  cin>>n;
  if(n%2==0) cout<<n<<endl;
  else cout<<n*2<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args){
		
		Scanner input = new Scanner(System.in);
		long N = input.nextInt();
        long D = input.nextInt();
        long remain = (long)(2 * Math.pow(10,9)) * 2;
        a:for (long i = N; i < D; i++) {
            for (long j = i + 1; j <= D; j++) {
                if((i*j)%2019 < remain)
                    remain = (i*j)%2019;
                if(remain == 0)
                    break a;
            }
        }
		System.out.println(remain);
	}
}

Measured memory_bytes: 23636
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  // ここにプログラムを追記
  int n;
  cin >> n;
  vector<int> a(n);
  int sumA = 0;
  int sumB = 0;
  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 += 2){
    sumA += a.at(i);
  }
  for(int i = 1; i < n; i += 2){
    sumB += a.at(i);
  }
  cout << sumA-sumB <<endl;
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
   int n;
    std::cin >>n;
    int a , b;
    for(int i=0 ; i<n ; i++){
        std::cin >>a >>b;
        if(a%b!=0)std::cout <<a%b;
        else std::cout <<b;
        std::cout << std::endl;
    }
    return 0;
}

Measured memory_bytes: 1160
import math
K=int(input())
c = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    if math.gcd(i,j) == 1:
      c += K
    else:
      for k in range(1,K+1):
        if i == j == k:
          c += i
        elif i == j:
          c += math.gcd(i,k)
        elif i == k:
          c += math.gcd(i,j)
        elif j == k:
          c += math.gcd(i,k)
        else:
          c += math.gcd(math.gcd(i, j), k)
print(c)

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

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

    string ck = "ACGT";
    int n = s.size(), ans = 0, tmp = 0;
    rep(i, n)
    {
        bool ok = false;
        rep(j, 4)
        {
            if (s[i] == ck[j])
            {
                ok = true;
            }
        }
        if (ok)
        {
            tmp++;
            ans = max(ans, tmp);
        }
        else
        {
            tmp = 0;
        }
    }

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


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

using namespace std;

int main(){
    string first, second;
    long long int count_;
    bool vertical;
    string::iterator f_itr, s_itr;
    getline(cin, first);
    getline(cin, first);
    getline(cin, second);
    f_itr = first.begin(); 
    s_itr = second.begin();
    if(*f_itr == *s_itr){
            count_ = 3;
            vertical = true;
            f_itr++;
            s_itr++;
    }else{
            count_ = 6;
            vertical = false;
            f_itr += 2;
            s_itr += 2;
    }
    while(f_itr < first.end() && s_itr < second.end()){
        if(*f_itr == *s_itr){
            if(vertical){
                count_ *= 2;
            }
            vertical = true;
            f_itr++;
            s_itr++;
        }else{
            if(vertical){
                count_ *= 2;
            }else{
                count_ *= 3;
            }
            vertical = false;
            f_itr += 2;
            s_itr += 2;
        }
    }
    cout << count_ % 1000000007 << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
a = list(map(int, input().split()))
mod=10**9+7
import fractions
lcm_m = a[0]%mod
for i in range(1, N):
#    lcm_m = lcm_m * a[i] // fractions.gcd(lcm_m, a[i])
#    lcm_m = (lcm_m%(10^9+7))*(a[i]%(10^9+7))//(fractions.gcd(lcm_m,a[i])%(10^9+7))
#    lcm_m = (lcm_m%(10**9+7))*a[i]//(fractions.gcd(lcm_m%(10**9+7),a[i]))
#    lcm_m = ((lcm_m%mod)*(a[i]%mod))%mod//(fractions.gcd(lcm_m,a[i]))
    lcm_m = ((lcm_m)*(a[i]%mod))//(fractions.gcd(lcm_m,a[i]%mod))
#print(lcm_m)

#sol = 0
#for i in range(N):
#    sol += lcm_m / a[i]
#print(int(sol)%(10**9+7))
sol=sum([lcm_m//x for x in a])
print(sol%mod)
#print(sol)

Measured memory_bytes: 264428
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(a) (ll)(a.size())
#define pll pair<ll,ll>
#define all(v) v.begin(), v.end()
#define FOR(i, a, b) for(i=a;i<b;i++)

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll i,j,k,n,t;
	cin>>n;
	vector<ll> v(n);
	for(i=0;i<n;i++)
		cin>>v[i];
	sort(all(v), greater<ll>());
	ll ans = v[0];
	ll flag = 0;
	k = 1;
	i=1;
	while(i<n-1)
	{
		if(flag>=2)
		{
			flag = 0;
			k++;
		}
		// cout<<v[k]<<endl;
		ans += v[k];
		flag++;
		i++;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4776
#include<bits/stdc++.h>
using namespace std;
#define int long long int 
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout<<fixed;cout<<setprecision(10);
#define in cin>>
#define out cout<<
#define br cout<<"\n";

void solve(){
    int a;
    cin>>a;
    cout<<a + a*a + a*a*a<<"\n";
}

int32_t main(){
    FASTIO
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
    #endif

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

    #ifndef ONLINE_JUDGE
        cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
    #endif

    return 0;
}

Measured memory_bytes: 3644
// I look at my watch
// it say nine twenty-five
// And I think oh God
// I'm still alive !
 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(x) int((x).size())
#define all(v) (v).begin(),(v).end()
#define trace(x) cerr << #x << " = " << x << endl
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define For(i,a,b) for(int i = int(a); i < int(b); ++i)
#define roF(i,a,b) for(int i = int(a); i >= int(b); i--)
using namespace std;
 
typedef long long ll;
typedef pair<int,int> ii;
typedef long double ld;




int main(){	
	ll n,k;cin>>n>>k;
	ll ini=1;
	ll ans=-1;
	vector<ii>vec(n);
	For(i,0,n){
		ll val,c;cin>>val>>c;
		vec[i]={val,c};
	}
	sort(all(vec));
	For(i,0,n){
		ll val=vec[i].ff,c=vec[i].ss;
		ll l=ini,r=ini+c;
		if(l<=k&&k<r){
			ans=val;
			break;
		}
		ini=r;
	}
	cout<<ans<<endl;
	
	return 0;
}


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

int main(){
    int H, W;
    while(1){
        cin >> H >> W;
        if(H == 0 && W == 0) break;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if(i == 0 || i == H - 1 || j == 0 || j == W - 1)
                cout << "#";
                else cout << ".";
            }
            cout << endl;
        }
        cout << endl;
    }

    return 0;
}



Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//(a+b-1)/b
//priority_queue<ll, vector<ll>, greater<ll>> q;
using pl = pair<ll,ll>;

signed main(){
	ll n,k; cin>>n>>k;
	ll ans=0;
	rep(i,k,n+2){
		ll a=i*(i-1)/2;
		ll b=(2*n-i+1)*i/2;
		//cout<<a<<" "<<b<<endl;
		ans+=b-a+1;
		ans%=MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <numeric>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)




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

	cout << r*r<< endl;
}

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

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

bool isLoop(string s)
{
//    cerr << s << endl;
    rep(i,s.length()/2){
        if(s[i] != s[s.length()-1-i]) return false;
    }
    return true;
}

int main() {
    bool ans = true;

    string s;
    cin >> s;

    int n = s.length();
    ans = isLoop(s) && isLoop(s.substr(0, n/2)) && isLoop(s.substr((n-1+3)/2));
    cout << (ans ? "Yes" : "No") << endl;
    return 0;    
}


Measured memory_bytes: 256
#include <stdio.h>
int main ()
{
	int a,b,c,d,e,f;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	e=a+b;
	f=c+d;
	if(e>f)
	printf("Left\n");
	else if(e<f)
	printf("Right\n");
	else
	printf("Balanced");
	
	return 0;

}
	
	

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

typedef pair <int, int> ii;

struct node {
	int lo, hi, mid, val;
	node *l, *r;
	node (int _lo, int _hi): lo(_lo), hi(_hi), mid((_lo + _hi) / 2), val(0) {
		if (lo != hi) l = new node(lo, mid), r = new node(mid + 1, hi);
	}
	void update(int p, int v) {
		if (lo == hi) {
			val = v;
			return;
		}
		if (p <= mid) l -> update(p, v);
		else r -> update(p, v);
		val = l -> val + r -> val;
	}
	int query(int s, int e) {
		if (lo >= s && hi <= e) return val;
		if (s > mid) return r -> query(s, e);
		else if (e <= mid) return l -> query(s, e);
		else return l -> query(s, e) + r -> query(s, e);
	}
} *root;

int n, q;
int c[500005];
vector <ii> lr[500005];
int prv[500005], temp[500005];
vector <int> lst[500005];
int ans[500005];

int main() {
	scanf("%d%d", &n, &q);
	root = new node(1, n);
	for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
	for (int i = 0; i < q; i++) {
		int l, r; scanf("%d%d", &l, &r);
		lr[l].emplace_back(r, i);
	}
	for (int i = 1; i <= n; i++) {
		prv[i] = temp[c[i]];
		temp[c[i]] = i;
	}
	for (int i = 1; i <= n; i++) {
		lst[prv[i]].push_back(i);
	}
	for (int i : lst[0]) root -> update(i, 1);
	for (int i = 1; i <= n; i++) {
		for (ii ri : lr[i]) {
			int r, index; tie(r, index) = ri;
			ans[index] = root -> query(i, r);
		}
		for (int j : lst[i]) root -> update(j, 1);
	}
	for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
	return 0;
}


Measured memory_bytes: 105268
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<iomanip>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (unsigned int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifdef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {}
#define TF(f) {}
#define END {}
#endif
const int MOD =  1000000007 ;
const int INF = 2000000000;


    ll A,B,C,D,N,X[3];
    ll ans=0;
    string S;
    bool F;
int main(){
    cin>>S;
    cout<<((S.end()!=std::find(ALL(S),'7'))?"Yes":"No")<<endl;

    return 0;
}


Measured memory_bytes: 3632
fun main(args: Array<String>) {
    var (A, B, C, D) = listOfLong(-1, 0, 0, 0)
    val e = lcm(C, D)
    val ac = A / C
    val ad = A / D
    val ae = A / e
    val a = ac + ad - ae
    val bc = B / C
    val bd = B / D
    val be = B / e
    val b = bc + bd - be
    val ans = (B - A) - (b - a)
    println(ans)
}

fun gcd(a: Long, b: Long): Long = if (b > 0) gcd(b, a % b) else a
fun lcm(a: Long, b: Long): Long = a * b / gcd(a, b)
fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)
fun listOfLong() = listOfString().map(String::toLong)
fun listOfDouble() = listOfString().map(String::toDouble)
fun listOfInt(delta: Int = 0) = listOfString().map { Integer.parseInt(it) + delta }
fun listOfInt(vararg offset: Int) = listOfString().map { Integer.parseInt(it) }.mapIndexed { index, int -> int + offset[index % offset.size] }
fun listOfLong(delta: Long = 0L) = listOfString().map { java.lang.Long.parseLong(it) + delta }
fun listOfLong(vararg offset: Long) = listOfString().map { java.lang.Long.parseLong(it) }.mapIndexed { index, long -> long + offset[index % offset.size] }
fun listOfDouble(delta: Double = 0.0) = listOfString().map { java.lang.Double.parseDouble(it) + delta }
fun pairIntLong() = listOfLong().let { Pair(it[0].toInt(), it[1]) }
fun tripleIntIntLong() = listOfLong().let { Triple(it[0].toInt(), it[1].toInt(), it[2]) }
fun tripleIntLongLong() = listOfLong().let { Triple(it[0].toInt(), it[1], it[2]) }
fun pairIntLong(offset: Pair<Int, Long> = Pair(0, 0L)) = listOfLong().let { Pair(it[0].toInt() + offset.first, it[1] + offset.second) }
fun tripleIntIntLong(offset: Triple<Int, Int, Long> = Triple(0, 0, 0L)) = listOfLong().let { Triple(it[0].toInt() + offset.first, it[1].toInt() + offset.second, it[2] + offset.third) }
fun tripleIntLongLong(offset: Triple<Int, Long, Long> = Triple(0, 0L, 0L)) = listOfLong().let { Triple(it[0].toInt() + offset.first, it[1] + offset.second, it[2] + offset.third) }



Measured memory_bytes: 37792
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
template<typename T1, typename T2> inline bool chmin(T1& a, T2 b) { if (a > b) { a = b; return 1; }return 0; }
template<typename T1, typename T2> inline bool chmax(T1& a, T2 b) { if (a < b) { a = b; return 1; }return 0; }


int main() {
	int n;
	cin >> n;
	vector<ll> a(n+1);
	vector<ll> b(n);
	REP(i, n + 1) {
		cin >> a[i];
	}
	REP(i,n){
		cin >> b[i];
	}
	ll res = 0;
	ll car = 0;
	REP(i, n) {
		//res += min<ll>(a[i], b[i] + car);
		if (a[i] > (b[i] + car)) {
			res += b[i] + car;
			car = 0;
		}
		else {
			res += a[i];
			//car = b[i] - a[i];
			car = min(b[i] + car - a[i], b[i]);
		}
	}
	res += min(car, a[n]);
	put(res);
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
const int MOD = 1e9+7;
int n, m;
long long dp[305][305][305];
int main(){
	scanf("%d%d", &n, &m);
	dp[0][1][0] = 1;
	rep(i,m) rep(j,n+1) rep(k,n-j+1){
		(dp[i+1][j+k][0] += dp[i][j][k] * j) %= MOD;
		(dp[i+1][j][k] += dp[i][j][k] * k) %= MOD;
		(dp[i+1][j][k+1] += dp[i][j][k] * (n-j-k)) %= MOD;
	}
	printf("%lld\n", dp[m][n][0]);
}

Measured memory_bytes: 218624
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){
  int M=0;
  int a[100];
  int n;
  int i,j;
  //scanf("%d",&n);
  n=2;
  for(i=0;i<n;i++){
    scanf("%d",a+i);
  }
  if(a[0]%a[1]==0){
    printf("0");
  }else{
  printf("1");
}
}

Measured memory_bytes: 128
N = int(input())
A = list(map(int,input().split()))
B = [[A[i],i] for i in range(N)]
d = {}
B.sort()
for i in range(N):
    d[B[i][1]] = i
for i in range(N):
    if d[i] <N//2:
        print(B[N//2][0])
    else:
        print(B[-1+(N//2)][0])

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

int main(){
  int DP[100001],N = 100000,count = 1;
  for(int i = 0;i < 100001;i++)DP[i] = 0;
  queue<int> que,newque;
  int v[] = {1,pow(6,1),pow(6,2),pow(6,3),pow(6,4),pow(6,5),pow(6,6),pow(9,1),pow(9,2),pow(9,3),pow(9,4),pow(9,5)};
  for(int i = 0;i < 12;i++){
    que.push(v[i]);
    DP[v[i]] = 1;
  }
  while(1){
    bool flag = 1;
    for(int i = 1;i <= 100000;i++)if(!DP[i])flag = 0;
    if(flag)break;
    count++;
    while(que.size()){
      int q = que.front();
      for(int i = 0;i < 12;i++){
        if(0 < q+v[i] && q+v[i] < 100001){
          if(!DP[q+v[i]]){
            newque.push(q+v[i]);
            DP[q+v[i]] = count;
          }
        }
      }
      que.pop();
    }
    que = newque;
  }
  cin >> N;
  cout << DP[N] << endl;
}


Measured memory_bytes: 1424
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
 
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
 

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

ll dp[3002][3002] = {};

int main(){
    std::ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[n] = {};
    for(int i=0;i<n;++i)
    {
      cin >> a[i];
    }

    for(int i=0;i<n;++i)
    {
      dp[i][i+1] = 0; // [i, j) = 0;
    }

    for(int l=0;l<n;++l)
    {
      for(int i=0;i<n;++i)
      {
        if(i+l+1 > n)
        {
          break;
        }

        int turn = (n - (l + 1)) % 2;
        if(turn == 0)
        {
          // maximize X - Y
          dp[i][i+l+1] = max(dp[i+1][i+l+1] + a[i], dp[i][i+l] + a[i+l]);
        }
        else
        {
          // minimize X - Y
          dp[i][i+l+1] = min(dp[i+1][i+l+1] - a[i], dp[i][i+l] - a[i+l]);
        }
      }
    }

    cout << dp[0][n] << endl;
}

Measured memory_bytes: 70016
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 2000000
int H;
int A[MAX+1];
// void swap(int* a,int* b){
//     int* t;
//     t = a;
//     a = b;
//     b = t;
// }
void maxHeap(int x,int A[MAX+1]){
    int l,r,largest;
    l = 2*x;
    r = 2*x+1;
    if(l<=H && A[x]<A[l]){
        largest = l;
    }else{
        largest = x;
    }
    if(r<=H && A[largest]<A[r]){
        largest = r;
    }
    if(largest!=x){
        swap(A[largest],A[x]);
        maxHeap(largest,A);
    }
}
int main(){
    int A[MAX+1];
    scanf("%d",&H);
    for(int i=1;i<=H;i++){
        scanf("%d",&A[i]);
    }
    for(int i=H/2;i>=1;i--){
        maxHeap(i,A);
    }
    for(int i=1;i<=H;i++){
        printf(" %d",A[i]);
    }
    printf("\n");
}



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

using namespace std;

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

    for (int i = 1; i < 100000; ++i) {
        int da = i * 0.08;
        int db = i * 0.1;
        if(da == n and db == m) return cout << i << "\n", 0 ;
    }
    cout << "-1\n";
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

# In[5]:


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


# In[6]:


ans = 0
for i in range(0,N,2):
    if a[i]%2 == 1:
        ans += 1
print(ans)


# In[ ]:






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

using namespace std;

int main(){
	int N,W;
	cin >> N >> W;
	vector<long long> w(N),v(N);
	vector<long long> dp(100001, 1e18);
	
	for(int i = 0; i < N; i++){
		cin >> w[i] >> v[i];
	}
	dp[0] = 0;
	for(int i = 0; i < N; i++){
		for(int j = 100000; j >= 0; j--){
		 	if(j>=v[i])dp[j] = min(dp[j], dp[j-v[i]] + w[i]);
		}
	}
	
	for(int j = 100000; j>= 0;j--){
		if(dp[j]<=W){
			cout << j << "\n";
			return 0;
		}
	}
	
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<int,int>;

int main()
{
  ll N,A,B;
  cin >> N >> A >> B;
  vector<ll> X(N);
  REP(i, N) cin >> X[i];
  
  ll ans=0;
  REP(i,N-1){
    if((X[i+1]-X[i])*A>=B){
      ans+=B;
    }else{
      ans+=(X[i+1]-X[i])*A;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }

void _main() {
  int A, B, C;
  cin >> A >> B >> C;

  rep(i, 1, 101) {
    if (C == (A*i)%B) {
      cout << "YES" << "\n";
      return;
    }
  }
  cout << "NO" << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<numeric>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define int64 long long
#define modbig (10*10*10*10*10*10*10*10*10+7)
using namespace std;

int main(){
  int n,k;
  cin>>n>>k;
  cout<<n-k+1;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>


 
int main() {
 int j,k,i,a[3],b[3],m;
  for(i=0;i<3;i++)
  scanf("%d %d",&a[i],&b[i]);
  k=0;
  m=0;
  for(i=1;i<5;i++){
    k=0;
    for(j=0;j<3;j++){
      if(a[j]==i)
        k=k+1;
      if(b[j]==i)
        k=k+1;
      if(k==3)
        m=1;
    }
  }
  
  if(m!=1)
    printf("YES");
  else printf("NO");

}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<utility>
#define rep(i, n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	int k, x;
	cin>>k>>x;
	if(500*k>=x)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <cstdlib>
#include<iomanip>
#define rep(i,x) for(int i=0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using namespace std;
using ld = long double;
using ll = long long;
const ll INF = 1001001001;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
ll gcd(ll a, ll b) {//a>b
    if (a < b)swap(a, b);
    if (a % b == 0) return b;
    else return gcd(b, a % b);
}


int main() {
    ll N;
    cin >> N;
    map<ll, ll> num;
    ll n;
    rep(i, N) {
        cin >> n;
        num[n]++;
    }
    ll ans = 0;
    for (auto x : num) {
        if (x.first > x.second)ans += x.second;
        else ans += x.second - x.first;
    }
    cout << ans << endl;
}


Measured memory_bytes: 6272
def main():
    NM = list(map(int, input().split()))
    N, M = NM[0], NM[1]
    LR = []
    L, R = [], []
    ans = 0
    maxL = 1
    minR = N

    for i in range(M):
        LR.append(list(map(int, input().split())))

    for j in range(M):
        L.append(LR[j][0])
        R.append(LR[j][1])

    for k in range(M):
        maxL = max(maxL, L[k])
        minR = min(minR, R[k])

    ans = minR - maxL + 1
    ans = max(ans, 0)
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 29060
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
# ifdef __GNUC__
# if __cplusplus > 199711L
# include <unordered_set>
# include <unordered_map>
# else
# include <tr1/unordered_map>
# include <tr1/unordered_set>
using namespace tr1;
# endif
# else
# include <unordered_map>
# include <unordered_set>
# endif
using namespace std;

#define fi first
#define se second
#define FO(x, n) for (int x = 0; x < n; ++x)
#define FOR(x, a, b) for (int x = a; x < b; ++x)
#define RFO(x, n) for (int x = n - 1; x >= 0; --x)
#define RFOR(x, a, b) for (int x = b - 1; x >= a; --x)
typedef unsigned char byte;
typedef unsigned int uint;
typedef long long llong;
typedef unsigned long long ullong;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llong, llong> pll;
inline bool feq(const double& a, const double& b) { return fabs(a - b) < 1e-10; }

const int MAXN = 2e5 + 10;
int N;
llong nums[MAXN], sums[MAXN];

int main()
{
    while (cin >> N)
    {
        sums[0] = 0;
        FO (i, N)
        {
            cin >> nums[i];
            sums[i + 1] = sums[i] + nums[i];
        }
        llong res = LLONG_MAX;
        for (int i = 1; i <= N - 1; ++i)
        {
            res = min(res, abs(sums[i] - (sums[N] - sums[i])));
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 3328
while True:
    n,x = map(int,input().split())
    if (n==0) and (x==0):
        break
    result = 0
    for j in range(1,n+1):
        for k in range(1,n+1):
            if k <= j:
                continue
            c = x - (j+k)
            if (c > k) and (c <= n):
                result += 1
    print(result)


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

int a[105];
long long dp[105][100005];

#define MOD 1000000007

int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }

    for(int i = 0; i <= k; ++i){
        if(i)dp[0][i] = dp[0][i-1];
        if(i <= a[0])dp[0][i]++;
    }

    for(int i = 1; i < n; ++i){
        dp[i][0] = 1;
        for(int j = 1; j <= k; ++j){
            dp[i][j] = dp[i][j - 1];
            dp[i][j] += dp[i - 1][j] - (j - a[i] - 1 >= 0 ? dp[i - 1][j - a[i] - 1] : 0);
            dp[i][j] %= MOD;
        }
    }

    cout << (dp[n - 1][k] - (k > 0 ? dp[n - 1][k - 1] : 0) + MOD) % MOD << "\n";
    return 0;
}
/*
3 4
3 2 4
*/


Measured memory_bytes: 80128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define FASTIO() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int N = 200005, M = 1000000007, BIG = 0x3f3f3f3f;

int ct = 0;
int n;
int m;

bool Read() {
  cin >> n;
  if (cin.eof())
    return 0;
  cin >> m;

  return 1;
}

bool Valid(int x) {
  return (int)(double(x) * 0.08) == n && (int)(double(x) * 0.1) == m;
}

void Process() {
  for (int i = 1; i < 10555; i++) 
    if (Valid(i)) {
      cout << i << "\n";
      return;
    }
  cout << "-1\n";
}

int main() {
  FASTIO();

  while (Read())
    Process();

  return 0;
}

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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;
// 約数列挙
template <class T>
vector<T> dividers(T n) {
    vector<T> ret;
    for (T x = 1; x * x <= n; x++) {
        if (n % x == 0) {
            ret.push_back(x);
            if (x * x != n) ret.push_back(n / x);
        }
    }
    sort(ret.begin(), ret.end());
    return ret;
}
int main() {
    lint N;
    cin >> N;
    lint ans = dividers(N - 1).size() - 1;
    for (auto div : dividers(N)) {
        if (div == 1) continue;
        lint n = N;
        while (n % div == 0) {
            n /= div;
        }
        if (n % div == 1) { ans++; }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 550000;
const ll MOD = 1e9+7;
using namespace std;

int main()
{
    int n;
    cin >> n;
    set<int> st1,st2;
    st1.insert(0);
    st2.insert(0);
    multiset<int> ms1,ms2;
    for(int i = 1;i<=n;++i)
    {
        int a;
        cin >> a;
        if (i%2==0)
            st1.insert(a),ms1.insert(a);
        else
            st2.insert(a),ms2.insert(a);
    }
    vector<pair<int,int>> ans1;
    vector<pair<int,int>> ans2;
    for(auto x:st1)
        ans1.push_back({n/2-(int)ms1.count(x),x});
    for(auto x:st2)
        ans2.push_back({n/2-(int)ms2.count(x),x});
    sort(ans1.begin(),ans1.end());
    sort(ans2.begin(),ans2.end());
    if (ans1[0].second!=ans2[0].second)
        cout << ans1[0].first+ans2[0].first;
    else
        cout << min(ans1[0].first+ans2[1].first,ans1[1].first+ans2[0].first);
    return 0;
}


Measured memory_bytes: 10748
#include<cstdio>

using namespace std;
int C[3000][3000];
int b[3000];
void getC(int n){
	C[0][0]=1;
	for (int i=1;i<n;i++){
		C[i][0]=1;
		for (int j=1;j<=i;j++)
		C[i][j]=(C[i-1][j]+C[i-1][j-1])%n;
	}
}
int main(){
	int p;
	scanf("%d",&p);
	getC(p);
	for (int i=0;i<p;i++){
		int x;
		scanf("%d",&x);
		if (x){
			int k=1;
			for (int j=0;j<p;j++){
				b[p-1-j]-=1ll*C[p-1][j]*k%p;
				if (b[p-1-j]<0) b[p-1-j]+=p;
				k=1ll*k*(p-i)%p;
			}
			b[0]++;
			if (b[0]>=p) b[0]-=p;
		}
	}
	for (int i=0;i<p;i++)
	printf("%d ",b[i]);
	return 0;
}

/*
f(x)=\sum_{i=0}^{p-1} b_i*x^i
f(i)=a_i (mod p)

根据拉格朗日插值的思想，可以把函数f(x)
分成若干个函数f_i(x) 
并且每一个函数f_i(x)满足 
f_i(i)=a_i 
f_i(j)=0 (i!=j)
因为费马小定理 
a^p=a (mod p)
对于 1<=a<=p-1  a^{p-1}=1 (mod p)
-> 1-a^{p-1}
对于 a=0        a^{p-1}=0 (mod p) 

那么我们构造一个函数
f_i(x)=1-(x-k)^{p-1}
然后我们来考虑为什么可以这样构造
以及 k 的含义
如果 a_i 是 1
那么我们令 k=i
此时 
当 x=i 时 1-(i-i)^{p-1}=1=a_i (mod p)
当 x!=i 时 1-(x-i)^{p-1}=0 (mod p)   
(费马小定理)

如果 a_i 是 0
我们令 f_i(x)=0 就行了
此时满足上面的条件

那么最后的多项式
f(x)=\sum_{i=0}^{p-1} f_i(i)   

但问题是怎么快速的拆出
1-(x-k)^{p-1}
二项式定理 (x-k)^{p-1}=\sum_{i=0}^{p-1} -C(p-1,i)x^{p-1-i}(-k)^{i}
                     

于是预处理出 组合数就可以在O(p^2)时间内解决
 
 

*/

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

int M;
int a[7];
int s, g;
int N[301];

bool isChecked[301];
vector<int> milestone[301];  //そのマスで出せばゴールにたどり着ける目を格納する

int iabs(int x){ return x >= 0 ? x : -x; }

bool search(int now){
	if (isChecked[now]) return false;
	else if (now == g)  return true;

	isChecked[now] = true;
	for (int dice = 1; dice <= 6; dice++){
		if (now + a[dice] <= M && search(now + a[dice] + N[now + a[dice]])){
			milestone[now].push_back(a[dice]);
		}
		if (now - a[dice] >= 1 && search(now - a[dice] + N[now - a[dice]])){
			milestone[now].push_back(-a[dice]);
		}
	}

	return milestone[now].size() > 0 ? true : false;
}

int main(){
	cin >> M;
	for (int i = 1; i <= 6; i++){
		cin >> a[i];
	}
	cin >> s >> g;
	for (int i = 1; i <= M; i++){
		cin >> N[i];
	}
	bool canGoal = search(s);

	int now = s; //自分が今いるマスの番号
	for (;;){
		int dice;
		cin >> dice;

		bool found = false;
		for (vector<int>::iterator it = milestone[now].begin(); it != milestone[now].end(); it++){
			if (iabs(*it) == a[dice]){
				if (*it > 0){
					now = now + a[dice] + N[now + a[dice]];
					cout << 1 << endl;
				}
				else{
					now = now - a[dice] + N[now - a[dice]];
					cout << -1 << endl;
				}
				found = true;
				break;
			}
		}
		if(!found) cout << 0 << endl;
		cout.flush();

		if (now == g) return 0;
	}
	
	return 0;
}

Measured memory_bytes: 1304
// 文字列変換等
fun main(args: Array<String>) {
    var inputs = readInputLine().split(" ").map { Integer.parseInt(it) }
    val n = inputs[0]
    val x = inputs[1]

    inputs = readInputLine().split(" ").map { Integer.parseInt(it) }
    
    var pos = 0
    var ans = 1
    
    for (i in 0 until n) {
        pos += inputs[i]
        if (pos <= x) {
            ans++
        } else {
            break
        }
    }
    
    println("$ans")
}
 
fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 38024
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N;
long double A[1001];
int main(){
    cin >> N;
    long double sum = 0;
    for(int i=0;i<N;i++){
        cin >> A[i];
        sum += 1/A[i];
    }
    
    printf("%0.6Lf",1/sum);
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <cmath>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#define rep(i,n) for (int i = 0; i < (n); ++i)

using namespace std;
const int MOD = 1000000007;

typedef long long int ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;

int solve(vector<int> &dp,int n) {
    if(n==0)return 1;
    if(dp[n]!=0)return dp[n];
    dp[n] =  solve(dp,n-3) +solve(dp,n-2) + solve(dp,n-1);
    return dp[n]; 
}

int main() {
    vector<int> dp(31,0);
    int n;
    cin >> n;
    dp[1]=1;dp[2]=2;dp[3]=4;

    while(n){
        cout << ((solve(dp,n)/10)/365)+1  << endl;
        cin >> n;
    }
    return 0;
}



Measured memory_bytes: 3048
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+6;
const int mod=1e9+7;
int mul(int x,int y){
	return (1ll*x*y)%mod;
}
void add(int &x,int y){
	x+=y;
	if(x>=mod){
		x-=mod;
	}
}
void sub(int &x,int y){
	x-=y;
	if(x<0){
		x+=mod;
	}
}
int sub1(int x,int y){
	x-=y;
	if(x<0){
		x+=mod;
	}
	return x;
}
int binpow(int x,int y){
	int tich=1;
	while(y){
		if(y&1){
			tich=mul(tich,x);
		}
		x=mul(x,x);
		y>>=1;
	}
	return tich;
}
int ar[N],cnt[N],pref[N],bit[N],bit1[N],lst[N],nxt[N],bit2[N];
void upd2(int idx,int val){
	while(idx<N){
		add(bit2[idx],val);
		idx+=(idx&-idx);
	}	
}
int getsum2(int idx){
	int sum=0;
	while(idx){
		add(sum,bit2[idx]);
		idx-=(idx&-idx);
	}
	return sum;
}
int get2(int l,int r){
	return sub1(getsum2(r),getsum2(l-1));
}
void upd1(int idx,int val){
	while(idx<N){
		add(bit1[idx],val);
		idx+=(idx&-idx);
	}	
}
int getsum1(int idx){
	int sum=0;
	while(idx){
		add(sum,bit1[idx]);
		idx-=(idx&-idx);
	}
	return sum;
}
int get1(int l,int r){
	return sub1(getsum1(r),getsum1(l-1));
}
void upd(int idx,int val){
	while(idx<N){
		add(bit[idx],val);
		idx+=(idx&-idx);
	}	
}
int getsum(int idx){
	int sum=0;
	while(idx){
		add(sum,bit[idx]);
		idx-=(idx&-idx);
	}
	return sum;
}
int get(int l,int r){
	return sub1(getsum(r),getsum(l-1));
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,tich=1,ans=0;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>ar[i];
		cnt[ar[i]]++;
	}
	for(i=n;i>0;i--){
		cnt[i]+=cnt[i+1];
	}
	for(i=1;i<=n;i++){
		cnt[i]-=n-i;
		tich=mul(tich,cnt[i]);
		if(cnt[i]<=0){
			cout<<0;
			return 0;
		}
		j=mul(cnt[i]-1,binpow(cnt[i],mod-2));
		if(pref[i-1]){
			pref[i]=mul(pref[i-1],j);
		}
		else{
			pref[i]=j;
		}
		lst[i]=lst[i-1];
		if(!pref[i]){
			lst[i]=i;
		}
	}
	nxt[n]=n+1;
	for(i=n-1;i>0;i--){
		nxt[i]=nxt[i+1];
		if(!pref[i+1]){
			nxt[i]=i+1;
		}
	}
	for(i=1;i<=n;i++){
		add(ans,mul(mul(get(lst[ar[i]],ar[i]),pref[ar[i]]),500000004));	//a(j)<=a(i), (a(j),a(i)]
		add(ans,get1(ar[i]+1,n));			//a(j)>a(i) (a(i),a(j)]
//		assert(ar[i]+1<=nxt[ar[i]]);
		if(pref[ar[i]]){
			sub(ans,mul(mul(binpow(pref[ar[i]],mod-2),get2(ar[i]+1,nxt[ar[i]]-1)),500000004));
		}
		else{
			sub(ans,mul(get2(ar[i]+1,nxt[ar[i]]-1),500000004));
		}
		upd1(ar[i],1);
		if(pref[ar[i]]){
			upd(ar[i],binpow(pref[ar[i]],mod-2));
		}
		else{
			upd(ar[i],1);
		}
		upd2(ar[i],pref[ar[i]]);
	}
	cout<<mul(ans,tich)<<endl;
}

Measured memory_bytes: 6528
#include <iostream>

using namespace std;

int main() {

   const int size = 26;
   int count[size]{};
   char chara;

   while(cin >> chara) {
   
      if ('a' <= chara && chara <= 'z') {
         int id = chara - 'a';
         ++count[id];
      } else if ('A' <= chara && chara <= 'Z') {
         int id = chara - 'A';
         ++count[id];
      }

   }

   for (int i = 0; i < size; ++i) {

      char word = 'a' + i;
      cout << word << " : " << count[i] << endl;

   }

   return 0;

}

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

#define int long long
#define double long double
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) (x).erase(unique(all(x)), (x).end())
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << (x) << endl
using vint=vector<int>;
using vvint=vector<vint>;
using pint=pair<int, int>;
using vpint=vector<pint>;
template<typename T> using priority_queue_rev=priority_queue<T, vector<T>, greater<T>>;
constexpr double pi = 3.1415926535897932384626433832795028L;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) {
    while (b) { swap(a %= b, b); }
    return a;
}
int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> void fin(T mes) {
    cout << mes << endl;
    exit(0);
}
template<typename T1, typename T2> bool chmax(T1 &a, const T2 &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> bool chmin(T1 &a, const T2 &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct setup {
    static constexpr int PREC = 20;
    setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int N;
int A[330][330];
signed main() {
    cin >> N;
    rep(i, N)rep(j, N) { cin >> A[i][j]; }
    int ans = 0;
    rep(i, N) {
        rep(j, i) {
            rep(k, N) {
                if (i == k || j == k) { continue; }
                if (A[i][k] + A[j][k] < A[i][j]) { fin(-1); }
                if (A[i][k] + A[j][k] == A[i][j]) { goto nene; }
            }
            ans += A[i][j];
            nene:;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll tmp, res = 0;
int N,M,Q;
vector<int> A;
vector<vector<int>> F;
void solve(vector<int> &A, int cur, int x){
    A[cur] = x;
    if (cur==N-1){
        tmp = 0;
        for (int i=0; i<Q; ++i){
            if (A[F[i][1]] - A[F[i][0]]==F[i][2]) tmp += F[i][3];
        }
        res = max(res, tmp);
    }else {
        for (int next_v=x; next_v<=M; ++next_v) solve(A,cur+1,next_v);
    }
}
int main() {
    cin >> N >> M >> Q;
    A.resize(N);
    F.resize(Q, vector<int>(4));
    for (int i=0; i<Q; ++i){
        for (int j=0; j<4; ++j){
            cin >> F[i][j];
            if (j==0 || j==1) F[i][j]--;
        }
    }
    for (int x=1; x<=M; ++x) solve(A,0,x);
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3612
use std::vec::Vec;

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()
}

fn read_touple<T: std::str::FromStr + Copy>() -> (T, T) {
  let v: Vec<T> = read_vec();
  assert_eq!(v.len(), 2);
  (v[0], v[1])
}

fn main() {
  let n: usize = read();
  let mut s: Vec<(char)> = read::<String>().chars().collect();

  if n % 2 != 0 {
     println!("No");
     return
  }

  let mut ans = "Yes";
  for i in 0..n/2 {
    if s[i] != s[i + n/2] {
       ans = "No";
    }
  }

  println!("{}", ans);
}



Measured memory_bytes: 4352
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<vector>
#define ll  long long 
using namespace std;
ll a[100005], f[100005] = {1}, mod = 1000000007, n, k;
ll quick_pow(ll a, ll b, ll mod)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)	ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
ll vim(ll a, ll b)
{
	return quick_pow(a, b - 2, b);
}
inline ll C(ll a, ll b)
{
	return f[b] * vim(f[a], mod) % mod * vim(f[b - a], mod) % mod;
}
ll solve()
{
	ll mx = 0, mn = 0;
	sort(a, a + n);
	for (int i = n - 1; i >= k - 1; i--)
		mx = (mx + C(k - 1, i) * a[i]) % mod;
	for (int i = n - 1, j = 0; i >= k - 1; i--, j++)
		mn = (mn + C(k - 1, i) * a[j]) % mod;
	return ((mx - mn) % mod + mod) % mod;
}
signed main()
{
	for (int i = 1; i <= 100000; i++)	f[i] = f[i - 1] * i % mod;
	//cout << vim(1, mod) << endl;
	while (~scanf("%lld%lld", &n, &k))
	{
		for (int i = 0; i < n; i++)	scanf("%lld", &a[i]);
		printf("%lld\n", solve());
	}
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

#define M 1'000'000'007
ll factorial[200'002];

ll modfact(ll num) {
    if (num == 0) {
        return 1;
    }
    if (num <= 2) {
        return num;
    }
    if (factorial[num] != 0) {
        return factorial[num];
    }
    return factorial[num] = (modfact(num - 1) * num) % M;
}
ll mod_power(ll x, ll n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        return mod_power((x * x) % M, n / 2);
    } else {
        return (mod_power((x * x) % M, n / 2) * x) % M;
    }
}
ll modinv(ll a) {
    ll b = M, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= M;
    if (u < 0) u += M;
    return u;
}

ll comb(ll n, ll k) { return (((modfact(n) * modinv(modfact(k))) % M) * modinv(modfact(n - k))) % M; }

ll com[2000009];
ll comb_l(ll n, ll k) {
    if (com[k] != 0) return com[k];
    com[0] = 1;
    reps(i, k) { com[i] = ((((n - i + 1) * modinv(i)) % M) * com[i - 1]) % M; }
    return com[k];
}

int n, a, b;
int main() {
    cin >> n >> a >> b;
    ll ans = mod_power(2, n) - 1;
    ans = (ans - comb_l(n, b) >= 0) ? (ans - comb_l(n, b)) % M : (ans - comb_l(n, b) + M) % M;
    ans = (ans - comb_l(n, a) >= 0) ? (ans - comb_l(n, a)) % M : (ans - comb_l(n, a) + M) % M;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long > vll;
typedef vector< vi > vvi;
int main() {
	int a,b,c,d,n,count=0;
	while(cin>>n){
		if(n>36){
			cout<<0<<endl;
		}
		else{
			for(a=0;a<10;a++){
				for(b=0;b<10;b++){
					for(c=0;c<10;c++){
						for(d=0;d<10;d++){
							if(a+b+c+d==n){
								count++;
							}
						}
					}
				}
			}
			cout<<count<<endl;
		}
		count=0;
	}
}

Measured memory_bytes: 1160