akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl;

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<long long, long long> pll;

const int INF = 1 << 30;
const long long INFL = 1LL << 62;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 2000;

int main() {
	int h, w;
	cin >> h >> w;
	string s[N];
	rep(i, h) cin >> s[i];

	vector<vector<int>> light_h(h + 2, vector<int>(w + 2));
	vector<vector<int>> light_v(h + 2, vector<int>(w + 2));
//	int light_h[N + 2][N + 2], light_v[N + 2][N + 2];
//	rep(i, h + 2) rep(j, w + 2) {
//		light_h[i][j] = 0;
//		light_v[i][j] = 0;
//	}

	for(int i = 1; i <= h; i++) {
		for(int j = 1; j <= w; j++) {
			if(s[i - 1][j - 1] == '.') {
				light_h[i][j] = light_h[i][j - 1] + 1;
			}
		}
		for(int j = w; j >= 1; j--) {
			if(light_h[i][j + 1] > 0 && light_h[i][j] > 0) {
				light_h[i][j] = light_h[i][j + 1];
			}
		}
	}
	for(int i = 1; i <= w; i++) {
		for(int j = 1; j <= h; j++) {
			if(s[j - 1][i - 1] == '.') {
				light_v[j][i] = light_v[j - 1][i] + 1;
			}
		}
		for(int j = h; j >= 1; j--) {
			if(light_v[j + 1][i] > 0 && light_v[j][i] > 0) {
				light_v[j][i] = light_v[j + 1][i];
			}
		}
	}
	
	int ans = 0;
	for(int i = 1; i <= h; i++) {
		for(int j = 1; j <= w; j++) {
			ans = max(light_h[i][j] + light_v[i][j] - 1, ans);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 35840
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	string n; cin >> n;
	int sum = 0;
	for(char c : n) {
		sum += (c - '0');
		sum %= 9;
	}
	cout << (sum % 9 == 0 ? "Yes" : "No") << '\n';
	return 0;
}

Measured memory_bytes: 3752
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] n = sc.next().toCharArray();

        sc.close();

        if ((n[0] == n[1] && n[1] == n[2])
                || (n[1] == n[2] && n[2] == n[3])) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21716
#include <iostream>
#include <cstdint>
#include <string>
#include <cstdlib>

int main() {
  std::int_fast64_t n;
  std::string s;
  std::cin >> n >> s;

  std::int_fast64_t counter = 0;
  std::int_fast64_t open_count = 0;
  for (const char& c : s) {
    switch (c) {
    case '(':
      ++counter;
      break;
    case ')':
      --counter;
      if (counter < 0) {
        ++open_count;
        counter = 0;
      }
      break;
    default:
      std::exit(EXIT_FAILURE);
    }
  }

  std::cout << std::string(open_count, '(') << s << std::string(counter, ')') << std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;

#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector<ll>
#define vld vector<ld>
#define pll pair<ll,ll> 
#define pld pair<ld,ld> 
#define vpll vector<pll>
#define vpld vector<pld>
#define all(X) X.begin(),X.end()
#define endl "\n"
#define sz(x) ((ll)((x).size()))
const ll N=2e5+5,inf=1e9;
ll ary[N];
ll ans[N];
vll G[N];
ll n;
ll tree[4*N];
multiset<ll> res;
ll query(ll nd,ll st,ll ed,ll l,ll r)
{
	if(st>r||ed<l||st>ed)return 0;
	if(st>=l && ed<=r)
		return tree[nd];
	ll mid=(st+ed)/2;
	return max(query(2*nd,st,mid,l,r),query(2*nd+1,mid+1,ed,l,r));
}
void update(ll nd,ll st,ll ed,ll id,ll val)
{
	if(st>=id&&ed<=id)
	{
		tree[nd]=val;
	}
	else
	{
		ll mid=(st+ed)/2;
		if(mid>=id)
			update(2*nd,st,mid,id,val);
		else
			update(2*nd+1,mid+1,ed,id,val);
		tree[nd]= max(tree[2*nd],tree[2*nd+1]);
	}
}

ll dfs(ll a,ll p)
{
	ll x=query(1,0,n-1,0,ary[a-1]-1);
	ll pre=query(1,0,n-1,ary[a-1],ary[a-1]);
	res.insert(x+1);
	update(1,0,n-1,ary[a-1],x+1);
	ans[a]=*(--res.end());	
	lp(i,0,G[a].size())
	{
		ll x=G[a][i];
		if(x!=p)
			dfs(x,a);
	}
	update(1,0,n-1,ary[a-1],pre);
	res.erase(res.find(x+1));
	return 0;
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin >> n;
	vll v;
	lp(i,0,n)
	{
		cin >> ary[i];
		v.pb(ary[i]);
	}	    
	map<ll,ll> M;
	sort(all(v));
	ll c=0;
	lp(i,0,n)
	{
		if(M.count(v[i])==0)
		{
			M[v[i]]=c++;
		}
	}
	lp(i,0,n)
	{
		ary[i]=M[ary[i]];
	}
	lp(i,0,n-1)
	{
		ll u,v;
		cin >>u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1,0);
	lp(i,0,n)
	{
		cout<<ans[i+1]<<endl;
	}
	return 0;
}

Measured memory_bytes: 52568
#include <bits/stdc++.h>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

vector<int> L(MAX/2+2), R(MAX/2+2);
int cnt;

void merge(vector<int> &A, int n, int left, int mid, int right) {
    int n1 = mid - left;
    int n2 = right - mid;
    for (int i = 0; i < n1; i++) L.at(i) = A.at(left + i);
    for (int i = 0; i < n2; i++) R.at(i) = A.at(mid + i);
    L[n1] = R[n2] = SENTINEL;
    int i = 0, j = 0;
    for (int k = left; k < right; k++) {
        cnt++;
        if (L.at(i) <= R.at(j)) {
            A.at(k) = L.at(i++);
        } else {
            A.at(k) = R.at(j++);
        }
    }
}

void mergeSort(vector<int> &A, int n, int left, int right) {
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        mergeSort(A, n, left, mid);
        mergeSort(A, n, mid, right);
        merge(A, n, left, mid, right);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A.at(i);
    }
    mergeSort(A, n, 0, n);
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        cout << A.at(i);
    }
    cout << endl;
    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 6792
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
  ll n;
  cin >> n;
  if(n%2==1){
    cout << 0;
    return 0;
  }
  ll ans=0;
  ll p=10;
  while(n>=p){
    ll q=n%p;
    ll cp=n-q;
    ans+=cp/p;
    p*=5;
  }
  cout << ans;
}
    
    

Measured memory_bytes: 3604
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Kein Yukiyoshi
 */

#include "bits/stdc++.h"
#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) begin(obj), end(obj)
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))
#define Endl endl

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);

int ceil_(int a, int b) { return (a + (b - 1)) / b; }
int positive_surplus(int &a) { return (a + MOD) % MOD; }
int bpm(int x, unsigned int y) {
  if (x == 0) return 0;
  if (y == 0) return 1;
  int ans   = 1;
  int digit = (int)((log((double)y) / log((double)2) / 1 + 1));
  x %= MOD;
  for (int i = 0; i < digit; i++) {
    if (((y >> i) & 1u) == 1) ans = ans * x % MOD;
    x = x * x % MOD;
  }
  return ans;
}
template <class T>
void cumulative_sum(T &container) {
  for (int i = 0; i < container.size() - 1; i++) container[i + 1] += container[i];
}

class AZeroSumRanges {
public:
  static void solve(std::istream &cin, std::ostream &cout) {
    int N;
    cin >> N;
    vector<int> A(N + 1, 0);
    map<int, vector<int>> mp;
    mp[0].emplace_back(1);
    rep(i, N) {
      cin >> A[i + 1];
      A[i + 1] += A[i];
      mp[A[i + 1]].emplace_back(1);
    }
    int ans = 0;
    rep(i, N) {
      mp[A[i]].pop_back();
      ans += mp[A[i]].size();
    }
    cout << ans << endl;
  }
};


signed main() {
  AZeroSumRanges solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}


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

using namespace std;

typedef long long ll ;
typedef double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< pair<int,int> > vii;
const double pi = 2*acos(0) ;

#define pf		  	 printf
#define sf			 scanf
#define pb(a)        push_back(a)
#define mp			 make_pair
#define ff			 first
#define ss			 second
#define for0(i,n)    for(int i=0;i<n;i++)
#define for1(i,n)    for(int i=1;i<=n;i++)
#define forab(i,a,b) for(int i=a;i<=b;i++)
#define lcm(a, b)    ((a)*((b)/gcd(a,b)))
#define sq(a)		 (a)*(a)
#define endl		     "\n"
#define abs(x)		 fabs(x)
#define all(v) 		 v.begin(),v.end()
#define pcase(z,x)   cout<<"Case "<<z<<": "<<x<<"\n"
#define mod 1000000007
#define WakandaForever     ios_base::sync_with_stdio(0); cin.tie(0);
ll dp[1000007];
int main()
{
    WakandaForever
    ll s;
    cin>>s;
    dp[0] = 1;
    for(ll i=1 ; i<=s ; i++){
        for(ll j=3 ; j<=s ; j++){
            if(i>=j) dp[i] = (dp[i] + dp[i-j])%mod;
        }
    }
    cout<<dp[s]<<endl;

    return 0;
}

Measured memory_bytes: 3648
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <math.h>
#include <string.h>
#include <string>
#include <queue>
#include <stack>
using namespace std;
typedef long long int ll;
map<pair<ll, ll> , int> visited;
pair<ll, ll> point[111111];
ll h, w, n;
ll ans[10];
int dy[9]={0,1,1,1,0,-1,-1,-1,0};
int dx[9]={1,1,0,-1,-1,-1,0,1,0};

int exist(ll u, ll v)
{
	if(lower_bound(point+1,point+n+1,make_pair(u,v))!=upper_bound(point+1,point+n+1,make_pair(u,v)))
	{
		return 1;
	}
	return 0;
}

int main(void)
{
	cin>>h>>w>>n;
	int i,j, k;
	ll u, v;
	ll tot=(h-2)*(w-2);
	for(i=1 ; i<=n ; i++)
	{
		scanf("%lld %lld",&u,&v);
		point[i]=make_pair(u,v);
	}
	sort(point+1,point+n+1);
	for(i=1 ; i<=n ; i++)
	{
		for(j=0 ; j<9 ; j++)
		{
			int cnt=0;
			ll y, x;
			y=point[i].first+dy[j];
			x=point[i].second+dx[j];
			if(visited.find(make_pair(y,x))==visited.end() && y>=2 && y<=h-1 && x>=2 && x<=w-1)
			{
				for(k=0 ; k<9 ; k++)
				{
					cnt+=exist(y+dy[k],x+dx[k]);
				}
				ans[cnt]++;
				visited[make_pair(y,x)]=1;
			}
		}
	}
	for(i=1 ; i<=9 ; i++)
	{
		tot-=ans[i];
	}
	printf("%lld\n",tot);
	for(i=1 ; i<=9 ; i++)
	{
		printf("%lld\n",ans[i]);
	}
}

Measured memory_bytes: 58112
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define r register
using namespace std;
inline void rd(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
void pt(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)pt(x/10);putchar(x%10+48);
}
long long n,m,a[1200],cnt;
int main()
{
	cin>>n;m=n;
	if(n==0)
	{
		cout<<0;
		return 0;
	}
	while(m)
	{
		a[++cnt]=m%(-2);
		m/=(-2);
	}
	for(int i=1;i<=cnt;i++)
	{
		if(a[i]==-1)a[i]=1,a[i+1]++;
		a[i+1]+=a[i]/2;
		a[i+2]+=a[i]/2;
		a[i]%=2;
	}int bi=0;
	for(int i=cnt+2;i;i--)
	{
		if(bi==0&&a[i]==0)continue;
		bi=1;printf("%d",a[i]);
	}
}

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

using namespace std;

long int vi[100005],dp[100005][105];
int wi[100005];
int main()
{
	int n,w;
	scanf("%d%d",&n,&w);
	for(int i=0;i<n;++i)
	scanf("%d%ld",wi+i,vi+i);
	for(int i=0;i<=w;++i)
	{
		for(int j=0;j<=n;++j)
		{
			if(i == 0 || j == 0)
			dp[i][j] = 0;
			else if(wi[j-1] > i)
			dp[i][j] = dp[i][j-1];
			else
			dp[i][j] = max(dp[i][j-1],dp[i-wi[j-1]][j-1]+vi[j-1]); 
		}
	}
	printf("%ld\n",dp[w][n]);
	return 0;
}


Measured memory_bytes: 82304
/* Kadai6_2
   saitomo  */

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

#define SIZE 150

int main(void){
    int length;
    char word[SIZE];
    fgets(word, SIZE, stdin);//英単語を入力
    length = strlen(word);//文字列の長さをlengthとする
    printf("%c%d%c\n", word[0], length-3, word[length-2]);//最初の文字(word[0]),間の数字(length-3),最後の数字(word[length-2])を足して出力
    return 0;
}


Measured memory_bytes: 128
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define pii pair<int, int>
#define pll pair<long long, long long>
const double PI = acos(-1);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    while (1) {
        int x,y,s; cin >> x >> y >> s;
        if (x == 0 && y == 0 && s == 0) break;
        vector<int> A(s);
        int ans = 0;
        for (int i = 1; i < s; i++) A[i] = i*(100+x)/100;
        for (int i = 1; i < s; i++) {
            for (int j = 1; j < s; j++) {
                if (A[i]+A[j] == s) {
                    chmax(ans,i*(100+y)/100+j*(100+y)/100);
                }
            }
        }

        cout << ans << endl;

    }
}


Measured memory_bytes: 3112
import scala.io.StdIn._
object Main extends App {
  val n = readInt()
  val str = readLine.trim
  val count = ('a' to 'z').map(c ⇒ str.count(_ == c)).toArray
  val mod = 1000000007L
  println(
    (count.foldLeft(1L){(a, b) ⇒ a * (b + 1) % mod} - 1 + mod) % mod
  )
}

Measured memory_bytes: 29300
class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,k=map(int,input().split())
arr=[0]+[int(input()) for _ in range(n)]
for i in range(1,n+1):
  arr[i]+=arr[i-1]-k
s=set(arr)
key=sorted(list(s))
dic={}
for i in range(len(key)):
  dic[key[i]]=i+1
bit=BIT(len(key)+1)
ans=0
bit.add(dic[0],1)
for i in range(1,n+1):
  ans+=bit.sum(1,dic[arr[i]])
  bit.add(dic[arr[i]],1)
print(ans)

Measured memory_bytes: 55900
#include<stdio.h>

int main() {
	int p;
	int sum = 0;
	for (int i = 0; i < 5; ++i) {
		scanf("%d", &p);
		if (p < 40) { p = 40; }
		sum += p;
	}
	printf("%d\n", sum / 5);

	return 0;
}

Measured memory_bytes: 2764
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
using namespace std;
int mod = 1e9+7;

int main() {

  int n; cin >> n;
  string s = "";
  while(n != 0){
    if(n%(-2) != 0){
      n--;
      s += '1';
    }else s += '0';
    n /= -2;
  }
  if( s.size() == 0 ){
    cout << "0" << endl;
    return 0;
  }
  reverse(s.begin(), s.end());
  cout << s << endl;

  return 0;
}




//


Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int n;
	int s;
	while(1){
		scanf("%d %d\n",&n,&s);
		if(!n&&!s)break;
		int i;
		int all[101][10];
		int j,k;
		for(j=0;j<101;j++)for(k=0;k<10;k++)all[j][k]=0;
		int bcnt;
		int bnum;
		for(i=1;i<(0x1<<10);i++){
			bcnt=0;
			bnum=0;
			for(j=0;j<10;j++){
				if(i&(0x1<<j)){
					bcnt++;
					bnum+=j;
				}
			}
			if(bnum<=s)all[bnum][bcnt]++;
		}
		printf("%d\n",all[s][n]);
	}
	
	return 0;
}

Measured memory_bytes: 604
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll bg=pow(10,9)+7;
#define ff(i,n) for(i=0;i<n;i++)
#define gg1(n1) cin>>n1;
#define gg(n1,n2) cin>>n1>>n2;
#define gg3(n1,n2,n3) cin>>n1>>n2>>n3;
#define hh(n) cout<<n<<endl;
#define t top
#define p push
#define pb push_back
#define mp make_pair
int main()
{
  string s,f;
  cin>>f>>s;
  ll n=f.length(),m=s.length();
  ll dp[n+1][m+1],i,j;
  for(i=0;i<=n;i++)
    for(j=0;j<=m;j++)
       dp[i][j]=0;
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
       {
            if(f[i-1]==s[j-1])
               dp[i][j]=max(dp[i][j],1+dp[i-1][j-1]);
            dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1]));
       }
  string ans;
  ll maxi=dp[n][m];
  for(i=n;i>=1;i--)
    for(j=m;j>=1;j--)
    {
       if(dp[i][j]==maxi&&s[j-1]==f[i-1])  
         {
              maxi--;
              ans.pb(s[j-1]);
           /*i**nn*/  break;                                                                        //up
         }
    }
   reverse(ans.begin(),ans.end()); 
  cout<<ans;
  return 0;
}

Measured memory_bytes: 70656
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int A = Integer.parseInt(scanner.next());
        int B = Integer.parseInt(scanner.next());
        String S = scanner.next();
        scanner.close();

        if (S.matches(String.format("^[0-9]{%d}-[0-9]{%d}", A, B))) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 21716
#include <iostream>
#define llint long long

using namespace std;

llint l, k;
llint dp[105][2];

int main(void)
{
  cin >> l >> k;
  dp[0][0] = 1;
  for(int i = 0; i < l; i++){
    if(i+k <= l) dp[i+k][1] += dp[i][0];
    dp[i+1][1] += dp[i][0];
    dp[i+1][0] += dp[i][1];
  }

  llint ans = 0;
  for(int i = 1; i <= l; i++){
    ans += dp[i][1];
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3088
n = gets.to_i
l = gets.split.map(&:to_i)

flag = true

if n.odd?
  cn = l.count(0)
  if cn != 1
    flag = false
  end
  syo = n / 2
  amari = n % 2
  nl = l.uniq
  if nl.size != syo + amari
    flag = false
  end
  nl.each do |t|
    if t.odd?
      flag = false
    end
  end
  if flag
    k = n /2
    puts 2 ** k % 1000000007
  else
    puts 0
  end
else
  nl = l.uniq
  if nl.size != (n / 2)
    flag = false
  end
  nl.each do |t|
    if t.even?
      flag = false
    end
  end
  if flag
    k = n /2
    puts 2 ** k % 1000000007
  else
    puts 0
  end
end


Measured memory_bytes: 12692
#[allow(unused_imports)] use proconio::{input, marker::{Bytes, Chars, Usize1, Isize1}};
#[allow(unused_imports)] use std::cmp::{min, max};
#[allow(unused_imports)] use superslice::Ext as _;

#[proconio::fastout]
fn main() {
	input! {
		n: usize,
	}

	let mut count9 = 9usize;
	let mut count8 = 8usize;
	let mut count10 = 10usize;
	for _i in 1..n {
		count9 *= 9;
		count8 *= 8;
		count10 *= 10;

		if count8 > 1000000007 || count8 > 1000000007 || count8 > 1000000007 {
			count8 %= 1000000007;
			count9 %= 1000000007;
			count10 %= 1000000007;
		}
	}

	//println!("{}, {}, {}", count10, count9, count8);
	let ans = (count10 + 1000000007 * 2 - (count9 * 2 - count8)) % 1000000007;

	println!("{}", ans);
}


Measured memory_bytes: 2196
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;

int main()
{
    fastio;
    long long n,x,t,ans;
    cin>>n>>x>>t;
    if(n%x==0)
        ans=(n/x)*t;
    else
        ans=(n/x+1)*t;
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 3632
while True:
    N, M = map(int, raw_input().split())
    if N == 0 and M == 0: break
    h = [input() for _ in range(N)]
    for i in range(N-1):
        h[i+1] += h[i]
    w = [input() for _ in range(M)]
    for i in range(M-1):
        w[i+1] += w[i]
    h = [0] + h
    w = [0] + w
    hl = [0] * (h[-1] + 1)
    wl = [0] * (w[-1] + 1)
    for i in range(N):
        for j in range(i+1, N+1):
            hl[h[j]-h[i]] += 1
    for i in range(M):
        for j in range(i+1, M+1):
            wl[w[j]-w[i]] += 1

    ans = 0
    for i, j in zip(hl, wl):
        ans += i*j
    print ans

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

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

int main(){
	int n;
	cin >> n;
	vector<int> p(n);
	for(int i=0;i<n;i++)	cin >> p.at(i);

	int ans=0;
	for(int i=1;i<n-1;i++){
		int x=p.at(i-1)+p.at(i)+p.at(i+1);
		x-=max({p.at(i-1),p.at(i),p.at(i+1)});
		x-=min({p.at(i-1),p.at(i),p.at(i+1)});
		if(p.at(i)==x)	ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <math.h>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// 最小公倍数
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}*/

ll par[100000 + 10];
ll ran[100000 + 10];

// n要素で初期化
void init(int n) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		ran[i] = 0;
	}
}

// 木の根を求める
int find(ll x) {
	if (par[x] == x) {
		return x;
	}
	else {
		return par[x] = find(par[x]);
	}
}

// xとyの属する集合を併合
void unite(ll x, ll y) {
	x = find(x);
	y = find(y);
	if (x == y) return;

	if (ran[x] < ran[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (ran[x] == ran[y]) ran[x]++;
	}
}

// xとyが同じ集合に属するか否か
bool same(ll x, ll y) {
	return find(x) == find(y);
}


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

	int n, m;
	cin >> n >> m;
	vector<int> p(n);
	rep(i, n) {
		int t;
		cin >> t;
		p[i] = t - 1;
	}
	vector<pair<int, int>> xy(m);
	rep(i, m){
		int x, y;
		cin >> x >> y;
		xy[i].first = x - 1;
		xy[i].second = y - 1;
	}

	// Union-FInd木つかえないか？

	// 繋がりのあるマスとマスのグループを作る
	init(n);

	rep(i, m) {
		//unite(xy[i].first, xy[i].second);
		unite(p[xy[i].first], p[xy[i].second]);
	}

	int ans = 0;

	rep(i, n) {
		if (same(i, p[i])) ans++;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2944
// In the name of god
#include <bits/stdc++.h>
#pragma GCC optimze("02")
using namespace std;
using ll =long long;
const ll maxn=1e5+5,inf=1e18+18;
ll n,m,x,sum;
string s;
int main(){
//	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
	cin>>n;
	while(n>0){
		m=1;
		sum=0;
		while(sum<n){
			m*=26;
			sum+=m;
		}
		sum-=m;
		m/=26;
		x=1;
		while(x*m+sum<n)x++;
		s+=('a'+x-1);
		n-=m*x;
	}
	cout<<s;	
}


Measured memory_bytes: 3628
#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

yes = "Yes"
no = "No"




def main():
    a,b,c = mi()
    if c-a-b<=0:
        print(no)
        exit()
    else:
        if (c-a-b)**2 > 4*a*b:
            print(yes)#gcdは3.4.3だとfractionsにある
from fractions import gcd
import math

from math import factorial as f

from math import ceil,floor,sqrt


import bisect
import re
import heapq


from copy import deepcopy
import itertools

from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

yes = "YES"
no = "NO"

alpha = ['a','b','c','d','e','f','g','h','i','j']


def makealpha(n,depth,tmp,maxtmp):
    if depth == n:
        tmpalpha = ''
        for i in tmp:
            tmpalpha+=alpha[i]
        print(tmpalpha)
    else:
        
        for i in range(maxtmp+2):
            tmptmp = deepcopy(tmp)
            tmptmp.append(i)
            maxtmp = max(maxtmp,i)
            makealpha(n,depth+1,tmptmp,maxtmp)
    return 0


def main():
    n = ii()
    makealpha(n,1,[0],0)

    


main()



Measured memory_bytes: 6448
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define INF (1<<30)

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

	int cnt0=0, cnt1=0;
	for (int i = 0; i < S.length(); i++) {
		if(S[i]=='0') cnt0++;
		if(S[i]=='1') cnt1++;
	}

	cout << min(cnt1,cnt0)*2 << endl;
}



Measured memory_bytes: 512
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    n_half = n // 2
    a = list(map(int, input().split()))
    ls = [0] * n
    ans = []

    for i in range(n-1, -1, -1):
        ai = a[i]
        if ai > n_half:
            ls[i] = ai
            ans.append(i+1)
        elif (sum(ls[i::i+1]) % 2) != ai:
            ls[i] = 1
            ans.append(i+1)
    print(sum(ls))
    if ans:
        print(*ans[::-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 15540
//
//  main.cpp
//  Study
//
//  Created by 佐々木勇星 on 2020/03/12.
//  Copyright © 2020 佐々木勇星. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <algorithm>

using namespace std;


int main(int argc, const char * argv[]) {
    

    int n, m;
    string ans = "No";
    
    cin >> n >> m;
    
    if (n == m) ans = "Yes";
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] strArr = br.readLine().split(" ");
		long[] arr = new long[strArr.length];
		for(int i = 0;i < strArr.length;i++){
			arr[i] = Long.parseLong(strArr[i]);
		}
		System.out.println((arr[0] < arr[1] && arr[1] < arr[2]) ? "Yes" : "No");
	}
}

Measured memory_bytes: 16896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	ll h;
  	cin >> h;
  	
	ll cnt = 1, ret = 0;
  	for (ll i = h; h > 0; h /= 2)
    {
      ret += cnt;
      cnt *= 2;
    }
  cout << ret << endl;
}

Measured memory_bytes: 256
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, K = LI()

    print(N - K + 1)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 10048
#include <bits/stdc++.h>
using namespace std;
#define nin(n) int n; cin >> n;
#define kin(k) int k; cin >> k;
 
int main() {
  unsigned long long x;
  cin >> x;
  int ans=0;
  unsigned long long n=100;
  while(n<x){
    n=(long long)n*1.01;
    ans++;
  }
  cout << ans;
}

Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
using ll = long long;

int main(){
    ll a,b,c,d,e,k,l,m,n,o=0,p,q,x,y,z,max1=0,ans;
    string s,t,u;
    cin>>n>>k>>s;
    s[k-1]=tolower(s[k-1]);
    
    cout<<s<<endl;
}




Measured memory_bytes: 888
H,W = map(int, input().split())
S = []
result=[]
for n in range(H):
    a = list(input())
    a.insert(0,".")
    a.append(".")
    S.append(a)
a = ["."]*(W+2)
S.insert(0,a)
S.append(a)
result=[]


for h in range(H):
    result.append("")
    for w in range(W):
        if S[h+1][w+1]=="#":
            result[h] = result[h] + "#"
        else:
            sum=0
            for i in range(3):
                for j in range(3):
                    if S[h+i][w+j]=="#":
                        sum=sum+1
            sum = sum
            result[h] = result[h] + str(sum)

for h in range(H):
    print(result[h])

Measured memory_bytes: 3064
#include <iostream>

int main()
{
   const long long kMod = 1000000007;
   int n, oddness;
   std::cin >> n >> oddness;
   long long ***dp = new long long**[55];
   for (int i = 0; i < 55; i++) {
      dp[i] = new long long*[55];
      for (int j = 0; j < 55; j++) {
         dp[i][j] = new long long[2550];
         for (int k = 0; k < 2550; k++) {
            dp[i][j][k] = 0;
         }
      }
   }
   dp[0][0][0] = 1;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < i + 1; j++) {
         for (int k = 0; k < oddness + 1; k++) {
            dp[i + 1][j][k + 2 * j] += dp[i][j][k];
            dp[i + 1][j][k + 2 * j] %= kMod;
            dp[i + 1][j + 1][k + 2 * (j + 1)] += dp[i][j][k];
            dp[i + 1][j + 1][k + 2 * (j + 1)] %= kMod;
            dp[i + 1][j][k + 2 * j] += 2 * j * dp[i][j][k] % kMod;
            dp[i + 1][j][k + 2 * j] %= kMod;
            if (j) {
               dp[i + 1][j - 1][k + 2 * (j - 1)] += j * j * dp[i][j][k] % kMod;
               dp[i + 1][j - 1][k + 2 * (j - 1)] %= kMod;
            }
         }
      }
   }
   std::cout << dp[n][0][oddness] << std::endl;
   
   return 0;
}


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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) (a).begin(),(a).end()
#define SORT(a) sort(all(a))
using ll = long long;
constexpr ll INF = 10000000000;
constexpr ll MOD = 1000000007;

using namespace std;

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	long long g = gcd(a, b);
	return a / g * b;
}

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

	vector<int>r(10);
	for (int i = 1; i < 9; i++) {
		r[i] = pow(2, i);
	}
	
	if (n == 1) {
		cout << 1 << endl;
		return 0;
	}

	for (int i = 0; i < 9; i++) {
		if (r[i] > n) {
			cout << r[i - 1] << endl;
			return 0;
		}
	}
}


Measured memory_bytes: 512
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

/*
thx
http://topcoder.g.hatena.ne.jp/kuuso1/20170124/1485278180
*/
void solve(){
	int N;
	LL A,B;
	cin >> N >> A >> B;
	vector<LL> S(N+1);
	S[0] = -LINF;
	for(int i=0;i<N;++i){
		cin >> S[i+1];
	}
	if( A > B ){
		swap(A,B);
	}
	
	if( N == 1 ){
		cout << 2 << endl;
		return;
	}
	vector<LL> dpA(N+1,0),dpB(N+1,0);
	vector<LL> sumA(N+2,0),sumB(N+2,0);
	dpA[0] = 1;
	sumA[1] = 1;
	dpB[0] = 1;
	sumB[1] = 1;

	int clA = 0;//[0,clA)
	int clB = 0;
	int okA = 0;
	int okB = 0;
	for(int i=1;i<N;++i){
		while(S[okA] <= S[i+1] - A && okA < i ){
			okA++;
		}
		while(S[okB] <= S[i+1] -B && okB < i ){
			okB++;
		}

		if(okA >= clB ){
			dpA[i] = sumB[okA]-sumB[clB] + MOD;
		}
		if(dpA[i] >= MOD ){dpA[i] -= MOD;}
		if(okB >= clA ){
			dpB[i] = sumA[okB]-sumA[clA] + MOD;
		}
		if( dpB[i] >= MOD ){dpB[i] -= MOD;}

		if(S[i+1]-A < S[i]) clA = i;
		if(S[i+1]-B < S[i]) clB = i;

		sumA[i+1] = sumA[i] + dpA[i];
		if(sumA[i+1]>=MOD)sumA[i+1]-=MOD;
		sumB[i+1] = sumB[i] + dpB[i];
		if(sumB[i+1]>=MOD)sumB[i+1]-=MOD;
	}
	LL ans = sumA[N]+sumB[N]+
			(-sumA[clA]+MOD)+
			(-sumB[clB]+MOD);
	ans %= MOD;
	cout << ans << endl;
}
#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	
	
	solve();
}
#pragma endregion //main()


Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(vec) vec.begin(), vec.end()
#define rALL(vec) vec.rbegin(), vec.rend()
using namespace std;
using ll = long long;

int main() {
    int R;
    cin >> R;
    printf("%lf", 2*3.14159265*R);
    return 0;
}

Measured memory_bytes: 3716
#include<bits/stdc++.h>
 
#define EB emplace_back
#define int long long
#define F first
#define S second
#define N 100005
#define ALL(x) x.begin(),x.end()
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
 
 
using namespace std;
bool OK(string s)
{
string t = s;
reverse(ALL(t));
return t == s;
}
 
int32_t main()
{
    IOS;
 
    int tt=1;
    //cin>>tt;
    while(tt--)
    {
       int n; cin>>n;
       int arr[n];
       map<int,int> mp,mpp;
       for (int i = 0; i < n; i++)
	   {
			cin>>arr[i];   
			mp[arr[i]]++;
	   }
	   int ans = 0;
	   for(auto x : mp)
	   {
			ans += (x.S-1)*(x.S)/2;
	   }   
	   for (int i = 0; i < n; i++)
	   {
		   int cnt = mp[arr[i]];
		   cout << ans - cnt + 1 <<endl;
	   }
	   
    }
    return 0;
 
}

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

using namespace std;



int main() {

	int n;
	cin >> n ;

	int h[101];
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	int counter =1;
	for (int i = 1; i < n; i++) {
		bool yn = true;
		for (int j = 0; j <= i - 1; j++) {
			if (h[i] < h[j]) {
				yn = false;
				break;
			}

		}
		if(yn==true){counter++;}

	}
	cout << counter << endl;

}

Measured memory_bytes: 256
def comb(n,k):
  if n == 0:
    return 0
  if n == k:
    return 1
  
  num = 1
  for i in range(n-k+1,n+1):
    num *= i
    
  for i in range(2,k+1):
    num //= i
    

  return num
    
def syou(n,k):
  if k == 0:
    return 1
  
  if len(n) < k:
    return 0
  
  if len(n) == 1:
    return int(n)
  
  l = len(n)
  if n[0] == '0':
    return syou(n[1:l], k)
  
  ans = comb(l-1, k) * (9**k)
  
  top = int(n[0])
  ans += comb(l-1, k-1) * (top-1) * (9**(k-1))
  
  ans += syou(n[1:l], k-1)
  return ans


n = input()
k = int(input())

print(syou(n, k))

Measured memory_bytes: 3188
from collections import deque
INF=3234566667
X=[]
q=deque([i for i in range(1,10)])
D=[[0,1],[0,1,2],[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9]]
while(len(q)>0):
    r=q.popleft()
    X.append(r)
    for m in D[r%10]:
        p=r*10+m
        if p<=INF:
            q.append(p)
X.sort()
K=int(input())
print(X[K-1])


Measured memory_bytes: 48368
#include <stdio.h>
#include <stdbool.h>



int main(void)
{
  bool arr[100][100] = {{false}};
  int w, h, n;
  int x, y, a;
  int ans=0;


  scanf("%d %d %d", &w, &h, &n);


  for (int r=0; r < n; r++){
    scanf("%d %d %d", &x, &y, &a);
     if (a == 1) {
      for (int j=0; j < h; j++) {
        for (int i=0; i < x; i++) {
          arr[j][i] = true;
        }
      }
    } else if (a == 2) {
      for (int j=0; j < h; j++) {
        for (int i=x; i < w; i++) {
          arr[j][i] = true;
        }
      }
    } else if (a == 3) {
      for (int j=0; j < y; j++) {
        for (int i=0; i < w; i++) {
          arr[j][i] = true;
        }
      }
    } else if (a == 4) {
      for (int j=y; j < h; j++) {
        for (int i=0; i < w; i++) {
          arr[j][i] = true;
        }
      }
    }

  }

  for (int j=0; j < h; j++) {
    for (int i=0; i < w; i++) {
      if (arr[j][i] == false) {
        ans++;
      }
    }
  }


  printf("%d\n", ans);


    return 0;
}


Measured memory_bytes: 128
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int d[2005],h[2005],vst[2005],cnt,n,m,s[2005];
struct Edge{
    int to,next,value;
}e[10005];
struct Heap_Node{
    int dis,no;
    bool operator <(const Heap_Node K) const{
        return dis>K.dis;
    }
};
priority_queue<Heap_Node>q;
void Add_Edge(int u,int v,int w){
    e[++cnt].to=v;
    e[cnt].value=w;
    e[cnt].next=h[u];
    h[u]=cnt;
}
void Read_In(){
	int x,y;
    scanf("%d%d%d",&n,&x,&y);
    Add_Edge(x,y,1);
    Add_Edge(y,x,1);
    for(int i=1;i<n;i++){
    	Add_Edge(i,i+1,1);
    	Add_Edge(i+1,i,1);
    }
}
void Dijkstra(int start){
	memset(vst,0,sizeof(vst));
    memset(d,0x3f,sizeof(d));
    d[start]=0;
    q.push((Heap_Node){d[start],start});
    while(!q.empty()){
        Heap_Node u=q.top();
        q.pop();
        if(vst[u.no])continue;
        vst[u.no]=1;
        for(int i=h[u.no];i;i=e[i].next){
            int t=e[i].to,v=e[i].value;
            if(!vst[t]&&d[t]>d[u.no]+v){
                d[t]=d[u.no]+v;
                q.push((Heap_Node){d[t],t});
            }
        }
    }
    for(int i=1;i<=n;i++)s[d[i]]++;
}
int main(){
    Read_In();
    for(int i=1;i<=n;i++)Dijkstra(i);
    for(int i=1;i<n;i++)cout<<s[i]/2<<endl;
    return 0;
}

Measured memory_bytes: 384
# E - ∙ (Bullet)
import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

pow2_mod = [1] + [0] * (N + 10)
for i in range(1, N + 10):
    pow2_mod[i] = pow2_mod[i-1] * 2 % MOD

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        #d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        # いずれもマイナスの場合、傾きはプラスになる
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            #d_T[(B, -A)] += 0
        # 片方がマイナスの場合、必ずAがマイナスになるよう揃える
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow2_mod[s_cnt] - 1 # Sから1匹以上選ぶ組合せ
    tmp += pow2_mod[t_cnt] - 1 # Tから1匹以上選ぶ組合せ
    tmp += 1 # どちらも選ばない組合せ
    ans = (ans * tmp)%MOD

ans -= 1 # 最終的に1匹も選ばない組合せ
ans += zeros # (0, 0)のイワシの数

print(ans%MOD)

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

YES = "Yes"  # type: str
NO = "No"  # type: str

n,m = map(int, input().split())
As = list(map(int, input().split()))

sum_a = sum(As)
judge = sum_a/(4*m)

cnt = 0
for a in As:
    if a >= judge:
        cnt += 1
if cnt >= m:
    print(YES)
else:
    print(NO)

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

set <int> pare, impare;

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

    if (n == 3) {
        cout << "2 5 63\n";
        return 0;
    }
    int nmax(2), spare(0);

    while (pare.size() + impare.size() < n) {
        if (nmax % 2 != 0 && nmax % 3 != 0)
            nmax++;
        if (nmax & 1)
            impare.insert(nmax++);
        else {
            spare += nmax;
            pare.insert(nmax++);
        }
    }

    if (impare.size() % 2 != 0) {
        int x = *pare.rbegin();
        pare.erase(x);
        spare -= x;
        while (nmax % 3 != 0 || nmax % 2 == 0)
            nmax++;
        impare.insert(nmax++);
    }

    if (spare % 3 != 0) {
        int x = *pare.rbegin();
        pare.erase(x);
        spare -= x;
        while (nmax % 2 == 1 || (spare + nmax) % 3 != 0)
            nmax++;
        pare.insert(nmax);
    }

    for (auto i : pare)
        cout << i << ' ';
    for (auto i : impare)
        cout << i << ' ';

    return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define mp make_pair
#define bs binary_search
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define For(i,a,b) for(int i=a; i>b ;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define setprec(x,k) cout << fixed << setprecision(x) << k
#define one(x) __builtin_popcount(x)
#define endl "\n"
#define mod 1000000007

int main()
{
	string s, t;
	cin>>s;
	cin>>t;
	// cout<<s<<" "<<t<<endl;
	ll int ans=INT_MAX, c=0, k=0;
	FOR(i,0,s.length()-t.length()+1)
	{
		c=0;
		k=0;
		FOR(j,i,i+t.length())
		{
			if(t[k]!=s[j])
			{
				c++;
				k++;
			}
			else
				k++;
		}
		ans=min(ans,c);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3564
//For higher stack size use g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 a.cpp -o a.exe in cmd
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define ll long long
    #define ld long double
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define pb push_back
    #define f first
    #define s second
    
    using namespace std;
    int main()
    {
        std::ios::sync_with_stdio(false);
        int T;
        T=1;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            int k,x,i,j;
            cin>>k>>x;
            for(i=x-k+1;i<=k+x-1;++i)
                cout<<i<<" ";
            cout<<endl;
        }
        return 0;
    }


Measured memory_bytes: 256
#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;
typedef unsigned int ui;
const ll MOD = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
#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;
int main() {
	int a, b, h;
	cin >> a >> b >> h;
	cout << (a + b)*h / 2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef set<int> si;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define per(i,a,b) for(int i=(b)-1; i>=(a); --i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int INF = 987654321;
const int MOD = (int)1e9+7;
//const long double PI = (acos(-1));
//const long double EPS = 0.0000000001;

const int MAX_N = 100050;
int n;
ll a[MAX_N];
ll b[MAX_N];

int main(void) {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	//freopen("in.txt", "r", stdin);
	//memset(b, -1, sizeof(b));
	cin >> n;
	ll total = 0;
	rep(i,0,n) {
		cin >> a[i];
		total += a[i];
	}
	b[0] = total;
	for(int i=1; i<n; i=i+2) {
		b[0] -= 2 * a[i];
	}
	rep(i,1,n) {
		b[i] = 2*a[i-1] - b[i-1];
	}
	rep(i,0,n) {
		cout << b[i] << ' ';
	}
	return 0;
}


Measured memory_bytes: 2944
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define INT_MAX 2147483647

using namespace std;

int main(){
	int N;
	int A[100005], dp[100005];
	
	scanf("%d",&N);
	
	for (int i=0;i<N;i++) scanf("%d",A+i);
	for (int i=0;i<N;i++) dp[i] = INT_MAX;
	//memset(dp,INT_MAX,N);
	dp[0]=0;
	
	for (int i=0;i<N;i++){
		if (i+1 < N && dp[i] + abs(A[i] - A[i+1]) < dp[i+1]) dp[i+1] = dp[i] + abs(A[i] - A[i+1]);
		if (i+2 < N && dp[i] + abs(A[i] - A[i+2]) < dp[i+2]) dp[i+2] = dp[i] + abs(A[i] - A[i+2]);
	}
	
	printf("%d\n",dp[N-1]);
	
	return 0;
}


Measured memory_bytes: 896
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Set;


public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();


		Set<Integer> adj[] = new HashSet[n+1];
		for(int i = 1; i<adj.length; i++) {
			adj[i] = new HashSet<Integer>();
		}


		for(int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();

			adj[a].add(b);
			adj[b].add(a);
		}

		int[] dist = new int[n+1];
		dist[0] = 0;
		int[] ans = new int[n+1];

		Set<Integer> endcheck = new HashSet<>();
		endcheck.add(1);
		ArrayDeque<Integer> q = new ArrayDeque<>();
		q.add(1);

		while(!q.isEmpty()) {

			int v1 = q.poll();

			int tdist = dist[v1] + 1;

			Iterator<Integer> adjit = adj[v1].iterator();
			while(adjit.hasNext()) {
				int v2 = adjit.next();
				if(!endcheck.contains(v2)) {
					q.add(v2);
					endcheck.add(v2);

					dist[v2] = tdist;
					ans[v2] = v1;
				}
			}
		}

		System.out.println("Yes");
		for(int i = 2; i < n+1; i++) {
			System.out.println(ans[i]);
		}
	}

}


Measured memory_bytes: 105452
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define PI acos(-1)
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<typename T> using v2 = vector<vector<T>>;
template<typename T> using v3 = vector<vector<vector<T>>>;
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int MOD = 1e9 + 7;
const int INF = 1e9 + 200;
const ll INFLL = 2e18 + 200;

int main() {
    ll N, D;
    cin >> N >> D;
    D *= D;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        ll X, Y;
        cin >> X >> Y;
        if (X * X + Y * Y <= D) ans++;
    }
    cout << ans << endl;
}

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

using namespace std;

int main() {

  int n, a;
  int p, v;

  cin >> n >> a;

  p = n % 500;

  if (p <= a) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
    return(0);
}

Measured memory_bytes: 3628
# Python template 
from collections import defaultdict 
import sys
import math 

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()


n = int(input())
a = get_array()

pre_sum = [0]

for i in range(n-1,-1,-1):
    pre_sum.append(pre_sum[-1]+a[i])

pre_sum = pre_sum[::-1]
mod = 1000000007
ans = 0
for i in range(n):
    ans = (ans+a[i]*pre_sum[i+1])%mod 

print(ans)




Measured memory_bytes: 32196
// E - Active Infants

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

pair<ll, int> A[2000]; // 活発度とindexのペア
ll dp[2001][2001]; // dp[l][r]: 左端にl人、右端にr人移動させたときのうれしさの合計の最大値

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


	for (int i=0; i<N; i++) {
		ll a;
		cin >> a;
		A[i] = make_pair(a, i);
	}

	sort(A, A+N, greater<pair<ll, int>>());

	ll ans = 0;

	dp[0][0] = 0;

	for (int l=0; l<N; l++) {
		for (int r=0; r<N; r++) {
			int i = l + r;
			if (i >= N) continue;

			ll act = A[i].first;
			int loc = A[i].second;

			dp[l+1][r] = max(dp[l+1][r], dp[l][r] + act * abs(l - loc));
			dp[l][r+1] = max(dp[l][r+1], dp[l][r] + act * abs((N-1) - r - loc));

			ans = max(ans, dp[l+1][r]);
			ans = max(ans, dp[l][r+1]);
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 26212