akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
const int inf=1e9;
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define MOD 100000007
// a^b mod MOD
ll powmod(ll a,ll b){
	if(b==1)return a%MOD;
	ll out=powmod(a,b/2)%MOD;
	out=out*out%MOD;
	if(b%2)out=out*a%MOD;
	return out;
}
// nCr
ll nCr(int n,int r){
	ll out=1;
	r=min(r,n-r);
	for(int i=n;i>n-r;i--)out=out*i%MOD;
	for(int i=2;i<=r;i++)out=out*powmod(i,MOD-2)%MOD;
	return out;
}
int main(){
	int n,m,a,b,c,d;
	cin>>n>>m>>a>>b>>c>>d;
	if(c<a)swap(a,c);
	if(d<b)swap(b,d);
	int x=min(c-a,n-c+a),y=min(d-b,m-d+b);
	ll out=nCr(x+y,y);
	if(c-a==n-c+a)out*=2;
	if(d-b==m-d+b)out*=2;
	cout<<out%MOD<<endl;
}

Measured memory_bytes: 1160
#include<stdio.h>
int main(void) {
    int n, i, x;
    scanf("%d", &n);
    for(i = 3; i <= n; i++) {
        x = i;
        if(x%3 == 0) printf(" %d", i);
        else {
            while(x != 0) {
                if(x%10 == 3) {
                    printf(" %d", i);
                    break;
                }
                x = x/10;
            }
        }
    }
    putchar('\n');
    return 0;
}


Measured memory_bytes: 2104
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int N, M, X, A[100];
    cin >> N >> M >> X;
    for (int i = 0; i < M; i++) cin >> A[i];

    int left = 0, right = 0;
    for (int i = 0; i < M; i++)
    {
        if (A[i] < X)
        {
            left++;
        }
        else if (A[i] > X)
        {
            right++;
        }
    }
    int result = min(left, right);
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 256
#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 = 1e9;
const int MOD = 1000000007;

int main(){
    int n;
    cin >> n;
    vector<vector<int>> graph(n,vector<int>());
    int m = 0;
    if(n%2 == 0){
        rep(i,n){
            rep(j,i){
                if(i+j==n-1) continue;
                graph[i].push_back(j);
                ++ m;
            }
        }
    }else{
        rep(i,n){
            rep(j,i){
                if(i != n-1 && i+j == n-2) continue;
                graph[i].push_back(j);
                ++ m;
            }
        }
    }
    cout << m << endl;
    rep(i,n)rep(j,graph[i].size()){
        cout << i+1 << " " << graph[i][j]+1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int num,i,j;
    long long int sum=0;
    cin>>num;
    if(num==1)
    {
        cout<<num<<endl;
    }
    else if(num==2)
    {
        cout<<num<<endl;
    }
    else
    {
        sum=0;
        for(i=1; i<=num; i++)
        {
            if(i%3!=0 && i%5!=0)
            {
                sum=sum+i;
            }
        }
        cout<<sum<<endl;
    }

    return 0;
}


Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		String s = sc.next();
		for(int i = 0; i<s.length(); i++) {
			pw.print("x");
		}
		pw.close();
	}
	
	static class FastScanner {
		private BufferedReader reader = null;
	    private StringTokenizer tokenizer = null;
	    public FastScanner(InputStream in) {
	        reader = new BufferedReader(new InputStreamReader(in));
	        tokenizer = null;
	    }

	    public String next() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                tokenizer = new StringTokenizer(reader.readLine());
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }
	        return tokenizer.nextToken();
	    }

	    public String nextLine() {
	        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	                return reader.readLine();
	            } catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        }

	        return tokenizer.nextToken("\n");
	    }

	    public long nextLong() {
	        return Long.parseLong(next());
	    }

	    public int nextInt() {
	        return Integer.parseInt(next());
	    }

	    public double nextDouble() {
	         return Double.parseDouble(next());
	     }

	    public int[] nextIntArray(int n) {
	        int[] a = new int[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextInt();
	        return a;
	    }

	    public long[] nextLongArray(int n) {
	        long[] a = new long[n];
	        for (int i = 0; i < n; i++)
	            a[i] = nextLong();
	        return a;
	    }
	}
}

Measured memory_bytes: 21204
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>
#include <set>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ;
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back

//#define int long long

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}
struct UnionFind{
    vector<int> par,rank;
    UnionFind(int N){
        par.assign(N,0);
        rank.assign(N,0);
        REP(i,N) par[i]=i;
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
    void unite(int x,int y){
        x=find(x),y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]) swap(x,y);

        //x becomes root
        par[y]=x;
        if(rank[x]==rank[y]) rank[x]++;
    }
};

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

signed main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M; cin >> N >> M;
    int exist[112345] = {};
    UnionFind uf(N);
    REP(i,M){
        int x,y,z; cin >>x>>y>>z;
        x--; y--;
        uf.unite(x,y);
    }
    REP(i,N){
        int p = uf.find(i);
        exist[p] = 1;
    }
    int ans = 0;
    REP(i,N){
        if(exist[i] == 1) ans++;
    }
    cout << ans << endl;


}

Measured memory_bytes: 1536
from collections import deque
S = input()
Q = int(input())
Query = []

for i in range(Q):
    Query.append(list(input().split()))


turning = 1
# 1なら正常　-1なら反転
ans = deque(S)
for i in Query:
    if i[0] == "1":
        turning *= -1
    else:
        if i[1] == "1":
            if turning == 1:
                ans.appendleft(i[2])
            else:
                ans.append(i[2])
        else:
            if turning == 1:
                ans.append(i[2])
            else:
                ans.appendleft(i[2])


print("".join(list(ans)) if turning == 1 else "".join(list(ans)[::-1]))


Measured memory_bytes: 137332
def solve(N):
    s = 1
    e = int(pow(N, 0.5)) + 1
    ds = []
    for k in range(s, e):
        if N % k == 0:
            m = (N // k) - 1
            if m and N // m == N % m:
                ds.append(m)

    return sum(ds)

if __name__ == "__main__":
    N = int(input())
    print(solve(N))

Measured memory_bytes: 3060
import collections
import sys

input = sys.stdin.readline
N = int(input())
candidate = [input().strip("\n") for _ in range(N)]

candidate.sort()
c = collections.Counter(candidate)

MAX = c.most_common()[0][1]

l = sorted([k for k, v in c.items() if v == MAX])

for i in l:
    print(i)

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

using namespace std;

int main() {
	string s;
	cin >> s;
	sort(s.begin(), s.end());
	if (s == "abc") {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000000)


def main():
    A, B, C, K = map(int, input().split())
    num = K
    if K <= A:
        print(K)
    elif (A + B) >= K:
        print(A)
    else:
        # import pdb; pdb.set_trace()
        print(2 * A + B - K)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9168
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String S = scan.next();
		String T = scan.next();
		scan.close();
		int l = S.length();

		int[]R1 = new int[26];
		int[]R2 = new int[26];
		Arrays.fill(R1, -1);
		Arrays.fill(R2, -1);
		// 'a' = 97
		int[]s = new int[l];
		int[]t = new int[l];
		for(int i = 0; i < l; i++) {
			s[i] = (int)S.charAt(i) - 97;
			t[i] = (int)T.charAt(i) - 97;
		}
		for(int i = 0; i < l; i++) {
			if(R1[s[i]] >= 0) {
				if(R1[s[i]] != t[i]) {
					System.out.println("No");
					System.exit(0);
				}
			}else {
				R1[s[i]] = t[i];
			}
			if(R2[t[i]] >= 0) {
				if(R2[t[i]] != s[i]) {
					System.out.println("No");
					System.exit(0);
				}
			}else {
				R2[t[i]] = s[i];
			}
		}
		System.out.println("Yes");
	}
}


Measured memory_bytes: 28848
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
g = A[-1]
l = A[-1]
import fractions
for i in range(2,N+1):
    a = A[-i]
    g = fractions.gcd(l,a)
    l = l*a//g
    if l//2 > M:
        print(0)
        quit()
b = l//2
f = (M-b)//l + 1
for i in range(N):
    if b%A[i] == 0:
        f = 0
        break
if M < l//2:
    ans = 0
else:
    ans = f
print(ans)

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

#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple

using namespace std;

int niz[100010];
vector<int> graf[100010];
vector<pair<int, int>> res;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    cin >> s;
    int n = s.size();
    for(int i = 1; i <= n; i++)
        niz[i] = s[i-1] - '0';
    bool ok = true;
    if(niz[1] == 0 || niz[n] == 1) ok = false;
    for(int i = 1; i <= n/2; i++)
        if(niz[i] != niz[n - i]) {ok = false; break;}

    if(!ok) {cout << -1; return 0;}

    int tr = 1;
    for(int i = 1; i < n; i++)
    {
        res.pb(mp(i+1, tr));

        if(niz[i] == 1)
            tr = i + 1;
    }
    for(int i = 0; i < res.size(); i++)
        cout << res[i].fi << " " << res[i].se << "\n";


    return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<ll,pair<ll,ll>> pii;
typedef pair<ll,ll> pi;
typedef vector<ll> vl;

#define matrix vector<vector<ll>>
#define llmax LLONG_MAX
#define llmin LLONG_MIN
#define rep(i,n) for(ll (i)=0;(i)<n;++(i))
#define crep(i,m,n) for(ll (i)=m;(i)<n;++(i))
#define zero(a) memset((a),0,sizeof((a)))
#define minus(a) memset((a),-1,sizeof((a)));
#define sq(a) ((a)*(a))
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define ff first
#define ss second

void test_case();
int main(){
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    ll t=1;
    // cin >> t;
    for(ll T=0;T<t;T++){
        test_case();
    }
    //**************************************************************************//
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

void test_case(){
    string str1,str2,ans="";
    cin>>str1>>str2;
    ll n1=str1.size(), n2=str2.size() ;
    vector<vector<int>> dp(n1+1, vector<int>(n2+1,0));

    crep(i,1,n1+1){
        crep(j,1,n2+1){
            if(str1[i-1]==str2[j-1])dp[i][j]=dp[i-1][j-1]+1;
            else{
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    ll l=n1,r=n2;
    while(l>=1 && r>=1){
        if(str1[l-1]==str2[r-1]){ans+=str1[l-1];--l;--r;continue;}
        if(dp[l-1][r]>=dp[l][r-1]){
            --l;
        }
        else if(dp[l-1][r]<dp[l][r-1]){
            --r;
        }

    }
    reverse(all(ans));
    cout<<ans;
}


Measured memory_bytes: 38536
#include<bits/stdc++.h>
#define rep(i, l, r) for(register int i = l; i < r; i++)
#define tms(x) ___ = x; while(___--)
#define D(x) cout<<"D: "<<#x<<'='<<x<<endl;
#define R(x, l) cout<<"R: Array "<<#x<<endl; rep(i, 0, l) cout<<' '<<i<<':'<<*(x+i)<<endl;
#define pb push_back
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int ___;
template<typename tn> inline tn next(void);
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v);
signed main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	string str = next<string>();
	if (str[2] == str[3] && str[4] == str[5]) puts("Yes");
	else puts("No");
	return ~~(0-0);
}
template<typename tn> inline tn next(void)
{
	tn k;
	cin>>k;
	return k;
}
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v)
{
	rep(i, 0, v.size()) os<<v[i]<<' ';
	return os;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main() {
  int a[5000], n, i, j, result, tmp;
  while(cin >> n && n) {
    for(i = 0; i < n; i++) cin >> a[i];
    for(i = 1; i < n; i++) a[i] += a[i-1];
    result = a[n-1];
    for(i = n-1; i >= 0; i--)
      {
	if (a[i] > result) result = a[i];
	for(j = 0; j < i; j++)
	  if ((tmp = a[i] - a[j]) > result) result = tmp;
      }
    cout << result << endl;
  }
  return 0;
}

Measured memory_bytes: 1176
N = int(input())
a,b,c = [0]*N, [0]*N, [0]*N
for i in range(N):
    a[i],b[i],c[i] = map(int, input().split())

d = {0:a, 1:b, 2:c}
dp = [[0]*3 for _ in range(N+1)]

for i in range(N):
    for cur in [0,1,2]:
        for prev in [0,1,2]:
            if prev == cur:
                continue
            dp[i+1][cur] = max(dp[i+1][cur],
                               dp[i][prev] + d[cur][i])

print(max(dp[N]))        

Measured memory_bytes: 60504
#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>;

int a[3][3];
int d[3][3];

int main() {
  rep(i,3)rep(j,3) cin >> a[i][j];
  int n;
  cin >> n;
  rep(ni,n) {
    int x;
    cin >> x;
    rep(i,3)rep(j,3) if (a[i][j] == x) d[i][j] = 1;
  }
  bool ans = false;
  rep(i,3) {
    int cnt = 0;
    rep(j,3) cnt += d[i][j];
    if (cnt == 3) ans = true;
  }
  rep(i,3) {
    int cnt = 0;
    rep(j,3) cnt += d[j][i];
    if (cnt == 3) ans = true;
  }
  {
    int cnt = 0;
    rep(j,3) cnt += d[j][j];
    if (cnt == 3) ans = true;
  }
  {
    int cnt = 0;
    rep(j,3) cnt += d[j][2-j];
    if (cnt == 3) ans = true;
  }
  puts(ans?"Yes":"No");
  return 0;
}


Measured memory_bytes: 256
h, w = list(map(int, input().split()))
xs = [input()  for i in range(h)]

d = {}
for i in range(h):
    for j in range(w):
        d[(i+1, j+1)] = xs[i][j]


def neighbore(d, coor):
    i, j = coor
    mine = 0
    for di in range(-1, 2):
        for dj in range(-1, 2):
            if di == 0 and dj == 0:
                continue
            if d.get((i+di, j+dj), ".") == "#":
                mine  += 1
    return str(mine)


for i in range(1, h+1):
    line = []
    for j in range(1, w+1):
        if d[i, j] == ".":
            line.append(neighbore(d, (i, j)))
        elif d[(i,j)] == "#":
            line.append("#")
        else:
            assert(False)
    print("".join(line))





Measured memory_bytes: 3316
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n, k = MAP()
x = LIST()
d = [x[i + k - 1] - x[i] + min(abs(x[i] - 0), abs(x[i + k - 1] - 0)) for i in range(n - k + 1)]
print(min(d))

Measured memory_bytes: 83820
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
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 int INF = 1e9;
const LL LLINF = 1e16;

int main(){
    int r;
    cin >> r;
    cout << 3 * r * r << endl;
}

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


using namespace std;
using namespace __gnu_cxx;

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
//    freopen("output.out", "w", stdout);
#endif
    int AC, WA, TLE, RE;
    AC = WA = TLE = RE = 0;
    int n; cin >> n;
    string verdict;
    for(int i = 0; i < n; i++) {
        cin >> verdict;
        if(verdict == "AC") AC++;
        else if(verdict == "WA") WA++;
        else if(verdict == "TLE") TLE++;
        else RE++;
    }

    cout    << "AC x " << AC << '\n'
            << "WA x " << WA << '\n'
            << "TLE x " << TLE << '\n'
            << "RE x " << RE << '\n';
}

Measured memory_bytes: 3596
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;

        while (!(line = br.readLine()).equals("0 0")) {
            String[] input = line.split(" ");
            int n = Integer.parseInt(input[0]);
            int m = Integer.parseInt(input[1]);
            boolean[] away = new boolean[n];
            int potato = n - 1;

            for (int i = 0; i < n - 1; i++) {
                int counter = 0;
                while (counter != m) {
                    potato = (potato + 1) % n;
                    if (!away[potato]) {
                        counter++;
                    }
                }
                away[potato] = true;
            }

            for (int i = 0; i < n; i++) {
                if (!away[i]) {
                    System.out.println((i + 1));
                    break;
                }
            }
            
        }
    }
}


Measured memory_bytes: 25344
N = int(input())
B = list(map(int, input().split()))

ans = B[0]
buff = []
for i in range(N-2):
    ans += min(B[i],B[i+1])
    buff.append(min(B[i],B[i+1]))

buff.append(B[-1])
ans += B[-1]
print(ans)

Measured memory_bytes: 3064
from itertools import accumulate
n,W,*L=map(int,open(0).read().split())
l=[[] for _ in range(4)]
lim=[1]*4
m=min(L[::2])
for w,v in zip(*[iter(L)]*2):
	l[w-m].append(v)
	lim[w-m]+=1
ll=[]
for x in l:
	ll.append([0]+list(accumulate(sorted(x)[::-1])))
ans=0
for i in range(lim[0]):
	if m*i>W:
		continue
	for j in range(lim[1]):
		if m*i+(m+1)*j>W:
			continue
		for k in range(lim[2]):
			if m*i+(m+1)*j+(m+2)*k>W:
				continue
			for l in range(lim[3]):
				if m*i+(m+1)*j+(m+2)*k+(m+3)*l>W:
					continue
				ans=max(ans,ll[0][i]+ll[1][j]+ll[2][k]+ll[3][l])
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

int main()
{
    int N;
    cin >> N;
    REP(i, 100000)
    {
        if (i * 108 / 100 == N)
        {
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
}


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

from sys import stdin
from math import isinf


def generate_adj_table(v_table, _init_adj_table):
    for each in v_table:
        start, end, weight = map(int, each)
        _init_adj_table[start][end] = weight

    return _init_adj_table


def floyd(_adj_table):
    for k in v_range:
        for i in v_range:
            for j in v_range:
                _adj_table[i][j] = min(_adj_table[i][j],
                                       _adj_table[i][k] + _adj_table[k][j])
    return _adj_table


def solve(_after_table):
    negative = False
    for m in v_range:
        if _after_table[m][m] < 0:
            negative = True

    if negative:
        print('NEGATIVE CYCLE')
        return None
    else:
        for each in _after_table:
            print(' '.join(('INF' if isinf(ele) else str(ele) for ele in each)))

    return _after_table


if __name__ == '__main__':
    _input = stdin.readlines()
    vertices, edges = map(int, _input[0].split())
    info_list = map(lambda x: x.split(), _input[1:])
    v_range = range(vertices)

    init_adj_table = tuple([float('inf')] * vertices for _ in v_range)
    for n in v_range:
        init_adj_table[n][n] = 0

    adj_table = generate_adj_table(info_list, init_adj_table)
    after_table = floyd(adj_table)
    ans = solve(after_table)

Measured memory_bytes: 8820
#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;
const int MOD = 1000000007;
struct mint { int n; mint(int n_ = 0) : n(n_) {} };
mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

vector<mint> F_{1, 1}, R_{1, 1}, I_{0, 1};
void check_fact(int n) {
  for (int i = I_.size(); i <= n; i++) {
    I_.push_back(I_[MOD % i] * (MOD - MOD / i));
    F_.push_back(F_[i - 1] * i);
    R_.push_back(R_[i - 1] * I_[i]);
  }
}

mint I(int n) { check_fact(abs(n)); return n >= 0 ? I_[n] : -I_[n]; }
mint F(int n) { check_fact(n); return n < 0 ? 0 : F_[n]; }
mint R(int n) { check_fact(n); return n < 0 ? 0 : R_[n]; }
mint C(int n, int r) { return F(n) * R(n - r) * R(r); }
mint P(int n, int r) { return F(n) * R(n - r); }
mint H(int n, int r) { return n == 0 ? (r == 0) : C(n + r - 1, r); }


int N, K;
int main(void){
    cin >> N >> K;
    if(K>C(N-1,2).n) cout << -1 << endl;
    else{
        cout << N - 1 + (C(N-1,2).n - K) << endl;
        for(int i=2;i<=N;i++) cout << 1 << " " << i << endl;
        int count = 0;
        for(int i=2;i<N;i++) for (int j=i+1;j<=N;j++){
            if(count >= C(N-1,2).n - K) return 0;
            cout << i << " " << j << endl;
            count++;
        }
    }
    return 0;
}



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

int main()
{
    int n;
    cin >> n;
    vector<int> w(n);
    for (int i = 0; i < n; i++)
    {
        cin >> w[i];
    }
    int ans = 1e9;
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = 0;
        for (int j = 0; j < i; j++)
            l += w[j];
        for (int j = i; j < n; j++)
            r += w[j];
        ans = min(ans, abs(l - r));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <map>
#include <set>
#include <sstream>
#include <iostream>
#include <limits>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <cmath>


using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef stringstream ss;
const int mii = numeric_limits<int>::min();
const int mai = numeric_limits<int>::max();
const ll mil = numeric_limits<long long>::min();
const ll mal = numeric_limits<long long>::max();

#define REP(i, a, b) for(long long i=a; i<=b; ++i)
#define RREP(i, a, b) for(long long i=a; i>=b; --i)
#define PB(x) push_back(x)
#define MP(x, y) make_pair(x, y)

int main(int argc, char **argv) {

    int a, b;
    cin >> a>>b;

    /*int n1l = a/0.08;
    int n1h = ((a+1)/0.08) - 1;
    int n2l = b/0.1;
    int n2h = ((b+1)/0.1) - 1;

    set<int> s1;
    set<int> s2;
    vi res;

    REP(i, n1l, n1h)
        s1.insert(i);
    REP(i, n2l, n2h)
        s2.insert(i);

    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), back_inserter(res));
    sort(res.begin(), res.end());*/

    int res = -1;

    REP(i, 1, 1008) {
        if(floor(i*0.08) == a && floor(i*0.1) == b) {
            res = i;
            break;
        }

    }

    if(res == -1)
        cout << "-1" << endl;
    else
        cout << res << endl;

    return 0;
}

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

#define INF  						1e15
#define EPS   						1e-9
#define MOD 						1000000007
#define Pi 							3.14159265358979323846264338327950288419716939937510

#define umap 						unordered_map
#define uset 						unordered_set
#define fi 							first
#define se 							second
#define ll 							long long 
#define vi 							vector<int>
#define pii 						pair<int,int>
#define vll 						vector<ll>
#define pll							pair<ll,ll>
#define pb 							push_back
#define pob 						pop_back
#define pf 							push_front
#define pof 						pop_front
#define maxE(a,n) 					*max_element(a,a+n);
#define minE(a,n) 					*min_element(a,a+n);
#define all(x) 						x.begin(), x.end()

#define fast 						ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fori(i,a,n) 				for (ll  i=a;i<n;i++)
#define ford(i,a,n) 				for (ll  i=n-1;i>=a;i--)

ll gcd(ll a, ll b){ll temp;while (b > 0){temp = a%b;a = b;b = temp;} return a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll power(ll x, ll b,ll m) {ll p = 1;while (b > 0) {if(b&1) {p = p * x; p %= m;} b >>= 1; x *= x; x %= m;} return p % m;}

using namespace std;


void solve(){

	ll n;
	cin>>n;

	ll op = 0;
	for(int i=1;i<=n;i++){
		op +=  (n/i);
		if(n%i == 0) op--;
	}

	cout<<op<<endl;

}


int main(){

	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	fast;
	ll t = 1;


	while(t--){
		solve();
	}
}


Measured memory_bytes: 3660
#include<cstdio>
int N,C;
int t[3][35],d[35][35];
//t[i][j]:余数为i,颜色为j的数量
int main()
{
	int ans=0x3f3f3f3f;
	scanf("%d %d",&N,&C);
	for(int i=1;i<=C;i++)
		for(int j=1;j<=C;j++)
			scanf("%d",&d[i][j]);
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
		{
			int x;
			scanf("%d",&x);
			t[(i+j)%3][x]++;
		}
	int x,y,z;
	for(int i=1;i<=C;i++)//余数为0全部转化为颜色i
	{
		x=0;
		for(int j=1;j<=C;j++)
			x+=t[0][j]*d[j][i];
		for(int j=1;j<=C;j++)//余数为1全部转化为颜色j
		{
			y=0;
			if(j==i) continue;//不同余数颜色不同
			for(int k=1;k<=C;k++)
				y+=t[1][k]*d[k][j];
			for(int k=1;k<=C;k++)//余数为2全部转化为颜色k
			{
				z=0;
				if(k==i||k==j) continue;
				for(int m=1;m<=C;m++)
					z+=t[2][m]*d[m][k];
				if((x+y+z)<ans) ans=x+y+z;
			}
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 128
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        edges[a].append(b)
        edges[b].append(a)

    counter = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        counter[p] += x

    def dfs(cur, par):
        for nex in edges[cur]:
            if nex == par:
                continue
            counter[nex] += counter[cur]
            dfs(nex, cur)

    dfs(0, -1)
    print(*counter, sep=" ")


if __name__ == "__main__":
    main()


Measured memory_bytes: 268464
open Batteries
module EnumL = Enum.Labels
module ListL = List.Labels
module ArrayL = Array.Labels

let dbg0 x = Printf.eprintf "[debug]%s\n" @@ dump x
let dbg1 x = dbg0 x; x

let id = identity

let (++) n m = List.range n `To m
let (++-) n m = if n >= m then List.range n `Downto m else []
let (++^) n m = if n < m then List.range n `To (pred m) else []

let scan fmt = Scanf.sscanf (read_line ()) fmt

let scan_lines n fmt f =
  if n = 0 then []
  else List.map (fun _ -> scan fmt f) (1 ++ n)

let scan_list ?sep cnv =
  let line = read_line () in
  (match sep with
   | None -> List.map String.of_char @@ String.to_list line
   | Some sep -> String.split_on_char sep line)
  |> List.map cnv

let scan_array ?sep cnv = Array.of_list @@ scan_list ?sep cnv

let scan_matrix n m e ?sep conv =
  let arr = Array.make_matrix n m e in
  ListL.iter (0 ++^ n)
    ~f:(fun i -> arr.(i) <- Array.of_list @@ scan_list ?sep conv);
  arr

let atoi c = Char.code c - Char.code '0'

let rec powerset = function
  | [] -> [[]]
  | hd::tl ->
    let pws =  powerset tl in
    pws @ ListL.map pws ~f:(fun pw -> hd::pw)

let permutations l =
  let rec interleave x = function
    | [] -> [[x]]
    | (hd::tl) as l ->
      (x::l) :: (interleave x tl |> ListL.map ~f:(fun l -> hd::l)) in
  let rec aux = function
    | [] -> [[]]
    | a::rest ->
      aux rest |> ListL.map ~f:(interleave a) |> List.concat in
  aux l

let intersection l =
  EnumL.filter ~f:(fun x -> EnumL.exists ~f:((=) x) @@ Enum.clone l)

let zip l m =
  let n = min (List.length l) (List.length m) in
  List.combine (List.take n l) (List.take n m)

let lower_bound n f =
  let rec aux l u =
    if u - l > 1 then
      let m = (l + u) / 2 in
      if f m then aux l m
      else aux m u
    else u in aux (-1) n

let between n x m = n <= x && x < m

let n = scan "%d" id
let p = scan_list ~sep:' ' Int.of_string
let q = scan_list ~sep:' ' Int.of_string

let () =
  let sets = permutations (1++n)
             |> List.sort (List.compare Int.compare) in
  let a = List.index_of p sets |> Option.get in
  let b = List.index_of q sets  |> Option.get in
  Printf.printf "%d\n" @@ abs (a - b)


Measured memory_bytes: 13696
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def main():
    N, C = [int(_) for _ in input().split()]
    nr0, nr1, nr2 = 0, 0, 0

    Diff = []
    for _ in range(C):
        Diff.append([int(__) for __ in input().split()])

    Color = []
    for _ in range(N):
        Color.append([int(__) for __ in input().split()])

    R0 = collections.defaultdict(lambda: 0)
    R1 = collections.defaultdict(lambda: 0)
    R2 = collections.defaultdict(lambda: 0)

    for y in range(N):
        for x in range(N):
            r = (y + x) % 3

            if r == 0:
                R0[Color[y][x]] += 1
                nr0 += 1
            elif r == 1:
                R1[Color[y][x]] += 1
                nr1 += 1
            else:
                R2[Color[y][x]] += 1
                nr2 += 1

    R0s = []
    for dist_color in range(C):
        d = 0
        for src_color in R0.keys():
            d += Diff[src_color-1][dist_color] * R0[src_color]

        R0s.append(d)

    R1s = []
    for dist_color in range(C):
        d = 0
        for src_color in R1.keys():
            d += Diff[src_color-1][dist_color] * R1[src_color]

        R1s.append(d)

    R2s = []
    for dist_color in range(C):
        d = 0
        for src_color in R2.keys():
            d += Diff[src_color-1][dist_color] * R2[src_color]

        R2s.append(d)
        
    ans = 10**100
    for i in range(C):
        for j in range(C):
            for k in range(C):
                if i == j or j == k or i == k:
                    continue

                ans = min(ans, R0s[i] + R1s[j] + R2s[k])

    print(ans)

main()


Measured memory_bytes: 7076
#include<stdio.h>
int main()                                                                
{
	int A,B,C;
	scanf("%d %d %d",&A,&B,&C);
	if(A==5 && B==7 &&C==5) puts("YES");
	else if(A==5 && B==5 &&C==7) puts("YES");
	else if(A==7 && B==5 &&C==5) puts("YES");
	else puts("NO");
	return 0;
}

Measured memory_bytes: 128
pt = {
  'A' => [[1,1],
  		  [1,1]],

  'B' => [[1],
		  [1],
		  [1],
		  [1]],

  'C' => [[1,1,1,1]],

  'D' => [[0,1],
		  [1,1],
		  [1,0]],

  'E' => [[1,1,0],
		  [0,1,1]],

  'F' => [[1,0],
		  [1,1],
		  [0,1]],

  'G' => [[0,1,1],
  		  [1,1,0]]
}

def pt_match(b, p, x, y, h, w)
	for dx in 0 .. (w-1)
		xx = x + dx
		if xx >= 8 then
			return false
		end
		for dy in 0 .. (h-1) do
			yy = y + dy
			if yy >= 8 then
				return false
			end

			if b[yy][xx] != p[dy][dx] then
				return false
			end
		end
	end

	return true
end

def mv_pat(b, p, h, w)
	x = 0
	while x <= (8 - w) do
		y = 0
		while y <= (8 - h) do
			if pt_match(b, p, x, y, h, w) then
				return true
			end
			y += 1
		end
		x += 1
	end
	return false
end

loop {
	b = []
	8.times {
		if (line = gets) == nil then
			exit
		end
		b.push line.chomp.split('').map(&:to_i)
	}

	pt.each { | key, d |
		h = d.size
		w = d[0].size

		if mv_pat(b, d, h, w) then
			puts key
			break
		end
	}

	if gets == nil then
		break
	end
}

Measured memory_bytes: 6120
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vii;
typedef vector<pair<int,int>> vip;

#define ZOOM ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ff it->first
#define ss it->second
#define all(v) (v).begin(),(v).end()
#define loop for(auto i=0;i<n;++i)
#define LOOP_IT(s) for(auto it=(s).begin();it!=(s).end();++it)


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

    int n;
    cin>>n;
    vii v(n);
    loop cin>>v[i];
    int cnt=0,mn=1e9;
    loop
    {
        mn=min(mn,v[i]);
        if(v[i]==mn)
            ++cnt;
    }
    cout<<cnt;

    return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int n;
  cin >> n;
  int b[n - 1];
  REP(i, n - 1) cin >> b[i];
  int ans = 0;
  ans += b[0];
  for (int i = 1; i < n - 1; ++i) {
    ans += min(b[i - 1], b[i]);
  }
  ans += b[n - 2];
  cout << ans << endl;
  return 0;
}

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

#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back

using ll = long long;
using i_i = tuple<int, int>;

const int MOD = 1e9 + 7;

ll C[1010][1010];

int main() {
    for (int x = 0; x < 1010; x++) {
        C[x][0] = 1;
        for (int y = 1; y <= x; y++)
            C[x][y] = (C[x - 1][y - 1] + C[x - 1][y]) % MOD;
    }
    int N, K; cin >> N >> K;
    vector<int> a(K);
    rep(k, K) cin >> a[k];
    vector<ll> dp(N + 1);
    dp[0] = 1;
    rep(k, K) {
        vector<ll> _dp(N + 1);
        rep(x, N + 1) rep(dx, N - x + 1) {
            if (dx > a[k]) continue;
            int _x = x + dx;
            ll z = dp[x] * C[N - x][dx] % MOD * C[N - dx][a[k] - dx] % MOD;
            _dp[_x] = (_dp[_x] + z) % MOD;
        }
        dp = _dp;
    }
    cout << dp[N] << endl;
}


Measured memory_bytes: 7552
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const long double PI = (acos(-1));
#define rep(i, x, n) for (int i = x; i < (int)(n); i++)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
int main(){
    int k; sc(k);
    int a, b; sc(a), sc(b);
    if (b/k > a/k || a % k == 0 || b % k == 0) cout << "OK" << endl;
    else cout << "NG" << endl;
    return 0;
}

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

int main() {
  string T;
  cin >> T;
  
  for(int i = 0; i < T.size(); i++){
    if(T.at(i) == '?'){
      T.at(i) = 'D';
    }
  }
  
  cout << T << endl;
}

Measured memory_bytes: 3724
//Moh_K_Imar .......
//28/08/2020  ... 11,50.
//Ya Rab....
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
int main(){
    ll a,b;
    cin>>a>>b;
    if(b%a==0)cout<<a+b<<endl;
    else cout<<b-a<<endl;

    return 0;
}



Measured memory_bytes: 3600
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)


int main(){
	int n;
	cin>>n;
	vector<int> p(n),a(n),b(n);
	rep(i,n)cin>>p[i];
	
	rep(i,n)a[i] = b[i] = (i+1)*20001;
	reverse(all(b));
	
	
	rep(i,n)b[ p[i]-1 ]+=i;
	
	
	rep(i,n){
		if(i)cout<<" ";
		cout<<a[i];
	}
	cout<<endl;
	
	rep(i,n){
		if(i)cout<<" ";
		cout<<b[i];
	}
	cout<<endl;
}

Measured memory_bytes: 896
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <utility>
#include <climits>
#define REP(i, n) for(int i = 0; i < n; ++i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define F first
#define S second
#define OUT(x) cout << x << "\n"
#define int long long
using namespace std;
using point = pair< int,int >;

signed main() {
    int x;
    cin >> x;

    OUT(x / 11 * 2 + x % 11 / 6 + (x % 11 % 6 != 0));
    return 0;
}



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

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))

int get_int(void) {
  int num;
  scanf("%d", &num);
  return num;
}

int get_int2(int *a1, int *a2) {
  scanf("%d %d", a1, a2);
  return 0;
}

int get_int3(int *a1, int *a2, int *a3) {
  scanf("%d %d %d", a1, a2, a3);
  return 0;
}

int get_int4(int *a1, int *a2, int *a3, int *a4) {
  scanf("%d %d %d %d", a1, a2, a3, a4);
  return 0;
}

struct point2d {
    int x;
    int y;
};

enum direction {
    ENUM_RIGHT = 'R',
    ENUM_LEFT = 'L',
    ENUM_UP = 'U',
    ENUM_DOWN = 'D'
};

#define NUM_MAX 20000
static char buffer[NUM_MAX];
int bidx = 0;
void ccw(struct point2d start, struct point2d end) {
    int i;
    if(start.x < end.x && start.y < end.y) {
        for(i = start.x; i < end.x; i++) {
            buffer[bidx++] = ENUM_RIGHT;
        }
        for(i = start.y; i < end.y; i++) {
            buffer[bidx++] = ENUM_UP;
        }
    } else {
        for(i = start.x; i > end.x; i--) {
            buffer[bidx++] = ENUM_LEFT;
        }
        for(i = start.y; i > end.y; i--) {
            buffer[bidx++] = ENUM_DOWN;
        }
    }
}

int main(void) {
    struct point2d start;
    struct point2d end;
    get_int4(&start.x, &start.y, &end.x, &end.y);

    ccw(start, end);
    ccw(end, start);

    // round2
    // forth
    struct point2d start2 = {start.x, start.y-1};
    struct point2d end2 = {end.x+1, end.y};
    buffer[bidx++] = ENUM_DOWN;
    ccw(start2, end2);
    buffer[bidx++] = ENUM_LEFT;
    // back
    end2 = (struct point2d){end.x, end.y+1};
    start2 = (struct point2d){start.x-1, start.y};
    buffer[bidx++] = ENUM_UP;
    ccw(end2, start2);
    buffer[bidx++] = ENUM_RIGHT;

#ifdef DEBUG
    printf("length: %d\n", bidx);
#endif
    printf("%s\n", buffer);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
//Combination
long long extGCD(long long a,long long mod,long long &x,long long &y){
    if(mod==0){
        x=1;
        y=0;
        return a;
    }
    long long d=extGCD(mod,a%mod,y,x);
    y-=(a/mod)*x;
    return d;
}
long long invmod(long long a,long long mod){
    long long x,y;
    extGCD(a,mod,x,y);
    x%=mod;
    if(x<0)x+=mod;
    return x;
}
ll fac[2000010],finv[2000010],inv[2000010];
void combinit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    REP(i,2,2000010){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=invmod(i,mod);
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll comb(ll n,ll k){
    if(n<k)return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
ll rui(ll a,ll b){
    ll res=1;
    ll x=a;
    while(b){
        if(b&1)res=res*x%mod;
        x=x*x%mod;
        b/=2;
    }
    return res;
}
signed main(){
    ll n,a,b,c;cin>>n>>a>>b>>c;
    ll m=100*invmod(100-c,mod)%mod;
    ll ans=0;
    combinit();
    REP(i,n,2*n){
        ans=(ans+m%mod*i%mod*comb(i-1,n-1)%mod*(rui(a,n)%mod*rui(b,i-n)%mod+rui(a,i-n)%mod*rui(b,n)%mod)%mod*invmod(rui(a+b,i),mod))%mod;
    }
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
}

Measured memory_bytes: 47104
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int main() {
    int n, m; cin >> n >> m;
    if (m % n == 0) cout << n + m << endl;
    else cout << m - n << endl;
}

Measured memory_bytes: 3608
x = int(input())
a=b=c=0

for i in range(1,5):
    if i==1:
        d=x%10
    elif i==2:
        c=x%10
    elif i==3:
        b=x%10
    else:
        a=x%10

    x/=10
    x = int(x)


#apply 8 combinations

if a+b+c+d == 7:
    print(str(a) + "+" + str(b) + "+" + str(c) + "+" + str(d) + "=" + "7")
elif a+b+c-d == 7:
    print(str(a) + "+" + str(b) + "+" + str(c) + "-" + str(d) + "=" + "7")
elif a+b-c+d == 7:
    print(str(a) + "+" + str(b) + "-" + str(c) + "+" + str(d) + "=" + "7")
elif a+b-c-d == 7:
    print(str(a) + "+" + str(b) + "-" + str(c) + "-" + str(d) + "=" + "7")
elif a-b-c-d == 7:
    print(str(a) + "-" + str(b) + "-" + str(c) + "-" + str(d) + "=" + "7")
elif a-b-c+d == 7:
    print(str(a) + "-" + str(b) + "-" + str(c) + "+" + str(d) + "=" + "7")
elif a-b+c-d == 7:
    print(str(a) + "-" + str(b) + "+" + str(c) + "-" + str(d) + "=" + "7")
elif a-b+c+d == 7:
    print(str(a) + "-" + str(b) + "+" + str(c) + "+" + str(d) + "=" + "7")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rFOR(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,b) FOR(i,0,b)
#define INF 1e9
#define dump(x) cerr<< #x << " = "<<(x)<<endl
#define int long long

using ll = long long;
const ll mod = LLONG_MAX;

typedef pair<int,int> P;

int a[110];
bool isc[10];
int cnt,ret;
signed main(){
  int n;
  cin>>n;

  rep(i,n){
    cin>>a[i];
  }
  rep(i,10){
    isc[i]=false;
  }

  rep(i,n){
    if(a[i]<=399)isc[0]=true;
    else if(a[i]<=799)isc[1]=true;
    else if(a[i]<=1199)isc[2]=true;
    else if(a[i]<=1599)isc[3]=true;
    else if(a[i]<=1999)isc[4]=true;
    else if(a[i]<=2399)isc[5]=true;
    else if(a[i]<=2799)isc[6]=true;
    else if(a[i]<=3199)isc[7]=true;
    else cnt++;
  }

  rep(i,9){
    if(isc[i])ret++;
  }
    int t;
  if(ret>0)t=0;
  else t=1;

  cout<<ret+t<<" "<<ret+cnt<<endl;

}


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

int main(){
	int N;
	cin>>N;
	int A[N];
	for(int i=0;i<N;++i){
		cin>>A[i];
	}
	int ans=0;
	string evaluate="equal";
	for(int i=1;i<N;++i){
		if(A[i]-A[i-1]>0){
			if(evaluate=="smaller"){
				ans++;
				evaluate="equal";
			}
			else if(evaluate=="equal") evaluate="greater";
		}
		if(A[i]-A[i-1]<0){
			if(evaluate=="greater"){
				ans++;
				evaluate="equal";
			}
			else if(evaluate=="equal") evaluate="smaller";
		}
	}
	cout<<ans+1<<endl;
}


Measured memory_bytes: 640
#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
long long m,n;
int main()
{
  scanf("%lld %lld",&m,&n);
  if(m*10000<n)
    {
        printf("-1 -1 -1");
        puts("");
        return 0;
	}
    if(m*1000>n)
	{
        printf("-1 -1 -1");
        puts("");
        return 0;
    }
    if(n%1000!=0)
	{
        printf("-1 -1 -1");
        puts("");
        return 0;
    }
    for(int i=0;i<=m;i++)
     for(int j=0;j<=m;j++)
      for(int k=0;k<=m,i+j+k<=m;k++)
       {
            if(i+j+k==m && i*1000+j*5000+k*10000==n)
            {
                printf("%d %d %d",k,j,i);
                puts("");
                return 0;   
            }
       }
    printf("-1 -1 -1");
    puts("");
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using psi=pair<string,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void get(){}template<class H,class...T>void get(H&h,T&...t){cin>>h;get(t...);}
template<class T>void geti(T&a){for(auto&_:a)cin>>_;}
template<class T>void getii(T&a){for(auto&_:a)geti(_);}
void put(string d){}template<class H,class...T>void put(string d,H&h,T&...t){cout<<h;if(sizeof...(t))cout<<d;put(d,t...);}
template<class T>void puti(T&a,string d=" "){bool f=1;for(auto&_:a)cout<<(exchange(f,0)?"":d)<<_;cout<<endl;}
template<class T>void putii(T&a,string d=" "){for(auto&_:a)puti(_,d);}
#define dcl(...) ll __VA_ARGS__;get(__VA_ARGS__)
#define dclt(t,...) t __VA_ARGS__;get(__VA_ARGS__)

int main(){
	int n,ans=0;
	cin>>n;
	vi a(n);
	for(auto&&i:a)cin>>i;
	
	bool f=true;
	while(f){
		f=false;
		for(int j=n-1;j>0;j--){
			if(a[j]<a[j-1]){
				swap(a[j],a[j-1]);
				ans++;
				f=true;
			}
		}
	}
	puti(a);
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 3164