akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

vector<long> sumA;

long calc(int start, int end,  int split) {
    return abs((sumA[split] - sumA[start]) - (sumA[end] - sumA[split]));

}

long localMin(int start, int end) {
    long offset = sumA[start];
    long val = (sumA[end] - sumA[start]) / 2;

    int a = lower_bound(sumA.begin() + start, sumA.begin() + end, offset + val) - sumA.begin();
    //cout << start << " " << end << " " << a << " " << min(calc(start,end,sumA,a-1),calc(start,end,sumA,a)) << endl;
    return min(calc(start, end, a), calc(start, end,  a - 1));

}


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

    int N;
    cin >> N;
    vector<int> A;

    sumA.push_back(0);
    for (int i = 0; i < N; ++i) {
        int tmp;
        cin >> tmp;
        A.push_back(tmp);
    }
    long sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += A[i];
        sumA.push_back(sum);
    }

    long ans = 1000000000000000000L;
    for (int center = 2; center <= N - 2; ++center) {
        long left_val = localMin(0, center);
        long right_val = localMin(center, N);
        long left_max = (sumA[center] + left_val) / 2;
        long left_min = (sumA[center] - left_val) / 2;
        long right_max = (sumA[N] - sumA[center] + right_val) / 2;
        long right_min = (sumA[N] - sumA[center] - right_val) / 2;
        //cout << "res" << left_max << " " << left_min <<  " "  <<  right_max << " " <<  right_min << endl;
        ans = min(ans, max(left_max, right_max) - min(left_min, right_min));
    }
    cout << ans << endl;
}

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

#define MAX_N 2000
int x[MAX_N][MAX_N];
int H, W;
int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> x[i][j];
		}
		if (x[i][0] == 1) { x[i][0] = 0; }
		else { x[i][0] = 1; }
		for (int j = 1; j < W; j++) {
			if (x[i][j] == 1) {
				x[i][j] = 0;
			}
			else {
				x[i][j] = x[i][j - 1] + 1;
			}
		}
	}
	int maxn = 0;
	for (int i = 0; i < W; i++) {
		for (int j = 0; j < H; j++) {
			int X = x[j][i], cnt = 0;
			if (x[j][i] == 0)continue;
			for (int k = j; k >= 0; k--) {
				cnt++; X = min(X, x[k][i]);
				if (X*(j + 1) <= maxn) { break; }
				maxn = max(maxn, X*cnt);
			}
		}
	}
	cout << maxn << endl;
	return 0;
}

Measured memory_bytes: 14000
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Random r = new Random();
        int n = 10000000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = r.nextInt();
        }
        Arrays.sort(a);
        solve();
    }

    public static void solve() {
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        System.out.println(r * r);
        sc.close();
    }
}


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

int mod = 1000000007;

int main()
{
    int H, N, tmp;
    cin >> H >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        H -= tmp;
    }
    cout << (H > 0 ? "No" : "Yes");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memset(x,y,sizeof(x))
#define STS system("pause")
template<class D>I read(D &res){
	res=0;register D g=1;register char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')g=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		res=(res<<3)+(res<<1)+(ch^48);
		ch=getchar();
	}
	res*=g;
}
const int M=6010;
int n,Mod,N,ans;
int f[6060][12020];
I add(int &x,int y){
	(x+=y)>=Mod?x-=Mod:0;
}
int main(){
	read(n);read(Mod);N=n*3;
	f[0][M]=1;
	F(i,0,N){
		F(j,-N,N){
			add(f[i+1][j+1+M],f[i][j+M]);
			add(f[i+2][j-1+M],(ll)f[i][j+M]*(i+1)%Mod);
			add(f[i+3][j+M],(ll)f[i][j+M]*(i+1)%Mod*(i+2)%Mod);
		}
	}
	ans=0;
	F(i,0,N)add(ans,f[N][i+M]);
	printf("%d",ans);
	return 0;
}



Measured memory_bytes: 282880
#include <algorithm>
#include <bits/stdc++.h>
#include<iostream>
#include<string>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
const ll MOD=1000000007;
const ll INF=1000000000000000001;
int main(){
 string s;cin>>s;
 int cnt=0;
 rep(i,s.size()-1){
    if(s[i]==s[i+1]){
        if(s[i]=='1')s[i+1]='0';
        if(s[i]=='0')s[i+1]='1';
        cnt++;
    }
 }
 cout << cnt << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>

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

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

    if(s >= 'a' && s <= 'z') {
        cout << 'a' << "\n";
    } else {
        cout << 'A' << "\n";
    }
}

Measured memory_bytes: 3592
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <complex>
#include <vector>
#include <limits>
#include <iomanip>
#include <cassert>

using namespace std;

typedef long long ll;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n-1;i >= 0;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second

const long double pi = 3.141592653589793;
const int mod = 1e9 + 7;

ll money = 1000, share = 0;
ll A[100], N;


int main() {

 // freopen("input.in","r",stdin);
 // freopen("output.out","w",stdout);

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

  int x;
  cin>>x;
  if(x >= 30) cout<<"Yes";
  else cout<<"No"<<endl;










 return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <list>
#include <bitset>
#include <numeric>
#include <utility>
#define INF 1e9
#define MOD 1000000007
#define ll long long
#define int long long
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> p;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    double t,a;
    vector<double> h(n);
    cin>>n>>t>>a;
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    double q=900000000;
    int ans;
    for(int i=0;i<n;i++){
        double x=abs(t-0.006*h[i]-a);
//        cout<<x<<endl;
        if(x<q){
            q=x;
            ans=i+1;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 33024
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> W(N);
	for(int i = 0; i < N; ++i) {
		cin >> W[i];
	}
	int sum = 0;
	for(int i = 0; i < N; ++i) {
		sum += W[i];
	}
	int b = 0, pos = 0;
	while(b <= sum / 2) {
		b += W[pos];
		++pos;
	}
	cout << min(b * 2 - sum, sum - (b - W[pos - 1]) * 2) << endl;
	return 0;
}

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

using namespace std;
typedef long long ll;




int main()
{
    vector<int> a(3);
    rep(i,3) cin >> a[i];
    sort(all(a));
    reverse(all(a));
    
    cout << a[0]*10 + a[1] + a[2] << endl;
    
    
    return 0;
}



Measured memory_bytes: 256
n = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)
b = gets.chomp.split(" ").map(&:to_i)
count = 0

for i in 0..n-1
  #puts "a[i]#{a[i]} a[i+1]#{a[i+1]} b[i]#{b[i]}"
    if a[i]+a[i+1] > b[i]
        if a[i] > b[i]
            count += b[i]
            a[i] -= b[i]
            b[i] = 0
        else
            count += a[i] + ((b[i]-a[i]))
            a[i+1] -= b[i] - a[i]
            b[i] = b[i]-a[i] - (a[i+1]-b[i])
            a[i] = 0
        end
    else
        count += a[i] + a[i+1]
        a[i] = 0
        a[i+1] = 0
        b[i] -= b[i]-(a[i]+a[i+1])
    end
    # if i == n-1
    #     if a[i+1]>b[i]
    #         count += a[i+1] - b[i]
    #     else
    #         count += a[i+1]
    #     end
    # end
  #puts "count#{count}
end
puts count



Measured memory_bytes: 17556
import math
n,m = map(int,input().split())
s = input()
t = input()
lcm = n*m//math.gcd(n,m)
ans = []
s_ind = lcm//n
t_ind = lcm//m
check_ind = s_ind*t_ind//math.gcd(s_ind,t_ind)
for i in range(0,lcm,check_ind):
    if s[i//s_ind] != t[i//t_ind]:
        print(-1)
        exit()
print(lcm)

Measured memory_bytes: 9352
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define NCLR(a) memset((a), -1 ,sizeof(a))
#define sq(n) (n) * (n)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
typedef complex<double> P;
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 29;
static const LL LL_INF = 1ll << 60;
static const int dx[] = { -1, 0, 1, 0, 1, -1, 1, -1 };
static const int dy[] = { 0, -1, 0, 1, 1, 1, -1, -1 };

#ifdef WIN32
#define dump(x) cout << #x << " = " << (x) << "\n"
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n"
#else
#define dump(x)
#define debug(x)
#endif

string str;
int n;


void solve() {
	while ( n-- ) {
		dump( str );
		string cstr;
		for ( int i = 0; i < str.size(); i++ ) {
			int cnt = 0;
			int j = i;
			for ( ; j < str.size(); j++ ) {
				if ( str[ i ] != str[ j ] ) {
					i = j - 1;
					break;
				}
				cnt++;
			}
			stringstream many;
			many << cnt;
			cstr += many.str() + str[ i ] ;
			i = j - 1;
		}
		str = cstr;
	}
	printf( "%s\n", str.c_str() );
}

int main() {
#ifdef WIN32
	printf( "Debug Mode\n" );
#endif
	while ( cin >> n && n ) {
		cin >> str;
		solve();
	}
	return 0;
}

Measured memory_bytes: 1356
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

int bfs(V &start, V &run) {
    int N = start.size();
    int M = run.size();

    map<V, int> d;
	queue<V> que;
    que.push(start);
    d[start] = 0;

    V g1;
    int bit = 0;
    for (auto x : run) {
        rep(k, x) g1.emplace_back(bit);
        bit ^= 1;
    }

    V g2 = g1;
    rep(i, N) g2[i] ^= 1;

    while (!que.empty()) {
        auto now = que.front(); que.pop();
        if (now == g1 || now == g2) {
            return d[now];
        }

        rep(i, N - 1) {
            V nxt(now);
            swap(nxt[i], nxt[i + 1]);
            if (d.count(nxt) == 0) {
                que.push(nxt);
                d[nxt] = d[now] + 1;
            }
        }

    }

}

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

    int N, M;
    cin >> N >> M;
    V start(N);
    rep(i, N) cin >> start[i];
    V run(M);
    rep(i, M) cin >> run[i];

    cout << bfs(start, run) << endl;

}

Measured memory_bytes: 4552
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  string ans,query;
  while(ans.size()<11){
    if(!ans.empty()){
      query=ans+"0";
      while(query.size()<18) query+="9";
      cout<<"? "<<query<<endl;
      char f;
      cin>>f;
      if(f=='Y'){
	ans+="0";
	continue;
      }
    }
    int l=0,r=9;
    while(l+1<r){
      int m=(l+r)/2;
      query=ans;
      query+=(char)('0'+m);
      while(query.size()<18) query+="9";
      cout<<"? "<<query<<endl;
      char f;
      cin>>f;
      if(f=='Y') r=m;
      else l=m;
    }
    ans+=(char)('0'+r);
  }
  int l=0;
  while(l<11){
    l++;
    query="1";
    for(int i=0;i<l-1;i++) query+="0";
    cout<<"? "<<query<<endl;
    char f;
    cin>>f;
    if(f=='N'){
      cout<<"! "<<ans.substr(0,l-1)<<endl;
      return 0;
    }
  }
  l=0;
  while(l<11){
    l++;
    query="2";
    for(int i=0;i<l-1;i++) query+="0";
    cout<<"? "<<query<<endl;
    char f;
    cin>>f;
    if(f=='Y'){
      cout<<"! "<<ans.substr(0,l)<<endl;
      return 0;
    }
  }
  
  return 0;
}


Measured memory_bytes: 668
def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))+[0]*(k+10)
  dp=[(float("inf")) for i in range(n+k+10)]
  dp[0]=0
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  return (dp[n-1])
print(main())


Measured memory_bytes: 57568
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
#define Y second
#define FOR(x,e,b) for(int e = head[x], b = vb[e]; e; e = nxt[e], b = vb[e])
#define N 200010
int n,m,q;
pii ans[N][11];
int M = 0, head[N], vb[N], nxt[N], vc[N];

void ins(int a,int b)
{
	nxt[++ M] = head[a];
	head[a] = M;
	vb[M]=b;
}

void insert(int a,int b)
{
	ins(a, b);
	ins(b, a);
}

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int main()
{
	n = read();
	m = read();
	for(int i = 1; i <= m; i ++)
	{
		int a, b;
		a = read();
		b = read();
		insert(a, b);
	}
	q = read();
	for(int i = 1; i <= q; i ++)
	{
		int v, d, c;
		v = read();
		d = read();
		c = read();
		ans[v][d] = max(ans[v][d], mp(i, c));
	}
	for(int i = 10; i >= 1; i --)
		for(int j = 1; j <= n; j ++)
		{
			ans[j][i - 1] = max(ans[j][i - 1], ans[j][i]);
			FOR(j, e, b)
				ans[b][i - 1] = max(ans[b][i - 1], ans[j][i]);
		}
	for(int j = 1; j <= n; j ++)
		printf("%d\n",ans[j][0].Y);
	return 0;
}


Measured memory_bytes: 12288
// Contest: AtCoder Beginner Contest 175 (https://atcoder.jp/contests/abc175)
// Problem: A: Rainy Season (https://atcoder.jp/contests/abc175/tasks/abc175_a)


// region boilerplate
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <chrono>
#include <cstdint>
#include <deque>
#include <exception>
#include <forward_list>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#if __cplusplus >= 201703L
#   include <optional>
#   include <string_view>
#   include <variant>
#endif

using namespace std;

#if __cplusplus >= 201703L
#   define all(a)      begin(a),end(a)
#   define sz(x)       ((int)size(x))
#else
#   define all(a)      (a).begin(),(a).end()
#   define sz(x)       ((int)(x).size())
#endif

#define rep(a, b)      for(int a = 0; a < (b); ++a)
#define reps(a, b, c)  for(int a = (b); a < (c); ++a)
#define trav(a, b)     for(auto& a : b)

using ll = long long;
using ld = long double;
using u64 = uint64_t;
using u32 = uint32_t;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vpi = vector<pi>;

#if __cplusplus >= 201703L
#   define MAYBE_UNUSED [[maybe_unused]]
#else
#   define MAYBE_UNUSED
#endif

MAYBE_UNUSED static constexpr int INF = (int)1e9 + 5;
MAYBE_UNUSED static constexpr ll INFL = (ll)1e18 + 5;
MAYBE_UNUSED static mt19937 rng((u32)chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
//endregion

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

    string s; cin >> s;
    int i = 0;
    if (s == "RRR")
        i = 3;
    else if (s[1] == 'R' && (s[0] == 'R' || s[2] == 'R'))
        i = 2;
    else if (find(all(s), 'R') != end(s))
        i = 1;
    cout << i << '\n';

    return 0;
}


Measured memory_bytes: 3576
const input=require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/);const tn=():number=>{const a=input[0];input.shift();return Number(a)};const tnn=(n:number):number[]=>{const a=[];for(let i=0;i<n;i++){a.push(tn())}return a};const ts=():string=>{const a=input[0];input.shift();return String(a)};const tss=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(ts())}return a};const tc=():string=>{let a=input[0].split('');const b=a[0];a.shift();if(a.length>0){input[0]=a.join('')}else{input.shift()}return String(b)};const tcc=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(tc())}return a};const to=(...arg)=>{console.log(...arg)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const floor=(a)=>{return Math.floor(a)};const asc=(ar:number[])=>{return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{return ar.sort((a,b)=>{return b-a})};const sw=(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length-1;i+=2){if(eval(a+op+arr[i])){return arr[i+1];}}return arr[arr.length-1]};const near=(n:number,arr:number[]):number=>{let ne=arr[0],ni=0;for(let i=1;i<arr.length;i++){if(Math.abs(n-ne)>Math.abs(n-arr[i])){ne=arr[i];ni=i}}return ni};
const main=()=>{
  let [a,b,k]=tnn(3)
  let x=[]
  for(let i=0;i<k;i++){
    if(a+i>b-i){
      break
    }
    if(a+i===b-i){
      x.push(a+i)
      break
    }else {
      x.push(a+i)
      x.push(b-i)
    }
  }
  to(...asc(x))
}
main()


Measured memory_bytes: 7628
// http://www.igaris.com/math/c.pdf

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define NEXTP(x) next_permutation(x.begin(),x.end())
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = (B-1); I >= (A); --I)
const ll INF=1e18+7;
const ll MOD=1e9+7;

class comb{
	public:
	vector<ll> f,fr;
	ll MOD;
	//a^(p-1) = 1 (mod p)(p->Prime numbers)
	//a^(p-2) = a^(-1)
	ll calc(ll a,ll b,ll p){//a^(b) mod p   
		if(b==0)return 1;
		ll y = calc(a,b/2,p);y=(y*y)%p;
		if(b & 1) y = (y * a) % p;
		return y;
	}
	void init(ll n,ll mod){//input max_n
		MOD = mod;
		f.resize(n+1);
		fr.resize(n+1);
		f[0]=fr[0]=1;
		for(ll i=1;i<n+1;i++){
			f[i] = (f[i-1] * i) % mod;
			fr[i] = calc(f[i],mod-2,mod);
		}
	}
	ll nCr(ll n,ll r){
		return f[n] * fr[r] % MOD * fr[n-r] % MOD;
	}
};


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n,k;
	cin >> n >> k;
	comb co;
	co.init(n+k,MOD);
	ll ans = 0;
	FOR(i,1,k+1){
		ll w = 0;
		FOR(j,1,i+1){
			w += co.calc(-1,i-j,MOD)*co.nCr(i,j)%MOD*co.calc(j,n,MOD)%MOD;
			w %= MOD;
		}
		w *= co.fr[i];
		w %= MOD;
		ans += w;
		ans %= MOD;
	}
	if(ans<0)ans += MOD;
	cout << ans << endl;
}


Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
int main ()
{
	long long n, a, b;
	scanf ("%lld%lld%lld", &n, &a, &b);
	if (a > b) swap (a, b);
	if ((a - b) % 2 == 0) printf ("%lld\n", (b - a) / 2);
	else printf ("%lld\n", min (a + (b - a - 1) / 2, n - b + 1 + (b - a - 1) / 2));
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for (int i = m; i < n; ++i)
#define rem(i, m, n) for (int i = m; i >= n; --i)
typedef long long ll;
#define mod 1000000007
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; }

int main() {
  vector<int> a(3);
  rep(i, 0, 3) cin >> a[i];
  sort(a.begin(), a.end(), greater<>());
  cout << 10*a[0] + a[1] + a[2] << endl;
  return 0;
}


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

long long int memo[111][11][1111];

long long int solve(int p, int n, int s){
  
  if(n == 1 && s >= p && s < 101) return memo[p][n][s] = 1;
  if(n == 1 || s*100 < s) memo[p][n][s] = 0;
  if(s < 0) return 0;
  if(~memo[p][n][s]) return memo[p][n][s];
  
  long long int ans = 0;
  for(int i=p;i<101;i++) ans += solve(i+1, n-1, s-i);
  
  return memo[p][n][s] = ans;
}

int main(){

  memset(memo, -1, sizeof(memo));
  for(int i=1;i<10;i++)
    for(int j=0;j<1001;j++) 
      solve(0, i, j);
  
  int n, s;
  while(cin >> n >> s, n+s) cout << solve(0, n, s) << endl;
  
}

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

#define pb push_back
#define mp make_pair
#define ll long long int
#define MOD 1000000007

void Fast_IO(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	// #ifndef ONLINE_JUDGE
	// freopen("input.in","r",stdin);
	// freopen("output.out","w",stdout);
	// freopen("debug.out","w",stderr);
	// #endif
}

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

	ll m=a[0],ans=0;
	for(i=0;i<n;i++){
		ans=ans+(ll)max(0,(int)(m-a[i]));
		if(m<a[i])
			m=a[i];
	}

	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 5212
#include <iostream>
#include <numeric>
#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() {

	string S;
	cin >> S;
	if (S.at(2) == S.at(3) && S.at(4) == S.at(5)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}


}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <string>    
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll h, w;
string str;

int main(){
	cin >> h >> w;
	bool s[h][w];
	for(ll i = 0; i < h; i++){
		cin >> str;
		for(ll j = 0; j < w; j++){
			if(str[j] == '#'){s[i][j] = false;}
			else{s[i][j] = true;}
		}
	}
	
	ll score[h][w];
	memset(score, 0, sizeof(score));
	for(ll i = 0; i < h; i++){
		ll buf = 0;
		for(ll j = 0; j < w; j++){
			if(!s[i][j]){buf = 0;}
			else{
				buf++;
				score[i][j] += buf;
			}
		}
		
		for(ll j = w-1; j >= 0; j--){
			if(!s[i][j]){buf = 0;}
			else{
				if(buf == 0){buf = score[i][j];}
				else{score[i][j] = buf;}
			}
		}
	}
	
	ll scorew[h][w];
	memset(scorew, 0, sizeof(scorew));
	for(ll j = 0; j < w; j++){
		ll buf = 0;
		for(ll i = 0; i < h; i++){
			if(!s[i][j]){buf = 0;}
			else{
				buf++;
				scorew[i][j] += buf;
			}
		}
		
		for(ll i = h-1; i >= 0; i--){
			if(!s[i][j]){buf = 0;}
			else{
				if(buf == 0){buf = scorew[i][j];}
				else{scorew[i][j] = buf;}
			}
		}
	}
	
	ll ans = 0;
	for(ll i = 0; i < h; i++){
		for(ll j = 0; j < w; j++){
			if(s[i][j]){
				ans = max(score[i][j]+scorew[i][j]-1, ans);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 66688
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;
const double EPS = 1e-11;
static const double pi = 3.141592653589793;

bool isOK(double theta, double x, double a, double b){
  if (a*tan(theta) > b){
    return a*b*b >= 2*x*tan(theta);
  }else {
    return 2*a*a*b - a*a*a*tan(theta) >= 2*x;
  }
}

// [ok,ng]から okであるもののうち最大を求める
double my_binary_search(double ok, double ng, double x, double a, double b){
  double mid;
//  while(abs((ng-ok)/ng) > EPS){
  for(int i=0; i<1000000; i++){
    mid = (ok+ng)/2;
    if(isOK(mid, x, a, b)) ok = mid;
    else ng = mid;
  }
  return ok;
}


int main(int argc, const char * argv[]) {
  double a, b, x; cin >> a >> b >> x;
  
  double ans = my_binary_search(0, pi/2, x, a, b);
  cout << setprecision(10) << fixed << ans * 180 / pi << endl;

  return 0;
}

Measured memory_bytes: 256
import copy
N = int(input())
testimony = []
for n in range(N):
    A = int(input())
    testimony.append({})
    for a in range(A):
        x, y = map(int, input().split())
        testimony[n][x - 1] = y    

def judge(truthy):
    answer = True
    for i in range(len(truthy)):
        if truthy[i] == 1:
            for t in testimony[i].keys():
                if truthy[t] != testimony[i][t]:
                    answer = False
                    break
        if not answer:
            break
    # print(answer, truthy)
    return 0 if not answer else truthy.count(1)

def dfs(truthy, depth):
    if N == depth:
        return judge(truthy)
    truth = copy.copy(truthy)
    truth.append(1)
    t = dfs(truth, depth + 1)
    false = copy.copy(truthy)
    false.append(0)
    f = dfs(false, depth + 1)
    return max(t, f)

print(dfs([], 0))

Measured memory_bytes: 9360
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
//#include <stdio.h>
//#include <stack>
//#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
//#include <fstream>
//#include <list>
//#include <iomanip>
#include <cctype>

using namespace std;

#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define ssort(z) sort(z.begin(),z.end())
#define eerase(z) z.erase(unique(z.begin(),z.end()),z.end())


void printVec(std::vector<int> & vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}

int vector_finder(std::vector<string> vec, string number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}

#include <sstream> 
std::vector<std::string> StringSplit(const std::string& str, char sep)
{
	std::vector<std::string> v;
	std::stringstream ss(str);
	std::string buffer;
	while (std::getline(ss, buffer, sep)) {
		v.push_back(buffer);
	}
	return v;
}

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

bool comp(const string a, const string b) {
	return a.length() < b.length();
}

bool integer(double num) {
	return floor(num) == num;
}

string gen(int num) {
	string str = "";
	for (int i = 0; i < num; i++) str += ".";
	return str;
}
Int fact(int num) {
	if (num == 0) return 1;
	else return num * fact(num - 1);
}

int main() {
	//int n; cin >> n;
	int n = 5;
	vector<int> v(n), c(n);
	int sum = 0,temp=11,hoji=-1;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		if (v[i] % 10 < temp&& v[i] % 10>0) {
			hoji = i;
			temp = v[i] % 10;
		}
	}

	for (int i = 0; i < n; i++) {
		if (i != hoji) sum +=( (v[i] + 9) / 10)*10;
		else sum += v[i];
	}
	cout << sum;
	
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
function main(input) {
  var a = parseInt(input[0].split(" ")[0], 10);
  var b = parseInt(input[0].split(" ")[1], 10);
  if(a < 10 && b < 10) {
    console.log("%d", a * b);
  } else {
    console.log("-1");
  }
}

main(require("fs").readFileSync("/dev/stdin", "utf8").split("\n"));


Measured memory_bytes: 10056
import sys
import numpy as np
from collections import Counter
import math

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = np.array(readline().split(), np.int64)
    A_cum = np.cumsum(A)
    counter = Counter(A_cum)

    def cmb(n, r):
        return math.factorial(n) // (math.factorial(r)*math.factorial(n-r))

    ans = 0
    for key, value in counter.items():
        if value >= 2:
            ans += cmb(value, 2)
        if key == 0:
            ans += value
    print(ans)


if __name__ == '__main__':
    main()


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

int main(){
    int n;
    cin>>n;
    
    vector<int> a(n);
    
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
    
    
    long long sum = 0;
    

    for(int i=0;i<n;i++){
        sum = sum + a[i];
    }
    
    cout<<a[0]<<" "<<a[n-1]<<" "<<sum<<endl;
}


Measured memory_bytes: 3204
T=[]
for _ in range(5):
    T.append(int(input()))
ans=sum([(t//10)*10 for t in T])
U=[t%10 for t in T]
U.sort()
if U[4]==0:
    pass
elif U[3]==0:
    ans+=U[4]
elif U[2]==0:
    ans+=10+U[3]
elif U[1]==0:
    ans+=20+U[2]
elif U[0]==0:
    ans+=30+U[1]
else:
    ans+=40+U[0]
print(ans)

Measured memory_bytes: 3064
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    L = []
    res = [[False] * 3 for _ in range(3)]
    for _ in range(3):
        L.append(lmi())
    n = ii()
    for _ in range(n):
        num = ii()
        for i in range(3):
            for j in range(3):
                if L[i][j] == num:
                    res[i][j] = True
    # print(res)
    trans = [[None] * 3 for _ in range(3)]
    for i in range(3):
        for j in range(3):
            trans[j][i] = res[i][j]
    print('Yes') if any(map(all, (res[0], res[1], res[2], trans[0], trans[1], trans[2], [res[0][0], res[1][1], res[2][2]], [res[0][2], res[1][1], res[2][0]]))) else print('No')


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;


int main(){
    ll N;
    cin >> N;
    ll ans = 0;
    vector<ll> fac(N + 1, 2);
    fac[1] = 1;
    for(ll i = 2; i <= N; i++){
        ll tmp = i;
        while(tmp + i <= N){
            tmp += i;
            fac[tmp]++;
        }
    }
   // rep(i, N)cout << fac[i + 1] << endl;
    rep(i, N) ans += (i + 1) * fac[i + 1];
    cout << ans << endl;
}

Measured memory_bytes: 81372
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <memory>
#include <map>
#include <array>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

template<typename node_type>
class Node{
public:
    explicit Node(vector<node_type> _children,node_type _parent) : children(_children),parent(_parent){};
    ~Node(){};
    vector<node_type> children=NULL;
    node_type parent;
    int depth = -1;
    int condition_num;

    void children_print(){
        if(children.size()==0){
              return;
        }else{
            int n = children.size()-1;
            REP(i,n){
                cout << children[i] << ", ";
            }
            cout << children[n];
        }
    }
};



int main(){
    int n;
    cin >> n;
    map<int, Node<int> > tree;
    
    int tmp,m,tmp_node_key;
    vector<int> tmp_node_children;
    REP(i,n){
        cin >> tmp_node_key;
        
        cin >> m;
        REP(j,m){
            cin >> tmp;

            tmp_node_children.push_back(tmp);

        }
        tree.insert(make_pair(tmp_node_key, Node<int>(tmp_node_children,tmp_node_key)));
        tmp_node_children.clear();
    }
    
    for(auto x:tree){
        for(auto y :x.second.children){

            tree.at(y).parent = x.first;

        }
    }

    for(auto &x:tree){
        tmp = 0;
        tmp_node_key = x.first;
        while(tree.at(tmp_node_key).parent!=tmp_node_key){
            tmp++;
            
            tmp_node_key = tree.at(tmp_node_key).parent;
            
        }

        x.second.depth = tmp;
    }

    for(auto x:tree){
        cout << "node " << x.first << ": parent = "<<((x.second.parent!=x.first) ? x.second.parent : -1);

        cout << ", depth = "<<x.second.depth;
        cout << ", ";

    
        if(x.second.parent==x.first){
            cout << "root";
        }else{

            if(x.second.children.size()==0){
                cout << "leaf";
            }else{
                cout << "internal node";
            }
       }
        cout<< ", [";
        x.second.children_print();
        
        cout <<"]"<<  endl;
    }

    return 0;
}


Measured memory_bytes: 13304
H,W = map(int,input().split())
a = W%3
if a==0:
    s1 = 0
else:
    s1 = H
a = H%3
if a==0:
    s2 = 0
else:
    s2 = W
s3 = H*W
for i in range(1,W):
    a = max(i*H,(H-H//2)*(W-i))
    b = min(i*H,(H//2)*(W-i))
    s3 = min(s3,a-b)
s4 = H*W
for i in range(1,H):
    a = max(i*W,(W-W//2)*(H-i))
    b = min(i*W,(W//2)*(H-i))
    s4 = min(s4,a-b)
print(min(s1,s2,s3,s4))

Measured memory_bytes: 3064
r, l = 0, 0
pr, pl = 0, 0

d = []
S = input()
for i,s in enumerate(S):
    if r!=0 and l!=0 and s=="R":
        d.append((r,l,pr,pl))
        r, l = 1, 0
    elif s=="R":
        r+=1
    elif s=="L" and l==0:
        pl, pr = i, i-1
        l+=1
    else:
        l+=1
if r!=0 and l!=0:
    d.append((r,l,pr,pl))

ans = [0]*len(S)
for r,l,pr,pl in d:
    ans[pl] = r//2 + l - l//2
    ans[pr] = l//2 + r - r//2

print(*ans)

Measured memory_bytes: 13816
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
	public static void main(String[] args) {
		// ??????????????°
		String[] strArry = null;
		String a;
		String sin = "";

		Scanner sc = new Scanner(System.in);		//?????????????????§??\???


		while(sc.hasNext()){
			a = sc.next();		//??\?????????????????????a?????\??????
			int nagasa = a.length();
			if(nagasa > 20){
				break;
			}

			Pattern p = Pattern.compile("[0-9a-zA-Z]+");		//????§???±??°????????£?¨?
			Matcher m = p.matcher(a);

			boolean matchResult = m.matches();
			if(matchResult == false){
				break;
			}

			strArry = a.split("");		//a?????\??£?????????????????????strArray?????\??????

			for(int b = strArry.length-1; 0 <= b ; b--){
				String c =strArry[b];
				sin = sin + c ;
			}
		break;
		}
		System.out.println(sin);
	}
}

Measured memory_bytes: 25724
K, A, B = list(map(int, input().split()))

if A + 2 >= B:
  print(K + 1)
  exit()

if K <= A:
  print(K + 1)
  exit()

K -= A - 1
M = A

if K % 2 == 1:
  K -= 1
  M += 1

M += (B - A) * (K // 2)

print(M)

Measured memory_bytes: 3060
using System;
using System.Linq;

class B
{
	static void Main()
	{
		Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
		var h = read();
		var p = read();
		int n = h[0], k = h[1];

		var smin = Slide(p, k + 1, (x, y) => x <= y);
		var smax = Slide(p, k + 1, (x, y) => x >= y);
		var c = n - k + 1 - Enumerable.Range(0, n - k).Count(i => smin[i] == p[i] && smax[i] == p[i + k]);

		int c2 = 0, t = 0, v = -1;
		for (int i = 0; i < n; i++)
		{
			if (p[i] > v)
			{
				t++;
			}
			else
			{
				if (t >= k) c2++;
				t = 1;
			}
			v = p[i];
		}
		if (t >= k) c2++;
		if (c2 > 0) c -= c2 - 1;

		Console.WriteLine(c);
	}

	static int[] Slide(int[] a, int k, Func<int, int, bool> c)
	{
		var r = new int[a.Length - k + 1];
		var q = new int[a.Length];
		for (int i = 1 - k, j = 0, s = 0, t = -1; j < a.Length; i++, j++)
		{
			while (s <= t && c(a[j], a[q[t]])) t--;
			q[++t] = j;
			if (i < 0) continue;
			r[i] = a[q[s]];
			if (q[s] == i) s++;
		}
		return r;
	}
}


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

//Common
using namespace std;using f64 = double;using i64=long long;using u64=unsigned long long;
template<typename T> using Arr=vector<T>;template<typename T> using Func=function<T>;template<typename T> using Str=basic_string<T>;
#define hfor(v, s, e) for(int v=(s);(s)<=v&&v<(e);++v)//half-opened range
#define hfori(v, s, e) for(int v=(e)-1;(s)<=v&&v<(e);--v)//inversion
#define hforo(v, s, e) int v=(s);for(;(s)<=v&&v<(e);++v)//out declaration
#define hforoi(v, s, e) int v=(e)-1; for(;(s)<=v&&v<(e);--v)
#define cfor(v, s, e) hfor(v,(s),(e)+1)//closed range
#define cfori(v, s, e) hfori(v,(s),(e)+1)
#define cforo(v, s, e) hforo(v,(s),(e)+1)
#define cforoi(v, s, e) hforoi(v,(s),(e)+1)
#define rep(v,x) hfor(v,0,(x))
#define repi(v,x) hfori(v,0,(x))
#define repo(v,x) hforo(v,0,(x))
#define all(x) (x).begin(),(x).end()
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define cxp constexpr
#define PQMIN(...) std::priority_queue<__VA_ARGS__,Arr<__VA_ARGS__>,greater<__VA_ARGS__>>
template<class... A>
auto ARR(auto n, A&&...a){
	if constexpr(sizeof...(a)==0) return n;
	else return vector(n,ARR(a...));
}

//Math
template<typename T> cxp T inf() { return numeric_limits<T>::max() / 2; }
template<typename T> inline T sq(T x){return x*x;}
cxp int lgc(int x){return 64-__builtin_clzll(x-1);}
cxp int lgf(int x){return 63-__builtin_clzll(x);}
int rd(int lb, int ub){static mt19937 rng(time(0)^i64(new int)); return uniform_int_distribution<int>(lb, ub-1)(rng);}
int rd(int ub=inf<int>()){return rd(0,ub);}
const f64 pi=acosl(-1), eps=1e-10;

//IO
template<typename T>ostream& operator<<(ostream& s, const Arr<T>& a) {for(auto i:a) cout<<i<<' '; return s;}
auto cinint(){i64 x;cin>>x;return x;}
auto cinchr(){char x;cin>>x;return x;}
auto cinints(int n){Arr<i64> a(n);for(auto&i:a)cin>>i;return a;}
#ifndef DEBUG
	//#pragma GCC optimize ("Ofast") //somtimes it become more slower
	auto __PRE_RUN__=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),(cout<<fixed<<setprecision(11)), 0);
#endif

//Misc
int sz(const auto& x){return x.size();}
auto split(auto s, auto p){
	Arr<decltype(s)> ret;
	auto it1=s.begin();
	for(auto it2=it1; (it2 = find(it1,s.end(),p)) != s.end(); it1=it2+1)
		ret.pushb({it1, it2});
	ret.pushb({it1,s.end()});
	return ret;
}
template<typename T> T rev(const T& a){return {a.rbegin(),a.rend()};}
Arr<int> range(int n){ Arr<int> ret(n); rep(i,n)ret[i]=i; return ret; }
struct defer{ defer(auto f):f(f){} ~defer(){f();} function<void()> f; };
#define defer(x) auto _##__COUNTER__ = defer([&](){x;});
#define lam(expr, ...) [&](__VA_ARGS__){return expr;}
#define reduce accumulate

#define endl '\n'//not interactive?
#define int i64//MLE?
using pint = pair<int,int>;
using tint = tuple<int,int,int>;

signed main(){
	int n; cin>>n;
	cout<<1000*(n/1000+!!(n%1000))-n<<endl;
	return 0;
}



Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
using ll=long long;

const ll INF = pow(10,18)+1;

#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

template<typename T> bool chmin(T& a, T b) {return a > b ? a = b, true : false;}
template<typename T> bool chmax(T& a, T b) {return a < b ? a = b, true : false;}
 
int main(){
    string S;
    cin >> S;
    int zero = 0;
    int one = 0;
    REP(i,S.length()){
        if(S[i]=='0') zero++;
        if(S[i]=='1') one++;
    }
    cout << 2*min(zero,one) << endl;
    return 0;
}

Measured memory_bytes: 512
n = int(input())
a = list(map(int, input().split()))
count = 0
flag = True

while flag:
    flag = False
    for j in range(n - 1, 0, -1):
        if a[j] < a[j - 1]:
            a[j], a[j - 1] = a[j - 1], a[j]
            count += 1
            flag = True

print(*a)
print(count)

Measured memory_bytes: 6724
#include <bits/stdc++.h>
#define REP(i, N) for (int i = 0; i < (N); ++i)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

//++時計回り --反時計回り
// int dx[4] = {1, 0, -1, 0};
// int dy[4] = {0, 1, 0, -1};

int main() {
  ll N;
  cin >> N;
  cout << N*(N-1)/2 << '\n';
}


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

using namespace std;
typedef long long ll;
const long long mod = 1e9 + 7;

int main() {
  ll n, ans = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    ans = (ans * i) % mod;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
mod=10**9+7
ctx=0;cty=0
for i in range(n):
  ctx+=(2*i-n+1)*x[i]
  ctx%=mod
for i in range(m):
  cty+=(2*i-m+1)*y[i]
  cty%=mod
print((ctx*cty)%mod)

Measured memory_bytes: 18576
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <climits>
#include <math.h>
#include <memory.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, k, n) for(int i = (k); i < (int)(n); i++)
using namespace std;
using ll = long long;
int N, M;
int cnt = 0;
int ans = 0;
int main(){
    cin >> N;
    int A[N];
    rep(i, N) cin >> A[i];
    rep(i, N){
        if(i == 0)
            ans += abs(A[i]);
        else
            ans += abs(A[i] - A[i - 1]);
    }
    ans += abs(A[N - 1]);
    rep(i, N){
        int tmp = ans;
        if(i == 0){
            ans -= abs(A[i]) + abs(A[i + 1] - A[i]);
            ans += abs(A[i + 1]);
        }
        else if(i != N - 1){
            ans -= abs(A[i] - A[i - 1]) + abs(A[i + 1] - A[i]);
            ans += abs(A[i + 1] - A[i - 1]);
        }
        else{
            ans -= abs(A[i] - A[i - 1]) + abs(A[i]);
            ans += abs(A[i - 1]);
        }
        cout << ans << endl;
        ans = tmp;
    }
    return 0;
}

Measured memory_bytes: 1664
N = int(input())
h_list = list(map(int, input().split()))
dp = [0,abs(h_list[1]-h_list[0])]
for i in range(1,N-1):
    step_1 = dp[i]+abs(h_list[i+1]-h_list[i])
    step_2 = dp[i-1]+abs(h_list[i+1]-h_list[i-1])
    dp_ans = min(step_1,step_2)
    dp.append(dp_ans)
print(dp[-1])


Measured memory_bytes: 13980
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n,y;
	cin>>n>>y;
	for(int i=0; i<=n; i++)
		for(int j=0; j<=n-i; j++)
			if(i*10000+j*5000+(n-i-j)*1000==y)
				cout<<i<<' '<<j<<' '<<n-i-j<<'\n',exit(0);
	cout<<"-1 -1 -1"<<endl;
	return 0;
}

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

int main(void){
    int n,a,b,c;
    scanf("%d",&n);
    a = n%10;
    b = n/10 - (n/100)*10;
    c = n/100;
    if(a == 7 || b == 7 || c == 7){
        printf("Yes");
    }
    else{
        printf("No");
    }
    return 0;
}

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

int main(void) {
  int n, y;
  cin >> n >> y;

  int a=-1,b=-1,c=-1;
  
  int i, j, k;
  for(i=0;i<=n;i++) {
    for(j=0;j<=n-i;j++) {
      k = n - i - j;
      if(10000*i + 5000*j + 1000*k == y) {
        a = i;
        b = j;
        c = k;
      }
    }
  }
  cout << a << " " << b << " " << c << endl;
}

Measured memory_bytes: 256
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define U(v) cerr << #v << ": " << (v) << endl

int main() {
    int K;
    cin >> K;
    vector<int> a(K);
    for (int& i : a) cin >> i;
    reverse(a.begin(), a.end());
    if (a[0] != 2) {
        cout << -1 << endl;
        return 0;
    }
    long long beg = 2;
    long long end = 4;
    for (int i = 1; i < K; ++i) {
        long long p = beg;
        if (beg % a[i])
            p = beg + a[i] - beg % a[i];
        long long q = end;
        if (end % a[i])
            q = end + a[i] - end % a[i];
        if (p < end) {
            beg = p;
            end = q;
        } else {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << beg << ' ' << end - 1 << endl;
    return 0;
}


Measured memory_bytes: 640
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

// CHECK THE LIMITS
typedef long long ll;

const int MOD = 1000000007;
const ll INFLL = 1e18;
const int INF = 1e9;
const int NMAX = 1000001;

int gcd(int a, int b) {
  return b ? gcd(b, a%b) : a;
} 

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n , k;
    cin >> n >> k;
    vector<int> dp(n,INF);
    vector<int> h(n);

    for(int i =0; i < n; ++i)
    {
        cin >> h[i];
    }
    dp[0] = 0;
    for(int i = 0; i< n; ++i)
    {
        for(int j = 1; j<= k && i + j < n; ++j)
        {
            dp[i+j] = min(dp[i+j],dp[i] +  abs(h[i+j] - h[i]));
        }
    }
    cout << dp[n-1] << '\n';


    return 0;
}

Measured memory_bytes: 1024