akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
#define fr(i,a,b) for (long long int i = (a), _b = (b); i <= _b; i++)
// #define frr(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)

// #define repr(i,n) for (long long i = (n) - 1; i >= 0; i--)
// #define foreach(it,ar) for ( typeof(ar.begin()) it = ar.begin(); it != ar.end(); it++ )
// #define fill(ar,val) memset(ar, val, sizeof(ar))
// #define fill0(ar) fill((ar), 0)
// #define fillinf(ar, n) fr(i,0,(n)) ar[i] = INF
// #define debug(x) cout<<#x<<": "<<x<<endl
// #define arr1d(a,n) cout << #a << " : "; fr(,1,n) cout << a[] << ' '; cout << endl;
// #define arr1d0(a,n) cout << #a << " : "; rep(,n) cout << a[] << ' '; cout << endl;
// #define arr2d(a,n,m) cout << #a << " :" << endl; fr(,1,n) {fr(,1,m) cout << a[][__] << ' '; cout << endl;}
// #define arr2d0(a,n,m) cout << #a << " :" << endl; rep(,n) {rep(,m) cout << a[][__] << ' '; cout << endl;}
// #define ull unsigned long long
// #define ll long long int
// #define ld double
// #define ui unsigned int
// #define all(ar) ar.begin(), ar.end()
// #define pb push_back
// #define mp make_pair
// #define ff first
// #define ss second


// #define PI 3.1415926535897932385
// #define INF 1000111222
// #define EPS 1e-7
// #define MAXN 1000001
// #define MOD 998244353


//  #include<iostream>
//      #include<vector>
// #include <stdio.h>
// #include<algorithm>
// #include<math.h>
// #include <iomanip>  
// #include <algorithm> 
// #include<bits/stdc++.h>
// #include <iterator>
// using std::string;
// //#include <boost/algorithm/string.hpp> 
#include<bits/stdc++.h>
#include<ratio>
#include <set> 
#include <iterator>
using namespace std;
#define ll long long
#define VV vector
#define pb push_back
#define bitc  __builtin_popcountl
#define m_p make_pair
#define inf 200000000000000
#define MAXN 1000001
#define eps 0.0000000001
#define prime 1000000007
#define ll long long
using namespace std;
#define S second
#define F first
ll MOD=1e9+7;
#define rep(i,n) for (long long i = 0, _n = (n); i < _n; i++)
long long StringToInteger(string NumberAsString)
{
  long long NumberAsInteger;
  stringstream ss;
  ss << NumberAsString;
  ss >> NumberAsInteger;
  return NumberAsInteger;
}
 int32_t main()
{   
        int n;
        cin>>n;
        vector<int> hs(n,0);
        for(int i=0;i<n;i++)
        {
            cin>>hs[i];
            
        }
        VV<int> mini(n,0);
        mini[0]=0;
        mini[1]=abs(hs[1]-hs[0]);
        int ak1,ak2;
        int var;
        for(int i=2;i<n;i++)
        {
            ak1=mini[i-1]+abs(hs[i]-hs[i-1]);
            ak2=mini[i-2]+abs(hs[i]-hs[i-2]);
            var=min(ak1,ak2);
            mini[i]=var;
            //cout<<mini[i];
        }
        cout<<mini[n-1];
    
    
    return 0;
}

Measured memory_bytes: 1024
//https://atcoder.jp/contests/abc178/tasks/abc178_b
#include <bits/stdc++.h>
using namespace std;
int main() {
    long long a,b,c,d;
    cin>>a>>b>>c>>d;

    long long ans;
    ans=max(a*c, a*d);
    ans=max(ans, b*c);
    ans=max(ans, b*d);
    cout<<ans<<"\n";

    return 0;
}

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

/// easy access -------------
using namespace std;
using ll = long long;
using ld = long double;
typedef pair<int,int> pi;
typedef tuple<int, int, int> tp;
///-------------------------

int main()
{
    Phuong_; /// <3333
    int n;
    cin >> n;
    vector<ll> a(n);
    int zero=0;
    for(int i=0; i<n; ++i){
        cin >> a[i];
        if (a[i]==0) zero++;
    }
    if (zero) {
        cout << 0;
        return 0;
    }
    const ll maxx = 1e18L;
    ll prod =1;
    for(int i=0; i<n; ++i) {
        if (a[i] <= maxx/prod){
            prod= prod*a[i];
        } else {
            cout << -1;
            return 0;
        }
    }
    cout << prod;
    return 0;
}


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

using namespace std;

int main()
{
	int h, w;
	cin >> h >> w;

	char str[200][200], frame[200][200];

	for (int i = 0; i < h; i++)
	{
		cin >> str[i];
	}



	for (int i = 0; i < h + 2; i++)
	{
		for (int j = 0; j < w + 2; j++)
		{
			frame[i][j] = '#';
		}
	}

	for (int i = 0; i < h; i++)
	{
		for (int j = 0; j < w; j++)
		{
			frame[i + 1][j + 1] = str[i][j];
		}
	}

	for (int i = 0; i < h + 2; i++)
	{
		for (int j = 0; j < w + 2; j++)
		{
			cout << frame[i][j];
		}
		cout << endl;
	}

	
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)){
        	while(sc.hasNext()) {
        		int n= sc.nextInt();
        		int k = sc.nextInt();
        		int[] a= new int[n+1];
        		int min = 0;
        		for(int i=0;i<n;i++) {
        			a[i] = sc.nextInt();
        			if(a[i]==1)
        				min = i;
        		}
        		
        		int cnt = 0;
        		int h = 0;
        		cnt = min/(k-1);
        		if(min%(k-1) != 0) {
        			min = min+k-1-(min%(k-1));
        			cnt++;
        		}
       			for(int i=min+1;i<n;i++) {
       				if(h==0) {
       					cnt++;
       				}
       				a[i] = 1;
       				h++;
       				if(h==k-1) {
       					h=0;
       				}
        		}
       			System.out.println(cnt);
        	}
        }
    }
}




Measured memory_bytes: 51176
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,a;
  cin >> N;
  
  vector<int> vec2(N);    
  
  for (int i = 0; i < N; i++) {
    cin >> a;
    vec2.at(a-1)=i+1;
  }
  
  for (int i = 0; i < N; i++) {
    cout << vec2.at(i) << endl;  
  }
  
}

Measured memory_bytes: 1152
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        int result = 0;
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int t[] = new int[110000];
        int x[] = new int[110000];
        int y[] = new int[110000];
        
        // 初期位置
        t[0] = 0; x[0] = 0; y[0] = 0;

        // 入力値を代入
        for (int i = 0;i < n; i++){
            t[i+1] = sc.nextInt();
            x[i+1] = sc.nextInt();
            y[i+1] = sc.nextInt();
        }
        
        boolean can = true;
        // 時刻tに点(x,y)に到達できるか探索
		for (int i = 0; i < n; i++) {
		    // 入力値の時刻tから現在の経過時間を引き、制限時間を算出
		    int dt = t[i+1] - t[i];
		    
		    // 入力値の点(x,y)から現在の点(x,y)の値を引いた値の絶対値を足し、移動距離を算出
		    int dist = Math.abs(x[i+1] - x[i]) + Math.abs(y[i+1] - y[i]);
		    
		    // 制限時間より移動距離のほうが大きい場合失敗判定
		    if (dt < dist) can = false;
		    
		    // 制限時間と移動距離が共に偶数または奇数でない場合失敗判定
		    if (dist % 2 != dt % 2) can = false;
		}
        
        if (can) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
        sc.close();
    }
}

Measured memory_bytes: 91152
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a_sum;
    int b_sum;
    int min = 100000000;

    for(int i = 1 ; i < n ; ++i){
      int a = i;
      int b = n-i;
      a_sum = 0;
      b_sum = 0;
      
      while(n>0){
        a_sum += a%10;
        a = (a-a%10)/10;
        if(a==0) break;
      }
      while(n>0){
        b_sum += b%10;
        b = (b-b%10)/10;
        if(b==0) break;
      }
      
      min = Math.min(min,a_sum+b_sum);
      
      
    }

    System.out.println(min);
    
  }
}

Measured memory_bytes: 35756
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<queue>
#include<string>
#include<time.h>
#include<tuple>
#include<utility>
#include<vector>

using namespace std;
const long mod = 1000000007;

int main() {

	long N; cin >> N;
	long A[200009]; for (int i = 1; i <= N; i++) cin >> A[i];
	bool inball[200009] = {};
	long res = 0;

	for (int i = N; i >= 1; i--) {//iの倍数について考える。
		long link = 0;

		for (int j = 2; i * j <= N; j++) if (inball[i * j]) link++;

		if (link % 2 != A[i]) {inball[i] = true; res++;}

	}

	cout << res << endl;
	for (int i = 1; i <= N; i++) if (inball[i]) cout << i << " ";
}

Measured memory_bytes: 2688
def find_path(x, v, e):
    if len(v) == len(e):
        return 1
    ans = 0
    for xi in e[x - 1]:
        if xi in v:
            continue
        vi = v + [xi]
        ans += find_path(xi, vi, e)
    return ans

n, m = map(int, input().split())
e = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    e[a - 1].append(b)
    e[b - 1].append(a)
ans = find_path(1, [1], e)
print(ans)


Measured memory_bytes: 3064
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

#define POS(x) cout<<((x)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define Pos(x) cout<<((x)?"Possible":"Impossible")<<endl;
#define YES(x) cout<<((x)?"YES":"NO")<<endl;
#define Yes(x) cout<<((x)?"Yes":"No")<<endl;
#define yes(x) cout<<((x)?"yes":"no")<<endl;

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int a[4] = {};
  for(int i = 0; i < 4; i++) cin >> a[i];
  sort(a, a + 4);
  YES(a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP (i, 0, n)

using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    rep (i, n) cin >> a[i];

    long long ans = 0;

    rep (i, n) {
        if (i == 0 && a[i] != 0) ans = -1;
        if (i != 0 && a[i - 1] + 1 < a[i]) ans = -1;
    }

    if (ans == 0) {
        int maxv = 0;
        int v = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (maxv == 0) {
                maxv = v = a[i];
            }
            else {
                v--;
                if (v == 0 || a[i] != v) {
                    ans += maxv;
                    maxv = v = 0;
                    i++;
                }
            }
        }
    }

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


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

char arr[1000000];

int main() {
    scanf("%s", arr);

    long long cb = 0, t = 0;
    for (char *p = arr; *p != '\0'; p++) {
        t += (*p == 'W') * cb;
        cb += *p == 'B';
    }

    printf("%lld\n", t);
}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <functional>
#include <map>
using namespace std;
#define ll long long
#define pp pair<ll, ll>
#define pps pair<ll, string>
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
#define fi first
#define se second
const ll INF = 1e9;
string s;
ll ct, ans;
int main()
{
    cin >> s;
    rep(i, s.size()) if (s[i] == 'W') ans += i - ct, ++ct;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
//#define int long long

struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout <<fixed<<setprecision(12);
        cerr <<fixed<<setprecision(12);
    }
}IoSetup;

typedef long long ll;
typedef pair < int , int >  pii;
static constexpr const signed int INF = 0x3f3f3f3f;
static constexpr const signed long long LINF = 0x3f3f3f3f3f3f3f3fLL;
static constexpr const signed int SMOD = 1000000007;
static constexpr const signed int NMOD = 998244353;
static constexpr const signed int dx[]={1,0,-1,0,1,1,-1,-1};
static constexpr const signed int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T &b){return(a=max(a,b))==b;}
template<class T>bool chmin(T &a, const T &b){return(a=min(a,b))==b;}
inline int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

#define T(x) (x) + 9000;

string s;
int X, Y;
vector<int> v;

int dp[8080][8080*2];



signed main() {

    cin >> s >> X >> Y;

    if(s[s.size()-1] == 'F') s += 'T';
    for(int i = 0, c = 0; i < s.size(); i++) {
        if(s[i] == 'F') c++;
        else v.bash(c), c = 0;
    }
    
    dp[0][9000+v[0]] = true;
    int t = 0;
    for(int i = 2; i < v.size(); i+= 2) {
        t = i;
        for(int j = 0; j < 16000; j++) {
            if(dp[i-2][j]) {
                dp[i][j+v[i]] = true;
                dp[i][j-v[i]] = true;
            }
        }
    }

    bool f = dp[t][9000+X];
    t = 0;
    memset(dp,0,sizeof(dp));

    dp[0][9000] = true;

    for(int i = 1; i < v.size(); i += 2) {
        t = i+1;
        for(int j = 0; j < 16000; j++) {
            if(dp[i-1][j]) {
                dp[i+1][j+v[i]] = true;
                dp[i+1][j-v[i]] = true;                
            }
        }
    }

    f &= dp[t][9000+Y];
    
    cout << (f?"Yes\n":"No\n") ;
    
    return 0;
}



Measured memory_bytes: 510464
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
//#define _0219nice 
using namespace std;
int main() {
#ifdef _0219nice
    freopen("1.in", "r", stdin);
#endif
    int k;
    while (cin >> k) {
        queue<long long> q;
        long long cur;
        for (int i = 1; i < 10; i++) {
            q.push(i);
        }
        for (int i = 0; i < k; i++) {
            cur = q.front();
            q.pop();
            if (cur % 10 > 0) {
                q.push(cur * 10 + cur % 10 - 1);
            }
            q.push(cur * 10 + cur % 10);
            if (cur % 10 < 9) {
                q.push(cur * 10 + cur % 10 + 1);
            }

        }
        cout << cur << endl;
    }
    return 0;
}


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

typedef long long ll;
#define ar array
#define vi vector<int>
#define vvi vector<vector<int>>
#define vll vector<long long>
#define all(x) (x).begin(), (x).end()
#define en '\n'
#define FILL(x, v) memset(x, v, sizeof(x))
#define pb push_back
#define fast                     \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);               \
	cout.tie(NULL);
#define F_OR(i, a, b, s) for (int i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...)       \
	F_ORC(__VA_ARGS__) \
	(__VA_ARGS__)

#define E_ACH2(x, a) for (auto &x : a)
#define E_ACH3(x, y, a) for (auto &[x, y] : a)
#define E_ACH4(x, y, z, a) for (auto &[x, y, z] : a)
#define E_ACHC(...) GET5(__VA_ARGS__, E_ACH4, E_ACH3, E_ACH2)
#define EACH(...)       \
	E_ACHC(__VA_ARGS__) \
	(__VA_ARGS__)

template <typename A, typename B>
inline void chmin(A &a, B b)
{
	if (a > b)
		a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b)
{
	if (a < b)
		a = b;
}

const int mxn = 5e5;
const int M = 1e9 + 7;

ll pw(ll b, ll e)
{
	ll res = 1;
	while (e)
	{
		if (e % 2)
			res = (res * b) % M;
		b = (b * b) % M;
		e >>= 1; // e/=2;
	}
	return res;
}

ll iv[mxn + 1], f1[mxn + 1], f2[mxn + 1];
ll nck(int n, int k)
{
	return f1[n] * f2[k] % M * f2[n - k] % M;
}

int main()
{
	fast;
	int n;
	cin >> n;
	cout << (n + 1) / 2;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
double eps = 1e-8;
ll cost;
struct milk{
	ll v;
	double id;	
	ll com;
	bool operator < (const milk& a) const {
		if(this->com < a.com)return true;
		else if(this->com == a.com)return this->id < a.id;
		return false;
	}
}a[4];


int main(int argc, char** argv) {
	//freopen("in.txt","r",stdin);
	a[0].id = 0.25, a[1].id = 0.5, a[2].id = 1, a[3].id = 2;
	for(int i=0;i<4;i++) {
		cin>>a[i].v;
		if(i == 0)a[i].com = 8 * a[i].v;
		else if(i == 1)a[i].com = 4 * a[i].v;
		else if(i == 2)a[i].com = 2 * a[i].v;
		else a[i].com = a[i].v;
	}
	ll need;     cin>>need;
	sort(a, a + 4);
	//cout<<a[1].id<<endl;
	if(a[0].id <= 1.0) {
		if(a[0].id == 0.25)need *= 4;
		else if(a[0].id == 0.5)need *= 2;
		cost = need * a[0].v;
		cout<<cost<<endl; 
	}else {
		cost = (need / 2) * a[0].v;
		if(need % 2 == 0) {	
			cout<<cost<<endl;
		}else {
			if(a[1].id == 0.25)need = 4;
			else if(a[1].id == 0.5)need = 2;
			else need = 1;
			cost += need * a[1].v;
			cout<<cost<<endl;
		}
	}
	
	return 0;
}

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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

void Main()
{
    ll n;
    cin >> n;
    vll a(n), s(n + 1);
    rep(i, n) cin >> a[i];

    rep(i, n) s[i + 1] = s[i] + a[i];

    ll mid1 = s.back() / 2;
    ll mid2 = dup(s.back(), (ll)2);
    ll ans = LINF;
    rep(i, n + 1)
    {
        ans = min((long long)ans, llabs(s[i] - mid1) * (ll)2);
        ans = min((long long)ans, llabs(s[i] - mid2) * (ll)2);
    }
    if (s.back() % 2 == 1)
    {
        ++ans;
    }
    cout << ans << endl;
}

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


Measured memory_bytes: 3456
import copy
N, W = map(int, input().split())

WV = [map(int,input().split()) for _ in range(N) ]


#dp[w] = max cost
costs = [-1 for _ in range(W + 1)]
costs[0] = 0

for w, v in WV:
    for index in reversed(range(W + 1)):
        if costs[index] == -1:
            continue
        if index + w > W:
            continue
        costs[index + w] = max(costs[index] + v, costs[index + w])


print(max(costs))



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

int main()
{
	int n = 0, a[100] = { 0 }, v = 0;

	cin >> n;

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

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

		int j = 0;

		v = a[i];
		j = i - 1;

		while (j >= 0 && a[j] > v) {
			a[j + 1] = a[j];
			a[j] = v;
			j--;
		}

		for (int k = 0; k < n - 1; k++)
			cout << a[k] << " ";

		cout << a[n - 1] << endl;
	}

		
	return 0;
}

Measured memory_bytes: 3104
s = list(input())
t = list(input())
s.sort()
t.sort(reverse=True)
sa = "".join(s)
ta = "".join(t)

ans = "No"
l = [sa, ta]
l.sort()
if l[1] == ta:
    ans = "Yes"
if l[0] == l[1]:
    ans = "No"
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <stack>
#include <cassert>
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
typedef long long int ll;
const ll  MOD = 1000000007;
typedef pair<ll,ll> P;
const ll INF = 100100100100100100;

ll N;
string s;
ll dp[500500];
int main(){
  cin >> N;
  cin >> s;
  ll t_cnt = 0;
  for(int i=1;i<=N;i++){
    dp[i] = max(dp[i],dp[i-1]);
    if(i<=N-2){
      if(s[i-1] == '1' && s[i] == '0' && s[i+1] == '1'){
        dp[i+2] = max(dp[i+2],1+t_cnt + dp[i-t_cnt-1]);
        if(t_cnt>0) dp[i+2] = max(dp[i+2],t_cnt + dp[i-t_cnt]);
        t_cnt = 0;
        ll k = 0;
        while(s[i+1+k] == '1'){
          dp[i+2+k] = max(dp[i+2+k],k+1 + dp[i-1]);
          k++;
        }
      }
      else if(s[i-1] == '1') t_cnt++;
      else if(s[i-1] == '0') t_cnt = 0;
    }
  }
  rep(i,N){
    cerr << dp[i+1] << endl;
  }
  cout << dp[N] << endl;
}


Measured memory_bytes: 4740
#include <bits/stdc++.h>
#define reg register

using namespace std;

typedef long long ll;
const int maxn = 100005;

inline ll read() {
    reg ll s = 0, t = 0; reg char ch = getchar();
    while (!isdigit(ch)) t |= ch == '-', ch = getchar();
    while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return t ? -s : s;
}

int main() {
    string s, t;
    cin >> s >> t;
    reg int Ans = 0;
    for (reg int i = 0; i < (int)s.size(); i++)
        if (s[i] == t[i]) Ans++;
    cout << Ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
typedef long long ll;

int main(){
  int N,Q;
  string S;
  cin >> N >> Q;
  cin >> S;
  int l[Q],r[Q];
  for(int i=0;i<Q;i++){
    cin >> l[i] >> r[i];
  }
  int sum[N];
  for(int i=0;i<N;i++){
    sum[i]=0;
  }
  for(int i=0;i<N-1;i++){
    if(S[i]=='A' && S[i+1]=='C') sum[i+1]=sum[i]+1;
    else sum[i+1]=sum[i];
  }
  for(int n=0;n<Q;n++){
    cout << sum[r[n]-1]-sum[l[n]-1] << endl;
  }
}


Measured memory_bytes: 4420
H, W = map(int, input().split())
S = H * W
ans = float('inf')
for h in range(1, H):
    Sa = h * W
    Sb = (H - h) // 2 * W
    Sc = S - Sa - Sb
    diff1 = max(abs(Sa-Sb), abs(Sb - Sc), abs(Sc - Sa))
    Sb = (H - h) * (W // 2)
    Sc = S - Sa - Sb
    diff2 = max(abs(Sa-Sb), abs(Sb - Sc), abs(Sc - Sa))
    ans = min(ans, diff1, diff2)
for w in range(1, W):
    Sa = H * w
    Sb = (W - w) // 2 * H
    Sc = S - Sa - Sb
    diff1 = max(abs(Sa - Sb), abs(Sb - Sc), abs(Sc - Sa))
    Sb = (W - w) * (H // 2)
    Sc = S - Sa - Sb
    diff2 = max(abs(Sa - Sb), abs(Sb - Sc), abs(Sc - Sa))
    ans = min(ans, diff1, diff2)
print(ans)



Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,num=0;
    string s;
    cin>>n>>s;
    for(int i=1;i<n;i++){
    	if(s[i]=='E')num++;
    }
    int x=num;
    for(int i=1;i<n;i++){
    	if(s[i-1]=='W')num++;
    	if(s[i]=='E')num--;
    	x=min(x,num);
    }
    cout <<x<<endl;

    return 0;
}


Measured memory_bytes: 900
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

int main(){
  int N, C;
  cin >> N >> C;
  pair<pair<int, int>,int> time[N];
  int s,e,c;
  rep(i,N){
    cin >>  s >> e >> c;
    time[i]=mp(mp(s,e),c);
  }
  //  cout << "" << endl;
  sort(time,time+N);
  vector<pair<int, int> > endt;
  endt.pb(mp(0,0));
  rep(i,N){
    int ts=(time[i].first).first;
    int te=(time[i].first).second;
    int tc=(time[i].second);
    rep(j,endt.size()){
      if(endt[j].first<ts || (endt[j].first==ts && endt[j].second==tc)){
	endt[j]=mp(te,tc);
	sort(endt.begin(),endt.end());
	break;
      }
      else if(j==endt.size()-1){
	endt.pb(mp(te,tc));
	break;
      }
    }
  }
  cout << endt.size() << endl;      
  return 0;

}


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

using namespace std;

int main() {
  int n; cin >> n;
  vector <int> v(n + n);
  for (auto &x : v) cin >> x;
  sort(v.begin(), v.end());
  int ans = 0;
  for (int i = 0; i < n + n; i += 2) {
    ans += v[i];
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
int dp[100001],h[100001];
int main(){
  int N,K;
  set<int> s;
  set<int>::iterator it;
  cin >> N >> K;
  for(int i=0;i<N;i++) cin >> h[i];
  dp[0]=0;
  dp[1]=abs(h[1]-h[0]);
  for(int i=2;i<N;i++)
  {
  	for(int j=i-1,jc=1;j>=0 && jc<=K;j--,jc++)
  	{
  		s.insert(abs(h[i]-h[j])+dp[j]);
  	}
  	it = s.begin();
    dp[i]=*it;
    s.clear();
  }
  cout << dp[N-1] << endl;
  return 0;
}

Measured memory_bytes: 1024
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int ans=0;			double wk=0;	int wk1=0;
		int N=sc.nextInt();	
		int D=sc.nextInt();	

		int X [][] = new int[N][D];		
		for(int i=1; i<=N;i++){		
			for(int j=1;j<=D;j++){	
				X [i-1][j-1]=sc.nextInt();	
			}			
		}
		for(int i=1; i<N;i++){		
			for(int j=i+1;j<=N;j++){	
				for(int k=1;k<=D;k++){	
				wk=(X [i-1][k-1]-X [j-1][k-1])*(X [i-1][k-1]-X [j-1][k-1])+wk;
				}	
				wk=Math.sqrt(wk);
				if(wk==Math.ceil(wk)){ans=ans+1;}
				wk=0;
			}			
		}	
		
	
	System.out.println(ans);
	}
}

Measured memory_bytes: 23508
N = gets.to_i
ss, sst = [], Array.new(N){Array.new(N)}
N.times do |i|
    ss[i] = gets.chomp
    N.times {|j| sst[j][i] = ss[i][j]}
end
sst.map!{|row| row.join}
sum = 0
N.times do |i|
    sum += 1 if N.times.all?{|j|ss[j].to_sym == sst[j].to_sym}
    ss.map!{|str| str[-1] + str[0...-1]}
    sst.rotate!(-1)
end
puts sum*N

Measured memory_bytes: 25340
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
#define endl '\n'
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=998244353;
signed main(){
    ll n;cin>>n;
    priority_queue<pair<pll,ll>,vector<pair<pll,ll> >,greater<pair<pll,ll> > >miq;
    priority_queue<pair<pll, ll> >maq;
    priority_queue<pair<pll,ll>,vector<pair<pll,ll> >,greater<pair<pll,ll> > >miq2;
    priority_queue<pair<pll, ll> >maq2;
    ll mal=0;
    ll mir=0;
    rep(i,n){
        ll l,r;cin>>l>>r;
        miq.push(mp(mp(r,l),i));
        maq.push(mp(mp(l,r),i));
        mal=max(mal,l);
        mir=min(mir,r);
    }
    maq2=maq;
    miq2=miq;
    ll ans=0,ans1=0;
    set<ll>st;
    ll now=0;
        while(st.size()<n){
            while(st.find(maq.top().se)!=st.end()){
                maq.pop();
            }
            pll k=maq.top().fi;
            ll idx=maq.top().se;
            ll l=k.fi,r=k.se;
            maq.pop();
            if(now<l){
                ans+=l-now;
                now=l;
            }else if(now>r){
                ans+=now-r;
                now=r;
            }
            st.insert(idx);
            if(st.size()==n)break;
            while(st.find(miq.top().se)!=st.end()){
                miq.pop();
            }
            k=miq.top().fi;
            idx=miq.top().se;
            l=k.se,r=k.fi;
            miq.pop();
            if(now<l){
                ans+=l-now;
                now=l;
            }else if(now>r){
                ans+=now-r;
                now=r;
            }
            st.insert(idx);
        }
    maq=maq2,miq=miq2;
    st.clear();
    ans+=abs(now);
    now=0;
        while(st.size()<n){
            while(st.find(miq.top().se)!=st.end()){
                miq.pop();
            }
            pll k=miq.top().fi;
            ll idx=miq.top().se;
            ll l=k.se,r=k.fi;
            miq.pop();
            if(now<l){
                ans1+=l-now;
                now=l;
            }else if(now>r){
                ans1+=now-r;
                now=r;
            }
            st.insert(idx);
            if(st.size()==n)break;
            while(st.find(maq.top().se)!=st.end()){
                maq.pop();
            }
            k=maq.top().fi;
            idx=maq.top().se;
            l=k.fi,r=k.se;
            maq.pop();
            if(now<l){
                ans1+=l-now;
                now=l;
            }else if(now>r){
                ans1+=now-r;
                now=r;
            }
            st.insert(idx);
        }
    ans1+=abs(now);
    cout<<max(ans,ans1)<<endl;
}

Measured memory_bytes: 15028
//B

#include<stdio.h>

int main (void){

    char s[102],c;
    int k,i,count=0;
    int is;
    int check=0;

    scanf("%d",&k);
    scanf("%c",&c);

    for(i=0;i<=101;i++){
        scanf("%c",&s[i]);
        if(s[i]=='\n'){
            break;
        }
    }

    if(i<=k){
        for(is=0;is<i;is++){
            printf("%c", s[is]);
        }
        //printf("%s",s);
    }else{
        for(i=0;i<k;i++) {
            printf("%c", s[i]);
        }
        printf("...");
    }



    return 0;
}

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

long func(long b, long n)
{
    if (b<=1) return -1;
    long res=0;
    while (n>0) {
        res+=n%b;
        n/=b;
    }
    return res;
}

int main()
{
    long n, s; cin>>n>>s;

    if (n==s) { cout<<n+1<<endl; return 0; }

    for(long b=2; b*b<=n; ++b) {
        if (func(b, n)==s) {
            cout<<b<<endl;
            return 0;
        }
    }
    unsigned long res=-1;
    for(long p=1; p*p<=n; ++p) {
        unsigned long b=(n-s+p)/p;
        if (func(b, n)==s)
            res=min(res, b);
    }
    cout<<(long)res<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}

int main() {
    int n;
    cin >> n;
    set<string> st;
    rep(i, n) {
        string s;
        cin >> s;
        st.insert(s);
    }
    cout << sz(st) << endl;
}

Measured memory_bytes: 19176
//
// Created by 26019 on 2020/6/7/007.
//

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    while (n) {
        if (n%10 == 7) {
            cout << "Yes";
            return 0;
        }
        n /= 10;
    }
    cout << "No";
    return 0;
}


Measured memory_bytes: 3128
main = print =<< solver <$> readLn <*> (map read . words <$> getLine) <*> (map read . words <$> getLine)

solver :: Int -> [Int] -> [Int] -> Double
solver n t v = (/8.0) $ realToFrac (sum xs)
    where
        ts = scanl (+) 0 t
        pln = zip ts (0 : v)
        nln = zip ts (v ++ [0])
        flat_xs = concat $ zipWith (\x y -> (take (x * 2)) (repeat (4 * y))) t v
        xs = zipWith f [1..(last ts * 2)] flat_xs
        filtmap g h = (fmap h) . (filter g)
        f x y = minimum ((fmap (\(a, b) -> 4*b + 2*x - 4*a - 1) (filter ((x >) . (2*) . fst) pln)) ++ (fmap (\(a, b) -> 4*b + 4*a - 2*x + 1) (filter ((x <=) . (2*) . fst) nln)) ++ [y])

Measured memory_bytes: 1020
# forしながらif、ifでないときはforしないので、計算量減
# 初期入力　　２０２０－０７２７　21：50
from collections import Counter
import sys
input = sys.stdin.readline  #文字列では使わない
N = int(input())
*S, =input().strip()
"""
c =Counter(S)
ans =combinations_count(N, 3) -len(c)
"""
count =0
x100=0
x10=0
x1=0
for i in range(10):
    if str(i) in S:
        x100 =S.index(str(i)) +1
        for j in range(10):
            if str(j) in S[x100:]:
                x10 =S[x100:].index(str(j)) +1
                for k in range(10):
                    if str(k) in S[x100 +x10:]:
                        x1 =S[x100+x10:].index(str(k)) +1
                        count +=1
                        #print("aa",i,j,k,"bb",x100,x100+x10,x100+x10+x1)

print(count)

Measured memory_bytes: 9676
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int main(void){
  int i,l;
  char s[200002],t[200002];
  char R1[30],R2[30];
  for(i=0;i<30;i++){
    R1[i]=-1;R2[i]=-1;
  }
  scanf("%s",s);
  scanf("%s",t);
  l=strlen(s);
  for(i=0;i<l;i++){
    if(R1[s[i]-'a']>0){
      if(t[i]!=R1[s[i]-'a']){
	printf("No\n");
	return 0;
      }
    }
    if(R2[t[i]-'a']>0){
      if(R2[t[i]-'a']!=s[i]){
	printf("No\n");
	return 0;
      }
    }
    if(R1[s[i]-'a']<0)
      R1[s[i]-'a']=t[i];
    if(R2[t[i]-'a']<0)
      R2[t[i]-'a']=s[i];
  } 
  printf("Yes\n");
  return 0;
}

Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
     
using namespace std;
     
typedef long long ll;
typedef pair<int, int> pii;
     
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
     
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());

const ll MOD = (ll)1e9 + 7;

const int N = (int)1e5 + 9;
int cnt[N];

int ab(int x){
    return max(x,-x);
}

int main(){
    fastIO;
    int n;
    cin >> n;
    int a;
    for(int i = 1; i <= n ;i ++ ){
        cin >> a;
        cnt[a] ++ ;
    }
    int shd;
    for(int i = 1; i <= n; i ++ ){
        shd = ab((i-1)-(n-i));
        cnt[shd] -- ;
        if(cnt[shd] < 0){
            cout << 0 << "\n";
            exit(0);
        }
    }
    ll res = 1ll;
    for(int i = 0 ; i < n/2; i ++ ){
        res=(res*2ll)%MOD;
    }
    cout << res;
    return 0;
}

Measured memory_bytes: 640
A, B, C, X, Y = gets.chomp.split(" ").map(&:to_i)

ans = 0
if A+B < 2*C then
  ans += [X, Y].min * (A+B)
else
  ans += [X, Y].min * 2 * C
end
if X > Y then
  if A < 2*C then
    ans += (X - Y) * A
  else
    ans += (X - Y) * 2 * C
  end
else
  if B < 2*C then
    ans += (Y - X) * B
  else
    ans += (Y - X) * 2 * C
  end
end

puts ans


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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef map<ll, ll> mii;
const int MOD = 1e9 + 7;

#define fastIO() \
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define mp make_pair 

int main() {
    ll x;
    cin >> x;
    ll a = x / 500;
    x %= 500;
    ll b = x / 5;
    ll ans = 1000 * a + 5 * b;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class A
{
    public static void Main(string[] args)
    {
        int t = 1;
        while (t > 0)
        {
            
            int n = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            bool ok = true;
            if (n % 2 == 1)
                ok = false;
            else
            {
                int mid = n / 2;
                for(int i = 0; i < mid; i++)
                {
                    if(s[i] != s[i + mid])
                    {
                        ok = false;
                    }
                }
            }
            Console.WriteLine(ok ? "Yes" : "No");
            t--;
        }
    }
}

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

int main()
{
  int h, w;
  vector<vector<char>> a(102, vector<char>(102, '#'));

  cin >> h >> w;
  for (int i = 1; i <= h; i++)
  {
    for (int j = 1; j <= w; j++)
      cin >> a[i][j];
  }
  for (int i = 0; i <= h + 1; i++)
  {
    for (int j = 0; j <= w + 1; j++)
      cout << a[i][j];
    cout << endl;
  }
}

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

#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define REP(i,a,b) for(int i=a; i<b; i++)

int main()
{
    FastIO

    int n;
    cin >> n;
    double p[n];
    REP(i,0,n)
        cin >> p[i];
    double dp[n+1][n+1];
    dp[0][0] = 1;
    REP(i,1,n+1)
        dp[0][i] = 0;
    REP(i,1,n+1)
        dp[i][0] = (1 - p[i-1])*dp[i-1][0];
    REP(i,1,n+1)
    {
        REP(j,1,n+1)
        {
            dp[i][j] = dp[i-1][j-1]*p[i-1] + dp[i-1][j]*(1-p[i-1]);
        }
    }
    double probability = 0;
    REP(i,(n-1)/2 + 1, n+1)
        probability += dp[n][i];
    cout << fixed << setprecision(10) << probability << "\n";
    return 0;
}

Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2202;
int n,i,j,cnt,pr[N],a[100002],b[100002][2],t,tot,x,y,k,c1,c2,ans;
map<int,int>c,used;
bool vis[N];
signed main(){
	scanf("%lld",&n);
	for (i=1;i<=n;i++) scanf("%lld",&a[i]);
	for (i=2;i<N;i++)
		if (!vis[i]){
			pr[tot++]=i;
			for (j=i+i;j<N;j+=i) vis[j]=1;
		}
	for (i=1;i<=n;i++){
		x=y=1;
		for (j=0;j<tot;j++)
			if (a[i]%pr[j]==0){
				cnt=0;
				while (a[i]%pr[j]==0) cnt++,a[i]/=pr[j];
				if ((cnt%=3)==0) continue;
				for (k=0;k<cnt;k++) x*=pr[j];
				for (k=cnt;k<3;k++) y*=pr[j];
			}
		t=sqrt(a[i]);
		if (t*t==a[i]) x*=t*t,y*=t;
		else x*=a[i],y*=a[i]*a[i];
		b[i][0]=x,b[i][1]=y;
		c[x]++;
	}
	for (i=1;i<=n;i++){
		c1=b[i][0],c2=b[i][1];
		if (used[c1] || used[c2]) continue;
		x=c[c1]>c[c2]?c1:c2,used[x]=1;
		ans+=x==1?1:c[x];
	}
	printf("%lld",ans);
}

Measured memory_bytes: 27648
#include<iostream> 
#include<cstring> 
#include<cstdlib> 
using namespace std; 
  

void lcs( string X, string Y, int m, int n ) 
{ 
   int L[m+1][n+1]; 
  
 
   for (int i=0; i<=m; i++) 
   { 
     for (int j=0; j<=n; j++) 
     { 
       if (i == 0 || j == 0) 
         L[i][j] = 0; 
       else if (X[i-1] == Y[j-1]) 
         L[i][j] = L[i-1][j-1] + 1; 
       else
         L[i][j] = max(L[i-1][j], L[i][j-1]); 
     } 
   } 
  
 
   int index = L[m][n]; 
  

   char lcs[index+1]; 
   lcs[index] = '\0';
  
  
   int i = m, j = n; 
   while (i > 0 && j > 0) 
   { 
    
      if (X[i-1] == Y[j-1]) 
      { 
          lcs[index-1] = X[i-1];  
          i--; j--; index--;     
      } 
  
     
      else if (L[i-1][j] > L[i][j-1]) 
         i--; 
      else
         j--; 
   } 
  
   
   cout  << lcs; 
} 
  

int main() 
{ string X,Y;
  cin >> X;
  cin >> Y;
  
  lcs(X, Y, X.length(), Y.length()); 
  return 0; 
} 


Measured memory_bytes: 35456
l = input().split(" ")
N = int(l[0])
K = int(l[1])
ts = 0
for b in range(K + 1, N + 1):
  ts += (N // b) * (b - K) \
      + max(0, N % b - K + 1)
  if K == 0:
    ts -= 1
print(ts)


Measured memory_bytes: 2940
function division(x)
	y = x
	a = Int[]
	k = 2
	while k <= sqrt(x)
		if y%k == 0
			push!(a,k)
			y = div(y,k)
		else
			k += 1
		end
	end
	if sqrt(x) < y
		push!(a,y)
	end
	a
end

function main()
	n = parse(Int, readline())
	d = Dict{Int,Int}()
	for i in 2:n
		a = division(i)
		for j in 1:length(a)
			if haskey(d,a[j])
				d[a[j]] += 1
			else
				d[a[j]] = 1
			end
		end
	end
	k = 1
	for v in values(d)
		k = k*(v+1)%1000000007
	end
	print(k)
end

main()

Measured memory_bytes: 111896
#include <vector>
#include <iostream>

using namespace std;

int main(){
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int h = (h2 - h1) * 60;
    int m = m2 - m1 + h;
    cout << m - k << endl;
}

Measured memory_bytes: 3600
#include <iostream>
//#include <iomanip>
//#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

ll two(ll a){
	ll res = 0 ;
	while(a%2==0){
		res++ ;
		a /= 2 ;
	}
	return res ;
}

ll pow(ll a,ll b){
	ll res = 1 ;
	for(int i=0;i<b;i++) res *= a ;
	return res ;
}

int main(){
	ll n,m ;
	cin >> n >> m ;
	ll cnt = -1 ;
	ll a=1,b=1 ;
	ll sub ;
	for(int i=0;i<n;i++){
		ll num ;
		cin >> num ;
		if(cnt==-1){
			cnt = two(num) ;
			sub = pow(2,cnt) ;
			a = lcm(a,num) ;
			b = lcm(b,num/2) ;
		}
		else{
			if(num%sub==0&&num/sub%2==1){
				a = lcm(a,num) ;
				b = lcm(b,num/2) ;
				if(b>m){
					cout << 0 << endl ;
					return 0 ;
				}
			}else{
				cout << 0 << endl ;
				return 0 ;
			}
		}
	}
//	cout << a << " " << b << endl ;
	cout << (m-b+a)/a << endl ;
}


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

class UnionFind {
private:
    vector<int> Parent;
public:
    UnionFind(int N){
        Parent = vector<int>(N, -1);
    }
    
    int root(int A){
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
        // ↑ここがUnion-Findで気にしたいところ
    }
    
    int size(int A){
        return - Parent[root(A)];
    }
    
    bool connect(int A, int B){
        A = root(A);
        B = root(B);
        if (A == B) return false;
        if (size(A) < size(B)) swap(A,B);
        Parent[A] += Parent[B];
        Parent[B] = A;
        return true;
    }
};

int main(){
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    for (int i=0; i<M; i++){
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
    
    vector<long long> ans(M);
    ans[M-1]=(long long)N*(N-1)/2;
    
    UnionFind uf(N);
    
    for (int i=M-1;i>=1;i--){
        ans[i-1] = ans[i];
        if (uf.root(A[i]) != uf.root(B[i])){
            ans[i-1] -= (long long)uf.size(A[i])*uf.size(B[i]);
            uf.connect(A[i], B[i]);
        }
    }
    
    for (int i=0;i<M;i++){
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 3328
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

D = [-1]*N
def bfs(s):
    isBi = True
    q = [s]
    D[s] = 0
    d = 0
    while q:
        qq = []
        d ^= 1
        for p in q:
            for np in graph[p]:
                if D[np] == -1:
                    D[np] = d
                    qq.append(np)
                elif D[np] != d:
                    isBi = False
        q = qq
    return isBi

a = 0
b = 0
c = 0
for n in range(N):
    if D[n] == -1:
        if len(graph[n]) == 0:
            c += 1
        elif bfs(n):
            a += 1
        else:
            b += 1

ans = 2*a**2 + 2*a*b + b**2 + 2*N*c - c**2
print(ans)

Measured memory_bytes: 62940
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    bool flag = false;
    while(n > 0) {
        if((n % 10 ) == 7) {
            flag = true;
        }
        n /= 10;
    }
    if(flag) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}




Measured memory_bytes: 3584
#import math
#import bisect
#import numpy as np
#import itertools
#import copy
#import collections
import sys

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

def main():
    n, m, k = list(map(int,ipti().split()))
    r = UnionFind(n)
    rr = [0] * n
    fr = [[0] * 2 for _ in range(m)]
    bl = [[0] * 2 for _ in range(k)]

    for i in range(m):
        a, b = list(map(int,ipti().split()))
        fr[i][0] = a - 1
        fr[i][1] = b - 1
        r.union(fr[i][0], fr[i][1])

    for i in range(k):
        a, b = list(map(int,ipti().split()))
        bl[i][0] = a - 1
        bl[i][1] = b - 1

    for i in range(m):
        a, b = fr[i][0], fr[i][1]
        if r.same(a, b):
            rr[a] += 1
            rr[b] += 1

    for i in range(k):
        a, b = bl[i][0], bl[i][1]
        if r.same(a, b):
            rr[a] += 1
            rr[b] += 1

    ans = [0] * n

    for i in range(n):
        ans[i] = r.size(i) - rr[i] - 1

    print(*ans)

if __name__ == '__main__':
    main()


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

signed main(){
  int N;
  cin>>N;
  int out=1;
  for(int i=1;i<=3500&&out;i++){
    for(int j=i;j<=3500&&out;j++){
      if(4*i*j-N*j-N*i>0){
        if(N*i*j%(4*i*j-N*j-N*i)==0){
          out=0;
          cout<<i<<" "<<j<<" "<<N*i*j/(4*i*j-N*j-N*i)<<endl;
        }
      }
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
typedef long double ld;
using ll=long long;
using namespace std;
const auto mod=1e9+7;



int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  
  int n,m,sum=0; cin >> n >> m;
  vector<int> a(n); 
  rep(i,0,n){
  	cin >> a[i];
  	sum+=a[i];
  } 
  sort(a.rbegin(),a.rend());
  string ans="Yes";
  double flag = (double)1/4/m;
  rep(i,0,m){
  	if((double)a[i]/sum< flag) ans="No";
  } 
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int A(int x){
  int i;
  if ( x < 2 ) return 0;
  else if ( x == 2 ) return 1;
  if ( x % 2 == 0 ) return 0;
  for ( i = 3; i*i <= x; i+=2 ){
    if ( x % i == 0 ) return 0;
  }
  return 1;
}

int main(){
  int n, x, i;

  int cnt = 0;
  scanf("%d", &n);
  
  for ( i = 0; i < n; i++ ){
    scanf("%d", &x);
    if ( A(x) ) cnt++;
  }
  printf("%d\n", cnt);
  
  return 0;
}


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

int main(){
  string s;
  int p[20],l,flag,max;
  char hoge;
  cin >> s;
  l = s.size();
  flag = 0;
  max = 0;
  for(int i = 0;i<l;i++){
    hoge = s[i];
    if(hoge == 'A' || hoge == 'C' || hoge == 'G' || hoge == 'T'){
      flag++;
    }else{
      if(flag > 0 && max < flag) max = flag;
      flag = 0;
    }
  }
  if(flag > 0 && max < flag) max = flag;
  cout << max << endl;
  return 0;
}

Measured memory_bytes: 256
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
  let mut s = String::new();
  std::io::stdin().read_line(&mut s).ok();
  s.trim().split_whitespace()
    .map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
  let hw: Vec<usize> = read_vec();

  for r in 1..hw[0] + 1 {
    let row: Vec<String> = read_vec();

    for (i, s) in row.iter().enumerate() {
      if s == "snuke" { println!("{}{}", ((i as u8) + ('A' as u8)) as char, r) }
    }
  }
}


Measured memory_bytes: 4352