akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T &a){int t = 0;for(auto itr :a){if(t++)cout << " "; cout << itr;} cout <<endl; }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
auto divisors(int n){
    vector<int>v;
    for(int i = 1; i *  i <= n;i++){
        if(n % i)continue;
        v.push_back(i);
        if(i != 1 and i * i != n)
            v.push_back(n /i);
    }
    sort(v.begin(),v.end());
    v.push_back(n);
    return v;
}
vector<int> primeFactors(int n) {
    vector<int> v;
    int i = 2;
    while (i * i <= n) {
        if (n % i == 0) {
            v.push_back(i);
            n /= i;
        } else {
            i++;
        }
    }
    if(n != 1)v.push_back(n);
    return v;
}
signed main(){
    
    // number of diviros is calculated by exponential number
    // 10 = 5 * 2  , diviros(10).size = (5^0,5^1) * (2^0,2^1)
    // prime[val] value is how many val contained in n!
    
    int n; cin >> n;
    int prime[102] = {};
    prime[1] = 1;
    for(int i = 2; i <= n; ++i){
        for(auto e : primeFactors(i)){
            prime[e]++;
        }
    }
    int ans = 0;
    int tans = 0;
    rep(i,101){
        rep(j,101){
            if(i == j)continue;
            if(prime[i] >= 24 and prime[j] >= 2){
                ++ans;
            }
        }
    }
    rep(i,101)rep(j,101)rep(k,101){
        if(i == k or i == j or k == j)continue;
        if(prime[i] >= 2 and prime[j] >= 4 and prime[k] >= 4) {
            ++tans;
        }
    }
    int subans = 0;
    rep(i,101)subans += (prime[i] >= 74);
    rep(i,101)rep(j,101){
        if(i == j)continue;
        if(prime[i] >= 14 and prime[j] >= 4){
            ++subans;
        }
    }
    cout << tans / 2 + ans + subans << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;

typedef long double ld;
typedef pair<ll,ll> pp;
typedef tree<pp,null_type,less<pp>,rb_tree_tag,tree_order_statistics_node_update> super_set;

#define x1 dfds
#define y1 dsfdsfe
#define pb push_back
#define forn(i,n) for(ll i = 1;i<=n;++i)
#define fi first
#define sc second
#define endl '\n'
#define po(x) (1ll<<x)
#define log sdfdsfdsf

const ll DIM = 2E5+7;
const ll MOD = 1e9+123;

const ll INF = 1E17;
const ld eps = 0.00000000000001;
const ld PI = 3.14159265358979323846;
int getInt(int a = 0, int b = INT_MAX){
    static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution <int> (a, b)(rng);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<max(max(b*d,a*d),max(a*c,b*c))<<endl;
    return 0;
}


Measured memory_bytes: 3664
#include <iostream>
#include <cmath>

using namespace std;

int n;

int t[100010], x[100010], y[100010];

int main() {
    cin >> n;
    t[0] = 0;
    x[0] = 0;
    y[0] = 0;
    for (int i = 0; i < n; i++) {
        cin >> t[i + 1] >> x[i + 1] >> y[i + 1];
    }
    for (int i = 0; i < n; i++) {
        if ((abs(x[i] - x[i + 1]) + abs(y[i] - y[i + 1])) % 2 != (t[i + 1] - t[i]) % 2) {
            cout << "No" << endl;
            return 0;
        }
        if (abs(x[i] - x[i + 1]) + abs(y[i] - y[i + 1]) > t[i + 1] - t[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 1408
sd = input()
t = input()

def compaierStr(expected: list, actual: list) -> bool:
    for e, a in zip(expected, actual):
        if e != a and a != "?":
            return False

    return True

candidates = []
for i in range(len(sd)-len(t)+1):
    if compaierStr(t, sd[i:i+len(t)]):
        candidates.append((sd[:i] + t + sd[i+len(t):]).replace("?", "a"))

if len(candidates) == 0:
    print("UNRESTORABLE")
else:
    ans = "z"
    for _c in candidates:
        if _c < ans:
            ans = _c

    print(ans)


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

int main(){
    string w;
    cin >> w;
    int ans = 0;
    if(w[0] == 'R'){
        ans++;
    }
    for(int i = 1;i < w.size();i++){
        if(w[i - 1] == 'R' && w[i] ==  'R') ans++;
        else if(w[i] == 'R') ans = max(ans, 1);
    }

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

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

int n, k, a[200005];
long long mx, s;
double ans, add;

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    for (int i = 0; i < k; i++){
        s += a[i];
        mx = s;
    }
    for (int i = k; i < n; i++){
        s -= a[i-k];
        s += a[i];
        mx = max(mx, s);
    }
    if (mx % 2 == 1) add += 0.5;
    mx /= 2;
    if (k % 2 == 1) add += 0.5;
    k /= 2;
    ans = mx;
    ans += k;
    ans += add;
    cout << fixed << setprecision(10);
    cout << ans << "\n";
}


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

using ll = long long;

const ll MOD = 1e9 + 7;
int N;
map<int, int> mp; // map[x]: 素数xが何個あるか？

int main() {
   cin >> N;

   for (int i = 2; i <= N; i++) { // N,N-1,N-2,..について各素数の個数を求める
      int x = i; // iを変更するとまずいのでxに値をコピー
      for (int j = 2; j <= x; j++) { // 素数jの個数を求める
         while (x % j == 0) {
            x /= j;
            mp[j]++;
         }
      }
   }

   ll ans = 1;
   for (auto x : mp) {
      ans = ((ans%MOD) * (x.second+1)%MOD) % MOD;
   }

   cout << ans << endl;

   return 0;
}

Measured memory_bytes: 256
#include <cstdio>
    #include <string>
    #include <vector>
    #include <iostream>
    using namespace std;
     
    int main(int argc, char const *argv[]) {
      vector<char> S;
      bool s[26];
      for (int i = 0; i < 26; i++) {
        s[i]=false;
      }
      char c;
      while((c = getchar())!=EOF){
        S.push_back(c);
      }
      for(auto itr = S.begin(); itr != S.end(); ++itr) {
        s[(*itr)-(char)'a'] = true;
      }
      for (char i = 0; i < 26; i++) {
        if(s[i]==false){
          putchar('a' + i);
          putchar('\n');
          return 0;
        }
      }
      printf("None\n");
      return 0;
    }


Measured memory_bytes: 888
#include <stdio.h>
#include <stdint.h>

uint32_t a[200000];

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

  scanf("%d\n", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d ", &a[i]);
  }

  if (n == 1) {
    printf("%d", a[0]);
  }
  else if (n % 2) {
    for (int i = n - 1; i >= 0; i -= 2)
      printf("%d ", a[i]);
    for (int i = 1; i < n; i += 2)
      printf("%d ", a[i]);
  }
  else {
    for (int i = n - 1; i >= 0; i -= 2)
      printf("%d ", a[i]);
    for (int i = 0; i < n; i += 2)
      printf("%d ", a[i]);
  }
  printf("\n");
}

Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

int H, W;
char c[610][610];

void rot(){
    char t[W][H];
    rep(i, H)rep(j, W) t[j][i] = c[i][j];
    swap(H, W);
    rep(i, H)rep(j, W) c[i][j] = t[i][j];
}

lint f(int flag){
    lint ret = 0;
    int cnt[H][W+1];
    rep(i, H){
        cnt[i][0] = 0;
        rep(j, W) cnt[i][j+1] = cnt[i][j] + (c[i][j] == '#');
    }
    rep(i, H){
        rep(s, W-1)if(c[i][s] == '#')For(t, s+1, W)if(c[i][t] == '#'){
            int d = t - s;
            if(i-d >= 0) ret += cnt[i-d][t+1] - cnt[i-d][s];
            if(i+d < H) ret += cnt[i+d][t+1] - cnt[i+d][s];

            if(flag){
                if(i-d >= 0) ret -= (c[i-d][s] == '#') + (c[i-d][t] == '#');
                if(i+d < H) ret -= (c[i+d][s] == '#') + (c[i+d][t] == '#');
            }
        }
    }
    return ret;
}

int main(){
    int h, w;
    scanf("%d%d", &h, &w);
    H = h + w, W = 2 * max(h, w);
    rep(i, H)rep(j, W) c[i][j] = '.';
    rep(i, h)rep(j, w){
        char t;
        scanf(" %c", &t);
        c[i+j][i-j+W/2] = t;
    }
    lint ans = f(0);
    rot();
    ans += f(1);
    printf("%lld\n", ans);
}

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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int A, B, K;
  cin >> A >> B >> K;
  int cnt = 0;
  for (int i = min(A,B); i >= 1; i--)
  {
    if (A % i == 0 && B % i == 0)
    {
      cnt++;
    }
    if (cnt == K)
    {
      cout << i << endl;
      return 0;
    }
    
  }

  return 0;
}


Measured memory_bytes: 3632
#include <stdio.h>

int main(void) {
	int num1, num2, num3, dummy;
	
	scanf("%d%d%d", &num1, &num2, &num3);
	
	if(num1 > num2) {
	    dummy = num1;
	    num1 = num2;
	    num2 = dummy;
	}
	if(num2 > num3) {
	    dummy = num2;
	    num2 = num3;
	    num3 = dummy;
	}
	if(num1 > num2) {
	    dummy = num1;
	    num1 = num2;
	    num2 = dummy;
	}
	
	printf("%d %d %d\n", num1, num2, num3);
	return 0;
}




Measured memory_bytes: 1904
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int h[100100];
    for(int i=0; i<n; i++){
        cin >> h[i];
    }
    int ans = 0;
    int tmp = 0;
    for(int i=0; i<n-1; i++){
        if(h[i]>=h[i+1]){
            tmp++;
        }else{
            ans = max(ans, tmp);
            tmp = 0;
        }
    }
    ans = max(ans, tmp);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mk make_pair
int gcd(int a,int b){
    if(b==0)
     return a;
    return gcd(b,a%b);
}
int main(){
    int t;
    cin>>t;
    if(t%1000==0)
     cout<<0<<endl;
    else
     cout<<1000-t%1000;
}


Measured memory_bytes: 3592
/*
 * atcoder/abc133_2nd/d.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

int N;
vector<ll> A, B;
ll b_1 = 0;
void solve() {
  cin >> N;
  A.resize(N);
  B.resize(N);
  loop(n,0,N) {
    cin >> A[n];
    B[0] += A[n];
    if (n%2==1) B[0] -= 2 * A[n];
  }

  loop(b_i,1,N) {
    B[b_i] = 2 * A[b_i-1] - B[b_i-1];
  }
  for (auto&& b:B) cout << b << " ";
  cout << endl;
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 2944
s = int(input())
s1= s//100
s2= s%100
if (1 <= s1 and s1 <= 12) and (1 <= s2 and s2 <= 12):
  print('AMBIGUOUS')
elif 1 <= s1 and s1 <= 12:
  print('MMYY')
elif 1 <= s2 and s2 <= 12:
  print('YYMM')
else:
  print('NA')

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

using namespace std;
typedef long long ll;
const int MAXN = 1010;

int N;
char res[MAXN][MAXN];

void place (int x, int y, int d)
{
    char g = 'a' + (5 * (x % 5) + y % 5);
    if (d)
        res[x][y] = res[x+1][y] = g;
    else
        res[x][y] = res[x][y+1] = g;
}

void place3easy (int x, int y)
{
    place (x, y, 1);
    place (x + 2, y + 1, 0);
}

void place3easy (int x)
{
    place3easy (x, x);
}

void place3k (int x, int n)
{
    if (n == 6)
    {
        for (int i = 0; i < 3; i++)
        {
            place (x + 2 * i, x, 1);
            place (x + 2 * i, x + 5, 1);
            place (x + 2 * i, x + 1, 0);
            place (x + 2 * i + 1, x + 3, 0);
        }
        return;
    }
    for (int i = 0; i < n; i += 3)
    {
        for (int j = 0; j < 3; j++)
            place3easy (x + i, x + (i + 3 * j) % n);
    }
}

void place4 (int x)
{
    place (x, x, 1);
    place (x, x + 1, 1);

    place (x, x + 2, 0);
    place (x + 1, x + 2, 0);

    place (x + 2, x + 2, 1);
    place (x + 2, x + 3, 1);

    place (x + 2, x, 0);
    place (x + 3, x, 0);
}

void place5 (int x)
{
    place (x, x, 0);
    place (x, x + 2, 0);
    place (x + 1, x, 1);
    place (x + 3, x, 1);
    place (x, x + 4, 1);
    place (x + 2, x + 4, 1);
    place (x + 4, x + 1, 0);
    place (x + 4, x + 3, 0);
    place (x + 1, x + 1, 1);
    place (x + 3, x + 2, 0);
}

void place7 (int x)
{
    place (x, x, 1);
    place (x + 2, x + 1, 1);
    place (x + 4, x, 1);
    place (x + 4, x + 1, 1);
    place (x + 6, x, 0);

    place (x, x + 2, 0);
    place (x + 2, x + 2, 0);
    place (x + 4, x + 2, 0);
    place (x + 1, x + 4, 0);
    place (x + 3, x + 4, 0);
    place (x + 6, x + 4, 0);

    place (x, x + 6, 1);
    place (x + 2, x + 6, 1);
    place (x + 5, x + 6, 1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    
    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            res[i][j] = '.';
    if (N == 2)
    {
        cout << "-1\n";
        return 0;
    }

    if (N % 3 == 0)
    {
        for (int i = 0; i < N; i += 3)
            place3easy (i);
    }
    else if (N % 3 == 1)
    {
        if (N == 7)
        {
            place7(0);
        }
        else
        {
            place4(0);
            if (N > 4)
                place3k (4, N - 4);
        }
    }
    else
    {
        if (N == 8)
        {
            place4(0);
            place4(4);
        }
        else
        {
            place5(0);
            if (N > 5)
                place3k (5, N - 5);
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << res[i][j];
        }
        cout << "\n";
    }
}

Measured memory_bytes: 2176
/*==============================================*\
Codeforces ID:    mdshihab
                                                  |
Name:     Md. Shihabul Minhaz                     |
Study:      CSE, JKKNIU                           |
Address:  Trishal, Mymensingh, Bangladesh         |
                                                  |
 mail:   mdshihabul20171@gmail.com                |
 FB  :   fb.com/mdshihabul.minhaz.7               |
 github: Shihabulminhaz                           |
stopstalk :  mdshihab                             |
                                                  |
@uthor   Md. Shihabul Minhaz (shihab)             |
\*===============================================*/


#include<bits/stdc++.h>
using namespace std;
#define fi(a) scanf("%d",&a);
#define fli(a) scanf("%ld",&a);
#define fll(a) scanf("%lld",&a);
#define pi(a) printf("%d\n",a);
#define ppi(i,a) printf("Case %d: %d\n",i,a);
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
void FI()
{
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\SHIHAB\\Desktop\\input.in","r",stdin);
#endif // ONLINE_JUDGE
}

int main()
{
    fast
   // FI(); /// skip this line for compile
    int n,a,cnt=0;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a;
        if(a%2==1 && i%2==1) cnt++;
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 3632
import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import java.io.*;

public class Main {

	List<Integer>[] graph;
	int[] col;
	boolean fail = false;
	
	void dfs(int u, int c){ 
		col[u] = c;
		for (int v : graph[u]) {
			if (col[v] == -1) {
				dfs(v, 1 - c);
			} else if (col[v] == col[u]) {
				fail = true;
			}
		}
	}
	
	void solve() {
		int n = in.nextInt();
		graph = new List[n];
		for (int i  =0; i < n; i++) {
			graph[i] = new ArrayList<>();
		}
		int m = in.nextInt();
		for (int  i= 0; i < m; i++) {
			int from = in.nextInt() - 1, to = in.nextInt() - 1;
			graph[from].add(to);
			graph[to].add(from);
		}
		col = new int[n];
		Arrays.fill(col, -1);
		dfs(0, 0);
		if (fail) {
			out.println(1L * n * (n - 1) / 2 - m);
		} else {
			long c = IntStream.of(col).filter(x -> (x == 0)).count();
			out.println(1L * c * (n - c) - m);
		}
	}

	FastScanner in;
	PrintWriter out;

	void run() {
		in = new FastScanner();
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastScanner(String s) {
			try {
				br = new BufferedReader(new FileReader(s));
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}

		public String nextToken() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
				}
			}
			return st.nextToken();
		}

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

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

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

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


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


int main()
{
    string s;
    cin >> s;
    ll counter = 0;
    s = s.substr(0, s.size()-2);
    while (s.size() > 0) {
        if (s.substr(0, s.size() / 2) == s.substr(s.size() / 2, s.size() / 2)) {
            cout << s.size() << endl;
            return 0; 
        } else {
            s = s.substr(0, s.size()-2);
        }
    }
    return 0;
}

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

int main() {
	// your code goes here
	int n;
	cin>>n;
	int arr[n];
	for(int i=0;i<n;i++)
	cin>>arr[i];
	int dp[n]={0};
	dp[0]=0;
	dp[1]=abs(arr[1]-arr[0]);
//	dp[1]=abs(arr[2]-arr[0]);
	for(int i=2;i<n;i++)
	dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i]-arr[i-2]));
	
	cout<<dp[n-1]<<" ";
	return 0;
}

Measured memory_bytes: 1024
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

#        tmp = list([int(i) for i in (list(str(i)))])

def main():
    n,a,b = map(int,input().split())
    numbers=[]
    tmp=0

    for i in range(1,n+1):
        if i >=a and i <=b and i < 10:
            numbers.append(i)
        else:
            tmp_array=list(map(int,list(str(i))))
            if len(tmp_array) > 1:
                for j in tmp_array:
                    tmp+=j
                if tmp >=a and tmp <=b:
                    numbers.append(i)
                tmp=0
            else:
                continue
    print(sum(numbers))
            
if __name__=="__main__":
    main()

Measured memory_bytes: 9324
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <queue>
#include<iomanip>
#include <cmath>
#include <set>
#include <unordered_set>

#define ABS(x) ((x)>0?(x):-(x))
#define MIN(x,y) ((x)>(y)?(y):(x))
#define MAX(x,y) ((x)<(y)?(y):(x))

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

#define INF 1000000000

using namespace std;
typedef long long ll;

ll newton(long long int a, long long int  b)
{
	if(a==b)
		return a;
	while(a != 0 && b != 0)
	{
		if(a > b)
		{
			b += a;
			a = b-a;
			b -= a;
		}
		b %= a;
	}
	return a;
}

struct UnionFind {
	vector<int> p;
	UnionFind(int N):p(N)
	{
		for(int i=0; i< N; i++)
		{
			p[i] = i;
		}
	}
	int root(int x)
	{
		if(p[x] == x)
			return x;
		return p[x] = root(p[x]);
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if(rx == ry) return;
		p[rx] = ry;
	}
	bool issame(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

//大きな数に対する割り算をするとき、MODを指定することで掛け算の値に変換できる

ll div2mul_calc(ll a, ll b, ll m)
{
	if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll d = div2mul_calc(a, b / 2, m);
        return (d * d) % m;
    } else {
        return (a * div2mul_calc(a, b - 1, m)) % m;
    }
}
ll div2mul(ll n, ll mod)
{
	return div2mul_calc(n, mod-2, mod);
}

ll twoRow(ll a, ll b, ll mod)
{
	ll ret = 1;
	for(ll i = 1 ;i <= a+b;++i)
	{
		ret *= i;
		ret %= mod;
	}
	for(ll i = 1 ;i <= a;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	for(ll i = 1 ;i <= b;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	return ret;
}

struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());
  return (ret);
}
/*
小数の桁数を指定する
	cout << setprecision(8)<< mp[0]-mx << endl;
*/

int main()
{
	ll i,j,k,a,b;//,ans=0;
	char c;
	ll N,M,T, X,Y;
	ll tm[100010] = {0};
	ll mp[100010] = {0};
	ll ans;
	ll cur;
	ll mod = 1000000000+7;
	cin >> N;
	for(i=0;i<N;++i)
	{
		cin >> tm[i];
	}
	j = 1;
	for(i=N-1;i>0;--i)
	{
		mp[i] = j;
		j *= i;
		j %= mod;
	}
	ans = 0;
	X = 1;
	T = 1;
	Y = 1;
	M = 1;
	for(i=1;i<N;++i)
	{
		j = mp[i];
		j *= X;
		j %= mod;
		j *= tm[i]-tm[i-1];
		j %= mod;

		ans += j;
		ans %= mod;

		if(i > 2)
		{
			M *= (i-1);
			M %= mod;
		}

		T *= (i+1);
		T += mod-M;
		T %= mod;

		X *= (i+1);
		X += T;
		X %= mod;
	}
	cout << ans << endl;

	return 0;
}




















Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();

        int[] num = new int[n];
        for (int i=0;i<n;i++){
            num[i] = cin.nextInt();
        }

        int res= 0;
        for (int i=0;i<n;i++){
            res = res+num[i];
        }

        System.out.println(res-n);

    }

}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll N;
ll A[200005];
ll ans[200005];
vector<ll> G[200005];
ll dp[200005];

void dfs(ll now,ll par){
    ans[now] = lower_bound(dp,dp+N+3,LLONG_MAX)-dp; 
    for (int i = 0;i < G[now].size();i++){
        if(G[now][i] == par) continue;
        ll to = G[now][i];
        ll idx = lower_bound(dp,dp+N+3,A[to])-dp;
        ll num = dp[idx];
        dp[idx] = A[to];
        dfs(to,now);
        dp[idx] = num;
    }
}

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

    cin >> N;

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

    for (int i = 0;i < N-1;i++){
        ll a,b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    fill(dp,dp+N+3,LLONG_MAX);

    *lower_bound(dp,dp+N+3,A[1]) = A[1];
    dfs(1,-1);

    for (int i = 1;i <= N;i++){
        cout << ans[i] << endl;
    }


    return 0;

}

Measured memory_bytes: 33568
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

ll n;
ll a[200010][2];

using T = tuple<ll, ll, ll>;

ll mv(set<T> &ss){
  return get<0>(*ss.begin());
}

ll Mv(set<T> &ss){
  auto ite = ss.end();
  ite--;
  return get<0>(*ite);
}

int main(){

  n = in();
  REP( i , n ){
    ll s = in();
    ll t = in();
    a[i][0] = min(s, t);
    a[i][1] = max(s, t);
  }

  ll mx = INFLL, Mx = -INFLL;
  ll my = INFLL, My = -INFLL;
  REP( i , n ){
    chmin(mx, a[i][0]);
    chmax(Mx, a[i][0]);
    chmin(my, a[i][1]);
    chmax(My, a[i][1]);
  }

  ll ans = (Mx - mx) * (My - my);

  ll lr = My - mx;

  vector<T> v;
  REP( i , n ){
    REP( j , 2 ){
      v.pb(a[i][j], i, j);
    }
  }
  SORT(v);

  if(get<1>(v[0]) == get<1>(v[2*n-1])){
    cout << ans << endl;
    return 0;
  }

  set<T> ss;
  REP( i , 2*n-1 ){
    ll s, t, u;
    tie(s, t, u) = v[i];
    if(u == 0){
      ss.insert(v[i]);
    }
  }

  REP( i , 2*n-1 ){
    ll s, t, u;
    tie(s, t, u) = v[i];
    if(u == 1){
      break;
    }
    ss.erase(ss.find(v[i]));
    ss.insert(T(a[t][1], t, 1LL));
    chmin(ans, lr * (Mv(ss) - mv(ss)));
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 28136
import java.io.*;
import java.util.*;

public class Main{
    
    public static void main(String[] arg){
        Scanner scan =new Scanner(System.in);
        int r=scan.nextInt();
        int d=scan.nextInt();
        int x=scan.nextInt();

        for(int i=0;i<10;i++){
            x=r*x-d;
            System.out.println(x);

        }

    }
}

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

int main()
{
    int N, X, Y;
    cin >> N >> X >> Y;
    X--;
    Y--;
    bool dis[N][N] = {};
    vector<pair<int, int>> V;
    int counter = 0;
    rep(i, N - 1)
    {
        dis[i][i + 1] = true;
        counter++;
        V.push_back(make_pair(i, i + 1));
    }
    dis[X][Y] = true;
    V.push_back(make_pair(X, Y));
    counter++;
    cout << counter << endl;
    vector<pair<int, int>> W;

    for (int i = 2; i < N; i++)
    {
        counter = 0;
        W = {};
        for (auto v : V)
        {
            int v1 = v.first;
            int v2 = v.second;
            int v1p = v1 + 1;
            int v1m = v1 - 1;
            int v2p = v2 + 1;
            int v2m = v2 - 1;
            if (v2p < N)
            {
                if (dis[v1][v2p] == false && v1 != v2p)
                {
                    counter++;
                    dis[v1][v2p] = true;
                    W.push_back(make_pair(v1, v2p));
                }
            }
            if (dis[v1][v2m] == false && v1 != v2m)
            {
                counter++;
                dis[v1][v2m] = true;
                W.push_back(make_pair(v1, v2m));
            }

            if (v1m >= 0)
            {
                if (dis[v1m][v2] == false && v1m != v2)
                {
                    counter++;
                    dis[v1m][v2] = true;
                    W.push_back(make_pair(v1m, v2));
                }
            }
            if (dis[v1p][v2] == false && v1p != v2)
            {
                counter++;
                dis[v1p][v2] = true;
                W.push_back(make_pair(v1p, v2));
            }
        }
        cout << counter << endl;
        swap(V, W);
    }
}

Measured memory_bytes: 4224
from bisect import*
from numpy import*
n=int(input())
*a,=map(int,input().split())
*b,=map(int,input().split())
x=array(a)-array(b)
y=x[x<0]
z=sorted(x[x>0],reverse=1)
#print(y,z)
if len(y)==0:
    print(0)
elif sum(y)+sum(z)<0:
    print(-1)
else:
    ans=len(y)
    ans+=bisect_left(cumsum(z),-sum(y))+1
    print(ans)

Measured memory_bytes: 27156
"""時計回り／反時計回りのどちらで行くかを考えると終わるのでは
"""
K, N = (int(x) for x in input().split(' '))
A = [int(x) for x in input().split(' ')]
#各家の間の距離も求めてGに追加していく
G = []
for i in range(len(A)-1):
  G += [A[i+1]-A[i]]
#先頭と最後の1軒距離を求める
G += [(K - (A[N-1] - A[0]))]
#一番幅の広い距離を避けて一周回る
print(sum(G)-max(G))

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

int main(){
  int n, x, sum;
  
  for(;;){
    int count = 0;
    cin >> n >> x;
    if( n == 0 && x == 0 ) break;
    
    for(int i = 1; i <= n; i++) {
      for( int j = i + 1; j <= n; j++ ){
        for( int k = j + 1; k <= n; k++ ){
          if( i == j || j == k || k == i ) break;
          sum = i + j + k;
          if( sum == x ) count = count + 1;
        }
      }
    }
    cout << count << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3080
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <ctime>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to
#define mp(a, b) make_pair(a, b)

using namespace std;

const int N = 100010;

vector<int> t[N], t0[N];

int calc(int x)
{
	if (!t[x].size()) return 0;
	int ret = 0, len = t[x].size();
	Rep0(i, len - 1) t0[x].push_back(calc(t[x][i]));
	sort(t0[x].begin(), t0[x].end());
	Rep0(i, len - 1) ret = max(ret, t0[x][i] + len - i);
	return ret;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 2; i <= n; i ++) {
		int x;
		scanf("%d", &x);
		t[x].push_back(i);
	}
	printf("%d\n", calc(1));
	
	return 0;
}

Measured memory_bytes: 20608
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <utility>
#include <map>
const int N=1e5+5;
typedef long long ll;
using namespace std;

int main() {
	int a,b,c,k;
	cin >> a >> b >> c >> k;
	int ans=0;
	if (a>=k) cout << k;
	else {
		ans+=a;
		k-=a;
		if (b>=k) cout << ans;
		else {
			k-=b;
			ans-=k;
			cout << ans;
		}
	}
	return 0;
}



Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <math.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001;
const int mINF = -1001001001;


int main() {
int a,b;
cin >> a >> b;
int ans = a+b;
if(ans>=24) ans-=24;
cout << ans << endl;
return 0;
}


Measured memory_bytes: 256
// https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_b

#include "algorithm"
#include "cmath"
#include "functional"
#include "iomanip"
#include "iostream"
#include "numeric"
#include "queue"
#include "set"
#include "string"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
#define repr(i, from) for (ll i = from - 1; i >= 0; --i)
#define all(vec) vec.begin(), vec.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

const ll INF = 1e18;

void solve() {
  ll N;
  cin >> N;

  rep(num, N + 1) {
    double taxed = num * 1.08;
    if (floor(taxed) == N) drop(num);
  }

  drop(":(");
}

void solve2() {
  ll N;
  cin >> N;

  ll cand1 = floor(N / 1.08);
  ll cand2 = floor((N + 1) / 1.08);

  if (cand1 + cand1 * 8 / 100 == N) drop(cand1);
  if (cand2 + cand2 * 8 / 100 == N) drop(cand2);
  drop(":(");
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve2();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

template <typename T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <typename T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[]args) {
		Scanner input=new Scanner(System.in);
		String c=input.next();
		if(c.contentEquals("a")||c.contentEquals("i")||c.contentEquals("u")||c.contentEquals("e")||c.contentEquals("o")) {
			System.out.println("vowel");
		}else{
			System.out.println("consonant");
		}
	}
}

Measured memory_bytes: 26980
//When I was writing this only God and I knew what it is
//Now, only The_Blitz know...

#pragma GCC optimize ("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define pb push_back
#define FER(i,a,b) for(int i = int(a); i < int(b); ++ i)
#define IFR(i,a,b) for(int i = int(a); i >= int(b); -- i)
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> ii;

const int N = 1e5 + 2;
const int Mod = 1e9 + 7;

int main(){
	string s; cin >> s;
	int a, z;
	FER(i, 0, sz(s)) if(s[i] == 'A'){
		a = i; break;
	}
	IFR(i, sz(s) - 1, 0) if(s[i] == 'Z'){
		z = i; break;
	}
	cout << z - a + 1 << endl;
	return 0;
}


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

using namespace std;
 
#define PB(x)	push_back(x)
#define ALL(x)	(x).begin(), (x).end()
#define ALLR(x)	(x).rbegin(), (x).rend()
#define MP(x)	make_pair(x)
 
#define debug(_x)		cerr << #_x << '=' << _x << endl;
#define debug2(_x, _y)	cerr << #_x << '=' << _x << ' ' << #_y << '=' << _y << endl;
#define debugn(_a)		cerr << #_a << ": "; for (const auto _x: _a) cerr << _x << ' '; cerr << endl;

#define FAST_IO ios::sync_with_stdio(false); cin.tie(0)

#define int long long int

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef unsigned long long ull;

const int INF = LONG_LONG_MAX;
const int NINF = LONG_LONG_MIN/2;

const double PI = 3.14159265358979311;
int32_t main() {
	FAST_IO;
	
	int n;
	cin >> n;
	
	int a[n-1];
	for (int& x: a) cin >> x;
	
	map<int, int> m;
	for (int x: a) {
		m[x]++;
	}
	
	vi ans(n, 0);
	for (ii p: m) {
		ans[p.first-1] = p.second;
	}
	
	for (int x: ans) cout << x << endl;
}

// g++ -Wall -Wextra -Wshadow -fsanitize=undefined


Measured memory_bytes: 18748
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

# Written by NoKnowledgeGG @YlePhan

#import math
#mod = 10**9+7



def main():
  a,b,c = map(int,input().split())
  dic = {}
  ans = 0
  i = 1
  while True:
    ans += a
    a_m = ans % b
    if ans % b == c:
      print('YES')
      exit()
    if not str(a_m) in dic.keys():
      dic[str(a_m)] = 1
    else:
      #print(dic)
      print('NO')
      exit()
    i +=1
  
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 3064
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))
    temp = [-1] + list(map(int, readline().split()))
    a = {i: temp[i] for i in range(1, n + 1)}

    cur = 1
    cnt = 0
    visited = {i: -1 for i in range(1, n + 1)}
    visited[1] = 0

    while True:
        cnt += 1
        cur = a[cur]
        if visited[cur] == -1:
            visited[cur] = cnt
        else:
            break

    start = cur
    st = visited[cur]
    gt = cnt
    period = gt - st
    t = k

    if t < st:
        cur = 1
        cnt = 0
        while cnt != t:
            cnt += 1
            cur = a[cur]
    else:
        t -= st
        t %= period
        cur = start
        cnt = 0
        while cnt != t:
            cnt += 1
            cur = a[cur]

    print(cur)


if __name__ == '__main__':
    main()


Measured memory_bytes: 144532
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#define lli long long int
#define uli unsigned long long int
#define inf 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define per(i,m,n) for(lli i=m-1;i>=n;i--)
#define st(n) sort(n.begin(), n.end())
#define rev(n) reverse(n.begin(),n.end())
#define ou(S) cout << S << endl
using namespace std;
int main(){
  int n,k,x,y;
  cin>>n>>k>>x>>y;
  if(n>=k)
    cout<<k*x+(n-k)*y<<endl;
  else
    cout<<n*x<<endl;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<string> mine(H);
  for (int k = 0; k < H; k++){
    cin >> mine.at(k);
  }
  
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      
      if (mine.at(i).at(j) == '#')
        continue;
      else {
        int count = 0;
        if (i > 0 && j > 0)
          if (mine.at(i-1).at(j-1) == '#')
            count ++;
        if (i > 0)
          if (mine.at(i-1).at(j) == '#')
            count ++;
        if (i > 0 && j < W-1)
          if (mine.at(i-1).at(j+1) == '#')
            count ++;
        if (j > 0)
          if (mine.at(i).at(j-1) == '#')
            count ++;
        if (j < W-1)
          if (mine.at(i).at(j+1) == '#')
            count ++;
        if (i < H-1 && j > 0)
          if (mine.at(i+1).at(j-1) == '#')
            count ++;
        if (i < H-1)
          if (mine.at(i+1).at(j) == '#')
            count ++;
        if (i < H-1 && j < W-1)
          if (mine.at(i+1).at(j+1) == '#')
            count ++;
        
        if (count == 0)
          mine.at(i).at(j) = '0';
        if (count == 1)
          mine.at(i).at(j) = '1';
        if (count == 2)
          mine.at(i).at(j) = '2';
        if (count == 3)
          mine.at(i).at(j) = '3';
        if (count == 4)
          mine.at(i).at(j) = '4';
        if (count == 5)
          mine.at(i).at(j) = '5';
        if (count == 6)
          mine.at(i).at(j) = '6';
        if (count == 7)
          mine.at(i).at(j) = '7';
        if (count == 8)
          mine.at(i).at(j) = '8';
      }
      
    }
  }
  
  for (int k = 0; k < H; k++){
    cout << mine.at(k) << endl;
  }
  
}


Measured memory_bytes: 256
// 132_D_Blue_and_Red_Balls.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{

	//解法
	//特殊な分割数を使用して解く
	//K個の青玉をi回で取りきる　⇔ K個の青玉をi個のグループに分ける（区切りは赤玉のグループ）
	//ただし、問題設定上、青玉は並べられているため、i個の各グループは区別される必要がある。
	//
	//例）青玉4個を3回で取りきる方法は(1,1,2)、(1,2,1)、(2,1,1)の3通り。
	//
	//通常用いられる分割数は各グループを区別しない考え方のため注意。
	//
	//また、区切りとなる赤玉も個数と位置による場合の数があるため、最終解答は
	//
	//解答 = 青玉の場合の数 * 赤玉の場合の数
	//
	//となる。

	int n, k = 0;
	cin >> n >> k;

	int redBallCount = n - k;

	int maxBallCount = max(k, redBallCount);

	const long long int MOD = 1000000000 + 7;


	//dp[i][j]:i個の玉の列をj個の部分列に分割する方法の場合の数
	//ちょっと大きめに配列作成
	long long int** dp = new long long int* [maxBallCount + 10];
	for (int i = 0; i <= maxBallCount; i++)
	{
		dp[i] = new long long int[maxBallCount + 10]();
	}

	//決めごとで1にする
	dp[0][0] = 1;

	//初期化
	for (int i = 1; i <= maxBallCount; i++)
	{
		//0個には分割できない
		dp[i][0] = 0;

		//1個に分割する方法は1通り
		dp[i][1] = 1;
	}

	//分割数の計算
	//計算方法（4個の玉を3個のグループに分ける場合の例）→答えは、(1,1,2)、(1,2,1)、(2,1,1)の3通り。
	//1.先頭の玉1個と残りの3個を分けて考える
	//
	//〇|〇〇〇
	//
	//この時、
	//
	//・先頭の玉のグループは1つのみ→(1,1,2)、(1,2,1)
	//・先頭の玉のグループは2個以上→(2,1,1)
	//
	//に場合分けされる。これは言い換えると、
	//
	//・残り3つの玉を2つのグループに分ける（先頭の1個と残りの3個を区切る）
	//・残り3つの玉を3つのグループに分ける（先頭の1個に2個目の玉が続く）
	//
	//となるので、再帰的に計算できる。
	//
	//4個の玉を3個のグループに分ける場合の数 = 3個の玉を2個のグループに分ける場合の数 + 3個の玉を3個のグループに分ける場合の数
	//
	//注意）玉の個数 = グループ数の場合は1通り、玉の個数 < グループ数の場合は0通り（不可能）。

	//玉の個数のループ
	for (int i = 2; i <= maxBallCount; i++)
	{
		//グループ数のループ
		for (int j = 1; j <= i; j++)
		{
			dp[i][j] = dp[i - 1][j] % MOD + dp[i - 1][j - 1] % MOD;
		}
	}


	//赤玉と青玉の関係
	//赤玉の列が青玉をi個に区切るが、以下の4パターンが考えられる。
	//1.両端が赤　　　　　：赤|青|・・・|青|赤
	//2.左端が赤、右端が青：赤|青|・・・|青
	//3.左端が青、右端が赤：   青|・・・|青|赤
	//4.両端が青　　　　　：   青|・・・|青
	//以上4パターンを合計する。

	for (int i = 1; i <= k; i++)
	{
		long long int count1 = dp[k][i] % MOD * dp[redBallCount][i + 1] % MOD;
		long long int count2 = dp[k][i] % MOD * dp[redBallCount][i + 0] % MOD;
		long long int count3 = dp[k][i] % MOD * dp[redBallCount][i + 0] % MOD;
		long long int count4 = dp[k][i] % MOD * dp[redBallCount][i - 1] % MOD;

		long long int countTotal = 0;
		countTotal += count1;
		countTotal %= MOD;
		countTotal += count2;
		countTotal %= MOD;
		countTotal += count3;
		countTotal %= MOD;
		countTotal += count4;
		countTotal %= MOD;

		cout << countTotal << endl;
	}
	
	return 0;
}


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

int main () {
  string Atcoder, s, Contest;
  cin >> Atcoder >> s >> Contest;
  
  char a = Atcoder.at(0);
  char x = s.at(0);
  char c = Contest.at(0);
  
  cout << a << x << c << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>
#include <iostream>
#include <string>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }

int N, K, A[567],a[567];

vector<int> DivList(int n) {
	vector<int> ret;
	int t = sqrt(n);
	rep(i, t) {
		if (n % (i + 1) == 0) {
			ret.push_back(i + 1);
			ret.push_back(n / (i + 1));
		}
	}
	sort(all(ret));

	return ret;
}

int main() {

	scanf("%d%d", &N, &K);
	rep(i, N) scanf("%d", &A[i]);

	int Sum = 0;
	rep(i, N) Sum += A[i];

	auto dl = DivList(Sum);

	int ans = 1;
	for (auto dd : dl) {
		rep(i, N) a[i] = A[i] % dd;
		sort(a, a + N);
		int c = 0, t = 0;
		int j = N - 1;
		rep(i, N) {
			t = a[i];
			a[i] = 0;
			c += t;
			while (t) {
				if (dd - a[j] > t) {
					a[j] += t;
					t = 0;
				}
				else {
					t -= dd - a[j];
					a[j] = 0;
					j--;
				}
			}
			if (i == j) break;
		}
		if (c <= K) ans = max(ans,dd);
	}

	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define deb(x) cout<< #x << " " << x << "\n";
#define INF 9223372036854775807
const ll mod=998244353;


int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll a,b,c,d,e;
    cin>>a>>b>>c>>d>>e;
    if(a==0) cout<<1;
    else if(b==0) cout<<2;
    else if(c==0) cout<<3;
    else if(d==0) cout<<4;
    else if(e==0) cout<<5;
    
    return 0;
}

Measured memory_bytes: 3612
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout()]
fn main() {
    input! {
        _n: usize,
        mut s: Bytes,
        q: usize,
    }

    s.iter_mut().for_each(|c| *c -= b'a');
    let mut index = vec![BTreeSet::new(); 26];
    for (i, &b) in s.iter().enumerate() {
        index[b as usize].insert(i);
    }
    
    for _ in 0..q {
        input!(command: usize );
        if command == 1 {
            input!(i: Usize1, c: char);
            let c = c as u8 - b'a';
            let c2 = s[i];
            s[i] = c;
            index[c2 as usize].remove(&i);
            index[c as usize].insert(i);
        } else {
            input!(l: Usize1, r: Usize1);
            let mut res = 0;
            for c in 0..26 {
                if index[c].range(l..=r).next().is_some() {
                    res += 1;
                }
            }
            println!("{}", res);
        }
    }
}


Measured memory_bytes: 13584
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b) {
	return (ll)min(2e18l + 10, a / gcd(a, b) *1.0l* b);
}
ll a[20];
double p[20];
double dp[1 << 20];
int main() {
	int n;
	ll m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		p[i] /= 100;
	}
	for (int bit = 1; bit < (1 << n); bit++) {
		ll mul = 1;
		for (int i = 0; i < n; i++) if (bit&(1 << i)) mul = lcm(mul, a[i]);
		dp[bit] = m / mul;
	}
	for (int i = 0; i < n; i++) for (int bit = 0; bit < (1 << n); bit++) {
		if (bit&(1 << i)) dp[bit] -= dp[bit ^ (1 << i)];
	}
	double ans = 0;
	for (int bit = 0; bit < (1 << n); bit++) {
		double prob = 1.0;
		for (int i = 0; i < n; i++) if (bit&(1 << i)) prob *= p[i]; else prob *= 1 - p[i];
		ans += prob * abs(dp[bit]);
	}
	printf("%.15lf\n", ans);
 }


Measured memory_bytes: 11460
#include <iostream>
#define rep(i,a) for(int i=0;i<(a);++i)

int fib[45];
int n;

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

  fib[0] = fib[1] = 1;
  rep( i, n-1 )
    fib[i+2] = fib[i] + fib[i+1]; 

  std::cout << fib[n] << std::endl;

  return 0;
}

Measured memory_bytes: 3072
#include <iostream>
using namespace std;
int main(void){
   int n,a,b,c;
   cin >> n;

   for(int i = 0; i < n; i++){
       cin >> a >> b >> c;
       if(c > a && c > b && a * a + b * b == c * c){
           cout << "YES" << endl;
       }
       else if(b > a && b > c && a * a + c * c == b * b){
           cout << "YES" << endl;
       }
       else if(a > b && a > c && b * b + c * c == a * a){
           cout << "YES" << endl;
       }
       else{
           cout << "NO" << endl;
       }
   }
}


Measured memory_bytes: 3076
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int A = scan.nextInt();
		int B = scan.nextInt();
		
		if(A <= 8 && B <= 8){
			System.out.println("Yay!");
		}else{
			System.out.println(":(");

		}

	}





}

Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
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;}

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

  int N,X,T;
  cin>>N>>X>>T;

  int M=(N+X-1)/X;
  cout<<M*T<<endl;

  return 0;
}


Measured memory_bytes: 3604