akhauriyash/Code-Regression huggingface dataset:
import kotlin.math.sqrt

fun main(){
    val n = readLine()!!.toLong()
    //var primeList : List<Map<Int, Int>> = listOf()
    var primeAndIndex : MutableMap<Long, Int> = mutableMapOf()
    var tmp = n
    var i = 2L
    while(tmp != 1L) {
        //println(tmp)
        var indexCount = 0
        while (tmp % i == 0L) {
            tmp /= i
            indexCount++
            //println(tmp)
        }
        //println("end")
        i++
        if(indexCount > 0) primeAndIndex[i] = indexCount
        if(i >= sqrt(n.toDouble())){
            primeAndIndex[n] = 1
            break
        }
        //println(primeAndIndex)
        //println(tmp)
        //println(i)
    }
    //println("whileend")
    var count = 0
    primeAndIndex.forEach{
        var j = 1
        var index = it.value
        while(true){
            index -= j
            if(index < 0) break
            //println(index)
            j++
            count++
        }
    }
    println(count)
}

Measured memory_bytes: 34564
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>
#include <fstream>
#include <functional>
#define endl '\n'
#define ll long long
#define mod 1000000007
#define NCONS 1000000000
//#define NCONS 100001
//#define NCONS 1001
//#define NCONS 101
#define MCONS 2001
#define LIMIT 1000000000
#define TRUE 1
#define FALSE 0
#define toRadian(degree) ((degree) * (M_PI / 180.))
#define toDegree(radian) ((radian) * (180. / M_PI))
using namespace std;
struct Point{int x; int y;};
struct PPoint{Point x; Point y;};
inline ll gcd(ll a, ll b) { if(a < b) swap(a, b); if(b <= 0) return a; return gcd(b, a % b); }

int main(void)
{
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    int A, B; cin >> A >> B;
    if(A >= 13)
        cout << B;
    else if (A <= 5)
        cout << 0;
    else
        cout << B / 2;
    
   
    return 0;
}


Measured memory_bytes: 256
import sys


def main():
    x, y, a, b, c = [int(s) for s in sys.stdin.readline().strip().split()]
    p = [int(s) for s in sys.stdin.readline().strip().split()]
    q = [int(s) for s in sys.stdin.readline().strip().split()]
    r = [int(s) for s in sys.stdin.readline().strip().split()]

    p.sort(reverse=True)
    q.sort(reverse=True)
    r.sort(reverse=True)

    p = p[:x]
    q = q[:y]

    combined = p + q + r
    combined.sort(reverse=True)
    print(sum(combined[:x+y]))

main()


Measured memory_bytes: 101160
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {

		Scanner stdIn = new Scanner(System.in);

		int n = stdIn.nextInt();

		int[] a = new int[n];
		int[] d = new int[(int)(1e5+1)];
		long ans = 0;

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


		int q = stdIn.nextInt();
/*
		int[] b = new int[q];
		int[] c = new int[q];

*/
		for(int i = 0; i < q; i++) {
			int b = stdIn.nextInt();
			int c = stdIn.nextInt();

	//		System.out.println("d[b]:"+d[b]);

			if(d[b] != 0) { //もし要素がひとつでもあれば
				ans += (c - b)*d[b];
				d[c] += d[b];
				d[b] = 0;
				System.out.println(ans);
				continue;
			}
			System.out.println(ans);
		}



	}
}


Measured memory_bytes: 60076
#include<stdio.h>
#include<stdlib.h>

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

int main(void){
    int N,Q;
    scanf("%d%d",&N,&Q);

    char S[N+1];
    scanf("%s",S);

    //A[0]~A[N]に、S[0]~S[i]にACが何個あったかを格納する
    int A[N];
    A[0]=0;
    for(int i=1;i<N;i++){
        if(S[i-1]=='A' && S[i]=='C') A[i]=A[i-1]+1;
        else A[i]=A[i-1];
    }

    int ans[Q];

    for(int i=0;i<Q;i++){
        int l,r;
        scanf("%d%d",&l,&r);

        if(l==1) ans[i]=A[r-1];
        else ans[i]=A[r-1]-A[l-1];
        
    }

    /*
    for(int i=0;i<N;i++){
        printf("%d ",A[i]);
    }
    printf("\n");
    */

    for(int i=0;i<Q;i++){
        printf("%d\n",ans[i]);
    }

    return 0;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define piii pair<int,pii>
#define pll pair<ll,ll>
#define plii pair<ll,pii>
#define vi vector<int>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mx 100001
#define eps 0.00000000001
#define mod 1000000007
#define pi acos(-1)
#define inf 100000000
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main()
{
    fio;
    int n;
    cin>>n;
    bool chk = false;
    loop(i,1,10)
    {
        if(n%i==0)
        {
            if(n/i<=9)
            {
                chk = true;
                break;
            }
        }
    }
    if(chk)
        cout<<"Yes\n";
    else
        cout<<"No\n";
             return 0;
}



Measured memory_bytes: 3600
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = readLine >>= main'
    where
        main' [n, m] = readContents m >>= print . solve n m 

solve :: Int -> Int -> [[Int]] -> Int
solve n m = count . check 0 n
    where
        count (l, h) = max 0 $ h - l

        check x y ([l, r] : xs) = check (max x $ l - 1) (min y r) xs
        check x y _ = (x, y)


readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

Measured memory_bytes: 37244
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n) for(int i=1;i<=n;i++)
const ll MOD = 1000000007;

struct edge{
    int to,weight;
    edge(int to,int weight):to(to),weight(weight){}
};
using Graph = vector<vector<int>> ;
using GraphEdge = vector<vector<int>> ;

long long modinv(long long a, long long m=MOD) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
    /*MODの割り算の際に
    a/＝b;
    を
    a *= modinv(b,MOD);
    とする。
        */
}
int main(){
    int N;cin >> N;
    int L[11];
    int ma = 0;
    int sum = 0;
    rep(i,N){
        cin >> L[i];
        sum += L[i];
        ma = max(L[i],ma);
    }
    sum -= ma;

    if(ma < sum)cout << "Yes" << endl;
    else cout << "No" << endl;


    return 0;
}

Measured memory_bytes: 3584
#include <stdio.h>

#define Max 100

#define A 0
#define B 1
#define C 2

#define INF 1<<21

int ori[Max][Max];
int n;

int Prim(void);

int main()
{
  int i,j,k;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&k);
      if(k==-1) ori[i][j]=INF;
      else ori[i][j]=k;
    }
  }

  printf("%d\n",Prim());
  
  return 0;
}

int Prim()
{
  int i,j,k,x,min,count=0;
  int omomi[Max];
  int parent[Max];
  int judgement[Max];

  for(i=0;i<n;i++){
    omomi[i]=INF;
    parent[i]=-1;
    judgement[i]=A;
  }

  omomi[0]=0;

  for(x=0;;x++){
    min=INF;
    j=-1;

    for(i=0;i<n;i++){
      if(judgement[i]!=C && min>omomi[i]){
	j=i;
	min=omomi[i];
      }
    }

    if(j==-1) break;
    judgement[j]=C;

    for(k=0;k<n;k++){
      if(judgement[k]!=C && ori[j][k]!=INF){
	if(omomi[k]>ori[j][k]){
	  omomi[k]=ori[j][k];
	  parent[k]=j;
	  judgement[k]=B;
	}
      }
    }
  }

  for(i=0;i<n;i++){
    if(parent[i]!=-1) count+=ori[i][parent[i]];
  }

  return count;
}
  
	
    
  
  



Measured memory_bytes: 2052
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define loop(i,a,b) for(ll i = (ll)a ; i < (ll)b ; i++)
#define rtloop(i,a,b) for(ll i = (ll)a; i >= (ll)b; i--)
#define pb push_back
#define mp make_pair
#define yo(a) cerr <<#a <<" = " << a <<"\n";
#define COOL ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);



void solve(){
    ll a, b, c, d;
    cin >> a >> b >> c >>d;
    while(1){
        c -= b;
        if(c <= 0){
            cout <<"Yes\n";
            break;
        }
        a -= d;
        if(a <= 0){
            cout <<"No\n";
            break;
        }
    }



    
}



int main() {
    // #ifndef ONLINE_JUDGE
    //     freopen("inn.txt", "r", stdin);
    //     freopen("op.txt", "w", stdout);
    // #endif
    COOL
    // ll t;
    // cin >> t;
    // while(t--)
        solve();
    
        


    return 0;
}





Measured memory_bytes: 3552
// 2012/07/13 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int s1, s2;
		cin >> s1 >> s2;

		if(s1==0&&s2==0)
			break;

		char n_max = 'A';
		int s_max = s1+s2;

		cin >> s1 >> s2;
		if(s1+s2>s_max){
			n_max = 'B';
			s_max = s1+s2;
		}

		cin >> s1 >> s2;
		if(s1+s2>s_max){
			n_max = 'C';
			s_max = s1+s2;
		}

		cin >> s1 >> s2;
		if(s1+s2>s_max){
			n_max = 'D';
			s_max = s1+s2;
		}

		cin >> s1 >> s2;
		if(s1+s2>s_max){
			n_max = 'E';
			s_max = s1+s2;
		}

		cout << n_max << ' ' << s_max << endl;
	}

	return 0;
}

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

using namespace std;

#define Rep(i,a,b)  for (int i=(a);i<(b);i++)
#define rep(i,n)    for (int i=0;i<(n);i++)
#define all(x)      (x).begin(), (x).end()

#define ll long long

int main()
{
	string s;
	ll k;
	cin >> s >> k;
	for (int i = 0; i < min((ll)s.size(), k); i++) {
		if (s[i] >= '2') {
			cout << s[i] << endl;
			return 0;
		}
	}
	cout << '1' << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
const long long MAXN = 1e6+5;
multiset<pair<long long,long long>> s1;
long long arr[MAXN];
int main(){
    long long n,m;
    cin>>n>>m;
    long long total = 0;
    for(long long i=1;i<=n;i++){
        cin>>arr[i];
        s1.insert(make_pair(arr[i],1));
        
    }
    for(long long i=1;i<=m;i++){
        long long x,y;
        cin>>x>>y;
        s1.insert(make_pair(y,x));
        
    }
    
    for(long long i=1;i<=n;i++){
        if(s1.empty()){
            break;
        }
        auto it = s1.end();
        it--;
        auto hold = *it;
        
        s1.erase(it);
        
        total+=(hold.first);
        hold.second--;

        if(hold.second>0){
            s1.insert(hold);
        }
      
        
    }
    cout<<total<<endl;
}

Measured memory_bytes: 13568
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
int main(){
	int a;
	int yama[10];
	for(a=0;a<10;a++){
		cin >> yama[a];
	}
	sort(yama,yama + 10,greater<int>());
	for(a=0;a<3;a++){
		cout << yama[a] << endl;
	}
	return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <random>
#include <chrono>
#include <algorithm>
#define rep(i, x) for(ll i = 0; i < x; i++)
using namespace std;
typedef long long ll;
const ll MOD = (ll)1e9+7;
const ll N = 5e5+5, inf = 1e9+5000;
ll add(ll x, ll y) { x += y; if (x >= MOD) return x - MOD; return x; }
ll sub(ll x, ll y) { x -= y; if (x < 0) return x + MOD; return x; }
ll mult(ll x, ll y) { return (x * y) % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  ll x, k, d; cin >> x >> k >> d;

  x = abs(x);

  if (k < x/d) {
    cout << x-k*d << endl;
  } else {
    if ((x/d) % 2 == k % 2) {
      cout << x%d << endl;
    } else {
      cout << d-x%d << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define INF 2147483647
#define INFF 9223372036854775807
#define ll long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)
#define ALL(N) (N.begin(),N.end())
#define de cout << "debug" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


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

    string S;
    cin >> S;
    ll AC = 0;
    ll ans = 0;
    ll i = 0;

    if(S.size() == 1){
        cout << 0 << endl;
        return 0;
    }

    while(i+1 < S.size()){
        if(S[i] == 'A'){
            AC++;
        }
        else if(S[i] == 'B' && S[i+1] == 'C'){
            ans += AC;
            i++;
        }
        else if(AC > 0 && S[i] != 'A'){
            AC = 0;
        }
        i++;
    }

    cout << ans << endl;
}


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

int main(void){
    int h, w;
    cin >> h >> w;
    
    int s[52][52] = {{0}};
    char input;
    int i, j;
    for(i = 1; i <= h; i++){
        for(j = 1; j <= w; j++){
            cin >> input;
            if(input == '#'){
                s[i][j]++;
            }
        }
    }
    
    for(i = 1; i <= h; i++){
        for(j = 1; j <= w; j++){
            if(s[i][j] == 1 && s[i][j - 1] + s[i][j + 1] + s[i - 1][j] + s[i + 1][j] == 0){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    
    cout << "Yes" << endl;
    
    return 0;
}


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

int n,k;
char c[50];

void solve(){
    cin>>n>>k;
    rep(i,n){
        cin>>c[i];
        if(i==k-1){
            c[i]=c[i]+('a'-'A');
        }
        cout<<c[i];
    }
}

int main(){
    solve();
    cout<<endl;
    return 0;
}

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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 210
const int MOD = 1000000007;

int c[10][10], m[maxn][maxn],dist[11];

vector<pair<int, int>> g1[maxn];

void dijkstra(int src) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> st;
    dist[src] = 0;
    st.push({0, src});
    while (!st.empty()) {
        auto top = st.top();
        st.pop();

        int node_dist = top.first;
        int node = top.second;

        if (node_dist != dist[node])continue;

        for (int i = 0; i <= 9; i++) {
            auto dest = i;
            if (dest == node)continue;
            if (dist[dest] > node_dist + c[dest][node]) {
                dist[dest] = node_dist + c[dest][node];
                st.push({dist[dest], dest});
            }
        }
    }
}


void solve() {
    int h, w;
    cin >> h >> w;

    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            cin >> c[i][j];
    memset(dist, 63, sizeof dist);
    dijkstra(1);
    int ans = 0;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            cin >> m[i][j];
            if (m[i][j] == -1)continue;
            ans += dist[m[i][j]];
        }
    cout << ans << endl;
}

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

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int k,s,cnt=0;
	cin>>k>>s;
	for(int i=0;i<k+1;i++){
		for(int j=0;j<k+1;j++){
				if(s-i-j+i+j==s && s-i-j>=0 && (s-i-j)<=k && i<=k && j<=k){
					cnt++;
			}
		}
	}
	cout<<cnt<<endl;
}


Measured memory_bytes: 256
/*#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
typedef struct edgenode {
	int adjvex;
	int w;
	struct edgenode *next;
}edgenode;
typedef struct vertexnode {
	int vertex;
	edgenode *first_v;
}vertexnode;
typedef struct graph {
	int n, e;
	vertexnode adjlist[maxn];
}graph;
graph *g;
void greatedg(int a,int n, int e) {
	edgenode *s;
	int w, b;
	cin >> b >> w;
	s = (edgenode *)malloc(sizeof(edgenode));
	s->adjvex == b;
	s->next = g->adjlist[a].first_v;
	g->adjlist[a].first_v = s;
}
int main()
{
	int n, e;
	cin >> n;
	g->n = n;
	for (int i = 0;i < n;i++){
		int a, k;
		cin >> n >> k;
		for (int j = 0;j < k;j++) {
			int b, w;
			cin >> b >> w;
			greatedg(a, b, w);
		}
	}

	return 0;
}*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 111;
typedef long long ll;
ll mp[maxn][maxn];
const ll INF = 1LL << 32;
int main()
{
	int v, e;
	int flag = 0;
	cin >> v >> e;
	for (int i = 0;i < v;i++)
	{
		for (int j = 0;j < v;j++)
		{
			if (i == j)mp[i][j] = 0;
			else mp[i][j] = INF;
		}
	}
	int a, b, w;
	for (int i = 0;i < e;i++)
	{
		cin >> a >> b>>w;
		if (mp[a][b] > w)
			mp[a][b] = w;
	}
	for (int k = 0;k < v;k++)
	{
		for (int i = 0;i < v;i++)
		{
			if (mp[i][k] == INF)
				continue;
			for (int j = 0;j < v;j++)
			{
				if (mp[k][j] == INF)
					continue;
				if (mp[i][k] + mp[k][j] < mp[i][j])
					mp[i][j] = mp[i][k] + mp[k][j];
			}
		}
	}
	for (int i = 0;i < v;i++)
	{
		if (mp[i][i] < 0)
		{
			flag = 1;break;
		}
	}
	if (flag == 1)
		cout << "NEGATIVE CYCLE" << endl;
	else
	{
		for (int i = 0;i < v;i++)
		{
			for (int j = 0;j < v;j++)
			{
				if (j)
					cout << " ";
				if (mp[i][j] == INF)
					cout << "INF";
				else
					cout << mp[i][j];
			}
		cout << endl;
		}
	}
	return 0;
}


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

int main(){
    int N;
    string S;
    cin >> N;
    cin >> S;
    string al = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    for(int i=0; i<S.length(); i++){
        int w = al.find_first_of(S[i]);
        cout << al[(w + N) % 26];
    }

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{ int a,b,c,i,t,j,d,e;
	while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
	{
		if(b<=c||a>=d)
		{
			e=0;
		}
		else
		{
			i=a<c?a:c;
			j=a+c-i;
			t=d<b?d:b;
			e=t-j;
		}
		printf("%d\n",e);
	}
}

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

using namespace std;

int main(){
    string o,e;
    cin >> o >> e ;
    string answer;
    for (int i = 0; i < e.size(); i++) {
        answer.push_back(o[i]);
        answer.push_back(e[i]);
    }
    if (o.size() > e.size()) {
        answer.push_back(o.back());
    }
    cout << answer << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
	ll N, n, digSum;
	string result;
	cin >> N;
	n = N;
	while (n > 0) {
		digSum += n % 10;
		n /= 10;
	}
	if (N % digSum == 0) {
		result = "Yes";
	}
	else {
		result = "No";
	}

	cout << result << endl;
	return 0;
}

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

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

    int a[n];

    bool has_odd = false;
    for (size_t i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] % 2 == 1)
        {
            has_odd = true;
        }
    }

    if (has_odd)
    {
        cout << 0 << endl;
        return 0;
    }

    int ans = 0;
    while (true)
    {
        for (size_t i = 0; i < n; i++)
        {
            if (a[i] % 2 == 1)
            {
                cout << ans << endl;
                return 0;
            }
        }
        for (size_t i = 0; i < n; i++)
        {
            a[i] /= 2;
        }

        ans += 1;
    }
}

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

int main() {
    int A,B,C,K;
    cin >> A >> B >> C >> K;

    if (A == K || A + B == K) {
        cout << A << endl;
    }
    else if (A + B + C == K) {
        cout << A - C << endl;
    }
    else if (A > K) {
        cout << K << endl;
    }
    else if (A + B > K) {
        cout << A << endl;
    }
    else if (A + B + C > K) {
        C += K - (A + B + C);
        cout << A - C << endl;
    }

    return 0;
}

Measured memory_bytes: 3624
n=int(input())
k=len(str(n))
f=int(str(n)[0])
l=int(str(n)[-1])
if k==1:
    print(n)
    exit()
m=(n%(10**(k-1))-l)//10
ans=0
for i in range(1,10):
    if i<f:
        ans+=((10**(k-1)-1)//9+1)**2
    elif i==f:
        if i<=l:
            ans+=((10**(k-2)-1)//9+m+2)**2
        else:
            ans+=((10**(k-2)-1)//9+m+1)**2
    else:
        ans+=((10**(k-2)-1)//9+1)**2
for i in range(1,10):
    for j in range(1,10):
        if i!=j:    
            if i<f:
                a=(10**(k-1)-1)//9
            elif i==f:
                if j<=l:
                    a=(10**(k-2)-1)//9+m+1
                else:
                    a=(10**(k-2)-1)//9+m
            else:
                a=(10**(k-2)-1)//9
            if j<f:
                b=(10**(k-1)-1)//9
            elif j==f:
                if i<=l:
                    b=(10**(k-2)-1)//9+m+1
                else:
                    b=(10**(k-2)-1)//9+m
            else:
                b=(10**(k-2)-1)//9
            ans+=a*b
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

#define maxN 500011

int n, i, cnt;
char s[maxN], rev[maxN];
int pr[maxN];

bool le[maxN], ri[maxN];

void solve(char *s, bool *ans) {
    int i, u;

    pr[1] = u = 0;
    for (i = 2; i <= n; i++) {
        while (u != 0 && s[i] != s[u + 1]) u = pr[u];
        if (s[i] == s[u + 1]) u++;
        pr[i] = u;

        ans[i] = (u != 0 && i % (i - u) == 0);
    }
}

int main()
{
  //  freopen("test.in", "r", stdin);

    scanf("%s", s + 1);
    n = strlen(s + 1);

    for (i = 1; i <= n; i++)
        rev[n - i + 1] = s[i];

    solve(s, le);
    solve(rev, ri);

    if (le[n] == false) {
        printf("1\n1");
        return 0;
    }

    bool same = true;
    for (i = 2; i <= n; i++)
        if (s[i] != s[1])
            same = false;

    if (same) {
        printf("%d\n%d", n, 1);
        return 0;
    }

    for (i = 1; i < n; i++) {
        if (!le[i] && !ri[n - (i + 1) + 1])
            cnt++;
    }

    printf("2\n%d", cnt);

    return 0;
}


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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << std::setprecision(10);

  int n; std::cin >> n;
  set<char> s;
  rep(i, n) {
    char c; std::cin >> c;
    s.insert(c);
  }
  std::cout << (s.size() == 3 ? "Three" : "Four") << "\n";
}


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

using namespace std;

int main(){
  int N; cin >> N; vector<int> A(N); for(int i = 0; i < N; i++){ cin >> A[i]; A[i]--;}
  long long cnt = 0;
  for(int j = 0; j < N; j++){
    if(A[A[j]] == j){ cnt++;}}
  
  cout << cnt/2 << endl; return 0;}

Measured memory_bytes: 640
#include "bits/stdc++.h"
using namespace std;

int main() {
	string S;
	map<char, int> C;
	int K;
	C['a'] = 0;
	for (int i = 1; i < 26; i++) {
		char c = 123 - i;
		C[c] = i;
	}
	cin >> S >> K;
	for (int i = 0; i < S.size(); i++) {
		if (C[S[i]] <= K) {
			K -= C[S[i]];
			S[i] = 'a';
		}
	}
	S[S.size() - 1] = (S[S.size() - 1] + K + 7) % 26 + 97;
	cout << S;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define all(x) (x).begin(),(x).end()
using ll = long long;
using namespace std;

int main() {
  int n;
  cin>>n;
  int a[n];
  vector<vector<int>> x(n),y(n);
   rep(i,n){
     cin>>a[i];
     rep(j,a[i]){
          int q,w;
          cin>>q>>w;
       q--;
          x[i].push_back(q);
          y[i].push_back(w);
       }
     
     
   }
 /////////////////////////////////
  vector<bool> hon(n);
  int ans=0;
  for(int bit=0;bit<(1<<n);bit++){
    bool mujun=false;
    
    hon.assign(n,false);
    rep(i,n){
    		 if(bit&(1<<i)){
       			hon[i]=true;
     		 }
    }
    //if(bit==3) cout<<45<<endl;
    rep(i,n){
     // cout<<34<<endl;
      	if(!hon[i]){
      	  //continue;
      	}
      	else{//i人目がif正直者
        	rep(j,a[i]){ //その人の情報を出す(aiこ）
          				
          				
           						 if(hon[x[i][j]]==1&& y[i][j]==1){//矛盾しない
           	   
           						 }
              					else if(hon[x[i][j]]==0 && y[i][j]==0){
                                  
                                }
            					else{  
                                  //if(bit==3) cout<<i<<j<<endl;//矛盾
             					 mujun=true;
                                  //cout<<32<<endl;
            					//  break;
                                  
            					}
          			   
        	}//rep
     		   
        }//else
      //if(mujun) break;
    }
    if(mujun){
      
    }//continue;
    else{
      int v=0;
      rep(i,n){
       // cout<<hon[i]<<endl;
        if(hon[i]) v++;
      }
      
      ans=max(ans,v);
      //cout<<bit<<endl;
    }
  }
  
  cout<<ans<<endl;
  
}



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

typedef struct zahyo {
	int X;
	int Y;
}zahyo;

int main() {
	zahyo point[2];
	int differenceX, differenceY;
	
	cin >> point[0].X >> point[0].Y;//2 3
	cin >> point[1].X >> point[1].Y;//6 6

	differenceX = (point[1].X - point[0].X);//4
	differenceY = (point[1].Y - point[0].Y);//3
	
	cout << point[1].X - differenceY << " " << point[1].Y + differenceX << " ";
	cout << point[0].X - differenceY << " " << point[0].Y + differenceX << endl;

	return 0;

}
//*/

Measured memory_bytes: 256
/***** ?????¬???????????¬?????? *****/

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for(int i=a; i<n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 999999999

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long int ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int const MOD = 1000000007;

int main() {
    int a[4], b[4];
    while(cin >> a[0] >> a[1] >> a[2] >> a[3] >> b[0] >> b[1] >> b[2] >> b[3]) {
        set<int>s1, s2;
        rep(i,0,4) s1.insert(a[i]);
        rep(i,0,4) s2.insert(b[i]);

        int hit = 0, blow = 0;
        rep(i,0,4) {
            if(a[i] == b[i]) hit++;
            else if(s1.count(b[i]) != 0) blow++;
        }

        printf("%d %d\n",hit,blow);
    }
    return 0;
}

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

#define FAST_IO                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cerr.tie(NULL);

#define dbg(x) cerr << #x << " = " << x << ",  ";
#define vw(v)                        \
    cerr << endl                     \
         << endl                     \
         << (#v) << " is: " << endl; \
    for (int B : (v))                \
    {                                \
        cerr << B << " ";            \
    }                                \
    cerr << endl
#define check(x) cerr << "here " << (x) << "?" << endl

#define rep(i, a, b) for (long long i = (a); i < (b); i++)
#define per(i, a) for (long long i = (a - 1); i >= 0; i--)

#define all(x) (x).begin(), (x).end()
#define rv(x) (x).rbegin(), (x).rend()
#define pb push_back

typedef long long ll;
ll const INF = 2147483647, R_INF = 9223372036854775807, MOD = 1e9 + 7;

const int N = 1e3 + 2;
bool grid[N][N];
int DP[N][N];
int main()
{
    FAST_IO
    int n , m;
    cin >> n >> m;
    rep(i, 1, n + 1)
    {
        rep(j, 1, m + 1)
        {
            char c;
            cin >> c;
            grid[i][j] = c == '#';
        }
    }
    if (grid[1][1])
        return cout << 0, 0;
        
    DP[1][1] = 1;
    rep(i, 1, n + 1)
        rep(j, 1, m + 1) if (!grid[i][j])
            DP[i][j] += (DP[i - 1][j] + DP[i][j - 1]) % MOD;

    cout << DP[n][m];
}

Measured memory_bytes: 5120
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>

#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define MEM(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int gcd(int a, int b) {
	if (a < b)swap(a, b);
	int k = a % b;
	if (k == 1)return 1;
	if (k == 0)return b;
	int ans = gcd(b, k);
	return ans;
}
int a[114514];
int dp[55][10010];
int main() {
	IOS;
	ll n;
	cin >> n;
	int sum = 0;
	for (int i = 16; i >= 0; i--) {
		ll k = (ll)pow(10, i);
		if (k > n)continue;
		ll x = n / k;
		ll y = n % k;
		if (y == k - 1)sum = x + 9 * i;
		else sum = 9 * i + x - 1;
		break;
	}
	cout << sum << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

using namespace std;
typedef long long ll ;

string cad;
int ans = 0, cont = 0;
int main(){
	fastio;
	cin>>cad;
	
	for(int i=0; i<cad.size();i++){
		char b=cad[i];
		if(b=='A' || b=='C' || b=='G' || b=='T') cont++;
		else {
			ans = max(cont,ans);
			cont = 0;
		}
	}
	cout<<max(ans,cont)<<"\n";	
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
int n;
long long h[200020];
int k;
long long ans;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>h[i];
	sort(h+1,h+n+1);
	for(int i=1;i<=n-k;i++)
	{
		ans+=h[i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
package main

import "fmt"

func selectionSort(a []int, n int) ([]int, int) {
	var cnt int
	for i := 0; i < n; i++ {
		minj := i
		for j := i; j < n; j++ {
			if a[j] < a[minj] {
				minj = j
			}
		}
		a[i], a[minj] = a[minj], a[i]
		if i != minj {
			cnt++
		}
	}
	return a, cnt
}

func main() {
	var n, cnt int
	fmt.Scan(&n)
	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}
	a, cnt = selectionSort(a, len(a))
	for i, v := range a {
		if i == len(a)-1 {
			fmt.Printf("%d\n", v)
		} else {
			fmt.Printf("%d ", v)
		}
	}
	fmt.Println(cnt)
}


Measured memory_bytes: 1120
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n, m;
  cin >> n >> m;
  int first = min(n, m);
  int second = max(n, m);
  rep(i, second) cout << first;
  cout << endl;
}

Measured memory_bytes: 256
/***
 ** " Any fool can write code that a computer can understand. Good programmers write code that humans can understand "
 **     -- Martin Fowler
***/

/**
  *  Author: dhruv_gheewala
  *  Problem: __________
  *  Date:   02.08.2020
  *  Time:   17:42:57
**/

#if __has_include("debug.h")
    #include "debug.h"
#else
    #include<bits/stdc++.h>
    using namespace std;
    
    #define fundri 108
    #define debug(...) 1729
#endif

#define int int64_t
typedef pair<int, int> pii;
typedef vector<int> vi;

const bool testcases = false;
#define ff first
#define ss second
#define endl '\n'
#define all(s) s.begin(), s.end()

// if vector isn't soted then it will remove consecutive same elements
#define make_unique(vec) vec.erase(unique(all(vec)), vec.end())
#define test int TC = 1;if(testcases)cin >> TC;for(int tc = 1 ; tc <= TC ; tc++)solve(), fundri
#define sort_by(cont,expr) sort(all(cont),[&](const auto &lhs,const auto &rhs){return expr;})

int seed; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l = 0, int r = INT_MAX) {return uniform_int_distribution<int>(l, r)(rng);}

inline bool in_range(int a, int l, int r) {return (a >= l && a <= r);}
template<typename H, typename ...T>void inp(H &head) {cin >> head;}
template<typename H, typename ...T>void inp(H &head, T &...tail) {cin >> head;inp(tail...);}
template<typename T>bool isPrime(T n) {for(T i = 2; i * i <= n; i++)if(n % i == 0)return false; return n >= 2;}
template<typename T>inline istream &operator >>(istream &in, vector<T> &a) {for(T &x : a)in >> x; return in;}
template<typename T, typename U>inline istream &operator >>(istream &in, pair<T, U> &a) {in >> a.ff >> a.ss; return in;}

void solve();
void fast_io();

int32_t main(int32_t argc, char **argv)
{
    fast_io();
    test;
    return 0;
}

int MOD;
int add(int a, int b) {return ((a % MOD) + (b % MOD)) % MOD;}
int mul(int a, int b) {return ((a % MOD) * (b % MOD)) % MOD;}

void solve()
{
    int k;
    cin >> k;   
    MOD = k;

    int cnt = 1;
    int num = 7 % k;
    if(num == 0) {
        cout << 1 << endl;
        return;
    }
    
    set<int> s;
    while(num != 0) {
        s.insert(num);
        num = add(mul(num, 10), 7);
        if(s.find(num) != s.end()) {
            cout << -1 << endl;
            return;
        }
        cnt++;
    }
    cout << cnt << endl;
}

void fast_io()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef DHRUV_GHEEWALA
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif
}

Measured memory_bytes: 50428
n = int(input())
A = list(map(int, input().split()))

filled = [0]*(n+1)
ans = []
for i in range(n-1, -1, -1):
  if sum(filled[::i+1][1:]) % 2 != A[i]:
    filled[i+1] = 1
    ans.append(i+1)
print(len(ans))
print(' '.join(map(str, ans)))

Measured memory_bytes: 20788
///////////////////////////////////////////////////
/* __                                       __   */
/*|  |--.-----.---.-.----.----.-----.-----.|  |_ */
/*|  _  |  -__|  _  |  __|  __|  -__|  _  ||   _|*/
/*|_____|_____|___._|____|____|_____|   __||____|*/
/*                                  |__|         */
///////////////////////////////////////////////////
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>
typedef long long lint; using namespace std;
#define rep(counter, limit) for (int counter = 0; counter < limit; counter++)
#define INF 1000000000000
#define MOD 10000007
int gcd(int a, int b) { if (a % b == 0) { return(b); } else { return(gcd(b, a % b)); } }
int lcm(int a, int b) { return a * b / gcd(a, b); }
bool primenum(int a) { if (a == 1) { return false; }if (a == 2) { return true; }if (a % 2 == 0) { return false; }for (int i = 3; i < sqrt(a) + 1; i += 2) { if (a != i) { if (a % i == 0) { return false; } } }return true; }
struct setupios{setupios(){cin.tie(0);ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}setupios;
int main() {

  lint x;
  cin>>x;
  lint num=100;
  for(lint i=1;;i++){
    num*=1.01;
    if(num >= x){
      cout<<i<<endl;
      return 0;
    }
  }

}


Measured memory_bytes: 3668
#include <iostream>

using namespace std;

#define INF (1 << 30)

int main() {
  int N;
  long min_a = INF;
  long max_a = INF * (-1l);

  cin >> N;

  for (int i = 0; i < N; ++i) {
    long a;
    cin >> a;
    if (a < min_a) {
      min_a = a;
    }
    if (a > max_a) {
      max_a = a;
    }
  }

  cout << max_a - min_a << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
using namespace std;

int main(void) {
	int r, D, x[11];
	cin >> r >> D >> x[0];
	for (int i = 1; i <= 10; i++) {
		x[i] = x[i - 1] * r - D;
		cout << x[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import fractions

n,x=list(map(int,input().split()))
X=list(map(int,input().split()))
X.append(x)
X=sorted(X)
Y=[X[i+1]-X[i] for i in range(n)]

if n==1:
  print(max(X)-min(X))
  
else:
  gcd=fractions.gcd(Y[0],Y[1])
  for i in range(2,n):
    gcd=fractions.gcd(gcd,Y[i])
  print(gcd)

Measured memory_bytes: 16240
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()
#define clr(a,v) memset((a),(v),sizeof(a))

using P = std::pair<int, int>;
using State = std::pair<int, P>;

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

int R;
int W[2], H[2], X[2], Y[2];
int L[2][510][510];
bool used[510][510];
std::vector<int> lev[2];

void dijkstra( int k )
{
  clr( used, false );
  lev[k].clear();

  std::priority_queue<State, std::vector<State>, std::greater<State> > pque;
  pque.push( State( 1, P( X[k], Y[k] ) ) );

  int ma = 0;
  lev[k].push_back( 0 );

  while( !pque.empty() )
  {
    State st = pque.top(); pque.pop();
    int dist = st.first;
    P p = st.second;

    if( used[p.first][p.second] )
      continue;

    used[p.first][p.second] = true;

    ma = std::max( ma, dist );
    lev[k].emplace_back( ma );

    rep( i, 4 )
    {
      int nx = p.first+dx[i], ny = p.second+dy[i];

      if( nx >= 0 && nx < W[k] && ny >= 0 && ny < H[k] && !used[nx][ny] )
        pque.push( State( L[k][nx][ny], P( nx, ny ) ) );
    }
  }

  return;
}

int main()
{
  while( scanf( "%d", &R ), R )
  {
    rep( i, 2 )
    {
      scanf( "%d%d%d%d", W+i, H+i, X+i, Y+i );
      --X[i]; --Y[i];

      rep( j, H[i] ) rep( k, W[i] )
        scanf( "%d", &L[i][k][j] );
    }

    dijkstra( 0 );
    dijkstra( 1 );

    int ans = 1<<30;

    rep( i, R+1 )
    {
      if( lev[0].size() <= i )
        continue;
      if( lev[1].size() <= R-i )
        continue;

      ans = std::min( ans, lev[0][i]+lev[1][R-i] );
    }  

    printf( "%d\n", ans );
  }
  
  return 0;
}


Measured memory_bytes: 8372
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s;
  cin >> s;
  int N = s.size();
  int a,b;
  
  for (int i = 0; i < N; i++) {
    if (s.at(i) == 'A') {
      a = i;
      break;
    }
  }
  
  for (int i = N; N > 0; i--) {
    if (s.at(i-1) == 'Z') {
      b = i-1;
      break;
    }
  }
  
  cout << b - a + 1 << endl;
}

Measured memory_bytes: 640
import fractions
import sys

N,K = map(int,input().split())

A = list(map(int,input().split()))

A.sort()

if len(A) == 1:
    if A[0] == K:
        print ("POSSIBLE")
    else:
        print ("IMPOSSIBLE")
    sys.exit()

for i in range(N-1):

    if i == 0:
        now = fractions.gcd(A[0],A[1])

    else:
        now = fractions.gcd(now,A[i+1])

if K % now == 0 and K <= A[-1]:
    print ("POSSIBLE")
else:
    print ("IMPOSSIBLE")


Measured memory_bytes: 16144
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,k, = map(int,readline().split())
*p, = map(int,readline().split())
*c, = map(int,readline().split())

for i in range(n): p[i] -= 1

ans = [-1<<31]*n
pos = list(range(n))
val = [0]*n
for i in range(min(k,n)):
#for i in range(48):
    for j in range(n):
        pos[j] = p[pos[j]]
        val[j] += c[pos[j]]
        if ans[j] < val[j]: ans[j] = val[j]

#print(pos,val)
#print(ans,max(ans))
    #print(pos,"p")
    #print(val,"v")

pos = list(range(n))
val = [0]*n

pp = p[:]
vv = [c[p[j]] for j in range(n)]

k -= n

if k < 0:
    print(max(ans))
    #print(ans,"short")
    exit()


#print(pp,vv,0)
for i in range(31):
    vvv = vv[:]
    ppp = pp[:]
    if k&1:
        for j in range(n):
            val[j] += vvv[pos[j]]
            pos[j] = pp[pos[j]]
        #print(pos,val,i)
    
    #print(pp)
    for j in range(n):
        vvv[j] += vv[pp[j]]
    for j in range(n):
        ppp[j] = pp[pp[j]]
    vv = vvv
    pp = ppp
    #print(pp,vv,i+1)
    k >>= 1

#print(pos,val,"pv-orig")

for i in range(n):
    for j in range(n):
        pos[j] = p[pos[j]]
        val[j] += c[pos[j]]
        if ans[j] < val[j]: ans[j] = val[j]

#print(ans)
print(max(ans))










Measured memory_bytes: 69384
import itertools
import math

X, Y = map(int,input().split())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if (X+Y)%3 != 0:
  Answer = 0
else:
  m = int(X-(X+Y)/3)
  n = int(Y-(X+Y)/3)
  Answer = cmb(m+n,n,mod)
  
print(Answer)

Measured memory_bytes: 121872
from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
c23 = c2 + c3
dp = [[[0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])


Measured memory_bytes: 254984
#include <bits/stdc++.h>
#define N 10010
using namespace std;
int main(){
	vector<int> a;
	int us[10]={0,2,5,5,4,5,6,3,7,6},dp[N];
	int n,m,i,j,x;
	cin>>n>>m;
	for(i=0;i<m;i++)
	{
		cin>>x;
		a.push_back(x);
	}
	memset(dp,-1,sizeof(dp));
	dp[0]=0;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<m;j++)
		{
			if(i<us[a[j]])
			{
				continue;
			}
			dp[i]=max(dp[i],dp[i-us[a[j]]]+1);
		}
	}
	sort(a.begin(),a.end());
	reverse(a.begin(),a.end());
	i=0;
	while(n!=0)
	{
		if(n>=us[a[i]]&&dp[n]==dp[n-us[a[i]]]+1)
		{
			cout<<a[i];
			n-=us[a[i]];
		}
		else
		{
			i++;
		}
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll long long int
#define MOD 1000000007
#define oo 1000000000000000000
#define forr(i,n) for(ll i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0) ; cout.tie(0);
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define pb push_back
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
 
using namespace __gnu_pbds; 
using namespace std;

ll valueOfIndex(ordered_set&s , ll i){ return *(s.find_by_order(i)); }
ll indexOfValue(ordered_set&s , ll x){ return s.order_of_key(x); }
ll add(ll a, ll b,ll p=MOD) { a%=p; b%=p; return (a+b + p)%p;}
ll mul(ll a, ll b,ll p=MOD) { a%=p; b%=p; return (a*b + p)%p;} // __int128
ll power(ll x,ll n,ll p=MOD){ if(x==0) return 0; if(n==0 || x==1) return 1LL;
    ll r = (power(x,n/2,p))%p; if(n&1) return mul(mul(r,r,p) , x,p); else return mul(r,r,p);
}
ll inv(ll x){return power(x,MOD-2);}



void __sol(){
    int n,m; cin >> n >> m;
    int ans[n+10];
    bool visit[n+10];
    vector<vector<int>> g(n+10);
    forr(i,m){
        int u,v; cin >> u >> v;
        g[v].eb(u); g[u].eb(v);
    }
    visit[1]=0,ans[1]=-1;
    for(int i=2;i<=n;i++) ans[i]=-1,visit[i]=0;
    queue<int> q; q.push(1);
    visit[1]=1;
    while(!q.empty()){
        int node = q.front(); q.pop();
            for(auto &i: g[node]){
                if(!visit[i]){
                    ans[i] = node;
                    visit[i]=true;
                    q.push(i);
                }
            }
    }
    for(int i=2;i<=n;i++){
        if(!visit[i]){
            cout << "No";
            return;
        }
    }
    cout << "Yes\n";
    for(int i=2;i<=n;i++) cout << ans[i] << "\n";


}


int main(){
    fastio
    ll tc=1; //cin >> tc;
    while(tc--) __sol();
    return 0;
}

Measured memory_bytes: 10368
from numpy import*;N,K=map(int,input().split());m,L,o=zeros((3*K,3*K)),2*K,0
for _ in[0]*N:x,y,c=input().split();t=c=='W';m[int(x)%L,int(y)%L]+=2*t-1;o+=t
for _ in"00":m[L:]=m[:K];m=cumsum(m,0);m[:L]-=m[K:];m=m.T
m=m[:L,:L];print(o-int((m+roll(roll(m,K,0),K,1)).min()))

Measured memory_bytes: 153080
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using bint = boost::multiprecision::cpp_int;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repSE(i,s,n) for (int i = (s); i < (n); i++)
#define rrepSE(i,s,e) for (int i = (s); i > (e); i--)
#define ssort(v) sort(v.begin(), v.end())
#define gsort(v) sort(v.rbegin(), v.rend())
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }
#define DEBUG_PRINT(var) std::cout << #var << " = " << var << "\n";

int main()
{
    int n;
    string s;
    cin >> n;
    cin >> s;
    int ans = 0;
    set<int> mp[10];
    rep(id,n) {
        int sid = s[id] - '0';
        mp[sid].insert(id);
    }
    rep(i,10) rep(j,10) rep(k,10) {
        if (mp[i].size() == 0 || mp[j].size() == 0 || mp[k].size() == 0) continue;
        int id1 = *(mp[i].begin());
        auto it2 = mp[j].upper_bound(id1);
        if (it2 == mp[j].end()) continue;
        int id2 = *it2;
        auto it3 = mp[k].upper_bound(id2);
        if (it3 == mp[k].end()) continue;
        int id3 = *it3;
        ans ++;
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 5036