akhauriyash/Code-Regression huggingface dataset:
//gauravsinghh
#include<bits/stdc++.h>
using namespace std;

using ll = long long int;
using bigint = int64_t;

#define pll pair<ll, ll>
#define vll vector<ll>
#define vpll vector<pll>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define bitcount __builtin_popcount
#define endl "\n"
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define deb(x) cout << #x << " = " << x << endl;
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(ll i = a; i <= b; i++)
#define ffo(i, a, b) for(ll i = a; i >= b; i--)
#define ffi(i,a,b,c) for(ll i = a ; i <= b ; i += c)
#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int MOD = 1000000007;

void io_set() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

void solve() {
    ll n, k;
    cin >> n >> k;
    cout << floor(log2(n)/log2(k))+1 << endl;
}

int main() {
    IOS;
    //io_set();
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}


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

int main(){
    string s,t;
    cin >>s >>t;
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    reverse(t.begin(),t.end());

    if(s<t)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
// -----------------------------------
// author   : MatsuTaku
// country  : Japan
// created  : 09/20/20 21:00:19
// -----------------------------------

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;

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

  int n; cin>>n;
  struct City {
    int x,y,i;
  };
  vector<City> C(n);
  for (int i = 0; i < n; i++) {
    int a,b; cin>>a>>b;
    C[i] = {a,b,i};
  }

  sort(C.begin(), C.end(), [](auto l, auto r) {return l.x<r.x;});
  atcoder::dsu cdsu(n);
  map<int, int> ss;
  for (auto c:C) {
    auto th = ss.upper_bound(c.y);
    if (th == ss.begin()) {
      ss[c.y] = c.i;
    } else {
      for (auto it = ss.begin(); it != th; ++it) {
        cdsu.merge(it->second, c.i);
      }
      ss.erase(next(ss.begin()), th);
    }
  }

  for (int i = 0; i < n; i++) {
    cout << cdsu.size(i) << endl;
  }

  return 0;
}


Measured memory_bytes: 11016
#include <bits/stdc++.h>
using namespace std;;
#define rep(i, n) for(int i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define INF 1<<30
#define LINF 1LL<<62
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
const int MOD = 1000000007;
 
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll m,d,mm,dd;
  cin >> m >> d >> mm >> dd;
  if(m!=mm){
    cout << 1 << endl;
  }else{
    cout << 0 << endl;
  }
}

Measured memory_bytes: 384
import math
from functools import reduce
import itertools

def gcd(*numbers):
	return reduce(math.gcd, *numbers)

limit_num = int(input())
result_list = []
for num in itertools.product(range(1, limit_num + 1), repeat=3):
	result_list.append(gcd(num))

print(sum(result_list))


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

int main(){
    int n;
    cin>>n;
    for(int i=1; i<10; i++){
        for(int j=1; j<10; j++){
            if(i*j==n){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

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

using namespace std;
using ll = long long;
constexpr ll mod = 1e9+7;
constexpr ll md = mod;
constexpr ll inf = 1e15;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> s(n),t(m);
    for(auto & a : s) cin>>a;
    for(auto & a : t) cin>>a;
    vector<vector<ll>> dp(n+1,vector<ll>(m+1));
    auto sum = dp;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j)if(i==0 or j==0)sum[i][j] = 1;
    }
    ll ret = 1ll;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(s[i] == t[j]){
                dp[i+1][j+1] = (sum[i][j])%mod;
                ret += dp[i+1][j+1];
            }
            sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] + mod - sum[i][j] + dp[i+1][j+1])%mod;
        }
    }
    cout << ret%mod << endl;
    return 0;
}



Measured memory_bytes: 62976
def main():
    N, A, B = (int(i) for i in input().split())
    X = [int(i) for i in input().split()]
    diff = [(X[i+1] - X[i])*A if (X[i+1] - X[i])
            * A < B else B for i in range(N-1)]
    print(sum(diff))


if __name__ == '__main__':
    main()


Measured memory_bytes: 63640
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

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

    String s = sc.nextLine();
    char[] cs = s.toCharArray();

    List<Character> rud = Arrays.asList('R', 'U', 'D');
    List<Character> lud = Arrays.asList('L', 'U', 'D');

    boolean isEasy = true;
    for (int i = 0; i < cs.length; i++) {
        if ((i % 2 == 0 && !rud.contains(cs[i]))
            ||
            (i % 2 != 0 && !lud.contains(cs[i]))) {
            isEasy = false;
            break;
        };
    }

    System.out.println(isEasy ? "Yes" : "No");
  }
}

Measured memory_bytes: 23124
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;

//#define int long long
#define rep(i, n) for(long long i = 0; i < (n); i++)

const int INF = 2000000000; //2e9
const long long INF2 = 1000000000000000000; //1e18
const long double pi = acos(-1);

const int MOD = 1000000007; //1e9 + 7
//const int MOD = 1000000009; //1e9 + 9
//const int MOD = 998244353;




//繰り返し2乗法
//N^aの、Mで割った余りを求める。
ll my_pow(ll N, ll a, ll M) {
	ll tempo;
	if (a == 0) {
		return 1;
	}
	else {
		if (a % 2 == 0) {
			tempo = my_pow(N, a / 2, M);
			return (tempo * tempo) % M;
		}
		else {
			tempo = my_pow(N, a - 1, M);
			return (tempo * N) % M;
		}
	}
}

ll my_pow(ll N, ll a) {
	ll tempo;
	if (a == 0) {
		return 1;
	}
	else {
		if (a % 2 == 0) {
			tempo = my_pow(N, a / 2);
			return (tempo * tempo);
		}
		else {
			tempo = my_pow(N, a - 1);
			return (tempo * N);
		}
	}
}


signed main() {
	int N; cin >> N;

	vector<int> X(N), Y(N), P(N);
	rep(i, N) cin >> X[i] >> Y[i] >> P[i];

	vector<ll> res(N + 1, INF2);
	res[N] = 0;

	int M = my_pow(2, N);
	vector<vector<int>> memox(M, vector<int>(N, -1));
	vector<vector<int>> memoy(M, vector<int>(N, -1));


	//前計算
	rep(j, M) {
		vector<int> Ys, Xs;
		Xs.push_back(0); Ys.push_back(0);
		rep(k, N) {
			if (j & (1LL << k)) Xs.push_back(X[k]);
			if (j & (1LL << k)) Ys.push_back(Y[k]);
		}
		
		rep(k, N) {
			int tempo1 = INF;
			rep(l, (int)Xs.size()) {
				tempo1 = min(tempo1, abs(X[k] - Xs[l]));
			}
			memox[j][k] = tempo1;

			tempo1 = INF;
			rep(l, (int)Ys.size()) {
				tempo1 = min(tempo1, abs(Y[k] - Ys[l]));
			}
			memoy[j][k] = tempo1;
		}
	}
	//前計算終わり

	rep(j, M) {
		rep(j2, M) {
			if (j & j2) continue;
			int i = __builtin_popcountll(j) + __builtin_popcountll(j2);
			ll tempo0 = 0;
			rep(k, N) tempo0 += (ll)min(memox[j][k], memoy[j2][k]) * (ll)P[k];
			res[i] = min(res[i], tempo0);
		}
	}

	rep(i, N + 1) {
		cout << res[i] << endl;
	}


}

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

using namespace std;

bool check(int a, int b, int c)
{
    bool flag = true;
    if (a >= b + c)
        flag = false;
    if (b >= a + c)
        flag = false;
    if (c >= b + a)
        flag = false;
    return flag;
}

int main()
{
    int N;
    cin >> N;
    vector<int> L(N);
    for (int i = 0; i < N; i++)
        cin >> L.at(i);
    long long count = 0;

    sort(L.begin(), L.end(), greater<int>());

    for (int i = 0; i < N - 2; i++)
    {
        int a = L.at(i);
        for (int j = i + 1; j < N; j++)
        {

            int b = L.at(j);
            for (int k = j + 1; k < N; k++)
            {
                int c = L.at(k);
                if (check(a, b, c))
                    count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }



void solve();

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

  int T;
  // cin >> T;
  T = 1;

  while (T--) {
      solve();
  }
}

void solve() {
  int K, q;
  cin >> K >> q;
  vector<int> d(K);
  rep(i, K) cin >> d[i];

  while (q--) {
    int n, x, m;
    cin >> n >> x >> m;
    int k = K;

    chmin(k, n - 1);

    vector<int> d2 = d;
    rep(i, k) d2[i] %= m;

    // ">" を計算
    // a は単調増加数列だから普通 "<"
    // ">" となるのは, d2 < m に注意して, 商が 1 大きくなったとき
    ll a0 = x;
    ll an_1 = a0;

    ll sum = 0;
    rep(i, k) sum += d2[i];

    an_1 += n / k * sum;
    if (n % k == 0) {
      an_1 -= d2[k - 1]; // debuged
    } else {
      rep(i, n % k - 1) {
        an_1 += d2[i];
      }
    }

    ll ans = an_1 / m - a0 / m;
    // cout << endl << ans << endl;

    // "=" を計算
    sum = 0;
    rep(i, k) if (d2[i] == 0) sum++;
    ans += n / k * sum;
    if (n % k == 0) {
      if (d2[k - 1] == 0) ans--;
    } else {
      rep(i, n % k - 1) {
        if (d2[i] == 0) ans++;
      }
    }

    ans = n - 1 - ans; // "<" = 全体 - "=" - ">"
    cout << ans << endl;
  }
}


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

struct node
{
	int key;
	node* lc, * rc, * p;
};

node* root = 0;

void insert(int x)
{
	node* pre = root;        //设当前节点为根，以根为起点
	node* temp = pre;        //用来保存当前节点的临时指针

	node* in = (node*)malloc(sizeof(node));
	in->key = x;
	in->lc = 0;     
	in->rc = 0;     

	while (pre != 0)
	{
		temp = pre;
		if (in->key < pre->key)
			pre = pre->lc;
		else
			pre = pre->rc;
	}
	pre = temp;

	in->p = pre;
	if (pre == 0)
		root = in;
	else
	{
		if (in->key < pre->key)
			pre->lc = in;
		else
			pre->rc = in;
	}
}

void Inorder(node* r)
{
	if (r->lc != 0)
		Inorder(r->lc);

	cout << " " << r->key;

	if (r->rc != 0)
		Inorder(r->rc);
}

void Preorder(node* r)
{
	cout << " " << r->key;

	if (r->lc != 0)
		Preorder(r->lc);
	if (r->rc != 0)
		Preorder(r->rc);
}

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

	int n, x;
	string p;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> p;

		if (p == "insert")
		{
			cin >> x;
			insert(x);
		}
		else
		{
			Inorder(root);
			cout << endl;
			Preorder(root);
			cout << endl;
		}
	}

	return 0;
}


Measured memory_bytes: 26652
#!/usr/bin/env python3
"""
n, k = [int(i) for i in input().split(' ')]

arr = [int(i) for i in input().split(' ')]

dp = [10**10]*n

k += 1
dp[0] = 0

for i in range(0, n):
    for j in range(1, k):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i] + abs(arr[i+j]-arr[i]))

print(dp[n-1])
n = int(input())

a = [int(i) for i in input().split(' ')]

for i in range(1, n):
    new_a = [int(i) for i in input().split(' ')]
    new_a[0] = max(new_a[0]+a[1], new_a[0]+a[2])
    new_a[1] = max(new_a[1]+a[0], new_a[1]+a[2])
    new_a[2] = max(new_a[2]+a[1], new_a[2]+a[0])
    a, new_a = new_a, a

print(max(a))
"""

n, W = [int(i) for i in input().split(' ')]

dp = [0]*(W+1)

for _ in range(n):
    curwt, val = [int(i) for i in input().split(' ')]
    for wt in range(W-curwt, -1, -1):
        dp[wt+curwt] = max(dp[wt+curwt], dp[wt]+val)

print(max(dp))


Measured memory_bytes: 68404
n = int(input())
a = list(map(int, input().split()))

mid = sum(a)/2
#print(mid)

x=[0]*(n)
for i in range(n-1):
  x[i+1]=x[i]+a[i]

x=x[1:]
#print(x)
dis = [abs(x[i]-mid) for i in range(n-1)]
ret = int(min(dis)/0.5)

print(ret)

Measured memory_bytes: 27756
#include <iostream>
#include <stdio.h>
using namespace std;

int main(void) {
	double a, b;
	int  d, r;
	double f;
	cin >> a >> b;
	d = (int) (a / b);
	r = (int) a % (int) b;
	f = a / b;
	printf("%d %d %.5f", d, r, f);
	return 0;
}




Measured memory_bytes: 3196
class Dice:
    def __init__(self, dice: list):
        self.top = dice[0]
        self.bottom = dice[5]
        self.front = dice[1]
        self.behind = dice[4]
        self.right = dice[2]
        self.left = dice[3]

    def __eq__(self, other):
        if not isinstance(other, Dice):
            return NotImplemented
        return self.top == other.top and self.bottom == other.bottom and self.front == other.front \
                and self.behind == other.behind and self.right == other.right and self.left == other.left

    def roll(self, direction: str):
        buffer = self.top
        if direction == 'E':
            self.top = self.left
            self.left = self.bottom
            self.bottom = self.right
            self.right = buffer
        elif direction == 'N':
            self.top = self.front
            self.front = self.bottom
            self.bottom = self.behind
            self.behind = buffer
        elif direction == 'S':
            self.top = self.behind
            self.behind = self.bottom
            self.bottom = self.front
            self.front = buffer
        else:
            self.top = self.right
            self.right = self.bottom
            self.bottom = self.left
            self.left = buffer

    def turn(self):
        buffer = self.front
        self.front = self.right
        self.right = self.behind
        self.behind = self.left
        self.left = buffer


def main():
    dices = [Dice(list(map(int, input().split()))) for _ in range(int(input()))]
    for index, dice1 in enumerate(dices[:-1]):
        for dice2 in dices[index+1:]:
            for _ in range(2):
                for _ in range(4):
                    for _ in range(4):
                        if dice1 == dice2:
                            print('No')
                            return
                        dice2.turn()
                    dice2.roll('N')
                dice2.roll('E')
    print('Yes')


if __name__ == '__main__':
    main()



Measured memory_bytes: 5612
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>
#include<iostream>
#include<vector>
#define MAXN 1000100
using namespace std;
typedef long long ll;
///设一个怪物炸y次,总共炸x次则
/// a[i]<=A*y+(x-y)*B 即 x*B+(A-B)y
/// 所以 y>=(a[i]-x*B)/(A-B) (向上取整) 66666
ll a[MAXN];
ll n,A,B;
bool judge(ll x)
{
    ll sub=x*B;
    ll div=A-B;
    ll sum=0;
    for(ll i=0;i<n;i++)
    {
        if(a[i]>sub)
        {
            ll temp=(a[i]-sub)/div;
        if((a[i]-sub)%div>0)
            sum+=temp+1;
        else sum+=temp;
        }
        
    }
   // cout<<x<<"     "<<sum<<endl;
    if(sum<=x)return true;
    return false;
}
int main()
{
    cin>>n>>A>>B;
    ll cnt=0;
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
        cnt+=a[i]/B+1;
    }
    ll l=1,r=cnt;
    while(l<=r)
    {
       // cout<<l<<endl;
        ll mid=(l+r)>>1;
        if(judge(mid))
            r=mid-1;
        else l=mid+1;
    }
    cout<<l<<endl;
}







Measured memory_bytes: 1024
from fractions import gcd
def lcm(x,y):
  return (x*y) // gcd(x,y)
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
l = a[0]
for i in range(1,n):
  l = lcm(l,a[i])
ans = 0
for i in range(n):
  ans += l//a[i]
print(ans%mod)

Measured memory_bytes: 6200
import java.util.*;

public class Main {

	/**
	 * @param args
	 */
	
	public void copy (int i, int j, int game[][], int result[][]) {
		result[i][j] = game[i][j];
	}
	
	public void decisionmain (int n, int game[][], int result[][]) {
		for (int j = 0; j < 3; j++) {
			for (int i = 0; i < n; i++) {
				for (int k = 0; k < n; k++) {
					decisionsub(i, j, k, game, result);
				}
			}
		}	
	}
	
	public void decisionsub (int i, int j, int k, int game[][], int result[][]) {
		if (k != i) {
			if (game[i][j] == game[k][j]) {
				result[i][j] = 0;
			}
		}
	}
	
	public void scoresum (int n, int result[][]) {
		for (int i = 0; i < n; i++) {
			int sum = 0;
			for (int j = 0; j < 3; j++) {
				sum += result[i][j];
			}
			System.out.println(sum);
		}
	}
	
	void doIt () {
		
		Scanner sc = new Scanner (System.in);

		int n = sc.nextInt();

		int [][] game = new int [n][3];
		int [][] result = new int [n][3];

		int i, j;
		
		for (i = 0; i < n; i++) {
			for (j = 0; j < 3; j++) {
				game[i][j] = sc.nextInt();
				copy(i, j, game, result);
			}
		}
		
		decisionmain(n, game, result);
		scoresum(n, result);
		
	}
	
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		
		new Main(). doIt();
		
	}

}

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

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if ((10*b+c)%4==0) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    // cout<<b<<" "<<c<<" "<<(10*b+c)%4<<endl;
    return 0;

}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{

    int coin;       cin >> coin;

    int happy = 0;
    while (coin > 5){
        if (coin >= 500){
            happy += 1000;
            coin -= 500;
        }else if (coin >= 5){
            happy += 5;
            coin -= 5;
        }
    }

    cout << happy << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
#include <iomanip>
#include <cstring> 
using namespace std;
using ll=long long;

#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define LLONG_MAXs 9223372036854775800

#define ALL(a) (a).begin(),(a).end()

#include <iostream>
#include <cmath>
using namespace std;
 

 
bool isPrimeNum( ll x ){ // 素数である場合 true を返す
  if( x <= 1 ){ // 1以下である場合は素数でないことがすぐにわかる
    return false;
  }
  // sqrt( double型 ) は引数の平方根を double型で返すので、int型でキャスト
  int n = (int)sqrt( (double)x );
  for( int i = 2; i <= n; i++ ){
    if( x % i == 0 ){ // 割り切る整数がある場合、即判定終了
      return false;
    }
  }
  return true; // 割り切る整数がない場合、素数である
}

ll myPow(ll x, ll n, ll m){
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll abs(ll a,ll b){
if(a>=b)return a-b;
if(a<b)return b-a;
}
constexpr ll min(ll a,ll b){
if(a>=b)return b;
if(a<b)return a;
}

constexpr ll max(ll a,ll b){
if(a>=b)return a;
if(a<b)return b;
}

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

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;
 
	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}
 
	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}
 
	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい]
	}
 
	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}
 
		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);
 
		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;
 
		return true;
	}
};




long long fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < 510000; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


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

  ll maxid=n;
  ll minid=1;

  FOR(i,0,m-1){
  ll tp1,tp2;
  cin >> tp1>>tp2;
  maxid=min(maxid,tp2);
  minid=max(minid,tp1);
  }

  cout<<max(0,maxid-minid+1)<<endl;




}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

using namespace std;
#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x);
#define if_range(x, w, h) if (w <= x && x <= h)
#define BitCheck(a,b)   (a >> b) & 1
#define BitSet(a,b)       a |= (1 << b)
#define BitunSet(a,b)    a &= ~(1 << b)
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define Numof(array)  (sizeof (array) / sizeof *(array))

struct cmp_c {
	bool operator()(int x, int y) {
		return x < y;
	}
} cmp;

int main() {
	int n, a[1000000], dp[1000001];
	scanf("%d", &n);
	fill(dp, &dp[n], INT_MAX);
	for (int i = 0; n > i; i++)
		scanf("%d", &a[i]);

	for (int i = 0; n > i; i++) {
		*lower_bound(dp, &dp[n], a[i]) = a[i];
	}
	printf("%d\n", lower_bound(dp, &dp[n], INT_MAX) - dp);
	return 0;
}

Measured memory_bytes: 3636
s = gets.chomp.split("")
k = gets.to_i

if s.all? { |a| a == s.first }
  length = s.length * k
  puts length / 2
  exit
end

s_2 = s * 1
s_3 = s * 2

previous = "A"
s_2_count = 0
s_2.each do |s2|
  if s2 == previous
    s_2_count += 1
    previous = "A"
  else
    previous = s2
  end
end

previous = "A"
s_3_count = 0
s_3.each do |s3|
  if s3 == previous
    s_3_count += 1
    previous = "A"
  else
    previous = s3
  end
end

gap = s_3_count - s_2_count

puts s_2_count + gap * (k - 1)


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define hell1 1e9+7
#define hell2 1e9+9
#define pi 3.1415926535
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define ll long long
#define ld long double 
#define no_of_digits(n) floor(log10(n)) + 1
#define see(x) cout << (#x) << " is " << (x) << endl
#define INF 1e9

using namespace std;

ll mult(ll a,ll b, ll p=hell1){   return ((a%p)*(b%p))%p; }
ll multbig(ll a,ll b,ll mod=hell1){   if(a==0 or b==0) return 0;if(a==1 or b==1) return (a*b)%mod;ll cur=multbig(a,b/2,mod);cur=(2*cur)%mod;if(b%2) cur=(cur+a)%mod;return cur;
}
ll add(ll a, ll b, ll p=hell1){ if(a>=p) a%=p; if(b>=p) b%=p; if(a+b>p) return (a + b)%p; else return a+b;}
ll sub(ll a, ll b, ll p=hell1){return (a%p - b%p + p)%p;}
ll fpow(ll n, ll k, ll p = hell1) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = mult(r,n,p); n = mult(n,n,p);} return r;}
ll inv(ll a, ll p = hell1) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = hell1){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
int isPowerof2(ll x) { return (x && !(x & x-1)); } 
ll log2(ll x) { ll res = 0; while (x >>= 1) res++; return res; } 

// max({a, b, c, d})

vector<ll>adj[200005];
ll update[200005];
ll ans[200005];

int binaryToDecimal(string n) 
{ 
    string num = n; 
    int dec_value = 0; 
  
    // Initializing base value to 1, i.e 2^0 
    int base = 1; 
  
    int len = num.length(); 
    for (int i = len - 1; i >= 0; i--) { 
        if (num[i] == '1') 
            dec_value += base; 
        base = base * 2; 
    } 
  
    return dec_value; 
} 

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

    cout << min(n*a, b) << "\n";
}




Measured memory_bytes: 6016
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
using lll = long long;
using ull = unsigned long long;
using namespace std;



int main(){
  lll ii,jj,kk;
  long n;

  cin >> n;

  vector<long> v;
  v.resize(n);

  for(ii=0;ii<n;ii++){
    cin >> v[ii];
  }

  sort(v.begin(),v.end());
  double sum = 0;
  sum = v[0];
  for(ii=1;ii<n;ii++){
    sum = (sum + v[ii])/2;
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const ll MOD=1000000007;
//const ll MOD=998244353;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);
int dx[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0};
int dy[9] = {0, 1, 0, -1, 1, -1, -1, 1, 0};

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

/*複数の整数に対する素因数分解、素数判定*/

//エラトステネスの篩
//前処理でmake_eratos() デフォルトで150msくらい
const int MAX_for_eratos=10000100;
int eratos[MAX_for_eratos];
int prime_number_list[MAX_for_eratos/2];

void make_eratos(){
  rep(i,MAX_for_eratos) eratos[i]=-1;
  //2の倍数だけ先にやっちゃう
  prime_number_list[0]=2;
  for(int j=2;j<MAX_for_eratos;j+=2) eratos[j]=2; 
  int k=1;
  for(int i=3;i<MAX_for_eratos;i+=2){
    if(eratos[i]>-1) continue;
    prime_number_list[k]=i; k++;
    eratos[i]=i;
    if(i>MAX_for_eratos/i+1) continue;
    for(int j=i*i;j<MAX_for_eratos;j+=i) if(eratos[j]==-1) eratos[j]=i;
  }
  
  return;
}
//osa_k法による素因数分解
//普通の因数分解と同様N==1の時に注意
//前処理make_eratos必要
vector<pair<ll,ll>> prime_factorize(ll N){
  vector<pair<ll,ll>> ret={};
  for(int i=0;N>MAX_for_eratos-100&&prime_number_list[i]*(ll)prime_number_list[i]<=N;i++){
    if(N%prime_number_list[i]!=0) continue;
    ll a=prime_number_list[i];
    ll ex=0;
    while(N%a==0){
      ex++;
      N/=a;
    }
    ret.push_back({a,ex});
  }
  if(N>MAX_for_eratos-100) {ret.push_back({N,1}); return ret;}
  while(N>1){
    ll ex=0;
    ll a=eratos[N];
    while(N%a==0){
      ex++;
      N/=a;
    }
    ret.push_back({a,ex});
  }
  
  return ret;
}

//素数判定
//前処理make_eratos必要
bool is_prime(ll N) {
  if(N==1) return false;
  if(N<=MAX_for_eratos-100) return N==eratos[N];
  else{
    for(int i=0;prime_number_list[i]*(ll)prime_number_list[i]<=N;i++){
      if(N%prime_number_list[i]==0) return false;
    }
    return true;
  }
}

/*終わり*/

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // cout << fixed << setprecision(15);

  make_eratos();
  ll N; cin>>N;
  ll ans=0;
  for(int c=1;c<=N-1;c++){
    ll sans=1;
    if(N-c==1) {ans++; break;}
    for(auto p:prime_factorize(N-c)) sans*=p.second+1;
    ans+=sans;
  }
  
  cout<<ans<<'\n';
  
  return 0;
}


Measured memory_bytes: 45328
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iomanip>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;

#define ld long double
#define ll long long

map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N,K;
  cin >> N >> K;
  bool used[101000]={0};
  pair<int,int> a[N];
  ll ans=0;
  int t,d;
  for(int i=0;i<N;i++){
    cin >> a[i].second >> a[i].first;
  }
  sort(a,a+N);
  reverse(a,a+N);

  priority_queue<int,vector<int>,greater<int>> que;
  ll cnt=0;
  for(int i=0;i<K;i++){
    ans+=a[i].first;
    if(!used[a[i].second]){
      cnt++;
      used[a[i].second]=true;
    }else{
      que.push(a[i].first);
    }
  }
  ll point =ans+cnt*cnt;

  for(int i=K;i<N;i++){
    if(cnt==K)break;
    if(!used[a[i].second]){
      cnt++;
      ans=ans-que.top()+a[i].first;
      que.pop();
      used[a[i].second]=true;
      point=max(point,ans+cnt*cnt);
    }else{
      continue;
    }
  }
  cout << point << endl;
  return 0;
}

Measured memory_bytes: 1536
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())
s = input() #sys.stdin.readlineは最後が改行
t = input() #sys.stdin.readlineは最後が改行

ans = 2*n
for i in range(n):
    if s[i:n] == t[:(n-i)]:
        print(2*n-(n-i))
        exit()

print(2*n)

Measured memory_bytes: 3064
import math
#平方オーダーなら収まるので平方根とって方針を分ける
n = int(input())
s = int(input())
if n == s:
  print(n + 1)
  exit(0)
def sqrt(k):
  return int(math.sqrt(k))
def digitsum(b, m):
  if m < b:
    return m
  return digitsum(b, m // b) + m % b
#√nより小さいなら
#全探索余裕 桁は多くて40程度なので
for b in range(2, sqrt(n) + 1):
  if digitsum(b, n) == s:
    print(b)
    exit(0)
#√nより大きいなら
#b^2 > n である。２桁ということ
#2桁目がpなら、1桁目はs-pである
#pb + s - p = n
#b = (n - s) // p + 1
for p in range(sqrt(n), 0, -1):
  b = (n - s) // p + 1
  if b <= 1: continue
  if digitsum(b, n) == s:
    print((n - s) // p + 1)
    exit(0)
print(-1)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
   cin.tie(0);
   ios::sync_with_stdio(false);
   ll n, a, b;
   cin >> n >> a >> b;
   ll ans = 0;
   ll cnt = n/(a+b);
   ans += cnt*a;
   cnt = n%(a+b);
   if(cnt<=a) {
       ans+=cnt;
   } else {
       ans+=a;
   }
   cout << ans << endl;
}

Measured memory_bytes: 256
N,K= list(map(int, input().split()))
A= list(map(int, input().split()))
AA=sorted(A)
num=0
for i in A:
    num+=AA.index(i)
num2=0
for i in range(N-1):
    for j in range(i+1,N):
        if A[i]>A[j]:
            num2+=1
hoge=(K-1)*K//2%1000000007
hoge=hoge*num%1000000007
hoge2=num2*K%1000000007
hoge=(hoge+hoge2)%1000000007
print(hoge)

Measured memory_bytes: 41708
// #include "knapsack_1.h"
    #include <algorithm>
    #include <iostream>
     
    #include <vector>
     
    struct Item {
        int weight;
        int value;
     
        Item(int w, int v)
            : weight{w}
            , value{v}
        {
        }
    };
     
    long long max_value(const std::vector<Item>& items, int capacity)
    {
        std::vector<long long> dp(capacity + 1);
     
        for (const auto& item : items) {
            for (int weight = capacity - item.weight; weight >= 0; --weight) {
                auto& current = dp[weight + item.weight];
                current = std::max(current, item.value + dp[weight]);
            }
        }
     
        return *std::max_element(dp.cbegin(), dp.cend());
    }
     
    int main(int argc, char* argv[])
    {
        int n, capacity;
        std::cin >> n >> capacity;
        std::vector<Item> items;
        items.reserve(n);
     
        for (int i = 0; i < n; ++i) {
            int weight, value;
            std::cin >> weight >> value;
            items.emplace_back(weight, value);
        }
        std::cout << max_value(items, capacity) << std::endl;
        return 0;
    }

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
#include<cstdio>
#include<cmath>

struct Point{ double x, y; };

Point set_p(double a, double b)
{
    Point p;
    p.x = a; p.y = b;
    return p;
}

struct Vector{ double vx, vy; };

Vector set_v(const Point &p1, const Point &p2)
{
    Vector v;
    v.vx = p2.x - p1.x;
    v.vy = p2.y - p1.y;
    return v;
}

double inpro(const Vector &v1, const Vector &v2)
{
    return (v1.vx * v2.vx) + (v1.vy * v2.vy);
}

double det2(const Vector &v1, const Vector &v2)
{
	return (v1.vx * v2.vy) - (v1.vy * v2.vx);
}

int main()
{
	double p0x, p0y, p1x, p1y;
	scanf("%lf %lf %lf %lf", &p0x, &p0y, &p1x, &p1y);
	Point P0 = set_p(p0x, p0y);
	Point P1 = set_p(p1x, p1y);
	Vector V1 = set_v(P0, P1);

	double p2x, p2y, d;

	int q;
	scanf("%d", &q);
	for(int i = 0; i < q; i++){
		scanf("%lf %lf", &p2x, &p2y);
		Point P2 = set_p(p2x, p2y);
		Vector V2 = set_v(P0, P2);
		Vector V = set_v(P1, P2);
		d = det2(V1, V2);
		if(d > 0){ printf("COUNTER_CLOCKWISE\n"); }
			else if(d < 0){ printf("CLOCKWISE\n"); }
			else{
			    if(inpro(V1, V2) < 0){ printf("ONLINE_BACK\n"); }
			    else if(inpro(V1, V) > 0){ printf("ONLINE_FRONT\n"); }
			    else{ printf("ON_SEGMENT\n"); }
			}
	}
	return 0;
}

Measured memory_bytes: 1204
"""
author : halo2halo
date : 23, Jan, 2020
"""

import sys
# import itertools
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M, X, Y = map(int, readline().split())
x = [int(x) for x in readline().split()]
y = [int(y) for y in readline().split()]

x.append(X)
y.append(Y)
# print(x)
# print(y)
print("No War" if max(x)<min(y) else "War")


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

vector<int> adj[200005];

int main(){

    cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
  
    // what if languages are nodes too :seremepeepoggers:

    int n, m; cin >> n >> m;
  
    for(int i = 0; i < n; ++i){
        int k; cin >> k;
        for(int j = 0; j < k; ++j){
            int a; cin >> a;
            adj[a + n].push_back(i);
            adj[i].push_back(a + n);
        }
    }

    int cnt = 0;

    queue<int> q;
    q.push(0);

    bitset<200005> vis;
    vis[0] = 1;

    while(!q.empty()){
        int node = q.front();
        q.pop();
        if(node < n){
            ++cnt;
            if(cnt == n){
                cout << "YES\n"; return 0;
            }
        }
        for(auto nx : adj[node]){
            //ide[l] &= vis;
            //for(int nx = ide[l]._Find_first(); nx < ide[l].size(); nx = ide[l]._Find_next(nx)){
            //    vis[nx] = 0;
            //    //cout << "ADD " << nx << endl;
            //    q.push(nx);
            //}
            if(vis[nx]) continue;
            vis[nx] = 1;
            q.push(nx);
        }
    }

    cout << "NO\n";

    return 0;

}


Measured memory_bytes: 8952
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
typedef long long ll;
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 long long INF = 1LL << 60;
const int inf = 1001001001;
const int mod = 1000000007;
using pint=pair<ll,ll>;
 
// union by size + path having
class UnionFind {
public:
   vector <ll> par; // 各元の親を表す配列
   vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
 
   // Constructor
   UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
       for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
   }
   void init(ll sz_) {
       par.resize(sz_);
       siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
       for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
  }
 
   // Member Function
   // Find
   ll root(ll x) { // 根の検索
      while (par[x] != x) {
           x = par[x] = par[par[x]]; // x の親の親を x の親とする
       }
       return x;
  }
 
   // Union(Unite, Merge)
   bool unite(ll x, ll y) {
       x = root(x);
       y = root(y);
       if (x == y) return false;
       // merge technique（データ構造をマージするテク．小を大にくっつける)
       if (siz[x] < siz[y]) swap(x, y);
       siz[x] += siz[y];
       par[y] = x;
       return true;
  }
 
  bool same(ll x, ll y) { // 連結判定
       return root(x) == root(y);
  }
 
  ll size(ll x) { // 素集合のサイズ
      return siz[root(x)];
  }
};
 
ll modpow(ll x, ll n) {
   x = x%mod;
   if(n==0) return 1;  //再帰の終了条件
 
   else if(n%2==1) {
       return (x*modpow(x, n-1))%mod;  //nが奇数ならnを1ずらす
   }
   else return modpow((x*x)%mod, n/2)%mod;  //nが偶数ならnが半分になる
}
 
ll com(ll n, ll k) {
   ll x = 1;
   for(int i=n-k+1; i<=n; i++) {
      x = x*i%mod;
   }
 
   ll y = 1;
   for(int i=1; i<=k; i++) {
       y = y*i%mod;
   }
   y = modpow(y, mod-2);
 
   return x*y%mod;
}
 
int main(){

  ll n,k;
  cin >> n >> k;
  vector<ll> data(n);
  rep(i,n) cin >> data.at(i);
  ll ans=0;
  rep(i,n){
    ans+=2*min(data.at(i),k-data.at(i));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
/*input
5
0.42 0.01 0.42 0.99 0.42
*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;cin>>n;
	vector<double> prob(n+1);
	for(int i=1;i<=n;i++) cin>>prob[i];

	vector<vector<double>> dp(n+1,vector<double> (n+1,(double)0));
	dp[0][0]=1;
	for(int i=1;i<=n;i++) for(int j=0;j<=i;j++) dp[i][j] = dp[i-1][j]*(1-prob[i])+(j-1>=0?dp[i-1][j-1]*prob[i]:0);
	double ans = 0;
	for(int j=n/2+1;j<=n;j++) ans+=dp[n][j];
	cout<<setprecision(20)<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 73764
import java.util.Scanner;	
public class Main 	
{	
    public static void main(String args[])	
    {	
        String str;	
        Scanner sc = new Scanner(System.in);	
        while(true){	
            str=sc.nextLine();	
            if(str.equals("0")) break;	
            int sum = 0;	
            for(int i=0;i<str.length();i++){	
                 sum+=str.charAt(i)-'0';	
            }	
            System.out.println(sum);	
        }	
    }	
}	
	


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

constexpr int mod = 1000000007;

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

    vector<int> broken(n + 1, false);
    rep(i, m)
    {
        int a;
        cin >> a;
        broken[a] = true;
    }
    vector<ll> dp(n + 1);
    dp[0] = 1;
  
    for (int i = 0; i < n; ++i)
    {
        if (!broken[i + 1])
        {
            dp[i + 1] += dp[i];
            dp[i + 1] %= mod;
        }
        if (i + 2 > n)
            continue;
        if (!broken[i + 2])
        {
            dp[i + 2] += dp[i];
            dp[i + 2] %= mod;
        }
    }

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

Measured memory_bytes: 4564
import java.io.*;
public class Main {
	public static void main(String[] args){
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		try{
			String line = reader.readLine();
			int n = Integer.parseInt(line);
			for (int i = 1; i <= n; i++) {
				if (i % 3 == 0) {
					System.out.print(" " + i);
				} else {
					int x = i;
					int y = i;
					int b = 0;
					while (x != 0) {
						x = x % 10;
						if (x == 3) {
							b++;
							break;
						}
						y = y / 10;
						x = y;
					}
					if (b > 0) {
						System.out.print(" " + i);
					}
					
				}
			}
			System.out.println();
		} catch (IOException e) {
          System.out.println(e);
        } catch (NumberFormatException e) {
          System.out.println("error");
        }
    }
}

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

int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
     
      long long n,i,j,k,sum=0,count=0,ans=0,x,y,l,r;
      char c;
      cin>>c;
      k=int (c-'a');
      if(k>=0 && k<26)
      cout<<'a';
      else
      cout<<'A';
	return 0;
}

Measured memory_bytes: 3644
//https://codeforces.com/contest/1333/problem/C


//#include <bits/stdc++.h>
 #include <algorithm>
  #include <bitset>
  #include <complex>
  #include <deque>
  #include <exception>
  #include <fstream>
  #include <functional>
  #include <iomanip>
  #include <ios>
  #include <iosfwd>
  #include <iostream>
  #include <istream>
  #include <iterator>
  #include <limits>
  #include <list>
  #include <locale>
  #include <map>
  #include <memory>
  #include <new>
  #include <numeric>
  #include <ostream>
  #include <queue>
  #include <set>
  #include <sstream>
  #include <stack>
  #include <stdexcept>
  #include <streambuf>
  #include <string>
  #include <typeinfo>
  #include <utility>
  #include <valarray>
  #include <vector>
  #include <array>
  #include <atomic>
  #include <chrono>
  #include <condition_variable>
  #include <forward_list>
  #include <future>
  #include <initializer_list>
  #include <mutex>
  #include <random>
  #include <ratio>
  #include <regex>
  #include <scoped_allocator>
  #include <system_error>
  #include <thread>
  #include <tuple>
  #include <typeindex>
  #include <type_traits>
  #include <unordered_map>
  #include <unordered_set>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long 
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;



int32_t main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	
  ini(x);
  ini(x1);
  out((x*3+x1)/2);
  
	return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  AOJ1153
//
//  Created by aki33524 on 2014/07/15.
//  Copyright (c) 2014年 aki33524. All rights reserved.
//

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

void solve(vector<int> v1, vector<int> v2){
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    
    int sum1 = accumulate(v1.begin(), v1.end(), 0);
    int sum2 = accumulate(v2.begin(), v2.end(), 0);
    int sum = sum1 + sum2;
    if(sum%2 == 1){
        cout << -1 << endl;
        return;
    }
    
    for(int i=0; i<v1.size(); i++){
        for(int j=0; j<v2.size(); j++){
            if(sum1 - v1[i] + v2[j] == sum/2){
                cout << v1[i] << " " << v2[j] << endl;
                return;
            }
        }
    }
    
    cout << -1 << endl;
}

int main(int argc, const char * argv[])
{
    int n, m;
    while(cin>>n>>m, n|m){
        vector<int> v1(n);
        vector<int> v2(m);
        for(int i=0; i<n; i++)
            cin >> v1[i];
        for(int i=0; i<m; i++)
            cin >> v2[i];
        
        solve(v1, v2);
    }

    return 0;
}

Measured memory_bytes: 1216
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`);
    var N:Int =sc.nextInt();
    var K:Long=sc.nextLong();
    val A :ArrayList<Int> = ArrayList();
    for(i in 0..N-1){
        A.add(sc.nextInt()-1);    //入力を受け取る
    }
    val loop :ArrayList<Int> = ArrayList(); //来た町を記録する
    var visited = IntArray(N){-1}; //訪問判定（2度来てたらループする）
    //初期条件を考える
    var now = 0;
    while(visited[now] < 0){
        visited[now] = loop.size;
        loop.add(now);
        now = A[now];
    }
    //println(visited[now]);
    //println(loop.size);
    var loopsize = loop.size - visited[now];
    var beforeloop = visited[now];
    if(K < beforeloop){
        println(loop[(K.toInt() )]+1);
    }else{
        K-=beforeloop;
        K%=loopsize.toLong();
        println(loop[beforeloop+ (K.toInt() ) % loopsize]+1);
    }
    //println(loop);
    //println(visited);
/*
    println(count);
    println(beforeloop);
    println(loop.toString());
    println(A.toString());
*/
}


Measured memory_bytes: 67824
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n, ans = 0;
    cin >> n;
    vector<int> a(n, -1), b(n-1);
    for(int i = 0; i < n-1; i++){
        cin >> b[i];
    }
    a[0] = b[0];
    for(int i = 0; i < n-2; i++){
        if(b[i] <= b[i+1]){
            if(a[i] != -1){
                a[i+1] = b[i];
            }
            else{
                a[i] = a[i+1] = b[i];
            }
        }
        else{
            if(a[i] == -1){
                a[i] = b[i];
            }
        }
    }
    if(a[n-2] == -1) a[n-2] = b[n-2];
    a[n-1] = b[n-2];
    for(int i = 0; i < n; i++){
        ans += a[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
from math import gcd
import random,time

def gcdcount(n,m):
    x,y=min(n,m),max(n,m)
    if x==0:
        return 0
    else:
        return 1+gcdcount(x,y%x)

fibo=[0,1,2]
for i in range(100):
    fibo.append(fibo[-1]+fibo[-2])

gcdfibo=[[],[(1,2),(1,3)]]

for i in range(2,101):
    temp=[]
    for a,b in gcdfibo[-1]:
        temp.append((b,a+b))
    a,b=fibo[i],fibo[i+2]
    temp.append((a,b))
    temp.sort()
    gcdfibo.append(temp)

def solve(x,y):
    if x>y:
        x,y=y,x
    mod=10**9+7
    if x==1:
        return  (1,y%mod)
    if (x,y)==(2,2):
        return (1,3)
    id=1
    t=-1
    while True:
        if fibo[id+1]<=x and fibo[id+2]<=y:
            id+=1
        else:
            if fibo[id+1]>x:
                if fibo[id+2]>y:
                    t=0
                else:
                    t=1
            else:
                t=2
            break

    #print(t)
    if t==0:
        res=0
        for a,b in gcdfibo[id]:
            if a<=x and b<=y:
                res+=1
        return (id,res)
    elif t==1:
        res=0
        for a,b in gcdfibo[id]:
            if a<=x and (a,b)!=(fibo[id],fibo[id+2]) and b<=y:
                res+=(y-b)//a+1
                res%=mod
        return (id,res)
    else:
        res=0
        for a,b in gcdfibo[id+1]:
            u,v=b-a,a
            if u<=x and v<=y:
                res+=1
                res%=mod
            if u<=y and v<=x:
                res+=1
                res%=mod
        return (id,res)

mod=10**9+7
Q=int(input())
start=time.time()
for _ in range(Q):
    x,y=map(int,input().split())
    id,res=solve(x,y)
    if (x,y)==(2,2):
        res+=1
    print(id,res)

#print(time.time()-start)

Measured memory_bytes: 87580
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
const ll mod=1e9+7;
const ll MAXN = 1e7+10;


  
int spf[MAXN];

void solve(){
    
    int ans=0,n=0;
    cin>>n;
    for (int i = 0; i < n; i++) {
        int a;cin>>a;
        if(((i+1)%2==1)&&(a&1)) ans++;
    }
    cout<<ans<<"\n";
    
    
}
  
        

int main(){
   
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout); 
    #endif */
        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int T=1;
        //cin>>T;
        while(T--){
            solve();
        }
            
            
        return 0;
}
 

Measured memory_bytes: 3552
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append([i,n // i])
    # divisors.sort()
    return divisors

n = int(input())
a = make_divisors(n)
print(a[-1][0]+a[-1][1]-2)

Measured memory_bytes: 3560