akhauriyash/Code-Regression huggingface dataset:
while line = gets
  break if line.chomp == '0'

  cards = line.chomp.split.map(&:to_i)

  dp = Array.new(cards.size + 1) { Array.new(22, 0) }

  dp[0][0] = 1

  for i in 0...cards.size
    card = cards[i]
    for j in 0...22
      if card == 1
        dp[i + 1][j] = [dp[i + 1][j], dp[i][j - 1]].max if j - 1 >= 0 && j - 1 < 22
        dp[i + 1][j] = [dp[i + 1][j], dp[i][j - 11]].max if j - 11 >= 0 && j - 11 < 22
      else
        card = 10 if card > 10
        dp[i + 1][j] = dp[i][j - card] if j - card >= 0 && j - card < 22
      end
    end
  end

  a = 0
  for i in 0...22
    a = i if dp[cards.size][i] == 1
  end
  puts a
end

Measured memory_bytes: 8892
#import math
#g = math.gcd
import fractions
g = fractions.gcd
n = int(input())
a = [int(_) for _ in input().split()]
mod = 10**9 + 7
lcm = 1
for x in a:
    lcm *= x // g(lcm, x)
ans = 0
for x in a:
    ans += lcm * pow(x, mod - 2, mod)
    ans %= mod
print(ans)

Measured memory_bytes: 6200
import sys
from functools import reduce
import copy
import math
from pprint import pprint


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    [A, B] = string_to_int(inputs[0])
    count = 0
    for n in range(A, B+1):
        s = str(n)
        front = []
        back = []
        if len(s) % 2 == 0:
            half = len(s) // 2
            front = list(s[:half])
            back = list(s[half:])
        else:
            half = len(s) // 2
            front = list(s[:half])
            back = list(s[half+1:])
        if front == list(reversed(back)):
            count += 1
    return count


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 3940
def dijkstra(G, s):
    # sを始点としてすべての点への最短距離を求める
    inf = 10**18
    n = len(G)
    D = [inf for i in range(n)]
    D[s] = 0
    Q = [s]
    while Q:
        x = Q.pop()
        for y in G[x]:
            if D[y] > D[x] + 1:
                D[y] = D[x] + 1
                Q.append(y)
    return D


n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
D0 = dijkstra(G, 0)
D1 = dijkstra(G, n-1)
c0, c1 = 0, 0
for i in range(n):
    if D0[i] <= D1[i]:
        c0 += 1
    else:
        c1 += 1
if c0 > c1:
    print('Fennec')
else:
    print('Snuke')


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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

const int INF=123456789;

int main()
{
    int n;
    while(cin >>n,n)
    {
        vector<int> p(n),t(n);
        rep(i,n) scanf(" %d %d", &p[i],&t[i]);

        int dp[41][4];
        fill(dp[0],dp[41],INF);
        dp[0][0]=0;
        if(p[0]<=t[0]) dp[1][1]=p[0];

        for(int i=1; i<n; ++i)
        {
            for(int j=1; j<=3; ++j)
            {
                if(p[i-1]*(j+1)+p[i]<=t[i]-t[i-1])
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+p[i]+p[i-1]);
            }

            for(int j=2; j<=3; ++j)
            {
                if(abs(p[i]-p[i-1])*j<=t[i]-t[i-1])
                dp[i+1][j]=min(dp[i+1][j],dp[i][j-1]+abs(p[i]-p[i-1]));
            }
        }

        int ans=INF;
        rep(i,4) ans=min(ans,dp[n][i]+p[n-1]);
        if(ans<INF) printf("OK %d\n", ans);
        else
        {
            rep(i,n)
            {
                bool check=false;
                rep(j,4) if(dp[i+1][j]<INF) check=true;
                if(!check)
                {
                    ans=i+1;
                    break;
                }
            }
            printf("NG %d\n", ans);
        }
    }
    return 0;
}

Measured memory_bytes: 3124
#import numpy as np
h,w=list(map(int,input().split()))
s=[[i for i in input() ] for _ in range(h)]

l=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
r=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
u=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
d=[[1 if s[h_i][w_i]=="." else 0 for w_i in range(w)] for h_i in range(h)]
for h_i in range(h):
    for w_i in range(w):
        rev_w=w-w_i-1
        rev_h=h-h_i-1
        if s[h_i][w_i]!="#" and w_i!=0:
            l[h_i][w_i]+=l[h_i][w_i-1]
        if s[h_i][rev_w]!="#" and w_i!=0:
            r[h_i][rev_w]+=r[h_i][rev_w+1]
        if s[h_i][w_i]!="#" and h_i!=0:
            u[h_i][w_i]+=u[h_i-1][w_i]
        if s[rev_h][w_i]!="#" and h_i!=0:
            d[rev_h][w_i]+=d[rev_h+1][w_i]
ans=0
for h_i in range(h):
    for w_i in range(w):
        tmp=l[h_i][w_i]+r[h_i][w_i]+u[h_i][w_i]+d[h_i][w_i]-3
        ans=max(ans,tmp)

print(ans)

Measured memory_bytes: 317704
p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
cnt = 1
cnt0 =0
C = {i:0 for i in range(N)}
B = []
for i in range(N):
    a = A[i]
    if a==0:
        cnt = (cnt*(3-cnt0))%p
        cnt0 += 1
    else:
        cnt = (cnt*C[a-1])%p
        C[a-1] -= 1
    C[a] += 1
print(cnt)

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

const int M = 1000000007;
long long H, W, A, B, ans, fac[300006];

long long inv(long long a, long long b) {
	if (b == 0) {
		return 1;
	}
	if (b == 1) {
		return a;
	}
	if (b % 2 == 0) {
		long long temp = inv(a, b/2);
		return temp * temp % M;
	} else {
		return a * inv(a, b - 1) % M;
	}
}

int main() {
	cin >> H >> W >> A >> B;
	fac[0] = 1;
	for (int i = 1; i < 210000; i++) {
		fac[i] = fac[i - 1] * i % M;
	}
	H = H - 1;
	W = W - 1;
	ans = fac[H + W] * inv(fac[H], M - 2) % M;
	ans = ans * inv(fac[W], M - 2) % M;
	//cout << ans << endl;
	for (int i = 0; i < B; i++) {
		//cout << i << endl;
		long long temp = fac[H - A + i] * inv(fac[H - A], M - 2) % M;
		temp = temp * inv(fac[i], M - 2) % M;
		temp = temp * fac[W + A - 1 - i] % M;
		temp = temp * inv(fac[A - 1], M - 2) % M;
		temp = temp * inv(fac[W - i], M - 2) % M;
		ans = ans - temp;
		ans = ans % M;
		//cout << temp << endl;
	}
	ans = (ans + M) % M;
	cout << ans << endl;
	return 0;
}

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

int main() {
  int a,b,c;
  int cnt1 = 0,cnt2 = 0;
  while ( scanf("%d,%d,%d",&a,&b,&c) != EOF ) {
    if ( a == b ) {
      //      cout << "cnt2" << " " << a << "," << b << "," <<  c << endl;
      cnt2++;
    } else if ( a < c && b < c ) {
      //      cout <<"cnt1" << " "<<  a << "," << b << "," <<  c << endl;
      cnt1++;
    }
    
  }
  cout << cnt1 << endl << cnt2 << endl;
  return 0;
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int i,j,n,m,x,y,z,a,b,c;
  string s;
  cin >> x;
  a=x;
  cin >> y;
  b=y;
  cin >> z;
  c=z;
  
  cout << z << " " << x << " " << y << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
#define MAX 1000

class stack{
    int num;
    stack* head = NULL;
    stack* prev = NULL;
    stack* tail = NULL;
    bool isEmpty = true;
public:
    void push(int x){
        if(isEmpty){
            isEmpty = false;
            num = x;
            return;
        }
        if(head == NULL){
            head = new stack(x);
            head->prev = this;
            this->tail = this;
        }
        else{
            stack* tmp = tail->head;
            tmp->prev = tail;
            tmp->head = new stack(x);
            tail =  tmp;
        }
    }
    
    int top(){
        if(head == NULL){
            return num;
        }
        else{
            return tail->head->num;
        }
    }
    
    void pop(){
        if(head == NULL){
            isEmpty = true;
        }
        else{
            stack* tmp = tail;
            delete tmp->head;
            tmp->head = NULL;
            tail = tail->prev;
        }
    }
    
    bool empty(){
        return isEmpty;
    }
    
    stack(){
        
    }
    
    stack(int num){
        this->num = num;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,q,command,t,x;
    stack myStack[MAX];
    cin >> n >> q;
    
    for (int i = 0;i < q;++i) {
        cin >> command >> t;
        switch(command){
                // push
            case 0:
                cin >> x;
                myStack[t].push(x);
                break;
                // top
            case 1:
                if(!myStack[t].empty()){
                    cout << myStack[t].top() << endl;
                }
                break;
                // clear
            case 2:
                if(!myStack[t].empty()){
                    myStack[t].pop();
                }
                break;
        }
    }
}



Measured memory_bytes: 12624
n, m = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]

s1 = []
sn = []

for i in range(m):
    if A[i][0] == 1:
        s1.append(A[i][1])
    elif A[i][1] == n:
        sn.append(A[i][0])

#print(s1, sn)
if len(set(s1) & set(sn)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

typedef double          D;
typedef long long int   LL;
typedef long double     LD;
#define OR              ||
#define AND             &&
#define nl              '\n'
#define S               string
#define inf             INT_MAX
#define SQR(a)          (a) * (a)
#define pb              push_back
#define GCD(a, b)       __gcd(a, b)
#define MOD             1000000007
#define PI              2.0*acos(0.0)
#define LCM(a, b)       (a * b) / GCD(a, b)
#define mem(a,b)        memset(a,b,sizeof(a))
#define srtv(v)         sort(v.begin(),v.end())
#define T               int t; cin>>t; while(t--)
#define Rep(i,a,b)      Rep(int i = 0; i <n; i++)
#define rep(i,a,b)      rep(int i = n; i >= 0; i--)
#define boost		    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inout           freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)

#define si(x)           scanf("%d",&x)
#define pi(x)           printf("%d",x)
#define ss(str)         scanf("%s",str)
#define pl(x)           printf("%lld",x)
#define sl(x)           scanf("%lld",&x)
#define sii(x,y)        scanf("%d %d",&x,&y)
#define sll(x,y)        scanf("%lld %lld",&x,&y)
#define siii(x,y,z)     scanf("%d %d %d",&x,&y,&z)
#define slll(x,y,z)     scanf("%lld %lld %lld",&x,&y,&z)

using namespace std;

int main(void){
    boost;

    LL n,m,k,sum=0;
    cin>>n;

    vector<LL>a(n+1);

    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j +=i){
            a[j]++;
        }
        //cout<<a[i]<<" ";
        sum +=i*a[i];
    }
    cout<<sum<<'\n';
}






Measured memory_bytes: 81324
#include <iostream>

int main() {
    long long n;
    std::cin >> n;

    long long sum = 0;
    for(int i = 1; i <= n; i++) {
        if(i % 3 != 0) {
            if(i % 5 != 0) {
                sum += i;
            }
        }
    }

    std::cout << sum << std::endl;
}


Measured memory_bytes: 3544
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <math.h>
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (ll)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
ll gcd(ll a,ll b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int INF=1e9;
const ll MX = 1e18;
const int MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
 
int main() {
  int n;
  cin>>n;
  vi a(n),b(n),c(n);
  rep(i,n) cin>>a[i];
  rep(i,n) cin>>b[i];
  rep(i,n) cin>>c[i];
  sort(all(a));
  sort(all(b));
  sort(all(c));
  ll ans=0;
  rep(i,n){
    ll s=lower_bound(all(a),b[i])-a.begin();
    ll g=c.end()-upper_bound(all(c),b[i]);
    ans+=s*g;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 4548
#include<bits/stdc++.h>
using namespace std;
const int MAXN=110000;

int n,m;
char str[5];

int p[MAXN];
long long weight[MAXN];
int find(int u)
{
	if(u==p[u])return u;
	else
	{
		int root=find(p[u]);
		weight[u]+=weight[p[u]];
		return p[u]=root;
	}

}

int main()
{
	while(scanf("%d%d",&n,&m))
	{
		if(0==n&&0==m)break;

		int i;
		//init;
		for(i=1;i<=n;i++)
		{
			p[i]=i;
			weight[i]=0;
		}

		int start,end,w;
		for(i=0;i<m;i++)
		{
			scanf("%s",str);
			if(!strcmp(str,"!"))
			{
				scanf("%d%d%d",&start,&end,&w);
				int x=find(start);
				int y=find(end);
				if(y!=x)
				{
					p[y]=x;
					weight[y]=w+weight[start]-weight[end];
				}
			}
			else if(!strcmp(str,"?"))
			{
				scanf("%d%d",&start,&end);
				int x=find(start);
				int y=find(end);
				if(x!=y)printf("UNKNOWN\n");
				else printf("%d\n",weight[end]-weight[start]);
			}
		}
	}
	return 0;
}

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

class UnionFind():
    def __init__(self, N):
        self.N = N
        self.r = [-1] * (N+1)

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] > self.r[y]:
            x, y = y, x
        self.r[x] += self.r[y]
        self.r[y] = x
        return True

    def size(self, x):
        return -self.r[self.root(x)]

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

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        A, B = map(lambda i: int(i)-1, input().split())
        uf.unite(A, B)

    ans = 0
    for i in range(N):
        ans = max(ans, uf.size(i))

    print(ans)

main()

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

using namespace std;

int main(void) {
  int a, b;
  cin >> a >> b;

  int diff = b - a;

  int tmp = 0;

  for(int i = 0; i < diff; i++) {
    tmp += i;
  }

  cout << tmp - a << endl;
}

Measured memory_bytes: 256
N, Q = gets.split.map(&:to_i)
S = gets.chomp
LRs = readlines.map{|l| l.split.map(&:to_i)}

a = Array.new(N + 1, 0)
c = ''
n = 0
(2 .. N).each do |i|
  n += 1 if S[i - 2] == 'A' && S[i - 1] == 'C'
  a[i] = n
end
LRs.each do |l, r|
  puts a[r] - a[l]
end

Measured memory_bytes: 18172
#include<iostream>
#include<algorithm>
#include <iostream> 
#include <algorithm> 
#include<string>
#include<queue>
#include<utility>
#include<fstream>
#include<queue>
#include<set>
#include<stack>
//#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 
 
typedef pair<int,int >P;
//////////////////////////
/////////////////////////

int main(){
    string s;
    cin>>s;
    
    for(int i = 0;i<s.size();i++){
        for(int j=0;j<s.size();j++)if(s[i]!=s[j]){
            cout<<"Yes"<<endl;
            return 0;
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
/*
    問題をよく読もう！
    論理的に考えよう！
    サンプルを確認しよう!
    絶対に諦めるな！
    工夫をしろ！
    配列は少し多めにとっておく

    Twitterは終わるまでログアウト！
    （間違えて解法をツイートしてはいけないから）

*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <functional>
#include <cmath>
using namespace std;
#define rep(i, n) for(int i=0; i<n; ++i)
typedef long long ll;
//必要な宣言

void solve();

double t, x;

int main() {
  cin >> t >> x;

  solve();

  return 0;
}

void solve() {

  cout << t/x << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
const int N=200005;
set<pii> S;
int f[N],t[N],n,Ans[N],X,Q,v[N];
struct Ask{
	int t,a,from;
}A[N];
int cmp(Ask x,Ask y){
	return x.t<y.t;
}
int find(int x){
	if (x==f[x])return x;
	return f[x]=find(f[x]);
}
signed main(){
	scanf("%lld%lld",&X,&n);
	for (int i=1;i<=n;i++)scanf("%lld",&t[i]);
	t[++n]=2e9;
	scanf("%lld",&Q);
	for (int i=1;i<=Q;i++)scanf("%lld%lld",&A[i].t,&A[i].a),A[i].from=i;
	sort(A+1,A+Q+1,cmp);
	for (int i=1;i<=Q;i++)f[i]=i,v[i]=A[i].a,S.insert(mp(A[i].a,i));
	int sum=0,cnt=Q;
	for (int i=1,j=1;i<=n;i++){
		while (j<=Q&&A[j].t<=t[i]){
			Ans[A[j].from]=v[find(j)]+sum;
			if (i&1)Ans[A[j].from]-=A[j].t-t[i-1];
			else Ans[A[j].from]+=A[j].t-t[i-1];
			if (Ans[A[j].from]<0)Ans[A[j].from]=0;
			if (Ans[A[j].from]>X)Ans[A[j].from]=X;
			j++;
		}
		if (i&1){
			sum-=t[i]-t[i-1];
			vector<int> vv;
			while (S.begin()!=S.end()){
				pii now=*S.begin();
				if (now.fi+sum>=0)break;
				S.erase(S.begin());
				vv.push_back(now.se);
			}
			if (vv.size()){
				cnt++;
				f[cnt]=cnt;
				v[cnt]=-sum;
				for (int j:vv)f[j]=cnt;
				S.insert(mp(-sum,cnt));
			}
		}
		else {
			sum+=t[i]-t[i-1];
			vector<int> vv;
			while (S.begin()!=S.end()){
				set<pii>::iterator iter=S.end();iter--;
				pii now=*iter;
				if (now.fi+sum<=X)break;
				S.erase(iter);
				vv.push_back(now.se);
			}
			if (vv.size()){
				cnt++;
				f[cnt]=cnt;
				v[cnt]=X-sum;
				for (int j:vv)f[j]=cnt;
				S.insert(mp(X-sum,cnt));
			}
		}
	}
	for (int i=1;i<=Q;i++)printf("%lld\n",Ans[i]);
}


Measured memory_bytes: 17916
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int main()
{
	string a;
	cin>>a;
	int tmp=a.find("ST");
	while(a.length()>0&&tmp>=0)
	{
		a.erase(tmp,2);
		int x=max(tmp-1,0);
		tmp=a.find("ST",x);
		if(tmp==string::npos)
			tmp=-1;
	}
	cout<<a.length()<<endl;
	return 0;
} 

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

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

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

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

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;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

#define rep(i,n) for (int i = 0; i < n; ++i)
#define reps(i,s,n) for (int i = s; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
#define per(i,n) for (int i = n - 1; i >= 0; --i)
#define per1(i,n) for (int i = n; i >= 1; --i)
#define all(c) begin(c),end(c)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline T intceil(T a, T b) { return (a + (b - 1)) / b; }
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const long long MOD = 1e9+7;
#define precout() cout << std::fixed << std::setprecision(20);
#define print(a) cout << a << endl;
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };
// if(nextH >= 0 && nextH < H && nextW >= 0 && nextW < W)
static const long double pi = acos(-1.0);
typedef complex<ld> cd;

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

    string s; cin >> s;
    print(s.substr(0, 3));
}


Measured memory_bytes: 3612
#include<iostream>
using namespace std;
int N, A[3][3], b[10];
bool appear[3][3];
int main() {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) cin >> A[i][j];
	}
	cin >> N;
	for (int i = 0; i < N; i++) cin >> b[i];
	for (int i = 0; i < N; i++) {
		 for (int j = 0; j < N; j++) {
			 appear[i][j] = false;
			 for (int k = 0; k < N; k++) {
				 if (A[i][j] == b[k]) appear[i][j] = true;
				
			 }
			
		 }
		
	 }
	 string ANS = "No";
	 for (int i = 0; i < 3; i++) {
		if (appear[i][0] and appear[i][1] and appear[i][2]) ANS = "Yes";
	 }
	 for (int i = 0; i < 3; i++) {
		 if (appear[0][i] and appear[1][i] and appear[2][i]) ANS = "Yes";
	 }
	if (appear[0][0] and appear[1][1] and appear[2][2]) ANS = "Yes";
	if (appear[0][2] and appear[1][1] and appear[2][0]) ANS = "Yes";
	cout << ANS << endl;
	return 0;
	
}

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

#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(v) (int) v.size()

#define endl '\n'

using Long = long long;

const int N = 3005;
const Long MOD = 998244353;

int a[N];
Long dp[N][N];
int n , s;

Long solve( int pos , int sum ){

    if( sum < 0 ) return 0;
    if( pos == 0 ) return (Long) sum == 0;

    Long &ans = dp[pos][sum];

    if( ans != -1 ) return ans;

    ans = 0;
    ans += solve( pos - 1 , sum ) * 2 ;
    ans += solve( pos - 1 , sum - a[pos] ) ;
    ans %= MOD;

    return ans;
}

int main(){

    cin >> n >> s;

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

    memset( dp , -1 , sizeof dp );
    cout << solve( n , s ) << endl ;

    return 0;
}

Measured memory_bytes: 74372
#include <bits/stdc++.h>
#define fast_cin() ios_base::sync_with_stdio(0) 
typedef long long int ll;
using namespace std;
const int MOD=1e9+7;
const int size=1 << 10;

ll n,m;
char a[size][size];
int main()
{
	cin >> n >> m;
	ll x=1;
	while(n--)
	{
		if(x*2>x+m)
			x+=m;
		else
			x*=2;
	}
	cout << x;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
import java.math.BigDecimal;
import java.nio.charset.StandardCharsets;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	static class Node {
		int id;
		Set<Integer> conns;

		Node(int id) {
			this.id = id;
			this.conns = new HashSet<>();
		}
	}

	int N;
	Node[] nodes;

	Main(BufferedReader in) throws IOException {
		N = Integer.parseInt(in.readLine());
		nodes = new Node[N];
		for (int i = 0; i < N; ++i) {
			nodes[i] = new Node(i);
		}
		for (int i = 0; i < N - 1; ++i) {
			String[] tokens = in.readLine().split(" ");
			int a = Integer.parseInt(tokens[0]) - 1;
			int b = Integer.parseInt(tokens[1]) - 1;
			nodes[a].conns.add(b);
			nodes[b].conns.add(a);
		}
	}

	List<Integer> getPath(int current, int parent) {
		if (current == N - 1) {
			List<Integer> path = new ArrayList<>();
			path.add(current);
			return path;
		} else {
			List<Integer> remain = null;
			for (Integer i : nodes[current].conns) {
				if (i != parent) {
					List<Integer> l = getPath(i, current);
					if (l != null) {
						remain = l;
						break;
					}
				}
			}
			if (remain != null) {
				remain.add(current);
			}
			return remain;
		}
	}

	int count(int current, int parent) {
		int c = 1;
		for (Integer i : nodes[current].conns) {
			if (i != parent) {
				c += count(i, current);
			}
		}
		return c;
	}

	void calc() {
		// まずpathを求める
		List<Integer> path = getPath(0, -1);
		Collections.reverse(path);
		int middle = (path.size() - 1) / 2;
		// 分割する
		int blackEdge = path.get(middle);
		int whiteEdge = path.get(middle + 1);
		nodes[blackEdge].conns.remove(whiteEdge);
		nodes[whiteEdge].conns.remove(blackEdge);

		int blackNum = count(0, -1);
		int whiteNum = count(N - 1, -1);
		if (blackNum <= whiteNum) {
			System.out.println("Snuke");
		} else {
			System.out.println("Fennec");
		}
	}

	void showResult() {
	}
}

Measured memory_bytes: 93924
# -*- coding: utf-8 -*-
import sys

X,N,*P = map(int, sys.stdin.buffer.read().split())

diff = 0
while True:
  if X-diff not in P:
    print(X-diff)
    break
  if X+diff not in P:
    print(X+diff)
    break
  diff += 1

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

using namespace std;

const int N = 100005;
const int LG = 19;
const int inf = 1e9+7;

int n, a[N], l, q, up[LG][N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);
    }
    scanf("%d %d", &l, &q);
    for (int i = 0; i < n; ++i) {
        int pos = upper_bound(a + i, a + n, a[i] + l) - a - 1;
        up[0][i] = pos;
    }
    for (int i = 1; i < LG; ++i) {
        for (int j = 0; j < n; ++j) {
            up[i][j] = up[i - 1][up[i - 1][j]];
        }
    }
    while (q--) {
        int x, y;
        scanf("%d %d", &x, &y);
        --x; --y;
        if (x > y) {
            swap(x, y);
        }
        int result = inf, cur = 0;
        for (int i = LG - 1; i >= 0; --i) {
            if (up[i][x] >= y) {
                result = min(result, cur + (1 << i));
            } else {
                cur += (1 << i);
                x = up[i][x];
            }
        }
        printf("%d\n", result);
    }
    return 0;
}


Measured memory_bytes: 8576
'use strict'

const main = input => {
	const args = input.split('\n').map(arg => arg.split(' '))
	const S = args[0][0]
	const N = S.length 
	let ans = false

	for (let i = 0; i < N - 1; i++) {
		if (S.slice(i, i + 2) === 'AC') ans = true
	}

	console.log(ans ? 'Yes' : 'No')
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 21064
#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    string s;
    cin>>s;
    int l=s.length();
    int i=0,cnt=0,max=0;
   while(i<l)
   {
       if(s[i]=='R')
       {
           cnt+=1;
       }
       if(max<cnt){
            max=cnt;
           }
       if(s[i]!='R')
       {

           cnt=0;
       }
       i++;
   }
   cout<<max<<"\n";
    return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
ll p[200005];
int a[200005];
typedef pair<int, int> P;
P f(int x) {
	int a;
	a = x % 10;
	int b = 0;
	while (x) {
		b = x;
		x = x / 10;
	}
	return P(a, b);
}
int main() {
	ll n;
	cin >> n;
	map<P, int>mp;
	for (int i = 1; i <= n; i++) {
		P p = f(i);
		mp[p]++;
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		P p = f(i);
		P q(p.second, p.first);
		ans += mp[q];
	}
	cout << ans << endl;
	return 0;
}

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

typedef long long ll;
typedef pair<ll, ll> P;

const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

    ll tmp_a, tmp_b;
    
    if (a == 0 and b == 0) cout << 1 << endl;
    else if (a == 0) {
        cout << b/x + 1 << endl;
    }
    else {
        cout << b/x - (a-1)/x << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

#define FORR(i,b,e) for(int i=(b);i<(int)(e);++i)
#define FOR(i,e) FORR(i,0,e)
#define dump(var) cerr << #var ": " << var << "\n"
#define dumpc(con) for(auto& e: con) cerr << e << " "; cerr<<"\n"

typedef long long ll;
typedef unsigned long long ull;

const double EPS = 1e-6;
const int d4[] = {0, -1, 0, 1, 0};

using namespace std;


struct Edge {
    int t, w;
    Edge() {}
    Edge(int t, int w): t(t), w(w) {}
    bool operator<(const Edge &o) const {
        return w > o.w;
    }
};

vector<Edge> edges[10010];


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

    int V, E;
    cin >> V >> E;
    
    FOR(i, E) {
        int s, t, w;
        cin >> s >> t >> w;
        edges[s].push_back(Edge(t, w));
        edges[t].push_back(Edge(s, w));
    }

    set<int> vs;
    priority_queue<Edge> q;
    int total_weight = 0;
    q.push(Edge(0, 0));
    while (vs.size() != V) {
        Edge e = q.top(); q.pop();
        if (vs.find(e.t) != vs.end()) continue;
        vs.insert(e.t);
        total_weight += e.w;
        for (auto &ne: edges[e.t]) {
            if (vs.find(ne.t) != vs.end()) continue;
            q.push(ne);
        }
    }

    cout << total_weight << endl;

    return 0;
}

Measured memory_bytes: 4996
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    vi h(n);
    rep(i, n) cin >> h[i];
    sort(h.begin(), h.end());
    int ans = 1001001001;
    rep(i, n-k+1) {
        chmin(ans, h[i+k-1] - h[i]);
    }
    cout << ans << endl;
}

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

using namespace std;

class UnionFind {
  vector<int> data;
  public:
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
      x = root(x); y = root(y);
      if (x != y) {
          if (data[y] < data[x]) swap(x, y);
          data[x] += data[y]; data[y] = x;
      }
      return x != y;
  }
  bool findSet(int x, int y) {
      return root(x) == root(y);
  }
  int root(int x) {
      return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
      return -data[root(x)];
  }
};

int main(){
  int N,M;
  cin >> N >> M ;
  int *A=new int[M];
  int *B=new int[M];
  for(int i=0;i<M;i++){
    cin >> A[i] >> B[i];
    A[i]--;
    B[i]--;
  }
  UnionFind bridge(N);
  vector<long long> conv(M+1,0);
  for(int i=M-1;i>=0;i--){
    if(bridge.findSet(A[i],B[i])==false){
      conv[i]=conv[i+1]+bridge.size(A[i])*bridge.size(B[i]);
      bridge.unionSet(A[i],B[i]);
    }else{
      conv[i]=conv[i+1];
    }
  }
  for(int i=1;i<=M;i++){
    cout << conv[0]-conv[i] <<endl;
  }
  return 0;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define gc() getchar()
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc() ; !(tmp >= '0' && tmp <= '9') ; tmp = gc())
    key = (tmp == '-');
  for ( ; tmp >= '0' && tmp <= '9' ; tmp = gc())
    x = (x << 3) + (x << 1) + tmp - '0';
  if (key) x = -x;
}
typedef long long ll;
const int MAX = 2500, M = 8, N = 100010;
const ll MAXV = (ll)(1e10);
int isp[MAX + 10],pri[MAX],pcnt;
void prework() {
  for (int i = 2 ; i <= MAX ; ++ i) {
    if (!isp[i]) pri[++pcnt] = i;
    for (int j = 1 ; j <= pcnt && pri[j] * i <= MAX ; ++ j) {
      isp[i * pri[j]] = 1;
      if (i % pri[j] == 0) break;
    }
  }
}
int n,val[N],fac[N][M],num[N][M],fcnt[N],res[N],ans;
map<int,int> match,mp,sqr;
signed main() {
  prework();
  read(n);
  for (int i = 1 ; i <= n ; ++ i)
    read(val[i]);
  for (int i = 1 ; i <= n ; ++ i)
    for (int j = 1 ; j <= pcnt && 1ll * pri[j] * pri[j] * pri[j] <= val[i]; ++ j)
      while (val[i] % (1ll * pri[j] * pri[j] * pri[j]) == 0)
	val[i] /= 1ll * pri[j] * pri[j] * pri[j];
  for (int i = 1 ; i <= n ; ++ i) {
    res[i] = val[i];
    ++ mp[val[i]];
    for (int j = 1 ; j <= pcnt && pri[j] <= res[i] ; ++ j)
      if (res[i] % pri[j] == 0) {
	num[i][++fcnt[i]] = pri[j];
	while (res[i] % pri[j] == 0)
	  fac[i][fcnt[i]] ++, res[i] /= pri[j];
      }
  }
  for (int i = 1 ; 1ll * i * i <= MAXV ; ++ i)
    sqr[1ll * i * i] = i;
  for (int i = 1 ; i <= n ; ++ i) {
    __int128 tmp = 1;
    for (int j = 1 ; j <= fcnt[i] ; ++ j)
      if (fac[i][j] == 1) tmp *= num[i][j] * num[i][j];
      else tmp *= num[i][j];
    if (sqr.count(res[i]))
      tmp *= sqr[res[i]];
    else tmp *= res[i] * res[i];
    if (tmp > MAXV) tmp = -1;
    if (tmp < val[i] && tmp != -1)
      match[tmp] = val[i];
    else match[val[i]] = tmp;
  }
  for (map<int,int>::iterator t = match.begin() ; t != match.end() ; ++ t) {
    if (t->first == 1) ans ++;
    else ans += max(mp[t->first],mp[t->second]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 36736
# include <stdio.h>

int main(){
    int n;
    scanf("%d", &n);

    if (n == 999)
        printf("%d", 111);
    else if (n == 991)
        printf("%d", 119);
    else if (n == 919)
        printf("%d", 191);
    else if (n == 199)
        printf("%d", 911);
    else if (n == 911)
        printf("%d", 199);
    else if (n == 191)
        printf("%d", 919);
    else if (n == 119)
        printf("%d", 991);
    else
        printf("%d", 999);    


    return 0;
}

Measured memory_bytes: 128
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.string;

void main() {
    auto N = readln.chomp.to!int;
    auto AB = N.iota.map!(_ => readln.split.map!(to!long).array).array;

    Tuple!(long, int, int)[] C;

    foreach (i; 0..N) {
        foreach (j; 0..2) {
            C ~= tuple(AB[i][j], i, j);
        }
    }
    C.sort!"a[0] < b[0]";

    long ans = 0;
    auto cnt1 = new int[](N);
    auto cnt2 = new int[](2);

    foreach (i; 0..N) {
        ans += C[i][0];
        cnt1[C[i][1]] += 1;
        cnt2[C[i][2]] += 1;
    }

    if (cnt1.map!(c => c == 1).all && cnt2[0] != 0 && cnt2[1] != 0) {
        if (C[N-1][1] == C[N][1]) {
            ans = min(ans - C[N-2][0] + C[N][0], ans - C[N-1][0] + C[N+1][0]);
        } else {
            ans = ans - C[N-1][0] + C[N][0];
        }
    }

    ans.writeln;
}


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

int table[] = {
  0, 2, 5, 5, 4, 5, 6, 3, 7, 6
};

int n, m;
int a[10];
bool dp[10001][10001];
char dig[10001][10001];
int main() {
  cin >> n >> m;
  for (int p = 0; p < m; ++p) {
    cin >> a[p];
  }
  sort(a, a + m);
  
  dp[0][0] = true;
  for (int i = 1; i <= n; ++i) {
    for (int k = 1; k <= n; ++k) {
      for (int p = m - 1; p >= 0; --p) {
        int d = a[p];
        int c = table[d];
        if (k - c < 0) continue;
        if (dp[i - 1][k - c]) {
          dp[i][k] = true;
          dig[i][k] = d;
          break;
        }
      }
    }
  }
  
  string ans;
  int i = n;
  while (!dp[i][n]) {
    --i;
  }
  
  int k = n;
  for (; i > 0; --i) {
    int d = dig[i][k];
    int c = table[d];
    ans += '0' + d;
    k -= c;
  }
  cout << ans << endl;
}

Measured memory_bytes: 99456
def main():
    n = int(input())
    l = list(map(int, input().split()))

    if n <= 2:
        print(0)
        return 0
    
    l.sort(reverse=True)
    
    cnt = 0
    for i in range(n-2):
        for j in range(i+1, n-1):
            for k in range(j+1, n):
                if l[i] == l[j] or l[j] == l[k]:
                    continue
                elif l[i] < l[j] + l[k]:
                    cnt += 1

    print(cnt)

    

if __name__ == '__main__':
    main()

Measured memory_bytes: 67996
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
long long n,m,i,j,k,l,dp[200005][3][3][2],sum,cnt,cnt2,mod=998244353,ans;
string st;
int main()
{
	ios_base::sync_with_stdio(0); 
	cin>>st;
	if (st.length()==2)
	{
		if (st[0]==st[1]) cout<<1; else cout<<2;
		return 0;
	}
	if (st.length()==3)
	{
		if (st[0]!=st[1]&&st[1]!=st[2]&&st[0]!=st[2]) cout<<3;
		else if (st[0]==st[1]&&st[1]==st[2]) cout<<1;
		else if (st[0]!=st[2]) cout<<6;
		else cout<<7;
		return 0; 
	}
	for (i=0;i<st.length();i++)
	{
		sum+=st[i]-'a';
		if (i&&st[i-1]!=st[i]) cnt++;
		if (i&&st[i-1]==st[i]) cnt2++;
	}
	if (cnt==0)
	{
		cout<<1;
		return 0;
	}
	dp[1][0][0][0]=1;
	dp[1][1][1][0]=1;
	dp[1][2][2][0]=1;
	n=st.length();
	for (i=2;i<=n;i++)
	{
		for (j=0;j<3;j++)
		{
			for (k=0;k<3;k++)
			{
				for (l=0;l<3;l++)
				{
					if (l!=k)
					{
						(dp[i][(j+l)%3][l][0]+=dp[i-1][j][k][0])%=mod;
						(dp[i][(j+l)%3][l][1]+=dp[i-1][j][k][1])%=mod;
					}
					else
					{
						(dp[i][(j+l)%3][l][1]+=dp[i-1][j][k][0]+dp[i-1][j][k][1])%=mod;
					}
				}
			}
		}
	}
	if (!cnt2) ans=1; else ans=0;
	for (i=0;i<3;i++) (ans+=dp[n][sum%3][i][1])%=mod;
	cout<<ans;
	return 0;
}

Measured memory_bytes: 28692
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int INF = numeric_limits<int>::max() / 2;

const int n = 100001;
vector<bool> dp(100001,false); //falseなら素数

void Eratosthenes(){
    dp[0] = dp[1] = true;
    for(int i = 2; i < n; i++){
        if(dp[i]) continue;
        for(int j = i * 2; j < n; j += i){
            dp[j] = true;
        }
    }
}

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

	int q;
	cin >> q;

	vector<int> ruisekiwa(100005,0);
	for(int i = 1; i <= 100000; i++){
		ruisekiwa[i] = ruisekiwa[i-1];
		if(!dp[i] && !dp[(i+1)/2]) ruisekiwa[i]++;
	}

	for(int i = 0; i < q; i++){
		int l,r;
		cin >> l >> r;
		cout << ruisekiwa[r] - ruisekiwa[l-1] << endl;
	}
	return 0;
}

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

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define MOD 1000000007

string str1,str2;
int ans;
int a,b;
int n;

int main(){
  cin >> n ;

  cout << n*n*n << endl;
  return 0;
}

Measured memory_bytes: 256
#![allow(non_snake_case, unused_macros, unused_imports)]

// Input
macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect() }; input_inner!{next, $($r)*} }; }
macro_rules! input_inner { ($next:expr) => {}; ($next:expr, ) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} };}
macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ( $(read_value!($next, $t)),* ) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::<Vec<char>>() }; ($next:expr, bytes) => { read_value!($next, String).into_bytes() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; }

// Module
use std::cmp::{min,max};
use std::collections::{HashSet,BTreeMap};

// Main
fn main(){
    input!{
        a: [i32; 3],
    }
    let mut a = a;
    a.sort_by(|a,b| b.cmp(a));
    println!("{}", if a[0]==a[1]+a[2] {"Yes"} else {"No"});
}




Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};
vi dir2 = {0, 1, 0};

int main() {
  int h, w;
  cin >> h >> w;
  vector<vi> g(h + 2, vi(w + 2, -1));
  rep2(i, 1, h + 1) rep2(j, 1, w + 1) {
    char c;
    cin >> c;
    if(c == '#') g[i][j] = 0;
  }
  vi v;
  rep(i, h - 1) v.push_back(0);
  rep(j, w - 1) v.push_back(1);
  sort(all(v));
  bool ans = false;
  do {
    int i = 1, j = 1;
    vector<vi> gg = g;
    gg[1][1] = 1;
    bool ok = true;
    for(auto k : v) {
      if(k % 2)
        j++;
      else
        i++;
      if(gg[i][j] == -1)
        ok = false;
      else
        gg[i][j] = 1;
    }
    rep2(ih, 1, h + 1) rep2(jw, 1, w + 1) if(gg[ih][jw] == 0) ok = false;
    if(ok) ans = true;
  } while(next_permutation(all(v)));
  cout << (ans ? "Possible" : "Impossible") << endl;
}

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

using namespace std;

const int MOD = 1e9 + 7;

void dfs_and_solve(int rad, vector <vector <int> > &v, vector <vector <int> > &dp, vector <bool> &viz) {
    viz[rad] = true;
    for (auto &&node: v[rad]) {
        if (!viz[node]) {
            dfs_and_solve(node, v, dp, viz);
            dp[rad][0] = (1ll * dp[rad][0] * (dp[node][0] + dp[node][1])) % MOD;
            dp[rad][1] = (1ll * dp[rad][1] * dp[node][0]) % MOD;
        }
    }
}

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

    vector <vector <int> > v(n + 1);
    vector <int> grad(n + 1, 0);
    int x, y;
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        grad[x]++;
        grad[y]++;
    }

    int rad = 1;
    for (int i = 1; i <= n; i++) {
        if (grad[i] == 1) {
            rad = i;
            break;
        }
    }

    vector <vector <int> >dp(n + 1, vector <int> (2, 1));
    vector <bool> viz(n + 1, false);
    
    dfs_and_solve(rad, v, dp, viz);
    cout << (dp[rad][0] + dp[rad][1]) % MOD << '\n';
    return 0;
}

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

int main(){
  int N;
  cin>>N;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin>>a.at(i);
    a.at(i) = a.at(i)-1-i;
  }
  
  /*for(int i=0;i<N;i++){
    cout << a.at(i) << " ";
  }
  cout << endl;*/
  
  sort(a.begin(),a.end());
  int med=a.at(N/2);
  long long int ans = 0;
  for(int i=0;i<N;i++){
    ans += abs(a.at(i)-med);
  }
  
  /*for(int i=0;i<N;i++){
    cout << a.at(i) << " ";
  }
  cout << endl;*/
  
  cout <<ans <<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N = 205;

int arr [MAX_N];

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

  n *= 2;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }

  sort(arr, arr + n);

  int ans = 0;
  for (int i = 0; i < n; i += 2) {
    ans += arr[i];
  }

  cout << ans << endl;
}


Measured memory_bytes: 3632
my $N = <STDIN>;
my $s = <STDIN>;
@s = split(/ /,$s);

my $down_flag = 0;

for(my $i = 1; $i < $N;$i++ ){
  if( $s[$N-$i-1] <$s[$N-$i] ){
    if( $down_flag == 0 ) { 
     next;
    }else{ 
       $down_flag = 0;
    }
  }elsif($s[$N-$i-1] == $s[$N-$i] ){
    next;
  }else{
   if( ($s[$N-$i-1] - 1 )== $s[$N-$i] ){
     if(  $down_flag == 0 ){
       $down_flag = 1;
     }else{
        print "No\n";
        exit;
     }
   }else{
     print "No\n";
     exit;
   }
  }
}
print "Yes\n";


Measured memory_bytes: 11724
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll h, w, n, x, y;
  in3(h, w, n);
  ll a = 0;
  vector<ll> c(n);
  rep(i, n)
    in(c[i]);
  vector<vector<ll>> d(h, vector<ll> (w));
  x = y = 0;
  rep(i, n){
    rep(j, c[i]){
      d[y][x] = i + 1;
      if(a == 0 && x == w - 1){
        y++;
        a++;
      }
      else if(a == 1 && x == 0){
        y++;
        a--;
      }
      else if(a == 0)
        x++;
      else
        x--;
    }
  }
  rep(i, h){
    rep(j, w){
      out(d[i][j]);
        cout<<" ";
    }
    memi;
  }
}


Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int mod = 1e9+7;
#define ll long long
int dp[2010][2010];
int n, k;
int main()
{
	
	dp[0][0] = 1;
	for (int i = 1; i < 2010; i++)
	{
		dp[i][0] = 1;
		for (int j = 1; j < 2010; j++)
		{
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
			if (dp[i][j] >= mod)dp[i][j] -= mod;
		}

	}cin >> n >> k;
	for (int i = 1; i <= k; i++)
		cout << (1ll*dp[k-1][i - 1] * dp[n - k+1][i] % mod) << endl;
}

Measured memory_bytes: 16000
#xorの性質
#AxorA=0、交換法則、結合法則が成立、bitごとに独立して考える！

import numpy as np

n=int(input())
a=np.array(list(map(int,input().split())))
res=0
for j in range(60):
  s=0 #1の数
  """
  for i in a:
    if (i>>j & 0b1)==0b1:
      s+=1
  """
  s=np.count_nonzero(a>>j&1)
  r=2**j*(n-s)*s
  res=(res+r)%(10**9+7)
print(res)

Measured memory_bytes: 48840