akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

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

    vl s(n), t(m);
    rep(i, n) {
        cin >> s[i];
    }
    rep(i, m) {
        cin >> t[i];
    }

    vvl dp(n, vl(m));  // dp[i][j] : s[i]とt[j]をペアにするときs[i]までとt[j]までで整数列として等しい部分列の組の個数
    vvl rui(n+1, vl(m+1));  // rui[i][j] : sum_{0 <= x < i, 0 <= y < j} dp[x][y]
    rep(i, n) {
        rep(j, m) {

            if(s[i] == t[j]) {
                dp[i][j] = rui[i][j] + 1;
            }

            rui[i+1][j+1] = rui[i+1][j] + rui[i][j+1] + mod - rui[i][j] + dp[i][j];

            dp[i][j] %= mod;
            rui[i+1][j+1] %= mod;
        }
    }

    out(rui[n][m] + 1);
    re0;
}

Measured memory_bytes: 62976
def main():
    O = input()
    E = input()
    p = ""
    i = 0
    j = 0
    for k in range(len(O) + len(E)):
        if (k + 1)%2 == 0:
            p += E[j]
            j += 1
        else:
            p += O[i]
            i += 1
    print(p)
main()

Measured memory_bytes: 2940
#!/usr/bin/env python3
import sys
import heapq

def solve(N: int, M: int, A: "List[int]"):

    while True:
        tmp = heapq.heappop(A) * -1
        heapq.heappush(A,tmp // 2 * -1)
        M -= 1
        if M == 0:
            break
    
    print(sum(A) * -1)

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = []
    heapq.heapify(A)
    for i in range(N):
        heapq.heappush(A,int(next(tokens)) * -1)

    solve(N, M, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 15384
#include <bits/stdc++.h>
    using namespace std;
    
    int main(){
        int n , k , x , y;
        cin >> n >> k >> x >> y ;
        long ans = 0;
        if(n > k){
            ans += k * x;
            ans += (n - k) * y;
        }else{
            ans += n * x;
        }
        cout << ans << endl;
        return 0;
    }

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] visited = new int[n + 1];
        for (int i = 0; i < k; ++i) {
            int d = scanner.nextInt();
            for (int j = 0; j < d; ++j) {
                int people = scanner.nextInt();
                visited[people] = 1;
            }
        }
        int number = n;
        for (int i = 1; i <= n; ++i) {
            if (visited[i] == 1) {
                number--;
            }
        }
        System.out.println(number);
    }
}


Measured memory_bytes: 46232
N = int(input())
A = list(map(int,input().split()))
a = 0
s = 0
for i in range(N):
    a = (a+A[i])%(10**9+7)
for i in range(N-1):
    a = a-A[i]
    s = (s+A[i]*a)%(10**9+7)
print(s)

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

#define name ""
#define ini freopen(name".inp","r",stdin); freopen(name".out","w",stdout)
#define foe(it,c) for (__typeof(c.begin()) it = c.begin(); it != c.end(); it++)
#define long long long 
#define db double 
#define pii pair <int, int>
#define pll pair <long, long>
#define all(c) c.begin(), c.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

const int INF = 1e9+7;
const int MOD = 1e9+7;
const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};

int main()
{
  fastio;
  int n; cin >> n;
  long res = 0;
  for (int i = 1; i <= n; i++){
    for (int j = 1; j <= n; j++){
      for (int k = 1; k <= n; k++){
        res += __gcd(i, __gcd(j, k));
      }
    }
  }
  cout << res;
  return 0;
}

Measured memory_bytes: 3648
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<vector<int> > vvi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<string, int> psi;
typedef pair<int, int> pii;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
int parent(int u) {
	return u / 2;
}
int left(int u) {
	return u * 2;
}
int right(int u) {
	return u * 2 + 1;
}
int main() {
	int N;
	cin >> N;
	vi A(N+1);
	for (int i = 1; i <=N; i++)
	{
		cin >> A[i];
	}
	for (int i = 1; i <= N; i++)
	{
		cout<<"node "<<i<<": key = "<<A[i]<<", ";
		if (parent(i)>=1) {
			cout << "parent key = " << A[parent(i)] << ", ";
		}
		if (left(i)<=N) {
			cout << "left key = " << A[left(i)] << ", ";
		}
		if (right(i)<=N) {
			cout << "right key = " << A[right(i)] << ", ";
		}
		cout << endl;
	}
	

};




Measured memory_bytes: 3088
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>
#include <vector>
#include <queue>
#include <ctime>
#include <numeric>
#include <cstdlib>

using namespace std;

typedef long long ll;
#define FOR(i,a,b)   for(ll i = (a); i < (b); i++ )
#define REP(i, n)    FOR(i,0,n)
typedef pair< ll, ll >   cp2;
typedef pair< ll, cp2 >   cp3;
#define fi first
#define se second
#define sec  se.fi
#define thr  se.se
const ll mod = 1000000007;
//              123456789

 
///////////////////////////////////////////////
//
//
///////////////////////////////////////////////

////////////////////////////////////////////////
////////////////////////////////////////////////

int N;
int W, H;

int main(){
	
	cin>>N>>H>>W;
	
	cout<<(N-W+1)*(N-H+1)<<endl;
	
	return 0;
	
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<math.h>
using namespace std; 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define pp(...) "\033[94m [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define dg1(x) debug() << pp(x)
#define dg2(x,y) debug() << pp(x) pp(y)
#define dg3(x,y,z) debug() << pp(x) pp(y) pp(z)
#define dg4(w,x,y,z) debug() << pp(w) pp(x) pp(y) pp(z)
#define msg(x) debug() << x
#define int long long
const int xx = 2e5;
const int MOD = 1e9 + 7;

signed main(){

  ios::sync_with_stdio(false);cin.tie(0);

  int x , a;
  cin >> x >> a;
  if(x < a){
    cout << 0 << '\n';
  }
  else cout << 10 << '\n';
  
}


Measured memory_bytes: 256
from collections import deque
N=int(input())
uvw=list(list(map(int,input().split())) for _ in range(N-1))

graph_list=[[] for _ in range(N)]
for u,v,w in uvw:
    graph_list[u - 1].append([v,w])
    graph_list[v - 1].append([u,w])

colors=[-1]*N
colors[0]=0
queue=deque([1])

while len(queue)>0:
    x=queue.popleft()
    if all(colors[i]!=-1 for i in range(N)):
        break
    for j in graph_list[x-1]:
        if colors[j[0]-1]==-1:
            queue.append(j[0])
            colors[j[0]-1]=(2+colors[x-1]+j[1])%2
for p in colors:
    print(p)


Measured memory_bytes: 59624
/**
 * author: moririn_cocoa       
**/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

int main(void) {
  
  int A;
  int B;
  int C;
  
  cin >> A;
  cin >> B;
  cin >> C;
  
  if ( A <= C && C <= B ) {
    
    cout << "Yes" << endl;
  }
  
  else {
    
    cout << "No" << endl;
  }
  
  return 0;
}


Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;


int main(){

    int k, a, b;
    cin >> k;
    cin >> a >> b; 
    bool flag = false;

    for(int i = a; i <= b; i++){
        if( i % k == 0){
            flag = true;
            break;
        }

    }

    if(flag == true){
        printf("OK\n");
    }
    else{
        printf("NG\n");
    }

    return 0;
    
}

Measured memory_bytes: 3636
n = gets.to_i
abs = []
n.times do
  abs << gets.split.map(&:to_i)
end

abs.sort_by! do |ab|
  [ab[1], ab[0]]
end

current = 0
abs.each do |ab|
  current += ab[0]
  if current > ab[1]
    puts "No"
    exit
  end
end
puts "Yes"


Measured memory_bytes: 28304
import sys
import math
from collections import deque
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, u, v = IL()
ab = [IL() for _ in range(N-1)]

aoki = [0]*(N+1)
aoki_visited = [False]*(N+1)
choku = [0]*(N+1)
choku_visited = [False]*(N+1)

edge = [[] for _ in range(N+1)]
for a,b in ab:
  edge[a].append(b)
  edge[b].append(a)

d = deque([[v,0]])
while d:
  n,cnt = d.popleft()
  aoki_visited[n] = True
  aoki[n] = cnt
  for x in edge[n]:
    if aoki_visited[x] == False:
      d.append([x, cnt+1])

dd = deque([[u,0]])
while dd:
  n,cnt = dd.popleft()
  choku_visited[n] = True
  if cnt <= aoki[n]:
    choku[n] = cnt
  for x in edge[n]:
    if choku_visited[x] == False:
      dd.append([x, cnt+1])

#print(aoki)
#print(choku)

ans = 0
for i in range(N+1):
  if choku[i] == 0 and i != u:
    continue
  if aoki[i] > choku[i]:
    ans = max(ans, aoki[i] - 1)

print(ans)

Measured memory_bytes: 90584
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int x[252521];
int ne[252521][20],rne[252521][20];
int dp[(1<<20)+10],rdp[(1<<20)+10];
vector<int> v;
int main()
{
	int n,V;
	cin>>n>>V;
	rep(i,n) cin>>x[i];
	while(V>0){
		v.pb(V);V/=2;
	}
	v.pb(0);int m=v.size();
	rep(i,n) rep(j,m){
		rne[i][j]=i;
		if(i>0 && x[i]-x[i-1]<=v[j]) rne[i][j]=rne[i-1][j];
	}
	for(int i=n-1;i>=0;i--) rep(j,m){
		ne[i][j]=i;
		if(i<n-1 && x[i+1]-x[i]<=v[j]) ne[i][j]=ne[i+1][j];
	}
	memset(dp,0,sizeof(dp));
	rep(i,(1<<20)+5) rdp[i]=n-1;
	rep(i,(1<<m)) rep(j,m){
		if((i&(1<<j))>0) continue;
		dp[i+(1<<j)]=max(dp[i+(1<<j)],ne[dp[i]][j]+1);
		rdp[i+(1<<j)]=min(rdp[i+(1<<j)],rne[rdp[i]][j]-1);
	}
	//rep(i,(1<<m)) cout<<i<<' '<<dp[i]<<' '<<rdp[i]<<endl;
	if(dp[(1<<m)-1]<n && rdp[(1<<m)-1]>=0){
		assert(dp[(1<<m)-1]<n && rdp[(1<<m)-1]>=0);
		rep(i,n) cout<<"Impossible"<<endl;
		return 0;
	}
	int now=0;
	while(now<n){
		int f=0;
		rep(i,(1<<(m-1))){
			if(dp[(1<<m)-2-(i<<1)]>=now && rdp[(i<<1)]<=ne[now][0]) f=1;
		}
		REP(i,now,ne[now][0]+1){
			if(f>0) cout<<"Possible"<<endl;
			else cout<<"Impossible"<<endl;
		}
		now=ne[now][0]+1;
	}
}


Measured memory_bytes: 46208
/*
  KUNAL ANAND
  MNNIT ALLAHABAD
*/  
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define debug1(x) cout << # x << " " << x << endl;
#define debug2(x,y) cout << #x << " " << x << " " << #y << " " << y << endl;
#define debug3(x,y,z) cout << #x << " " << x << " " << #y << " " << y << " " << #z << " " << z << endl;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
typedef long long int ll;
const ll INF=1e14;
const ll mod=1e9+7;
ll dp[100005][3],ans=LLONG_MIN,var=0;
vector<ll>graph[100005];
ll nod_val[100005];
ll power(ll x,ll y)
{
    if(y==0)
        return 1;
    ll a=power(x,y/2);
    a=(a*a);
    if(y%2)
        a=(a*x);
    return a;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t,x;
    ll i,j,k,a,b,n,m,q,y,flag=0,c,d,sum=0,cr=0,maxi=0,cl=0,temp,curr,l,r,sum1,sum2,sum3,low,high,mid;
    cin >> n;
    ll A[n],B[n],C[n];
    for(i=0;i<n;i++)
        cin >> A[i];
    for(i=0;i<n;i++)
        cin >> B[i];
    for(i=0;i<n-1;i++)
        cin >> C[i];
    temp=-2;
    ll ans=0;
    for(i=0;i<n;i++)
    {
        if(A[i]-1==temp+1)
        {
            ans+=C[temp]+B[A[i]-1];
        }
        else
            ans+=B[A[i]-1];
        temp=A[i]-1;
    }  
    cout << ans << endl;
    return 0;
}    

Measured memory_bytes: 3584
N=int(input())
A=0
B=0
AB=0
ans=0

for i in range(N):
  s=input()
  for j in range(len(s)-1):
    if s[j]=="A" and s[j+1]=="B":
      ans+=1
      
  if s[0]=="B" and s[-1]=="A":
    AB+=1
  elif s[0]=="B":
    B+=1
  elif s[-1]=="A":
    A+=1
  else:
    continue

if AB==0:
  ans+=min(A,B)
else:
  if A==0 and B==0:
    ans+=(AB-1)
  else:
    ans+=(AB+min(A,B))
    
print(ans)

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <vector>

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(a) (a).begin(), (a).end()

#define INF 1000000000

using namespace std;

int main() {
    long long N, A, B, C;

    cin >> N >> A >> B;

    C = A + B;

    long long n = N / C;

    long long remain = N - (n * C);

    cout << n * A + min(remain, A) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int,int>;

const int mx = 2e5+5;
int n, w, a[mx], b[mx];
ll dp[105][mx];

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(0);

    cin >> n >> w; int tot = 0;
    for(int i=1; i<=n; i++)
        cin >> a[i] >> b[i], tot += b[i];

    for(int i=0; i<=n; i++)
        for(int j=0; j<=tot; j++)
            dp[i][j] = (ll)1e13;

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

    ll ans = 0;
    for(int i=1; i<=tot; i++)
        if(dp[n][i] <= w)
            ans = i;
    cout << ans << "\n";


    return 0;
}



Measured memory_bytes: 82828
#pragma optimize("unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
// using namespace __gnu_pbds;
// #include <ext/pb_ds/assoc_container.hpp>
// typedef tree<int,null_type,less<int>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define Max(a,b,c) max(a,max(b,c))
#define Min(a,b,c) min(a,min(b,c))
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define pc(x)  __builtin_popcount (x)
#define vl vector< ll >
#define sorts(v) sort(v.begin(),v.end())
#define sortg(v) sort(v.begin(),v.end(),greater<ll>())
#define ss second
#define ff first
#define ll long long
#define ld long double
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1e18)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod 1000000007
#define mem(x,y) memset(x,y,sizeof(x))
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define gcd __gcd
#define primeDEN 727999983
#define nx_pe next_permutation(s.begin(),s.end())
#define cl cout<<"\n"
#define sp(x) setprecision(x)
const ll N=105,M=1e5+5;
ll dp[M][2];
ll n,k;
ll a[N];

bool fun(ll cnt,ll turn)
{
    if(dp[cnt][turn]!=-1)return dp[cnt][turn];
    rep(i,n)
    {
        ll x=cnt-a[i];
        if(x>=0&&fun(x,turn^1)==turn)return dp[cnt][turn]=turn;
    }
    return dp[cnt][turn]=turn^1;
}

void solve()
{
    cin>>n>>k;
    rep(i,n)cin>>a[i];
    mem(dp,-1);
    if(fun(k,1))cout<<"First\n";
    else cout<<"Second\n";

}


    
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin) ;
    freopen("ouput.txt", "w", stdout) ;
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL) ; cout.tie(NULL) ;
    std::ios::sync_with_stdio(false);
    ll te=1;
    // cin>>te;
    while(te--){
        solve();
    }
    
}


Measured memory_bytes: 9804
#include <cstdio>
#include <map>
#include <vector>
using namespace std;

#define iter(i, n) for (int i = 1; i <= n; ++i)
#define iter_r(i, n) for (int i = n; i >= 1; --i)
#define NR 201000
const int inf = 1e9;
const int mod = 1e9 + 7;

typedef pair<int, int> pii;
int w[NR], c[NR], n, X, Y, cnt[NR], li[NR], len, fac[NR], inv[NR];
pii minw[NR], pre[NR], suf[NR];
#define fi first
#define se second
vector<int> e[NR];
bool vis[NR];

void add_edge(int x, int y) { e[x].push_back(y); e[y].push_back(x); }

void dfs(int x) {
	if (cnt[c[x]] == 0) li[++len] = c[x];
	++cnt[c[x]];
	vis[x] = true;
	for (int v : e[x]) if (!vis[v]) dfs(v);
}

int pr(int a, int z) {
	int s = 1;
	while (z > 0) {
		if (z % 2 == 1) s = 1ll * s * a % mod;
		a = 1ll * a * a % mod;
		z /= 2;
	}
	return s;
}

int binom(int n, int k) { return 1ll * fac[n] * inv[k] % mod * inv[n - k] % mod; }

int main() {
	scanf("%d%d%d", &n, &X, &Y);
	fac[0] = inv[0] = 1;
	iter(i, n) {
		minw[i] = pii(inf, 0);
		fac[i] = 1ll * fac[i - 1] * i % mod;
	}
	inv[n] = pr(fac[n], mod - 2);
	iter_r(i, n - 1) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;

	iter(i, n) {
		scanf("%d%d", &c[i], &w[i]);
		minw[c[i]] = min(minw[c[i]], pii(w[i], i));
	}
	pre[0] = suf[n + 1] = pii(inf, 0);
	iter(i, n) pre[i] = min(pre[i - 1], minw[i]);
	iter_r(i, n) suf[i] = min(suf[i + 1], minw[i]);

	iter(i, n) {
		if (minw[c[i]].fi + w[i] <= X && minw[c[i]].se != i) add_edge(minw[c[i]].se, i);
		pii tmp = min(pre[c[i] - 1], suf[c[i] + 1]);
		if (tmp.se != 0 && tmp.fi + w[i] <= Y) add_edge(tmp.se, i);
	}

	int ans = 1;
	iter(i, n) {
		if (!vis[i]) dfs(i);
		int cur = 0;
		iter(k, len) {
			int &c = cnt[li[k]];
			cur += c; ans = 1ll * ans * binom(cur, c) % mod;
			c = 0;
		}
		len = 0;
	}

	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 20860
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int i,j,k,n,m,mark[2000000];

int main(){
	mark[1]=1;
	for(i=1;i<=1000000;i++){
		if(mark[i]==1){
			if(i*2<=1000000)mark[i*2]=1;
			if(i*3<=1000000)mark[i*3]=1;
			if(i*5<=1000000)mark[i*5]=1;
		}
		mark[i]+=mark[i-1];
	}
	while(scanf("%d",&m)*m){
		scanf("%d",&n);
		printf("%d\n",mark[n]-mark[m-1]);
	}
	return 0;
}

Measured memory_bytes: 4696
#include <stdio.h>
int main(void)
{
	int n;
	int a;
	scanf("%d", &n);
	n=n+1;
	for (a=1;a<n;a++)
	{
		if (a%3==0)
		{
			printf(" %d", a);
		}
		else if (a%10==3)
		{
			printf(" %d", a);
		}
		else if ((a/10)%10==3)
		{
			printf(" %d", a);
		}
		else if ((a/100)%10==3)
		{
			printf(" %d", a);
		}
		else if (a/10==3)
		{
			printf(" %d", a);
		}
		else if (a/100==3)
		{
			printf(" %d", a);
		}
		else if (a/1000==3)
		{
			printf(" %d", a);
		}

	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 600
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []
    mij = []
    for i in range(3):
        mi = []
        for j in range(3):
            mi.append([i*4+j,i*4+j+1,i*4+j+4,i*4+j+5])
        mij.append(mi)

    def f(n):
        a = [LI() for _ in range(n)]
        fs = set()
        def _f(i,j,d,d1,d4,d13,d16):
            if d >= n:
                return True
            key = (i,j,d,d1,d4,d13,d16)
            if key in fs:
                return False
            if i == 0:
                if j == 0:
                    d1 = d
                elif j == 2:
                    d4 = d
            elif i == 2:
                if j == 0:
                    d13 = d
                elif j == 2:
                    d16 = d
            for mm in mij[i][j]:
                if a[d][mm] > 0:
                    fs.add(key)
                    return False
            if d - min([d1,d4,d13,d16]) >= 7:
                fs.add(key)
                return False

            if _f(i,j,d+1,d1,d4,d13,d16):
                return True
            for ni in range(3):
                if i == ni:
                    continue
                if _f(ni,j,d+1,d1,d4,d13,d16):
                    return True
            for nj in range(3):
                if j == nj:
                    continue
                if _f(i,nj,d+1,d1,d4,d13,d16):
                    return True
            fs.add(key)
            return False

        if _f(1,1,0,-1,-1,-1,-1):
            return 1

        return 0

    while True:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str,rr))


print(main())



Measured memory_bytes: 44240
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
#define INF __INT32_MAX__
#define LINF __LONG_LONG_MAX__

int main() {
    ll N, K;
    cin >> N >> K;

    if (K == 0) {
        cout << (N * N) << endl;
        return 0;
    }

    ll cnt = 0;
    for (int b = 1; b <= N; b++) {
        if (b <= K) continue;
        ll bcnt = 0;

        ll cycle = N / b;
        bcnt += cycle * (b - K);

        ll mod = N % b;
        if (mod >= K) {
            bcnt += mod + 1 - K;
        }
// cout << "b: " << b << ", cycle: " << cycle << ", mod: " << mod << ", bcnt: " << bcnt << endl;

        cnt += bcnt;
    }

    cout << cnt << endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;

int main(){
    int n;
    cin >> n;
    vector<int> b(n-1);
    rep(i,n-1) cin >> b[i];

    vector<int> a(n);
    a[0] = b[0];
    for(int i=1; i<n-1; i++){
        a[i] = min(b[i],b[i-1]);
    }
    a[n-1] = b[n-2];

    ll sum=0;
    rep(i,n){
        sum += a[i];
    }
    cout << sum << endl;

}

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

void startup()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}

int32_t main()
{
    startup();
	
		int n;
		cin>>n;
		if(n>=30)
			cout<<"Yes\n";
		else
			cout<<"No\n";

		
		

    return 0;
}




Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll ans = 0;
    for(int i = 1; i < n; i++) {
        if(a[i] < a[i - 1]) {
            ans += a[i - 1] - a[i];
            a[i] = a[i - 1];
        }
    }
    cout << ans << endl;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  
  if(abs(a-c) <= d) cout << "Yes" << endl;
  else if(abs(a-b) <= d && abs(c-b) <= d) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}


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

using namespace std;

long long X, K, D;

int main() {
  scanf("%lld %lld %lld", &X, &K, &D);

  long long x = abs(X) - min(K, (abs(X) / D)) * D;
  long long k = max(0LL, K - abs(X) / D);
  if (k % 2 == 0) {
    cout << x << endl;
  } else {
    cout << abs(x - D) << endl;
  }
}

Measured memory_bytes: 3760
#include <iostream>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int main() {
	int n, k;
	int s[101][3] = {};
	int b[101] = {};
	cin >> n >> k;
	REP(i, k) {
		int a;
		cin >> a;
		cin >> b[a];
	}
	s[0][0] = 1;
	FOR(i, 1, n+1) {
		REP(j, 3) {
			if(b[i]>0 && b[i]!=j+1) {
				s[i][j] = 0;
			}else {
				if(i==1 || i==2) {
					REP(k, 3) s[i][j] += s[i-1][k];
				} else if(i==3) {
					REP(k, 3) s[i][j] += s[i-1][k];
					if((b[i-1]==0 || b[i-1]==j+1) && (b[i-2]==0 || b[i-2]==j+1))s[i][j] -= 1;
				} else {
					REP(k, 3) s[i][j] += s[i-1][k];
					s[i][j] -= s[i-1][j];
					if(b[i-1]==0 || b[i-1]==j+1) {
						REP(k, 3) s[i][j] += s[i-2][k];
						s[i][j] -= s[i-2][j];
					}
				}
			}
			s[i][j] += 10000;
			s[i][j] %= 10000;
		}
	}
	
	int r = 0;
	REP(i, 3)r += s[n][i];
	r %= 10000;
	
	cout << r << endl;
	
	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
map<pair<string, string>, ll> mp;
int main() {
	int n; string s; cin >> n >> s;
	rep(i, (1 << n)) {
		string r, b;
		rep(j, n) {
			if (i&(1 << j)) {
				r += s[n + j];
			}
			else {
				b += s[n + j];
			}
		}
		mp[{r, b}]++;
	}
	ll res = 0;
	rep(i, (1 << n)) {
		string r, b;
		rep(j, n) {
			if (i&(1 << j)) {
				r += s[j];
			}
			else {
				b += s[j];
			}
		}
		reverse(b.begin(), b.end());
		reverse(r.begin(), r.end());
		res += mp[{b,r}];
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 87040
//
//  agc029a.cpp
//  
//
//  Created by Yoshida Satoshi on 2018/12/15.
//

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;

int main()
{
    string s;
    cin>>s;
    int n=s.size();
    
    int cnt=0;
    ll ans=0;
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]=='W') cnt++;
        else
        {
            ans+=cnt;
        }
    }
    
    cout<<ans<<endl;
    return 0;
}


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

int main(){
	double a,b,x;
	scanf("%lf%lf%lf",&a,&b,&x);a=a*a;
	if (a*b/2>=x){
		// b x*2/b 
		printf("%.7f",90-atan((x*2/b/sqrt(a))/b)/acos(-1)*180);
	}else {
		//(p+b)*a=2x pa+ba=2x pa=2x-ba p=(2x-ba)/a
		printf("%.7f",atan(1.0*(b-((2*x-b*a)/a))/sqrt(a))/acos(-1)*180);
	}
	return 0;
}

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

using namespace std;

template <class T> void mini(T &l, T r) {l = min(l, r);}
template <class T> void maxi(T &l, T r) {l = max(l, r);}

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(bool a) {
  return a ? "T" : "F";
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ll = long long;
using ld = long double;

const int N = 110;

char ans[N];
string s;

bool check() {
  int n = strlen(ans);
  set <int> st;
  for (int i = 0; i < 26; ++i) {
    st.insert(i);
  }
  for (int i = 0; i < n; ++i) {
    st.erase(ans[i] - 'a');
  }
  vector <int> v(st.begin(), st.end());
  for (int i = v.size() - 1, j = n; i >= 0; --i, ++j) {
    ans[j] = v[i] + 'a';
  }
  if (ans > s) {
    for (int i = n; i < n + v.size(); ++i) ans[i] = 0;
    return 1;
  }
  for (int i = n; i < n + v.size(); ++i) ans[i] = 0;
  return 0;
}

void run() {
  cin >> s;
  set <int> st;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 26; ++j) {
      if (st.count(j)) continue;
      ans[i] = j + 'a';
      if (check()) {
        break;
      }
    }
    st.insert(ans[i] - 'a');
    if (ans > s) {
      break;
    }
    
  }
  if (ans > s)
    puts(ans);
  else
    puts("-1");
}

int main() {
  run();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    cout << ((n[0] == '7' || n[1] == '7' || n[2] == '7') ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 3572
e = [[False for _ in range(4)] for _ in range(4)]
for _ in range(3):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # 0-indexed
    e[a][b] = True
    e[b][a] = True

for r1 in range(4):
    for r2 in range(4):
        if r1 == r2: continue
        if not e[r1][r2]: continue
        for r3 in range(4):
            if r3 == r1: continue
            if r3 == r2: continue
            if not e[r2][r3]: continue
            for r4 in range(4):
                if r4 == r1: continue
                if r4 == r2: continue
                if r4 == r3: continue
                if not e[r3][r4]: continue
                print('YES')
                exit()
print('NO')


Measured memory_bytes: 3064
#include <stdio.h>

int main(){
  char ch;
  while(scanf("%c", &ch) != EOF){
    if(ch >= 65 && ch <= 90) printf("%c", ch + 97 - 65);
    else if(ch >= 97 && ch <= 122) printf("%c", ch - 97 + 65);
    else printf("%c", ch);
  }
}



Measured memory_bytes: 2604
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <set>
#include <vector>

using namespace std;

const int MAXN = 500 + 10;

int H, W, h, w;
int G[MAXN][MAXN];

void Work()
{
	scanf("%d%d%d%d", &H, &W, &h, &w);
	int SZ;
	if (h * w == 1)
		SZ = 1;
	else
		SZ = (1000000000 - 1) / (h * w - 1);
	for (int i = 0; i < H; i ++)
		for (int j = 0; j < W; j ++)
		{
			if ((i + 1) % h == 0 && (j + 1) % w == 0)
				G[i][j] = -(h * w - 1) * SZ - 1;
			else
				G[i][j] = SZ;
		}
	long long sum = 0;
	for (int i = 0; i < H; i ++)
		for (int j = 0; j < W; j ++)
			sum += (long long) G[i][j];
	if (sum <= 0)
		printf("No\n");
	else
	{
		printf("Yes\n");
		for (int i = 0; i < H; i ++)
		{
			for (int j = 0; j < W - 1; j ++)
				printf("%d ", G[i][j]);
			printf("%d\n", G[i][W - 1]);
		}
	}
}

int main()
{
	Work();
	return 0;
}

Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;

const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n),b(n);
    for(int i = 0; i < n; i++) cin >> a[i] >> b[i];
    reverse(a.begin(),a.end()),reverse(b.begin(),b.end());
    ll base = 0;
    for(int i = 0; i < n; i++){
        a[i] += base;
        if(a[i]%b[i] == 0) continue;
        if(a[i] < b[i]) base += b[i]-a[i];
        else base += b[i]-(a[i]%b[i]);
    }
    cout << base << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>
#include<stdlib.h>
#define MAX 100000
typedef struct
{
	int A;
	int B;
}omise;

int cmp(const void *p, const void *q) {
	return ((omise*)p)->A - ((omise*)q)->A;
}


int main()
{
	int N, M,i;
	omise list[MAX];

	unsigned long kingaku = 0;

	scanf("%d %d", &N, &M);
	for (i = 0;i < N;i++)
	{
		scanf("%d %d", &list[i].A, &list[i].B);
	}
	qsort(list, N, sizeof(omise), cmp);
	for (i = 0;M>0;i++)
	{
		if (M > list[i].B) {
			kingaku += (list[i].A*list[i].B);
		}else {
			kingaku += (list[i].A*M);
		}

		M -= list[i].B;
	}
	printf("%lu\n",kingaku);
	return 0;
}


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

using namespace std;

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

    vector<long long> vta, vtb;
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        vta.push_back(a);
        vtb.push_back(b);
    }

    long long ans = 0, tmp;
    for (int i = n - 1; i >= 0; i--) {
        vta[i] += ans;
        tmp = vta[i] % vtb[i];
        if (tmp != 0) {
            ans += vtb[i] - tmp;
        }
    }
    
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main()
{
    long long n, sum = 0; cin >> n;
    for (long long i = 1; i <= n; i++)
    {
      	if (i%3 == 0 || i%5 == 0)
            continue;
        sum += i;
    }
    cout << sum << endl;
    return 0;
}


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

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int n;
int sum = 0;
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n;
  bitset<4001000> x;
  x[0] = 1;
  R(i,n){
    int pom;
    cin >> pom;
    sum += pom;
    x |= x << pom;
  }
  for(int i = (sum + 1) / 2; ;i++){
    if(x[i]){
      cout << i << "\n";
      return 0;
    }
  }
}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n;
   int shotoku[10000];
   while(cin >> n){
       int sum=0;
       int s=0;
       if(n==0)break;
           for(int i=0; i<n; i++){
               cin >> shotoku[i];
                   sum += shotoku[i];
           }
       int x=sum/n;
       for(int j=0; j<n; j++){
           if(shotoku[j]<=x)
               s = s + 1;
       }
       cout << s << endl;
   }
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Vec = vector<int>;
using Graph = vector<Vec>;

int		main(void)
{
	int n, a, b;
	cin >> n >> a >> b;
	if (a * n < b)
		cout << a * n << endl;
	else
		cout << b << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 200005 ;
using namespace std ;

int n, a[N], e, ter[N], nxt[N], lnk[N] ;

void add(int x, int y) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e ;
}

bool dfs(int p, int las) {
	ll sum = 0, mx = 0 ;
	bool flg = false ;
	for (int i = lnk[p]; i; i = nxt[i]) if (ter[i] != las) {
		if (!dfs(ter[i], p)) return false ;
		sum += a[ter[i]] ;
		mx = max(mx, (long long) a[ter[i]]) ;
		flg = true ;
	}
	if (!flg) {
		return true ;
	}
	if (sum < (long long) a[p]) return false ;
	if (2LL * a[p] < sum) return false ;
	if (sum - a[p] > sum / 2LL || sum - a[p] > sum - mx) return false ;
	a[p] -= sum - a[p] ;
	return true ;
}

int main() {
	scanf("%d", &n) ;
	rep(i, 1, n) scanf("%d", &a[i]) ;
	int x, y ;
	rep(i, 1, n - 1) {
		scanf("%d%d", &x, &y) ;
		add(x, y), add(y, x) ;
	}
	if (n == 2) {
		if (a[1] == a[2]) printf("YES\n") ; 
			else printf("NO\n") ;
		return 0 ;
	}
	int rt = 0 ;
	rep(i, 1, n) if (nxt[lnk[i]]) rt = i ;
//	printf("%d\n", rt) ;
	if (dfs(rt, 0) && !a[rt]) printf("YES\n") ; 
		else printf("NO\n") ;
	return 0 ; 
}

Measured memory_bytes: 8320
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <functional>
#include <utility>
using namespace std;
typedef long long ll;
int main(){
  int A,B,C;
  cin >> A >> B >> C;
  if(A + B + C >= 22)cout << "bust" << endl;
  else cout << "win" << endl;
}

Measured memory_bytes: 256
s = input()
cnt = 0
for i in range(2,len(s)-1,2):
    s_1 = s[:(len(s)-i)//2 ]
    s_2 = s[(len(s)-i)//2 :len(s)-i]
    
    if s_1 == s_2:
        print(len(s) - i)
        cnt = 1
        break
if cnt == 0:
    print(2)

Measured memory_bytes: 9092
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;

int main(){
	int A,B,K,count=0,i=0,a[100]={};
	cin>>A>>B>>K;
	while(i!=A&&i!=B){
		i++;
	if(A%i==0&&B%i==0)
	{
		a[count]=i;
		count++;
	}
		}
		cout<<a[count-K];
	return 0;
	}

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

int main(){
  long long n;
  cin >> n;
  long long a[3*n];
  long long f[n+1], l[n+1];
  long long sum_f=0, sum_l=0;
  for(int i=0;i<3*n;i++){
    cin>>a[i];
  }

  priority_queue<long long, vector<long long>,greater<long long>> qf;
  for(int i=0;i<n;i++){
    qf.push(a[i]);
    sum_f += a[i];
  }
  f[0]=sum_f;

  for(int i=0;i<n;i++){
    qf.push(a[n+i]);
    sum_f += a[n+i];
    sum_f -= qf.top();
    qf.pop();
    f[i+1]=sum_f;
  }

  priority_queue<long long, vector<long long>, less<long long>> ql;
  for(int i=0;i<n;i++){
    ql.push(a[2*n+i]);
    sum_l+=a[2*n+i];
  }
  l[n]=sum_l;

  for(int i=0;i<n;i++){
    ql.push(a[2*n-1-i]);
    sum_l += a[2*n-1-i];
    sum_l -= ql.top();
    ql.pop();
    l[n-1-i]=sum_l;
  }

  long long result=f[0]-l[0];
  for(int i=0;i<n+1;i++){
    if(f[i]-l[i]>result){
      result = f[i]-l[i];
    }
  }

  cout<<result<<endl;

  return 0;
}

Measured memory_bytes: 6260
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const int MOD = 1000000007;

// vector<p> cut(M);
// cut[i].second
// cut[i].first;
// REP(i,M){
//     int a,b;cin>>a>>b;
//     cut[i] = make_pair(b,a);//last first の順番
// }
// for(int i=0; i<N;i++){
// }
// sort(cut.begin(),cut.end()); //sort
// char '' str ""
#include <bits/stdc++.h>
using namespace std;

struct union_find{
    vector<int> par,r;

    union_find(int n){
        par.resize(n);
        r.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            r[i]=0;
        }
    }

    int find(int x){
        if(par[x]==x) return x;
        else return find(par[x]);
    }

    void unite(int x,int y){
        x=find(x);
        y=find(y);
        if(r[x]<r[y]){
            par[x]=y;
        }
        else{
            par[y]=x;
            if(r[x]==r[y]) r[x]++;
        }
    }

    bool same(int x,int y){
        return find(x)==find(y);
    }
};


int main(void)
{
    int N,K,L;cin>>N>>K>>L;
    int p,q,r,s;


    union_find road(N), rail(N);

    for(int i=0; i<K;i++){
      cin>>p>>q;
      p--; q--;
      if(!road.same(p, q)) road.unite(p, q);
    }

    for(int i=0; i<L;i++){
        cin>>r>>s;
        r--; s--;
      if(!rail.same(r, s)) rail.unite(r, s);
    }

   pair<int,int> pairs[2*100000+1];
   map<pair<int,int>, int> mp;

   for(int i=0; i<N;i++){
     pairs[i] = make_pair(road.find(i), rail.find(i));
     mp[pairs[i]]++;
   }

   for(int i=0; i<N;i++){
     cout<<mp[pairs[i]]<<" ";
   }

    cout<<endl;
    return 0;
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int n,k,x;
	cin>>n>>k;
	int a[200000+5]={0},i;
	for(i=1;i<=n;i++)
	{
		cin>>x;
		a[x]++;
	}
	
	sort(a+1,a+200000+1,cmp);
	
	int s=0;
	for(i=k+1;i<=200000;i++)
	s+=a[i];
	
	cout<<s;
	return 0;
 } 

Measured memory_bytes: 1024
#include <iostream>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(n);++i)

const int INF = 1e9+1;
const int MAX_V = 1e5+1;
int main() {
  int N, W; cin >> N >> W;

  int w[N], v[N];
  rep(i, N) {
    cin >> w[i] >> v[i];
  }

  // 価値の制約が小さくなっているのでそちらで解く
  // dp[i][v] = i番目(1-idx)までで価値の総和がvとなるようにしたとき、最小の重さの総和

  ll dp[N+1][MAX_V];
  rep(i, N+1) rep(w, MAX_V) dp[i][w] = INF;
  dp[0][0] = 0;

  int ans = 0;
  rep(i, N) {
    rep(j, MAX_V) {
      dp[i+1][j] = dp[i][j];
      if (j >= v[i])
        dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i]);
    }
  }
  rep(j, MAX_V) {
    if (dp[N][j] <= W)
      ans = j;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 79104
from sys import stdin
from collections import deque
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    G=[[] for _ in range(n+1)]
    for _ in range(n-1):
        u,v,w=map(int,readline().split())
        G[u].append((v,w))
        G[v].append((u,w))

    d=[0]*(n+1)
    flags=[False]*(n+1)
    flags[1]=True
    q=deque([1])
    while len(q)>0:
        now=q.popleft()
        for nex in G[now]:
            if flags[nex[0]]==False:
                flags[nex[0]]=True
                q.append(nex[0])
                d[nex[0]]=d[now]+nex[1]

    for i in range(1,n+1):
        if d[i]%2==0:
            print(0)
        else:
            print(1)

if __name__=="__main__":
    main()

Measured memory_bytes: 43924
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int main()
{
	string str;
	int ss;
	cin>>ss;
	cin>>str;
    int js=str.length();
    if(ss-js>=0)
    {
    	cout<<str;
    	return 0;
    }	
    else
    {
    	for(int i=0;i<ss;i++)
    		cout<<str[i];
    	cout<<"...";  	
    }
	return 0;
}

Measured memory_bytes: 3608
import java.util.Scanner;


// 152_b
public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        boolean[] n_ac = new boolean[n];
        int[] n_wa = new int[n];
        for (int i = 0; i < n; i++) {
            n_ac[i] = false;
            n_wa[i] = 0;
        }
        for (int i = 0; i < n; i++) {
            n_ac[i] = false;
        }
        int m = sc.nextInt();

        int seitou = 0;
        int pena = 0;

        for (int i = 0; i < m; i++) {
            int pi = sc.nextInt();
            String s1 = sc.next();
            if (n_ac[pi - 1]) {
                continue;
            }
            if ("AC".equals(s1)) {
                n_ac[pi - 1] = true;
                seitou++;
                pena += n_wa[pi - 1];
            }
            if ("WA".equals(s1)) {
                n_wa[pi - 1]++;
            }
        }

        out(seitou + " " + pena);

    }

    /*
     * 以下メソッド集
     */

    static long gcd(long a, long b) {

        return (b == 0) ? a : gcd(b, a % b);
    }

    static int gcd(int a, int b) {

        return (b == 0) ? a : gcd(b, a % b);
    }

    static void out(String info) {

        System.out.println(info);
    }

    static void out(int info) {

        System.out.println(info);
    }

    static void out(double info) {

        System.out.println(info);
    }

    static void out(long info) {

        System.out.println(info);
    }

}


Measured memory_bytes: 63788
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);

	void run() {
		for (;;) {
			int n = sc.nextInt();
			if (n == 0) return;
			int[][] c = new int[n][2];
			for (int i = 0; i < n; i++) {
				c[i][0] = sc.nextInt();
				c[i][1] = sc.nextInt();
			}
			int[][] dp = new int[n + 1][1011];
			dp[0][0] = 1;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j <= 1000; j++) {
					if (dp[i][j] != 0) {
						dp[i + 1][j] += dp[i][j];
						for (int k = 1; k <= c[i][1]; k++) {
							if (j + k * c[i][0] <= 1000) dp[i + 1][j + k * c[i][0]] += dp[i][j];
						}
					}
				}
			}
			int m = sc.nextInt();
			while (m-- > 0) {
				System.out.println(dp[n][sc.nextInt()]);
			}
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 20540
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int N;
vpint adj[200001];
int d[200001],color[200001],p[200001];
void dijkstra(int start){
	priority_queue<pint> PQ;
	rep(i,N){
		d[i]=INF;
		color[i]=0;
	}
	d[start]=0;
	color[start]=1;
	PQ.push(mp(0,start));
	while(!PQ.empty()){
		pint f=PQ.top();
		PQ.pop();
		int u=f.second;
		color[u]=2;
		if(d[u]< -f.first) continue;
		rep(j,adj[u].size()){
			int v=adj[u][j].first;
			if(color[v]==2) continue;
			if(d[v]>d[u]+adj[u][j].second){
				d[v]=d[u]+adj[u][j].second;
				PQ.push(mp(-d[v],v));
				color[v]=1;
			}
		}
	}
}
int main(){
	//int count[200001]={};
	//int ha=0;
	scan(N);
	rep(i,N-1){
		int a,b;
		scan(a>>b);
		a--; b--;
		adj[a].push_back(mp(b,1));
		adj[b].push_back(mp(a,1));
		//count[a]++;
		//count[b]++;
	}
	/*rep(i,N){
		if(count[i]==1) ha++;
	}
	if((N-ha)%3==0) prin("Second");
	else prin("First");*/
	dijkstra(0);
	int dmax=0,maxnode;
	rep(i,N){
		if(d[i]>dmax){
			dmax=d[i];
			maxnode=i;
		}
	}
	dijkstra(maxnode);
	dmax=0;
	rep(i,N){
		if(d[i]>dmax){
			dmax=d[i];
			maxnode=i;
		}
	}
	if(dmax%3==1) prin("Second");
	else prin("First");
	return 0;
}


Measured memory_bytes: 17876