akhauriyash/Code-Regression huggingface dataset:
// Copyright (C) 2017 __debug.

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>

#define x first
#define y second
#define MP std::make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using std::pair;
using std::vector;
using std::string;

typedef long long LL;
typedef pair<int, int> Pii;

const int oo = 0x3f3f3f3f;

template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
string procStatus()
{
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template<typename T> T read(T &x)
{
    int f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        f = (ch == '-' ? -1 : 1);
    for (x = 0; isdigit(ch); ch = getchar())
        x = 10 * x + ch - '0';
    return x *= f;
}
template<typename T> void write(T x)
{
    if (x == 0) {
        putchar('0');
        return;
    }
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    static char s[20];
    int top = 0;
    for (; x; x /= 10)
        s[++top] = x % 10 + '0';
    while (top)
        putchar(s[top--]);
}
// EOT

const int MAXN = 1e5 + 5;

int N, K;
int A[MAXN];

void input()
{
    read(N); read(K);
    for (int i = 1; i <= N; ++i) {
        read(A[i]);
    }
}

vector<int> G[MAXN];
int ans;

int calc(int u)
{
    int maxd = 0;
    for (int i = 0; i < SZ(G[u]); ++i) {
        int v = G[u][i];
        chkmax(maxd, calc(v));
    }
    if (A[u] != 1 && maxd + 1 == K) {
        ++ans;
        return 0;
    }
    return maxd + 1;
}

void solve()
{
    ans = (A[1] != 1);
    A[1] = 1;
    for (int i = 2; i <= N; ++i) {
        G[A[i]].push_back(i);
    }
    calc(1);
    printf("%d\n", ans);
}

int main()
{
#ifdef __DEBUG
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
#endif

    input();
    solve();

    return 0;
}

// 落木千山天远大，澄江一道月分明。
//     -- 黄庭坚《登快阁》


Measured memory_bytes: 12288
#include<iostream>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<algorithm>
    #include<string>
    #include<math.h>
    #include<sstream>
    #include<set>
    using namespace std;
    #define INF 10000000;

    int main(){
     int w,h,n,cnt = 0;
     cin >> w >> h >> n;
     vector<vector<int>> euclid(w,vector<int>(h));
     //cout << euclid[0][0] <<endl;
    
     
     int x[n],y[n],a[n];

     for(int i=0;i<n;i++){
       cin >> x[i] >> y[i] >> a[i];
      }


    //aの操作をしていく
     for(int i=0;i<n;i++){
       if(a[i] == 1){
         for(int j=0;j<x[i];j++){
           for(int k=0;k<h;k++){
             euclid[j][k]++;
           }
         }
       }
     
     
       if(a[i] == 2){
         for(int j=x[i];j<w;j++){
           for(int k=0;k<h;k++){
             euclid[j][k]++;
           }
         }
       }

       if(a[i] == 3){
         for(int j=0;j<w;j++){
           for(int k=0;k<y[i];k++){
             euclid[j][k]++;
        }
      }
     }
      if(a[i] == 4){
         for(int j=0;j<w;j++){
           for(int k=y[i];k<h;k++){
             euclid[j][k]++;
          }
         }

      }
     }

     //数える
      for(int i=0;i<w;i++){
        for(int j=0;j<h;j++){
          if(!euclid[i][j])cnt++;
          //cout << i << ',' << j << "   " << euclid[i][j] <<endl;
        }
      }
      cout << cnt <<endl;
    }
    
    

Measured memory_bytes: 256
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<deque>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define ll __int64
#define __int64 long long
#define P pair<ll,ll>
int n;
ll t[111111];
ll a,b;
ll ans=0;
int main(){
	cin>>n>>a>>b;
	rep(i,n)cin>>t[i];
	for(int i=1;i<n;i++)ans+=min(b,a*(t[i]-t[i-1]));
	cout<<ans<<endl;
	return 0;	
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int h = S/3600;
		int m = (S%3600)/60;
		int s = S%60;
		System.out.println(h+":"+m+":"+s);
	}
}

Measured memory_bytes: 26112
import java.util.*;

public class Main {
	int N;
	List<Long> A;
	long result = 0;
	long resultB = 0;

	private Main() {
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		A = new ArrayList<>(N);
		for (int i = 0; i < N; ++i) {
			A.add(in.nextLong());
		}
		in.close();
		Collections.sort(A);
	}

	private void calc() {
		Deque<Long> origs = new ArrayDeque<>(N);
		for (int i = 0; i < N; ++i) {
			origs.addLast(A.get(i));
		}

		Deque<Long> targets = new ArrayDeque<>(N);
		targets.addLast(origs.pollFirst());

		boolean getSmall = false;
		while (!origs.isEmpty()) {
			if (getSmall) {
				if (origs.size() != 1) {
					targets.addLast(origs.pollFirst());
					targets.addFirst(origs.pollFirst());
				} else {
					targets.addLast(origs.pollFirst());
				}
			} else {
				if (origs.size() != 1) {
					targets.addLast(origs.pollLast());
					targets.addFirst(origs.pollLast());
				} else {
					targets.addLast(origs.pollLast());
				}
			}
			getSmall = !getSmall;
		}

		long prev = targets.pollFirst();
		while (!targets.isEmpty()) {
			long current = targets.pollFirst();
			result += Math.abs(current - prev);
			prev = current;
		}
	}

	private void calcB() {
		Deque<Long> origs = new ArrayDeque<>(N);
		for (int i = 0; i < N; ++i) {
			origs.addLast(A.get(i));
		}

		Deque<Long> targets = new ArrayDeque<>(N);
		targets.addLast(origs.pollLast());

		boolean getSmall = true;
		while (!origs.isEmpty()) {
			if (getSmall) {
				if (origs.size() != 1) {
					targets.addLast(origs.pollFirst());
					targets.addFirst(origs.pollFirst());
				} else {
					targets.addLast(origs.pollFirst());
				}
			} else {
				if (origs.size() != 1) {
					targets.addLast(origs.pollLast());
					targets.addFirst(origs.pollLast());
				} else {
					targets.addLast(origs.pollLast());
				}
			}
			getSmall = !getSmall;
		}

		long prev = targets.pollFirst();
		while (!targets.isEmpty()) {
			long current = targets.pollFirst();
			resultB += Math.abs(current - prev);
			prev = current;
		}
	}

	private void show() {
		System.out.println(Math.max(result, resultB));
	}

	public static void main(String[] args) {
		Main ins = new Main();
		ins.calc();
		ins.calcB();
		ins.show();
	}
}

Measured memory_bytes: 63404
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, k;
  cin >> n >> k;
  
  int a = 1;
  for (int i = 0; i < n; i++) {
    if (a * 2 < a + k)
      a *= 2;
    
    else
      a += k;
  }
  
  cout << a << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;

int main()
{
    int s;
    ll i=1;
    vector<bool> a(100000);
    cin>>s;
    a[s]=true;
    while(1)
    {
        ++i;
        if(s%2==0)
            s/=2;
        else
            s=3*s+1;
        if(a[s])
            break;
        a[s]=true;
    }
    cout<<i<<endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
using namespace std;
char c;int b[1000005],a[1000005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	FOR(i,1,n){
		cin>>c;
		b[i]=c-'0';
	}
	rep(i,1,n)a[i]=abs(b[i+1]-b[i]);
	n--;
	bool f=0;
	FOR(i,1,n){
		if(a[i]==1){
			f=1;break;
		}
	}
	int ans;
	if(!f){
		ans=2;
		FOR(i,1,n){
			if(a[i]==2)a[i]=1;
		}
	}else{
		ans=1;
		FOR(i,1,n){
			if(a[i]==2)a[i]=0;
		}	
	}
	bool anf=a[1];
	FOR(i,2,n){
		if(((i-1)&(n-1))==i-1)anf^=a[i];
	}
	if(anf){
		cout<<ans;
	}else cout<<0;
	RE 0;
}




Measured memory_bytes: 8064
#include<iostream>

using namespace std;

int main(){
  int n,x,t;
  cin >> n >> x >> t;
  
  if(n % x == 0){
    cout << t * (n/x) << endl;
  }
  else{
    cout << t * (n / x + 1) << endl;
  }
  return 0;
}

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

int main() {
    double d, t, s;
    cin >> d >> t >> s;
    double ans = d / s;
    if (ans <= t) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3736
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
int main(){
    char s[201],t[101],i,n,ans=0;
    scanf("%s%s",s,t);
    n=strlen(s);
    for(i=0;i<n;i++){
        s[n+i]=s[i];
    }
    for(i=0;i<n;i++){
        if(strncmp(s+i,t,n)==0) ans=1;
    }
    if(ans==1) printf("Yes");
    else printf("No");
    return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"

#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,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(V),v.end()));
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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

typedef long long ll;
using namespace std;


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, m;
	cin >> n >> m;
	ll left = 0, right = 10000000000000ll;
	ll mid;
	while (right > left+1) {
		 mid = (right - left) / 2 + left;
		if (n >= mid) {
			if (m >= 2 * mid) left = mid;
			else right = mid;
		}
		else {
			if (m - (mid - n) * 2 >= 2 * mid) left = mid;
			else right = mid;
		}
	}
	cout << left << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define _GLIBCXX_DEBUG
using namespace std;
using P = pair<int,int>;
typedef long long ll;


int main() {

    int n,k;
    cin>>n>>k;

    double ret=0;
    for(int i=1;i<=n;i++){
        double tmp=1.0/n;
        int now=i;
        while(now<k){
            now*=2;
            tmp/=2;
        }
        ret+=tmp;
    }

    printf("%.12f\n",ret);

 return 0;
}

Measured memory_bytes: 256
import sys

input = lambda: sys.stdin.readline().rstrip()



def solve():

    s = input()

    ans = 0
    if s == 'SUN':
        ans = 7
    elif s == 'MON':
        ans = 6
    elif s == 'TUE':
        ans = 5
    elif s == 'WED':
        ans = 4
    elif s == 'THU':
        ans = 3
    elif s == 'FRI':
        ans = 2
    elif s == 'SAT':
        ans = 1

    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 2940
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, M, X, Y, Z;
int Group[int(1e5 + 5)];

int Unite(){
  int GX = Group[X], GY = Group[Y];
  while (GX != Group[GX]) GX = Group[GX];
  while (GY != Group[GY]) GY = Group[GY];

  int G = min(GX, GY);
  Group[max(GX, GY)] = G;
  Group[X] = G; Group[Y] = G;
  return 0;
}

int main(){
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; i++) Group[i] = i;

  for (int i = 0; i < M; i++){
    scanf("%d%d%d", &X, &Y, &Z);
    Unite();
  }

  int ans = 0;
  for (int i = 1; i <= N; i++){
    int Gi = Group[i];
    while (Gi != Group[Gi]) Gi = Group[Gi];
    if (i == Gi) ans++;
  }
  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 4216
S = list(input())

L = len(S)

plus = [False] * (L-1)

sum = 0

for n in range(1 << (L-1)):
    for i in range(L-1):
        if (n >> i) % 2:
            plus[i] = True
        else:
            plus[i] = False

    stack = []
    for i in range(L):
        stack.append(S[i])
        if i == L - 1:
            sum += int("".join(stack))
            stack = []
        elif plus[i]:
            sum += int("".join(stack))
            stack = []

print(sum)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main(void){
 
    unsigned int A, B, C;
    std::cin >> A >> B >> C;
    if(A < B){
        if(A < C && C < B){
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }else if(B < A){
        if(A > C && C > B){
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }
    
    std::cout << "No" << std::endl;
    return 0;
}


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


public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] p = sc.nextIntArray(n);
        int left = 0, right = 0;
        double cur = 0;
        while (right < k)
            cur += getProp(p[right++]);
        double ans = cur;
        while (right < n) {
            cur -= getProp(p[left++]);
            cur += getProp(p[right++]);
            ans = Math.max(ans, cur);
        }
        out.println(ans);
        out.flush();
        out.close();
    }

    static double getProp(int n) {
        return (1.0 * n * (n + 1)) / (2 * n);
    }


    static class Scanner {

        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }

        boolean ready() throws IOException {
            return br.ready();
        }


        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

        public Long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }


        public Integer[] nextIntegerArray(int n) throws IOException {
            Integer[] a = new Integer[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public double[] nextDoubleArray(int n) throws IOException {
            double[] ans = new double[n];
            for (int i = 0; i < n; i++)
                ans[i] = nextDouble();
            return ans;
        }

        public short nextShort() throws IOException {
            return Short.parseShort(next());
        }

    }

}

Measured memory_bytes: 44048
N = int(input())
counter = [51]*26
for i in range(N):
    s = input()
    for j in range(97,123):
        counter[j-97] = min(counter[j-97],s.count(chr(j)))
ps = ''
for i in range(26):
    ps += chr(i+97)*counter[i]
print(ps)

Measured memory_bytes: 72320
/*suri_kumkaran*/

#include <bits/stdc++.h>

using namespace std;

#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define MP make_pair
#define EB emplace_back
#define endl "\n"
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long

typedef long long int64;
typedef vector<int> VI64;
typedef vector<pair<int,int>> VII64;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;


int32_t main()
{
	IOS;
	int T=1;
	//cin>>T;
	while(T--)
	{	
		int n,i,u,v;
		cin>>n;
		map<int,int> mp;
		for(i=2;i<=n;i++)
		{
			cin>>u;
			mp[u]++;
		}
		for(i=1;i<=n;i++)
		{
			cout<<mp[i]<<endl;
		}
	}

	return 0;
}

Measured memory_bytes: 16164
import Data.List

solve :: [[Int]] -> [(Int,Int)] ->	[Int]
solve _ [] = []
solve l ((a,b):xs)
  | a == m l = b :	solve l xs
  | otherwise = solve l xs
    where m = maximum . map length

main = do
  l <- fmap (group . sort . map (read :: String -> Int) . lines) getContents
  putStr $ unlines $ map show $ solve l $ zip (map length l) (map head l)


Measured memory_bytes: 4104
#include <stdio.h>

 int main(void)
 {
 int n=0,i=0,count=0;
 int a,b=0;
 
 scanf("%d %d %d",&a,&b,&n);

 

 for(i=1;i<=n;i++){
 if(n%i==0){
 if(a<=i && b>=i){
 count++;
 }
 }
 }
 
 printf("%d\n",count);
 

 return 0;
 }

Measured memory_bytes: 596
#include <stdio.h>
#include <string.h>

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

    int len = strlen(s);

    int i,count = 0;
    for (i = 1; i < len; i++)
    {
        if(s[i - 1] != s[i])count++;
    }
    printf("%d",count);
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    const int array_num = 3;
    int a[array_num];
    int product = 1;

    //cout << "Input 3 integers=>" << endl;
    cin >> a[0] >> a[1] >> a[2];

    //judge if the input integers are less than 10;
    for(int i = 0; i < array_num; i++){
        if(a[i] < 1 || 10 < a[i]){
            cout << "NO" << endl;
            return 0;
        }
    }


    for(int i = 0; i < array_num; i++) product *= a[i];
    if(175 == product){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
// #define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
//using namespace __gnu_pbds;
#define int long long int
#define pb push_back
#define vec vector<int>
#define fo(i, n) for (int i = 0; i < n; i++)
#define foo(i, a, b) for (int i = a; i < b; i++)
#define mp make_pair
#define deb(x) cout << #x << " --> " << x << endl;
#define deb1a(v) cout << #v << "--->" << endl; for (auto it : v)  cout << it << " "; cout << endl;
#define deb2a(v) cout << #v << "--->" << endl;for (auto it:v){for(auto it1 : it){cout << it1 << " ";}cout<< endl;}
#define deb3a(v) cout << #v << "-->" << endl; for(auto it:v){cout << it.fi << " " << it.se << endl;}
#define mod 29996224275833
#define so(v) sort(v.begin(),v.end())
#define fi first
#define se second
#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
int power(int x, unsigned int y, int p){ int res = 1;x = x % p;while (y > 0)  { if (y & 1)res = (res*x) % p;y = y>>1;  x = (x*x)% p;} return res;}
int mI(int a, int m)  {return power(a, m - 2, m);}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    vec h(n);
    fo(i, n)
            cin >>
        h[i];
    vector<set<int>> g(n);
    fo(i,m){
        int x, y;
        cin >> x>>y;
        x--;
        y--;
        g[x].insert(h[y]);
        g[y].insert(h[x]);
    }
    int ans = 0;
    fo(i,n){
        if(g[i].size()==0){
            ans++;
        }
        else{
            auto it = g[i].end();
            it--;
            if(h[i]>*it)
                ans++;
        }
    }
    cout << ans;
}
    


Measured memory_bytes: 17980
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define rep2(i,a,b) for (ll i = (a); i < (b); ++i)

#define INF (1<<18)



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

    int l = str.length();
    int s[l];
    rep(i,l) s[i] = str[l-i-1]-'0';


    ll ans = 0; 
    ans += s[0]*(1<<l-1);

    rep(i,1 << l-1 ){
        int b = -1;
        rep(j,l-1){
            if((i >> j)&1) b = j;
            ans += s[j+1]*pow(10,j-b);
        }
    }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define endl "\n"
#define speed() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sz(x) (int)(x).size()
#define _USE_MATH_DEFINES
using namespace std;
typedef long long int lli;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
    speed();
    string s, t; cin >> s >> t;
    bool ans = false;
    rep(i, 0, s.size()) {
        if (s == t) {
            ans = true;
            break;
        }
        s = s.back() + s.substr(0, s.size()-1);
    }
    ans ? cout << "Yes" : cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define rep(i,n) for(int i=0; i<(n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1001001001; // > 10^9
const int MOD = (int)1e9 + 7;
const ll INFLL = 1001001001001001001;  // > 10^18
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {

  int h,n; cin >>h>>n;
  vector<int> a(n); rep(i,n) cin >> a[i];

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

  if (sol >= h) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  } 
  
  return 0;
}




Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define ll long long
const int MOD = 1000000007;

int main()
{
    int n = 0;
    scanf("%d", &n);
    n++;
    n /= 2;
    printf("%d",n);
    return 0;
}


Measured memory_bytes: 128
def main2():
    n, k = list(map(int, input().split()))
    monsters = list(map(int, input().split()))
    monsters.sort(reverse=True)

    for i in range(k):
        if i >= len(monsters):
            break
        monsters[i] = 0
    print(sum(monsters))

if __name__ == '__main__':
    main2()

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

using lint = int64_t;
#define bit(n) ((lint)1 << n);
const int INF = 1e9;
const lint LINF = 1e18;

const lint MOD = 1e9 + 7;
// const lint MOD = 998244353;

class IoSetup {
    public:
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(12);
        cerr << fixed << setprecision(12);
    }
} iosetup;

int main() {
    lint n;
    cin >> n;
    vector<lint> a(4), b(4);
    for (int i = 1; i <= 3; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= 3; i++) {
        cin >> b[i];
    }

    vector<lint> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i] = i;
        for (int j = 1; j <= 3; j++) {
            if (i - a[j] >= 0) {
                dp[i] = max(dp[i], dp[i - a[j]] + b[j]);
            }
        }
    }

    lint m = dp[n];
    vector<lint> dp2(m + 1);
    for (int i = 1; i <= m; i++) {
        dp2[i] = i;
        for (int j = 1; j <= 3; j++) {
            if (i - b[j] >= 0) {
                dp2[i] = max(dp2[i], dp2[i - b[j]] + a[j]);
            }
        }
    }

    cout << dp2[m] << endl;
    return 0;
}

Measured memory_bytes: 195584
N,x=int(input()),0
s=list(map(int,input().split()))
for j in s:
    x+=j
x=x-s[0]*2
ans=abs(x)
for k in range(1,N-1):
    x=x-s[k]*2
    ans=min(ans,abs(x))
print(ans)    
    

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

using namespace std;

typedef long long ll;

const int MAX_N = 1e5 + 5;

int N;
int a[MAX_N];

int main()
{
  //freopen("in.txt", "r", stdin);
  cin >> N;
  for (int i = 0; i < N; ++i) scanf("%d", &a[i]);
  sort(a, a + N);
  int ans = 1;
  for (int i = 0; i < N; ++i) {
    int tn = a[i], tmp;
    tmp = upper_bound(a, a + N, tn + 1) - lower_bound(a, a + N, tn - 1);
    ans = max(ans, tmp);
    tn = a[i] - 1;
    tmp = upper_bound(a, a + N, tn + 1) - lower_bound(a, a + N, tn - 1);
    ans = max(ans, tmp);
    tn = a[i] + 1;
    tmp = upper_bound(a, a + N, tn + 1) - lower_bound(a, a + N, tn - 1);
    ans = max(ans, tmp);
  }
  printf("%d\n", ans);
  return 0;
}


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

int binarySearch(int*,int);

int n;
  
int main(){
  int i,q,*S,*T,C=0;
  scanf("%d",&n);
  S=(int*)malloc(sizeof(int)*n);
  for(i=0;i<n;i++)
    scanf("%d",&S[i]);
  scanf("%d",&q);
  T=(int*)malloc(sizeof(int)*(q+1));
  for(i=0;i<q;i++)
    scanf("%d",&T[i]);
  for(i=0;i<q;i++){
    C+=binarySearch(S,T[i]);
  }
  printf("%d\n",C);
  return 0;
}

int binarySearch(int *S,int key){
  int left=0;
  int right;
  int mid;
  right=n;
  while(left<right){
    mid=(left+right)/2;
    if(key==S[mid])
      return 1;
    if(key>S[mid])
      left=mid+1;
    else if(key<S[mid])
      right=mid;
  }
  return 0;
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

// snukeさんのmodint
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

// mint N;

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

// combination c(N);
// mint ans = c(N,n);
// cout << ans.x << endl;
// Nとnはll型(mintではない)
// -------------------------------------------------------------


int main(){
  ll X,Y;
  cin >> X >> Y;
  if((X+Y)%3 != 0){
    cout << 0 << endl;
    return 0;
  }
  ll num = (X+Y)/3;
  X -= num;
  Y -= num;
  combination c(X+Y);
  mint ans = c(X+Y,X);
  cout << ans.x << endl;
  return 0;
}

Measured memory_bytes: 10624
#include <cstdio>
#include <iostream>
using namespace std;
int main(void) {
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int K, P;
		cin >> K >> P;
		int ans = K % P;
		if (ans == 0) {
			ans += P;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1160
package main

import "fmt"

func main() {
	var s, t, u string
	var a, b int
	fmt.Scan(&s, &t)
	fmt.Scan(&a, &b)
	fmt.Scan(&u)

	if u == s{
		a--
	}else if u == t{
		b--
	}

	fmt.Println(a, b)
}

Measured memory_bytes: 1768
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n][3];
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	}
	vector<vector<int>> ans(n,vector<int> (3));
	ans[0][0]=a[0][0];
	ans[0][1]=a[0][1];
	ans[0][2]=a[0][2];
	for(int i=1;i<n;i++){
		ans[i][0]=a[i][0]+max(ans[i-1][1],ans[i-1][2]);
		ans[i][1]=a[i][1]+max(ans[i-1][0],ans[i-1][2]);
		ans[i][2]=a[i][2]+max(ans[i-1][0],ans[i-1][1]);	
		
	}
	int x=max(ans[n-1][0],ans[n-1][1]);
	cout<<max(ans[n-1][2],x);
}

Measured memory_bytes: 9864
import collections
input = raw_input
n = int(input())
nums = map(int, input().split(" "))

counter = collections.Counter(nums)
values = counter.keys()
all_out = 0
for val, num in counter.items():
    if num == 1:
        continue
    else:
        all_out += num * (num-1) // 2

outs = {}
for val, num in counter.items():
    if num == 1:
        outs[val] = all_out
    else:
        outs[val] = all_out - (num-1)

for num in nums:
    print(outs[num])

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

int main() {
  int N;
  cin >> N;
  vector<int>data(N);
  int sum=0;
  for (int i=0; i<N; i++) {
    cin >> data.at(i);
  }
  for (int i=0; i<((N+1)/2); i++) {
    if( (data.at(2*i))%2 == 1) {
      sum++;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
#include <unordered_map>
#include <fstream>
#include <time.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef pair<int,int> pii;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(int i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 2020000;
ll dy[8] = {1,-1,0,0,1,-1,1,-1};
ll dx[8] = {0,0,1,-1,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T> inline void print(T &a){
    rep(i,a.size()) cout << a[i] << " ";
    cout << "\n";
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int main(){
	int n; cin >> n;
	vl a(n); vc s(n);
	rep(i,n){
		cin >> a[i];
		if(i < n-1) cin >> s[i+1];
	}
	s[0] = '+';
	vvl dp(n+1,vl(3,-linf));
	dp[0][0] = 0;
	rep(i,n){
		if(s[i] == '+'){
			chmax(dp[i+1][0], dp[i][0] + a[i]);
			chmax(dp[i+1][1], dp[i][1] - a[i]);
			chmax(dp[i+1][2], dp[i][2] + a[i]);
			chmax(dp[i+1][0], dp[i][1] - a[i]);
			chmax(dp[i+1][1], dp[i][2] + a[i]);
		}else{
			chmax(dp[i+1][2], dp[i][1] + a[i]);
			chmax(dp[i+1][1], dp[i][0] - a[i]);
			chmax(dp[i+1][0], dp[i][0] - a[i]);
			chmax(dp[i+1][1], dp[i][1] + a[i]);
			chmax(dp[i+1][2], dp[i][2] - a[i]);
		}
	}
	cout << max({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
}

Measured memory_bytes: 9596
//Link : https://atcoder.jp/contests/abc150/tasks/abc150_f

#include <bits/stdc++.h>

using namespace std;
#define ll long long

#define N 4000005
ll in[N],tmp[N];

int a[N],b[N];
int table[N];

bool isTrue(int *p1,int *p2,int pos,int match) {
  if( (p1[pos+match]^p2[match] ) == (p1[pos]^p2[0])) {
    return true;
  } else {
    return false;
  }
}
void makeTable(int n) {
  int pos = 1,match = 0;
  while(pos+match<n) {
    if(isTrue(b,b,pos,match)) {
      ++match;
      table[pos+match-1] = match;
    } else {
      if(match==0) {
        ++pos;
      } else {
        pos += match- table[match-1];
        match = table[match-1];
      }
    }
  }
}
vector<pair<int,int> > getMatch(int n) {
  vector<pair<int,int> > ret;
  int pos=0,match = 0;
  while(pos<n) {
    if(match!=n && isTrue(a,b,pos,match)) {
      ++match;
      if(match==n) {
        ret.push_back(make_pair(pos, a[pos]^b[0]));
      }
    } else {
      if(match==0) {
        ++pos;
      } else {
        pos += match- table[match-1];
        match = table[match-1];
      }
    }
  }
  return ret;
}
void solve() {
  int n;scanf("%d ", &n);
  for(int i=0;i<n;++i) {
    scanf("%d ", &a[i]);
    a[i+n] = a[i];
  }
  for(int i=0;i<n;++i) {
    scanf("%d ", &b[i]);
  }
  makeTable(n);
  vector<pair<int,int> > ret = getMatch(n);
  for(int i=0;i<ret.size();++i) {
    printf("%d %d\n", ret[i].first,ret[i].second);
  }
}
int main() {
    //freopen("input.txt","r",stdin);
    solve();
    return 0;
}


Measured memory_bytes: 14064
#include <bits/stdc++.h>
#define int long long
#define multi_test true and false
#define all(a) (a).begin(),(a).end()
using namespace std;

void dfs(int v,vector<bool>& bani,vector<int>& path,int arr[]){
    if(bani[v]){
        path.push_back(v);
        return ;
    }
    bani[v] = true;
    path.push_back(v);
    dfs(arr[v],bani,path,arr);
}

void solve(){
    int n , k ;
    cin >> n >> k ;
    int arr[n];
    for(int& i : arr)
        cin >> i ;

    for(int& i : arr)
        i--;

    vector<int>path;
    vector<bool>bani(n,false);
    dfs(0,bani,path,arr);

    int index = -1;
    for(int i=0;i<(int)path.size();i++){
        if(path[i] == path.back()){
            index = i;
            break;
        }
    }
    if(k < (int)path.size()){
        cout << path[k] + 1 << endl; 
        return ;
    }
    vector<int>new_path(path.begin()+index,path.end());
    // for(int i : new_path) cout << i << ' ';
    // cout << endl ;
    k -= index; 
    n = (int)new_path.size()-1;
    k = k%n ;
//    cout << k << ' ' << n << endl ;
    cout << new_path[k] + 1 << endl ;
}

signed main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        int test=1;
        if(multi_test) cin>>test;
        while(test--)
            solve();

        return 0;
}


Measured memory_bytes: 15680
// SeeAlso: https://atcoder.jp/contests/abc063/tasks/abc063_a

#include <bits/stdc++.h>

using namespace std;

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

#define MAX 100000
#define NIL -1
#define MOD 1000000007

typedef int _loop_int;
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// 最大公約数
inline constexpr ll gcd(ll a,ll b){if(!a||!b)return 0;while(b){ll c=b;b=a%b;a=c;}return a;}
// 最小公倍数
inline constexpr ll lcm(ll a,ll b){if(!a||!b)return 0;return a*b/gcd(a,b);}

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << setprecision(12) << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }


int main() {
    int a,b;
    cin >> a >> b;
    if(a+b>=10) {
        print("error");
    } else {
        print(a+b);
    }
}


Measured memory_bytes: 384
H, W, A, B = map(int, input().split())


def f():
    if H // 2 < B or W // 2 < A:
        return False, None

    s0 = "1" * A + "0" * (W - A)
    s1 = "0" * A + "1" * (W - A)

    F = [s0] * B + [s1] * (H - B)
    return True, F


can, field = f()
if can:
    for f in field:
        print(f)
else:
    print("No")


Measured memory_bytes: 3956
#include <iostream>
#include <map>
#include <string.h>
#include <vector>

using namespace std;

#define int_ int64_t
#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>

const int N=710,M=N*N;
int n,m;
int color[N];
bool g[N][N];
bool dp[N][N];

bool dfs(int x,int c,int& a,int &b) {
    color[x]=c;
    if (c==0) a++;
    else b++;
    bool res=1;
    for (int y=1;y<=n;y++) {
        if (x!=y&&!g[x][y]) {
            if (color[y]!=-1) {
                if (color[y]==color[x]) return false;
            } else {
                res&=dfs(y,1-c,a,b);
            }
        }
    }
    return res;
}

int calc(int x) { return x*(x-1)/2; }

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u][v]=g[v][u]=1;
    }
    memset(color,-1,sizeof(color));
    vector<int> taka,hashi;
    for (int i=1;i<=n;i++) {
        int p=0,q=0;
        if (color[i]==-1) {
            bool res=dfs(i,0,p,q);
            if (!res) {
                printf("-1\n");
                return 0;
            }
            taka.pb(p),hashi.pb(q);
        }
    }
    dp[0][0]=1;
    for (int i=0;i<taka.size();i++) {
        for (int j=0;j<=n;j++) {
            if (j>=taka[i]) dp[i+1][j]|=dp[i][j-taka[i]];
            if (j>=hashi[i]) dp[i+1][j]|=dp[i][j-hashi[i]];
        }
    }
    int ans=INF;
    for (int i=1;i<=n;i++) {
        if (dp[taka.size()][i]) {
            ans=min(ans,calc(i)+calc(n-i));
        }
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 1280
#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;

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

    double rad = C * M_PI / 180.0;

    double h = b * sin(rad);
    double S = a * h / 2.0;
    double L = a + b + sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(rad));
    cout << fixed << setprecision(7) << S << endl;
    cout << fixed << setprecision(7) << L << endl;
    cout << fixed << setprecision(7) << h << endl;

    return 0;
}

Measured memory_bytes: 1284
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()

int N;
ll A, B;
ll S[100010];
ll D[100010][2];
ll P[100010];

const ll MOD = 1e9 + 7;

void solve(){
	scanf("%d%lld%lld", &N, &A, &B);
	for(int i=1;i<=N;i++)scanf("%lld", S+i);
	if(A > B)swap(A, B);
	S[++N] = 3e18;
	D[0][0] = 1;
	D[1][0] = 1; D[1][1] = 0;
	P[0] = 1; P[1] = 2;
	int pre = -1;
	for(int i=2;i<=N;i++){
		if(S[i] - S[i-1] >= B)D[i][0] = (D[i-1][0] + D[i-1][1]) % MOD;
		int idx = min(i-2, (int)(upper_bound(S+1, S+1+N, S[i] - B) - S - 1));
		if(pre == -1 || idx >= pre){
			D[i][1] = P[idx] - (pre == -1 ? 0 : P[pre-1]);
			D[i][1] = (D[i][1] + MOD) % MOD;
		}
		if(S[i] - S[i-1] < A)pre = i - 1;
		P[i] = P[i-1];
		if(S[i+1] - S[i-1] >= A)P[i] = (P[i] + D[i][1]) % MOD;
		P[i] = (P[i] + D[i][0]) % MOD;
	}
	printf("%lld\n", (D[N][0] + D[N][1]) % MOD);
}

int main(){
	int Tc = 1; // scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Measured memory_bytes: 3328
//
// Created by tac on 2016/10/25.
//


#include <cstdlib>
#include <iostream>

namespace {

const int N_SIZE = 100;
int a[N_SIZE];

void print_array(int a[], int n) {
    for (int i = 0; i < n; ++i) {
        if (i > 0) {
            std::cout << " ";
        }
        std::cout << a[i];
    }
    std::cout << std::endl;
    return;
}

//1 selectionSort(A, N) // N??????????´??????????0-?????????????????????A
//2   for i ??? 0 ?????? N-1 ?????§
//3     minj = i
//4     for j ??? i ?????? N-1 ?????§
//5       if A[j] < A[minj]
//6         minj = j
//7     A[i] ??¨ A[minj] ?????????
void sort_array(int a[], int n) {
    int count = 0;
    int minj;
    for (int i = 0; i < n; ++i) {
        minj = i;
        for (int j = i; j < n; ++j) {
            if (a[j] < a[minj]) {
                minj = j;
            }
        }
        std::swap(a[i], a[minj]);
        if (i != minj) {
            ++count;
        }
    }

    print_array(a, n);
    std::cout << count << std::endl;
    return;
}

}

int main() {
    int n;

    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    sort_array(a, n);

    return EXIT_SUCCESS;
}

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

int main()
{
  int n, count = 0;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for(int i = 1; i < n - 1; i++) {
  if(((a[i - 1] < a[i]) && (a[i] < a[i + 1])) || ((a[i - 1] > a[i]) && (a[i] > a[i + 1]))) count++;
  }
  
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define MAX 10000
#define NIL -1

struct node{
  int parent,left,right;

};
struct node T[MAX];
int D[MAX],n,H[MAX];

void depth(int,int);
int height(int);
int get(int);
void print(int);


int main(){
  int i,id,l,r,rt=0;

  scanf("%d",&n);
  if(n<1||n>25) exit(1);

  for(i=0;i<n;i++)
    T[i].parent=NIL;
  for(i=0;i<n;i++){
    scanf("%d%d%d",&id,&l,&r);
    T[id].left=l;
    T[id].right=r;
    if(l!=NIL) T[l].parent=id;
    if(r!=NIL) T[r].parent=id;

  }
  for(i=0;i<n;i++)
    if(T[i].parent == NIL) rt=i;
  depth(rt,0);
  height(rt);

  for(i=0;i<n;i++) print(i);
  return 0;
}

void depth(int u,int dep){
  if(u == NIL) return;
  D[u] = dep;
  depth(T[u].left,dep+1);
  depth(T[u].right,dep+1);

}

int height(int u){
  int hl=0,hr=0;
  if(T[u].left!=NIL)
    hl= height(T[u].left)+1;
  if(T[u].right!=NIL)
    hr= height(T[u].right)+1;

  if(hl>hr) H[u]=hl;
  else H[u]=hr;
  return H[u];
}

int get(int u){


  if(T[u].parent==NIL) return NIL;
  if(T[T[u].parent].left != u&&T[T[u].parent].left !=NIL)
    return T[T[u].parent].left;
  if(T[T[u].parent].right != u&&T[T[u].parent].right !=NIL)
    return T[T[u].parent].right;
  return NIL;


}

void print(int u){
  int d;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("sibling = %d, ",get(u));
  d=0;
  if(T[u].left!=NIL) d++;
  if(T[u].right!=NIL) d++;
  printf("degree = %d, ",d);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);

  if(T[u].parent==NIL){
    printf("root\n");

  }else if(T[u].left ==NIL&&T[u].right==NIL){
    printf("leaf\n");
  }else{
    printf("internal node\n");

  }
	 
}



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




int main () {

	int h,w;
	int i,j;
	cin>>h>>w;

	vector<vector<char>> cell(h,vector<char>(w));

//input

	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			cin>>cell.at(i).at(j);
		}
	}

//comp==================================
int h_out=h,w_out=w;

//width--------------
bool jdg;
j=0;
while (j<w_out) {

	jdg=true;
	i=0;
	while (i<h) {

		if (cell.at(i).at(j)=='#'){
			jdg=false;
			break;

		}
		i++;
	}

	if (jdg==true) {
		//圧縮
		for (int n=j;n<w_out-1;n++) {
			for (int m=0;m<h_out;m++){

			cell.at(m).at(n)=cell.at(m).at(n+1);

			}
		}

		w_out--;
		j--;//列ずれにより、再度同列検査。
	}
	j++;
}

//hight-------------
i=0;
while (i<h_out) {
	j=0;
	jdg=true;
	while (j<w_out) {
		if (cell.at(i).at(j)=='#') {

			jdg=false;
			break;
		}
		j++;
	}

	if (jdg==true) {
		//ずらし
		for (int m=i;m<h_out-1;m++) {
			for (int n=0;n<w_out;n++) {

				cell.at(m).at(n)=cell.at(m+1).at(n);

			}
		}
		h_out--;
		i--;
	}
	i++;
}

//output============================
for (i=0;i<h_out;i++) {

	for (j=0;j<w_out;j++) {

		cout<<cell.at(i).at(j);
	}
	cout<<endl;
}
}//main










Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
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


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


	ll N;
	scanf("%lld", &N);

	int sq = sqrt(N);
	ll saishou = 1e18;
	for (int i = sq; i >= 1; i--) {
		if ((ll)((double)N / i) * i == N) {
			printf("%lld", N / i + i - 2);
			return 0;
		}
	}

	Would you please return 0;
}

Measured memory_bytes: 128
from numba import jit
@jit
def main():
  n,k=map(int,input().split())
  p=list(map(int,input().split()))
  c=list(map(int,input().split()))
  ans=-10**18
  for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1!=i: #ループ部分
      start=p[start]-1
      count+=1
      val+=c[start]
    start=i
    if val>0:
      a=(k//count-1)*val #一周目はループのどの部分から始めるのが最適かわからないので
      ans=max(a,ans)
      num=count+k%count
    else:
      a=0
      num=min(k,count)
    for _ in range(num):
      start=p[start]-1
      a+=c[start]
      ans=max(a,ans)
  print(ans)
main()


Measured memory_bytes: 119908
n = gets.to_i
c = []
s = []
f = []
for i in 0...(n - 1) do
  c[i], s[i], f[i] = gets.split.map(&:to_i)
end
for j in 0...n do
  x = 0
  for i in j...(n - 1) do
    r = x % f[i]
    x += f[i] - r if r > 0
    x = [x, s[i]].max
    x += c[i]
  end
  puts x
end


Measured memory_bytes: 3836