akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) container.begin(), container.end()
#define RALL(container) container.rbegin(), container.rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

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 (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}

const int INF = 1<<28;
const double EPS = 1e-8;
const int MOD = 1000000007;


class SegTree{
	typedef vi SegT;
	private:
		vector<SegT> val;
		int n;
	public:
		SegTree(const vector<int> &in){
			n=1;
			while(n<in.size())n<<=1;
			val=vector<SegT>(2*n);
			for(int i=n-1 + in.size()-1;i>=0;i--){
				if(n-1 <= i) val[i] = vi(1, in[i - (n-1)]);
				else{
					val[i] = vi(val[i*2+1].size() + val[i*2+2].size());
					merge(ALL(val[i*2+1]),ALL(val[i*2+2]), val[i].begin());
				}
			}
		}
		//[a, b) の値を取ってくる
		int query(int a,int b,int x,int k=0,int l=0,int r=-1){
			if(r==-1)r=n;
			if(r<=a||b<=l) return INF;
			if(a<=l&&r<=b){
				int res = INF;
				auto it = lower_bound(ALL(val[k]), x);
				if(it != val[k].end()) res = *it - x;
				if(it != val[k].begin()) res = min(res, x - *(--it));
				return res;
			}else{
				return min(query(a,b,x,k*2+1,l,(l+r)/2),query(a,b,x,k*2+2,(l+r)/2,r));
			}
		}
};
int n, q;
main(){
	scanf("%d", &n);
	vi d(n);
	REP(i, n) scanf("%d", &d[i]);
	SegTree seg(d);
	scanf("%d", &q);
	REP(i, q){
		int l, r, D;
		scanf("%d %d %d", &l, &r, &D);
		printf("%d\n", seg.query(l, r+1, D));
	}
	return 0;
}


Measured memory_bytes: 19336
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll a,b,c,k;
  cin >> a >> b >> c >> k;
  int ans=a-b;
  if(k%2==0) cout << ans <<endl;
  else cout << -ans << endl;
  return 0;
}


Measured memory_bytes: 764
N = int(input())
S = input()
ans = -1
for i in range(N):
    S1 = S[0:i+1]
    S2 = S[i+1:]
    #print(S1, S2)
    dic_S1 = {}
    for j in S1:
        if j not in dic_S1:
            dic_S1[j] = 1
    tmp = 0
    for j in S2:
        if j in dic_S1:
            tmp += 1
            del dic_S1[j]
    ans = max(tmp, ans)
print(ans)

Measured memory_bytes: 3064
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,k = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    l = 1
    r = 10**9+1
    while l != r:
        mid = l+(r-l)//2
        nm = 0
        for i in a:
            nm += (i-1)//mid
        if nm > k:
            l = mid+1
        else:
            r = mid

    print(r)

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 94932
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
#define double long double
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
#define eps 1e-12 
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N; cin >> N;
	VI A(N);
	REP(i, N)cin >> A[i];
	SORT(A);
	VI cnt(1000002, 0);
	fore(i, A) {
		if (cnt[i] != 0) {
			cnt[i] = 2;
			continue;
		}
		for (int j = i; j < 1000002; j += i)cnt[j]++;
	}

	int ans = 0;
	fore(i, A)if (cnt[i] == 1)ans++;
	cout << ans << endl;
	return 0;
}



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

int main()
{
    long long int h, w;
    cin >> h >> w;
    if (h == 1 || w == 1){
        cout << 1 << endl;
    }else{
        if(h * w % 2 == 0) cout << h * w / 2 << endl;
        else cout << (h * w + 1) / 2 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
typedef long long ll;
using namespace std;
int main(void){
    ll n,k;
    cin>>n>>k;
    if(n>=k){
        ll kai = n/k;
        n = n-k*kai;
    }
    if(n<k)n=min(n,abs(n-k));
    cout<<n<<endl;
}

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll H, W, K; cin >> H >> W >> K;
    ll dp[H+1][W];
    for(int i=0;i<=H;i++){
        for(int j=0;j<W;j++){
            dp[i][j] = 0;
        }
    }
    dp[0][0] = 1;
    for(int i=1;i<=H;i++){
        for(int bit=0;bit < (1 << (W - 1));bit++){
            // cout << bit << endl;

            // exist bridge between i and i + 1 or not
            bool br[W-1]; // 0, ..., W - 2
            for(int j=0;j<W-1;j++) br[j] = false;
            for(int t=0;t<W-1;t++){
                if(bit & (1 << t)){
                    br[t] = true;
                }
            }

            // check br is valid
            bool isvalid = true;
            for(int j=0;j<W-2;j++){
                if(br[j] && br[j+1]){
                    isvalid = false;
                    break;
                }
            }
            if(!isvalid) continue;

            for(int j=0;j<W;j++){
                if(j-1 >= 0 && br[j-1]){
                    // left
                    dp[i][j] += dp[i-1][j-1];
                    dp[i][j] %= MOD;
                }else if(j <= W-2 && br[j]){
                    // right
                    dp[i][j] += dp[i-1][j+1];
                    dp[i][j] %= MOD;
                }else{
                    dp[i][j] += dp[i-1][j];
                    dp[i][j] %= MOD;
                }
            }
        }
    }
    cout << dp[H][K - 1] << endl;
}

Measured memory_bytes: 256
from collections import defaultdict

M = 998244353
B = pow(10, 18, M)
N = int(input())

def ext_euc(a, b):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, b
  while z1 != 1:
    d, m = divmod(z2,z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1, y1

def inv_mod(a, b, m):
  x, y = ext_euc(a, m)
  return (x * b % m)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(e):
  g = {}
  for i in range(N, 0, -1):
    if i not in e:
      continue
    m = mex({g.get(j, 0) for j in e[i]})
    if m:
      g[i] = m
  sum_g = defaultdict(int)
  sum_g[0] = inv_mod(B-1, pow(B, N+1, M)-B, M)
  x = 1
  for i in range(1, N+1):
    x = (x * B) % M
    if i in g:
      sum_g[g[i]] = (sum_g[g[i]] + x) % M
      sum_g[0]  = (sum_g[0] - x) % M
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(set)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].add(b)
  return e

def solve(N, edge):
  sum_g = list(map(calc_grundy, edge))
  ret = 0
  for gx, sx in sum_g[0].items():
    for gy, sy in sum_g[1].items():
      gz = gx^gy
      sz = sum_g[2][gz]
      if sz:
        ret = (ret + sx*sy*sz) % M
  return ret


edge = [read_edge() for i in range(3)]

print(solve(N, edge))

Measured memory_bytes: 116568
# import bisect
# import copy
# import fractions
# import math
# import numpy as np
# from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

def resolve():
    n=int(input())

    [A,B,C]=[[0]*n for _ in range(3)]
    for i in range(n):
        A[i],B[i],C[i]=map(int,input().split())

    dp=[[0]*3 for _ in range(n)]

    dp[0]=[A[0],B[0],C[0]]

    for i in range(n-1):
        dp[i+1][0]=max(dp[i][1]+A[i+1],dp[i][2]+A[i+1])
        dp[i+1][1]=max(dp[i][0]+B[i+1],dp[i][2]+B[i+1])
        dp[i+1][2]=max(dp[i][0]+C[i+1],dp[i][1]+C[i+1])

    print(max(dp[n-1]))



resolve()

Measured memory_bytes: 61528
#include <iostream>
#include<string>
#define den 1000000007
using namespace std;

int main() {
	string s;cin>>s;
	int n=s.size();
	int a[n],c[n],h[n];

	for(int i=0;i<n;i++){
		a[i]=c[i]=h[i]=0;
		switch(s[i]){
				 case 'A':
					 a[i]=1;
					 break;
				 case 'C':
					 c[i]=1;
					 break;
				 case'?':
					 h[i]=1;
					 break;
		}
	}
	long long lpow=1;
	long long la[n];
	switch(s[0]){
			 case 'A':
				 la[0]=1;
				 break;
			 case'?':
				 lpow*=3;
				 la[0]=1;
				 break;
			 default:
				 la[0]=0;
	}
	for(int i=1;i<n;i++){
		switch(s[i]){
				 case 'A':
					 la[i]=la[i-1]+lpow;
					 break;
				 case'?':
					 la[i]=la[i-1]*3+lpow;
					 lpow*=3;
					 break;
				 default:
					 la[i]=la[i-1];
		}
		if(la[i]>den)la[i]%=den;
		if(lpow>den)lpow%=den;
	}
	long long rpow=1;
	long long rc[n];
	switch(s[n-1]){
			 case 'C':
				 rc[n-1]=1;
				 break;
			 case'?':
				 rpow*=3;
				 rc[n-1]=1;
				 break;
			 default:
				 rc[n-1]=0;
	}
	for(int i=n-2;i>=0;i--){
		switch(s[i]){
				 case 'C':
					 rc[i]=rc[i+1]+rpow;
					 break;
				 case'?':
					 rc[i]=rc[i+1]*3+rpow;
					 rpow*=3;
					 break;
				 default:
					 rc[i]=rc[i+1];
		}
		if(rc[i]>den)rc[i]%=den;
		if(rpow>den)rpow%=den;
	}
	long long ans=0;
	for(int i=1;i<n-1;i++){
		if((s[i]=='B')+(s[i]=='?')){
		long long add=la[i-1]*rc[i+1];
		if(add>den)add%=den;
		ans+=add;
		if(ans>den)ans%=den;
		}
	}
	cout<<ans<<endl;
//	for(int i=0;i<n;i++){
//		cout<<la[i]<<' ';
//	}
//	cout<<endl;
//	for(int i=0;i<n;i++){
//		cout<<rc[i]<<' ';
//	}
//	cout<<endl;
	return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#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 REP(i, m, n) for(int i = (m); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

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

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

template<class T> inline auto __lcm(T& a, T& b) 
{ return a * b / __gcd(a, b); }


int main() {
    ll N;  cin >> N;
    vector<ll> H(N);  rep(i, N) cin >> H[i];

    vector<ll> sum;
    ll tmp = 0;
    rep(i, N) {
        chmax(tmp, H[i]);
        sum.pb(tmp-1);
    }

    rep(i, N) {
        if (H[i] < sum[i]) {
            no;
            return 0;
        }
    }

    yes;
    return 0;
}



Measured memory_bytes: 2168
using System;
using System.Collections;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Xml.Schema;
using static System.Console;

namespace ConsoleApp2
{
    class Program
    {
        static public int[] Sarray() { return ReadLine().Split().Select(int.Parse).ToArray(); }
        static public List<int> Slist() { return new List<int>(ReadLine().Split().Select(int.Parse)); }
        static void Main(string[] args)
        {
            var NM = Sarray();
            var N = NM[0];
            var M = NM[1];
            var fl = new HashSet<int>();
            var ll = new HashSet<int>();
            for (var i=0;i<M;i++)
            {
                var ab = Sarray();
                if (ab[0] == 1 && !fl.Contains(ab[1])) fl.Add(ab[1]);
                if (ab[1] == N && !ll.Contains(ab[0])) ll.Add(ab[0]);
            }
            foreach(var f in fl)
            {
                if(ll.Contains(f))
                {
                    WriteLine("POSSIBLE");
                    return;
                }
            }
                    WriteLine("IMPOSSIBLE");
        }
    }
}


Measured memory_bytes: 25624
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    String S  = sc.next();
    char[]ss = S.toCharArray();
 
    if(ss[0]+0 >= 65 && ss[0]+0<= 90){
    	System.out.println("A");
    }else{
	System.out.println("a");
      }
}
}

Measured memory_bytes: 35560
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; ++i)
#define rep(i,n) for(int i = 1; i <= n; ++i)
#define boost ios::sync_with_stdio(0)
#define ms0(s) memset((s), 0, sizeof(s))
#define INF 0x3f3f3f3f
#define ABS(x) ((x)<0 ? (-(x)) : (x))
#define forvec(it,v) for(vector<int>::iterator it = v.begin(); it != v.end(); ++it)
 
#ifdef LOCAL
#define DEBUG 1
#else
#define DEBUG 0
#endif
#define $ if(DEBUG)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template <typename T>
inline void read(T& x){
	int w = 1; T data = 0;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-') ch = getchar();
	if(ch == '-') w = -1, ch = getchar();
	while(isdigit(ch))
		data = 10 * data + ch - '0', ch = getchar();
	x = data * w;
}
 
const int maxn = 100005;
int a[maxn], n, m;
pii seg[maxn];
bool cmp(pii p1, pii p2){
	return p1.second < p2.second || (p1.second == p2.second && p1.first > p2.first);
}
int main()
{
	read(n), read(m);
	REP(i, m) read(seg[i].first), read(seg[i].second);
	sort(seg, seg + m, cmp);
	int pt = seg[0].second, cnt = 1;
	for(int i = 0; i < m; ++i){
		if(seg[i].first < pt) continue;
		pt = seg[i].second;
		cnt++;
	}
	printf("%d\n", cnt);
}

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

int main()
{
	int n;
	cin >> n;
	vector<int> v(n);
	for (auto& a : v) {
		cin >> a;
	}

	long long ret = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i + 1; j < n; ++j)
		{
			for (int k = j + 1; k < n; ++k)
			{
				if (v[i] == v[j] || v[j] == v[k] || v[k] == v[i]) {
					continue;
				}
				vector<int> t(3);
				t[0] = v[i];
				t[1] = v[j];
				t[2] = v[k];
				sort(t.begin(), t.end());
				if (t[2] < t[0] + t[1]) {
					++ret;
				}
			}
		}
	}
	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int a,now,ans;
char u;
int main(){
    cin>>a;
    for(int s=0;s<a;s++){
        cin>>u;
        if(u=='I')now++;
        else
        now--;
        ans=max(ans,now);
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(){
  int Nmade,Ncont; 
  cin >> Nmade;
  unordered_map<int, int> diffs_made;
  int diff;
  for(int i=0; i<Nmade; i++){
    cin >> diff;

    if(!diffs_made.count(diff)){
      diffs_made[diff]= 1;
    }
    else{
      diffs_made.at(diff)++;
    }
  }

  cin >> Ncont;

  bool is_satisfied= true;
  for(int i=0; i<Ncont; i++){
    cin >> diff;

    if(!diffs_made.count(diff) || diffs_made.at(diff)==0){
      is_satisfied= false;
      break;
    }
    else{
      diffs_made.at(diff)--;
    }
  }

  string ans= is_satisfied ? "YES"
                           : "NO";

  cout << ans << endl;
}

Measured memory_bytes: 8520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=200005;
const ll INF=1LL<<60;
map<ll,ll> dis;
ll N,A,B,C,D;

vector<ll> x={2,3,5},y;

void dijkstra(){
    dis[N]=0;
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> PQ;
    y={A,B,C};
    
    PQ.push(make_pair(0LL,N));
    while(!PQ.empty()){
        ll a=PQ.top().first;
        ll b=PQ.top().second;
        PQ.pop();
        if(dis[b]<a) continue;
        
        for(int i=0;i<3;i++){
            if(b%x[i]==0){
                if(dis.count(b/x[i])==0||dis[b/x[i]]>a+y[i]){
                    dis[b/x[i]]=a+y[i];
                    PQ.push(mp(dis[b/x[i]],b/x[i]));
                }
            }else{
                ll to=b/x[i];
                if(to>=0){
                    if(dis.count(to)==0||dis[to]>a+y[i]+D*(b-to*x[i])){
                        dis[to]=a+y[i]+D*(b-to*x[i]);
                        PQ.push(mp(dis[to],to));
                    }
                }
                to++;
                if(to>=0){
                    if(dis.count(to)==0||dis[to]>a+y[i]+D*(to*x[i]-b)){
                        dis[to]=a+y[i]+D*(to*x[i]-b);
                        PQ.push(mp(dis[to],to));
                    }
                }
            }
        }
        
        if(log10(D)+log10(b)<=18.0){
            if(dis.count(0)==0) dis[0]=a+D*b;
            else chmin(dis[0],a+D*b);
        }
    }
    return;
}//a,dが長さ

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int Q;cin>>Q;
    while(Q--){
        cin>>N>>A>>B>>C>>D;
        dis.clear();
        dijkstra();
        
        cout<<dis[0]<<endl;
    }
}


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

int main() {
  int m, f, r;
  char grade;

  while (true) {
    cin >> m >> f >> r;
    if (m < 0 && f < 0 && r < 0)
      break;

    if (m < 0 || f < 0) {
      grade = 'F';
    } else if (80 <= m + f) {
      grade = 'A';
    } else if (65 <= m + f) {
      grade = 'B';
    } else if (50 <= m + f) {
      grade = 'C';
    } else if (30 <= m + f) {
      if (50 <= r)
        grade = 'C';
      else
        grade = 'D';
    } else {
      grade = 'F';
    }
    cout << grade << endl;
  }

  return 0;
}



Measured memory_bytes: 3076
#include <stdio.h>
#define INF 1010001000
#define min(a, b) a<b?a:b

int road[20][20];

int main(void)
{
    int i, j, k, n, m, a, b, c, d, cost, money;
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            road[i][j] = INF;
        }
    }
    for (i = 0; i < m; i++) {
        scanf("%d,%d,%d,%d", &a, &b, &c, &d);
        road[a-1][b-1] = c;
        road[b-1][a-1] = d;
    }
    scanf("%d,%d,%d,%d", &a, &b, &money, &cost);
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                road[i][j] = min(road[i][j], road[i][k] + road[k][j]);
            }
        }
    }
    printf("%d\n", money - cost - road[a-1][b-1] - road[b-1][a-1]);
    return 0;
}

Measured memory_bytes: 600
N,K = map(int,input().split())
L = []
for i in range(N):
  L.append(int(input()))
L.sort()
ans = float('inf')
for i in range(N-K+1):
  cur = L[i+K-1]-L[i]
  if cur <= ans:
    ans = cur
print(ans)

Measured memory_bytes: 7384
t = list(input())
n = int(input())
for i in range(n):
    cmd, a, b, *c = input().split()
    a = int(a)
    b = int(b)
    if cmd == "print":
        print(*t[a:b+1], sep='')
    elif cmd == "reverse":
        t[a:b+1] = reversed(t[a:b+1])
    else:
        t[a:b+1] = c[0]



Measured memory_bytes: 5736
# define _CRT_SECURE_NO_WARNINGS 1
# include <iostream>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <map>
# include <stack>
using namespace std;
# define M_PI 3.141592
# define FOR(i,n) for(int i=0;i<(int)n;i++)
# define FORI(i,k,n) for(int i=k;i<(int)n;i++)
# define toRad 2.0*M_PI/360.0
# define inin(x) int x;cin>>x;
# define all(x) x.begin(),x.end()
# define debug(x) cout<<#x<<" :"<<x<<endl;
# define rep(i,n) for(int i=0;i<(int)n;i++)
# define EPS 1e-12
# define CHECK(i,a) FOR(i,a.size())cout<<#a<<"["<<i<<"] : "<<a[i]<<endl; 


int main()
{
	int a, b;
	while (cin >> a >> b)
	{
		vector<int> c;
		stringstream ans;
		while (a >= b)a -= b;
		c.push_back(a);
		a *= 10;
		while (true)
		{
			int x = 0;
			while (a >= b)
			{
				a -= b;
				x++;
			}
			ans << x;
			if (a == 0)
			{
				cout << ans.str() << endl;
				break;
			}
			else
			{
				int p = c.size()-1;
				for (; p >= 0; p--)
				{
					if (c[p] == a)
					{
						break;
					}
				}
				if (p != -1)
				{
					cout << ans.str() << endl;
					for (int i = 0; i < p; i++)cout << ' ';
					for (int i = p; i < ans.str().size(); i++)cout << '^';
					cout << endl;
					break;
				}
			}
			c.push_back(a);
			a *= 10;
		}
	}
}

Measured memory_bytes: 1244
#include<iostream>
#include<queue>
#include<utility>

using namespace std;

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

char input[100][100];
int visit[100][100];
queue<pair<int,int> > q;
queue<int> q2;

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

int main(){
	IOS;
	int h,w,sum=0,ans=1e9;
	while(cin>>h>>w){
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin>>input[i][j];
				if(input[i][j] == '.'){
					sum++;
				}
			}
		}
		sum--;
		
		q.push(make_pair(0,0));
		q2.push(0);
		visit[0][0]=1;
		while(!q.empty()){
			int x=q.front().first;
			int y=q.front().second;
			int z=q2.front();
			q.pop();
			q2.pop();
			if(x == h-1 and y == w-1){
				ans=z;
				break;
			}
			for(int i=0;i<4;i++){
				int nx=x+dx[i];
				int ny=y+dy[i];
				if(nx >= 0 and nx<h and ny >= 0 and ny<w and input[nx][ny] != '#' and visit[nx][ny] != 1){
					q.push(make_pair(nx,ny));
					q2.push(z+1);
					visit[nx][ny] =1;
				}
			}
		}
		
		if(ans == 1e9){
			cout<<-1<<endl;
		}
		else{
			cout<<sum-ans<<endl;
		}
		
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define PLI pair<ll,int>
using namespace std;
const int N=1e5+10;
string s[N];
int main()
{
//	freopen("UVA1636_input.txt","r",stdin); 
//	 freopen("UVA1636_out.txt","w",stdout);	
	int n;
	cin>>n;
	ll ans=0,x=0;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		sort(s[i].begin(),s[i].end());
	}
	sort(s+1,s+n+1); 
	for(int i=2;i<=n;i++)
	{
		if(s[i]==s[i-1])
		{
			x=x+1;
		}
		else
		{
			ans=ans+(x*(x+1)/2);	
			x=0;
		}
	}
	if(s[n]==s[n-1])
	ans=ans+x*(x+1)/2;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 7296
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
	int n;
	vector<pair<int, int>> a;
	cin >> n;
	for (int i = 0, b, d; i < n; ++i) {
		cin >> b >> d;
		a.push_back({ b,d });
	}
	sort(a.begin(), a.end(), [](pair<int, int> t, pair<int, int> k) {return t.second < k.second ? true : t.second > k.second ? false :
		t.first < k.first ? true : false; });

	int h = 0;
	for (int i = 0; i < n; ++i) {
		h += a[i].first;
		if (h > a[i].second) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T>
string join(const vector<T>&v, string del=", "){ stringstream s;
    for(auto x : v) s << del << x; return s.str().substr(del.size());
}
template<typename T>
ostream& operator<<(ostream& o, const vector<T>&v){
    if(v.size()) o << "[" << join(v) << "]"; return o;
}
template<typename T>
ostream& operator<<(ostream& o, const vector<vector<T> >&vv){
    int l = vv.size();
    if(l){ o<<endl; rep(i,l) o << (i==0 ? "[ " : ",\n  " ) << vv[i] << (i==l-1 ? " ]" : ""); }
    return o;
}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");
    int h, w; cin >> h >> w;
    vvi c(10, vi(10));
    rep(i,10) rep(j,10) cin >> c[i][j];
    vvi a(h, vi(w));
    rep(i,h) rep(j,w) cin >> a[i][j];

    rep(k,10) rep(i,10) rep(j,10){
        c[i][j] = min(c[i][j], c[i][k] + c[k][j]);
    }

    int ans = 0;
    rep(i,h) rep(j,w){
        if(a[i][j] == -1) continue;
        ans += c[a[i][j]][1];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 384
n = int(input())
n = n-1
ans = 0


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

li = make_divisors(n)
n = n+1
for i in range(2,n+1):
    if i**2 > n:
        break
    tmp = n
    #print(i)
    while tmp % i == 0:
        #print(tmp)
        #exit()
        tmp = tmp / i
    if tmp % i == 1:
        ans += 1
        li.append(i)
#print(li)
print(len(set(li)))

exit()

for i in range(2,n+1):
    """
    if i**2 > n:
        break
    """
    tmp = n
    #print(i)
    if tmp % i == 0:
        #print(tmp)
        #exit()
        #tmp = tmp / i
        ans += 1
        print(i)
    """
    if tmp == 1:
        ans += 1
        print(i)
    """
        
print(ans)

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

#define ll long long
#define ull unsigned long long
#define N 100005
#define mod 998244353 
#define boost ios_base::sync_with_stdio(false);cin.tie(0)
#define prec(n) fixed<<setprecision(n)

#define mii unordered_map<int,int>
#define mll unordered_map<ll,ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi  first

#define se second
#define pb push_backP
#define mp make_pair
#define pp pop_back
#define vii vector<int>
#define vll vector<ll>
#define vpp vector<pii>
#define all(c) c.begin(),c.end()
#define tr(it,c) for(it = c.begin() ; it!=c.end() ; it++)
int inf = INT_MAX ;
ll modulo(ll num,ll MOD=mod){ return ((num%MOD)+MOD)%MOD;} // for negative integer
ll power(ll b,ll e,ll MOD=mod){ll ans=1; while(e){if(e%2) ans=(ans*b)%MOD; b=(b*b)%MOD; e/=2;} return ans;}
ll inv(ll num,ll MOD=mod){ return power(modulo(num),MOD-2,MOD); }
ll gcd(ll a,ll b){ return ((b==0) ? a:gcd(b,a%b));}

int main(){
	boost;
	

	ll h,n;
    cin>>h>>n;

    ll k,sum = 0;
    for(int i =0;i<n;i++){
        cin>>k;
        sum = sum +k;
    }

    if(sum>=h)
        cout<<"Yes";
    else{
        cout<<"No";
    }
}

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

int main(){
  int a, b;
  cin >> a >> b;

  vector<vector<char>> C(a,vector<char>(b));
  for(int i = 0; i < a; i++){
    for(int j = 0; j < b; j++){
      cin >> C[i][j];
    }
  }
  vector<vector<char>> D(2 * a,vector<char>(b));
  for(int i = 0; i < 2 * a; i++){
    for(int j = 0; j < b; j++){
      D[i][j] = C[i / 2][j];
      cout << D[i][j];
      if(j == b - 1){ cout << endl;}
    }
  }
}

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

public class Main { 
	public static void main(String[] args) throws IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		
		while (true) {
			int[] arr = new int[10];
			int[] arr2 = new int[10];
			
			String words = input.readLine();
			
			if (words == null) {
				break;
			}
			
			String[] split = words.split(" ");
			
			if (split.length < 4) {
				break;
			}
			
			for (int i = 0; i < 4; i++) {
				int a = Integer.parseInt(split[i]);
				arr[a]++;
				arr2[i] = a;
			}
			
			int hit = 0;
			int blow = 0;
			
			split = input.readLine().split(" ");
			
			for (int i = 0; i < 4; i++) {
				int b = Integer.parseInt(split[i]);
				
				if (arr2[i] == b) {
					hit++;
				} else if (arr[b] == 1) {
					blow++;
				}
			}
			
			System.out.println(hit + " " + blow);
		}
		
		input.close();
	}	
}

Measured memory_bytes: 24032
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]
INF = 10**9+7
ans = [0]*(N+1)
ans[1] = 1
if M != 0:
    s = A[0]
    if s == 1:
        ans[1] = 0
A = set(A)
ans[0] = 1

for i in range(2,N+1):
    if i in A:
        ans[i] = 0
    else:
        ans[i] = ans[i-1] + ans[i-2]
        ans[i] %= INF
        
print(ans[-1])

Measured memory_bytes: 13984
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i< (n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
//long long ccw(const Point& A, const Point& B, const Point& C) {
//	return 1LL * (B.x - A.x)*(C.y - A.y) - 1LL * (B.y - A.y)*(C.x - A.x);
//}
ll mod = 1000000007;
ll d[2001][2001];
ll go(int x, int y) {
	if (x == 0)return 1;
	if (y == 0 || x == y)return 1;
	if (y == 1)return x;

	ll &ret = d[x][y];
	if (ret != -1)return ret;
	d[x][y] = go(x - 1, y - 1) + go(x - 1, y);
	d[x][y] %= mod;
	return ret;
}
int main() {
	// D , D , 앳코더 1회 ㄱ? 
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, k; cin >> n >> k;
	memset(d, -1, sizeof(d));
	ll ans = 0;

	for (int i = 1; i <= k; i++) {
		ans = 0;
		ll cnt = go(k - 1, k - i);
		int R = n - k;
		if (R == 0) {
			if (i == 1) {
				cout << cnt << '\n';
			}
			else {
				cout << 0 << '\n'; 
			}
			continue;
		}
		if (i > 1 && R - 1 >= 0 && R - (i - 1) >= 0) {
			ans += (cnt * go(R - 1, R - (i - 1))) % mod; ans %= mod;
		}
		if (R - 1 >= 0 && R - i >= 0) {
			ans += (((cnt * go(R - 1, R - i)) % mod) * 2) % mod; ans %= mod;
		}
		if (R - 1 >= 0 && R - i - 1 >= 0) {
			ans += (cnt * go(R - 1, R - i - 1)) % mod; ans %= mod;
		}
		cout << ans << '\n';
	}


	// 2H3 = 2개를 중복을 허용해서 3개를 뽑는다.
	// 111,222, 112, 122, 
	// 3 0 , 0 3 2 1  1 2  
 

}

Measured memory_bytes: 31616
#include <bits/stdc++.h>
using namespace std;
#define maxn 510
#define ll long long
#define db double
#define vi vector<int>
#define pb push_back
#define mod 998244353
#define fi first
#define pi pair<int, int>
#define se second
#define mp make_pair
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
// head
ll a[maxn][maxn];
const int S = 20050;
bool bpr[S];
map<int, int> r[2];
ll gcd(ll a, ll b) {
	if (!b) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}	
int main() {
	vi pr;
	for (int i = 0; i < S; i++)
		bpr[i] = 1;
	for (int i = 2; i < S; i++) {
		if (!bpr[i]) continue;
		pr.pb(i);
		for (int j = 2; j * i < S; j++)
			bpr[i * j] = 0;
	}
	int n;
	cin >> n;
	if (n == 2) {
		cout << 4 << ' ' << 7 << endl << 23 << ' ' << 10 << endl;
		return 0;
	}
	int cnt = 0;
	for (int i = 1; i <= 2 * n; i += 2)
		r[0][i] = pr[cnt++];
	for (int i = -n - 1; i <= n + 1; i++)
		if (i % 2)
			r[1][i] = pr[cnt++];
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= n; j++) {
 			if ((i + j) % 2 == 0) {
	 			ll ns = 1ll * max(1, r[1][i - j + 1]) * max(1, r[1][i - j - 1]) * max(1, r[0][i + j + 1]) * max(1, r[0][i + j - 1]);
	 			a[i][j] = ns + 1;
			}
			else a[i][j] = r[0][i + j] * r[1][i - j];
			printf("%lld ", a[i][j]);
		}
		printf("\n");
	}
	return 0;
}


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

int main(void)
{
	int n;
	int ans; 
	int a[200010];
	int mini;

	cin >> n;
	ans = 0;
	rep(i, n) cin >> a[i];
	mini = a[0];
	rep(i, n)
	{
		if (mini >= a[i])
		{
			ans++;
			mini = a[i];
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <iomanip>
#include <cassert>
#include <atcoder/convolution>

using namespace std;
using namespace atcoder;
typedef long long ll;

int main()
{
   int N, M;
   cin >> N >> M;
   vector<ll> a(N);
   vector<ll> b(M);
   for (int i = 0; i < N; i++)
   {
      cin >> a[i];
   }
   for (int i = 0; i < M; i++)
   {
      cin >> b[i];
   }
   auto result = convolution(a, b);
   for (auto r : result)
   {
      cout << r << " ";
   }

   cout << endl;
   return 0;
}


Measured memory_bytes: 27192
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
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;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k,m;
    cin>>n>>k>>m;
    string s;
    cin>>s;
    ll now=0;
    V res1;
    while(now<n){
        if(s[now]=='o'){
            res1.push_back(now);
            now+=m+1;
        }else{
            now++;
        }
    }
    if(res1.size()!=k){
        return 0;
    }
    now=n-1;
    V res2;
    while(now>=0){
        if(s[now]=='o'){
            res2.push_back(now);
            now-=(m+1);
        }else{
            now--;
        }
    }
    if(res2.size()!=k){
        return 0;
    }
    reverse(all(res2));
    rep(i,k){
        if(res1[i]==res2[i]){
            cout<<res1[i]+1<<endl;
        }
    }
}


Measured memory_bytes: 5128
using System;

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = int.Parse(line[0]);
        var m = int.Parse(line[1]);
        var trip = Array.ConvertAll(Console.ReadLine().Trim().Split(' '), int.Parse);
        var cost = new long[n , 3];
        for (int i = 0; i < n - 1; i++)
        {
            string[] line2 = Console.ReadLine().Trim().Split(' ');
            for (int j = 0; j < 3; j++) cost[i+1, j] = int.Parse(line2[j]);
        }
        var countrail = new int[n ];
        for (int i = 1; i < m; i++)
        {
            var sfrom = Math.Min(trip[i], trip[i - 1]);
            var sto = Math.Max(trip[i], trip[i - 1]);
            for (int j = sfrom; j <= sto-1; j++)
                countrail[j]++;
        }
        var totalcost = 0L;
        for (int i = 1; i < n; i++)
        {
            long kami = countrail[i] * cost[i, 0];
            long icc = countrail[i] * cost[i, 1] + cost[i, 2];
            totalcost +=   Math.Min(kami, icc);
        }
        Console.WriteLine(totalcost);
    }
}

Measured memory_bytes: 19428
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define inf 1000000000000001
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,q,i,j,sum=0,b,c;
    cin>>n;
    vector<ll> v(n);
    map<ll,ll> ma;
    for(i=0;i<n;i++)
    {
        cin>>v[i];
        ma[v[i]]++;
        sum+=v[i];
    }
   // cout<<sum<<endl;
    cin>>q;
    while(q)
    {
        cin>>b>>c;
        if(ma[b]>0)
        {
            sum-=(ma[b]*b);
           // cout<<"1*"<<sum<<" ";
            ma[c]+=ma[b];
            sum+=(ma[b]*c);
            ma[b]=0;
        }
        cout<<sum<<endl;
        q--;
    }
    
    return 0;
     
}

Measured memory_bytes: 9680
import numpy as np

def main():
    count=0
    temp=input()
    l=list(map(int,list(temp.split(" "))))
    l.sort()
    
    sa1=l[2]-l[0]
    sa2=l[2]-l[1]
    if sa1%2==1 and sa2%2==1:
        sa1-=1
        sa2-=1
        count+=1
        count+=int(sa1/2)+int(sa2/2)
    elif sa1%2==1 and sa2%2==0:
        sa1+=1
        count+=1
        count+=int(sa1/2)+int(sa2/2)
    
    elif sa1%2==0 and sa2%2==1:
        sa2+=1
        count+=1
        count+=int(sa1/2)+int(sa2/2)
    
    elif sa1%2==0 and sa2%2==0:
        # sa1-=1
        # sa2-=1
        # count+=1
        count+=int(sa1/2)+int(sa2/2)

    print(count)

        


    



    
  

    

if __name__ == '__main__':
    main()


Measured memory_bytes: 21376
'''
Doubling

nxt[i][r] = the value of r mod M after 2 ** i squaring
dp[i][r] = the sum of sequence of lenght 2 ** i starting from r

We split sequence A into multiple disjoint parts, 
where the lengths of each parts are the binary decomposition of N.

e.g.
N = 11 = 1 + 2 + 8
A = A[0:1], A[1:3], A[3:11]
Sum of each parts are:
sum(A[0:1]) = dp[0][A[0] % M]
sum(A[1:3]) = dp[1][A[1] % M]
sum(A[3:11]) = dp[3][A[3] % M]
'''

import math

N, X, M = map(int, input().split())

H = math.ceil(math.log2(N)) + 1

nxt = [[0] * M for _ in range(H)]
dp = [[0] * M for _ in range(H)]
nxt[0] = [r ** 2 % M for r in range(M)]
dp[0] = list(range(M))

for i in range(1, H):
    for r in range(M):
        nxt[i][r] = nxt[i - 1][nxt[i - 1][r]]
        dp[i][r] = dp[i - 1][r] + dp[i - 1][nxt[i - 1][r]]

ans = 0
r = X % M
for i in range(H):
    if N & (1 << i):
        ans += dp[i][r]
        r = nxt[i][r]
print(ans)



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

struct UnionFind{
    vector<int> par;
    UnionFind(int N) : par(N){
        for(int i = 0; i < N; i++){
            par[i] = -1;
        }
    }
    int root(int x){
        if(par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry) return;
        else{
            if(par[rx] > par[ry]) swap(rx, ry);
            par[rx] += par[ry];
            par[ry] = rx;
       }
   }
    bool same(int x, int y){
        return root(x) == root(y);
    }
    void check(){
        for(auto x : par){
            cout << x << " ";
        }
        cout << endl;
    }
};

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

    int N, K, L;
    cin >> N >> K >> L;

    UnionFind UF1(N), UF2(N);

    for(int i = 0; i < K; i++){
        int p, q;
        cin >> p >> q;
        UF1.unite(p - 1, q - 1);
    }
    for(int i = 0; i < L; i++){
        int r, s;
        cin >> r >> s;
        UF2.unite(r - 1, s - 1);
    }

    map<pair<int, int>, int> mp;
    for(int i = 0; i < N; i++){
        mp[{UF1.root(i), UF2.root(i)}]++;
    }

    for(int i = 0; i < N; i++){
        if(i > 0) cout << " ";
        cout << mp[{UF1.root(i), UF2.root(i)}];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 13568
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <sstream>
using namespace std;
int main(){
	int i=0,a,b,c,d,e,f,g,ans;
	while(i<5){
		cin>>a;
		if(a==0)break;
		b=1000-a;
		c=b%500;
		d=c%100;
		e=d%50;
		f=e%10;
		g=f%5;
		ans=b/500+c/100+d/50+e/10+f/5+g;
		cout<<ans<<endl;
		ans=0;
		i++;
	}
	return 0;
}

Measured memory_bytes: 3076
s = list(input())
K = int(input())
t = sorted(list(set(s[:]))) 
p = set()
for i in range(len(s)):
    for j in range(1, K+1):
        if i+j <= len(s):
            p.add("".join(s[i:i+j]))

p = list(p)
p = sorted(p)
print(p[K-1])

    

Measured memory_bytes: 40432
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

typedef long long ll;

ll cnt[30];

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

	for(int i=0;i<N;i++)cnt[S[i] - 'a']++;

	ll ans = 1;

	for(int i=0;i<26;i++)
	{
		ans *= (cnt[i]+1);
		ans %= (int)(1e9+7);
	}
	
	cout<<ans-1<<endl;

	return 0;
}

Measured memory_bytes: 1144
import math

def modpow(x, n, mod):
    ans = 1
    while n:
        if n % 2:
            ans = ans * x % mod
        x = x * x % mod
        n >>= 1
    return ans

def modcomb(k, n, mod):
    x = 1
    y = 1
    for i in range(k):
        x = x * (n - i) % mod
        y = y * (k - i) % mod
    y = modpow(y, mod-2, mod)
    return x * y % mod
    


n, a, b = map(int, input().split())
mod = 1000000007

sum2 = modpow(2, n, mod)
ca = modcomb(a, n, mod)
cb = modcomb(b, n, mod)
ans = (sum2 - ca -cb -1) % mod

print(ans)





Measured memory_bytes: 3064
// clang-format

#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;

using lli = long long int;
char f[25][25];

int h, w;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool rn(int x, int y) { return 0 <= x && x < h && y >= 0 && y < w; }
int calc(int sx, int sy, int gx, int gy) {
  lli dp[25][25] = {};
  dp[sx][sy] = 1;
  queue<pair<pair<int, int>, int>> que;
  que.push(make_pair(make_pair(sx, sy), 0));
  while (!que.empty()) {

    int d = que.front().second;
    pair<int, int> s = que.front().first;
    if (s.first == gx && s.second == gy)
      return d;

    que.pop();

    rep(i, 4) {
      int nx = dx[i] + s.first;
      int ny = dy[i] + s.second;
      if (rn(nx, ny) && f[nx][ny] == '.') {
        if (!dp[nx][ny]) {
          dp[nx][ny] = 1;
          que.push(make_pair(make_pair(nx, ny), d + 1));
        }
      }
    }
  }
  return 1e7;
}
int main() {
  cin >> h >> w;
  rep(i, h) rep(j, w) cin >> f[i][j];
  int ans = 0;
  rep(sx, h) rep(sy, w) rep(gx, h) rep(gy, w) {

    if (f[sx][sy] == '.' && f[gx][gy] == '.') {
      int tmp = calc(sx, sy, gx, gy);
      if (tmp != 1e7)
        ans = max(ans, tmp);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
def run(x, n, num_array):
    '''
    '''
    if len(num_array) == 0:
        print(x)
        return
    
    i = 0
    while True:
        if x - i not in num_array:
            print(x - i)
            return
        elif x + i not in num_array:
            print(x + i)
            return
        i += 1
        

if __name__ == '__main__':
    x, n = list(map(int, input().split()))
    num_array = list(map(int, input().split()))
    run(x, n, num_array)

Measured memory_bytes: 9036
n, m = gets.split.map(&:to_i)
ary = m.times.map { gets.split.map(&:to_i) }
years_by_pref = ary.group_by { |pref, year| pref }
year_index_by_pref = years_by_pref.map { |key,val| [key, val.map(&:last).sort.map.with_index.to_h] }.to_h
ary.each do |pref, year|
  puts "%06d%06d" % [pref, year_index_by_pref[pref][year] + 1]
end


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

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define mp make_pair
#define fst first
#define snd second
#define pb push_back

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int, int> pii;

const int INF = 1 << 29;
const double EPS = 1e-10;

double zero(double d) {
    return d < EPS ? 0.0 : d;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    os << '[';
    rep(i, a.size()) os << (i ? " " : "") << a[i];
    return os << ']';
}

// to avoid error on mingw
string toString(int i) {
    stringstream ss;
    ss << i;
    return ss.str();
}

const int M = 1000000007;
// a^k
ll fpow(ll a, ll k, int M) {
    ll res = 1ll;
    ll x = a;
    while (k != 0) {
        if ((k & 1) == 1)
            res = (res * x) % M;
        x = (x * x) % M;
        k >>= 1;
    }
    return res;
}

int main() {
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(8);
    ios_base::sync_with_stdio(false);

    int R, C;
    while(cin >> R >> C, (R||C)) {

        bool sen[R][C];
        memset(sen, 0, sizeof(sen));
        rep(r, R) {
            rep(c, C) {
                int b;
                cin >> b;
                if (b == 1)
                    sen[r][c] = true;
            }
        }

        int res = 0;
        rep(bits, 2 << R) {
            rep(i, R)
                if (((bits >> i) & 0x1) == 1)
                    rep(c, C) sen[i][c] ^= 0x1;

            int tmpRes = 0;
            rep(c, C) {
                int trueNum = 0;
                rep(r, R)
                    if (sen[r][c]) trueNum++;
                tmpRes += max(trueNum, R - trueNum);
            }
            res = max(res, tmpRes);

            rep(i, R)
                if (((bits >> i) & 0x1) == 1)
                    rep(c, C) sen[i][c] ^= 0x1;
        }

        cout << res << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1304
import sys
input = sys.stdin.readline

def connected_components(graph):
  seen = set()
  def component(n):
    nodes = set([n])
    while nodes:
      n = nodes.pop()
      seen.add(n)
      nodes |= graph[n] - seen
      yield n
  for n in graph:
    if n not in seen:
      yield component(n)

n,m,k=map(int,input().split())
friend={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  friend[a-1].add(b-1)
  friend[b-1].add(a-1)
block={i:set() for i in range(n)}
for i in range(k):
  c,d=map(int,input().split())
  block[c-1].add(d-1)
  block[d-1].add(c-1)
c = connected_components(friend)
fnum=[-1 for i in range(n)]
for graph in c:
  s = set(graph)
  for x in s:
    fnum[x] = len(s) - len(s & block[x]) -len(friend[x])- 1
print(' '.join(map(str,fnum)))

Measured memory_bytes: 129636