akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    int one=0,four=0;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        if(a%4==0) four++;
        if(a%2==1) one++;
    }
    if(one<=four || four>=n/2) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3632
// https://beta.atcoder.jp/contests/abc104

#define SUBMIT

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <cmath>
#include <unordered_map>
#include <map>

using namespace std;
using ui64 = unsigned long long;
using i64 = long long;


int main() {
#ifdef SUBMIT
    int D, G;
    cin >> D >> G;
    vector<int> p(D), c(D);
    for (int i = 0; i < D; ++i) {
        cin >> p[i] >> c[i];
    }
#else
//    int D = 2, G = 2000;
//    vector<int> p {3, 5};
//    vector<int> c {500, 800};

    int D = 5, G = 25000;
    vector<int> p {20, 40, 50, 30, 1};
    vector<int> c {1000, 1000, 1000, 1000, 1000};
#endif

    ui64 ans = 1 << 29;
    for (int bit = 0; bit < (1 << D); ++bit) {
        ui64 n_solved = 0;
        ui64 sum_score = 0;
        // bit 全探索
        // 全完する組み合わせ
        for (int i = 0; i < D; ++i) {
            if (bit & (1 << i)) {
                sum_score += (i + 1) * 100 * p[i] + c[i];
                n_solved += p[i];
            }
        }

        if (G <= sum_score) {
            ans = min(ans, n_solved);
        } else {
            // scoreが高い問題から解いていく
            for (int i = D - 1; i >= 0; i--) {
                if (bit & (1 << i)) continue;

                // 1問解く度にスコアがG以上になっていないか確認しながら繰り返す
                for (int j = 0; j < p[i]; ++j) {
                    if (G <= sum_score) break;

                    // solve 1 problem
                    sum_score += (i + 1) * 100;
                    n_solved++;
                }
            }

            ans = min(ans, n_solved);
        }
    }

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

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
using namespace std;
#define vel vector<long long>
#define vvel vector<vel>
#define int long long
#define rep(i,n) for(long long i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define mmax(a,b) a=max(a,b)
#define mmin(a,b) a=min(a,b)
#define mkp make_pair
#define pin pair<int,int>
#define V vector
long long p = 1000000007;
vel kai(200001, 1);
vel ink(200001, 1);
int le = (1 << 20) + 1;
vel BIT(le, 0);
vel uni(vel &list) {
	if (list.size() == 0) { return list; }
	sort(list.begin(), list.end());
	vel ql(1, list[0]);
	rep(i, list.size() - 1) {
		if (list[i] != list[i + 1]) { ql.push_back(list[i + 1]); }
	}
	list = ql;
	return ql;
}
int ru(int a, int r) {
	if (r == 0) { return 1; }
	int ans = ru(a, r / 2);
	ans *= ans; ans %= p;
	if (r % 2 == 1) { ans *= a; }
	return ans % p;
}
int inv(int a) {
	return ru(a, p - 2);
}
void make_kai() {
	rep(i, 200000) { kai[i + 1] = (kai[i] * (i + 1)) % p; }
	rep(i, 200001) { ink[i] = inv(kai[i]); }
}
int com(int n, int r) {
	int ans = kai[n] * ink[r];
	ans %= p; ans *= ink[n - r]; ans %= p;
	return ans;
}
int per(int n, int r) {
	int ans = kai[n] * ink[n - r];
	ans %= p;
	return ans;
}
signed main() {
	int n, m; cin >> n >> m;
	vvel s(m);
	rep(i, m) {
		int k; cin >> k;
		rep(j, k) { int qs; cin >> qs; qs--; s[i].push_back(qs); }
	}
	vel p(m);
	rep(i, m) { cin >> p[i]; }
	int ans = 0;
	rep(in, 1 << n) {
		vel cnt(m,0);
		rep(i, m) {
			rep(j, s[i].size()) {
				int qans = (in/(1<<s[i][j]))%2;
				cnt[i] += qans;
			}
		}
		int pl = 1;
		rep(i, m) {
			if (cnt[i]%2 != p[i]) { pl = 0; }
		}
		ans += pl;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 11572
/* おまじない　*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD=pow(10,9)+7;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}


int main(){
    init();

    ll N,A,B;cin>>N>>A>>B;
    cout<<min(A*N,B)<<endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func square (num float64) float64{
	return num * num
}

func main() {
	var n,d int
	fmt.Scan(&n,&d)
	
	points := make([][]float64,n)
	for i := range points {
		points[i] = make([]float64,d)
	}
	
	for r := 0; r < n; r++ {
		for c := 0; c < d; c++ {
			fmt.Scan(&points[r][c])
		}
	}
	
	cnt := 0
	for i := 0; i < n-1; i++ {
		for j := i+1; j < n; j++ {
			distance := 0.0
			for c := 0; c < d; c++ {
              distance += square(math.Abs(points[i][c]-points[j][c]))
			}
			if math.Sqrt(distance) == math.Floor(math.Sqrt(distance)) {
				cnt++
			}
		}
	}
	fmt.Println(cnt)
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007

ll now = 0,ans = 0, n;
map<ll,ll> m;
int main() {
	m[0] = 1;
	cin >> n;
	REP(i, n) {
		ll a;
		cin >> a;
		now += a;
		m[now]++;
		ans += m[now] - 1;
	}
	cout << ans << endl;
}



Measured memory_bytes: 12800
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  int N;
  std::cin >> N;
  vvi A = vv(N, 2, 0, int);
  set<int> num;
  std::vector<int> ans(N*N+1, 0);
  for(int i=0;i<N;i++) A[i][1]=i+1,std::cin >> A[i][0];
  sort(A.begin(), A.end());
  for(int i=1;i<=N*N;i++) num.insert(i);
  for(int i=0;i<N;i++) num.erase(A[i][0]), ans[A[i][0]]=A[i][1];
  for(int i=0;i<N;i++){
    for(int j=0;j<A[i][1]-1;j++){
      auto itr = num.begin();
      if(*itr>A[i][0]){
        std::cout << "No" << '\n';
        return 0;
      }
      ans[*itr] = A[i][1];
      num.erase(itr);
    }
  }
  for(int i=N-1;i>=0;i--){
    for(int j=0;j<N-A[i][1];j++){
      auto itr = num.end();
      itr--;
      if(*itr<A[i][0]){
        std::cout << "No" << '\n';
        return 0;
      }
      ans[*itr]=A[i][1];
      num.erase(*itr);
    }
  }
  std::cout << "Yes" << '\n';
  for(int i=1;i<=N*N;i++) std::cout << ans[i] << (i==N*N?"\n":" ");
  return 0;
}


Measured memory_bytes: 13952
#include<stdio.h>
int main(){
  int unused __attribute__((unused));
  int A, B, X;
  unused = scanf("%d %d %d", &A, &B, &X);

  if(X < A) printf("NO");
  else if(X >= A && X-A <= B) printf("YES");
  else printf("NO"); 
  return 0;
}

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


// 3 2 6 1
// 12
int main(){
int N;
cin >> N;
int sum = 0;
int a_a = 0;
vector<int>A(N + 2);
A.at(0) = 0;
for(int i = 1; i <= N; i++){ 
 cin >> A.at(i);
 sum += abs(A.at(i - 1) - A.at(i));
}
A.at(N + 1) = 0;
sum += abs(A.at(N) - A.at(N + 1));
// cout << sum << endl; 
// cout << A.at(0) << endl;
// cout << A.at(1) << endl;
// cout << A.at(2) << endl;
for(int i = 1; i <= N; i++){ 
     int ans;
     ans = sum - ((abs(A.at(i - 1) - A.at(i)) + abs(A.at(i) - A.at(i + 1))) - abs(A.at(i - 1) - A.at(i + 1))); 

cout << ans << endl; 
}

}

Measured memory_bytes: 1664
import sys
input = sys.stdin.readline
N, D = map(int, input().split())
X = [list(map(int,input().split())) for i in range(N)]

ans = 0

for i in range(N) :
    for j in range(N) :
        if i < j :
            dist = 0
            for w in range(D) :
                dist += (X[i][w] - X[j][w]) ** 2
            dist = dist ** 0.5
            if dist.is_integer() :
                ans += 1

print(ans)


Measured memory_bytes: 3064
from sys import stdin


def main() -> None:
    s = next_str()
    x = set()
    y = set()

    for c in s:
        if c == "N" or c == "S":
            y.add(c)
        if c == "W" or c == "E":
            x.add(c)

    if len(x) % 2 != 0 or len(y) % 2 != 0:
        print("No")
    else:
        print("Yes")


def next_str() -> str:
    result = ""
    while True:
        tmp = stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    lint n;
    cin >> n;
    vector<lint> a(n);
    lint ts = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        while (a[i] % 2 == 0) {
            ts++;
            a[i] /= 2;
        }
    }
    cout << ts << "\n";
    return 0;
}

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

int main(void){

   unsigned long long int a,b,x;
   cin >> a >> b >> x;
   if(a % x == 0) cout << (b / x) - (a / x) + 1 << endl;
   else cout << (b / x) - (a / x) << endl;
}


Measured memory_bytes: 3520
p['   '];t['   '];n,x,k,j;main(i){for(;i++<1e6;)for(x=i;x<1e6;p[x+=i]=1);for(;*t=scanf("%d%d",&n,&x),n;memset(t,!printf(x<2?"NA\n":"%d\n",x),4e6)){for(;n--;)for(i=-scanf("%d",&k);++i<x;)t[i]&&++t[i+k];for(;p[x]|!t[x];x--);}}

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

int main()
{
  int r,g,b;
  int n;  

  cin >> r >> g >> b;

  n=r*100+g*10+b;

  if(n%4==0){
  cout << "YES" << endl;
  }else{
  cout << "NO" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long int power(long long int x,long long int y) 
{ 
    long long int res = 1;     // Initialize result 
  // x=x;
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x); 
   
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x);  // Change x to x^2 
    } 
    return res; 
}
long long int power(long long int x,long long int y,long long int m) 
{ 
    long long int res = 1;     // Initialize result 
   x=x%m;
    while (y > 0) 
    { 
        // If y is odd, multiply x with result 
        if (y & 1) 
            res = (res*x)%m; 
   
        // y must be even now 
        y = y>>1; // y = y/2 
        x = (x*x)%m;  // Change x to x^2 
    } 
    return res; 
}

long long int gcd(long long int a, long long int b){ 
    if (a == 0) 
        return b;  
    return gcd(b % a, a);  
 } 
 long long int lcm(long long int a, long long int b)  
 { 
     long long int temp;
    
    return (a*b)/gcd(a, b);  
 }
 
int main() {
        long long int t=0;
        string c;
        string s;
       long long int n,m,o=0,l,d=0,i,j,p=0,k,f;
       double pie=3.141592653589793238;
    long long int MOD=1000000007;
    cin>>n>>k;
    long long int a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
     //   p=p+a[i];
       // b[a[i]-1]=i;
    }
    sort(a,a+n);
    for(i=0;i<n;i++)
    {
        if((n-i-1)>=k)
        p=p+a[i];
        else
        break;
    }
    cout<<p;
 return 0;
}

Measured memory_bytes: 1792
A,B=map(int,input().split())
g=[['.']*100 for i in range(25)]+[['#']*100 for i in range(25)]
i,j=1,0
for x in range(B-1):
    g[i][j]='#'
    if j<98:
        j+=2
    else:
        i,j=i+2,0
i,j=26,0
for x in range(A-1):
    g[i][j]='.'
    if j<98:
        j+=2
    else:
        i,j=i+2,0
print(50,100)
print(*[''.join(g[l]) for l in range(50)],sep='\n')

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

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define ALL(v) (v.begin(),v.end())
#define COUT(x) cout<<(x)<<endl

int main(){
    int n;
    cin >> n;
    int a[n];
    int ans = 0;
    REP(i,n){
        cin >> a[i];
        ans += a[i];
    }
    int min1 = INF,index=0;
    REP(i,n){
        if(min1>abs(a[i]*n-ans)){
            min1 = abs(a[i]*n-ans);
            index = i;
        }
    }
    COUT(index);
    return 0;
} 

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();

        final int[][] count = new int[n][26];
        for (int i = 0; i < n; i++) {
            for (final char c : scanner.next().toCharArray()) {
                count[i][c - 'a']++;
            }
        }

        final int[] array = new int[26];
        for (int i = 0; i < 26; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                min = Math.min(min, count[j][i]);
            }
            array[i] = min;
        }

        final StringBuilder builder = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i]; j++) {
                builder.append((char) (i + 'a'));
            }
        }

        System.out.println(builder);
    }
}


Measured memory_bytes: 22608
n,m=map(int,input().split())
x=[];y=[];z=[]
for i in range(n):
  a,b,c=map(int,input().split())
  x.append(a);y.append(b);z.append(c)
mx=0
for i in [-1,1]:
  for j in [-1,1]:
    for k in [-1,1]:
      s=[]
      for l in range(n):
        s.append(i*x[l]+j*y[l]+k*z[l])
      s.sort()
      s.reverse()
      d=abs(sum(s[0:m]))
      if d>mx:
        mx=d
print(mx)
  

Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#define rep(i, n) for(long long i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const int N = 50;

int main() {
    ll k;
    cin >> k;

    vector<ll> ans(N);
    rep(i, N) {
        ans[i] = k/N + N -1;
    }

    rep(i, k%N) {
        ans[i] += N;
        rep(j, N) {
            if(i != j) {
                ans[j]--;
            }
        }
    }

    cout << N << "\n";
    rep(i, N) {
        cout << ans[i] << " ";
    }

    cout << endl;
    return 0;
}

Measured memory_bytes: 256
H,W=map(int,input().split())

co=[]
c=[0]*10
for i in range(10):
   temp=list(map(int,input().split()))
   co.append(temp)


for k in range(10):
    for i in range(10):
        for j in range(10):
            temp=[]
            if co[i][j] > co[i][k] + co[k][j]:
                co[i][j] = co[i][k] + co[k][j]

for i in range(10):
    c[i]=co[i][1]


ans=0
for i in range(H):
    A=list(map(int,input().split()))
    for j in range(W):
        if A[j]!=-1 and A[j]!=1:
            ans+=c[A[j]]
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <string>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける
using vl = vector<ll>;  // long longの1次元の型に vl という別名をつける
using vvl = vector<vl>; // long longの2次元の型に vvl という別名をつける
int MOD = 1000000007; //10^9 + 7

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

// 無限大の値
const ll  lINF = 1LL << 60;
const int iINF = 1 << 29;

int main(void){
  int n,a;
  cin  >> n >> a;
  cout << n*n-a << endl;
  return 0;
} 

Measured memory_bytes: 3628
while gets do
  $_.to_i.times do
    l = gets
    line = l
    a,b = 1,1
    while line !~ /th(at|is)/
      line = l.unpack("C*").map{|n|
        n = (n >= 97 and n <= 122) ? (a*n+b)%26+97 : n
      }.pack("C*")
      b=(b+1)%26
      if b==0
        begin
          a+=1
        end while a.gcd(26) != 1
      end
    end
    puts line
  end
end

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






int main() {
    int n;
    cin>>n;
    vector<ll> l(n);
    vector<ll> r(n);
    map<int,int>mp;
    ll ans=0;
    rep(i,n){
        int a;
        cin>> a;
        ans += mp[i-a];
        mp[i+a]++;
    }
    cout << ans << endl;
    return 0;
}


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

int cnt = 0;
int A[1000005];

void show(int A[], int n, int i, int j) {
    for (int i = 0; i < n; i++) {
        if (i)
            cout << " ";
        cout << A[i];
    }
    printf(" swap(%d, %d) cnt=%d", i, j, cnt);
    cout << endl;
}
void insertionSort(int A[], int n, int g) {
    for (int i = g; i < n; i++) {
        int j = i - g;
        for (; j >= 0; j -= g) {
            if (A[j] <= A[j + g])
                break;
            swap(A[j], A[j + g]);
            cnt++;
            // show(A, n, j, j + g);
        }
    }
}

void shellSort(int A[], int n) {
    int m = 0;
    int h = 0;
    while (h <= n / 9)
        h = 3 * h + 1;
    vector<int> G;
    for (; h > 0; h /= 3) {
        m++;
        G.push_back(h);
        insertionSort(A, n, h);
    }
    cout << m << endl;
    for (int i = 0; i < m; i++) {
        if (i)
            cout << " ";
        cout << G[i];
    }
    cout << endl;
    cout << cnt << endl;
    for (int i = 0; i < n; i++) {
        cout << A[i] << endl;
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }

    // for (int i = 0; i < n; i++) {
    //     if (i)
    //         cout << " ";
    //     cout << A[i];
    // }
    // cout << endl;

    shellSort(A, n);
}


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

using namespace std;

int main(){
  long long int N;
  long long int CAP[5];

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

  long long int min = CAP[0];
  for(int i = 1; i < 5; i++)
    if(min > CAP[i]) min = CAP[i];

  long long int adtime = (N-1)/min;

  cout << 5 + adtime << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>



int main(void)
{
	int a[2000], b[2000];
	int i = 0, j;
	int n = 9;
	int count = 1;
	
	while (scanf("%d %d", &a[i], &b[i]) != EOF){
		a[i] += b[i];
		i++;
	}
	for (j = 0; j < i; j++){
		while (1){
			if (a[j] > n){
				count++;
				n *= 10;
				n += 9;
			}
			else {
				b[j] =count;
				count = 1;
				n = 9;
				break;
			}
		}
	}
	
	for (j = 0; j < i; j++){
		printf("%d\n", b[j]);
	}
	
	return (0);
}

Measured memory_bytes: 608
n,m=map(int,input().split())
c=list()

for i in range(m):
    c.append(list(map(int,input().split())))

s=(list(map(lambda x:x[0],c)))
b=(list(map(lambda x:x[1],c)))

maxs=max(s)
minb=min(b)

if minb<maxs:
    print('0')
else:
    ans=minb-maxs+1
    print(ans)

Measured memory_bytes: 28552
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int d = sc.nextInt();
		int x = sc.nextInt();
		int a[] = new int[n];
		for(int i=0; i<n;i++){
			a[i] = sc.nextInt();
		}	
		int num = x;
		for(int i=0; i<n; i++){
			num += 1+(d-1)/a[i];
		}
		System.out.print(num);
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;

int n,lake[MAXN];
int dp[MAXN];

int solve(int k){
    if(k==n-1)return 0;
    if(dp[k]>=0)return dp[k];

    int um=abs(lake[k]-lake[k+1])+solve(k+1);
    if(k+2<n){
        return dp[k]=min(abs(lake[k]-lake[k+2])+solve(k+2),um);
    }
     return dp[k]=um;
    }

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp,-1,sizeof(dp));
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>lake[i];
    }

    cout<<solve(0);
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
ll K;
int main(){
	cin >> K;
	ll rem = K%50ll;
	ll a = K/50ll;
	vector<ll> ans;
	for(int i=0;i<50-rem;i++){
		ans.pb(49ll-rem);
	}
	for(int i=rem-1;i>=0;i--){
		ans.pb(50ll-i);
	}
	for(int i=0;i<ans.size();i++){
		ans[i]+=a;
	}
	cout << 50 << endl;
	for(int i=0;i<ans.size();i++){
		printf("%lld",ans[i]);
		if(i==ans.size()-1)printf("\n");
		else printf(" ");
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	char x=0,y=0;
	int i,flag=1;
	for(i=0;i<4;i++)
	{
		if(i!=0)
		{
			y=x;
		}
		scanf("%c",&x);
		if(y==x)flag=0;
	}
	if(flag)printf("Good");
	else printf("Bad");
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int r, c, a[101][101] = { {} };
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            a[i][c] += a[i][j];
        }
    }
    for (int j = 0; j < c + 1; j++) {
        for (int i = 0; i < r; i++) {
            a[r][j] += a[i][j];
        }
    }
    for (int i = 0;i < r + 1;i++) {
        for (int j = 0; j < c ; j++) {
            cout << a[i][j] << " ";
        }
        cout <<a[i][c]<< endl;
    }
}


Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
const int INF = 2e9;

int main() {
  int n, m;
  cin >> n >> m;
  int h[n];
  rep(i,n) cin >> h[i];
  int a[m][2], b[m][2];
  rep(i,m) {
    cin >> a[i][0] >> a[i][1];
    b[i][0]=a[i][0];
    b[i][1]=a[i][1];
  }
  reverse(b,b+n);
  bool t[n];
  rep(i,n) t[i]=true;
  rep(i,m) {
    if(h[a[i][0]-1]<h[a[i][1]-1]) t[a[i][0]-1]=false;
    else if(h[a[i][0]-1]==h[a[i][1]-1]) {
      t[a[i][0]-1]=false;
      t[a[i][1]-1]=false;
    }
      else t[a[i][1]-1]=false;
  }

  int ans=0;
  rep(i,n) {
    if(t[i]==true) ans++;
  }
  cout << ans << endl;
}

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

#ifdef LOCAL
#include "../debug.h"
#else
#define debug(x...) 141
#endif
#define forn(i,x,n) for(int i = x; i < n; ++i)
#define forit(it, m) for(auto it = m.begin(); it!=m.end(); ++it)
typedef long long ll;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n,ans=0;

    cin>>n;
    vector<int> a(n);
    forn(i,0,n)
    	cin>>a[i];
    sort(a.rbegin(),a.rend());
    forn(i,0,n-1){
    	ans+=a[(i+1)/2];
    }
    cout<<ans<<'\n';
    
    return 0;
}

Measured memory_bytes: 3988
#include<stdio.h>
#define ck 26
#include<sys/time.h>

unsigned long long seed;

unsigned long long xorshift(){
  seed=seed^(seed<<13);
  seed=seed^(seed>>7);
  seed=seed^(seed<<17);
  return seed;
}

int d;
int c[32];
int s[512][32];
int res[512];

int eval(){
  int i,j,lc[32],r=0;
  for(i=1;i<=ck;i++){lc[i]=-1;}
  for(i=0;i<d;i++){
    r+=s[i][res[i]];
    lc[res[i]]=i;
    for(j=1;j<=ck;j++){
      r-=c[j]*(i-lc[j]);
    }
  }
  return r;
}

int sum(int x){
  return (x*(x+1))/2;
}

int delq(int tg,int x){
  int r,i;
  int bfb=-1,bff=d,afb=-1,aff=d;
  r=s[tg][x]-s[tg][res[tg]];

  for(i=tg-1;i>=0;i--){
    if(res[i]==res[tg]){bfb=i;break;}
  }
  for(i=tg+1;i<d;i++){
    if(res[i]==res[tg]){bff=i;break;}
  }

  for(i=tg-1;i>=0;i--){
    if(res[i]==x){afb=i;break;}
  }
  for(i=tg+1;i<d;i++){
    if(res[i]==x){aff=i;break;}
  }
  
  r+=c[res[tg]]*sum((tg-bfb)-1);
  r+=c[res[tg]]*sum((bff-tg)-1);
  r-=c[res[tg]]*sum((bff-bfb)-1);

  r-=c[x]*sum((tg-afb)-1);
  r-=c[x]*sum((aff-tg)-1);
  r+=c[x]*sum((aff-afb)-1);
  return r;
}

int main(){
  long long stt,nt;
  struct timeval tv;
  gettimeofday(&tv, NULL);
  seed=(tv.tv_sec*1000000+tv.tv_usec);
  stt=seed;
  int i,j,q,r,tg,x;
  scanf("%d",&d);
  for(i=1;i<=ck;i++){scanf("%d",&c[i]);}
  for(i=0;i<d;i++){
    for(j=1;j<=ck;j++){
      scanf("%d",&s[i][j]);
    }
  }
  for(i=0;i<d;i++){
    res[i]=(i%ck)+1;
  }
  r=eval();
  q=0;
  while(1){
    tg=(xorshift()%d);
    for(i=1;i<=ck;i++){
      if(delq(tg,i)>=0){res[tg]=i;}
    }
    q++;
    if(q==d){
      q=0;
      gettimeofday(&tv, NULL);
      nt=(tv.tv_sec*1000000+tv.tv_usec);
      if((nt-stt)>=1900000){break;}
    }
  }
  for(tg=0;tg<d;tg++){
    for(i=1;i<=ck;i++){
      if(delq(tg,i)>=0){res[tg]=i;}
    }
  }
  for(i=0;i<d;i++){
    printf("%d\n",res[i]);
  }
  return 0;
}


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

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<vector<int>> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define umap unordered_map

const int MOD = 1e9 + 7;

int madd(int a, int b){
	a += b;
	if (a >= MOD) a -= MOD;
	return a;
}

int msub(int a, int b){
	a -= b;
	if (a < 0) a += MOD;
	return a;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n, k; cin >> n >> k;
	vi A = vi();
	rep(i, n){
		int x; cin >> x;
		A.pb(x);
	}
	vvll dp = vvll(n, vll(k + 1, 0));
	for(int c = 0; c <= A[0]; c++){
		dp[0][c] = 1;
	}
	vll P = vll(k + 1, 0);
	P[0] = dp[0][0]; P[0] %= MOD;
	for(int c = 1; c <= k; c++){
		P[c] = madd(dp[0][c], P[c-1]);
	}
	for(int r = 1; r < n; r++){
		vll NP = vll(k + 1, 0);
		for(int c = 0; c <= k; c++){
			int cutoff = c - A[r] - 1;	
			dp[r][c] = msub(P[c], (cutoff >= 0 ? P[cutoff] : 0));
		}
		for(int c = 0; c <= k; c++){
			NP[c] = madd(dp[r][c], (c > 0 ? NP[c-1] : 0));
		}
		P = NP; // haha....
	}
	cout << dp[n-1][k] % MOD;
}

Measured memory_bytes: 82972
a, b, c = map(int, input().split())
d = list(map(int, input().split()))
z = 0
for i in range(a):
    e = 0
    f = list(map(int, input().split()))
    for j in range(b):
        e += d[j] * f[j]
    if e + c > 0:
        z += 1
print(z)


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] d = new int[n];
		for(int i = 0; i < n; i++) {
			d[i] = scan.nextInt();
		}

		long ans = 0;
		for(int i = 0; i < n - 1; i++) {
			for(int j = i + 1; j < n; j++) {
				ans += d[i] * d[j];
			}
		}
		System.out.println(ans);
	}
}


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;
#define MAXH 10
int h;
int result=0;
vector<vector<int>>b(MAXH, vector<int>(5));

void initb(){
  rep(i, MAXH)rep(j, 5)b[i][j]=0;
  result=0;
}

void banish(int h){
  if(b[h][0]==b[h][1] && b[h][0]==b[h][2] && b[h][0]==b[h][3] && b[h][0]==b[h][4]){
    result+=5*b[h][0];
    rep(i, 5)b[h][i]=0;
    return;
  }

  rep(i, 2){
    if(b[h][i]==b[h][i+1] && b[h][i]==b[h][i+2] && b[h][i]==b[h][i+3]){
      result+=4*b[h][i];
      rep(j, 4)b[h][j+i]=0;
      return;
    }
  }

  rep(i, 3){
    if(b[h][i]==b[h][i+1] && b[h][i]==b[h][i+2]){
      result+=3*b[h][i];
      rep(j, 3)b[h][j+i]=0;
      return;
    }
  }
}

void fall(){
  rep(i, 5)rep(j, h){
    if(b[j][i]>0)continue;

    rep(k, h)for(int k=j; k<h-1; k++)if(b[k][i]==0)swap(b[k][i], b[k+1][i]);
  }
}

int solve(){
  initb();

  rrep(i, h)rep(j, 5)cin>>b[i][j];

  rep(j, h){
    rep(i, h)banish(i);
    fall();
  }

  return result;
}

int main(){
  while(cin>>h){
    if(h==0)break;

    cout<<solve()<<endl;
  }

  return 0;
}



Measured memory_bytes: 3132
#include <bits/stdc++.h>
#define int long long int
#define ldouble long double
#define vin vector<int> 
#define rep(i,a,n) for(i=(a);i<(n);i++)
#define INF (int)1000000007

//setprecision()<<

using namespace std;

void fin(int i,int n,vin &a){
    rep(i,0,n){
        cin>>a.at(i);
    } 
} 

int gcm(int a,int b){ //a<b
    int amari=INF,syou;
    while(amari!=0){
        amari=a%b;
        a=b;
        b=amari;
    }
    return a;
}

signed main() {
    int i;
    int A,B;
    cin>>A>>B;
    int g=gcm(max(A,B),min(A,B));
    //cout<<"g "<<g<<endl;
    vin soin(0);
    i=2;
    while(i<=sqrt(g) && g>1){
        if(g%i==0){
            soin.push_back(i);
            g/=i;
            while(g%i==0){
                g/=i;
            }
        }
        i++;
    }
    if(g>1){
        soin.push_back(g);
    }
    cout<<1+soin.size()<<endl;
return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<vector>
#include<cmath>
#include<algorithm>
#define rep(i, a, b) for(int i=a; i<b; i++)
#define rrep(i, a, b) for(int i=b-1; i>=a; i--)
#define REP(i, n) for(int i=0; i<n; i++)
#define rREP(i, n) for(int i=n-1; i>=0; i--)
#define MAX 101
typedef long long ll;
using namespace std;

int main(void){
  int n;  cin>>n;
  int u[MAX] = {0}, d[MAX] = {0};
  int sumU[MAX+1] = {0}, sumD[MAX+1] = {0};
  vector<int> ans;
  rep(i, 1, n+1)  cin >> u[i];
  rep(i, 1, n+1)  cin >> d[i];
  rep(i, 1, n+1)  {
    sumU[i] = sumU[i-1] + u[i];
    sumD[n-i+1] = sumD[n-i+2] + d[n-i+1];
  }
  rep(i, 1, n+1)  ans.push_back(sumU[i] + sumD[i]);
  sort(ans.begin(), ans.end());
  cout << ans.back() << endl;
  return 0;
}

Measured memory_bytes: 256
import numpy as np
n = int(input())
x = list(map(int, input().split()))


x_sum = sum(x)
# center = int((max_x + min_x)/2)
center = round(x_sum /n)
result = 0
for x_i in x:
    result += (x_i - center)*(x_i - center)

print(result)

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

using namespace std;

int main(){
  int a; cin >> a;
  int b; cin >> b;
  int ans = 0;
  
  ans = a - (b * 2);
  if( ans < 0) ans = 0;

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int a[3];
  REP(i, 3) cin >> a[i];
  sort(a, a + 3);
  int f = 0;
  int dif = (a[2] - a[1]) + (a[2] - a[0]);
  if(dif % 2 == 1) {
    a[2] += 1;
    a[1] += 1;
    dif = (a[2] - a[1]) + (a[2] - a[0]);
    f = 1;
  }
  cout << dif / 2 + f << endl;
  return 0;
}


Measured memory_bytes: 256
G=p,p,p,%w(a.. a.. .bb),%w(aabc ddbc efgg efhh),%w(abbcc ad..e fd..e f.ggh iijjh),%w(aabc.. ddbc.. ..eefg ..hhfg ij..kk ij..ll),%w(aabbcc. ..de..f ..de..f gh....i gh....i jj..kkl ..mmnnl)
N=gets.to_i
def w x,j
G[x].map{|g|s=?.*N
s[j,x]=g
puts s}end
if N<3
p~0elsif N<4
w 3,0else m=N%4+4
w m,0
(N/4-1).times{|j|w 4,m+j*4}end

Measured memory_bytes: 4988
#include<iostream>
#include<stdio.h>


using namespace std;

int main()
{
	int x;
	int i,j;

	for(i=1;i<=9;i++){
		for(j=1;j<=9;j++){
			x = i*j;
			cout << i << 'x' << j << '=' << x << endl;
		}
	}	
}

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

int main() {
    int n,m,tem,ans=0;
    cin>>n>>m;
    rep(i,m) {
        cin>>tem;
        ans+=tem;
    }
    cout << max(-1,n-ans) <<endl;
    return 0;
}

Measured memory_bytes: 3636
import std.stdio;
void main() {
	auto i = ["A","B","AB","O"];
	int[string] a;
	foreach (j;i) a[j] = 0;
	int n;
	string b;
	while ("%d,%s\n".readf(&n, &b)) a[b]++;
	foreach (j;i) a[j].writeln;
}

Measured memory_bytes: 2464
#include <iostream>
#include <string>
#include <math.h>
using namespace std;

int main()
{
	int N;
	int A[100010];

	cin >> N;

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

	for (int i = 1; i <= N; i++)
		cout << A[i] << " ";

	return 0;
}

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

#define HASH 1000003

typedef struct List {
	struct List *next;
	char *s;
	int l;
} list;

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}

int hash_string(char* s)
{
	int i, x = 0;
	for (i = 0; s[i] != 0; i++) x = ((x << 5) + s[i] - 'a') % HASH;
	return x;
}

int lex_smaller(char* s1, char* s2)
{
	int i;
	for (i = 0; s1[i] != 0 && s2[i] != 0; i++) {
		if (s1[i] < s2[i]) return 1;
		else if (s1[i] > s2[i]) return -1;
	}
	if (s1[i] == s2[i]) return 0;
	else if (s1[i] == 0) return 1;
	else return -1;
}

int main()
{
	int i, j, l[200001], N;
	char *S[200001], T[1000001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%s", T);
		for (l[i] = 0; T[l[i]] != 0; l[i]++);
		S[i] = (char*)malloc(sizeof(char) * (l[i] + 1));
		for (j = 0; j <= l[i]; j++) S[i][j] = T[j];
	}
	
	int h[200001];
	list *p, *hash[HASH], d[200001];
	for (i = 1; i <= N; i++) {
		h[i] = hash_string(S[i]);
		d[i].s = S[i];
		d[i].l = l[i];
		d[i].next = hash[h[i]];
		hash[h[i]] = &(d[i]);
	}
	
	int k, m, dp[2][26];
	long long ans = 0, tmp, pow[32];
	const long long inv = div_mod(1, 32, HASH);
	for (k = 1, pow[0] = 32; k < 32; k++) pow[k] = pow[k-1] * pow[k-1] % HASH;
	for (i = 1; i <= N; i++) {
		if (l[i] <= 1) continue;
		for (j = 0; j <= l[i]; j++) T[j] = S[i][j];
		for (j = l[i] - 1, k = 0, tmp = 1; j > 0; j >>= 1, k++) if ((j & 1) == 1) tmp = tmp * pow[k] % HASH;
		h[i] = (h[i] - tmp * (T[0] - 'a') % HASH + HASH) % HASH;
		tmp = tmp * inv % HASH;
		h[i] = (h[i] - tmp * (T[1] - 'a') % HASH + HASH) % HASH;
		for (j = 0; j < 26; j++) dp[0][j] = 0;
		dp[0][S[i][0] - 'a'] = 1;
		dp[1][0] = S[i][0] - 'a';
		for (j = 1, m = 1; j < l[i]; j++) {
			if (dp[0][S[i][j] - 'a'] == 0) {
				dp[0][S[i][j] - 'a'] = 1;
				dp[1][m++] = S[i][j] - 'a';
			}
			for (k = 0; k < m; k++) {
				T[j] = 'a' + dp[1][k];
				h[0] = (tmp * dp[1][k] + h[i]) % HASH;
				for (p = hash[h[0]]; p != NULL; p = p->next) {
					if (p->l != l[i] - j || p->s[0] != T[j] || p->s[p->l - 1] != T[l[i] - 1]) continue;
					else if (lex_smaller(p->s, &(T[j])) == 0) break;
				}
				if (p != NULL) ans++;
			}
			tmp = tmp * inv % HASH;
			h[i] = (h[i] - tmp * (S[i][j+1] - 'a') % HASH + HASH) % HASH;
		}
	}
	
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}

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

int main() {
  int k;
  bool cond = true;
  vector<int> a(5);
  rep(i, 5) cin >> a[i];
  cin >> k;
  rep(i,4){
    for (int j = i + 1; j < 5;j++){
      if(a[j]- a[i] > k) {
        cond = false;
        break;
      }
    }
  }
  cout << (cond? "Yay!" : ":(") << endl;
}

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

const int N = 1e5 + 5;
typedef pair<int, int> pii;

int n;

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    vector<pii> pts;
    set<pii> ptsset;
    int x,y;
    for (int i = 0; i < n; i++){
        cin>>x>>y;
        pts.push_back({x,y});
        ptsset.insert({x,y});
    }
    
    sort(pts.begin(), pts.end());
    
    int mi_cnt = n;
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            int p = pts[i].first - pts[j].first;
            int q = pts[i].second - pts[j].second;
            
            int cnt = 0;
            for (int k = 0; k < n; k++){
                if(ptsset.count({pts[k].first - p, pts[k].second - q}));
                else cnt++;
            }
            mi_cnt = min(mi_cnt, cnt);
        }
    }
    
    cout<<mi_cnt<<endl;
    
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  char s[1000];
  for(int i=1;i<=n;i++)
  {
    cin>>s[i];
  }
  s[k]=s[k]+' ';
  for(int i=1;i<=n;i++)
  {
    cout<<s[i];
  }
}

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

struct Edge{
  int to;
  int weight;
  Edge(int t,int w) : to(t),weight(w){}
};

using Graph = vector<vector<Edge>>;

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

  for(int i=0;i<m;++i){
    int from,to,weight;
    cin >> from >> to >> weight;
    G[from].push_back(Edge(to,weight));
  }
  for(int i=0;i<n;++i){
  vector<ll> dist(n,1001001);
  vector<int> cnt(n,0);
  queue<int> que;
  dist[i]=0;
  cnt[i]=1;
  que.push(i);
  while(!que.empty()){
    int v=que.front();
    que.pop();
    for(auto nv : G[v]){
      if(dist[nv.to] == 1001001 || dist[nv.to] > dist[v]+nv.weight){
        if(dist[nv.to]<0 && cnt[nv.to]>m){
          cout << "NEGATIVE CYCLE" << endl;
          return 0;
        }
        dist[nv.to] = dist[v]+nv.weight;
        cnt[nv.to]++;
        que.push(nv.to);
      }
    }
  }
  for(int j=0;j<n;++j){
    if(j!=n-1){
      if(dist[j]==1001001) cout << "INF" << " ";
      else cout << dist[j] << " ";
    }else{
      if(dist[j]==1001001) cout << "INF" << endl;
      else cout << dist[j] << endl;
    }
  }
}
  return 0;

}



Measured memory_bytes: 3268
open System
let R T = stdin.ReadLine()|> T
let RS T = stdin.ReadLine().Split()|>Array.map T
let Mod = (1e9|>int64)+7L
[<EntryPoint>]
let main argv =
    let N = R int
    let a = RS int
    let mutable cur = 1
    for i in [0..N-1] do
        if cur=a.[i] then cur <- cur+1
    if cur=1 then -1 else N-cur+1
    |>stdout.WriteLine
    0


Measured memory_bytes: 37200
N, K = map(int, input().split())
C = [[0] * (N + 1) for _ in range(N + 1)]
C[0][0] = 1
for i in range(N):
    for j in range(i + 1):
        C[i + 1][j] += C[i][j]
        C[i + 1][j + 1] += C[i][j]


def main():
    for i in range(1, K + 1):
        b = C[N - K + 1][i]
        r = C[K - 1][i - 1]
        ans = b * r % 1000000007
        print(ans)


main()


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

#define _CRT_SECURE_NO_WARNINGS

int main(int argc, char const *argv[])
{
	char str[207];
	scanf("%s",str);
	for(int i = strlen(str) - 2; i; i -= 2){
		if(strncmp(str,str + i / 2 ,i / 2) == 0){
			printf("%d\n",i);
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;

int main(){
    int n, t, a;
    cin >> n >> t >>a;
    int ans = 0;
    int min = 1000000;
    rep(i,n) {
        int x;
        cin >> x;
        int d = abs((t * 1000 - x * 6) - a * 1000);
        if (min > d) {
            min = d;
            ans = i + 1;
        }
    }
    cout << ans << endl;
} 

Measured memory_bytes: 3592
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		double sum=0;
		for(int i=0;i<N;i++)sum+=1/sc.nextDouble();
		double ans=1/sum;
		System.out.println(ans);
	}
}

Measured memory_bytes: 22740
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x,y,ans;
int get(int x,int y){while (1){if(!(x%y))return x/y;x-=(x-(x/y)*y)/(x/y+1)*(x/y+1);if(!(x%y))return x/y;x-=(x/y+1);}}
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){cin>>x>>y;ans^=get(x,y);}
	if (ans)puts("Takahashi");else puts("Aoki");
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);

	public void profit() {
		int num = sc.nextInt();
		int[] store = new int[num];
		for (int i = 0; i < num; i++) {
			store[i] = sc.nextInt();
		}
		
		int min = store[0];
		int max = -Integer.MAX_VALUE;
		
		for (int i = 1; i < num; i++) {
			max = Math.max(max, store[i] - min);
			min = Math.min(min, store[i]);
		}
		System.out.println(max);
	}

	
	
	public static void main(String[] args) {
		new Main().profit();
	}
}


Measured memory_bytes: 100612
#include<stdio.h>
#include<string.h>

int main(){
	int index;
	scanf("%d", &index);
	char string[index+2];
	scanf("%s", &string);
	//printf("string awal adalah %s\n", string);
	if(index%2==1){
		printf("No");
	}
	else{
		int flag=1;
		int i=0,j=0;
		for(i=0;i<=(index/2)-1;i++){
			j=(index/2)+i;
			if(string[i]==string[j]){
				flag=1;
//				printf("Huruf ke index %d adalah %c\n", i, string[i]);
//				printf("Huruf ke index %d adalah %c\n", j, string[j]);
//				printf("flag = %d\n", flag);
			}
			else{
				flag=0;
//				printf("Huruf ke index %d adalah %c\n", i, string[i]);
//				printf("Huruf ke index %d adalah %c\n", j, string[j]);
//				printf("flag = %d\n", flag);
				break;
			}
		}
		flag==1? printf("Yes\n"):printf("No\n");
	}
}

Measured memory_bytes: 1660
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    print(180*(n-2))
    return

#B
def B():
    s = S()
    res = 15-len(s)
    k = s.count("o")
    if k+res >= 8:
        print("YES")
    else:
        print("NO")
    return

#C
def C():
    return

#D
def D():
    n = I()
    v = [[] for i in range(n)]
    f = [[0,i] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a][0] += 1
        f[b][0] += 1
    f.sort(key = lambda x:-x[0])
    s = f[0][1]
    c = LI()
    c.sort(key = lambda x:-x)
    f[0][0] = c[0]
    q = deque()
    q.append(s)
    bfs = [1 for i in range(n)]
    f.sort(key = lambda x:x[1])
    bfs[s] = 0
    k = 1
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                f[y][0] = c[k]
                k += 1
                q.append(y)
    ans = 0
    q.append(s)
    bfs = [1 for i in range(n)]
    bfs[s] = 0
    while q:
        x = q.popleft()
        for y in v[x]:
            ans += min(f[x][0],f[y][0])
            if bfs[y]:
                bfs[y] = 0
                q.append(y)
    print(ans//2)
    for i, j in f[:-1]:
        print(i,end = " ")
    print(f[-1][0])
    return

#E
def E():
    mod = 1000003
    f = [None for i in range(2*mod+1)]
    f[0] = 1
    for i in range(2*mod):
        f[i+1] = (i+1)*f[i]%mod
    inv_f = [0 for i in range(2*mod+1)]
    inv_f[mod-1] = pow(f[mod-1],mod-2,mod)
    for i in range(mod-1)[::-1]:
        inv_f[i] = inv_f[i+1]*(i+1)%mod
    q = I()
    for _ in range(q):
        x,d,n = LI()
        if x == 0:
            print(0)
        elif d == 0:
            print(pow(x,n,mod))
        elif n >= mod:
            print(0)
        else:
            ans = pow(d,n,mod)
            x *= pow(d,mod-2,mod)
            x %= mod
            ans *= f[x+n-1]*inv_f[x-1]%mod
            ans %= mod
            print(ans)
    return

#F
def F():
    n = I()
    return

#Solve
if __name__ == "__main__":
    E()


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

long long countDivisibles(long long A, long long B, long long M) 
{ 
    if (A % M == 0) 
        return (B / M) - (A / M) + 1; 
  
    return (B / M) - (A / M); 
} 
  
int main() 
{ 
    long long a,b,m;
  	cin >> a >> b >> m;
   
    cout << countDivisibles(a, b, m) << endl; 
  
    return 0; 
} 


Measured memory_bytes: 256
def check(n):

    if n <= P-1:
        return True

    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-i for i in A[P-1:n]])

    if votes < M*V:
        return False
    else:
        return True

N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))

A.sort(reverse=True)

##開区間
right = N
left = 0

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Measured memory_bytes: 14964
#include<bits/stdc++.h>
using namespace std;
bool visited[200005];
int arr[200005];
int main(){
	long long k;
	int n;
	cin>>n>>k;
	for(int i=1; i<=n; i++) cin>>arr[i];
	vector<int>travel;
	int curr = 1;
	while(!visited[curr]){
		visited[curr] = true;
		travel.push_back(curr);
		curr = arr[curr];
	}
	int cycle_start;
	for(int i=0; i<travel.size(); i++){
		if(travel[i]==curr){
			cycle_start = i;
			break;
		}
	}
	if(k<=cycle_start) cout<<travel[k];
	else{
		k-=cycle_start;
		int cycle_len = travel.size()-cycle_start;
		k%=cycle_len;
		cout<<travel[cycle_start+k];
	}
}

Measured memory_bytes: 5296
#include <stdio.h>

using namespace std;

int main()
{
    double n,k,j;
    int i;
    double a[10001];
    double sum=0;
    scanf("%lf %lf",&n,&k);
    if(n<k)
    {
        for(i=1;i<=n;i++)
        {
            j=i;
            a[i]=1;
            while(j<k)
            {
                j*=2;
                a[i]/=2;
            }
            sum+=a[i];
        }
        sum/=n;
        printf("%.12f",sum);
    }
    else if(n>=k)
    {
        for(i=1;i<k;i++)
        {
            int j=i;
            a[i]=1;
            while(j<k)
            {
                j*=2;
                a[i]/=2;
            }
            sum+=a[i];
        }

        double b=(n-k+1);
        sum+=b;
        sum/=n;
        printf("%.12f",sum);

    }
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#define ll long long
#define out(a) printf("%d",a)
#define writeln printf("\n")
const int N=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,x,num;
int read()
{
	int s=0,t=1; char c;
	while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
	while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
	return s*t;
}
ll readl()
{
	ll s=0,t=1; char c;
	while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
	while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
	return s*t;
}
int main()
{
	n=read(); x=0;
	while (1){
	  num=n-x*4;
	  if (num%7==0) {
	  	puts("Yes");
	  	return 0;
	  }
	  if (num<0) break;
	  x++;
	}		
	puts("No");
	return 0;
}
	

Measured memory_bytes: 256