akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long
#define maxn 200005
using namespace std;

const int INF = 1e18;

struct Node {
    int dp, sum, mx;
    Node() {
        mx = dp = sum = 0;
    }
} tr[maxn * 4];

void pull(int x) {
    int L = x << 1;
    int R = L + 1;
    tr[x].sum = tr[L].sum + tr[R].sum;
    tr[x].dp = min(tr[L].dp, tr[R].dp);
    tr[x].mx = min(tr[L].mx + tr[R].sum, tr[R].mx);
}

void set_dp(int p, int v, int x = 1, int L = 0, int R = maxn) {
    if(L == R)  {
        tr[x].dp = min(tr[x].dp, v);
        tr[x].mx = min(tr[x].mx, v);
        return;
    }
    int m = (L + R) >> 1;
    if(p <= m) set_dp(p, v, x << 1, L, m);
    else set_dp(p, v, (x << 1) | 1, m + 1, R);
    pull(x);
}

void add(int p, int v, int x = 1, int L = 0, int R = maxn) {
    if(L == R)  {
        tr[x].sum += v;
        return;
    }
    int m = (L + R) >> 1;
    if(p <= m) add(p, v, x << 1, L, m);
    else add(p, v, (x << 1) | 1, m + 1, R);
    pull(x);
}

int ask() {
    return tr[1].mx;
}

map<int, int> T[maxn];
int n, m, sum = 0;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int l, r, a;
        cin >> l >> r >> a;
        T[r][l] += a; sum += a;
    }
    for(int i = 1; i <= n; i++) {
        T[i][i] += 0;
    }
    for(int i = 1; i <= n; i++) {
        set_dp(i, ask());
        for(auto it : T[i]) {
            add(it.first, it.second);
        }
    }
    cout << sum - ask() << '\n';
    return 0;
}



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

int main() {
  string S;
  cin >> S;

  // ここにプログラムを追記
  if ((S.at(2) == S.at(3)) && (S.at(4) == S.at(5))){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
    
    
}


Measured memory_bytes: 256
from collections import defaultdict
import sys
n = int(input())
A = list(map(int, input().split()))

# if n == 1:
#     print(1)
#     sys.exit()

d = defaultdict(int)

for key in A:
    d[key] += 1

# if len(d) == 1: # 全部同じ数
#     print(0)
#     sys.exit()

B = list(d)
# B.sort()

# if B[0] == 1: # 1が含まれる場合
#     print(d[1])
#     sys.exit()
# length = len(d)
m = max(d)
flag = [0 for i in range(m+1)]

for i in B:
    t = i
    while t <= m:
        flag[t] += 1
        t += i

ans = 0
for i in B:
    if flag[i] == 1 and d[i] == 1:
        ans += 1

print(ans)

Measured memory_bytes: 44664
# -*- coding: utf-8 -*-

import sys

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    n = int(lines[0])
    h = [int(e) for e in lines[1].split(" ")]

    return (n, h)


def solve(n, h):

    if n == 1:
        return 0

    count = 0
    count_max = 0
    for i in range(n-1, 0, -1):
        
        if h[i-1] >= h[i]:
            count = count + 1
        else:
            count = 0

        count_max = max(count_max, count)
        if debug:
            log("i=%d, count=%d" % (i, count))


    return count_max


def main():
    # 出力

    print("%s" % solve(*parse_input()))

if __name__ == '__main__':

    main()
	


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

using namespace std;

int main(){

  long long int W, a, b;
  cin>>W>>a>>b;
  
  if(a<=b and b<=a+W) cout<<0<<endl;
  else if(b<=a and a<=b+W) cout<<0<<endl;
  else{
    cout<<min(abs(b-a-W), abs(a-b-W))<<endl;  
  }
}


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

int a[100010];
int b[100010];
int main() {
	int n; cin >> n;
	for (int i=1; i<=n+1; ++i) {
		cin >> a[i];
	}
	for (int i=1; i<=n; ++i) {
		cin >> b[i];
	}

	long long int ans = 0;
	int tmp = 0;
	for (int i=1; i<=n; ++i) {
		tmp = min(a[i],b[i]);
		ans += tmp;
		a[i] -= tmp;
		b[i] -= tmp;
		tmp = min(a[i+1],b[i]);
		ans    += tmp;
		a[i+1] -= tmp;
		b[i]   -= tmp;
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<list>
using namespace std;

#define MAX_N 500000
#define INF 1145141919

vector<int>G[MAX_N];
list<int> out;
bool V[MAX_N];
int N, M, b, c[MAX_N], d;
int indeg[MAX_N];
queue<int>Q;

void bfs(int s) {
	Q.push(s);
	V[s] = true;
	while (!Q.empty()) {
		int u = Q.front(); Q.pop();
		out.push_back(u);
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			indeg[v]--;
			if (indeg[v] == 0 && V[v] == false) { V[v] = true; Q.push(v); }
		}
	}
}

void Tsort() {
	for (int i = 0; i < N; i++) {
		indeg[i] = 0;
	}
	for (int u = 0; u < N; u++) {
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i];
			indeg[v]++;
		}
	}
	for (int u = 0; u < N; u++) {
		if (indeg[u] == 0 && V[u] == false) {
			bfs(u);
		}
	}
	b = 0; d = 0;
	for (list<int>::iterator it = out.begin(); it != out.end(); it++) {
		cout << *it + 1 << endl;
		c[b] = *it;
		if (b >= 1) {
			for (int i = 0; i < G[c[b - 1]].size(); i++) {
				if (G[c[b - 1]][i] == c[b]) {
					goto F;
				}
			}
			d = 1;
		F:;
		}
		b++;
	}
	cout << d << endl;
}

int main() {
	int s, t;
	for (int i = 0; i < MAX_N; i++) { G[i].clear(); }
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> s >> t; s--; t--;
		G[s].push_back(t);
	}
	Tsort();
	return 0;
}

Measured memory_bytes: 16088
N = int(input())
res = [0 for _ in range(N)]

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            k = x**2 + y**2 + z**2 + x * y + y * z + z * x
            if k <= N:
                res[k - 1] += 1

print(*res, sep='\n')

Measured memory_bytes: 68808
import System.IO
import Data.List
import Data.Char
import Debug.Trace

sumScore :: [(Int, Int, Int)] -> (Int, Int)
sumScore xs = (sum $ map (\(_, p, _) -> p) xs, sum $ map (\(d, p, c) -> (p * d * 100) + c) xs)

minp :: Int -> [(Int, Int, Int)] -> Int
minp g xs = f g xs 0
  where
  f g xs t
    | g <= 0 = t
    | xs == [] = t
    | otherwise = do
      let (d, p, c) = last xs
      let newxs = (init xs) ++ (if pred p == 0 then [] else [(d, pred p, c)])
      f (g - (d * 100)) newxs (succ t)

sp :: [Int] -> [(Int, Int)]
sp [] = []
sp xs = do
  let y = take 2 xs
  (y !! 0, y !! 1):(sp $ drop 2 xs)

main = do
  s <- getLine
  let g = read $ words s !! 1 :: Int
  s <- getContents
  let gg = sp $ map read $ words s :: [(Int, Int)]
  let i = zipWith (\d (p, c) -> (d, p, c)) [1..] gg
  let powi = map (\s -> (s, i \\ s)) $ subsequences i
  let p = map (\(x, y) -> (x , sumScore y)) powi
  print $ minimum $ map (\(x, y) -> (fst y) + (minp (g - (snd y)) x)) p


Measured memory_bytes: 1020
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream> 
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;

const ll MOD=ll(1e9+7);

//repetition
#define REP(i,n)  for(ll i=0;i<n;i++)

ll P_POW(ll i, ll n) {
  if(n==0) return 1;

  n--;
  ll rep = i;

  while(n) {
    rep = rep * i;
    n--;
  }
  return rep;
} 

unsigned GetDigit(unsigned num){
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}
 
unsigned binarySearch(ll target, ll max, ll min) {
  while((max - min) > 1) {
      if((max + min)/2 > target) {
        max = (max + min)/2;
        min = min;
      } else {
        max = max;
        min = (max + min)/2;
      }
    }
}

ll n;


long long solve2(long long N) {
    if (N % 2 == 1) return 0;

    long long res = 0;
    N /= 2;
    while (N) {
        res += N / 5;
        cout << "N/5: " << N/5 <<  endl;
        cout << "res1: " << res <<  endl;
        N /= 5;
    }
    return res;
}


ll solve(ll n) {
    if (n % 2 == 1) return 0;

    ll res = 0;
    n /= 2;
    int c = 1;

    while ((ll) n/((ll)pow(5,c))) {
      res += n/P_POW(5,c);
      c++;
    }
    return res;
}

void f(int rest, string s) {
  char abc[] = "abc";
  if(rest == 0) {
    cout << s << endl;
  } else {
    for(int i=0; i < 3; i++) {
      f(rest - 1, s+abc[i]);
    }
  }
}

int main() {
  ll n, k;
  cin >> n >> k;
  vector<ll> a;
  vector<ll> s;
  vector<ll> si;
  REP(i, n) {
    ll ai;
    cin >> ai;
    a.push_back(ai);
  }


  ll total1 = 0;

  REP(i, a.size()) {
    vector<ll> ai;
    ai = vector<ll>(a.begin() + i, a.end());
    sort(ai.begin(), ai.end());
    int pos = lower_bound(ai.begin(), ai.end(), a[i]) - ai.begin();
    total1 += pos;
  }

  // A中でAiより小さいものの数 
  ll total2 = 0;
  REP(i, a.size()) {
    sort(a.begin(), a.end());
    int pos = lower_bound(a.begin(), a.end(), a[i]) - a.begin();
    total2 += pos;
  }
  /*
  ll total5 =  k * (k-1)%MOD * total2%MOD/2;
  ll total6 = total1%MOD * k%MOD;
  */
  ll total5 =  k * (k-1) / 2 % MOD * total2 % MOD;
  ll total6 = total1 * k %MOD;

  cout << (total5 + total6)%MOD << endl;

}


Measured memory_bytes: 256
import fractions
import sys
N,K = map(int,input().split())
L = []
L.append(N)
i = 0
if N == K:
    print(0)
    sys.exit(0)
if N == 0:
    print(0)
    sys.exit(0)
if K == 1:
    print(0)
    sys.exit(0)
Q = 0
N-=((N//K)*K)
while True:
  L.append(abs(N-K))
  N = abs(N-K)
  i += 1
  if i > 10**5:
    Q = min(L)
    break
if N%K == 0 and N>=K:
    print(0)
else:
    if N < K:
        print(min(N,Q))
    else:
        print(min(N%K,Q,fractions.gcd(N,K)))

Measured memory_bytes: 9144
#include <stdio.h>


int main()
{
	int A, B, C;
	
	scanf("%d %d %d", &A, &B, &C);
	(A==B && A==C && B==C) ? puts("No") : puts("");
	(A!=B && A!=C && B!=C) ? puts("No") : puts("");
	(A==B && A==C && B!=C) ? puts("Yes") : puts("");
	(A==B && A!=C && B==C) ? puts("Yes") : puts("");
	(A!=B && A==C && B==C) ? puts("Yes") : puts("");
	(A==B && A!=C && B!=C) ? puts("Yes") : puts("");
	(A!=B && A!=C && B==C) ? puts("Yes") : puts("");
	(A!=B && A==C && B!=C) ? puts("Yes") : puts("");

	
	return 0;
} 

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

using namespace std;

int main () {
  string s;
  bool ans = true;
  cin >> s;
  int n = s.length();


  if (s[0] != 'A') ans = false;
  else {
    int c = 0;
    for (int i = 2; i < n-1; i++) {
      if (s[i] == 'C') c += 1;
      else if (isupper(s[i])) ans = false;
    }
    if (c != 1) ans = false;
    if (isupper(s[1]) || isupper(s[n-1])) ans = false;
  }

  if (ans) cout << "AC" << endl;
  else cout << "WA" << endl;
  return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
s=input()
t=s[0]
c=[-1,1][s[0]=="R"]
d=[0]

for i in range(1,n):
    if t!=s[i]:
        d.append(c)
        c=0
    t=s[i]
    c+=[-1,1][s[i]=="R"]
d.append(c)
c=len(d)

if c>2:
    for i in range(1,k+1):
        if i*2>=c: break
        d[i*2]*=-1
chk=0
ans=0
for i in d:
    if (i>0 and chk>0) or (i<0 and chk<0):
        chk+=i
    else:
        if chk!=0: ans+=abs(chk)-1
        chk=i

print(ans+(abs(chk)-1))


Measured memory_bytes: 46028
N, A, B = map(int, open(0).read().split())

MOD = 10 ** 9 + 7

def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD

    return ret

print((pow(2, N, MOD) - 1 - comb(N, A) - comb(N, B)) % MOD)


Measured memory_bytes: 38768
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0;i<(n);++i)
#define per(i, n) for(int i=(n)-1;i>=0;--i)
#define repa(i, n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define all(x) (x).begin(), (x).end()
#define bit(x) (1ll << (x))
using ll = long long;
//const ll MOD = (ll)1e9+7;
const ll MOD = 998244353;
const int INF = (ll)1e9+7;
const ll INFLL = (ll)1e18;
using namespace std;
template<class t>
using vvector = vector<vector<t>>;
template<class t>
using vvvector = vector<vector<vector<t>>>;
template<class t>
using priority_queuer = priority_queue<t, vector<t>, greater<t>>;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

ll modpow(ll x, ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

ll modinv(ll x){
	return modpow(x, MOD-2);
}

bool was_output = false;
template<class t>
void output(t a){
	if(was_output)cout << " ";
	cout << a;
	was_output = true;
}
void outendl(){
	was_output = false;
	cout << endl;
}

ll n, m, a, b, c, t;
vector<ll> operator+(vector<ll> a, vector<ll> b){
	int n = min(a.size(), b.size());
	vector<ll> res(n);
	rep(i, n){
		res[i] = (a[i]+b[i]) % m;
	}
	return res;
}
vector<ll> operator*(vector<ll> a, ll k){
	foreach(i, a)i = (i * k) % m;
	return a;
}

vector<ll> s;
vvvector<ll> dp;
//fuct count is 2 ^ time
vector<ll> solve(int place, int time){
	if(time==0){
		vector<ll> res(n, 0);
		if(place+1<n){
			res[place+1] = a;
		}
		res[place] = b;
		if(place-1>=0){
			res[place-1] = c;
		}
		return res;
	}
	if(dp[place][time].size())return dp[place][time];
	vector<ll> res1 = solve(place, time-1);
	vector<ll> res2(n);
	rep(i, n){
		res2 = res2 + solve(i, time-1) * res1[i];
	}
	return dp[place][time] = res2;
}

vector<ll> solve2(int place, int time){
	vector<ll> res(n, 0);
	res[place] = 1;
	rep(i, 31){
		if(~time&bit(i))continue;
		vector<ll> tmp(n, 0);
		rep(j, n){
			tmp = tmp + solve(j, i) * res[j];
		}
		res = tmp;
	}
	return res;
}

void func(){
	s.assign(n, 0);
	foreach(i, s)cin>>i;
	dp.assign(n, vvector<ll>(31, vector<ll>(0)));
	vector<ll> ans(n, 0);
	rep(i, n){
		ans = ans + solve2(i, t) * s[i];
	}
	rep(i, n){
		output(ans[i]);
	}
	outendl();
}

int main(){
	while(cin>>n>>m>>a>>b>>c>>t&&n){
		func();
	}
	return 0;
}



Measured memory_bytes: 3572
#include<bits/stdc++.h>
#define N 105
#define P 1000000007
using namespace std;
int n,a[N],dp[N][N][N],Ans;
void upd(int &x,int y)
{
	x=(x+y)%P;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n*2-1;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n*2);
	dp[n][a[n]!=a[n-1]][a[n]!=a[n+1]]=1;
	for (int i=n;i>1;i--)
	{
		int L=a[i-1]!=a[i-2],R=a[n*2-i+1]!=a[n*2-i+2];
		for (int l=0;l<=n*2-1;l++)
			for (int r=0;r<=n*2-1;r++)
			{
				int tmp=dp[i][l][r];
				upd(dp[i-1][l+L][r+R],tmp);
				for (int j=0;j<l;j++) upd(dp[i-1][j+L][r+R+1],tmp);
				for (int j=0;j<r;j++) upd(dp[i-1][l+L+1][j+R],tmp);
			}
	}
	for (int i=0;i<=n*2-1;i++)
	for (int j=0;j<=n*2-1;j++)
		upd(Ans,dp[1][i][j]);
	printf("%d\n",Ans);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define rep3(i, s, n) for (int i = s; i > (int)(n); i--)
#define all(obj) obj.begin(), obj.end()
#define db(x) cerr << #x << ":" << x << " "
#define dbl(x) cerr << #x << ":" << x << "\n"
#define dbv(vec) cerr << #vec << ":"; for (auto e : vec) cerr << e << " "; cout << "\n"
#define dbvv(vv) cerr << #vv << ":\n"; for (auto vec : vv) { for (auto e : vec) cerr << e << " "; cerr << "\n"; }
#define YN(f) cout << (f ? "YES" : "NO") << "\n"
#define Yn(f) cout << (f ? "Yes" : "No") << "\n"
#define yn(f) cout << (f ? "yes" : "no") << "\n"
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

int main() {
	string S; cin >> S;
	int N = S.length(); // 0-ind
	vi ans(N);
	int Even = 0, Odd = 0; // 初期配置で偶数番目，奇数番目のマスの子どもの人数を積算
	int lastR, firstL; // そのブロックの中で最後のR，最初のL
	int x =  0; // 現在見ているマス
	while (x < N) {
		if (x % 2 == 0) Even++;
		else Odd++;
		if (S[x] == 'R' and S[x + 1] == 'L') {
			lastR = x; firstL = x + 1;
		} else if (S[x] == 'L' and S[x + 1] == 'R') {
			if (lastR % 2 == 0) {
				ans[lastR] = Even; ans[firstL] = Odd;
			} else {
				ans[lastR] = Odd; ans[firstL] = Even;
			}
			Even = Odd = 0;
		}
		x++;
	}
	if (lastR % 2 == 0) {
		ans[lastR] = Even; ans[firstL] = Odd;
	} else {
		ans[lastR] = Odd; ans[firstL] = Even;
	}
	dbv(ans);
	rep(i, N) {
		if (i) cout << " ";
		cout << ans[i];
	}
	cout << endl;
}

Measured memory_bytes: 1024
n, k = gets.chomp.split(" ").map(&:to_i)
arr = []
n.times do |i|
    a = gets.chomp.to_i
    arr << a
end
arr = arr.sort
st = 0
ans = 100000000000
while true
    sa = arr[st + k - 1] - arr[st]
    ans = [ans,sa].min
    if st + k - 1 == n - 1
         break
    end
    st += 1
end
puts ans

Measured memory_bytes: 16952
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = Integer.parseInt(sc.next());
        int d = Integer.parseInt(sc.next());
        long x = Long.parseLong(sc.next());
        getX(0, r, d, x);
    }

    private static long getX(int depth, int r, int d, long x) {
        if (depth == 10) {
            return x;
        }
        depth++;
        System.out.println(r * x - d);
        return getX(depth, r, d, r * x - d);
    }
}

Measured memory_bytes: 19924
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる




int main(){
  ll n,a;
  cin>>n>>a;

  vector<ll> p;
  vector<ll> q;
  ll zr=0;
  rep(i,n){
    ll x;
    cin>>x;
    x-=a;
    if(x==0) zr++;
    if(x>0) p.pb(x);
    if(x<0) q.pb(x);
  }

  vector<vector<ll>> pp(p.size()+1,vector<ll>(3000,0));
  pp[0][0]=1;
  repo(i,p.size()+1){
    rep(j,2600){
      pp[i][j]=pp[i-1][j];
      if(0<=j-p[i-1]) pp[i][j]+=pp[i-1][j-p[i-1]];
    }
  }

  vector<vector<ll>> qq(q.size()+1,vector<ll>(3000,0));
  qq[0][0]=1;
  repo(i,q.size()+1){
    rep(j,2600){
      qq[i][j]=qq[i-1][j];
      if(0<=j+q[i-1]) qq[i][j]+=qq[i-1][j+q[i-1]];
    }
  }

  ll ans=0;
  rep(i,2600){
    ans+=pp[p.size()][i]*qq[q.size()][i];
  }

  rep(i,zr){
    ans*=2;
  }



  cout << ans-1 << endl;

}

Measured memory_bytes: 1536
/* ex5_3
   YSK722 */

#include <stdio.h>

int main(void){
    int height, width;
    char box[3][100][100];
    scanf("%d %d", &height, &width);
    // 白黒を読み取る
    for (int i = 0; i < height; i++){
        for (int j = 0; j < width; j++){
            scanf(" %c", &box[0][i][j]);
        }
    }
    /* i行の要素が全て白のとき、2つめのboxのi行目の
    要素をすべて"n"にし、それ以外の時はすべて"y"にする */
    for (int i = 0; i < height; i++){
        for (int j = 0; j < width; j++){
            if (box[0][i][j] == '#'){
                for (int k = 0; k < width; k++){
                    box[1][i][k] = 'y';
                }
                break;
            }
            box[1][i][j] = 'n';
        }
    }
    /* j列の要素が全て白のとき、3つめのboxのj列目の
    要素をすべて"n"にし、それ以外の時はすべて"y"にする */
    for (int j = 0; j < width; j++){
        for (int i = 0; i < height; i++){
            if (box[0][i][j] == '#'){
                for (int k = 0; k < height; k++){
                    box[2][k][j] = 'y';
                }
                break;
            }
            box[2][i][j] = 'n';
        }
    }
    /* 2つめ、3つめのboxの対応する要素がどちらとも"y"のときだけ
       boxの要素を出力する */
    for (int i = 0; i < height; i++){
        for (int j = 0; j < width; j++){
            if (box[1][i][j] == 'y' && box[2][i][j] == 'y'){
                printf("%c", box[0][i][j]);
            }
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
using namespace std;

int main(){
  int n;
  cin >> n;
  string s,t;
  cin >> s >> t;
  
  REP(i,n){
    cout << s[i] << t[i];
  }
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int N=1e3+5;

struct node{
    int x,y;
}pos[N*N];

int d;
int a[N][N],sum[90005][305];

void cal(int st,int en){
    int x=st,px=pos[x].x,py=pos[x].y;
    while(x!=en){
        if(en-x<d)
            break;
        x+=d;
        sum[x][st]=abs(pos[x].x-px)+abs(pos[x].y-py);
        if(x>d)
            sum[x][st]+=sum[x-d][st];
        px=pos[x].x;
        py=pos[x].y;
    }
}

int cal2(int st,int en){
    int x=st,px=pos[x].x,py=pos[x].y,ans=0;
    while(x!=en){
        x+=d;
        ans+=abs(pos[x].x-px)+abs(pos[x].y-py);
        px=pos[x].x;
        py=pos[x].y;
    }
    return ans;
}


int main(){
    int h,w;
    scanf("%d%d%d",&h,&w,&d);
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            scanf("%d",&a[i][j]);
            pos[a[i][j]].x=i;
            pos[a[i][j]].y=j;
        }
    }
    int q;
    scanf("%d",&q);
    if(d<=300){
        for(int i=0;i<=d-1;i++){
            cal(i,90000);
        }
        for(int i=1;i<=q;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%d\n",sum[r][l%d]-sum[l][l%d]);
        }
    }
    else{
        for(int i=1;i<=q;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%d\n",cal2(l,r));
        }
    }
    return 0;
}


Measured memory_bytes: 111744
#define _USE_MATH_DEFINES

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int main(){
	
	bool num[200] = {};
	int N;
	cin >> N;
	
	for(int i = 0; i < N; i++){
		int n;
		cin >> n;
		num[n] = true;
	}
	
	int ans = 0;
	
	for(int i = 1; i <= 100; i++){
		ans += num[i];
	}
	
	cout << ans << endl;
	
	return 0;
}

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

double distance(double x, double y, double z, double w){
    double delta_x = z - x;
    double delta_y = w - y;
    double squared_distance = (delta_x) * (delta_x) + (delta_y) * (delta_y);
    return pow(squared_distance, 0.5);
}

int main(){
    int n;
    cin >> n;
    
    vector<double> x(n+1), y(n+1);
    vector<double> v(n);
    
    for (int i = 0; i < n; i++){
        cin >> x[i+1] >> y[i+1];
        v[i] = i+1;
    }
    
    double sumOfDistance = 0;
    double factorial = 1;
    
    do{
        for (int i = 0; i < n-1; i++){
            sumOfDistance += distance(x[v[i]], y[v[i]], x[v[i+1]], y[v[i+1]]);
        }
    } while (next_permutation(v.begin(), v.end()));
    
    for (int i = 2; i <= n; i++) factorial *= i;
    
    double ans = sumOfDistance / factorial;
    
    cout << fixed << setprecision(10);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std;

#define INF 999999999

int mindist[10010];
int min_prev_edge_cost[10010];

// edges[u] = (v, (dist, cost))
vector<pair<int, pair<int,int> > > edges[10010];
int _edge_dist(const pair<int, pair<int,int> > &p) { return p.second.first; }
int _edge_cost(const pair<int, pair<int,int> > &p) { return p.second.second; }
int _edge_node(const pair<int, pair<int,int> > &p) { return p.first; }

int main() {
    int N,M;
    while (cin >> N >> M, N || M) {
        // init
        for (int i=0; i<=N; ++i) mindist[i] = min_prev_edge_cost[i] = INF;
        for (int i=0; i<=N; ++i) edges[i].clear();

        for (int i=0; i<M; ++i) {
            int u,v,d,c; cin >> u >> v >> d >> c;
            edges[u].push_back( make_pair(v, make_pair(d,c)) );
            edges[v].push_back( make_pair(u, make_pair(d,c)) );
        }

        priority_queue<pair<int, int> > q; // <dist, node>
        q.push( make_pair(0, 1) );
        mindist[1] = 0;
        min_prev_edge_cost[1] = 0;

        while (!q.empty()) {
            int curr_dist = q.top().first * -1;
            int curr_node = q.top().second;
            q.pop();

            // todo:?????????
            if (mindist[curr_node] < curr_dist) continue;
            
            for (int i=0; i<edges[curr_node].size(); ++i) {
                int next_node = _edge_node(edges[curr_node][i]);
                int next_dist = curr_dist + _edge_dist(edges[curr_node][i]);
                int cost = _edge_cost(edges[curr_node][i]);
                if (mindist[next_node] > next_dist) {
                    mindist[next_node] = next_dist;
                    min_prev_edge_cost[next_node] = cost;
                    q.push( make_pair(next_dist * -1, next_node) );
                } else if (mindist[next_node] == next_dist && min_prev_edge_cost[next_node] > cost) {
                    min_prev_edge_cost[next_node] = cost;
                }
            }
        }

        // ????¨?
        int ans = 0;
        for (int i=1; i<=N; ++i) {
            ans += min_prev_edge_cost[i];
        }

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

Measured memory_bytes: 5016
#include <iostream>
#include <vector>

using namespace std;
const int MAXN = 1e5+10;
const int MAXT = 1e5+10;

int N, C;
int s[MAXN], t[MAXN], c[MAXN];
int dp[31][MAXN];

void solve() {
  for (int i=0;i<N;i++) {
    dp[c[i]-1][s[i]-1]++;
    dp[c[i]-1][t[i]]--;
  }
  for (int i=0;i<C;i++) {
    for (int j=1;j<MAXT;j++) {
      dp[i][j] += dp[i][j-1];
    }
  }
  for (int i=0;i<C;i++) {
    for (int j=0;j<MAXT;j++) {
      dp[i][j] = min(dp[i][j], 1);
    }
  }
  int cnt = 0;
  for (int i=0;i<MAXT;i++) {
    int tmp = 0;
    for (int j=0;j<C;j++) {
      tmp += dp[j][i];
    }
    cnt = max(cnt, tmp);
  }
  cout << cnt << endl;
}

int main() {
  cin >> N >> C;
  for (int i=0;i<N;i++) {
    cin >> s[i] >> t[i] >> c[i];
  }
  solve();
}


Measured memory_bytes: 13568
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	/*/TODO:!!!!!!!テスト用!!!!!!!!!
	sc = bufio.NewScanner(strings.NewReader(`

		10
	1 2 5 3 4 6 7 3 2 4
	1 2
	2 3
	3 4
	4 5
	3 6
	6 7
	1 8
	8 9
	9 10

				`))
	//TODO:!!!!!!!テスト用!!!!!!!!!*/

	/*/TODO:!!!!!!!テスト用!!!!!!!!!
	fp, err := os.Open("d:\\Users\\to_ke\\Desktop\\path_02.txt")
	if err != nil {
		panic(err)
	}
	defer fp.Close()
	sc = bufio.NewScanner((fp))
	//TODO:!!!!!!!テスト用!!!!!!!!!*/

	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)
	defer out.Flush() // !!!!caution!!!! you must use Fprint(out, ) not Print()
	/* --- code --- */
	//fmt.Fprintln(out, "[DEBUG]", time.Now())
	//https://atcoder.jp/contests/abc165/tasks/abc165_f
	//https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAA0887IQFx5BcrZcrpRD7uga/ABC165/F?dl=0&subfolder_nav_tracking=1

	n := nextInt()
	a := nextInts(n)

	r := make([][]int, n)

	edge := make([][]int, n)
	max := 0
	for i := 0; i < n-1; i++ {
		u, v := nextInt()-1, nextInt()-1
		edge[u] = append(edge[u], v)
		edge[v] = append(edge[v], u)

	}
	for i := 0; i < n; i++ {
		r[i] = []int{}

		if max < a[i] {
			max = a[i]
		}
	}

	lis := make([]int, n+1)
	for i := 0; i < len(lis); i++ {
		lis[i] = max + 2
	}

	ans := make([]int, n)

	var search func(int)
	search = func(p int) {
		//fmt.Fprintln(out, "[DEBUG]", wa)
		lisp := sort.SearchInts(lis, a[p])
		old := lis[lisp]
		lis[lisp] = a[p]

		ans[p] = sort.SearchInts(lis, max+1)

		for i := 0; i < len(edge[p]); i++ {
			// 未探索の頂点を追加
			if ans[edge[p][i]] == 0 {
				search(edge[p][i])
			}
		}

		lis[lisp] = old
	}
	//search(0, []int{})
	search(0)

	//fmt.Fprintln(out, "[DEBUG]", time.Now())

	for i := 0; i < n; i++ {
		fmt.Fprintln(out, ans[i])
	}

	//fmt.Fprintln(out, "[DEBUG]", d)
	//fmt.Fprintln(out, "[DEBUG]", time.Now())
	//fmt.Fprintln(out, ans)
}

//------------------------------------------------------------------------------

// -*-*-*-*-*-*-*-*-
// * I/O utilities *
// -*-*-*-*-*-*-*-*-

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

func chars(s string) []string {
	ret := make([]string, len([]rune(s)))
	for i, v := range []rune(s) {
		ret[i] = string(v)
	}
	return ret
}


Measured memory_bytes: 77292
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
typedef pair<ll, ll> PL;
const ll mod = 1e9 + 7;

const ll inf = 1e14;

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string a, b;
  cin >> a >> b;
  int n = a.size();
  VL lft(n, inf), rgt(n, inf);
  REP(i, 0, n) {
    ll r = i, l = (n - i) % n;
    REP(j, 0, n) {
      if (b[(i + j) % n] == '1') {
        lft[j] = min(lft[j], l);
        rgt[j] = min(rgt[j], r);
      }
    }
  }
  ll mi = inf;
  /*
  // <===0---|
  REP(r, 0, n) {
    ll l = 0;
    REP(i, 0, n) {
      if (b[(i + r) % n] != a[i]) {
        l = max(l, lft[i]);
      }
    }
    mi = min(mi, 2 * l + r);
  }
  // |----0===>
  REP(l, 0, n) {
    ll r = 0;
    REP(i, 0, n) {
      if (b[(i - l + n) % n] != a[i]) {
        r = max(r, rgt[i]);
      }
    }
    mi = min(mi, l + 2 * r);
  }
  */
  // <==---0=====>
  REP(stop, -n + 1, n) {
    vector<PL> pool;
    REP(i, 0, n) {
      if (b[(i + stop + n) % n] != a[i]) {
        pool.push_back(PL(lft[i], rgt[i]));
      }
    }
    sort(pool.begin(), pool.end());
    int m = pool.size();
    VL rma(m + 1, 0);
    for (int i = m - 1; i >= 0; --i) {
      rma[i] = max(rma[i + 1], pool[i].second);
    }
    REP(l, max(0, -stop), n) {
      int idx = upper_bound(pool.begin(), pool.end(), PL(l, inf + 1))
        - pool.begin();
      ll rmax = rma[idx];
      rmax = max(rmax, (ll)stop);
      mi = min(mi, 2 * (l + rmax) - abs(stop) + m);
    }
  }
  cout << (mi >= inf ? -1 : mi) << endl;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define y1 y11
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define skip continue
#define all(x) x.begin(), x.end()
#define NAME "code"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pii;
typedef pair<ll, pii> piii;
 
const ll inf = 1e9;
const int maxn = 1e3 + 11;

ll n, a, b;

int main(){

cin >> n >> a >> b;
if(n == 1 && a == b) cout << 1;
else if(a > b || n < 2) cout << 0;
else cout << (b - a) * (n - 2) + 1;

return 0;
}

Measured memory_bytes: 256
var lines = [];

var n=0;
var k=0;

var readline = require('readline');
var rl = readline.createInterface({
  input:  process.stdin,
  output: process.stdout
});

rl.on('line',function(x){
  lines.push(x);
});

rl.on('close',function(){
  n = Number(lines[0].split(" ")[0]);
  k = Number(lines[0].split(" ")[1]);

  if(n%2===0){
    if((Math.floor(n/2))<k || k<0){console.log("NO");}
    else{console.log("YES");}
  }
  else{
    if((Math.floor(n/2)+1)<k || k<0){console.log("NO");}
    else{console.log("YES");}
}

});


Measured memory_bytes: 7500
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-01-12 20:04:03
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;

template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { os << '{'; size_t n = vec.size(); for (size_t i = 0; i < n; ++i) { os << vec[i]; if (i != n - 1) os << ','; } os << '}'; return os; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }
template<class T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) { size_t n = vec.size(); for (size_t i = 0; i < n; ++i) is >> vec[i]; return is; }

#ifdef LOCAL
#define debug(_) cerr << #_ << ": " << (_) << '\n'
#else
#define debug(_) 1728
#endif


constexpr int dx[4] = {1, 0, -1, 0};
constexpr int dy[4] = {0, 1, 0, -1};

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

  int h, w; cin >> h >> w;
  char s[22][22];
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      cin >> s[i][j];
    }
  }

  auto bfs = [&](int x, int y) -> int {
    bool visited[h][w];
    fill(visited[0], visited[h], false);
    int shortest_dis[h][w];
    fill(shortest_dis[0], shortest_dis[h], 1e9);
    queue<pair<int, int>> que;

    que.push({x, y});
    visited[x][y] = 1;
    shortest_dis[x][y] = 0;

    while (!que.empty()) {
      pair<int, int> cur = que.front(); que.pop();
      for (int k = 0; k < 4; ++k) {
        int nx = cur.first + dx[k], ny = cur.second + dy[k];
        if (nx < 0 || nx >= h || ny < 0 || ny >= w || s[nx][ny] == '#') continue;
        if (visited[nx][ny]) continue;
        visited[nx][ny] = 1;
        shortest_dis[nx][ny] = shortest_dis[cur.first][cur.second] + 1;
        que.push({nx, ny});
      }
    }

    int ret = -1;
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        if (s[i][j] == '.'){
          ret = max(ret, shortest_dis[i][j]);
        }
      }
    }
    return ret;
  };

  int mx = -1;

  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      if (s[i][j] == '.') {
        mx = max(mx, bfs(i, j));
      }
    }
  }

  cout << mx << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
using namespace std;
long M=1e9+7;
long fac[3<<20],inv[3<<20],invfac[3<<20];
long pow(long a,long b){return b?pow(a*a%M,b/2)*(b%2?a:1)%M:1;}
long C(long a,long b)
{
	return fac[a]*invfac[a-b]%M*invfac[b]%M;
}
long H(long a,long b)
{
	return a==0&&b==0?1:C(a+b-1,b);
}
long a,b,c,sx,sy;
main()
{
	fac[0]=fac[1]=inv[1]=invfac[0]=invfac[1]=1;
	for(long i=2;i<3<<20;i++)
	{
		fac[i]=fac[i-1]*i%M;
		inv[i]=(M-M/i*inv[M%i]%M);
		invfac[i]=invfac[i-1]*inv[i]%M;
	}
	while(cin>>a>>b>>c>>sx>>sy,a+b+c)
	{
		long ans=0;
		for(long i=0;i<=sx-a&&i<=sy-b;i++)
		{
			if(sx-i>0&&a==0||sy-i>0&&b==0)continue;
			ans=(ans+H(a,sx-i-a)*C(a+b+c,a)%M*H(b,sy-i-b)%M*C(b+c,b)%M*H(a+b+c,i)%M)%M;
		}
		cout<<ans<<endl;
	}
}



Measured memory_bytes: 76800
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
  ll t;
  cin >> t;
  ll a=0,b=0,c=0,d=0;
  while(t--)
  {
    string s;
    cin >> s;
    if(s=="AC")
      a++;
    else if(s=="WA")
      b++;
    else if(s=="TLE")
      c++;
    else if(s=="RE")
      d++;
  }
  cout << "AC x " << a << endl;
  cout << "WA x " << b << endl;
  cout << "TLE x " << c << endl;
  cout << "RE x " << d << endl;
  return 0;
}

Measured memory_bytes: 3584
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    vector<pair<int, int>> a;
    rep(i, N) {
        int t; cin >> t;
        a.push_back({t, i + 1});
    }
    sort(a.begin(), a.end());
    vector<int> ans;
    int lastused = -1;
    int prev = -1;
    rep(i, K + 1) {
        for(int j = N - 1; j >= 0; j--) {
            if(a[j].second == prev) continue;
            ans.push_back(a[j].second);
            a[j].first--;
            if(a[j].first < 0) {
                cout << -1 << endl;
                return 0;
            }
            lastused = a[j].second;
        }
        prev = lastused;
        sort(a.begin(), a.end());
        //rep(j, N) cout << a[j].first << " ";
        //cout << endl;
    }
    cout << ans.size() << endl;
    rep(i, ans.size()) {
        if (i != 0) cout << " ";
        cout << ans[i];
    }
    cout << endl;


    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, MOD = 1e9 + 7;
int tree[N], n, a[N];
void add(int x) {
	++ x;
	while (x <= n) {
		tree[x] ++;
		x += x & -x;
	}
}
int query(int x) {
	++ x;
	int res = 0;
	while (x) {
		res += tree[x];
		x -= x & -x;
	}
	return res;
}
int r[N], P[N];
int main() {
	P[0] = 1;
	for (int i = 1; i < N; ++ i) P[i] = 1LL * P[i - 1] * i % MOD;
	scanf("%d", &n);
	for (int i = 0; i < n; ++ i) r[i] = 1;
	int R = 0;
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", &a[i]);
		a[i] --;
		if (a[i] >= 0) r[a[i]] = 0; else R ++;
	}
	long long sum = 0;
	for (int i = n - 1; i >= 0; -- i) {
		if (r[i] == 1) (sum += i) %= MOD;
		r[i] += r[i + 1];
	}
	long long ans = P[R], sc = 0, tmp = 0;
	for (int i = 1; i <= n; ++ i) {
		if (a[i] >= 0) {
			(ans += 1LL * a[i] * P[n - i] % MOD * P[R]) %= MOD;
			(ans += 1LL * (MOD - query(a[i])) * P[n - i] % MOD * P[R]) %= MOD;
			(ans += 1LL * (MOD - 1LL * sc * (R - r[a[i]]) % MOD * P[R - 1] % MOD) * P[n - i]) %= MOD;
			add(a[i]);
			(tmp += r[a[i]]) %= MOD;
		}
		else {
			(ans += 1LL * sum * P[R - 1] % MOD * P[n - i]) %= MOD;
			(ans += MOD - 1LL * tmp * P[R - 1] % MOD * P[n - i]) %= MOD;
			(ans += MOD - 1LL * (R - 1) * R / 2 % MOD * sc % MOD * P[R - 2] % MOD * P[n - i]) %= MOD;
			sc ++;
		}
	}
	cout << ans << endl;
}



Measured memory_bytes: 8064
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 82;
const int tmp = 80 * 80 * 2;
int h,w,x;
int a[N][N];
bool dp[N][N][N * N * 2];
int main()
{
    scanf("%d%d", &h, &w);
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            scanf("%d", a[i] + j);
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            scanf("%d", &x), a[i][j] -= x;
    dp[1][1][abs(a[1][1])] = 1;
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            for (int k = 0; k <= tmp; ++k)
                if (dp[i][j][k])
                {
                    dp[i][j + 1][abs(k + a[i][j + 1])] = 1;
                    dp[i][j + 1][abs(k - a[i][j + 1])] = 1;

                    dp[i + 1][j][abs(k + a[i + 1][j])] = 1;
                    dp[i + 1][j][abs(k - a[i + 1][j])] = 1;
                }
    int ans = 1e9;
    for (int k = 0; k <= tmp; ++k)
        if (dp[h][w][k])
        {
            ans = k;
            break;
        }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 87040
m,n = map(int,input().split())
#print(m,n)

def mn (m,n):
    if n == 1:
        return m %1000000007
    elif n%2 == 1:
        return mn(m,n//2)**2 * m %1000000007
    elif n%2 == 0:
        return mn(m,n/2)**2 %1000000007

print(mn(m,n))


Measured memory_bytes: 5608
input()
A = [int(v) for v in input().split(' ')]

swap_count = 0
def swap(A, i, j):
    t = A[i]
    A[i] = A[j]
    A[j] = t

for i in range(0, len(A)):
    for j in range(len(A) - 1, i, -1):
        if A[j] < A[j-1]:
            swap(A, j, j-1)
            swap_count += 1

print(" ".join([str(v) for v in A]))
print(swap_count)




Measured memory_bytes: 5608
from pprint import pprint
# 盤面座標は8000x8000(x 2)
N = 8000

s = input()
target_x, target_y = map(int, input().split())

# "FTTFF" -> [1, 0, 2]と変換。'F1TF0TF2T'のこと
dat_f = [len(Fcount) for Fcount in s.split("T")]

# x, yの閾値判定するのが面倒なので倍用意する(index error対策)
# マイナスを含むxとyのDP用配列を作る +1するのは原点用
curmap_x = [False] * ((N * 2 * 2) + 1)
curmap_y = [False] * ((N * 2 * 2) + 1)
nextmap_x = [False] * ((N * 2 * 2) + 1)
nextmap_y = [False] * ((N * 2 * 2) + 1)

# 初期座標 0,0
if s[0] == "F":
    start = 1
    curmap_x[N * 2 + dat_f[0]] = True
    direction_x = False
else:
    start = 0
    curmap_x[N * 2] = True
    direction_x = True
curmap_y[N * 2] = True

# 今がx軸かの判定

for i in range(start, len(dat_f)):
    step = dat_f[i]
    if direction_x:
        for j in range(N, N + (N * 2) + 1):
            nextmap_x[j] = True if curmap_x[j - step] or curmap_x[j + step] else False
        curmap_x, nextmap_x = nextmap_x, curmap_x
    else:
        for j in range(N, N + (N * 2) + 1):
            nextmap_y[j] = True if curmap_y[j - step] or curmap_y[j + step] else False
        curmap_y, nextmap_y = nextmap_y, curmap_y

    direction_x = not direction_x

print("Yes" if curmap_x[N * 2 + target_x] and curmap_y[N * 2 + target_y] else "No")


Measured memory_bytes: 45444
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = { -1, 0, 1, 0 }; const int dy[] = { 0, 1, 0, -1 };

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n)  { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x)         { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};

int main() {
	int n;
	cin >> n;
	int even;
	REP(i,n) {
		int a;
		cin >> a;
		if (a % 2 == 0)
			even++;
	}
	cout << ((n - even) % 2 == 0 ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 86400
//#define double long double
#define int long long
using namespace std;
const int INF = 1LL<<55;
const double EPS = 1e-6;
int n;
double vol;
int A[N];

bool check(double x){
  double tank = vol;
  vector<double> his(N);
  for(int i=0;i<N;i++){
    tank -= A[i%N];
    tank=min(vol,tank+x);   
    if(tank < 0) return 0;
  }
  
  for(int i=0;i<N;i++){
    tank -= A[i%N];
    tank=min(vol,tank+x);
    his[i]  = tank;
    if(tank < 0) return 0;
  }
  
  for(int i=0;i<N;i++){
    tank -= A[i%N];
    tank=min(vol,tank+x);
    if(his[i] > tank) return 0;
  }
  
  return 1;
}  
double search(){
  double L=0,M,R=(1e6)+10,cnt=50;
  while(cnt--){
    M = (L+R)/2;
    if(check(M)) R = M;
    else L = M;
  }
  return L;
}

signed main(){
  while(1){
    cin>>n>>vol;
    if(!n&&vol==0)break;
    memset(A,0,sizeof(A));  
    for(int i=0,s,t,u;i<n;i++){
      cin>>s>>t>>u;
      while(s < t) A[s++] = u;
    }
    printf("%.10lf\n",search());
  }  
  return 0;
}

Measured memory_bytes: 4468
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

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

		String str[] = br.readLine().split(" ");

		int n = Integer.parseInt(str[0]);
		int m = Integer.parseInt(str[1]);

		UnionFindTree uft = new UnionFindTree(n);

		for (int i = 0; i < m; i++) {
			str = br.readLine().split(" ");

			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);

			uft.union(a - 1, b - 1);
		}

		long s[] = new long[n];
		for (int i = 0; i < n; i++) {
			s[(int) uft.find(i)]++;
		}

		long max = 1;
		for (int i = 0; i < n; i++) {
			max = Math.max(max, s[i]);
		}

		System.out.println(max);
	}
}

class UnionFindTree {

	long[] parent; // ルートノードのインデックス
	long[] rank; // 木の高さ

	public UnionFindTree(int size) {
		this.parent = new long[size];
		this.rank = new long[size];

		for (int i = 0; i < size; i++) {
			makeSet(i);
		}
	}

	public void makeSet(int i) {
		parent[i] = i;
		rank[i] = 0; // 集合の高さ
	}

	public void union(int x, int y) {
		int xRoot = (int) find(x);
		int yRoot = (int) find(y);

		// xが属する木の方が大きい場合
		if (rank[xRoot] > rank[yRoot]) {
			parent[yRoot] = xRoot; // yの親をxに更新

		} else if (rank[xRoot] < rank[yRoot]) {
			parent[xRoot] = yRoot;

		} else if (xRoot != yRoot) {
			parent[yRoot] = xRoot;
			rank[xRoot]++; // 同じ高さの木がルートの子として着くから
		}
	}

	// 引数の属する木のルートのidを返す
	public long find(long i) {
		if (i != parent[(int) i]) {
			parent[(int) i] = find(parent[(int) i]);
		}
		return parent[(int) i];
	}

	// 同じ木に属しているか
	public boolean same(int x, int y) {
		return find(x) == find(y);
	}
}


Measured memory_bytes: 59128
process.stdin.resume();
process.stdin.setEncoding('utf8');
// 自分の得意な言語で
// Let's チャレンジ！！

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
 

var a = parseInt(lines[0],10);

var aa = a/1.08;

if(Number.isInteger(aa)){
    console.log(aa);
}else{
    var bb = Math.ceil(aa);
    var cc = Math.floor(aa);
    if(Math.floor(bb*1.08)===a){
        console.log(bb);
    }else if(Math.floor(cc*1.08)===a){
       console.log(cc);}
       else{
           console.log(':(')
       }
}


});

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

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

        for(int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }

        Arrays.sort(a);

        System.out.println(a[a.length-1] - a[0]);
        sc.close();
    }
}


Measured memory_bytes: 23124