akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long  ll;

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

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}





int main() {
    string s;
    cin>>s;
    if(s.size()%2!=0){
        cout<<"No"<<endl;
        return 0;
    }
    for(int i=0;i<s.size();i++){
        if(i%2==0 && s.at(i)!='h'){
            cout<<"No"<<endl;
            return 0;
        }
        if(i%2==1 && s.at(i)!='i'){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
const int INF = 1e9;

int main(void) {
    int min = INF;
    int N;
    cin>>N;
    int result = 0;
    for (int i = 0; i < N; i++) {
        int p;
        cin>>p;
        if (min >= p) {
            min = p;
            result++;
        }
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define cout16 cout << setprecision(16) 
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define SORT(A) sort(A.begin(),A.end())
#define REV(A) reverse(A.begin(),A.end())
typedef long long int ll;
using vi = std::vector<int>;
using vvi = std::vector<std::vector<int>>;
using vll = std::vector<ll>;
using vvll = std::vector<std::vector<ll>>;
using P = std::pair<int,int>;
using vp = std::vector<P>;
using namespace std;
#define INF 1001001001
#define LL_INF 1001001001001001001
#define fi first
#define se second

int main(void) {
	int n; cin >> n;
	vi a(n),b(n),c(n);
	rep(i,n) cin >> a[i];
	rep(i,n) cin >> b[i];
	rep(i,n) cin >> c[i];
	SORT(a); REV(a);
	SORT(b); REV(b);
	SORT(c); REV(c);
	
	vi nb(n);
	rep(i,n){
		int x = b[i];
		int l = -1, r = n;
		while(l+1<r){
			int m = (l+r)/2;
			if(c[m]>x) l=m; else r=m;
		}
		nb[i] = l+1;
	}
	
	vll s(n);
	s[0] = nb[0];
	rep(i,n-1) s[i+1] = s[i]+nb[i+1];
	
	ll ans = 0;
	rep(i,n){
		ll x = a[i];
		int l = -1, r = n;
		while(l+1<r){
			int m = (l+r)/2;
			if(b[m]>x) l=m; else r=m;
		}
		if(l!=-1)ans += s[l];
	}
	cout << ans << endl;
}


Measured memory_bytes: 2560
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <cassert>
#include <unordered_map>

#define _(x) { cout << #x << " = " << x << " "; }

const double E = 1e-8;
const double PI = acos(-1);

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    long long a, b, c, k, ans = 0;
    cin >> a >> b >> c >> k;
    ans += min(a, k); k -= a;
    k -= b;
    if (k > 0)
        ans -= k;
    cout << ans << '\n';
    return 0;
}



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

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, 1, 0, -1};

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, A, B; cin >> N >> A >> B;
  int sum = A + B;
  string S; cin >> S;
  for (char s : S) {
    if (s == 'a') {
      if (sum) {
        cout << "Yes" << endl;
        sum--;
      } else {
        cout << "No" << endl;
      }
    } else if (s == 'b') {
      if (B and sum) {
        cout << "Yes" << endl;
        B--;
        sum--;
      } else {
        cout << "No" << endl;
      }
    } else {
      cout << "No" << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 848
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int>a(n-1);
    vector<int>b(n-1);
    for (int i = 0; i < n-1; i++) {
        cin >> a.at(i);
        a.at(i) = a.at(i) - 1;
        b.at(i) = 0;
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < n-1; i++) {
        b.at(a.at(i))++;
    }
    for (int i = 0; i < n - 1; i++) {
        cout << b.at(i) << endl;
    }
    cout << 0<<endl;
}

Measured memory_bytes: 4756
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  
  int ans = 0;
  for(int i = 0; i < N; i++){
    int l,r;
    cin >> l >> r;
    ans += r - l + 1;
  }
  
  cout << ans << endl;
  
  
  
  return 0;
}

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

void MaxGCD(int a[],int n){

    int left[n+2];
    int right[n+2];

    left[1]=a[1];
    for(int i=2;i<=n;i+=1){
        left[i]=__gcd(left[i-1],a[i]);
    }

    right[n]=a[n];

    for(int i=n-1;i>=1;i-=1){
        right[i]=__gcd(right[i+1],a[i]);
    }

    int ans=max(right[2],left[n-1]);
    for(int i=2;i<n;i+=1){
        ans=max(ans,__gcd(left[i-1],right[i+1]));
    }
   
   cout<<ans<<endl;
}

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

    int a[n+1];
    for(int i=1;i<=n;i+=1){
        cin>>a[i];
    }

    MaxGCD(a,n);
    return 0;
}

Measured memory_bytes: 1408
A,B,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
p = min(A) + min(B)
for _ in range(M):
    x,y,c = map(int, input().split())
    p = min(p, A[x-1]+B[y-1]-c)
print(p)

Measured memory_bytes: 24860
a, b = map(int, input().split())
s = input()
if s[a] != '-':
	print("No")
	exit()
for i in range(a):
	if s[i] < '0' or s[i] > '9':
		print("No")
		exit()
for i in range(a + 1, a + b + 1):
	if s[i] < '0' or s[i] > '9':
		print("No")
		exit()
print("Yes")

Measured memory_bytes: 38384
#include<iostream>
#include<vector>
#include <limits>

using namespace std;

long long merge(vector<int> &A, int left, int mid, int right){
  int i, j, k;
  long long cnt = 0;
  int n1 = mid - left;
  int n2 = right - mid;
  vector<int> L(n1+1), R(n2+1);
  for(i = 0; i < n1; i++) L[i] = A[left + i];
  for(i = 0; i < n2; i++) R[i] = A[mid + i];
  L[n1] = R[n2] = numeric_limits<int>::max();  // Be careful not to overflow
  i = j = 0;
  for(k = left; k < right; k++){
    if(L[i] <= R[j]){
      A[k] = L[i++];
    }else{
      A[k] = R[j++];
      cnt += n1 - i;
    }
  }
  return cnt;
}

long long mergeSort(vector<int> &A, int left, int right){
  int mid;
  long long v1, v2, v3;
  if(left + 1 < right){
    mid = (left + right) / 2;
    v1 = mergeSort(A, left, mid);
    v2 = mergeSort(A, mid, right);
    v3 = merge(A, left, mid, right);
    return v1 + v2 + v3;
  }else{
    return 0;
  }
}

int main(){
  int n;
  cin >> n;
  vector<int> A(n);
  for(int i = 0; i < n; i++) cin >> A[i];

  long long ans = mergeSort(A, 0, n);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 4316
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()

edges = []
if N%2==0:
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if i+j==N+1:
                continue
            else:
                edges.append((i,j))
else:
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if i+j==N:
                continue
            else:
                edges.append((i,j))

print(len(edges))
for e in edges:
    print(*e)

Measured memory_bytes: 42992
#![allow(
    non_snake_case,
    unused_variables,
    unused_assignments,
    unused_mut,
    dead_code
)]
//use proconio::fastout;
use proconio::input;
use proconio::marker::Chars;
//use proconio::marker::Usize1;
//use std::collections::HashSet;
// use std::cmp::*;
//use std::collections::VecDeque;

fn main() {
    input! {
      N:usize,K:usize
    }
    //    let mut ans = 0;
    let mut t = 1;
    if N == 1 {
        println!("1");
        return;
    }
    for i in 1..31 {
        t *= K;
        if N < t {
            println!("{}", i);
            return;
        }
    }
}


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

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

    vector<bool> A(26);

    for(int i = 0; i < 26; i++)
    {
        A.at(i) = false;
    }

    for(int i = 0; i < s.size(); i++)
    {
        A.at(int(s.at(i) - 'a')) = true;
    }

    for(int i = 0; i < 26; i++)
    {
        if(A.at(i) == false)
        {
            char a = i + 'a';
            cout << a << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}

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

int x[10003]={};

int main(){
	long long a,sum=0;
	cin>>a;
	for (int i=0;i<a;i++){
		cin>>x[i];
		sum+=x[i];
	}
	sort(x,x+a);
	cout<<x[0]<<" "<<x[a-1]<<" "<<sum<<endl;
	
}


Measured memory_bytes: 3176
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long 
const int MAX = 510000;
const ll mod = 1000000007;
int main() {
  string s;
  cin >> s;
  
  if(s[s.size()-1]=='s'){
    cout << s << "es";
  }else{
    cout << s << 's';
  }
  
  
  //cout << res;
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define MAXN 300
#define INF 1e12

int N, M, L, Q;
LL d1[MAXN + 3][MAXN + 3], d2[MAXN + 3][MAXN + 3];

int main() {
    cin >> N >> M >> L;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++)
            d1[i][j] = d2[i][j] = INF;
    }

    for (int i = 1; i <= M; i++) {
        int a, b, c;
        cin >> a >> b >> c;

        d1[a][b] = d1[b][a] = c;
    }

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++)
                d1[i][j] = min(d1[i][j], d1[i][k] + d1[k][j]);
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (d1[i][j] <= L)
                d2[i][j] = 1;
        }
    }

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);
            }
        }
    }

    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        int s, t;
        cin >> s >> t;

        if (d2[s][t] < INF)
            cout << d2[s][t] - 1 << endl;
        else
            cout << -1 << endl;
    }
}


Measured memory_bytes: 1920
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ld long double
ll mod=1e9+7;
void swap(int & a, int & b){
	int t=a;
	a=b;
	b=t;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	string s;
	cin>>s;
	int n=s.size();
	ll dp[n+1][13];

	for(int i=0;i<n+1;i++){
		for(int j=0;j<13;j++){
			dp[i][j]=0;
		}
	}
	if(s[0]!='?'){
		dp[0][s[0]-'0']=1;
	}
	else{
		for(int i=0;i<=9;i++){
			dp[0][i]=1;
		}
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<13;j++){
			int st=0,end=9;
			if(s[i]!='?'){
				st=s[i]-'0'; end=st;
			}
			for(int k=st;k<=end;k++){
				int rem=(k+ (j*10)%13)%13;
				dp[i][rem]=(dp[i][rem]+dp[i-1][j])%mod;
			}
		}
	}
	cout<<dp[n-1][5];
}

Measured memory_bytes: 10604
n,x=map(int,input().split())
a=list(map(int,input().split()))
sum1=sum(a)

for i in range(1,n):
  if i==1:
    if a[0]+a[1]>x:
      if a[0]>x:
        a[1]=0
        a[0]=x
      else:
        sa=(a[0]+a[1])-x
        a[1]=a[1]-sa
  else:
    if a[i]+a[i-1]>x:
      sa=(a[i]+a[i-1])-x
      a[i]=a[i]-sa
      
sum2=sum(a)
print(sum1-sum2)
      
      

Measured memory_bytes: 85644
#include <iostream>
#include <fstream>

#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#define pb push_back
#define mp make_pair


int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    // cout.setf(ios::fixed), cout.precision(20);

#ifdef LOCAL
    ifstream cin("input.txt");
#endif

    int N, D, sol = 0;
    cin >> N >> D;
    for (int i = 1; i <= N; i++) {
        int x, y;
        cin >> x >> y;
        if (0LL + 1LL * x * x + 1LL * y * y <= 1LL * D * D) {
            sol++;
        }
    }
    cout << sol << '\n';
    return 0;
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main(void) {
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vector<ll> a(x);
    rep(i, x) cin >> a[i];
    vector<ll> b(y);
    rep(i, y) cin >> b[i];
    vector<ll> c(z);
    rep(i, z) cin >> c[i];

    sort(c.rbegin(), c.rend());

    vector<ll> ab;

    rep(i,x)
    rep(j,y) {
        ab.push_back(a[i] + b[j]);
    }

    sort(ab.rbegin(), ab.rend());

    vector<ll> abc;

    ll n = min(k, (ll)ab.size());
    ll n2 = min(k, (ll)c.size());
    rep(i, n) {
        rep(j, n2) {
            abc.push_back(ab[i] + c[j]);
        }
    }

    sort(abc.rbegin(), abc.rend());

    rep(i, k) {
        cout << abc[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 42856
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <functional>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <numeric>

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> c(n),v(n,0);
    rep(i,0,n)cin>>c[i];
    
    int q; cin>>q;
    rep(i,0,q){
        int t,x,d;
        cin>>t>>x>>d;
        x--;
        if(t==1){
            v[x]+=d;
            if(v[x]>c[x]){
                cout<<x+1<<endl;
                return 0;
            }
        }else {
            v[x]-=d;
            if(v[x]<0){
                cout<<x+1<<endl;
                return 0;
            }
        }
    }
    cout<<0<<endl;
    
    return 0;
}



Measured memory_bytes: 3108
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cstdlib>
#define ll long long
#define lowbit(x) (x&(-x))
using namespace std;

int main(){
    int h,a;
    cin>>h>>a;
    cout<<(h/a)+((h%a)!=0)<<endl;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn main() {
    let n: usize = read();

    let mut a = Vec::new();
    for _ in 0..n {
        a.push(read::<usize>());
    }

    let mut flag = true;

    for i in a {
        if i % 2 != 0 {
            continue;
        }

        if i % 3 != 0 && i % 5 != 0 {
            flag = false;
        }
    }

    if flag {
        println!("APPROVED")
    } else {
        println!("DENIED");
    }
}

/// Example
/// ```
///
///  let n: i32 = read();
///
///  let mut xs = Vec::new();
///  for _ in 0..n {
///      xs.push(read::<i32>() + 1000);
///  }
/// ```
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn hoge() {
        assert_eq!(run(20, 15), 0);
        assert_eq!(run(20, 30), 0);
        assert_eq!(run(12, 4), 4);
    }
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main() {


    int n;

    vector<int> v;


    cin >> n;

    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }

    bool stop = false;

    int counter = 0;

    while (!stop) {

        bool forAllDivisible = true;

        for (int i = 0; i < n; i++) {
            if (v[i] % 2 == 0) {

            } else {
                forAllDivisible = false;
            }
        }

        if (!forAllDivisible) {
            stop = true;
        } else {

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

                v[i] = v[i] / 2;
            }
            counter += 1;
        }
    }

    cout << counter << "\n";


    return 0;
}

Measured memory_bytes: 256
#include <cstdio>

int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    int l[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&l[i]);
    }
    int b;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(l[i] < l[j]){
                b = l[i];
                l[i] = l[j];
                l[j] = b;
            }
        }
    }

    int ans = 0;
    for(int i = 0; i < k; i++){
        ans += l[i];
    }
    printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 888
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>

using ll = long long;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, x) for(int i=1;i<=(int)(x);i++)
#define rrep(i, x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i, x) for(int i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007
#define put2darr(arr, row, col) rep(i, row) { rep(j, col) { printf("%18d", arr[i][j]); } cout << endl; }

using namespace std;

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; }

/* 1..10
 * rep:   0 1 2 3 4 5 6 7 8 9
 * reps:  1 2 3 4 5 6 7 8 9 10
 * rrep:  9 8 7 6 5 4 3 2 1 0
 * rreps: 10 9 8 7 6 5 4 3 2 1
 */
ll n;
ll a[100010];
int main(){
    int n,k;
    string s;
    cin >> n >> k >> s;
    rep(i, n){
        if(i + 1 == k){
            cout << char(tolower(s[i]));
        }else{
            cout << s[i];
        }
    }
    cout << endl;
}



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

typedef long long ll;

int N,K;
ll F[500010],R[500010];
ll mod = 998244353;
ll ans = 0;

ll pow_mod(ll a,ll b)
{
    if(b == 0)return 1;
    ll res = pow_mod(a * a % mod,b / 2);
    if(b & 1)res = res * a % mod;
    return res;
}

ll con(int a,int b)
{
    if(a < b || b < 0)return 0;
    return F[a] * R[b] % mod * R[a - b] % mod;
}

int main()
{
    scanf("%d%d",&N,&K);

    if(N > K)
    {
        printf("0\n");
        return 0;
    }

    F[0] = 1;
    for(int i = 1; i < 500010; i++)F[i] = F[i - 1] * i % mod;
    for(int i = 0; i < 500010; i++)R[i] = pow_mod(F[i],mod - 2);

    for(int i = 0; i <= K; i++)
    {
        int j = K - i;
        if(i < j)continue;
        ans += (con(K - (i == j),i) - con(K - (i == j),i + (i - N + 1)) + mod) % mod;
        ans %= mod;
    }
    printf("%lld\n",ans);

    return 0;
}


Measured memory_bytes: 8192
import java.util.Scanner;

/**
 * https://abc058.contest.atcoder.jp/tasks/arc071_b
 */
public class Main {

	static final int MOD = 1000000007;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long M = sc.nextLong();
		long[] x = new long[(int)N];
		long[] y = new long[(int)M];
		for(int i=0; i<N; i++) x[i] = Long.parseLong(sc.next());
		for(int i=0; i<M; i++) y[i] = Long.parseLong(sc.next());
		sc.close();
		
		
		long xsum = 0;
		long ysum = 0;
		for(int i=0; i<N; i++){
			xsum = ( xsum - (N-2*i-1)*x[i]%MOD ) %MOD;
		}
		for(int i=0; i<M; i++){
			ysum = ( ysum - (M-2*i-1)*y[i]%MOD ) %MOD;
		}
		
	
		System.out.println(xsum*ysum%MOD);

	}

}

Measured memory_bytes: 50412
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
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; }

int N, W;
ll v[110], w[110];
ll dp[110][10010];

int main() {
    cin >> N >> W;
    rep(i, N) cin >> v[i] >> w[i];

    for (int sum_w = 0; sum_w <= W; sum_w++) {
        for (int i = 0; i < N; i++) {
            if (sum_w - w[i] >= 0) {
                chmax(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i]);
            }
            chmax(dp[i+1][sum_w], dp[i][sum_w]);
        }
    }

    ll ans = 0;
    for (int sum_w = 0; sum_w <= W; sum_w++) {
        chmax(ans, dp[N][sum_w]);
    }
    cout << ans << endl;
}



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

int dfs(int x,int y);
int mas[20][20];
int memo[20][20];
int X,Y;

int main(){
	while(1){
		cin >> X >> Y;
		if(X == 0 && Y == 0) break;
		for(int i=0;i<20;i++){
			for(int j=0;j<20;j++){
				memo[i][j] = -1;
			}
		}
		for(int i=0;i<Y;i++){
			for(int j=0;j<X;j++){
				cin >> mas[i][j];
			}
		}
		int ans = 0;
		for(int i=0;i<X;i++){
			if(mas[0][i] == 0){
				ans += dfs(i,0);
			}
		}
		cout << ans << endl;
	}
}

int dfs(int x,int y){
	if(memo[y][x] != -1) return memo[y][x];
	if(mas[y][x] == 1) return 0;
	if(y>=Y-1) return 1;
	if(mas[y][x] == 2) return (memo[y][x] = dfs(x,y+2));
	else{
		int cou = 0;
		for(int i=-1;i<2;i++){
			int nx = x + i;
			int ny = y + 1;
			if(nx >= 0 && nx < X && ((i == 0 && mas[ny][nx] == 2) || (mas[ny][nx] == 0))){
				cou += dfs(nx,ny);
			}
		}
		return (memo[y][x] = cou);
	}
}

Measured memory_bytes: 1164
#include <iostream>
using namespace std;
int n,a[5000];
int main(){
	int i,j,t,s;
	while(cin >> n && n){
		s = 0;
		t = -1000000;
		for(i=0;i<n;i++){
			cin >> a[i];
		}
		for(i=0;i<n;i++){
			s += a[i];
			if(t < s) t = s;
				for(j=i+1;j<n;j++){
					s += a[j];
					if(t < s) t = s;
				}
			s = 0;
		}
		cout << t << endl;
	}
	return 0;
}

Measured memory_bytes: 0
n,m=(int(i) for i in input().split())
#print(n,m)
a=[]
for i in range(n):
    a.append(input())
#print(a)
b=[]
for i in range(m):
    b.append(input())
#print(b)
flag=0

for k in range(n-m+1):
  for j in range(n-m+1):
    cnt=0
    for i in range(m):
      if a[0+i+k][0+j:m+j]==b[0+i]:
        cnt+=1
    if cnt==m:
      flag=1
  
print('Yes' if flag==1 else 'No') 
    


Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>

int compare(const void *a,const void *b){
  return *(int*)b-*(int*)a;
}


int main(){
	
	int N,a[100010],i,b[100010];
	
	scanf("%d",&N);
	
	for(i=1;i<=N;i++){
		scanf("%d",&a[i]);
	}
	for(i=0;i<=100001;i++){
		b[i]=0;     /*b[i]にはi-1入る*/
	}
	
	for(i=1;i<=N;i++){
		b[a[i]]++;
		b[a[i]+1]++;
		b[a[i]+2]++;
	}
	
	qsort(b,100002,sizeof(int),compare);
	
	printf("\n%d\n\n",b[0]);
	
	return 0;
}

Measured memory_bytes: 1276
K,N = map(int,input().split())
Ai=list(map(int,input().split()))

dist=[]
dist.append(abs(Ai[N-1]-Ai[0]))
for i in range(N-1):
  dist.append(abs((K+Ai[i])-Ai[i+1]))

print(min(dist))
#print(dist)
  


Measured memory_bytes: 86140
Scanf.scanf "%d %d" (fun n m ->
    let rec loop r i acc =
        if r = 1 then acc else
            if i * i > r then 1 :: acc else
                if r mod i <> 0 then loop r (i + 1) acc else
                    let rec loop2 r c =
                        if r mod i = 0 then loop2 (r / i) (c + 1)
                        else loop r (i + 1) (c :: acc)
                    in
                    loop2 r 0
    in
    let mm = 1_000_000_007 in
    let extgcd x y =
        let rec eg r0 r1 a0 a1 b0 b1 =
            if r1 = 0 then a0 else
                let q1 = r0 / r1 in
                eg r1 (r0 mod r1) a1 (a0 - q1 * a1) b1 (b0 - q1 * b1)
        in
        eg x y 1 0 0 1
    in
    let inv x y = (* 1/x in mod y *)
        let c = extgcd x y in
        if c < 0 then c + y else c
    in
    let ( *@) a b = (a * b) mod mm in
    let binomial a b =
        let rec loop i j acc =
            if j > b then acc else
                let acc = acc *@ i *@ inv j mm in
                loop (i - 1) (j + 1) acc
        in
        loop a 1 1
    in
    let l = loop m 2 [] in
    List.fold_left (fun acc v -> acc *@ binomial (v + n - 1) v) 1 l
    |> Printf.printf "%d\n"
)

Measured memory_bytes: 384
#include<vector>
#include<queue>
#include<functional>
#include<algorithm>
#include<set>
#include<iostream>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> t3;

const int MX = 100005;
const int MM = 1000000007;

int D[MX], E[MX];

int main()
{
	int N;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++){
		scanf("%d", D+i);
		E[i] = i;
	}
	sort(E+1, E+N+1, [](int l, int r){
		return D[l] < D[r];
	});

	int ans = 0;
	for(int i = 1; i <= N; i++){
		ans += (E[i]-i)&1;
	}
	printf("%d\n", ans/2);
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N, T;
 
int dp[3000 + 10][3000 + 10][2];//dp[i][j][k] := i品目まで食べるかを選んで、jの時間がかかったときのおいしさの最大値 
//kが0の時は、最後に食べるものをまだ選んでない 1の時は最後に食べるものをもう選んでる状態
vector<int> A, B;
 
int main() {
	cin >> N >> T;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		A.push_back(a), B.push_back(b);
	}
	
	dp[0][0][0] = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= T - 1; j++) {
			for (int k = 0; k < 2; k++) {
				dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]);
				if (j - A[i - 1] >= 0)
					dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - A[i - 1]][k] + B[i - 1]);
				//最後に食べるとする
				if (k == 0) {
					dp[i][j][1] = max(dp[i][j][1], dp[i - 1][j][k] + B[i - 1]);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= T - 1; i++)for (int j = 0; j < 2; j++)
		ans = max(ans, dp[N][i][j]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 70912
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

int32_t main(){
	IOS;
	int arr[5], pos = -1;
	for(int i = 0; i < 5; i++){
		cin >> arr[i];
		if( arr[i] == 0 )
			pos = i;
	}

	cout << pos+1 << endl;
	return 0;
}

Measured memory_bytes: 3636
import std.stdio;
import std.algorithm;
import std.string;
import std.range;
import std.array;
import std.conv;
import std.complex;
import std.math;
import std.ascii;
import std.bigint;
import std.container;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

const real eps = 1e-10;

void main(){
	auto notPrime = new bool[](2000000);
	notPrime[0] = notPrime[1] = true;
	for(int i; i < notPrime.length; ++i) {
		if(!notPrime[i]) {
			for(int j = 2; i*j < notPrime.length; ++j) {
				notPrime[i*j] = true;
			}
		}
	}
	int[] primes;
	for(int i; i < notPrime.length; ++i) {
		if(!notPrime[i]) {
			primes ~= i;
		}
	}
	while(true) {
		int k = readInt();
		if(k == 0) return;
		auto t = primes.assumeSorted.trisect(k);
		if(!t[1].empty) {
			writeln(0);
		} else {
			writeln(t[2][0] - t[0][$-1]);
		}
	}
}

Measured memory_bytes: 5116
#include<iostream>
using namespace std;
int main(){
  long long n,d;
  cin >> n >> d;
  long long yokuto=0;
  for(int i=0;i<n;i++){
    long long x,y;
    cin >> x >> y;
    if(x*x+y*y<=d*d){
      yokuto++;
    }
  }
  cout << yokuto;
}

Measured memory_bytes: 3608
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stdio.h>
#include <random>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <tuple>
#include <math.h>
#include <set>
#include <map>
using namespace std ;
using ll = long long ;
using ld = long double ;
using vll = vector<ll> ;
using vvll = vector<vll> ;
using vc = vector<char> ;
using vvc = vector<vc> ;
using vb = vector<bool> ;
using vvb = vector<vb> ;
using pll = pair<ll,ll> ;
#define all(v) v.begin(),v.end() 
const ll INF = 1e18 ;
const ll mod = 1e9+7 ;
const double pie = acos(-1); 
vll dx4 = {-1,0,1,0} ;
vll dy4 = {0,-1,0,1} ;
vll dx8 = {-1,0,1,1,1,0,-1,-1} ;
vll dy8 = {-1,-1,-1,0,1,1,1,0} ; 

void fix_cout(){cout << fixed << setprecision(20) ; }
ll gcd(ll a,ll b){if(b==0) return a ; return gcd(b,a%b) ; }
ll lcm(ll a,ll b){return a/gcd(a,b)*b ; }
void chmax(ll &a,ll b){if(a<b) a = b ; }
void chmin(ll &a,ll b){if(a>b) a = b ; }

int main(){
	ll n ; cin >> n ;
	ll ans = 10 ;
	for(int i=1;i<n;i++) ans = ans*10%mod ;
	ll sub = 8 ;
	for(int i=1;i<n;i++) sub = sub*8%mod ;
	ans += sub ;
	sub = 9 ;
	for(int i=1;i<n;i++) sub = sub*9%mod ;
	sub = sub*2%mod ;
	ans = ans-sub+mod ;
	cout << ans%mod << endl ;
}

Measured memory_bytes: 3628
#include<stdio.h>
#define MAX 500000
#define SENTINEL 2000000000
int L[MAX/2+2], R[MAX/2+2];
int cnt;
void merge(int A[], int n, int left, int mid, int right){
	int n1=mid-left;
	int n2=right-mid;
	for(int i=0; i<n1; i++){
		L[i]=A[left+i];
	}
	for(int i=0; i<n2; i++){
		R[i]=A[mid+i];
	}
	L[n1]=R[n2]=SENTINEL;
	int i=0, j=0;
for(int k=left; k<right; k++){
	cnt++;
	if(L[i]<=R[j]){
		A[k]=L[i++];
	}
	else{
		A[k]=R[j++];
		}
	}
}

void mergeSort(int A[],int n, int left, int right){
	if(left+1<right){
		int mid=(left+right)/2;
		mergeSort(A,n,left,mid);
		mergeSort(A,n,mid,right);
		merge(A,n,left,mid,right);
		}
}
int main(void){	
	int A[MAX],n,i;
	cnt=0;
	scanf("%d",&n);
	for(i=0; i<n; i++){
		scanf("%d",&A[i]);
	}
	mergeSort(A,n,0,n);
	for(i=0; i<n; i++){
		if(i){
			printf(" ");
		}
		printf("%d", A[i]);
		}
	printf("\n");
	printf("%d\n",cnt);
	return 0;
}


Measured memory_bytes: 5620
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
	int a[3];
	for (int i = 0; i < 3; ++i)
	{
		cin >> a[i];
	}
	sort(a, a+3);
	cout << (a[0]*a[1])/2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<deque>
using namespace std;
typedef long long ll;
int main()
{
	int num;
	scanf("%d", &num);
	ll c1 = 0, c2 = 0;
	deque<ll>d;
	d.resize(num);
	for (int i = 0; i < num; i++)
	{
		scanf("%lld", &d[i]);
		if (d[i] >= 0)
		{
			if (i % 2 == 0)c1 += d[i];
			else c2 += d[i];
		}
	}
	if (c1 == 0 && c2 == 0)
	{
		ll maxi = -2000000000;
		int rr;
		for (int i = 0; i < d.size(); i++)if (maxi < d[i])maxi = d[i], rr = i;
		printf("%lld\n%d\n", maxi, num - 1);
		for (int i = num - 1; i > rr; i--)printf("%d\n", i + 1);
		for (int i = 0; i < rr; i++)printf("1\n");
		return 0;
	}
	printf("%lld\n", max(c1, c2));
	vector<int>ans;
	if (c1 < c2)
	{
		ans.push_back(0);
		d.pop_front();
	}
	vector<int>mok;
	for (int i = 0; i < d.size(); i += 2)if (d[i] >= 0)mok.push_back(i);
	if (mok.empty())
	{
		for (int i = 0; i < d.size(); i++)ans.push_back(0);
	}
	else
	{
		for (int i = int(d.size()) - 1; i >= mok[mok.size() - 1] + 1; i--)ans.push_back(i);
		for (int i = int(mok.size()) - 1; i >= 1; i--)
		{
			int t = (mok[i] - mok[i - 1]) / 2;
			for (int j = 0; j < t - 1; j++)ans.push_back(mok[i - 1] + 2);
			ans.push_back(mok[i - 1] + 1);
		}
		for (int i = 0; i < mok[0]; i++)ans.push_back(0);
	}
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); i++)printf("%d\n", ans[i] + 1);
}

Measured memory_bytes: 256
def calc(h, w):
  ans = (h+1)*(w+1)
  cut_1 = h//2
  cut_2 = h//2 + (h%2 == 1)
  for i in range(1, w):
    s1 = [h*i, cut_1*(w-i), cut_2*(w-i)]
    s2 = [h*i, h*((w-i)//2), h*((w-i)//2+ ((w-i)%2 == 1))]
    ans = min([ans, max(s1)-min(s1), max(s2)-min(s2)])
  return ans
def main():
  a, b = map(int,  input().split())
  print(min([calc(a,  b), calc(b, a)]))
  
if __name__ == "__main__":
  main()
    

Measured memory_bytes: 9116
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int a,b;
    cin >> a >> b;
    pr(max(0, a-2*b));
}

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

int main(){
 int x;
  cin >> x;
  
 if(x==1) cout << 0 << endl;
 if(x==0) cout << 1 << endl;
  
}

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

using namespace std;
const int N = 1e5 + 5;
int arr[N];

int main() {
    // freopen("in.txt", "rt", stdin);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
    }
    sort(arr, arr + n);
    int j = n / 2, i = j - 1;
    printf("%d", arr[j] - arr[i]);
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <numeric>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

enum class State {
    CONSTANT,
    INCREASING,
    DECREASING,
};

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

    int N; cin >> N;

    State s = State::CONSTANT;
    int res = 1;

    int a, prev_a;
    cin >> prev_a;

    rep(i, 1, N) {
        cin >> a;

        switch(s) {
            case State::CONSTANT:
                if (prev_a < a) s = State::INCREASING;
                else if (prev_a > a) s = State::DECREASING;
                break;

            case State::INCREASING:
                if (prev_a > a) { ++res; s = State::CONSTANT; }
                break;

            case State::DECREASING:
                if (prev_a < a) { ++res; s = State::CONSTANT; }
                break;
        }

        prev_a = a;
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main (void){
    int i=1;
    int n;
    int x;
    int z;
    int f;
    int k;
    int o;
    int p;
    scanf("%d",&n);
    for (i=1; i<=n; i++){
        x=i;
        if(x%3==0){printf(" %d",x);}
        else while(1){
            z=i;
            if(i/10==3||i/100==3||i/1000==3){printf(" %d",i); break;}
            if(i%10==3||i%100==3||i%1000==3){printf(" %d",i); break;}
            f=z/10;
            if(f==3||f%10==3){printf(" %d",z); break;}
            k=f/10;
            if(k==3||k%10==3){printf(" %d",z); break;}
            o=k/10;
            if(o==3||k%10==3){printf(" %d",z); break;}
            p=o/10;
            if(p==3||k%10==3){printf(" %d",z); break;}
            break;


        }
      }printf("\n");
return 0;
    }

Measured memory_bytes: 600
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

unsigned long long d[201][201];

int main()
{
	int N, M, R;
	cin >> N >> M >> R;
	vector<int> r(R);
	for (auto i = 0; i < R; ++i)
	{
		cin >> r[i];
	}

	for (auto i = 1; i <= N; ++i)
	{
		for (auto j = 1; j <= N; ++j)
		{
			if (i == j)
			{
				d[i][j] = 0;
			}
			else
			{
				d[i][j] = LLONG_MAX / 2;
			}
		}
	}

	for (auto i = 0; i < M; ++i)
	{
		unsigned long long A, B, C;
		cin >> A >> B >> C;
		d[A][B] = C;
		d[B][A] = C;
	}

	for (auto i = 1; i <= N; ++i)
	{
		for (auto j = 1; j <= N; ++j)
		{
			for (auto k = 1; k <= N; ++k)
			{
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}

	sort(r.begin(), r.end());
	auto result = ULLONG_MAX;
	do
	{
		auto sum = 0ull;
		for (auto i = 1; i < R; ++i)
		{
			sum += d[r[i - 1]][r[i]];
		}
		result = min(result, sum);
	} while (next_permutation(r.begin(), r.end()));

	cout << result << endl;

	return 0;
}

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

int main(){
  const int N = 1000000;
  int dp1[N+1], dp2[N+1], n;
  
  for(int i=0;i<=N;i++)dp1[i] = dp2[i] = N;
  dp1[0] = dp2[0] = 0;
  
  int val = 1;
  for(int i=1;val<=N;i++){
    for(int j=0;j+val<=N;j++){
      int nxt = j+val;
      dp1[nxt] = min(dp1[nxt],dp1[j] + 1);
      if(val&1)dp2[nxt] = min(dp2[nxt],dp2[j] + 1);
    }
    val = i*(i+1)*(i+2)/6;
  }

  while(cin>>n,n)cout << dp1[n] << " " << dp2[n] << endl;
}

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

// ABCテンプレート

#define rep(i,n) for (int i = 0; i<(n); i++)
#define in(n) cin >> (n)
#define out(ans) cout << (ans) << endl;
#define keta(n) cout << fixed << setprecision((n));
using ll = int64_t;
using v = vector<int>;


int main() {
  int N, ans=0;
  ll D;
  cin >> N >> D;
  rep(i,N) {
    ll x, y;
    cin >> x >> y;
    if(x*x+y*y<=D*D) ans++;
  }
  cout << ans;
}

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

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N, W;
    cin >> N >> W;
    vector<ll> v(N), w(N);
    for(int i=0;i<N;++i) {
        cin >> w[i] >> v[i];
    }

    vector<vector<ll>> dp(N+1, vector<ll>(W+1, 0));

    for(int i=1;i<=N;++i) {
        for(int j=1;j<=W;++j) {
            dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            if(j >= w[i-1]) dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1]);
        }
    }

    cout << dp[N][W] << endl;
}


Measured memory_bytes: 80256
from collections import Counter

def main():
    n = int(input())
    s = [input() for _ in range(n)]
    C = Counter(s)
    cl = C.most_common()
    mx = cl[0][1]
    ans = []
    for c in cl:
        if (c[1] == mx):
            ans.append(c[0])
        else:
            break
    ans.sort()
    for i in ans:
        print(i)


if __name__ == "__main__":
    main()

Measured memory_bytes: 47668
//2018.12.15 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
    res s=0;
    bool w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void _swap(res &x,res &y){
    x^=y^=x^=y;
}
inline int _abs(const res &x){
    return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
    return x>y?x:y;
}
inline int _min(const res &x,const res &y){
    return x<y?x:y;
}
const int N=2e5+10;
namespace MAIN{
    char str[N];
    LL ans;
    int p=1;
    inline void MAIN(){
        scanf("%s",str+1);
        res n=strlen(str+1);
        for(res i=1;i<=n;i++){
            if(str[i]=='W')ans+=i-p,p++;
        }
        printf("%lld\n",ans);
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<queue>

using namespace std;

#define mod 1000000007
#define ll long long 


string str;
int D;
int n;
ll dp[10001][101][2];

ll solve(int idx, int rem, int tight) {
	if(idx == n)
		return rem == 0;

	if(dp[idx][rem][tight] != -1)
		return dp[idx][rem][tight];	

	ll ans = 0;
	int d = str[idx] - '0';
	int limit = (tight == 1) ? d : 9;
	int new_tight, new_rem;
	

	for(int i = 0; i <= limit; i++) {
		
		new_rem = rem;
		new_rem += i;
		new_rem %= D;

		new_tight = ((tight) & (i >= d));

		ans += solve(idx + 1, new_rem, new_tight);
		ans %= mod;
	}

	return dp[idx][rem][tight] = ans%mod;
}


int main() {
	
	memset(dp, -1, sizeof(dp));
	cin>>str>>D;

	n = str.length();
	ll ans = solve(0, 0, 1)%mod;

	ans--;
	if(ans == -1)
		ans = mod - 1;
    cout<<ans<<endl;

}

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

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}


int main(){
  ll n;
  cin >> n;
  vector<ll> x(n);
  rep(i,n) cin >> x[i];
  sort(x.begin(), x.end());
  ll ans = 1e9;
  ll mi = x[0];
  ll ma = x[n-1];
  for(ll i = mi; i <= ma; i++){
    ll sum = 0;
    rep(j,n){
      sum += (x[j] - i)*(x[j] - i);
    }
    ans = min(ans, sum);
  }
  cout << ans << endl;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;

map <char,int> mp;
int a[N],g[3];

void init(){
	mp['r'] = 0;mp['s'] = 1;mp['p'] = 2;
	return ;
}

int main()
{
	init();
	int n,k;
	scanf("%d%d",&n,&k);
	scanf("%d%d%d",&g[0],&g[1],&g[2]);
	
	string l;
	cin >> l;
	for(int i = 0;i < l.size();++i) a[i] = (mp[l[i]]+2)%3;
	int sum = 0;
	for(int i = 0;i < l.size();++i){
		if(i-k >= 0 && a[i] == a[i-k]){
			a[i] = 4;
			continue;
		}
		sum += g[a[i]];
	}
	printf("%d\n",sum);
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>  // ver2.1.9
#define int long long
#define endl "\n"
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define Pii pair<int,int>
#define Tiii tuple<int,int,int>
#define PQi priority_queue<int>
#define PQir priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define sortr(v) sort(v,greater<>())
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define dem(a,b) ((a+b-1)/(b))
#define Vout(a) rep(lZ,0,a.size()-1)cout<<a[lZ]<<' ';cout<<a.back()<<endl
#define VVout(a) rep(lW,0,a.size()){Vout(a[lW]);}
#define INF 9000000000000000000  //  9.0 * 10^18
#define MOD 1000000007  //  10^9 + 7
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm
void uniq(Vi &v){sort(ALL(v)); v.erase(unique(ALL(v)),v.end());}  //  uniqのやつ

int mypow(int x, int n, int m){  //  累乗x^n(mod m)  O(log(n))
if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}

int f(int l,int n,Vi big,Vi P){
  if(l==0) return 1;
  if(n==1) return 0;
  else if(n <= big[l-1]+1) return f(l-1,n-1,big,P);
  else if(n==big[l-1]+2) return P[l-1]+1;
  else return f(l-1,n-2-big[l-1],big,P) + P[l-1] + 1;
  return 0;
}

signed main() {
  cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(16);
  Vi big(51);
  big[0] = 1;
  repeq(i,1,50){
    big[i] = big[i-1]*2+3;
  }
  Vi P(51);
  repeq(i,0,50){
    P[i] = mypow(2,i+1,INF)-1;
  }
  
  int l,n;
  cin >> l >> n;
  cout << f(l,n,big,P) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define F(i,a,b) for(int i=a;i<=b;++i)
int n,m,tot,ans;
char s[10][10];
int main()
{
	scanf("%d%d%d",&n,&m,&tot);
	F(i,0,n-1) scanf("%s",s[i]);
	int cnt=0;
	F(i,0,(1<<n)-1) F(j,0,(1<<m)-1)
	{
		cnt=0;
		F(k,0,n-1) if((1<<k)&i)
			F(l,0,m-1) if((1<<l)&j)if(s[k][l]=='#') ++cnt;
		if(cnt==tot) ++ans;
	}
	printf("%d",ans);
	return 0;
}

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

using namespace std;

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

const int INF = 1e9 + 7, N = 100005;

int dt[N];

int mx = 0;

vi G[N];

void dfs1(int u, int d = 0, int p = -1) {
	dt[u] = d;
	for(int v:G[u]) if(v != p)
		dfs1(v, d+1, u);
}

void dfs(int u, int d = 0, int p = -1) {
	if(d > dt[u]) return;
	if(G[u].size() == 1) {
		mx = max(mx, dt[u] - 1);
	} else {
		mx = max(mx, dt[u]);
	}
	for(int v:G[u]) if(v != p)
		dfs(v, d+1, u);
}

signed main()
{
	IO_OP;
	
	int n, s, t;
	cin >> n >> s >> t;
	for(int i=0;i<n-1;i++) {
		int u, v;
		cin >> u >> v;
		G[u].PB(v);
		G[v].PB(u);
	}
	dfs1(t);
	dfs(s);
	cout << mx << endl;
}



	

Measured memory_bytes: 9984
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <numeric>
using namespace std;
typedef long long int ll;


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n; int m; cin >> m;
    vector<string> s(n);
    for(int i=0;i<n;i++){
        cin >> s[i];
    }
    sort(s.begin(),s.end());
    for(int i=0;i<n;i++){
        cout << s[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
import static java.lang.System.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_B
 * 
 * @author Kyoro
 */
public class Main {

	int x;

	public void read() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(in));
		x = Integer.parseInt(reader.readLine());
	}

	public String solve() {
		return String.valueOf(x * x * x);
	}

	public static void main(String[] args) {
		Main main = new Main();
		try {
			main.read();
			out.println(main.solve());
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}



Measured memory_bytes: 24192