akhauriyash/Code-Regression huggingface dataset:
// khodaya khodet komak kon
#include <bits/stdc++.h>
#define pb push_back
#define ers erase
#define ins insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
#define kill(x) return cout << x, 0;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;

const ld Pi = 3.14159265359;
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll N = 2e5 + 10;
const ll INF = 1e18;
const ll LOG = 20;
str s;
int main(){
	IOS;
	cin >> s;
	ll ans1 = 0;
	ll ans2 = 0;
	for (int i = 0; i < s.size(); i+=2){
		if (s[i] == '1') ans1++;
		else{
			ans2++;
		}
	}
	for (int i = 1; i < s.size(); i += 2){
		if (s[i] == '0') ans1 ++;
		else ans2 ++;
	}
	cout << min(ans1, ans2);
	
	
	
	
	return 0;
}






/*
     ,---,           ___                 ,--,
    '  .' \        ,--.'|_             ,--.'|                             ,--,
   /  ;    '.      |  | :,'            |  | :                           ,--.'|    ,---.        ,---,
  :  :       \     :  : ' :            :  : '                 .--.--.   |  |,    '   ,'\   ,-+-. /  |
  :  |   /\   \  .;__,'  /    ,--.--.  |  ' |     ,--.--.    /  /    '  `--'_   /   /   | ,--.'|'   |
  |  :  ' ;.   : |  |   |    /       \ '  | |    /       \  |  :  /`./  ,' ,'| .   ; ,. :|   |  ,"' |
  |  |  ;/  \   \:__,'| :   .--.  .-. ||  | :   .--.  .-. | |  :  ;_    '  | | '   | |: :|   | /  | |
  '  :  | \  \ ,'  '  : |__  \__\/: . .'  : |__  \__\/: . .  \  \    `. |  | : '   | .; :|   | |  | |
  |  |  '  '--'    |  | '.'| ," .--.; ||  | '.'| ," .--.; |   `----.   \'  : |_|   :    ||   | |  |/
  |  :  :          ;  :    ;/  /  ,.  |;  :    ;/  /  ,.  |  /  /`--'  /|  | '.'\   \  / |   | |--'
  |  | ,'          |  ,   /;  :   .'   \  ,   /;  :   .'   \'--'.     / ;  :    ;`----'  |   |/
  `--''             ---`-' |  ,     .-./---`-' |  ,     .-./  `--'---'  |  ,   /         '---'
                            `--`---'            `--`---'                 ---`-'
*/




Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    int lenS=s.length(),lenT=t.length(),ans=1e4;
    for(int i=0;i+lenT<=lenS;i++)
	{
        int change=0;
        for(int j=0;j<lenT;j++)
		{
            if(s[i+j]!=t[j])
                change++;
        }
        ans=min(ans,change);
    }
    cout<<ans<<endl;
    return 0;
}

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

#define rep(i,n) for (int i = 0; i< (n); ++i)
#define vvec(m,n) vector<vector<int>> (int(m), vector<int>(n))
#define ALL(a) (a).begin(), (a).end()

using ll = long long;

int main(){
    int X, A, B;
    cin >> X >> A >> B;
    cout << (X - A) % B << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long 
#define N 18600
bool a[43][29][29][15];
LL f[16][43][29][29][15],state[N+20],n,ans;
int num,trans[N][10],len,all;char s[233];
LL dp[2][127][N+10][3];
void pre_work(){
	f[0][0][0][0][0]=1;
	for(int i=0;i<=14;i++)
		for(int j=0;j<=42;j++)
			for(int k=0;k<=28;k++)
				for(int l=0;l<=28;l++)
					for(int m=0;m<=14;m++)
						if(f[i][j][k][l][m]!=0){
							if(!a[j][k][l][m])a[j][k][l][m]=true,state[++num]=f[i][j][k][l][m];
							if(i==14)continue;
							for(int n=2;n<=10;n++)
								if(n==1)f[i+1][j][k][l][m]=f[i][j][k][l][m]*1;
								else if(n==2)f[i+1][j+1][k][l][m]=f[i][j][k][l][m]*2;
								else if(n==3)f[i+1][j][k+1][l][m]=f[i][j][k][l][m]*3;
								else if(n==4)f[i+1][j+2][k][l][m]=f[i][j][k][l][m]*4;
								else if(n==5)f[i+1][j][k][l+1][m]=f[i][j][k][l][m]*5;
								else if(n==6)f[i+1][j+1][k+1][l][m]=f[i][j][k][l][m]*6;
								else if(n==7)f[i+1][j][k][l][m+1]=f[i][j][k][l][m]*7;
								else if(n==8)f[i+1][j+3][k][l][m]=f[i][j][k][l][m]*8;
								else if(n==9)f[i+1][j][k+2][l][m]=f[i][j][k][l][m]*9;
								else if(n==10)f[i+1][j+1][k][l+1][m]=f[i][j][k][l][m]*10;
							}
	sort(state+1,state+num+1);
	for(int i=1;i<=N;i++){
		LL now=state[i];
		for(int j=0;j<=9;j++){
			LL to=state[i]*(j+1);
			int pos=lower_bound(state+1,state+num+1,to)-state;
			if(state[pos]==to)trans[i][j]=pos;
			else trans[i][j]=0;
		}
	}
}
int main(){
	pre_work();
	scanf("%s",s);len=strlen(s);n=1;
	for(int i=0;i<len;i++)n=n*(s[i]-'0'+1),all=all+(s[i]-'0');
	dp[0][0][1][1]=1;
	for(int i=0;i<len;i++){
		int now=i&1,to=now^1,sum=min(all,(i+1)*9);
		memset(dp[to],0,sizeof(dp[to]));
		for(int j=0;j<=sum;j++)
			for(int k=1;k<=N;k++){
				if(dp[now][j][k][0]){
					for(int l=0;l<=9;l++)
						dp[to][j+l][trans[k][l]][0]+=dp[now][j][k][0];
				}
				if(dp[now][j][k][1]){
					for(int l=0;l<s[i]-'0';l++)
						dp[to][j+l][trans[k][l]][0]+=dp[now][j][k][1];
					int r=s[i]-'0';
					dp[to][j+r][trans[k][r]][1]+=dp[now][j][k][1];
					for(int l=s[i]-'0'+1;l<=9;l++){
						dp[to][j+l][trans[k][l]][2]+=dp[now][j][k][1];
					}
				}
				if(dp[now][j][k][2]){
					for(int l=0;l<=9;l++)
						dp[to][j+l][trans[k][l]][2]+=dp[now][j][k][2];
				}
			}
	}
	int now=len&1,pos=lower_bound(state+1,state+num+1,n)-state;
	for(int i=0;i<all;i++)
		for(int j=1;j<=N;j++)
			for(int k=0;k<=2;k++)
				ans+=dp[now][i][j][k];
	for(int i=all;i<=all;i++)
		for(int j=1;j<pos;j++)
			for(int k=0;k<=2;k++)
				ans+=dp[now][i][j][k];
	for(int i=all;i<=all;i++)
		for(int j=pos;j<=pos;j++)
			for(int k=0;k<1;k++)
				ans+=dp[now][i][j][k];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 177472
#include <cstdio>

const int maxk=1e5+5, maxn=105, mod=1e9+7;

int dp[maxn][maxk];

inline int sum(int a, int b){
	if(a+b>=mod){
		return a+b-mod;
	}
	else if(a+b<0){
		return a+b+mod;
	}
	return a+b;
}

int main(){
	int n, k;
	scanf("%d%d", &n, &k);
	int a;
	dp[0][0]=1;
	int suma;
	for(int i=0; i<n; i++){
		scanf("%d", &a);
		suma=0;
		for(int j=0; j<=k; j++){
			suma=sum(suma, dp[i][j]);
			if(j-a>0){
				suma=sum(suma, -dp[i][j-a-1]);
			}
			dp[i+1][j]=suma;
		}
	}
	printf("%d\n", dp[n][k]);
	return 0;
}

Measured memory_bytes: 40704
#include<stdio.h>
int main()
{
    long long int A,B,C,D;
    scanf("%lld%lld%lld%lld",&A,&B,&C,&D);
    while(A>=0 && C>=0)
    {
        C = C - B;
        if(C<=0)
        {
            printf("Yes");break;
        }
        A = A - D;
        if(A<=0)
        {
            printf("No");break;
        }

    }
    return 0;
}


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

int main() {
	int n;
	cin >> n;
	
	long long a;
	long long Max = -1000000;
	long long Min =  1000000;
	long long Sum = 0;

	for (int i = 0; i < n; i++) {
		cin >> a;
		Sum += a;
		if (a >= Max) Max = a;
		if (a <= Min) Min = a;
	}

	cout << Min << " " << Max << " " << Sum << endl;

	return 0;
}


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

const int N=200100,mod=1000000007;
typedef long long ll;
int b[N],inv[N],n,X,Y,fa[N],sz[N];
pair<int,int>a[N];

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void U(int x,int y){fa[find(x)]=find(y);}


int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>X>>Y;inv[1]=1;
	for(int i=2;i<N;++i)inv[i]=mod-mod/i*(ll)inv[mod%i]%mod;
	for(int i=1;i<=n;++i)cin>>a[i].second>>a[i].first;
	sort(a+1,a+n+1);
	for(int i=n;i;--i)
		b[a[i].second]=i,fa[i]=i;
	for(int j=2;j<=n;++j){
		if(a[j].second!=a[1].second){
			for(int i=n;i;--i){
				if(i!=b[a[i].second]&&a[i].first+a[b[a[i].second]].first<=X)U(i,b[a[i].second]);
				else if(a[i].second!=a[1].second&&a[i].first+a[1].first<=Y)U(i,1);
				else if(a[i].second!=a[j].second&&a[i].first+a[j].first<=Y)U(i,1);
			}
			int ans=1;
			for(int i=1;i<=n;++i)
				if(find(i)==find(1)){
					ans=(ll)ans*(++sz[0])%mod;
					ans=(ll)ans*inv[++sz[a[i].second]]%mod;
				}
			cout<<ans<<'\n';
			return 0;
		}
	}
	cout<<1<<'\n';
	return 0;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
int main(){
  int n,m;
  while(cin >> n , n){
    int mas[22][22];
    memset(mas,0,sizeof(mas));
    for(int i=0;i<n;i++){
      int x,y;
      cin >> x >> y;
      mas[y][x] = 1;
    }
    cin >> m;
    int ny = 10,nx = 10;
    int cnt = 0;
    if(mas[ny][nx] == 1){
      cnt++;
      mas[ny][nx] = 0;
    }
    for(int i=0;i<m;i++){
      char c; int mv;
      cin >> c >> mv;
      if(c == 'N'){
	for(int j=0;j<mv;j++){
	  ny++;
	  if(mas[ny][nx] == 1){
	    cnt++;
	    mas[ny][nx] = 0;
	  }
	}
      }
      else if(c == 'S'){
	for(int j=0;j<mv;j++){
	  ny--;
	  if(mas[ny][nx] == 1){
	    cnt++;
	    mas[ny][nx] = 0;
	  }
	}
      }
      else if(c == 'E'){
	for(int j=0;j<mv;j++){
	  nx++;
	  if(mas[ny][nx] == 1){
	    cnt++;
	    mas[ny][nx] = 0;
	  }
	}
      }
      else {
	for(int j=0;j<mv;j++){
	  nx--;
	  if(mas[ny][nx] == 1){
	    cnt++;
	    mas[ny][nx] = 0;
	  }
	}
      }
    }
    if(cnt == n) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
#define inf 998244353
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
int dp[310][310][310]; 
string s;
int calc( int lef, int rig, int k){
	if( dp[lef][rig][k] != 0){
		return dp[lef][rig][k];
	}
	if( lef == rig ){
		return 1;
	}
	if( lef > rig ){
		return 0;
	}
	else{
		if( s[lef] == s[rig] ){
			dp[lef][rig][k] = calc( lef+1, rig -1, k ) + 2;
			return dp[lef][rig][k];
		}
		else{
			int c1 = -1;
			if( k > 0 ) c1 = calc( lef+1, rig-1, k-1) + 2;
			int c2 = calc( lef+1, rig, k);
			int c3 = calc( lef, rig-1, k);
			dp[lef][rig][k] = max( c1, max(c2,c3) );
			return dp[lef][rig][k];
		}
	}
}
signed main(){
	int k;
	cin >> s;
	cin >> k;
	int n = s.size();
	int ans = calc( 0, n-1, k );
	cout<<ans<<endl;
}

Measured memory_bytes: 221312
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
 

public class Main{
          
     
     public static void main(String args[]){
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
         try{
             String line;
            
             while((line=br.readLine())!= null){if(line.isEmpty())break;
                String[] spl=line.split(" ");
                int n1 = Integer.parseInt(spl[0]);
                int n2 = Integer.parseInt(spl[1]);
                int n3 = Integer.parseInt(spl[2]);
                int my=n1+n2; int countOut=0,countSafe=0;
                for(int i=1;i<=10;i++){
                    if(i==n1||i==n2||i==n3)continue;
                    if(i+my<=20)countSafe++;
                    else countOut++;
                }
                double p = (double) countSafe/(countOut+countSafe);
                 //System.out.println(p);//50<=p -> yes
                if(p>=0.5)System.out.println("YES");
                else System.out.println("NO");
             }br.close();
             
         }catch(Exception e){e.printStackTrace();}         
     }
   
 }

Measured memory_bytes: 16912
import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
ST = [readline().split() for _ in range(N)]
X = read().rstrip()

S, T = zip(*ST)

idx = S.index(X)
res = sum(map(int, T[idx+1:]))

print(res)


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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define ALL(x) x.begin(),x.end()
#define PB push_back
#define LL long long

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {
    _for(i,0,v.size()) os << v[i] << " ";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){
    for(typename set<T>::iterator it = v.begin();it != v.end();it++)
    os << *it <<" ";
    return os;
}

const LL mod = 1e9 + 7;


int main()
{
    LL A = 0,AB = 0,Q = 1;
    LL ans = 0;
    string s;
    cin >> s;
    _for(i,0,s.size()){
        char ch = s[i];
        if(ch == 'A') A += Q;
        else if(ch == 'B') {AB += A;AB %= mod;}
        else if(ch == 'C') {
            ans = (ans + AB)%mod;
        }
        else{
            ans = (3*ans)%mod;
            ans = (ans + AB)%mod;
            AB = (AB*3+A)%mod;
            A = (A*3+Q)%mod;
            Q = (Q*3)%mod;
        }
    }

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


Measured memory_bytes: 512
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			while(true){
				int n = Integer.parseInt(sc.next()), s =Integer.parseInt(sc.next());
				if(n == 0 && s == 0) break;
				System.out.println(dfs(0, 0, s, n));
			}
		}
	}
	public static int dfs(int total, int addval, int target, int n){
		if(n <= 0) return total == target ? 1 : 0;
		else if(addval >= 10) return 0;
		else return dfs(total + addval, addval + 1, target, n - 1) + dfs(total, addval + 1, target, n);
	}
}

Measured memory_bytes: 26096
#include <iostream>
using namespace std;
 
int main(){
    long long int N, K;
    cin >> N >> K;
    if(K%2 == 1){
        cout << (N/K)*(N/K)*(N/K);
    }else{
        cout << (N/K)*(N/K)*(N/K)+((N+K/2)/K)*((N+K/2)/K)*((N+K/2)/K);
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    ll cnt=0,ans=0;
    rep(i,len(s)){
      if(s[i]=='B'){
        cnt++;
      }else{
        ans+=cnt;
      }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 720
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int main(){
    int i,j,x,y,ans;
    ans=0;
    x=1;
    int n;
    int p[200000];
    scanf("%d",&n);
    int min=n;
    
    for(i=0;i<n;i++){
        scanf("%d",&p[i]);
    }
    for(i=0;i<n;i++){
        if(p[i]>min){  
            x=0;     
        } else{ min = p[i];}
        ans += x;
        x=1;
  
    }
    printf("%d",ans);
}

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

public class Main {

    private static final long MOD = 1_000_000_007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        int idx = 0;
        int num = 1;
        if (n % 2 != 0) {
            if (a[idx] != 0) {
                System.out.println(0);
                return;
            }
            idx++;
            num = 2;
        }
        long ans = 1;
        while (idx < n) {
            if (a[idx] != num || a[idx + 1] != num) {
                System.out.println(0);
                return;
            }
            idx += 2;
            num += 2;
            ans *= 2;
            ans %= MOD;
        }
        System.out.println(ans);
    }

}


Measured memory_bytes: 48764
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/04/28 10:57:41 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

#define MOD 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

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

// TOP
void	Main()
{
	string	s;
	cin >> s;

	bitset<26>	bs;
	rep(i, s.size())
		bs.set(s.at(i) - 'a');
	if (!bs.all())
	{
		cout << s;
		rep(i, 26)
		{
			if (!bs.test(i))
			{
				cout << (char)(i + 'a') << endl;
				return ;
			}
		}
	}
	// int	x;
	// rep(i, 25)
	// {
	// 	if (s.at(i) > s.at(i + 1))
	// 	{
	// 		x = i;
	// 		break ;
	// 	}
	// }
	// char	c;
	// if (x == -1)
	// 	x = 0;
	// c = s.at(x);
	string	original;
	original = s;
	if (!next_permutation(s.begin(), s.end()))
	{
		cout << -1 << endl;
		return ;
	}
	int i = 0;
	while (original.at(i) == s.at(i))
		i++;
	rep(j, i + 1)
		cout << s.at(j);
	cout << endl;
	// if (s.at(x) != c)
	// {
	// 	rep(i, x + 1)
	// 		cout << s.at(i);
	// 	cout << endl;
	// 	return ;
	// }
	// cout << s << endl;
}
// END

int		main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


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

#define ll long long
#define mp make_pair
#define pb push_back
#define loop(i, n)      for(int i = 0 ; i < n ; ++i)
#define rloop(i, n)     for(int i = int(n)-1 ; i >= 0 ; --i)
#define loopOne(i, n)   for(int i = 1 ; i <= n; ++i)
#define range(i, a, b)  for(int i = int(a) ; i <= int(b) ; ++i)
#define sz(x)   int(x.size())

void GO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
const ll N = 1e5+100, OO = 1e9;
int mx = -OO, mn = OO;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int arr[N], n, memo[N], res;

int Solve(int idx){

    if(memo[idx] != -1)    return memo[idx];
    int op1 = OO, op2 = OO;
    if(idx + 1 >= n)    return 0;
    op1 = abs(arr[idx]-arr[idx+1]) + Solve(idx+1);
    if(idx + 2 < n)
        op2 = abs(arr[idx]-arr[idx+2]) + Solve(idx+2);

    return memo[idx] = min(op1, op2);
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    GO();
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d", arr+i);
    }
    memset(memo, -1, sizeof(memo));
    printf("%d", Solve(0));
    return 0;
}

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

int main()
{
    int a,b,x,n,ans=0,j=0,l;
    cin >>a>>b>>x;
    n = (x%500==0 ? x/500 : x/500+1);
    l = (x%1000==0 ? x/1000 : x/1000+1);
    ans = a * l;
    for(int i=n;i>=0;i--)
    {
        int m = b*i+a*j;
        ans = (m<ans ? m: ans);
        j++;
        i--;
    }
    cout <<ans<<endl;
    return 0;
}


Measured memory_bytes: 3108
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char arr[100];
    scanf("%s", arr);

    int length= strlen(arr)-1;
    int counter=0,i=0;

    while(i<length){
        if(arr[i]==arr[length]){
            i++;
            length--;
        }else{
            arr[length]=arr[i];
            length--;
            i++;
        counter++;
        }
    }

    printf("%d",counter);

}





Measured memory_bytes: 128
#include <iostream>
#include <cstring>
#include <sstream>
#include <cctype>
using namespace std;

int P1 = 0, P2 = 0;

int main(){

	int n;
	cin >> n;

	for (int i = 0; i < n; i++){
		string W1, W2;
		cin >> W1 >> W2;
		for (int j = 0;;){
			W1[j] = tolower(W1[j]-'0');
			W2[j] = tolower(W2[j]-'0');
			if (W1[j] - 'a' > W2[j] - 'a'){
				P1+=3; break;
			}
			else if (W1[j] - 'a' < W2[j] - 'a'){
				P2+=3; break;
			}
			else if (j == W1.size() && j == W2.size()){
				P1++; P2++; break; 
			}
			else j++;
		}
	}

	cout << P1 << " " << P2 << endl;

	return 0;
}


Measured memory_bytes: 3156
#include <iostream>

int main() {
  using namespace std;

  int x, n;
  cin >> x >> n;

  bool flag[102] = { };
  for (int i = 0; i < n; i++) {
    int p;

    cin >> p;
    flag[p] = true;
  }

  int ans = 0;
  for (int i = 0; i < 102; i++) {
    if (!flag[i]) {
      if (abs(x - ans) > abs(x - i)) {
        ans = i;
      }
    }
  }

  cout << ans;

  return 0;
}


Measured memory_bytes: 3672
use std::io::stdin;

fn main() {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let n: i64 = s.trim().parse().unwrap();
    let itr = (1..=n).filter(|&e| !(e % 5 == 0 || e % 3 == 0));

    println!("{}", itr.sum::<i64>());
}


Measured memory_bytes: 2100
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <ctime>
 
using namespace std;
 
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
 
long gcd(long a, long b){
	if (a%b==0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}
}
 
long lcm(long a, long b){
	return (a*b) / gcd(a,b);
}
 
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a < b) { a = b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a > b) { a = b; return 1; } return 0; }
 
typedef long long ll;
 
const ll INF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS = 1e-10;

int main(){
	int a, b;
	
	cin >> a >> b;
	
	if (a <= 8 && b <= 8) cout << "Yay!" << endl;
	else cout << ":(" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <numeric>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, k, n) for(int i = (k); i < (int)(n); i++)
using namespace std;
using ll = long long;
int main(){
    ll N;
    cin >> N;
    ll a[N];
    ll sum[100001] = {0};
    ll cnt = 0;
    REP(i, N){
        cin >> a[i];
        if(a[i] > N)
            cnt++;//配列のサイズ以上の場合は捨てる
        else
            sum[a[i]]++;
    }
    FOR(i, 1, N + 1){
        if(sum[i] != 0){
            if(sum[i] > i)
                cnt += abs(i - sum[i]);
            else if(sum[i] < i)
                cnt += sum[i];
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 1792
while n = gets.to_i
  break if n.zero?
  data = []
  n.times do
    scores = gets.split.map(&:to_i)
    me_ave = scores[0,2].inject(&:+)/2.0
    ave = scores.inject(&:+)/3.0
    if scores.max == 100 || me_ave >= 90.0 || ave >= 80.0
      data << "A"
    elsif ave >= 70.0 || (ave >= 50 && scores[0,2].max >= 80)
      data << "B"
    else
      data << "C"
    end
  end
  puts data
end

Measured memory_bytes: 6144
use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let l: u64 = sc.read();
    let n = sc.read();
    let mut x: Vec<u64> = sc.vec(n);
    let ans1 = solve(&x, l);
    x = x.into_iter().rev().map(|x| l - x).collect();
    let ans2 = solve(&x, l);
    println!("{}", cmp::max(ans1, ans2));
}

fn solve(x: &Vec<u64>, l: u64) -> u64 {
    let n = x.len();
    let mut left_sum = vec![0; n + 1];
    for i in 0..n {
        left_sum[i + 1] = left_sum[i] + (l - x[n - 1 - i]);
    }
    let mut right_sum = vec![0; n + 1];
    for i in 0..n {
        right_sum[i + 1] = right_sum[i] + x[i];
    }

    let mut result = 0;
    for i in 0..n {
        let rest = n - i;
        let mut ans = 0;
        ans += (right_sum[rest / 2 + i] - right_sum[i]) * 2;
        ans += left_sum[rest / 2] * 2;
        if rest % 2 == 0 && rest / 2 > 0 {
            ans -= l - x[n - rest / 2];
        } else {
            ans += x[rest / 2 + i];
        }
        result = cmp::max(result, ans);
    }
    result
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

int solve () {
	int n;
	cin >> n;
	vector<long long> a(n);
	for (auto &e : a) cin >> e;
	string s;
	cin >> s;
	
	vector<long long> b;
	for (int i = n; i--> 0;) {
		long long e = a[i];
		for (const auto &c : b) e = min(e, e^c);
		if (e > 0) {
			if (s[i] == '1') return 1;
			b.push_back(e);
		}
	}
	return 0;
}

int main() {
	int t;
	cin >> t;
	while (t--) cout << solve() << '\n';
	return 0;
}

Measured memory_bytes: 3572
#![allow(non_snake_case)]

use std::collections::HashMap;
use std::io::{stdin, Read};
use std::str::FromStr;
fn read_option<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok()
}
fn read<T: FromStr>() -> T {
    let opt = read_option();
    opt.expect("failed to parse token")
}

fn main() {
    let N: usize = read();
    let t: usize = read::<usize>() - 1;
    let a: usize = read::<usize>() - 1;
    let mut m: HashMap<usize, Vec<usize>> = HashMap::new();
    for _ in 0..N - 1 {
        // 0 indexed
        let a = read::<usize>() - 1;
        let b = read::<usize>() - 1;
        m.entry(a).or_insert_with(|| vec![]).push(b);
        m.entry(b).or_insert_with(|| vec![]).push(a);
    }
    let mut max = 0;
    let t_dist: Vec<usize> = calc_distance(t, &m, N);
    let a_dist: Vec<usize> = calc_distance(a, &m, N);
    for (i, v) in t_dist.iter().enumerate() {
        if *v < a_dist[i] {
            max = std::cmp::max(max, a_dist[i]);
        }
    }
    println!("{}", max - 1);
}

fn calc_distance(origin: usize, map: &HashMap<usize, Vec<usize>>, max: usize) -> Vec<usize> {
    let mut vec = vec![0; max];
    dfs(origin, origin, &map, 0, &mut vec);
    vec
}
fn dfs(
    now: usize,
    parent: usize,
    map: &HashMap<usize, Vec<usize>>,
    depth: usize,
    result: &mut Vec<usize>,
) {
    result[now] = depth;
    for &child in &map[&now] {
        if child == parent {
            continue;
        }
        dfs(child, now, map, depth + 1, result)
    }
}


Measured memory_bytes: 20232
from fractions import gcd
a, b = map(int, input().split())
g = gcd(a, b)
ans = 1
for i in range(2, int(g ** 0.5) + 1):
    if g % i != 0:
        continue
    while g % i == 0:
        g //= i
    ans += 1
if g > 1:
    ans += 1
print(ans)


Measured memory_bytes: 5048
#include <bits/stdc++.h>
using namespace std;
int main(){
    char a, b;
    cin >> a >> b;
    if(a<b){
        cout << "<" << endl;
    }else if(a==b){
        cout << "=" << endl;
    }else{
        cout << ">" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
n=int(input())
box=sorted(list(map(int,input().split())))
if len(box)==2:print(max(box),min(box));exit()
max_box=max(box)
target=max_box//2
if max_box%2==0:
    if target not in box:
        box.append(target)
        box=sorted(box)
        add=box.index(target)
        if abs(target-box[add-1])>abs(target-box[add+1]):
            print(max_box,box[add+1])
        else:
            print(max_box,box[add-1])
    else:print(max_box,target)
else:
    if (target+1 not in box) and (target not in box):
        box.append(target)
        box=sorted(box)
        add=box.index(target)
        if abs(target-box[add-1])>abs(target+1-box[add+1]):
            print(max_box,box[add+1])
        else:print(max_box,box[add-1])
    else:
        if target in box:print(max_box,target)
        else:print(max_box,target+1)

Measured memory_bytes: 62704
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
#define il inline
#define ll long long
#define int __int128
#define gc getchar()
#define mp make_pair
#define P pair<int,int>
#define ri register int
#define rc register char
#define rb register bool
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
    
const int N=1e6+10;
int n,x,d,m[N],p[N],f[N],lim,dd,q[N],as;
struct node{int sz,cst,id;}nod[N];

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
il bool cmp(node gd,node gs){return gd.sz*gs.cst>gs.sz*gd.cst;}

signed main()
{
	//freopen("game.in","r",stdin);freopen("game.out","w",stdout);
	n=read(),x=read(),d=read();lim=n*n*n;m[1]=read();rp(i,2,n)m[i]=read(),p[i]=read();
	my(i,n,1){nod[i].id=i;nod[i].cst+=m[i];++nod[i].sz;nod[p[i]].cst+=nod[i].cst;nod[p[i]].sz+=nod[i].sz;}
	sort(nod+1,nod+1+n,cmp);rp(i,1,lim)f[i]=x+1;dd=min(n,d);
	rp(k,1,n)
	{
		ri v=nod[k].sz,w=nod[k].cst;
		rp(j,0,v-1)
		{
			ri p=(lim-j)/v,T=min(p,dd);if(nod[k].id==1)T=min(p,n);//if(!j)printf("p=%d T=%d\n",p,T);
			ri l=1,r=0;
			my(i,(lim-j)/v,1)
			{
				//if(!j && i==124964)printf("f1=%d f2=%d i-p=%d T=%d\n",f[j+q[r]*v]-q[r]*w,f[j+p*v]-p*w,i-p,T);
				while(~p && i-p<=T){while(l<=r && f[j+q[r]*v]-q[r]*w>f[j+p*v]-p*w)--r;q[++r]=p;--p;}
				while(l<=r && q[l]>=i)++l;;if(l<=r)f[j+i*v]=min(f[j+i*v],f[j+q[l]*v]+(i-q[l])*w);
				//if(!j && r<=100)printf("l=%d r=%d i=%d\n",l,r,i);
			}
			//printf("l=%d r=%d\n",l,r);
		}
	}
	rp(i,0,lim)
	{
		ri T=x-f[i],tmp=i,num;if(T<0)continue;
		//printf("f[%d]=%d\n",i,f[i]);
		rp(k,1,n)
		{
			if(nod[k].id==1)num=T;else num=d-dd;
			ri t=min(T/nod[k].cst,num);tmp+=t*nod[k].sz;T-=t*nod[k].cst;
		}
		as=max(as,tmp);
	}
	printf("%lld\n",(ll)as);
	return 0;
}
//val:sz;wei:cst;lim:d


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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

ll doubling(ll a, ll b) {
    // return a^b
    ll ans = 1;
    ll base = a;
    while (b != 0) {
        if (b & 1) {
            ans *= base;
            ans %= mod;
        }
        base *= base;
        base %= mod;
        b >>= 1;
    }
    return ans;
}

int main() {
source:
    ll n, k;
    cin >> n >> k;
    ll ans = 0;
    ll memo[k + 1];
    repd(i, 1, k + 1) {
        ll num = k / i;
        if (num == 1) {
            memo[i] = 1;
        } else {
            memo[i] = doubling(num, n);
        }
    }
    repd(x, 1, k + 1) {
        ll i = k - x + 1;
        ll num = 0;
        ll index = i * 2;
        while (index <= k) {
            num += memo[index];
            index += i;
        }
        memo[i] -= num;
        memo[i] = (memo[i] + mod * k) % mod;
        ans += memo[i] * i;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 4412
#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>

using namespace std;
const int INF = 1 << 29;

int main() {
    long long int N, Wmax;
    cin >> N >> Wmax;
    vector<long long int> V, W;
    map<long long int, long long int> c;
    map<long long int, priority_queue<long long int> > vp;
    for(int i = 0; i < N; i++) {
        long long int w, v;
        cin >> w >> v;
        V.push_back(v);
        W.push_back(w);
        c[w]++;
        vp[w].push(v);
    }

    vector<long long int> c_key;
    for(auto &e : c) {
        c_key.push_back(e.first);
    }

    long long int vmax = 0;
    for (int i = 0; i <= c[c_key[0]]; i++) {
        for (int j = 0; j <= c[c_key[1]]; j++) {
            for (int k = 0; k <= c[c_key[2]]; k++) {
                for (int l = 0; l <= c[c_key[3]]; l++) {
                    long long int w_ = c_key[0] * i + c_key[1] * j + c_key[2] * k + c_key[3] * l;
                    if (w_ > Wmax) continue;
                    long long int v_ = 0;
                    priority_queue<long long int> vp_1 = vp[c_key[0]];
                    priority_queue<long long int> vp_2 = vp[c_key[1]];
                    priority_queue<long long int> vp_3 = vp[c_key[2]];
                    priority_queue<long long int> vp_4 = vp[c_key[3]];
                    for (int v = 0; v < i; v++) {
                        v_ += vp_1.top(); vp_1.pop();
                    }
                    for (int v = 0; v < j; v++) {
                        v_ += vp_2.top(); vp_2.pop();
                    }
                    for (int v = 0; v < k; v++) {
                        v_ += vp_3.top(); vp_3.pop();
                    }
                    for (int v = 0; v < l; v++) {
                        v_ += vp_4.top(); vp_4.pop();
                    }
                    vmax = max(vmax, v_);
                }
            }
        }
    }
    cout << vmax << endl;



    return 0;
}

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

int main(){
    int N;  cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++)  cin >> A[i];
    sort(A.begin(), A.end());

    int m = 0;
    while(m != N-1){
        for(int i=m+1; i<N; i++) A[i] = A[i]%A[m];
        sort(A.begin(), A.end());
        m = lower_bound(A.begin()+m, A.end(), 1) - A.begin();
    }
    cout << A[m] << endl;
}

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(in.readLine());
    for(int i=111; i<=999; i=i+111) {
      if(i>=n){
        System.out.println(i);
        break;
      }
    }
  }
}
      

Measured memory_bytes: 21204
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define REP(i,n) for (ll i = 0; i < (n); ++i)


void solve(long long X, long long Y, long long Z){
    swap(X, Y);
    swap(X, Z);
    cout << X << " " << Y << " " << Z << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
int main(){
    long long X;
    scanf("%lld",&X);
    long long Y;
    scanf("%lld",&Y);
    long long Z;
    scanf("%lld",&Z);
    solve(X, Y, Z);
    return 0;
}


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

int add_num(int a)
{
	int sum=0;
	int value;
	while(a != 0){
		value = a % 10;
		sum += value;
		a /= 10;
	}
	return sum;
}

int main()
{
	int N,A,B;
	cin >> N >> A >> B;
	int sum = 0;
	for(int i=1; i<=N; i++){
		int ans = add_num(i);
		if(ans >= A && ans <= B){
			sum += i;
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string str, t;
    cin >> str >> t;
    bool b1 = false;
    string unrest = "UNRESTORABLE";
    int n = str.length();
    int t_len = t.length();
    vector<char> s(n, '*');
    // insert t
    for(int i=n-t_len; i>=0; --i){
        if(b1){
            break;
        }
        for(int j=0; j<t_len; ++j){
            if(!(str[i+j] == '?' || str[i+j] == t[j])){
                break;
            }
            if(j == t_len - 1){
                for(int k=0; k<t_len; ++k){
                    s[i+k] = t[k];
                    b1 = true;
                }
            }
        }
    }
    if(b1){
        for(int i=0; i<n; ++i){
            if(str[i] != '?'){
                s[i] = str[i];
            }
        }
        for(int i=0; i<n; ++i){
            if(s[i] == '*'){
                s[i] = 'a';
            }
        }
        for(int i=0; i<n; ++i){
            cout << s[i];
        }
    }
    else {
        cout << unrest;
    }
    cout << endl;
}


Measured memory_bytes: 256
import math


def main():
    N = int(input())

    # 1 * N
    ans = len(str(N))
    sqrt_N = int(math.sqrt(N))
    for i in range(2, sqrt_N + 1):
        if N % i == 0:
            d = N // i
            res = max(len(str(d)), len(str(i)))
            ans = min(ans, res)

    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
N=int(input())
t=[]
x=[]
y=[]
flag=False
for i in range(N):
  t1,x1,y1=[int(i) for i in input().split()]
  t.append(t1)
  x.append(x1)
  y.append(y1)
for i in range(N):
  if(i>0):
    t[i]=t[i]-t[i-1]
    x[i]=x[i]-x[i-1]
    y[i]=y[i]-y[i-1]

for i in range(N):
  if((x[i]+y[i])%2==t[i]%2 and abs(x[i])+abs(y[i])<=t[i]):
    flag=True
  else:
    flag=False
    break

if(flag):
  print("Yes")
else:
  print("No")

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

using namespace std;

int main(){
  int a,b;
  string s;
  cin>>a>>b;
  cin>>s;
  for(int i=0;i<a;i++){
    if(!('0'<=s[i] && s[i]<='9')){
      cout<<"No"<<endl;
      return 0;
    }
  }
    if(s[a] !='-'){
      cout<<"No"<<endl;
      return 0;
    }
  for(int i=a+1;i<a+b;i++){
    if(!('0'<=s[i] && s[i]<='9')){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
}


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

class Main{
	public static void main(String[] args){
		solve();
	}
	public static void solve(){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		int min = (int)Math.min(x,y);
		int ans = (int)Math.min(a+b, c*2)*min;
		ans += (int)Math.min(a*(x-min),2*c*(x-min)) + (int)Math.min(b*(y-min),2*c*(y-min));
		System.out.println(ans);
	}
}
	

Measured memory_bytes: 23764
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define break break
#define continue continue
#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, from, to) for(int i=(from); i<(int)(to); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define LLPair pair<ll, ll>
#define vint vector<int>
#define vll vector<ll>
typedef long long ll;

using namespace std;


int main(void){
	int n; cin >> n;
	rep(i, 500001){
		if((int)(i*1.08) == n){
			cout << i << endl;
			return 0;
		}
	}
	cout << ":(" << endl;
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul

mod = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


n = I()
P = LI()

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


ret = 0
for p in P:
    if p == -1:
        ret += 1

U = UnionFind(n)
for i in range(n):
    if P[i] != -1:
        U.union(P[i] - 1, i)

L = []
for j in range(n):
    if P[j] == -1:
        L += [U.size(j)]

dp = [0] * (len(L) + 1)
dp[0] = 1
for l in range(1, len(L) + 1):
    for m in range(l, 0, -1):
        dp[m] += dp[m - 1] * L[l - 1]

if L:
    dp[1] = sum(L) - len(L)
cycle_cnt = 0
for i in range(1, len(L) + 1):
    cycle_cnt = (cycle_cnt + fac[i - 1] * dp[i] * pow(n - 1, len(L) - i, mod)) % mod

ans = (n - (U.group_count() - ret)) * pow(n - 1, ret, mod) % mod
print((ans - cycle_cnt) % mod)


Measured memory_bytes: 237456
# A問題
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()

  for i in range(4):
    if s.count(s[i])!=2:
      return 'No'

  return 'Yes'

print(main())


Measured memory_bytes: 6860
import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
g = [list() for i in range(n)]
node = [0] * n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    node[p-1] += x

def dfs(v, p=-1):
    for u in g[v]:
        if u == p: continue
        node[u] += node[v]
        dfs(u, v)

dfs(0)
print(*node)

Measured memory_bytes: 268464
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define REPD(i,a,b) for (int i=(a);i<(b);i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef set<int> si;
typedef vector<si> vsi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<int> qi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const int mod = 1000000007;
const int INF = 1001001001;
// 小数点　<< fixed << setprecision(0) <<
// sort降順　sort(ALL(),greater<int>());
// 円周率　M_PI
// 文字判定　isupper islower
// 文字変換　
// 順列　do {} while(next_permutation(ALL(X)));
// 最大値　LLONG_MAX
// a内でx以上　auto iter = lower_bound(ALL(a), x);
// a内でxより大きい　auto iter = upper_bound(ALL(a), x);
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};
typedef struct edge se;
typedef vector<edge> ve;
unsigned Euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return Euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

vpll PrimeFactorization(ll n) {
  vpll res;
  for (ll i=2; i*i<=n; i++) {
    if(n%i!=0) continue;
    ll ex=0;
    while(n%i==0) {
      ex++;
      n/=i;
    }
    res.push_back(pll(i,ex));
  }
  if(n!=1) res.push_back(pll(n,1));
  return res;
}

int main() {
  int n;
  cin >> n;
  
  vb x(n+1,false);
  x[1]=true;
  REPD(i,2,n) {
    int j=i*i;
    while(j<=n) {
      x[j]=true;
      j*=i;
    }
  }
  REP(i,n){
    if(x[n-i]) {
      cout << n-i << endl;
      return 0;
    } 
  }
  
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cstring>
#include<functional>

using namespace std;

#define NAN -999999999999999999

int main()
{
	//freopen("input.txt", "r", stdin);

	int n;

	scanf("%d", &n);

	vector<long long> arr(200001);

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

	long long dp[200001][3];

	dp[0][0] = arr[0];
	dp[1][1] = arr[1];

	if (n >= 2)
	{
		dp[2][2] = arr[2];
		dp[2][0] = arr[0] + arr[2];
		dp[2][1] = NAN;
	}

	for (int i = 3; i < n; i++)
	{
		if (!(i % 2))
		{
			dp[i][0] = dp[i - 2][0] + arr[i];
			dp[i][1] = NAN;

			if (n % 2)
			{
				long long cand;

				cand = dp[i - 2][2];

				if (dp[i - 3][1] > cand)
				{
					cand = dp[i - 3][1];
				}

				if (i >= 4 && dp[i - 4][0] > cand)
				{
					cand = dp[i - 4][0];
				}

				dp[i][2] = cand + arr[i];
			}
		}

		else
		{
			dp[i][0] = dp[i][2] = NAN;

			long long cand;

			cand = dp[i - 2][1];

			if (dp[i - 3][0] > cand)
			{
				cand = dp[i - 3][0];
			}

			dp[i][1] = cand + arr[i];
		}
	}

	long long sol;

	if (n % 2)
	{
		sol = dp[n - 1][2];

		if (dp[n - 2][1] > sol)
		{
			sol = dp[n - 2][1];
		}

		if (n >= 3 && dp[n - 3][0] > sol)
		{
			sol = dp[n - 3][0];
		}
	}

	else
	{
		sol = dp[n - 1][1];

		if (dp[n - 2][0] > sol)
		{
			sol = dp[n - 2][0];
		}
	}

	printf("%lld\n", sol);

	return 0;
}

Measured memory_bytes: 9112