akhauriyash/Code-Regression huggingface dataset:
N,Q = map(int,input().split())
Ki_p = [0 for i in range(N+1)]
Ki_c = [[] for i in range(N+1)]
Ki_co = [0 for i in range(N+1)]
 
for i in range(N-1):
    a,b = map(int,input().split())
    Ki_p[b] = a
    Ki_c[a] += [b]
 
for i in range(Q):
    p,x = map(int,input().split())
    Ki_co[p] += x
 
ans = [0 for i in range(N+1)]
q = {1}
for i in range(N):
    vi = q.pop()
    ans[vi] = Ki_co[vi] + ans[Ki_p[vi]]
    q |= set(Ki_c[vi])
    
print(' '.join(map(str,ans[1:N+1])))

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

int main(void){
	int n, m, d8, d7, d6, d5, d4, d3, d2, d1;
	cin >> n;
	d8 = n / 100000000;
	d7 = n / 10000000;
	d6 = n / 1000000;
	d5 = n / 100000;
	d4 = n / 10000;
	d3 = n / 1000;
	d2 = n / 100;
	d1 = n / 10;
	m = d8 + (d7-d8*10) + (d6-d7*10) + (d5-d6*10) + (d4-d5*10) + (d3-d4*10) + (d2-d3*10) + (d1-d2*10) + (n-d1*10);
	if (n % m == 0){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
k = int(input())
x, y = map(int, input().split())

def sign(x):
    return 1 if x > 0 else -1

if (abs(x) + abs(y)) % 2 == 1 and k % 2 == 0:
    print(-1)
else:
    cx, cy = 0, 0
    ret = []
    while x != cx or y != cy:
        if abs(x - cx) + abs(y - cy) == k:
            cx, cy = x, y
        elif abs(x - cx) + abs(y - cy) <= 2 * k:
            dx = abs(x - cx)
            dy = abs(y - cy)
            rem = 2 * k - dx - dy
            if dx > dy:
                cy += (dy + rem // 2) * sign(y - cy)
                cx += (k - dy - rem // 2) * sign(x - cx)
            else:
                cx += (dx + rem // 2) * sign(x - cx)
                cy += (k - dx - rem // 2) * sign(y - cy)
        else:
            if abs(x - cx) > abs(y - cy):
                cx += sign(x - cx) * k
            else:
                cy += sign(y - cy) * k
        ret.append((cx, cy))

    print(len(ret))
    for cx, cy in ret:
        print(cx, cy)

Measured memory_bytes: 26328
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

string s;
int len, cnt;
long long ans;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> s;
	len = s.length();
	while (s[len - 1] == 'A') len--;
	int cur = 0;
	while (1) {
		if (cur >= len) break;
		bool ok = false, conti = true;
		if (s[cur] == 'A') {
			cur++;
			cnt++;
		}
		else if (s[cur] == 'B') {
			if (cur + 1 < len && s[cur + 1] == 'C') ok = true;
			else conti = false;
			cur++;
			if (ok) cur++;
		}
		else {
			conti = false;
			cur++;
		}
		if (ok) ans += cnt;
		if (!conti) {
			cnt = 0;
		}
	}
	cout << ans << E;
	//system("pause");
	return 0;
}

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

int main(){
  constexpr int Npat= 3;
  int N;
  cin >> N;

  vector<tuple<int, int, int>> data(N);
  int bufA,bufB,bufC;
  for(int i=0; i<N; i++){
    cin >> bufA >> bufB >> bufC;
    data.at(i)= make_tuple(bufA, bufB, bufC);
  }

  vector<vector<int>> dp(Npat, vector<int>(N+1));
  for(int n=1; n<=N; n++){
    dp.at(0).at(n)= get<0>(data.at(n-1))+ max(dp.at(1).at(n-1), dp.at(2).at(n-1));
    dp.at(1).at(n)= get<1>(data.at(n-1))+ max(dp.at(0).at(n-1), dp.at(2).at(n-1));
    dp.at(2).at(n)= get<2>(data.at(n-1))+ max(dp.at(0).at(n-1), dp.at(1).at(n-1));
  }

  vector<int> cand(Npat);
  for(int p=0; p<Npat; p++){
    cand.emplace_back(dp.at(p).back());
  }
  int ans= *max_element(cand.begin(), cand.end());

  cout << ans << endl;
}

Measured memory_bytes: 5812
#include<bits/stdc++.h>
using namespace std ;
typedef  long long int ll ;
#define inf ll(1e18)
#define mod 1000000007
#define mod1 998244353
#define mod2 999983
ll power(ll a,ll n,ll m) ;
ll power(ll a,ll n,ll m)
{  if(n==0)
   return 1 ;
   ll x=power(a,n/2,m) ;
   if(n%2!=0)
    return (((a*x)%m)*(x)%m)%m ;
    else return (x*x)%m ;
}
map<ll,ll>::iterator itr ;
ll ans ;
double PI=3.14159265357 ;
int32_t main()
{ ll n,i,j,x,y,m,k,t,sum,count,cnt,b,c,d,j1,z,a,o,temp;
  ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  long  double f1,f2 ;
  cin>>f1>>f2 ;
  cout<<ll(floor(f1*f2)) ;
  return 0 ; }


Measured memory_bytes: 3748
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>
#include<cstdio>
#include<iomanip>


using namespace std;
using ll = long long int; 

int main(void){

    vector<int> x(32);
    for(int i=0;i<3;i++) x[i] = 1;
    x[3] = 2;
    x[4] = 1;
    x[5] = 2;
    x[6] = 1;
    x[7] = 5;
    x[8] = 2;
    x[9] = 2;
    x[10] = 1;
    x[11] = 5;
    x[12] = 1;
    x[13] = 2;
    x[14] = 1;
    x[15] = 14;
    x[16] = 1;
    x[17] = 5;
    x[18] = 1;
    x[19] = 5;
    x[20] = 2;
    x[21] = 2;
    x[22] = 1;
    x[23] = 15;
    x[24] = 2;
    x[25] = 2;
    x[26] = 5;
    x[27] = 4;
    x[28] = 1;
    x[29] = 4;
    x[30] = 1;
    x[31] = 51;
   


    int k;
    cin>>k;



    cout<<x[k-1]<<endl;
    return 0;

}

Measured memory_bytes: 256
# https://atcoder.jp/contests/arc062/tasks/arc062_b

S = input()
N = len(S)

num = 0
ans = 0
for i in range(N):
    if S[i] == 'g':
        if num > 0:
            num -= 1
            ans += 1
        else:
            num += 1
    else:
        if num > 0:
            num -= 1
        else:
            num += 1
            ans -= 1

# print(S, num, ans)
print(ans)

Measured memory_bytes: 66240
public class Main {
  private static void solve() {
    double l = ni();
    l /= 3;
    System.out.printf("%.12f\n", l * l * l);


  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


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

int main() {
	int sn;
	cin >> sn;
	for ( int i = 0; i < sn; i++ ) {
		int n, k, ans, x[100000], l[100000];
		cin >> n;
		cin >> k;
		for ( int j = 0; j < n; j++ ) cin >> x[j];
		for ( int j = 0; j < n - 1; j++ ) l[j] = x[j + 1] - x[j];
		sort( &l[0], &l[n - 1] );
		ans = 0;
		if ( k < n ) for ( int j = 0; j < n - k; j++ ) ans += l[j];
		cout << ans << endl;
	}
}

Measured memory_bytes: 1956
#include<bits/stdc++.h>
using  namespace std;
typedef long long ll;
const int maxn=1e9;
int T;
ll a,b,c;

int main()
{
    cin>>a>>b>>c;
    if(a==b&&b==c)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;




	return 0;
}



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

int main(){
  int n;cin >> n;
  vector<int> a(n);
  vector<int> b(100005,0);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  for(int i=0;i<n;i++){
    b[a[i]]++;
    b[a[i]+1]++;
    if(a[i]!=0){
      b[a[i]-1]++;
    }
  }
 
  sort(b.rbegin(),b.rend());
  cout << b[0] << endl;
}

Measured memory_bytes: 1024
N = int(input())
all = 10 ** N
not_0 = 9 ** N
not_9 = 9 ** N
not_09 = 8 ** N
ans = all - ((not_0+not_9) - not_09)

if N == 1:
  print(0)
else:
  div_num = (10**9) + 7
  print(ans % div_num)

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

#define int long long
#define CASET int _T; cin >> _T; REP(caset, 0, _T)
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define sq(x) (x)*(x)
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int,int>
#define t3i tuple<int,int,int>
#define t4i tuple<int,int,int,int>
#define mii map<int,int>

const int INF = 1LL<<60;
const int MOD = 998244353;

template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
string to_string(string s) {return s;}
string to_string(bool b) {return b?"true":"false";}
template <typename A, typename B>
string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> t) {return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> t) { return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";}
template <typename A>
string to_string(vector<A> v) {
    bool first = true;
    string result = "[";
    for (A i : v) {
        if (!first) result += ", ";
        first = false;
        result += to_string(i); 
    }
    return result + "]";
}
string bin_string(int x) {
    const int d = 32;
    string result(d, ' ');
    REP(i, 0, d) result[d-1-i] = '0'+(x>>i & 1LL);
    return result;
}

int powa(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp&1) res = res*base % MOD;
        base = base*base % MOD;
        exp >>= 1;
    }
    return res;
}

main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int n;
    cin >> n;
    vi a(n+1), b(n);
    cin >> a >> b;
    
    int res = 0;
    REP(i, 0, n) {
        int temp = min(a[i], b[i]);
        a[i] -= temp;
        b[i] -= temp;
        res += temp;
        temp = min(a[i+1], b[i]);
        a[i+1] -= temp;
        b[i] -= temp;
        res += temp;
    }
    cout << res;
}

Measured memory_bytes: 1792
#include<stdio.h>
void check(int fild[8][8], int x, int y) {
	int i;
	fild[y][x] = 0;
	for (i = 1; i <= 3; i++) {
		if((fild[y][x+i] != 0) && x+i < 8)
		check(fild, x+i,y);
	}
	for (i = 1; i <= 3; i++) {
		if((fild[y][x-i] != 0) && x-i >= 0)
		check(fild,x-i,y);
	}
	for (i = 1; i <= 3; i++) {
		if((fild[y+i][x] != 0) && y+i < 8)
		check(fild,x, y + i);
	}
	for (i = 1; i <= 3; i++) {
		if((fild[y-i][x] != 0) && y-i >= 0)
		check(fild,x, y - i);
	}
	
}

int main(void) {
	int n,x,y ,fild[8][8] = {0};
	int i, j,k=1;
	scanf("%d",&n);
	while(n--){
		for (i = 0; i < 8; i++) {
			for (j = 0; j < 8; j++) {
				scanf("%1d", &fild[i][j]);
			}
		}
		scanf("%d",&x);
		scanf("%d", &y);

		check(fild,x-1,y-1);
		
		printf("Data %d:\n",k++);
		for (i = 0; i < 8; i++) {
		for (j = 0; j < 8; j++) {
		printf("%d",fild[i][j]);
		}
		printf("\n");
		}
	}
	return 0;
}

Measured memory_bytes: 600
// input macro
// ref: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_mut)]
#[allow(unused_parens)]
fn main() {
    // 入力
    input!(
        n: usize,
        a: [i32; n],
    );

    // 累積和
    let zero = vec![0];
    let travel = zero.iter()
                     .chain(a.iter())
                     .chain(zero.iter())
                     .map(|&i| i)
                     .collect::<Vec<i32>>();

    let cum = (1..n+2).map(|i| (travel[i]-travel[i-1]).abs())
                      .sum::<i32>();

    for i in 1..n+1 {
        let ans = (cum
                    - (travel[i]-travel[i-1]).abs()
                    - (travel[i]-travel[i+1]).abs()
                    + (travel[i+1]-travel[i-1]).abs());

        println!("{}", ans);
    }
}


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

int main(){
  long long int w,a,b,ans;
  cin>>w>>a>>b;
  if(b>(a+w)){
    ans = abs(b-(w+a));
  }else if((b+w)<a) {
    ans = abs(a-(b+w));
  }else{
    ans = 0;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int dx[] = {1,-1,0,0};
const int dy[] = {0,0,-1,1};
int w,h;
char data[50][50];
struct P{int x,y,d;};
int correct(int x,int y){
	return x >= 0 && y >= 0 && x < w && y < h;
}

int solve(int x,int y){
	queue<P> Q;
	bool done[50][50] = {0};
	int chk = 0;
	P t = {x,y,0};
	Q.push(t);
	while(Q.size()){
		P q = Q.front(); Q.pop();
		if(done[q.y][q.x])continue;
		else done[q.y][q.x] = true;
		
		if(data[q.y][q.x] != '.'){
			if(data[q.y][q.x] == 'B') chk |= 1;
			else chk |= 2;
			continue;
		}
		rep(i,4){
			P nxt = {q.x+dx[i] , q.y+dy[i], q.d+1};
			if(correct(nxt.x,nxt.y))Q.push(nxt);
		}
	}
	if(chk == 1)return 0;
	else if(chk == 2)return 1;
	else return 2;
}
int main(){
	while(cin >> w >> h , w ){
		int ret[3] = {0};
		rep(i,h)rep(j,w)cin >> data[i][j];
		rep(i,h)rep(j,w)
			if(data[i][j] == '.')ret[solve(j,i)]++;
		
		cout << ret[0] << " " << ret[1] << endl;
	}
}

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

int node;
vector<int>adj[2005];
int ara[2005];

vector<int>bfs(int st)
{
    vector<int>dis(node+1,-1);
    dis[st]=0;
    queue<int>q;
    q.push(st);
    int d=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        for(int i=0;i<adj[u].size();i++)
        {
            int y=adj[u][i];
            if(dis[y]==-1)
            {
                dis[y]=1;
                q.push(y);
                dis[y]=dis[u]+1;
            }
        }
    }
    return dis;
}
int main()
{
    cin>>node;
    int x,y;
    cin>>x>>y;
    adj[x].push_back(y);
    adj[y].push_back(x);
    for(int i=1;i<node;i++)
    {
        adj[i].push_back(i+1);
        adj[i+1].push_back(i);
    }
	for(int i=1;i<node;i++)
    {
        vector<int>dis=bfs(i);
        for(int j=i;j<=node;j++)
        {
          ara[dis[j]]++;
        }
    }
    for(int i=1;i<node;i++)
    {
        cout<<ara[i]<<endl;
    }

	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
main()
{
	string s;
	cin>>s;
	int n=s.length();
	char s1[10];
	if(s[n-1]=='s')
	{
	 // s1='es';
		
		cout<<s<<"es"<<endl;
	}
//	char s1[10] ;
	else
	{
	//	s1='s';
	s.append(1,'s');
		cout<<s<<endl;
	}

}

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<lint> a(n);
    lint x = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 2; i < n; ++i) {
        x ^= a[i];
    }
    map<array<lint, 2>, lint> cache;
    function<lint(lint, lint, lint)> dfs = [&](lint a, lint b, lint x) {
        if (cache.count({a, b}) == 1)
            return cache[{a, b}];
        if (((a & 1) ^ (b & 1)) != (x & 1))
            return inf;
        if (a == 1 || a == 0) {
            if ((a ^ b) == x)
                return 0LL;
            else
                return inf;
        }
        lint c = inf, d = inf;
        if (a != 0)
            c = dfs((a - 1) >> 1, (b + 1) >> 1, x >> 1) * 2 + 1;
        d                    = dfs((a) >> 1, (b) >> 1, x >> 1) * 2;
        return cache[{a, b}] = min({inf, c, d});
    };
    lint ret = dfs(a[0], a[1], x);
    if (ret == inf)
        cout << -1 << "\n";
    else
        cout << ret << "\n";
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

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

typedef pair<int, int> P;



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

    cout << ((n + (d*2))/ ((d*2)+1)) << endl;

    return 0;

}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a[10];
    int i,j,temp;
    for(i=0;i<10;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            if(a[i]>a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
    for(i=0;i<3;i++)
    {
        printf("%d\n",a[i]);
    }
    return 0;
}

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

import sys


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

def dfs_four_number(s_num, i, op_list:list):
    # ベースケース
    if i == 3:
        ans_num = int(s_num[0])
        for j, op in enumerate(op_list):
            if op == "+":
                ans_num += int(s_num[j+1])
            elif op == "-":
                ans_num -= int(s_num[j+1])

        if ans_num == 7:
            return op_list
        else:
            return False

    op_list.append("+")
    if dfs_four_number(s_num, i+1, op_list):
        return op_list

    op_list.pop()
    op_list.append("-")
    if dfs_four_number(s_num, i+1, op_list):
        return op_list
    op_list.pop()



def resolve():
    s_num = input().rstrip()

    op_list = []
    ans_op_list = dfs_four_number(s_num, 0, op_list)

    ans_str = ""
    for s, op in zip(s_num, ans_op_list):
        ans_str += s
        ans_str += op

    ans_str += s_num[3] + "=7"
    print(ans_str)

if __name__ == "__main__":
    resolve()



Measured memory_bytes: 38384
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL-1
double EPS=1e-9;
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef complex<double> P;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
long long int MOD = 1000000007;
/*
cin >> n;
vi a(n);
rep(i,n)cin>>a[i];
*/
string str;
char ans[114514];
int N,K;
vector<ll> a;
bool dp[5100][5100];
bool check(int x){
	dp[0][0]=true;
	rep(i,K)dp[0][i+1]=false;
	for(int i=0;i<N;i++){
		if(i!=x){
			for(int j=0;j<=K;j++){
				if(j>=a[i])dp[i+1][j]=(dp[i][j]||dp[i][j-a[i]]);
				else dp[i+1][j]=dp[i][j];
			}
		}else{
			for(int j=0;j<=K;j++){
				dp[i+1][j]=dp[i][j];
			}
		}
	}
	bool ret=false;
	if(K<a[x])return true;
	for(int t=K-a[x];t<=K-1;t++){
		ret=(ret||dp[N][t]);
	}
	return ret;
}


int main(){
	
	cin>>N>>K;
	for(int i=0;i<N;i++){
		ll hoge;
		cin>>hoge;
		a.pb(hoge);
	}
	
	sort(a.begin(),a.end());
	int mi=0,ma=N;
	while(ma-mi>1){
		int med=(mi+ma)/2;
		if(check(med)){
			ma=med;
		}else{
			mi=med;
		}
		
	}
	if(check(0))cout<<0<<endl;
	else{cout<<ma<<endl;}
}


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

int main(){

  int n;
  vector<int> a;
  cin >> n;
  string s="YES";
  for(int i=0;i<n;i++){int t;cin >> t;a.push_back(t);}
  sort(a.begin(),a.end());
  for(int i=0;i<n-1;i++){
  	if(a[i]==a[i+1]){
    	s="NO";
      	break;
    }
  }
  cout << s;
  return 0;
}

Measured memory_bytes: 1400
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long



using namespace std;

void file(){
	#ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
	#endif
}
int tc;
const int N=5e5+5,M=2e6+5,MOD=1e9+7,OO=1e9;
int g[205][205];
int n,m,k;
int dist[205][205];
set<int>wa[205];
void dij(int x){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
	for(int i=1;i<=n;i++)dist[x][i]=1e9;
	dist[x][x]=0;
	q.push({0,x});
	while(!q.empty()){
		auto p = q.top();
		q.pop();
		int u = p.second , cst = p.first;
		for(auto i : wa[u]){
			int v = i;
			int w = g[u][v];
			if(cst + w < dist[x][v]){
				dist[x][v] = cst+w;
				q.push({dist[x][v],v});
			}

		}
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//file();	
 	
 	scanf("%d %d",&n,&k);

 	std::vector<int> x(n),y(n);

 	for(int i=0;i<n;i++)scanf("%d %d",&x[i],&y[i]);
 	ll ans = 5e18;
 	for(auto x1 : x){
 		for(auto x2:x){
 			if(x2<x1)continue;
 			for(auto y1:y){
 				for(auto y2:y){
 					if(y2<y1)continue;
 					int cnt = 0;
 					for(int i=0;i<n;i++){
 						if(x[i]>=x1 && x[i]<=x2 && y[i]>=y1 && y[i]<=y2)cnt++;
 					}
 					if(cnt>=k){
 						ans = min(ans,(ll)(x2-x1)*(y2-y1));
 					}
 				}
 			}
 		}
 	}
 	printf("%lld\n",ans );
}		


Measured memory_bytes: 256
#include <stdio.h>
int A,B,C;
int main(){
  scanf("%d %d %d",&A,&B,&C);
  if(A!=B&&A!=C){
    printf("%d",A);
  } else if(B!=A&&B!=C){
    printf("%d",B);
  } else if(C!=A&&C!=B){
    printf("%d",C);
  }
  return 0;
}

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

namespace TYC
{
	typedef long long ll;
	const int N =  3005;

	int n, mod, C[N][N], S[N][N];

	inline int qpow(int x, int tim, const int p = mod)
	{
		int ans = 1;
		for (; tim; tim >>= 1, x = (ll)x * x % p)
			if (tim & 1)
				ans = (ll)ans * x % p;
		return ans;
	}

	void work()
	{
		scanf("%d%d", &n, &mod);
		for (int i = 0; i <= n; i++)
		{
			C[i][0] = 1;
			for (int j = 1; j <= i; j++)
				C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
		}
		S[0][0] = 1;
		for (int i = 1; i <= n + 1; i++)
		   	for (int j = 1; j <= i; j++)
				S[i][j] = (S[i - 1][j - 1] + (ll)S[i - 1][j] * j) % mod;
		int ans = 0;
		for (int i = 0; i <= n; i++)
		{
			int sum = 0, tmp = qpow(2, n - i), v = 1;
			for (int j = 0; j <= i; j++, v = (ll)v * tmp % mod)
				sum = (sum + (ll)S[i + 1][j + 1] * v) % mod;
			ans = (ans + (ll)((i & 1) ? mod - 1 : 1) * C[n][i] % mod * qpow(2, qpow(2, n - i, mod - 1)) % mod * sum % mod) % mod;
		}
		printf("%d\n", ans);
	}
}

int main()
{
	TYC::work();
	return 0;
}

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

using namespace std;

int main() {
  int n,m;cin>>n>>m;
  vector<int> vec(m);
  rep(i,n){
    int k;cin>>k;
    rep(j,k){
      int a;cin>>a;
      vec[a-1]++;
    }
  }
  int cnt=0;
  rep(i,m){
    if(vec[i]==n)cnt++;
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 3628
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W = mapint()
As = [list(input()) for _ in range(H)]

from collections import deque
Q = deque()
dist = [[10**18]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if As[h][w]=='#':
            Q.append((h, w))
            dist[h][w] = 0

dirc = ((0, 1), (0, -1), (1, 0), (-1, 0))
while Q:
    y, x = Q.popleft()
    for dy, dx in dirc:
        ny, nx = y+dy, x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx]>dist[y][x]+1:
            dist[ny][nx] = dist[y][x]+1
            Q.append((ny, nx))
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, dist[h][w])
print(ans)

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

#define int long long
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep1(i,n) for(int i=1;i<=(int)(n);++i)
#define rep11(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define repm(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end())
#define vdelete(v) (v).erase(unique(all(v)), (v).end())
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1000000007
#define INF LONG_LONG_MAX

int ans;
string s,t;

signed main() {
    cin >> s >> t;
    rep(i,s.size()) {
        if (s[i] == t[i])ans++;
    }
    cout << ans << endl;
}





Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

int main()
{
	char str[1001];

	while (true){
		cin >> str;

		if (str[0] == '0')
			break;

		int sum = 0;

		for (int i = 0; i < strlen(str); i++){
			sum += (str[i] - '0');
		}
		printf("%d\n", sum);
	}
	return 0;
}

Measured memory_bytes: 3196
a,b = map(int, input().split())

A=[]
B=[]
for i in range(a):
  B.append(str(b))

for j in range(b):
  A.append(str(a))
  
A_=str(''.join(A))
B_=str(''.join(B))

answer=(A_,B_)
answer=sorted(answer)


print(answer[0])



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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
int T,A;
char S[101010];
int i,a,b;
int ck(int ii){
    if(S[ii]=='0'){
        if(S[ii+1]=='0')
            return 0;
        return 1;
    }
    if(S[ii]=='1'&&S[ii+1]<='2'){
        return 1;
    }
    return 0;
}
int main(){
    scanf("%s", S);
    a = ck(0);
    b = ck(2);
    if(a==1&&b==1){
        printf("AMBIGUOUS");
    }else if(a==0&&b==0){
        printf("NA");
    }else if(a==1){
        printf("MMYY");
    }else{
        printf("YYMM");
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
	int n;
    cin >> n;
    vector<int> v(n + 1, 0);
    for (int i = 0; i < n + 1; i++) {
        cin >> v[i];
    }
    long long int res = 0;
    for (int i = 0; i < n; i++) {
        int h;
        cin >> h;
        if (h >= v[i]) {
            res += v[i];
            h -= v[i];
        } else {
            res += h;
            h = 0;
        }
        if (h >= v[i + 1]) {
            res += v[i + 1];
            v[i + 1] = 0;
        } else {
            res += h;
            v[i + 1] -= h;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 3788
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<numeric>

#define reps(i, j, k) for (int i = (j); i < (k); i++)
#define rep(i, j) reps(i, 0, j)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front

using namespace std;

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

const int mod = 1e9 + 7;
const long double pi = 3.141592653589793238462643383279502884197;
const long double eps = 1e-7;

int main() {
	int N, K;
	cin >> N >> K;

	int* num = new int[N + 1];
	rep(i, N + 1) {
		num[i] = 0;
	}

	reps(i, 1, N + 1) {
		int A;
		cin >> A;
		num[A]++;
	}

	vector<pair<int, int>> ps;
	reps(i, 1, N + 1) {
		if (num[i] > 0) {
			ps.pub({ i, num[i] });
		}
	}

	int size = ps.size();
	sort(ps.begin(), ps.end(), [](const pair<int, int>& x, const pair<int, int>& y) {return x.sc > y.sc; });

	//for (auto& i : ps) {
	//	cout << i.fs << ": " << i.sc << endl;
	//}

	int sum = 0;
	while (size > K) {
		sum += ps[size - 1].sc;
		ps.pob();
		size -= 1;
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 3188
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>
#include<limits>
#include<iomanip>
#include<iterator>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i=0; i<n; i++)
#define FOR(i,a,n) for(int i=a; i<n; i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ll, char> plc;

int p[15];

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

	int sum = 0;
	rep(i, 15) {
		sum += pow(3, i);
		p[i] = sum;
	}
	
	int n = 14,sign = 1;
	bool f = false;
	while (n >= 0) {
		int bob = pow(3, n);
		int diff;
		if (w > 0)
			diff = w - bob;
		else
			diff = w + bob;
		if (abs(diff) < abs(w)) {
			f = true;
			if (sign == 1 )cout << "+";
			else if (sign == -1)cout << "-";
			if (w >= 0) {
				w -= bob;
			}
			else {
				w += bob;
			}	
			if (w < 0)sign = -1;
			else sign = 1;
		}
		else if (f)cout << "0";
		n--;
	}
	cout << endl;
	return 0; 
}

Measured memory_bytes: 3276
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);

		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		
		int left=0;
		int right=n;
		
		for(int i = 0;i<m;i++) {
			int l = Integer.parseInt(sc.next());
			int r = Integer.parseInt(sc.next());
			if(l>left) {
				left=l;
			}
			
			if(right>r) {
				right = r;
			}
		}
		
		if(left>right) {
			System.out.println(0);
		}else {
			System.out.println(Math.abs(right-left)+1);
		}
	}
		
}

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

int main(){
    int N;
    cin >> N;
    int A[N]={};
    for(int i=0;i<N;i++){
        cin >> A[i];
    }
    for(int i=0;i<N;i++){
        if(A[i]%2==0){
            if((A[i]%3==0)||(A[i])%5==0){
                continue;
            }else{
                cout << "DENIED";
                return 0;
            }
        }
    }
    cout << "APPROVED";
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		HashMap<String, Integer> map = new HashMap<>();
		ArrayList<String> list = new ArrayList<>();
		String s = "";
		int t = 0;
		for(i=0;i<n;i++) {
			s = sc.next();
			t = parseInt(sc.next());
			map.put(s, t);
			list.add(s);
		}
		String x = sc.next();
		sc.close();
		int sum=0;
		for (i = list.indexOf(x)+1; i < list.size(); i++) {
			sum += map.get(list.get(i));
		}
		out.println(sum);
	}
}


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


int main(){

    int n;
    string s;
    cin >> n >> s;

    int ans = 0;
    for(int i = 0; i < n; i++){
        int cnt = 0;
        for(char c = 'a'; c <= 'z'; c++){
            int lft = 0, rgt = 0;

            for(int j = 0; j < i; j++){
                if(s[j] == c){
                    lft = 1;
                }
            } 
            for(int j = i; j < n; j++){
                if(s[j] == c){
                    rgt = 1;
                }
            }
            if(lft && rgt){
                cnt++;
            }
        }
        if(ans < cnt){
            ans = cnt;
        }
    }

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

Measured memory_bytes: 256
def main():
    n,m,x = map(int,input().split())
    c = []
    for i in range(n):
        cc = list(map(int,input().split()))
        c.append(cc)
    tmp = 2 ** n
    ans = 10**8

    bi=str(format(tmp,"b"))#2進表現に
    for k in range(tmp):
        anstmp = 0
        ary = [0] * m
        for i in range(n):
            if ((k >> i) & 1):
                anstmp += c[i][0]
                for j in range(1,m+1):
                    ary[j-1] += c[i][j]

        
        flg = True
        for j in range(m):
            if ary[j] < x:
                flg = False
                break
        if anstmp < ans and flg:
            ans = anstmp
    if ans == 10**8:
        print(-1)
    else:
        print(ans)



if __name__=='__main__':
    main()


Measured memory_bytes: 9236
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

int main()
{
  ll n, a, b;
  cin >> n >> a >> b;
  ll result = n / (a + b) * a;
  n %= a + b;
  result += min(a, n);
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 256
// Problem : D - Bouquet
// Contest : AtCoder - AtCoder Beginner Contest 156
// URL : https://atcoder.jp/contests/abc156/tasks/abc156_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//Macros

#define ll long long
#define db long double
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mi map<int,int>
#define mii map<pii,int>
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(x) (int)x.size()
#define mod 1000000007
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define inf 1e10
#define PI acos(-1.0)
#define int long long
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100005

//Solution

int binpow(int x,int y){
    x %= mod;
    int res = 1;
    while(y){
        if(y&1) res = (res*x)%mod;
        x = (x*x)%mod;
        y = y/2;
    }
    return res;
}
 
int inv(int a){
    return binpow(a,mod-2);
}

void solve(){
    int n,a,b;
    cin>>n>>a>>b;
    int ans = binpow(2,n)-1;
    ans += mod;
    ans %= mod;
    int cur = 1;
    for(int i=0;i<a;i++){
        cur *= n-i;
        cur %= mod;
        cur *= inv(a-i);
        cur %= mod;
    }
    ans -= cur;
    ans += mod;
    ans %= mod;
    cur = 1;
    for(int i=0;i<b;i++){
        cur *= n-i;
        cur %= mod;
        cur *= inv(b-i);
        cur %= mod;
    }
    ans -= cur;
    ans += mod;
    ans %= mod;
    cout<<ans<<endl;
}

signed main(){
    io;
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    int tests;
    //cin>>tests;
    tests = 1;
    while(tests--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3648
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e15;
const int MOD = 1e9 + 7;
const double PI = 3.14159265358979323846;

signed main() {
	int N;
	cin >> N;
	int a = 1;
	int b = N - 1;
	int ans = 0;
	while (1) {
		if (a >= b)break;
		ans++;
		a++;
		b--;
	}
	cout << ans;
}

Measured memory_bytes: 384
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<climits>
#include<cstdlib>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
//const ll mod = 1000000007;
typedef long long ll;
int N;
const int maxn = 1e5 + 5;

ll aa[maxn], a[maxn],p[maxn];
void solve() {
	//cout.precision(10);
	cin >> N;
	ll xsum = 0;
	ll ans = 0; ll tmp = 0;
	rep(i, 1, N)cin >> aa[i], xsum ^= aa[i];
	for (int j = 62; j >= 0; j--) {//remove 0s
		if ((xsum >> j)&1)tmp += 1ll << j;
		else {
			for (int i = 1; i <= N; i++)if ((aa[i] >> j) & 1)
				//a[i] = a[i]*2+1;
				a[i] |= 1ll << j;
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 62; j >= 0; j--) {
			if (!(a[i] >> j)) continue;//对线性基的这一位没有贡献
			if (!p[j]) { p[j] = a[i]; break; }//选入线性基中
			a[i] ^= p[j];
		}
	}
	for (int i = 62; i >= 0; i--) if ((ans^p[i])>ans) ans = ans ^ p[i];//从线性基中得到最大值
	ans *= 2;
	ans += tmp;
	cout << ans << endl;
	return;
}

int main() {
	solve();
	cin >> N;
	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
char A[26], c;
int main(){
	c=getchar();
	while(c!=10){
		if(A[c-'a']){
			printf("no\n");
			return 0;
		}
		A[c-'a']=1;
		c=getchar();
	}
	printf("yes\n");
}


Measured memory_bytes: 128
N = int(input())
x = list(map(int, input().split()))
MOD = 10**9+7
D = x[-1]-x[0]
ans = 0
fact = [1]

for i in range(1, N):
    fact.append(fact[-1]*i%MOD)

inv_table = [-1]*N

for i in range(N):
    inv_table[i] = pow(i, MOD-2, MOD)
    
for i in range(N-1):
    d = D-(x[i]-x[0])
    ans += d*fact[N-1]*inv_table[i+1]
    ans %= MOD

print(ans)

Measured memory_bytes: 65688
//#include<bits/stdc++.h>
#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;
typedef long long ll; 
#define PT pair<int, int>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

int N, M, R;
int E[201][201];
int D[8][201];
int r[8];
int kotae;
int ima;
bool v[8];
void sagasu(int n, int prev) {
	if (n == R) kotae = min(kotae, ima);
	else {
		rep(i, R) {
			if (!v[i]) {
				v[i] = 1;
				if (prev >= 0) ima += D[prev][r[i]];
				sagasu(n + 1, i);
				if (prev >= 0) ima -= D[prev][r[i]];
				v[i] = 0;
			}
		}
	}
}

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	N = getint();
	M = getint();
	R = getint();
	rep(i, R) r[i] = getint();

	rep1(i, N) {
		rep1(j, N) E[i][j] = 1e9;
		E[i][i] = 0;
	}
	rep(i, M) {
		int a = getint(), b = getint(), c = getint();
		E[a][b] = c;
		E[b][a] = c;
	}

	rep(i, R) rep1(j, N) D[i][j] = 1e9;
	rep(i, R) D[i][r[i]] = 0;

	priority_queue<PT, vector<PT>, greater<PT>> que;

	rep(k, R) {
		que.push(mp(0, r[k]));
		while (que.size()) {
			PT p = que.top();
			que.pop();
			int i = p.second;
			if (D[k][i] != p.first) continue;
			rep1(j, N) {
				ll d = D[k][i] + E[i][j];
				if (D[k][j] > d) {
					D[k][j] = d;
					que.push(mp(d, j));
				}
			}
		}
	}

	kotae = 1e9;
	sagasu(0, -1);

	printf("%d", kotae);

	Would you please return 0;
}

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

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

const int MAX_N = 200005;
int N;
int A[MAX_N];
bool used[MAX_N];

vector<int> prime;
vector<int> ans;

signed main()
{
  cin >> N;
  FOR(n,1,N+1) {
    cin >> A[n];
  }

  for(int n = N; 1 <= n; n--) {
    for(int m = 2; n*m <= N; m++) {
      A[n] += used[n*m];
    }
    if(A[n]%2 == 1) {
      ans.push_back(n);
      used[n] = true;
    }
  }

  cout << ans.size() << endl;
  if(ans.size() > 0) {
    for(int i = 0; i < ans.size(); i++) {
      cout << ans[i];
      if(i < ans.size()-1) {
        cout << " ";
      }
    }
    cout << endl;
  }
  

  return 0;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) for (long long i = 0, max_i = (n); i < max_i; i++)
#define REPI(i, a, b) for (long long i = (a), max_i = (b); i < max_i; i++)
#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)
#define fi first
#define se second
using ii = pair<int, int>;
vector<ii> dirs = {
  {1, 0}, {0, 1}, {-1, 0}, {0, -1},  // 4方向
  {1, 1}, {-1, 1}, {-1, -1}, {1, -1},  // 斜め
  {0, 0},  // 自身
};
template <class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template <class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <class T, class S> vector<T> make_vec(size_t n, S x) { return vector<T>(n, x); }
template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...)); }

// debug
template <class T> ostream& operator<<(ostream& s, vector<T>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : " "); return s; }
template <class T> ostream& operator<<(ostream& s, vector<vector<T>>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : "\n"); return s; }
template <class T, class S> ostream& operator<<(ostream& s, pair<T, S>& p) { s << "{" << p.first << ", " << p.second << "}"; return s; }
template <class T, class S> ostream& operator<<(ostream& s, map<T, S> m) { for (auto it = m.begin(); it != m.end(); it++) { s << *it << (next(it) == m.end() ? "" : "\n"); } return s; }
#ifdef _MY_DEBUG
  #define dump(...) cerr << "/* " << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), cerr << "*/\n\n";
#else
  #define dump(...)
  #define endl "\n"
#endif
void dump_func() { cerr << endl; }
template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) { cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...); }

struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
constexpr int MOD = 1000000007;
// *************** TEMPLATE END *************** 

signed main() {
  int n; cin >> n;
  vector<vector<int>> g(n);
  REP (i, n - 1) {
    int u, v; cin >> u >> v;
    u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  int di = 0;
  function<int(int, int)> dfs = [&](int v, int p) {
    int ma = 0;
    for (int s: g[v]) if (s != p) {
      int tmp = dfs(s, v) + 1;
      chmax(di, ma + tmp);
      chmax(ma, tmp);
    }
    return ma;
  };
  dfs(0, -1);
  cout << (di % 3 == 1 ? "Second" : "First") << endl;
}


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

int main(){
    int i,j,k,n,ans=0;
    cin >> n;
    string s;
    cin >> s;
    for(i=0;i<n-1;i++){
        int count=0;
        string mae=s.substr(0,i+1),ushiro=s.substr(i+1);
        //cout << mae <<" " <<  ushiro << endl;
        vector<int> maealpha(26,0),ushiroalpha(26,0);
        for(j=0;j<i+1;j++){
            for(k=0;k<26;k++){
                if((int)mae[j]==(int)'a'+k)maealpha.at(k)++;
            }
        }
        for(j=0;j<n-i-1;j++){
            for(k=0;k<26;k++){
                if((int)ushiro[j]==(int)'a'+k)ushiroalpha.at(k)++;
            }
        }
        for(k=0;k<26;k++){
                if(maealpha.at(k)*ushiroalpha.at(k)!=0)count++;
            }
            //cout << count << endl;
        if(ans<count)ans=count;
    }
    cout << ans << endl;
    /*vector<int> alpha(26);
    if((int)s[0] == (int)'a' + 3 )alpha.at(3)++;
    cout << alpha.at(3) << endl;*/
    return 0;
}

Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split(' ')))

ans = 0
cand = 0
pre_h = H[0]
for h in H[1:]:
	if pre_h >= h:
		cand += 1
	else:
		ans = max(ans,cand)
		cand = 0
	pre_h = h
ans = max(ans,cand)
print(ans)





Measured memory_bytes: 14252