akhauriyash/Code-Regression huggingface dataset:
//arc060.cpp
//Sat May 16 11:51:31 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

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

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

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

	ll count[n+1][6001];
	for (ll i=0;i<n+1;i++){
		for (ll j=0;j<6001;j++){
			count[i][j] = 0;
		}
	}

	for (ll i=1;i<n+1;i++){
		for (ll j=0;j<6001;j++){
			count[i][j] = count[i-1][j];
			if (j-x[i-1]>=0 && j-x[i-1]<=6000){
				count[i][j] += count[i-1][j-x[i-1]];
			}
		}
		count[i][x[i-1]+3000]++;
	}


	cout << count[n][3000]<< endl;
//	printf("%.4f\n",ans);
}

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

int main(){
	int K;
    string S;
	cin>>K;
    cin>>S;
	if(S.size()<=K) cout<<S<<endl;
    else{
    	for(int i=0;i<K;i++){
    		cout<<S.at(i);
        }
      cout<<"..."<<endl;
    }
}

Measured memory_bytes: 3640
def judge(s):
    ok = True
    n = len(s)
    m = (n - 1) // 2
    if (n == 1):
        ok = True
    else:
        if (m == 0):
            ok = (s[0] == s[1])
        else:
            for i in range(m):
                if s[i] != s[(n-1)-i]:
                    ok = False
                    break
    return ok

def strong_judge(s):
    ok = judge(s)
    n = len(s)
    m = (n - 1) // 2
    kf = (m - 1) // 2
    kb = m + kf + 1
    sf = s[0:m]
    sb = s[(m + 1):n]
    if ok:
        ok = judge(sf) and judge(sb)
    return ok

s = str(input())

if ((len(s) % 2 == 0) or (len(s) > 99) or (len(s) < 3)):
    print("No")
else:
    if strong_judge(s):
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 3064
#include <iostream>
using namespace std;
long long p[65],a[100005];
void insert(long long x)
{
 for(int i=60;i>=0;i--)
 {
  if(!(x>>i))continue;
  if(!p[i])
  {
   p[i]=x;
   break;
  }
  x^=p[i];
 }
}
long long query()
{
 long long ans=0;
 for(int i=60;i>=0;i--)
  ans=max(ans,ans^p[i]);
 return ans;
}
int main()
{
 int n;
 cin>>n;
 long long sum=0,ans=0;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i];
  sum^=a[i];
 }
 for(int i=1;i<=n;i++)
 {
  a[i]&=(~sum);
  insert(a[i]);
 }
 ans=query();
 cout<<ans*2+sum<<endl;
 return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#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()
 
using namespace std;
using ll = long long;
 
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; }

struct edge { int to; int cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int MOD = 1e9+7;
const double EPS = 1.0e-12;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

const int MAX_V = 1e5+10;

int V,E;
vector<int> g[MAX_V];
vector<int> sv;

void tSort() {
	int h[MAX_V]; memset(h, 0, sizeof(h));
	for(int i = 0; i <= V; i++) if(g[i].size()) for(auto& j : g[i]) h[j]++;

    stack<int> st;
    for(int i = 0; i <= V; i++) if(g[i].size() && h[i] == 0) st.push(i);
    while(st.size()) {
        int i = st.top(); st.pop();
        sv.push_back(i);
        for(auto& j : g[i]) {
            h[j]--;
            if(h[j] == 0) st.push(j);
        }
    }
}

int dp[100010];

int main(){
	cin >> V >> E;
	rep(i,E){
		int x,y;
		cin >> x >> y;
		g[x].push_back(y);
	}

	tSort();
	//for(auto& j : sv) cout << j << endl;

	for(auto& i : sv){
		for(auto j : g[i])
		chmax(dp[j],dp[i]+1);
	}

	int ans = 0;
	for(int i = 1; i <= V; i++) ans = max(ans,dp[i]);
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 7032
#include<stdio.h>
int main(){
	int a,b,c,A,B,C;
	scanf("%d %d %d",&a,&b,&c);
	A=a;
	B=b;
	C=c;
	if(a>b && b>=c){
		c=A;
		a=C;
	}
	else if(a>b && a>=c){
		a=B;
		b=C;
		c=A;
	}
	else if(a>b){
		a=B;
		b=A;
	}
	else if(b>c){
		b=C;
		c=B;
	}
	printf("%d %d %d\n",a,b,c);
	return 0;
}


Measured memory_bytes: 2104
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

a, b, c, d = list(map(int, input().split()))

_ac = (a-1) // c # a以下のcの倍数の数
_bc = b // c # b以下のcの倍数の数

_ad = (a-1) // d # a以下のdの倍数の数
_bd = b // d # b以下のdの倍数の数

_acd = (a-1) // lcm(c,d) # a以下のcdの倍数の数
_bcd = b // lcm(c,d) # b以下のcdの倍数の数

m = (b-a+1) - ((_bc-_ac) + (_bd-_ad) - (_bcd-_acd))
print(m)

Measured memory_bytes: 66156
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long double ld;
const ld theta=M_PI/3.0;
typedef pair<ld,ld> P;
void solve(int n,P a,P b){
	if(!n)	return;
	P s,t,u;
	s.x=(2.0*a.x+b.x)/3.0;
	s.y=(2.0*a.y+b.y)/3.0;
	u.x=(a.x+2.0*b.x)/3.0;
	u.y=(a.y+2.0*b.y)/3.0;
	P vec=make_pair(u.x-s.x,u.y-s.y);
	t.x=vec.x*cosl(theta)-vec.y*sinl(theta)+s.x;
	t.y=vec.x*sinl(theta)+vec.y*cosl(theta)+s.y;
	n--;
	solve(n,a,s);
	printf("%.15Lf %.15Lf\n",s.x,s.y);
	solve(n,s,t);
	printf("%.15Lf %.15Lf\n",t.x,t.y);
	solve(n,t,u);
	printf("%.15Lf %.15Lf\n",u.x,u.y);
	solve(n,u,b);
}
int main(){
	int n;	cin>>n;
	P a=make_pair(0,0),b=make_pair(100,0);
	printf("%.15Lf %.15Lf\n",a.x,a.y);
	solve(n,a,b);
	printf("%.15Lf %.15Lf\n",b.x,b.y);
	return 0;
}

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

int main() {
  int n,s,t,u;
  cin >> n;
  s = 0;
  t = 0;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a.at(i);
    if(a.at(i)%2==0){
      s++;
    }
    if(a.at(i)%4==0){
      t++;
    }
  }
  u = s -t;
  if(2*t >= n && n%2 == 0){
    cout << "Yes" << endl;
  }
  else if(2*t +1 >= n && n%2 == 1){
    cout << "Yes" << endl;
  }
  else if(s == n){
    cout << "Yes" << endl;
  }
  else if(2*t  + u >= n){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 640
#include <bits/stdc++.h> 
using namespace std; 
//#define endl "\n";
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
const long long int mod=pow(10,9)+7;


vector<vector<int>>g;
vector<bool>v;
int dfs(int u) 
{
    ll ans=0;
    v[u] = true;          
    ans++;
    for (int x : g[u])      
    {
        if (!v[x])         
            ans+=dfs(x);       
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll n,e;
	cin>>n>>e;
	v.assign(n,false);
    g.assign(n, vector<int>());
	for(int i=0;i<e;i++)
	{
	    ll x,y;
	    cin>>x>>y;
	    x--;y--;
	    g[x].push_back(y);
	    g[y].push_back(x);
	}
	ll max=0;
	for(int i=0;i<n;i++)
	{
	    if(!v[i])
	    {
	        ll mx=dfs(i);
	        if(max<mx)
	            max=mx;
	    }
	}
	cout<<max<<endl;
    return 0;
}


Measured memory_bytes: 23472
import std.conv;
import std.stdio;
import std.string;

void main()
{
	auto n = readln.strip.to!int;
	auto as = readln.split.to!( long[] );
	writeln( solve( n, as ) );
}

auto solve( in int n, in long[] as )
{
	auto c = 0;
	
	foreach( i, long a; as )
	{
		while( 0 < a && a % 2 == 0 )
		{
			a /= 2;
			c++;
		}
	}
	
	return c;
}

unittest
{
	assert( solve( 3, [ 5, 2, 4 ] ) == 3 );
	assert( solve( 4, [ 631, 577, 243, 199 ] ) == 0 );
	assert( solve( 10, [ 2184, 2126, 1721, 1800, 1024, 2528, 3360, 1945, 1280, 1776 ] ) == 39 );
}


Measured memory_bytes: 2684
#include <bits/stdc++.h>
using namespace std;
 #define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
  int N,M;
  cin>>N>>M;
  int x;
  x=(N*N-N+M*M-M)/2;
  cout<<x<<endl;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define MAX_N 10000000
#define ll longlong
using namespace std;

int main() {
    int n; cin>>n;
    vector<int> a(n); vector<int> b(n);
    rep(i,n) cin>>a[i];
    rep(j,n)
    b[a[j]-1]=j+1;
    rep(i,n) cout<<b[i]<<" ";      
        return 0;
}

Measured memory_bytes: 1536
#include <stdio.h>

int main(){
  int n,i,j,m,h[100005],f[100005]={},a,b;
  scanf("%d",&n);
  scanf("%d",&m);
  for(i=0;i<n;i++){
    scanf("%d",&h[i]);
  }
  for(i=0;i<m;i++){
    scanf("%d",&a);
    scanf("%d",&b);
    a--;
    b--;
    if(h[a]>h[b]){
      f[b]=1;
    }else if(h[a]==h[b]){
      f[a]=1;
      f[b]=1;
    }else{
      f[a]=1;
    }
  }
  m=0;
  for(i=0;i<n;i++){
    if(f[i]==0) m++;
  }
  printf("%d",m);
  return(0);
}

Measured memory_bytes: 2516
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=2000000000;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;
/*
ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		else a=a*a%MOD;
		b>>=1;
	}
	return res;
}
*/
ll x[maxn];
ll L;
int par[maxn][20];
int main()
{
	IOS;
	int n;
	cin>>n;
	REP(i,n) cin>>x[i];
	int q;
	cin>>L>>q;

	{
		int j=0;
		for(int i=0;i<n;i++){
			while(j<n&&x[j]<=x[i]+L) j++;
			par[i][0]=j-1;
		}
	}
	{
		for(int j=1;j<20;j++) REP(i,n){
			par[i][j]=par[par[i][j-1]][j-1];
		}
	}

	while(q--){
		int a,b;
		cin>>a>>b;
		a--;b--;
		if(a>b) swap(a,b);

		int ans=0;
		for(int i=19;i>=0;i--){
			int tmp=par[a][i];
			if(tmp>=b) continue;
			ans|=(1<<i);
			a=par[a][i];
		}
		cout<<ans+1<<'\n';
	}


	return 0;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
    using namespace std;
    
    int main() {

        int A,B,M;
           vector<int> a,b,c,x,y,goukei; 

        cin >> A >> B >> M;
        int M2  = M;

    while(A--) {
		int n;
		cin >> n;
		a.push_back(n);
	}
  
    while(B--) {
		int n;
		cin >> n;
		b.push_back(n);
	}
    while(M--) {
		int n1,n2,n3;
		cin >> n1 >>n2 >>n3;
		x.push_back(n1);
        y.push_back(n2);
        c.push_back(n3);
	}
        int min_a = *std::min_element(a.begin(), a.end());
        int min_b = *std::min_element(b.begin(), b.end());
        goukei.push_back(min_a+min_b);

        while(M2--) {
            int n;
           n= a[x[M2]-1]+b[y[M2]-1]-c[M2];
           //cout << x[M2]<< endl;
           goukei.push_back(n);
	}
    //*std::min_element(goukei.begin(), goukei.end()) 
       cout << *std::min_element(goukei.begin(), goukei.end()) << endl;
    }

Measured memory_bytes: 2936
n, m = map(int, input().split())
ls = [[0 for i in range(3)] for j in range(m)]
ans = [""] * m
for i in range(m):
    ls[i][0], ls[i][1] = map(int, input().split())
    ls[i][2] = i
a = sorted(ls, key=lambda x:x[1])
a = sorted(ls)
prefi = ""
cityi = "000001"
for i in range(6 - len(str(a[0][0]))):
    prefi += "0"
prefi += str(a[0][0])
ans[a[0][2]] = prefi + cityi
city = 2
for i in range(1, m):
    prefId = str(a[i][0])
    ansId = a[i][2]
    if(a[i-1][0] != a[i][0]):
        city = 1
    prefi = ""
    cityi = ""
    for i in range(6 - len(str(a[i][0]))):
        prefi += "0"
    prefi += prefId
    for i in range(6 - len(str(city))):
        cityi += "0"
    cityi += str(city)
    ans[ansId] = prefi+cityi
    city += 1
for i in ans:
    print(i)


Measured memory_bytes: 33936
S=input()

stack=[]
stack.append([S[0],1])
ans=0
while stack:
  v=stack.pop()
  formula=v[0]
  index=v[1]
  if index==len(S):
    ans+=eval(formula)
  else:
    stack.append([formula+S[index],index+1])
    stack.append([formula+"+"+S[index],index+1])

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int dp[2];

int main() {
  // dp、金額ちょうどと金額+1の支払う最小の枚数を保持
  string S;
  cin >> S;
  dp[1] = 1;
  for (char s : S) {
    int cur = s - '0';
    int prev[] = {0, 0};
    swap(dp, prev);
    dp[0] = min(prev[0] + cur, prev[1] + (10-cur));
    if (cur <= 8) {
      dp[1] = min(prev[0] + cur + 1, prev[1] + (10-cur-1));
    } else {
      dp[1] = prev[1];
    }
  }
  cout << dp[0] << '\n';
  return 0;
}

Measured memory_bytes: 5312
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------

ll N, K;
vector<ll> Graph[101010];
ll used[101010];
ll ans = 1;

void dfs(ll cur, ll from) {
  if (from != 0) ++used[cur];

  ans *= K - used[from];
  ans %= MOD;
  ++used[cur];
  ++used[from];

  for (auto nv : Graph[cur]) {
    if (nv == from) continue;

    dfs(nv, cur);
  }
}

int main() {
  cin >> N >> K;
  rep(i, 0, N - 1) {
    ll a, b;
    cin >> a >> b;
    Graph[a].push_back(b);
    Graph[b].push_back(a);
  }

  dfs(1, 0);

  cout << ans;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

const int MX = 201;

int main() {
  ll n, m, R, a, b, c;
  cin >> n >> m >> R;
  vector<ll> r(R);
  rep(i, R) cin >> r[i], r[i]--;

  ll dp[MX][MX];
  rep(i, MX) rep(j, MX) dp[i][j] = (i == j ? 0 : (ll)1e15);

  rep(i, m) {
    cin >> a >> b >> c;
    a--, b--;
    dp[a][b] = dp[b][a] = c;
  }

  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

  ll ans = 1e9;
  sort(r.begin(), r.end());
  do {
    ll t = 0;
    rep(i, R - 1) t += dp[r[i]][r[i + 1]];
    ans = min(ans, t);
    cout << endl;
  } while (next_permutation(r.begin(), r.end()));

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

Measured memory_bytes: 3948
n = int(input())
a = list(map(int, input().split()))
a_0 = sum(a) - 2 * sum(a[1::2])
ans = []
ans.append(a_0)
for i, A in enumerate(a[:-1], 1):
    ans.append(2 * A - ans[i-1])

print(*ans)

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

#define foreach(i,v) for(auto&& i: v)
#define all(x) (x).begin(), (x).end()

typedef std::vector< std::string > VS;
typedef std::vector<int> VI;
typedef long long ll;

template <class C> C& mini(C& a, C b) { if (b < a) a = b; return a; }
template <class C> C& maxi(C& a, C b) { if (a < b) a = b; return a; }

using namespace std;

char ans[6000];
int ansLen;
int K;

class SuffixAutomaton {
public:
    struct State {
        int id : 31,
            is_clone : 1;
        unsigned int len;
        int link;
        map<char, int> next;

        State(int id, unsigned int len, bool is_clone = false) : id(id), len(len), is_clone(is_clone)
        {
        }

		bool dfs(const SuffixAutomaton& sa) const {
			if (ansLen) {
//				printf("Got %.*s\n", ansLen, ans);
				if (K == 0)
					return true;
				K--;
			}
			ansLen++;
			foreach (it, next) {
				ans[ansLen-1] = it.first;
				if (sa.states[it.second]->dfs(sa))
					return true;
			}
			ansLen--;
			return false;
		}
    };
    State *root;
    State *last;

    vector<State*> states;

    SuffixAutomaton(int n_hint = 0)
    {
        root = new State(0, 0);
        root->link = -1;
        last = root;
        states.reserve(n_hint);
        states.push_back(root);
    }

    ~SuffixAutomaton()
    {
		for (auto it = states.rbegin(); it != states.rend(); it++)
            delete *it;
    }

    void Append(char c)
    {
        State* cur = new State(states.size(), last->len + 1);
        states.push_back(cur);

        State* p;
        for (p = last; p != NULL && !p->next.count(c); p = getState(p->link))
            p->next[c] = cur->id;
        if (p == NULL) {
            cur->link = 0;
        } else {
            State* q = states[p->next[c]];
            if (p->len + 1 == q->len) {
                cur->link = q->id;
            } else {
                State* clone = new State(states.size(), p->len + 1, true);
                states.push_back(clone);
                clone->next = q->next;
                clone->link = q->link;
                for (; p != NULL && p->next[c] == q->id; p = getState(p->link))
                    p->next[c] = clone->id;
                q->link = cur->link = clone->id;
            }
        }
        last = cur;
    }

    State *Step(State *node, char c)
    {
        map<char, int>::const_iterator it = node->next.find(c);
        if (it == node->next.end())
            return NULL;
        return states[it->second];
    }

    State *getState(int id)
    {
        return id >= 0 ? states[id] : NULL;
    }

    struct StateLen {
        StateLen *next;
        int id;
    };

};

char buf[6000];
int main(int argc, const char* argv[]) {
	scanf("%s\n", &buf[0]);
	scanf("%d", &K);
	SuffixAutomaton sa;
	char *p = &buf[0];
	while (*p)
		sa.Append(*p++);
	K--;
	sa.getState(0)->dfs(sa);
	printf("%.*s\n", ansLen, ans);
	return 0;
}


Measured memory_bytes: 1280
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007


int main()
{
	int n;
	cin >> n;
	double ans;
	if(n % 2 == 0) ans = 0.5;
	else ans = (n / 2 + 1.0) / (n + 0.0);
	printf("%.10f\n", ans);
}

Measured memory_bytes: 256
import numpy as np
from itertools import product
s = input()
n = int(s)

digit = len(s)

selected_num = []
for order in range(3, 10, 1):
    for i in product('753', repeat = order):
        concat_str = "".join(i)
        if(('7' in concat_str) and ('5' in concat_str) and ('3' in concat_str)):
            selected_num.append(int(concat_str))

selected_num_array = np.array(selected_num)

print(np.sum(selected_num_array <= n))

Measured memory_bytes: 13416
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_B main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


int main_B() {
    cin.tie(0);
    ios::sync_with_stdio(false); 
    
    int N, X; cin >> N >> X;
    vi L(N+1); FOR(i, 1, N+1) cin >> L[i];

    vi D(N+2, 0);

    D[1] = 0;
    int ans = 1;
    FOR(i,2,N+2) {
        D[i] = D[i - 1] + L[i - 1];
        if (D[i] <= X) ans++;
    }

    cout << ans << endl;

    return 0;
}

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

class Main{
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String n;
        while((n=br.readLine())!=null){
            if("-".equals(n)){
                break;                       // - が入力されたらwhileを抜ける
            }
            String str = n;                  // n で読み取ったものをstrに入れる
            int shuffle = Integer.parseInt(br.readLine());    //shuffleにシャッフル回数を入れる
            for(int i=0; i<shuffle; i++){                     //shuffleの回数分for文が行われる
                int h = Integer.parseInt(br.readLine());      //h にカードの移動位置が入れられる
                str = str.substring(h) + str.substring(0,h);  
                //substringでhの位置から文字を取り出して
                //次のsubstringで移動される文字を取り出して
                //二つのsubstringで取り出した文字をstrに入れている
            }
            System.out.println(str);
        }
    }
}

Measured memory_bytes: 17036
#include<iostream>
#include<iomanip>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1LL << 60)
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(n); ++i)

double dp[3000][3000];	//[枚数][表の数]:確率
int main()
{
	int N; cin >> N;
	vector<double> P(N);
	rep(i, N) cin >> P[i];

	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	rep(i, N) {
		rep(k, i + 1) {
			dp[i + 1][k] += dp[i][k] * (1 - P[i]);	//裏
			dp[i + 1][k + 1] += dp[i][k] * P[i];	//表
		}
	}
	double ans = 0;
	for (int i = (N + 1) / 2; i <= N; ++i)	ans += dp[N][i];
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}


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

enum{J='J',O='O',I='I'};

char moj[3]={J,O,I};
char ary[1010][1010];
int ary2[1010][1010][3]={};
int main(){
	int M,N,hog,ug,ma,cnt,nuk;
	char emb[2][2];
	cin>>M>>N;
	for(int i=0;i<M;i++){
		for(int j=0;j<N;j++){
			cin>>ary[i][j];
		}
	}
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			cin>>emb[i][j];
		}
	}
	cnt=0;
	for(int i=0;i<M-1;i++){
		for(int j=0;j<N-1;j++){
			hog=0;ug=-1;
			for(int k=0;k<4;k++){
				if(ary[i+k/2][j+k%2]!=emb[k/2][k%2]){
					hog++;
					ug=k;
				}
				if(hog>=2) break;
			}
			if(hog==0){
				cnt++;
				for(int k=0;k<4;k++){
					for(int l=0;l<3;l++){
						if(moj[l]!=ary[i+k/2][j+k%2])ary2[i+k/2][j+k%2][l]--;
					}
				}
			}
			else if(hog==1){
				switch(emb[ug/2][ug%2]){
				case J:
					ary2[i+ug/2][j+ug%2][0]++;
					break;
				case O:
					ary2[i+ug/2][j+ug%2][1]++;
					break;
				case I:
					ary2[i+ug/2][j+ug%2][2]++;
					break;
				}
			}
		}
	}

	ma=0;
	for(int i=0;i<M;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<3;k++){
				if(moj[k]!=ary[i][j]){
					ma=max(ma,ary2[i][j][k]);
				}
			}
		}
	}
	cnt+=ma;
	cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 14100
#include "bits/stdc++.h"
using namespace std;
#define IOS { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define pb push_back
#define nl cout<<"\n"
#define endl "\n"
#define ll long long
#define ld long double
#define all(c) (c).begin(),(c).end()
#define trav(a,x) for(auto a = x.begin() ; a != x.end() ; a++)
#define rep(i,n) for(int i = 0 ; i < n ; i++)
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define f first
#define s second

inline ll max(ll a,ll b) {return ((a>b)?a:b);}
inline ll min(ll a,ll b) {return ((a>b)?b:a);}
inline ll gcd(ll a ,ll b) {if(b==0) return a; a%=b;return gcd(b,a);}
ll power(ll x, ll y){if(y == 0) return 1; ll a = power(x,y/2);if (y % 2 == 0) return a * a; else return x * a * a; }
ll powermod(ll x, ll ex , ll md) {ll ans = 1ll;while (ex > 0) {if (ex & 1ll) ans = (ans * x) % md; ex >>= 1ll;x = (x * x) % md;}return ans;}

const ll inf = 1e18 + 9;
const ll mod = 1e9 + 7;
const ld PI = acos(-1);
const ld eps = 1e-9;

const ll N = 1e6 + 1;

void solve(){
    ll x[5];
    rep(i , 5) cin >> x[i];
    ll mark = -2;
    rep(i , 5) if(x[i] == 0) mark  = i;
    cout << mark + 1 << endl;
}
int main(){
    IOS;
    cout << fixed << setprecision(20);
    ll NTC=1;
    // cin>>NTC;
    ll PTC=0;
    while(PTC++<NTC){
        // cout<<"Case #"<<PTC<<":"<<' ';
        solve();
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}


Measured memory_bytes: 3776
def main():
    s = input()
    n = len(s)
    ans = 0
    for i in range(n):
        for j in range(i + 1, n + 1):
            if set(s[i:j]) - {"A", "C", "G", "T"} == set():
                ans = max(ans, len(s[i:j]))
    print(ans)


if __name__ == "__main__":
    main()


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

#define MAX 1000000

int head = 0,tail=0;
char name[MAX][11];
int ptime[MAX];

int main(){
  int n ,q,i,j,count = 0;
  scanf("%d%d",&n,&q);

  for(tail=0;tail<n;tail++) scanf("%s%d",name[tail],&ptime[tail]);
  

  while(head!=tail){
    if(q < ptime[head]){
      ptime[tail] = ptime[head]-q;
      strcpy(name[tail],name[head]);
      count += q;
      tail = (tail + 1)%MAX;
      head = (head + 1)%MAX;
    }
    
    else{
      count += ptime[head];
      
      printf("%s %d\n",name[head],count);
      
      head = (head + 1)%MAX;
      
    }
  }

  return 0;
}





Measured memory_bytes: 4484
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;



int main(){
    LL n;cin >> n;
    vector<vector<int>> a(n,vector<int> (n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n-1; j++) {
            cin >> a[i][j];
            a[i][j]--;
        }
    }
    vector<int> c(n,0);
    vector<bool> x(n,true);
    vector<queue<P>> q(2,queue<P>());
    for (int i = 0; i < n; i++) {
        int j = a[i][c[i]];
        if(x[i]&&x[j]&&a[j][c[j]] == i){
            q[1].push(mp(i,j));
            x[i] = false;
            x[j] = false;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n*(n-1)/2; i++) {
        while(!q[i%2].empty()){
            auto p = q[i%2].front();q[i%2].pop();
            int ea = p.fs;
            int eb = p.sc;
            c[ea]++;
            c[eb]++;
            if(c[ea]<n-1){
                int ee = a[ea][c[ea]];
                if(a[ee][c[ee]] == ea) q[(i+1)%2].push(mp(ea,ee));
            }
            else cnt++;
            if(c[eb]<n-1){
                int ee = a[eb][c[eb]];
                if(a[ee][c[ee]] == eb) q[(i+1)%2].push(mp(eb,ee));
            }
            else cnt++;
        }
        if(q[(i+1)%2].empty()){
            if(cnt==n){
                cout << i << endl;
                return 0;
            }
            else{
                puts("-1");
                return 0;
            }
        }
    }
    return 0;
}



Measured memory_bytes: 4224
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Security.Cryptography;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var sa = input.ReadLine();
        var sb = input.ReadLine();
        var sc = input.ReadLine();

        int a = 0;
        int b = 0;
        int c = 0;

        char active = 'a';

        while (true) {
            if(active == 'a') {
                if (a == sa.Length) return "A";
                active = sa[a];
                a++;
            }else if (active == 'b') {
                if (b == sb.Length) return "B";
                active = sb[b];
                b++;
            }else if (active == 'c') {
                if (c == sc.Length) return "C";
                active = sc[c];
                c++;
            }
        }
    }

    static long[] ToIntArray(string strs, int n) {
        var ret = new long[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = long.Parse(spl[i]);
        return ret;
    }
}

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

using namespace std;

typedef long long ll;
 
int n,k,p[110],dp[100100];

int main() {
	
	scanf("%d %d", &n, &k);
	
	for(int i = 0; i < n; i++) {
		scanf("%d", &p[i]);
		dp[p[i]] = 1;
	}
	
	for(int i = 1; i <= k; i++) {
		int flag = 0;
		
		for(int j = 0; j < n; j++) if(i - p[j] >= 0&&dp[i - p[j]] == 0) flag = 1;
		
		if(flag) dp[i] = 1;
	}
	
	//for(int i = 0; i < k; i++) printf("%d ", dp[i]);
	
	//printf("\n");
	
	if(dp[k]) printf("First");
	else printf("Second");
	
	return 0;
}
	
	

Measured memory_bytes: 768
/*
Created on Thu Aug 27 21:32:39 2020

@author: roastedcoder

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
const int mod = 1e9+7;
#define endl "\n"
#define append push_back
#define roastedcoder ios_base::sync_with_stdio(false); cin.tie(NULL);
//__________________________________________________________________

int a[100001];

int weird(int n) {
	vector <int> dp(n, INT_MAX);
	dp[0] = 0;
	for(int i = 0; i<n; i++) {
		for(int j = i+1; j<=i+2; j++) {
			if(j<n) {
				dp[j] = min(dp[j], dp[i] + abs(a[i]-a[j]));
			}
		}
	}
	return dp[n-1];
}

int main() {
	roastedcoder
	int n; cin>>n;
	for(int i = 0; i<n; i++) cin>>a[i];
	cout<<weird(n);
}

//__________________________________________________________________
/*
Sample Input:


Sample Output:


*/

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

n, a, b = map(int, input().split())

ans = 0
for i in range(1, n+1):
    _sum = 0
    tmp_i = i
    while tmp_i:
        _sum += (tmp_i % 10)
        tmp_i //= 10
    if a <= _sum <= b:
        ans += i

print(ans)


Measured memory_bytes: 65848
#include <bits/stdc++.h>
 
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(obj) (obj).begin(), (obj).end()
#define bit(n) (1LL << (n))
 
typedef long long ll;
 
using namespace std;
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n,m;
  cin>>n>>m;
  
  int as[200001] = {0}, bs[200001] = {0};
  
  rep(i,m) {
    int a,b;
    cin>>a>>b;
    
    if(a==1) as[b-1] = 1;
    if(b==n) bs[a-1] = 1;
  }
  
  rep(i,m) {
    int a = as[i];
    int b = bs[i];
    
    if(a==1 and b==1) {
      cout<<"POSSIBLE";
      return 0;
    }
  }
  
  cout<<"IMPOSSIBLE";
  
  return 0;
}

Measured memory_bytes: 1792
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data',function(chunk){


var data = chunk.toString().split(' ').map(Number);

var a = data[0];
var b = data[1];
var c = data[2];
var count = 0;

for(var i = a; i < b+1 ; i++){

if(c % i === 0){
    count++;
  }
 }
console.log(count);
});

Measured memory_bytes: 15592
#include <cmath>
#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <limits.h>
#include <map>
#include <numeric>

namespace test {
	std::string to_string (char val) {
		return std::string (1, val);
		// return std::string{val};
	}
	//if( str.find ("r") != string::npos)
}

using namespace std;
typedef long long int llint;

int main (void) {
	int r,g,b; cin >> r >> g >> b;
	int result = r * 100 + g * 10 + b;
	cout << (result % 4 == 0 ? "YES" : "NO" ) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int P = 1000000007;
const int N = 1010;

int dp[N][N];
char s[N][N];

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%s", s[i] + 1);
  dp[1][1] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (i == 1 && j == 1 || s[i][j] == '#')
        continue;
      if ((dp[i][j] = dp[i - 1][j] + dp[i][j - 1]) >= P)
        dp[i][j] -= P;
    }
  }
  printf("%d\n", dp[n][m]);

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 5120
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
const int maxN = 505;
const int maxK = 505 * 505;
bool is_free[maxN][maxN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int p[maxK];
int dist[maxN][maxN];
void run_dfs(int x, int y) {
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (dist[nx][ny] > dist[x][y] + (!is_free[x][y])) {
            dist[nx][ny] = dist[x][y] + !is_free[x][y];
            run_dfs(nx, ny);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n * n; i++) {
        cin >> p[i];
        p[i]--;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = min({i, n - i - 1, j, n - j - 1});
            is_free[i][j] = false;
        }
    }
    int ans = 0;
    for (int i = 0; i < n * n; i++) {
        int who = p[i];
        int row = who / n;
        int col = who % n;
        ans += dist[row][col];
        is_free[row][col] = true;
        run_dfs(row, col);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 24788
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = A[0]
    for i in range(1, N):
        B = B^A[i]
    ans = []
    for i in range(N):
        ans.append(B^A[i])
    print(*ans)

if __name__ == "__main__":
    resolve()



Measured memory_bytes: 114332
s = input()
n = len(s)
a = [] #010101…
for i in range(n):
  if i%2 == 1:
    a.append(1)
  else:
    a.append(0)

k = 0
for i in range(n):
  if int(s[i]) != a[i]:
    k = k + 1
print(min(k, n-k))

Measured memory_bytes: 3956
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb               push_back
#define sz(c)            (int)c.size()
#define len(c)           (int)c.length()
#define vec              vector
#define int              long long int
#define mp(x,y) 	     make_pair(x,y)
#define all(c)           c.begin(), c.end()
#define rall(c)          c.rbegin(), c.rend()
#define trav(a,i)        for(auto& i: a)
#define loop(n,i,a)      for(int i=a;i<n;i++)
#define invect(v,n)       for(int i=0;i<n;i++ ){int arb;cin>>arb;v.pb(arb);}
#define inset(s,n)        loop(n,i,0){int aset;cin>>aset;s.insert(aset);}
#define display(c)        trav(c,i) cout<<i;
#define F                 first
#define S                 second
#define pii               pair<int,int>
#define pp               pop_back
#define endl              "\n"
#define copy(a,b)         copy(all(a),back_inserter(b));
#define intersect(a,b,w)    set_intersection(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define union(a,b,w)      set_union(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define diff(a,b,w)       set_difference(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define symdiff(a,b,w)    set_symmetric_difference(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
//int m=10000009;
//int arr[100000];
#define M 					1000000007 
signed main(){
				fast
				//	freopen("input.txt","r",stdin);
				//	freopen("output.txt","w",stdout);
				int a,b;
				cin>>a>>b;
				if(a<=9&&b<=9)
					cout<<a*b;
				else cout<<-1;

			}
			
				
		
		 
		 


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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (auto& e : a) cin >> e;

  int r = n - k + 1;

  vector<int> c(n);
  c[n - 1] = 1;
  for (int i = n - 2; i >= 0; i--) c[i] = a[i] < a[i + 1] ? c[i + 1] + 1 : 1;
  int t = 0;
  for (auto e : c) t += e >= k;
  r -= max(0, t - 1);

  set<int> s;
  for (int i = 0; i < k; i++) s.insert(a[i]);
  for (int i = 0; i + k < n; i++) {
    r -= c[i] < k && a[i] == *s.begin() && a[i + k] > *s.rbegin();
    s.erase(a[i]);
    s.insert(a[i + k]);
  }

  cout << r << endl;
}


Measured memory_bytes: 11136
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const int maxn = 2e5+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
inline void read(int &x){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
int N,W;
struct segtree{
    struct node{
        int l,r;
        ll mi,lazy;
    }tr[maxn*4];
    void pushup(node &cur,node &L,node &R){
        cur.mi = min(L.mi,R.mi);
    }
    void pushdown(node &cur,node &L,node &R){
        if(cur.lazy == 0) return ;
        L.lazy += cur.lazy;
        R.lazy += cur.lazy;
        L.mi += cur.lazy;
        R.mi += cur.lazy;
        cur.lazy = 0;
    }
    void build(int l,int r,int u = 1){
        tr[u] = {l,r,0,0};
        if(l != r){
            int mid = (l+r)>>1;
            build(l,mid,u*2);
            build(mid+1,r,u*2+1);
        }
    }
    void modify(int l,int r,ll v,int u = 1){
        if(l <= tr[u].l && tr[u].r <=r){
            tr[u].lazy += v;
            tr[u].mi += v;
        }else{
            pushdown(tr[u],tr[u*2],tr[u*2+1]);
            int mid = (tr[u].l + tr[u].r) >>1;
            if(l<=mid) modify(l,r,v,u*2);
            if(r>mid) modify(l,r,v,u*2+1);
            pushup(tr[u],tr[u*2],tr[u*2+1]);
        }
    }
    ll query_min(int l,int r,int u = 1){
        if(l<=tr[u].l && tr[u].r <=r){
            return tr[u].mi;
        }else{
            pushdown(tr[u],tr[u*2],tr[u*2+1]);
            int mid = (tr[u].l + tr[u].r)>>1;
            if(r<=mid) return query_min(l,r,u*2);
            else if(l>mid) return query_min(l,r,u*2+1);
            else{
                return min(query_min(l,r,u*2),query_min(l,r,u*2+1));
            }
        }
    }
}tr1,tr2;


int main(){
//    debug;
    ios;

    cin>>N>>W;
    tr1.build(1,W);
    tr2.build(1,W);
    for(int i =1;i<=W;i++) tr2.modify(i,i,-i);
    for(int i =1;i<=N;i++){
        int a,b;cin>>a>>b;
        int r = b+1;
        if(r<=W){
            ll mi = tr2.query_min(1,b);
            ll ans = tr1.query_min(r,r);
            if(mi + r < ans){
                tr1.modify(r,r,mi+r-ans);
                tr2.modify(r,r,mi-tr2.query_min(r,r));
            }
        }
        tr1.modify(a,b,+inf);
        tr2.modify(a,b,+inf);
        tr1.modify(1,W,+1);
        tr2.modify(1,W,+1);

        ll mi = tr1.query_min(1,W);
        if(mi >= inf) cout<<"-1\n";
        else cout<<mi<<'\n';
    }


    return 0;
}

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

typedef long long int ll;

ll wt[102],val[102];
ll dp[102][100001];

ll func(ll n,ll w)
{
	if(dp[n][w]!=-1)
		return dp[n][w];
	if(w>=wt[n])
		dp[n][w] = max(func(n-1,w),func(n-1,w-wt[n])+val[n]);
	else
		dp[n][w] = func(n-1,w);
	return dp[n][w];
}

int main()
{
	ios::sync_with_stdio(0);
	ll n,w,i,j;
	cin >> n >> w;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=100000;j++)
			dp[i][j]=-1;
	}	
	for(i=1;i<=n;i++)
		cin >> wt[i] >> val[i];
	for(i=0;i<=w;i++)
		dp[0][i]=0;
	for(i=0;i<=n;i++)
		dp[i][0]=0;
	ll ans = func(n,w);
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 79232
#include<cstdio>
#include<cstring>
#include<algorithm>

#define ll long long
#define inf 10000000000000ll

using namespace std;

int N,A[10010],nm[210];
ll f[210],c[210][210],n;

int main()
{
    f[0]=f[1]=0;
    for (int i=2;i<=50;i++){
        f[i]=(1ll<<i-1)-1;
    }
    for (int i=0;i<=50;i++){
        c[i][0]=1;
        for (int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    scanf("%lld",&n);
    
    for (int i=1;i<=100&&n;i++){
        nm[i]=0;
        ll mx=0;int p=0;
        for (int w=1;w<=50;w++)if(f[w]<=n){
            if (mx<f[w]) mx=f[w],nm[i]=w,p=0;
            
            for (int j=nm[i-1]/2;j>=1;j--){
                ll nw=0;
                for (int k=1;k<=j;k++) nw=min(inf,nw+c[j][k]*c[nm[i-1]-j][k]);
                nw*=min((inf+nw-1)/nw,(ll)w-1);
                if (nw+f[w]>n) continue;
                if (mx<nw+f[w]) mx=nw+f[w],nm[i]=w,p=j;
            }
        }

        n-=mx;
        for (int j=1;j<=p;j++) A[N-j+2]=A[N-j+1];
        A[N-p+1]=i,N++;
        for (int j=2;j<=nm[i];j++) A[++N]=i;
    }

    printf("%d\n",N);
    for (int i=1;i<=N;i++) printf("%d ",A[i]);
    puts("");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(int i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
// typedef
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;


int main() {
int H, W; cin >> H >> W;
VS S(H); rep(i,0,H) cin >> S[i];

// . で周りのpadding
string pad("");
rep(i,0,W) pad += '.';
S.push_back(pad);
S.insert(S.begin(), pad);
rep(i, 0, H+2) {
    S[i] += '.';
    S[i].insert(S[i].begin(), '.');
}

// rep(i, 0, H+2) cout << S[i] << "\n";

int cnt;
rep(h,1,H+1){
    rep(w,1,W+1){
        if (S[h][w] == '#') continue;
        cnt = 0;
        rep(ph, h - 1,  h + 2){
            rep(pw, w - 1, w + 2){
                if (S[ph][pw] == '#') ++cnt;
            }
        }
        S[h][w] = char(cnt + '0');
    }
}

rep(h,1, H+1) cout << S[h].substr(1, W) << "\n";


return 0;
}

// 境界，出力文字列 チェック
// int は ± 2*10⁹.
// map[]は対数時間．unordered_map[]は一定時間．


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		String s = scan.next();

		if(s.equals("Sunny")) {
			System.out.println("Cloudy");
		}
		if(s.equals("Cloudy")) {
			System.out.println("Rainy");
		}
		if(s.equals("Rainy")) {
			System.out.println("Sunny");
		}

	}
}

Measured memory_bytes: 21712
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        int x = Integer.parseInt(sc.next());

        boolean result = false;
        if (x == 7 || x == 5 || x == 3) {
            result = true;
        }

        System.out.println(result ? "YES" : "NO");
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int j,n,i,ans=0,mx=INT_MAX,x,y,c=0;
   cin>>x>>n;
   if(n==0)
   {
    cout<<x<<endl;
    return 0;
   }
   int a[n+2];
   for(i=0;i<n;i++)
   {
     cin>>a[i];
   }
   for(i=0;i<=1000;i++)
   {
      c=0;
      for(j=0;j<n;j++)
      {
        if(a[j]==i)
        {
          c=1;
          break;
        }
      }
      if(c==0)
      {
        y=abs(x-i);
        if(mx>y)
        {
          ans=i;
          mx=abs(x-i);
        }
      }
   }
   cout<<ans<<endl;

}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,k;
int main()
{
	scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&k);
	if(e-a>k)
		puts(":(");
	else
		puts("Yay!");
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

	int n, l, x[210];
	cin >> n >> l;
	int sum1=0, y=MOD;
	for(int i=1; i<=n; i++){
		x[i]=l+i-1;
		sum1+=x[i];
	}
	int sum2=sum1;
	int ans;
	for(int i=1; i<=n; i++){
		sum1-=x[i];
		if(abs(sum2-sum1)<y){
			y=abs(sum2-sum1);
			ans=sum1;
		}
		sum1+=x[i];
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	sum, xor := make([]int, n+1), make([]int, n+1)
	for i := 1; i <= n; i++ {
		a := nextInt()
		sum[i] = sum[i-1] + a
		xor[i] = xor[i-1] ^ a
	}

	ans, r := 0, 1
	for l := 0; l < n; l++ {
		if r <= l {
			r++
		}
		for r < n+1 && (sum[r] - sum[l] == xor[r] ^ xor[l]) {
			r++
		}
		ans += r-l-1
	}

	fmt.Println(ans)
}

Measured memory_bytes: 4736
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

ll gcm(ll a, ll b){
  if(!(a%b)) return b;
  else return gcm(b,a%b);
}

int main(){
  ll n,k;
  cin >> n >> k;
  ll a[n];
  REP(i,n) cin >> a[i];
  ll g = a[0];
  ll M = a[0];
  REP(i,n-1){
    g = gcm(g,a[i+1]);
    M = max(M,a[i+1]);
  }
  if(!(k%g)&&k<=M) cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int LIM=1e5, MOD=1e9+7;
set<int> adjl[LIM+1];
vector<int> lvl(LIM+1,0);
long long int dp[LIM+1];
void dfs(int u)
{
    long long int white_ways=1, black_ways=1;
    for(int v: adjl[u])
    {
        if(lvl[v]==0)
        {
            lvl[v]=lvl[u]+1;
            dfs(v);
            white_ways*=dp[v];
            white_ways%=MOD;
            for(int w: adjl[v]) 
            {
                if(lvl[w]>lvl[v])
                {
                    black_ways*=dp[w];
                    black_ways%=MOD;
                }
            }
            dp[u]=(white_ways+black_ways)%MOD;
            //cout<<u<<": "<<white_ways<<" "<<black_ways<<"\n";
        }
    }
    if(adjl[u].size()==1 && u!=1) dp[u]=2;
}
int main()
{
    int n;
    cin>>n;
    if(n==1) 
    {
        cout<<2;
        return 0;
    }
    for(int i=1;i<n;i++)
    {
        int x, y;
        cin>>x>>y;
        adjl[x].insert(y);
        adjl[y].insert(x);
    }
    lvl[1]=1;
    dfs(1);
    //for(int i=1;i<=n;i++) cout<<dp[i]<<" ";
    cout<<dp[1];
}

Measured memory_bytes: 28100