akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)

struct Card{
    char suit;
    int value;
};

void BubbleSort(Card c[], int n){
    
    for(int i=0; i<n-1; ++i){
        for(int j=n-1; j>i; --j){
            if(c[j].value < c[j-1].value){
                Card tmp = c[j-1];
                c[j-1] = c[j];
                c[j] = tmp;
            }
        }
    }
}

void SelectionSort(Card c[], int n){

    rep(i, n){
        int minv = i;
        for(int j=i; j<n; ++j){
            if(c[minv].value > c[j].value){
                minv = j;
            }
        }
        if(minv != i){
            Card tmp = c[minv];
            c[minv] = c[i];
            c[i] = tmp;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    Card bubble[36];
    Card insertion[36];
    rep(i, n){
        cin >> bubble[i].suit >> bubble[i].value;
        insertion[i] = bubble[i];
    }

    BubbleSort(bubble, n);
    rep(k, n){
        cout << bubble[k].suit << bubble[k].value;
        if(k != n-1){
            cout << " ";
        }
    }
    cout << "\n" << "Stable" << endl;

    SelectionSort(insertion, n);
    rep(k, n){
        cout << insertion[k].suit << insertion[k].value;
        if(k != n-1){
            cout << " ";
        }
    }
    cout << "\n";

    rep(i, n){
        if(bubble[i].suit != insertion[i].suit){
            cout << "Not stable" << endl;
            return 0;
        }
    }
    cout << "Stable" << endl;

    return 0;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
#define int           long long
#define pb            push_back
#define mp            make_pair
#define PI            3.14159265
#define M             1000000007
#define MM            998244353
#define fr            first
#define sc            second
#define all(v)        (v).begin(),(v).end()
#define rall(v)       (v).rbegin(),v.rend()
#define vc            vector
#define vi            vector<int>
#define pii           pair<int,int>
#define psi           pair<string,int>
#define pis           pair<int,string>
#define mii           map<int,int>
#define msi           map<string,int>

int ans1,ans2;
int solve(){
    string str; cin>>str;
    for (int i = 0; i < str.length(); ++i)
    {
        if(i%2){
            if(str[i]=='0') ans1++;
            else ans2++;
        }
        else{
            if(str[i]=='0') ans2++;
            else ans1++;
        }
    }
    cout<<min(ans1,ans2);
    return 0;
}

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

Measured memory_bytes: 512
def smaller(x, y):
	if x < y:
		return x
	return y

S = input()
dp0 = []
dp1 = []
if S[0] == '0':
	dp0.append(0)
	dp1.append(1)
else:
	dp0.append(1)
	dp1.append(0)
for i in range(1, len(S)):
	newdp0 = dp1[-1]
	newdp1 = dp0[-1] + 1
	if S[i] == '1':
		newdp0 = dp1[-1] + 1
		newdp1 = dp0[-1]
	dp0.append(newdp0)
	dp1.append(newdp1)
print(smaller(dp0[-1], dp1[-1]))

Measured memory_bytes: 51824
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
//#include<vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

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

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


	int N = getint();
	int A[300][300];
	bool owari = 0;
	rep(i, N) rep(j, N) A[i][j] = getint();
	rep(i, N) A[i][i] = 1e9;

	ll kotae = 0;
	rep(i, N) {
		rep(j, i) {
			bool B = 1;
			rep(k, N) {
				if (A[i][j] == A[i][k] + A[j][k]) B = 0;
				else if (A[i][j] > A[i][k] + A[j][k]) owari = true;
			}
			if (B) kotae += A[i][j];
		}
		if (owari) {
			printf("-1");
			return 0;
		}
	}

	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int X = sc.nextInt();

        int[] C = new int[N];
        int[][] A = new int[N][M];

        for (int i = 0; i < N; i++) {
            C[i] = sc.nextInt();
            for (int j = 0; j < M; j++) {
                A[i][j] = sc.nextInt();

            }

        }
        int ans = Integer.MAX_VALUE;

        int[] v = new int[M];
        for (int bit = 0; bit < (1 << N); ++bit) {
            Arrays.fill(v, 0);
            int cost = 0;
            for (int i = 0; i < N; i++) {
                if ((bit & (1 << i)) != 0) {
                    cost = cost + C[i];
                    for (int j = 0; j < M; j++) {
                        v[j] = v[j] + A[i][j];
                    }
                }
            }
            boolean ok = true;
            for (int i = 0; i < M; i++) {
                if (v[i] < X) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ans = Math.min(ans, cost);
            }

        }
        System.out.println(ans<Integer.MAX_VALUE ? ans : -1);
        sc.close();

    }
}

Measured memory_bytes: 28272
#include <bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010;
string n;
int dfs(int a,int b,int c,bool f,int i){
    if(a==0&&b==0&&c==0)return 1;
    int res=0;
    if(f){
        if(n[i]-'0'>3){
            if(a)res+=dfs(a-1,b,c,false,i+1);
        }else if(n[i]-'0'==3){
            if(a)res+=dfs(a-1,b,c,true,i+1);
        }
        if(n[i]-'0'>5){
            if(b)res+=dfs(a,b-1,c,false,i+1);
        }else if(n[i]-'0'==5){
            if(b)res+=dfs(a,b-1,c,true,i+1);
        }
        if(n[i]-'0'>7){
            if(c)res+=dfs(a,b,c-1,false,i+1);
        }else if(n[i]-'0'==7){
            if(c)res+=dfs(a,b,c-1,true,i+1);
        }       
    }else{
        if(a)res+=dfs(a-1,b,c,f,i+1);
        if(b)res+=dfs(a,b-1,c,f,i+1);
        if(c)res+=dfs(a,b,c-1,f,i+1);
    }
    return res;
}
int main(){
    cin>>n;
    int ans=0;
    for(int i=3;i<=n.length();i++){
        for(int j=1;j<=i-2;j++){
            for(int k=1;k<=i-j-1;k++){
                int l=i-j-k;
                    if(i!=n.length()){
                        ans+=dfs(j,k,l,false,n.length()-i);
                    }else{
                        ans+=dfs(j,k,l,true,0);
                    }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}   

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SZ(x) ((int) (x).size())
using namespace std;

int main() {
    #ifdef LOCAL_RUN
    freopen("task.in", "r", stdin);
    freopen("task.out", "w", stdout);
    //freopen("task.err", "w", stderr);
    #endif // ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    int ans = 0, cnt = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (x == i) {
            cnt++;
            if (cnt == 2) {
                ans += 1;
                cnt = 0;
            }
        } else {
            ans += cnt;
            cnt = 0;
        }
    }
    ans += cnt;
    cout << ans << '\n';
}


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

using namespace std;

int main()
{
	int a,b;
	
	cin >> a >> b ;
	
	if(a > b){
		cout << "a > b" << endl;
	}
	if(a < b){
		cout << "a < b" << endl;
	}
	if(a == b){
		cout << "a == b" << endl;
	}
	
}


Measured memory_bytes: 3064
num_str = input().split()
n, m = [int(i) for i in num_str]
count = 0

Mat = []
Vec = []

for i in range(n):
    row = input().split()
    row_i = [int(i) for i in row]
    Mat.append(row_i)

for i in range(m):
    Vec.append(int(input()))

for i in range(n):
    tmp_list = [x * y for (x, y) in zip(Mat[i], Vec)]
    print(sum(tmp_list))



Measured memory_bytes: 5980
a = list(map(int, input().split()))
now = 0
for j in range(max(a[0], a[1])):
    i = min(a[0], a[1]) - j
    if ((a[0] % i == 0) and (a[1] % i == 0)):
        now += 1
    if now == a[2]:
        print(i)
        break

Measured memory_bytes: 3064
def mergeSort(A,left,right):
    if left + 1 < right:
        mid = (left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

def merge(A,left,mid,right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000000)
    R.append(1000000000)

    i = 0
    j = 0
    for k in range(left,right):
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            count += len(L) - i - 1
            j += 1

n = int(input())
nums = list(map(int,input().split(" ")))
count = 0

mergeSort(nums,0,n)
print(count)



Measured memory_bytes: 27468
#include<iostream>
#include<string>
#include <vector>
#include<algorithm>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using pii = pair<int, int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define vsort(v) sort(v.begin(), v.end())
#define ll long long
const ll MOD = 1e9 + 7;

int main() {
	string s, t;
	cin >> s >> t;
	int n, m;
	n = s.size();
	m = t.size();
	vsort(s);
	vsort(t);
	bool a, b;
	a = false;
	b = false;
	if (n < m) {
		rep(i, n) {
			if (s[i] == t[i]) a = true;
			else {
				a = false;
				break;
			}
		}
	}
	if (s[0] < t[m - 1]) b = true;
	if (a || b) cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

int main () {
    int n; cin >> n;
  
  	int ans = -1 * n;
  	for (int i = 0; i < n; i++) {
		int temp;
      	cin >> temp;
      	ans += temp;
    }
  	cout << ans;
}   

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int main(){
  
  int S;
  cin >> S;
  
  int num;
  
  vector<int> a(10000005);
  
  a[0] = S;
  
  int num2;
  
  if(S == 2){
    num = 4;
  }
  else if(S == 1){
    num = 4;
  }
  else{
  for(int i = 0;i < 1000005;++i){
    if(a[i] % 2 == 0){
      a[i + 1] = a[i] / 2;
    }
    else{
      a[i + 1] = a[i] * 3 + 1;
    }
    
    if(a[i] == 4){
      num = i + 4;
      break;
    }   
  }
  }
  
  cout << num << endl;
    
}


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

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

    bool found = false;
    for(int i = 0; i < 4; i++){
        if(s[i] == 'A' && s[i+1] == 'C')    found = true;
    }

    if(found)   cout << "Yes" << endl;
    else        cout << "No" << endl;
    
    return 0;
}

Measured memory_bytes: 256
N=int(input())
resList=[[0]*10 for i in range(10)]
for i in range(1,N+1):
  SA=str(i)
  top=int(SA[0])
  bottom=int(SA[len(SA)-1])
  resList[top][bottom]+=1

#for i in range(10):
#  print(resList[i])

res=0
for i in range(1,10):
  for j in range(i,10):
    if i==j:
      res+=resList[i][j]**2
    else:
      res+=resList[i][j]*resList[j][i]*2
print(res)

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
 
int main(){
    int a, b;
    string s, t, u;
    cin >> s >> t >> a >> b >> u;
    if(s == u){
        cout << a-1 << " " << b << endl;
    }
    else if(t == u){
        cout << a << " " << b-1 << endl;
    }
    return 0;
}


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

const int MAX = 50000;

vector<int> prime;

bool is_prime(int n) {
  if (n == 2 || n == 3) return true;
  if (n % 2 == 0) return false;
  for (int i = 3; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}

signed main() {
  for (int i = 2; i < MAX; i++) {
    if (is_prime(i)) prime.push_back(i);
  }
  while (true) {
    int m, a, b;
    cin >> m >> a >> b;
    if (!m && !a && !b) return 0;
    int p, q;
    p = q = 1;
    for (int i = 0; i < prime.size(); i++) {
      int ptmp = prime[i];
      for (int j = i; j < prime.size(); j++) {
        int qtmp = prime[j];
        if (ptmp * qtmp > m) break;
        double res = (double) ptmp / qtmp;
        if (res < (double) a / b) break;
        if (ptmp * qtmp > p * q) {
          p = ptmp;
          q = qtmp;
        }
      }
    }
    cout << p << " " << q << endl;
  }
}



Measured memory_bytes: 3092
N = int(input())

odds = [i for i in range(1, N+1) if i % 2 != 0]

result = []
for odd in odds:
    z = []
    for i in range(1, odd+1):
        if odd % i == 0:
            z.append(i)

    if len(z) == 8:
        result.append(z)
print(len(result))

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int mi=0x7fffffff;
int ma=0x80000000;
const ll zfc=0xffffffff;
const ll MOD=1e9+7;
string st;
int main()
{
    ios::sync_with_stdio(false);
    cin>>st;
    sort(st.begin(),st.end());
    for(int i=0;i<st.size();i++)
    if(st[i]==st[i+1]){cout<<"no";return 0;}
    cout<<"yes";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>;
#include <vector>;
#include <math.h>;
using namespace std;

inline int get_bit ( int mask, int num )
{
	return ( mask >> num ) & 1;
}
inline int add_bit ( int mask, int num )
{
	return ( mask + ( 1 << num ) );
}


int main ()
{
	int n = 0, m = 0;
	int i = 0, j = 0;
	cin >> n >> m;
	vector < vector < pair < int, int> > > graph ( n );
	for ( i = 0; i < m; i++ )
	{
		int source, destiny, len;
		cin >> source >> destiny >> len;
		graph[source].push_back ( make_pair ( destiny, len ) );
		//graph[destiny].push_back(make_pair(source, len));
	}

	int max_mask = pow ( 2, n );
	vector < vector < int > > dp ( max_mask, vector < int > ( n, -1 ) );
	dp[1][0] = 0;
	for ( int mask = 1; mask < max_mask; mask++ )
	{
		for ( int vertex = 0; vertex < n; vertex++ )
		{
			for ( i = 0; i < graph[vertex].size (); i++ )
			{
				int next = graph[vertex][i].first;
				if ( !get_bit ( mask, next ) && (dp[mask][vertex] != -1) )
				{
					if ( ( dp[add_bit ( mask, next )][next] > ( dp[mask][vertex] + graph[vertex][i].second ) ) || ( -1 == dp[add_bit ( mask, next )][next] ) )
					{
						if ( add_bit( mask, next ) == 63 )
						{
							int a = 0;
						}
						dp[add_bit ( mask, next )][next] = dp[mask][vertex] + graph[vertex][i].second;
					}
				}
			}
		}

	}
	int result = -1;
	for ( i = 1; i < n; i++ )
	{
		for ( j = 0; j < graph[i].size (); j++ )
		{
			if ( 0 == graph[i][j].first )
			{
				if ( dp[max_mask - 1][i] != -1 )
				{
					if ( ( result > ( dp[max_mask - 1][i] + graph[i][j].second ) ) || ( result == -1 ) )
					{
						result = dp[max_mask - 1][i] + graph[i][j].second;
					}
				}
			}
		}
	}
	cout << result << endl;
	return 0;
}

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

int main(){
    string s;
    cin>>s;
    bool ans = true;
    for(int i = 0;i<s.length();++i){
        if(i%2==1){
            if(s[i]=='R')ans=false;
        }
        else{
            if(s[i]=='L')ans = false;
        }
    }
    if(ans)cout<<"Yes"<<endl;
    else cout <<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9;
using namespace std;
using ll = long long;
vector <ll> a(100002);
int main() {
    int N;
    cin >> N;
    ll sum = 0;
    for(int i = 1; i <= N; i++){
        cin >> a[i];
    }
    for(int i = 0; i <= N; i++){
        sum+=abs(a.at(i) - a.at(i + 1));
    }
    for(int i = 1; i < N + 1; i++){
        cout << sum - abs(a.at(i) - a.at(i - 1)) - abs(a.at(i) - a.at(i + 1)) + abs(a.at(i - 1) - a.at(i + 1)) << endl;
    }
}

Measured memory_bytes: 3908
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#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 fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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;}
const int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;



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

    int x;
    cin>>x;

    for(int i=1;i<100000;i++){
        if((ll)i*(i+1)/2>=x){
            cout<<i<<endl;
            return 0;
        }
    }
    

//////////////////////////////////////////////////////
return 0;}


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

using namespace std;

const int N = 1e3+10;


const int mod = int(1e9)+7;

char a[N][N];
int dp[N][N];

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

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}

	dp[1][1] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(i==1&&j==1) continue;
			if(a[i][j] == '.') {
				dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod;
			}
			//cout << dp[i][j] << " ";
		}
		//cout << endl;
	}

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

Measured memory_bytes: 8548
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
 
#pragma comment(linker, "/STACK:336777216")  
 
using namespace std;
 
const int MAXN = 300000 + 10;
 
int N, Q;
int sb[MAXN], zerob[MAXN];
int b[MAXN];
vector <int> p[MAXN];
int dp[MAXN];
int Tree[MAXN * 4];
 
void Modify(int Node, int L, int R, int Pos, int x)
{
	if (L == R)
	{
		Tree[Node] = x;
		return;
	}
	int Mid = (L + R) / 2;
	if (Pos <= Mid)
		Modify(Node * 2, L, Mid, Pos, x);
	else
		Modify(Node * 2 + 1, Mid + 1, R, Pos, x);
	Tree[Node] = min(Tree[Node * 2], Tree[Node * 2 + 1]);
}
 
int Query(int Node, int L, int R, int l, int r)
{
	if (L == l && r == R)
		return Tree[Node];
	int Mid = (L + R) / 2;
	if (r <= Mid)
		return Query(Node * 2, L, Mid, l, r);
	else if (l > Mid)
		return Query(Node * 2 + 1, Mid + 1, R, l, r);
	else
		return min(Query(Node * 2, L, Mid, l, Mid), Query(Node * 2 + 1, Mid + 1, R, Mid + 1, r));
}
 
void Work()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i ++)
	{
		scanf("%d", &b[i]);
		zerob[i] = zerob[i - 1] + (1 - b[i]);
	}
 
	scanf("%d", &Q);
	for (int i = 0; i < Q; i ++)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		p[l].push_back(r);
	}
	
	dp[0] = 0;
	memset(Tree, 1, sizeof(Tree));
	for (int i = 1; i <= N; i ++)
		dp[i] = 10000000;
 
	for (int i = 1; i <= N; i ++)
	{
		Modify(1, 1, N, i, dp[i - 1] - zerob[i - 1]);
 
		for (int j: p[i]) // [i, j]
		{
			// dp[j] <- dp[k - 1] + zerob[j] - zerob[k - 1];
			int tmp = Query(1, 1, N, i, j);
			dp[j] = min(dp[j], zerob[j] + tmp);
			if (j != N)
				Modify(1, 1, N, j + 1, dp[j] - zerob[j]);
		}
		dp[i] = min(dp[i], dp[i - 1] + (b[i] != 0));
	}
	printf("%d\n", dp[N]);
}
 
int main()
{
	Work();
	return 0;
}

Measured memory_bytes: 20608
using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;
using static System.Math;
using System.Linq;
using static System.Array;

namespace ConsoleApp2
{
    class Program
    {
        static long N;
        static long K;
        static long[] P;
        static long[] C;
        static bool[] used;
        static long[,] map;
        static void Main(string[] args)
        {
            //var A = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            //var N = long.Parse(Console.ReadLine());
            //var NK = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            //var N = NK[0];
            //var K = NK[1];
            var NK = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            N = NK[0];
            K = NK[1];

            P = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            C = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            map = new long[N, 2];
            used = new bool[N];
            for (int i = 0; i < N; i++)
            {
                if (!used[i])
                {
                    Cul(i);
                }
            }

            long ans = long.MinValue;
            for (int i = 0; i < N; i++)
            {
                var rep = map[i, 0];
                var reps = 0L;
                var repb = false;
                long sum = 0;
                long tai = 0;
                if (map[i, 1] > 0 && K >= map[i, 0])
                {
                    reps = map[i, 1] * (K / map[i, 0] -1);
                    repb = true;
                    sum = reps;
                    ans = Max(ans, sum);
                    tai = K - ((K / map[i, 0]) - 1) * map[i, 0];
                }


                var restmove = 0L;
                if (repb)
                {
                    restmove = tai;
                }
                else if(K >= map[i, 0])
                {
                    restmove = Max(map[i, 0],1);
                }
                else
                {
                    restmove = Max(K,1);
                }

                var next = i;
                for (int j = 0; j < restmove; j++)
                {
                    next = (int)P[(int)next] - 1;
                    sum += C[next];
                    ans = Max(ans, sum);
                }
            }

            Console.WriteLine(ans);

        }

        static void Cul(int next)
        {
            long sum = 0;
            long count = 0;
            var avail = new List<int>();
            while (!used[next])
            {
                used[next] = true;
                avail.Add(next);
                next = (int)P[(int)next] - 1;
                sum += C[next];
                count++;
            }

            foreach (var item in avail)
            {
                map[item, 0] = count;
                map[item, 1] = sum;

            }
        }


    }
}


Measured memory_bytes: 29428
#include <stdio.h>
 
int main(void){
    char Str[1200];
    char *p;
    gets(Str);
    for(p = Str; *p!='\0'; p++){
        if('a' <= *p && *p <= 'z')*p+='A'-'a';
        else if('A' <= *p && *p <= 'Z')*p+='a'-'A';
    }
    printf("%s\n",Str);
 
    return 0;
}

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

#define v(type) vector<type> 
#define map(type1,type2) map<type1,type2>
#define INF 1000000005
#define pb push_back
#define mp make_pair
#define f0(i,n) for(i = 0; i < ( n ); i ++)
#define f1(i,n) for(i = 1; i <= ( n ); i ++)
#define f(i,m,n) for(i = ( m ); i <= ( n ); i ++)
#define nl cout<<endl

typedef long long int ll;
typedef unsigned long long int ull;

const int mod=1e9+7;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int h,w;
    cin>>h>>w;
    vector<vector<char> > grid(h,vector<char>(w));
    int i,j;
    f(i,0,h-1)
    {
        f(j,0,w-1)
        {
            char ch;
            cin>>ch;
            grid[i][j]=ch;
        }
    }
    vector<vector<int> > dp(h,vector<int>(w));
    dp[0][0]=1;
    for(int row=0;row<h;row++)
    {
        for(int col=0; col<w; col++)
        {
            for(int r2=row; r2<=row+1; r2++)
            {
                int c2=col;
                if(r2==row)
                    c2=col+1;
                if(r2<h && c2<w && grid[r2][c2]=='.')
                {
                    dp[r2][c2]=(dp[row][col]+dp[r2][c2])%mod;
                }
            }
        }
    }
    cout<<dp[h-1][w-1];
    return 0;
}

Measured memory_bytes: 5248
N = int(input())
W = [0]*N
for i in range(N):
    W[i] = input()

if len(W) != len(set(W)):
    print("No")
else:
    ans = "Yes"
    for i in range(1, N):
        if W[i-1][-1] != W[i][0]:
            ans = "No"
            break
    print(ans)



Measured memory_bytes: 3060
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner sc = new Scanner(System.in);

		ArrayList<String> lines = new ArrayList<String>();
		int in = 0;

		while (true) {
			String string = sc.nextLine();

			if (string.equals("0 0")) {
				break;
			}
			lines.add(string);
			in++;
		}

		for (int i = 0; i < in; i++) {
			int answer = 0;
			String[] kari = lines.get(i).split(" ");
			int n = Integer.parseInt(kari[0]);
			int x = Integer.parseInt(kari[1]);

			for (int j = 1; j <= n - 2; j++) {
				for (int k = j + 1; k <= n - 1; k++) {
					for (int l = k + 1; l <= n; l++) {
						if (j + k + l == x) {
							answer++;
						}
					}

				}

			}
			
			System.out.println(answer);

		}
	}

}

Measured memory_bytes: 27248
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
  int N, a, b, i, j, num=0, judge=0, sub;
  cin >> N >> a >> b;
  sub = abs(a - b);
  if (sub%2)
    judge = 1;
  else
    judge = -1;
  if (judge == -1)
    cout << "Alice" << endl;
  else if (judge == 1)
    cout << "Borys" << endl;
  else if (judge == 0)
    cout << "Draw" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n;
long long a[100005];
long long ans=0;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    int res=4;
    for(int i=n-1;i>=0;i--)
    {
        int num=1;
        int j=i-1;
        for(;j>=0;j--)
        {
            if(a[i]==a[j])num++;
            else break;
        }
        if(num>=4&&res==4)
        {
            res=0;
            ans=a[i]*a[i];
            break;
        }
        else if(num>=4&&res==2)
        {
            res=0;
            ans*=a[i];
            break;
        }
        else if(num>=2&&res==4)
        {
            res=2;
            ans=a[i];
        }
        else if(num>=2&&res==2)
        {
            res=0;
            ans*=a[i];
            break;
        }
        i=j+1;
    }
    if(res==0) cout<<ans;
    else printf("0");
    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = (N + 999) / 1000;
		int r = M * 1000 - N;
		System.out.println(r);
	}
}


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

const int MAXN = 100010;
long long a[MAXN];
int main() {
	int n;
	cin>>n;
	for (int i=0; i<n+1; i++)
		cin>>a[i];
	long long ans = 0;
	for (int i=0; i<n; i++) {
		long long b;
		cin>>b;
		long long tmp1 = min(a[i], b);
		ans += tmp1;
		b -= tmp1;
		long long tmp2 = min(a[i+1], b);
		ans += tmp2;
		a[i+1] -= tmp2;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll=long long ;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int> h(n);
    rep(i,n) cin>>h[i];
    vector<int> data(n,1);
    rep(i,m){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        if(h[a]>h[b]) data[b]=0;
        else if(h[a]<h[b]) data[a]=0;
        else{
            data[a]=0;
            data[b]=0;
        }
    }
    int ans=0;
    rep(i,n) ans+=data[i];
    cout<<ans;
}

Measured memory_bytes: 3984
#include <stdio.h>          // printf(), fprintf(), scanf()
#include <stdlib.h>         // exit()
#include <string.h>         // strlen(), strcpy()

#define QUE_SIZE 100000
#define L_STRINGS (11 * 100000)

typedef struct que_tbl
{
	const char* name;
	int time;
} que_t;

int que_in;
int que_out;
que_t queue[QUE_SIZE];
char strings[L_STRINGS];
int ix;

void
cleanup(int ecode)
{
	exit(ecode);
}

int
que_size()
{
	if (que_in >= que_out)
		return que_in - que_out;

	return que_in + QUE_SIZE - que_out;
}

void
que_pop()
{
	if (que_out != que_in)
	{
		que_out++;
		if (que_out >= QUE_SIZE)
			que_out = 0;
	}
}

int
main(int argc, char** argv)
{
	char name[11];
	int time;
	int q;
	int n;
	int i, j;
	int t;

	ix = 0;
	que_in = 0;
	que_out = 0;

	scanf("%d %d", &n, &q);
	for (i = 0; i < n; ++i)
	{
		scanf("%s %d", name, &t);
		queue[que_in].name = &strings[ix];
		queue[que_in].time = t;
		que_in++;
		if (que_in >= QUE_SIZE)
			que_in = 0;

		strcpy(&strings[ix], name);
		ix += strlen(name) + 1;
	}

	time = 0;
	while (que_size() != 0)
	{
		j = que_out; que_pop();
		if (queue[j].time <= q)
		{
			time += queue[j].time;
			printf("%s %d\n", queue[j].name, time);
		}
		else
		{
			queue[que_in].name = queue[j].name;
			queue[que_in].time = queue[j].time - q;
			que_in++;
			if (que_in >= QUE_SIZE)
				que_in = 0;

			time += q;
		}
	}

	return 0;
}



Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
 
int main(){
 
	string s, t;
	cin >> s >> t;
 
	int slen = s.length(), tlen = t.length();
 
	int lcs[slen+1][tlen+1];
 
	for (int i = 0; i <= slen; ++i) {
		for (int j = 0; j <= tlen; ++j) {
			if(0 == i || 0 == j ) lcs[i][j] = 0;
			else if(s[i-1] == t[j-1]){
				lcs[i][j] = lcs[i-1][j-1] + 1;
			}
			else{
				lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1]);
			}
		}
	}
 
	int i = slen, j = tlen;
	string ans;
 
	while(i != 0 && j != 0){
		if(s[i-1] == t[j-1]){
			ans += s[i-1];
			i--;
			j--;
		}
		else if(lcs[i-1][j] > lcs[i][j-1]) i--;
		else j--;
	}
 
	reverse(ans.begin(), ans.end());
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 35456
import java.util.Scanner;class Main{public static void main(String[] q){Scanner c=new Scanner(System.in);for(;;){int n=c.nextInt(),s=c.nextInt();if(n==0&&s==0)break;System.out.println(f(0,0,s,n));}}static int f(int x,int a,int t,int n){return n==0?x==t?1:0:a>9?0:f(x+a,a+1,t,n-1)+f(x,a+1,t,n);}}

Measured memory_bytes: 26368
import java.util.*;
public class Main{
	 public static void main(String[] args) {
		 Scanner sc = new Scanner(System.in);
		 int n = sc.nextInt();
		 int w[]=new int[n];
		 boolean f=true;
		 for (int i = 0; i < n; i++) {
				w[i]=sc.nextInt();
				
				}
		 int temp=0;
		 for(int i=0;i<n;i++) {
			  for(int j=0;j<n;j++) {
				  if(w[i]<w[j]) {
				  temp=w[i];
				  w[i]=w[j];
				  w[j]=temp;
			  }
		 }
		 }
		 int ans=0;
		 for(int i=0;i<n;i++) {
			while(w[i]%2==0) {
				w[i]=w[i]/2;
				ans++;
				
			}
		 }
		System.out.println(ans);
		 
		 }
		 
	 }
	

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll h,w;
  cin >> h >> w;
  if(h%3==0 || w%3==0){
    cout << 0 << endl;
    return 0;
  }
  ll ans = 1e9;
  // horizontal
  CHMIN(ans,w);
  // vertical
  CHMIN(ans,h);
  ll sh = h/3;
  CHMIN(ans,max(abs((h-sh)*(w%2)),max(abs(sh*w-(h-sh)*(w/2)),abs(sh*w-(h-sh)*(w-w/2)))));
  sh++;
  CHMIN(ans,max(abs((h-sh)*(w%2)),max(abs(sh*w-(h-sh)*(w/2)),abs(sh*w-(h-sh)*(w-w/2)))));
  ll sw = w/3;
  CHMIN(ans,max(abs((w-sw)*(h%2)),max(abs(sw*h-(w-sw)*(h/2)),abs(sw*h-(w-sw)*(h-h/2)))));
  sw++;
  CHMIN(ans,max(abs((w-sw)*(h%2)),max(abs(sw*h-(w-sw)*(h/2)),abs(sw*h-(w-sw)*(h-h/2)))));
  cout << ans<< endl;
  return 0;
}


Measured memory_bytes: 764
n = int(input())
ans = 0
for i in range(2,10**6+1):
  m = int(n)
  while True:
    if m % i == 0:
      m //= i
    elif m % i == 1:
      #print(i)
      ans += 1
      break
    else:
      break
for i in range(1,10**6+1):
  if (n-1) % i == 0 and (n-1) // i > 10**6:
    #print((n-1)//i,i)
    ans += 1
if n > 10**6:
  ans += 1
print(ans)

Measured memory_bytes: 3064
N = int(input())

ans = 0
if N<6:
    ans = N
else:
    amari = N%3
    N = N-amari

    #準備として１度に引き出せる金額を列挙（N以下）
    hiki = []
    i=1
    #6の累乗
    while True:
        if 6**i<=N:
            hiki.append(6**i)
        else:
            break
        i+=1
    #9の累乗
    i=1
    while True:
        if 9**i<=N:
            hiki.append(9**i)
        else:
            break
        i+=1
    hiki.sort()

    #動的計画法でテーブルを作る
    #テーブルは
    #0円を引き出すのに必要な回数、3円を引き出すのに必要な回数、6円を引き出すのに必要な回数
    #9円を引き出すのに必要な回数、12円を引き出すのに必要な回数、15円を引き出すのに必要な回数・・・と続く
    table = [0,3]
    i=6
    while True:
        if i in hiki:
            table.append(1)
        else:
            tableTmp=[]
            for j in hiki:
                if i-j<0:
                    break
                else:
                    tableTmp.append(table[(i-j)//3]+1)
            table.append(min(tableTmp))
        if i == N:
            break
        i += 3
    ans = table[N//3] + amari

print(ans)

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

int main(){
  int a[3];
  cin>>a[0]>>a[1]>>a[2];
  sort(a,a+3);

  int ans=a[2]-a[1];
  a[0]+=ans;

  ans+=(a[2]-a[0]+1)/2+((a[2]-a[0])%2==0?0:1);

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr auto INF = INT_MAX >> 1;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

int main() {

	int n;
	cin >> n;
	V<P> rob(n);
	rep(i, n) {
		int x, l;
		cin >> x >> l;
		rob[i] = make_pair(x, l);
	}

	sort(all(rob));

	stack<P> can;
	can.push(rob[0]);

	rep1(i, n - 1) {
		if (can.top().first + can.top().second <= rob[i].first - rob[i].second)can.push(rob[i]);
		else if(can.top().first + can.top().second > rob[i].first + rob[i].second) {
			can.pop();
			can.push(rob[i]);
		}
	}

	cout << can.size() << endl;

}

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

int main()
{
    long a,b;
    char op;
    cin>>a;
    cin>>op;
    cin>>b;
    //cout<<a<<b<<endl;
    if(op=='+')
        cout<<(a+b);
    else if(op=='-')
            cout<<(a-b);
    return 0;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define P 1000000007
#define N 2005 
int n,x;
bitset<N*N>dp;
int main(){
	int n,sum=0,ans;
	cin>>n;
	dp.set(0);
	for(int i=0;i<n;i++){
		cin>>x;sum+=x;
		dp|=dp<<x;
	}
	for(int i=1;i<=sum;i++)if(dp.test(i)){
		if(i>=sum-i){
			ans=i;break;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1664
import sys

n, m = map(int, sys.stdin.readline().split())
line = sys.stdin.readline().split()
nums = list(map(int, line))

sumi = sum(nums)
barr = (sumi / (4 * m))

if sum([1 for x in nums if x >= barr]) >= m:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solve(int u, const vector<vector<int>>& conn){
	if(conn.empty()){ return 0; }
	vector<int> x;
	for(const int v : conn[u]){
		x.push_back(solve(v, conn));
	}
	const int k = x.size();
	sort(x.begin(), x.end(), greater<int>());
	int answer = 0;
	for(int i = 0; i < k; ++i){
		answer = max(answer, x[i] + i + 1);
	}
	return answer;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<vector<int>> a(n);
	for(int i = 1; i < n; ++i){
		int ai;
		cin >> ai;
		a[ai - 1].push_back(i);
	}
	cout << solve(0, a) << endl;
	return 0;
}



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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll dp[100005][3];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    REP(i, N) {
        ll A[3];
        REP(j, 3) {
            cin >> A[j];
        }

        REP(j, 3) {
            dp[i + 1][j] = std::max(dp[i][(j + 1) % 3], dp[i][(j + 2) % 3]) + A[j];
        }
    }
    cout << std::max({dp[N][0], dp[N][1], dp[N][2]}) << endl;
    return 0;
}

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

using namespace std;

int main(){
    int n, k; cin >> n >> k;
    
    int x, c[200000] = {}, cnt = 0;
    for(int i = 0;i < n;i++){
        cin >> x;
        c[x-1]++;
        if(c[x-1]==1) cnt++;
    }

    sort(c, c+n);

    int ans = 0;
    for(int i = 0, j = 0; i < cnt - k; i++, j++){
        if(c[j] ==0 ) i--;
        ans += c[j];
    }

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


Measured memory_bytes: 1024
//ABC042 2020-8-3
#include<iostream>

bool is_575(int a, int b, int c);
void swap(int& a, int& b);
int main()
{
    int a, b, c;
    std::cin >> a >> b >> c;
    if(is_575(a, b, c)){
        std::cout << "YES\n";
    }else{
        std::cout << "NO\n";
    }
    return 0;
}

bool is_575(int a, int b, int c)
{
    if(a > b) swap(a, b);
    if(a > c) swap(a, c);
    if(b > c) swap(b, c);
    return (a == 5 && b == 5 && c == 7);
}

void swap(int& a, int& b)
{
    int tmp = a;
    a = b;
    b = tmp;
}


Measured memory_bytes: 3576
#include<iostream>
#include<map>

using namespace std;

int Fr[15];
map<pair<int,int>,int> M;

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

    int h,w,n;
    cin>>h>>w>>n;

    for(int i=1; i<=n; i++)
    {
        int x,y;
        cin>>x>>y;

        for(int x1=max(x-2,1); x1<=x; x1++)
        {
            for(int y1=max(y-2,1); y1<=y; y1++)
            {
                if(x1+2>h || y1+2>w)
                    break;
                M[{x1,y1}]++;
            }
        }

    }

    long long zero=1LL*(h-2)*(w-2);
    for(auto el:M)
    {
        zero--;
        Fr[el.second]++;
    }

    cout<<zero<<"\n";
    for(int i=1; i<=9; i++)
        cout<<Fr[i]<<"\n";
    return 0;
}


Measured memory_bytes: 56576
#include<cstdio>
using namespace std;
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    int A[n][m],b[m];
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&A[i][j]);
        }
    }
    
    for(int i=0;i<m;i++){
        scanf(" %d",&b[i]);
    }
    int ans[n];

    for(int i=0;i<n;i++){
        ans[i]=0;
        for(int j=0;j<m;j++){
            int tmp;
            tmp=A[i][j]*b[j];
            ans[i]+=tmp;
        }
        printf("%d\n",ans[i]);
    }

}


Measured memory_bytes: 2752
#pragma GCC optimize (3)
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>
#define PII pair<int,int>
#define ll long long
#define ull unsigned long long
#define INFI 2147483647
#define INFL 9223372036854775807
#define INFU 18446744073709551615
using namespace std;
using namespace __gnu_pbds;
const double PI=acos(-1.0);
const double eps=1e-6;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main()
{
	//ios_base::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
	ll n;
	while(cin>>n){
        if(n==1) printf("%d\n",0);
        else{
            ll i;
            for(i=1;i*i<n;i++);
            i--;
            if((i+1)*(i+1)==n) printf("%lld\n",i+i);
            else{
                for(;i>=1;i--) if(n%i==0) break;
                printf("%lld\n",i+(n/i)-2);
            }
        }
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,a,b) for (int i = (a); i < (b); i++ )
typedef pair<int,int> P;
typedef long long ll;
const int INF = 100000000;

int main() {
    int H,W;
    cin >> H >> W;
    char S[H][W];
    
    rep(h,0,H) {
        rep(w,0,W) {
            cin >> S[h][w];
        }
    }

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

    bool ans = true;
    rep(h,0,H) {
        rep(w,0,W) {
            if (S[h][w] != '#') {
                continue;
            }
            int tmp = 0;
            rep(i,0,4) {
                if(h+dy[i]>=0 && h+dy[i]<H && w+dx[i]>=0 && w+dx[i]<W) {
                    if (S[h+dy[i]][w+dx[i]]=='#') {
                        tmp++;
                    }
                }
            }
            if (tmp==0) {
                ans = false;
            }
        }
    }

    if (ans) { 
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (ll i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m1(x) memset(x,-1,sizeof(x))
const int INF = 1000000001;


int H, W;
char board[20][20];
int dist[20][20];

int bfs(int sx, int sy, int gx, int gy){
  rep(i,20) m1(dist[i]);
  dist[sy][sx] = 0;
  queue<P> que;
  que.push(P(sx, sy));
  int dx[4] = {-1, 0, 1, 0};
  int dy[4] = {0, -1, 0, 1};
  while(!que.empty()){
    P p = que.front();
    que.pop();
    if(p.first == gx && p.second == gy) break;
    int nx, ny;
    rep(i, 4){
      nx = dx[i] + p.first;
      ny = dy[i] + p.second;
      if(nx >= W || nx < 0 || ny >= H || ny < 0 || dist[ny][nx] != -1 || board[ny][nx] == '#') continue;
      dist[ny][nx] = dist[p.second][p.first] + 1;
      que.push(make_pair(nx, ny));
    }
  }
  return dist[gy][gx];
}

int main(){
  cin >> H >> W;
  rep(i, H){
    rep(j, W){
      cin >> board[i][j];
    }
  }
  int ans = -1;
  rep(i, H){
    rep(j, W){
      if(board[i][j] == '#') continue;
      rep(k, H){
        rep(l, W){
          if(board[k][l] == '#') continue;
          int tmp = bfs(j,i,l,k);
          ans = max(tmp, ans);
        }
      }
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 256
from sys import stdin

S = stdin.readline().rstrip()
N = len(S)
Sp = S

res_map = [0 for _ in range(N)]

aa_list2 = [1]
for i in range(1,N):
    aa_list2.append((aa_list2[i-1]*10)%2019)

res_map[N-1] = int(S[N-1])
index=1


for i in range(N-2,-1,-1):
    res_map[i] = (int(S[i])*aa_list2[index] + res_map[i+1])%2019
    index+=1

aa_table = [0 for i in range(2019)]
for i in range(len(res_map)):
    aa_table[res_map[i]]+=1

aa_table[0]+=1

tot = 0
for i in range(2019):
    tot+=int((aa_table[i]-1)*aa_table[i]/2)

print(tot)


Measured memory_bytes: 83156
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
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;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
typedef pair<pll, pll> P;
const ll INF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;
const bool debug = 0;
//---------------------------------//

// RangeSumQuery (??????????§???????)
template<typename T>
struct SegTree {
	T init_val;
	int n;
	vector<T> all, part;
	
	SegTree(int _n, T init_val) : init_val(init_val) {
		n = 1;
		while (n < _n) n *= 2;
		all.resize(n * 2 - 1, init_val);
		part.resize(n * 2 - 1, init_val);
	}
	
	// [a,b)???????´????x???????§???????
	void add(int a, int b, T x, int k, int l, int r) {
		if (r <= a || b <= l) return;
		
		if (a <= l && r <= b) {
			all[k] += x;
		}
		else {
			part[k] += (min(b, r) - max(a, l)) * x;
			add(a, b, x, k * 2 + 1, l, (l + r) / 2);
			add(a, b, x, k * 2 + 2, (l + r) / 2, r);
		}
	}
	void add(int a, int b, T x) {
		add(a, b, x, 0, 0, n);
	}
	
	// [a,b)???????¨?????±???????
	T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) return init_val;
		if (a <= l && r <= b) return (r - l) * all[k] + part[k];
		
		T res = (min(b, r) - max(a, l)) * all[k];
		res += query(a, b, k * 2 + 1, l, (l + r) / 2);
		res += query(a, b, k * 2 + 2, (l + r) / 2, r);
		return res;
	}
	T query(int a, int b) {
		return query(a, b, 0, 0, n);
	}
};

int main() {
	int n, q; cin >> n >> q;
	
	SegTree<ll> st(n, 0);
	
	while (q--) {
		int a, b, c, d;
		cin >> a >> b >> c;
		if (a == 0) {
			cin >> d;
			st.add(b - 1, c, d);
		}
		else printf("%lld\n", st.query(b - 1, c));
	}
	
	return 0;
}

Measured memory_bytes: 7036
#include <bits/stdc++.h>
//#include <mylib.h>
using namespace std;
//cin.sync_with_stdio(false);

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FOR_EQ(i,a,b) for(int i = (a); i <= (b); ++i)
#define FOR_RE(i,a,b) for(int i = (a); i > (b); --i)
#define rep(i,n) FOR(i,0,n)
#define rep_eq(i,n) FOR_EQ(i,0,n)
#define rep_re(i,n) FOR_RE(i,n,0)

#define WHITE 1//（未訪問）
#define GRAY 2//（訪問）未だに訪問していない頂点への辺を持っている。スタックに退避。
#define BLACK 3//（訪問完了）未訪問への頂点への辺を持たない
#define N 100
#define INFTY (1 << 21) //10^21
int M[N][N];//隣接行列
int color[N];

//1個上から時計周り
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//上右下左
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
static const int NIL = -1;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> Vector;
typedef vector<Vector>	DVector;
int n;

//配列の表示
void printArray(int array[], int n){
    rep(i, n){
        if(i)   cout << " ";
        cout << array[i];
    }
    cout << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int m;
    cin >> n >> m;
    int a[m], b[m];
    bool inter[n + 1];
    rep(i, n + 1)   inter[i] = false;
    rep(i, m){
        cin >> a[i] >> b[i];
        if(b[i] == n){
            inter[a[i]] = true;
        }
    }
    
    rep(i, m){
        if(a[i] == 1){
            if(inter[b[i]]){
                cout << "POSSIBLE" << endl;
                return 0;
            }
        }
    }
    cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
#include<boost/variant.hpp>
using namespace std;
typedef long long ll;
typedef vector<boost::variant<bool, ll, int, string, double>> any;
template<typename T> inline void pr(const vector<T> &xs){
	for(int i=0; i<xs.size()-1; i++) cout<<xs[i]<<" ";
	(xs.empty()?cout:(cout<<xs[xs.size()-1]))<<endl;
}
template<typename T> inline void debug(const vector<T> &xs){
#ifdef DEBUG
	pr(xs);
#endif
}

int main(){
	int N;
	cin >> N;
	vector<int> W(N);
	for(int i=0; i<N; i++) cin >> W[i];

	int wsum = 0;
	for(int i=0; i<N; i++) wsum += W[i];
	int wcum = 0;
	int ans = 1e8;
	for(int i=0; i<N; i++){
		wcum += W[i];
		ans = min(ans, abs(wsum-2*wcum));
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256