akhauriyash/Code-Regression huggingface dataset:
import sys
from bisect import bisect_left,bisect_right,insort
#input = sys.stdin.readline

def main():
    n=int(input())
    s=list(str(input()))
    p=[[] for _ in range(26)]
    for i,S in enumerate(s):
        p[ord(S)-ord('a')].append(i)
    q=int(input())
    for i in range(q):
        a,b,c=map(str,input().split())
        if a=='1':
            b=int(b)-1
            if s[b]==c:
                continue
            else:
                insl=bisect_left(p[ord(s[b])-ord('a')],b)
                p[ord(s[b])-ord('a')].pop(insl)
                insort(p[ord(c)-ord('a')],b)
                s[b]=c
        else:
            b,c=int(b)-1,int(c)-1
            cnt=0
            for i in range(26):
                insl=bisect_left(p[i],b)
                if insl>=len(p[i]):
                    continue
                elif p[i][insl]<=c:
                    cnt+=1
            print(cnt)

if __name__ == '__main__':
    main()

Measured memory_bytes: 28956
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
      
        int a = sc.nextInt();
        int b = sc.nextInt();
      
        int result = Math.max(Math.max(a+a-1, b+b-1), a+b);
        System.out.println(result);
    }
}


Measured memory_bytes: 23764
#include <iostream>
#include <algorithm>
#include <string>
#include <fstream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;

// #define DEBUG

const ll mod = 1e9 + 7;
ll mypow(ll x, ll y, ll m = mod)
{
    ll ans = 1;
    ll q = x;
    while (y > 0)
    {
        if (y % 2 == 1)
        {
            ans *= q;
            ans %= m;
        }
        q = q * q;
        q %= m;
        y = y / 2;
    }
    return ans % m;
}

ll permulation(ll x, ll y, ll m = mod)
{
    ll ans = 0;
    if (x >= y)
    {

        ans = 1;
        for (ll i = x - y + 1; i <= x; i++)
        {
            ans = (ans * i) % m;
        }
    }
    return ans;
}

ll combination(ll x, ll y, ll m = mod)
{
    ll ans = 0;
    if (y == 0 || y == x)
        ans = 1;
    else
    {
        ans = 1;
        for (ll i = x - y + 1; i <= x; i++)
        {
            ans = (ans * i) % m;
        }
        for (ll i = 1; i <= y; i++)
        {
            ans = (ans * mypow(i, m - 2, m)) % m;
        }
    }
    return ans;
}

ll fractual(ll x, ll m = mod)
{
    if (x == 0)
        return 0;
    else
        return permulation(x, x, m);
}

ll multi_choose(ll x, ll y, ll m = mod)
{
    return combination(x + y - 1, y - 1, m);
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif

    ll n, k;
    cin >> n >> k;
    cout << multi_choose(n, k) << endl;
    return 0;
}

// getline(cin,s);
// a = strtok(s, ",");  ","で分解
// for (int i = 0; i < n; i++)


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

int main() {
  int a,b,W,X,Y,Z;
  cin >> a >> b;
  W = a * b;
  X = W / 2;
  Y = X * 2;
  Z = W - Y;
  if (Z == 0) {
    cout << "Even" << endl;
  }
  if (Z == 1) {
    cout << "Odd" << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a[100],b[100];
  int n;
  int x=0,z=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
  }
  for(int i=0;i<n;i++){
    while(a[i]>z){
      z++;
      x++;
      if(x==b[i]&&a[i]!=z){
	x-=x;
      }
    }
    cout<<x<<endl;
    x-=x;
    z-=z;
  }
  return(0);
}
    
      

Measured memory_bytes: 3108
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#define mod 1000000007
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod

#define N 100010
ll n,m,q;
vector<ll> g[N];
ll col[N];
ll dp[N][12];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
	ll a,b; cin>>a>>b;
	g[a].push_back(b);
	g[b].push_back(a);
    }
    for(int i=1;i<=n;i++)g[i].push_back(i);
    for(int i=1;i<=n;i++)for(int d=0;d<12;d++)dp[i][d]=0;
    col[0]=0;
    cin>>q;
    for(ll i=1;i<=q;i++){
	ll a,b; cin>>a>>b>>col[i];
	chmax(dp[a][b],i);
    }
    for(int d=11;d>0;d--){
	for(int i=1;i<=n;i++)for(auto j:g[i]){
	    chmax(dp[j][d-1],dp[i][d]);
	}
    }
    for(int i=1;i<=n;i++){
	cout<<col[dp[i][0]]<<endl;
    }
}




Measured memory_bytes: 18048
#include <cmath>
#include <cstdio>
using std::abs;
int main(void)
{
	int x=0,y=0,nx,ny,dx,dy;
	int t=0,nt,dt,d,N;
	bool winFlag=true;
	scanf("%d",&N);
	while(N--)
	{
		scanf("%d%d%d",&nt,&nx,&ny);
		dx=abs(nx-x);
		dy=abs(ny-y);
		y=ny;
		x=nx;

		dt=nt-t;
		t=nt;

		if(dx+dy>dt ||(dx+dy)%2 !=dt%2)
		{
			winFlag=false;
		}
	
	}
	if(winFlag)
		printf("Yes\n");
	else
		printf("No\n");


}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  cout<<fixed;
  int a,b,c;
  cin>>a>>b>>c;
  if((a==b&&b!=c)||(b==c && a!=b)||(c==a && a!=b))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
      
    
  return 0;
}


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

using namespace std;

int main() {
	string s,s_in;
	cin >> s_in;
	int size = s_in.size();
	for (int i = 0; i < size; i++) {
		if (s_in[i] == '0') {
			s += '0';
		}else if (s_in[i] == '1') {
			s += '1';
		}else if (s_in[i] == 'B' && s.size() != 0) {
			s.pop_back();
		}
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;



int main(void) {

    map<char,int> m;
    int n;
    cin>>n;
    rep(i,n){
        char c;
        cin>>c;
        m[c]++;
    }
    int ans=(m['P']>0)+(m['W']>0)+(m['G']>0)+(m['Y']>0);
    if(ans==3)fin("Three");
    else fin("Four");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,maxn=0,ans=0,temp;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>temp;
		if(temp>=maxn){
			maxn=temp;
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, n) for(ll i = 1; i <= ll(n); ++i)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); ++i)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); ++i)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll a, b, t;
  cin >> a >> b >> t;
  cout << t/a*b << newl;
  return 0;
}

Measured memory_bytes: 256
N,X = map(int,input().split())
List = list(map(int,input().split()))
abs_List = [abs(List[i] - X) for i in range(N)]

import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

print(gcd(*abs_List))

Measured memory_bytes: 19936
//----->|try=0; while(!success) try++;|<------
//----->|Belief Yourself,Respect Yourself|<----
//----->|Be Proud Of Yourself,You're Doing Your best|<-----
#include<bits/stdc++.h>
using namespace std;
#define uniq(x)  x.erase(unique(x.begin(),x.end()), x.end()) //Unique value find from vector
#define upper(arr,n,fixed) upper_bound(arr,arr+n,fixed)-arr  //Upper value search;
#define lower(arr,n,fixed) upper_bound(arr,arr+n,fixed)-arr  //Lower value search;
#define max3(a,b,c) max(max(a,b),c)//maximum value find three value;
#define min3(a,b,c) min(min(a,b),c)//minimum value find three value;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, n) for(int i = 1; i <= n; ++i)
#define rep1(i,start,n) for(int i=start;i<n;++i)
#define PI acos(-1.0)//PI Calculation
#define LL long long
#define AND(a,b) ((a) & (b))
#define OR(a,b) ((a)|(b))
#define XOR(a,b) ((a) ^ (b))
#define MP make_pair
#define sqr(x) ((x)*(x))
#define sqrt(x) sqrt(1.0*(x))
#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define MX 1000005
#define MOD 1000000007
template<typename T> T POW(T b,T p)          //Pow calculation
{
    T r=1;
    while(p)
    {
        if(p&1)r=(r*b);
        b=(b*b);
        p>>=1;
    }
    return r;
}

template<typename T> T BigMod(T b,T p,T m) //BigMod Calculation
{
    T r=1;
    while(p)
    {
        if(p&1)r=(r*b)%m;
        b=(b*b)%m;
        p>>=1;
    }
    return r;
}

//||--------------------------->||Main_Code_Start_From_Here||<---------------------------------||
int main()
{
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    string s;
    int len;
    while(cin>>s)
    {
        len=s.size();
        if(s[0]==s[len-1]) len++;
        if(len%2) cout<<"First"<<endl;
        else cout<<"Second"<<endl;
    }

}


Measured memory_bytes: 512
#include <stdio.h>
#define N 1000000
void sellSort(int *A,int n);
void insertionSort(int *A,int n, int g);
int cnt;
int m=7;
int main(){
  int i,j,n,A[N];
  scanf("%d",&n);
   
  for(i=0;i<n;i++)
    scanf("%d",&A[i]);
   
   
  sellSort(A,n);
   
  
   
  return 0;
   
}
 
void sellSort(int *A,int n){
  int i,j=0,G[]={1093,364,121,40,13,4,1};
   
  cnt = 0;
  if(n<1093)j++;
  if(n<364)j++;
  if(n<121)j++;
  if(n<40)j++;
  if(n<13)j++;
  if(n<4)j++;
   
  for(i=j;i<m;i++){
     
    insertionSort(A,n,G[i]);
  }
  printf("%d\n",m-j);
   
  for(i=j;i<m;i++){
    if(i<m-1)
      printf("%d ",G[i]);
    else
      printf("%d\n",G[i]);
  }
  printf("%d\n",cnt);
  for(i=0;i<n;i++)printf("%d\n",A[i]);
   
   
}
 
 
void insertionSort(int *A,int n, int g){
  int i,j,v;
   
  for(i=g;i<n;i++){
    v=A[i];
    j=i-g;
    while(j>=0 && A[j]>v){
      A[j+g] = A[j];
      j=j-g;
      cnt++;
       
    }
    A[j+g] = v;
  }
}

Measured memory_bytes: 4504
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

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

  SORT(s);
  int ans = SUM(s);

  if (ans%10 == 0) {
    rep(i,n) {
      if (s[i]%10 != 0) {
        ans -= s[i];
        break;
      }
      if (i == n-1) ans = 0;
    }
  }

  cout << ans << endl;
}

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

int main() {
  int a,b; cin >> a >> b;
  vector<int>v{a+b,a-b,a*b};
  sort(v.begin(),v.end());
  int ans = v[2];
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>

int H, W;
char a[1000][1001];
int dp[1000][1000];
int mod = 1000000007;

int main(){

    scanf("%d %d", &H, &W);
    for(int i = 0; i < H; i++){
        scanf("%s", &a[i]);
    }

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            dp[i][j] = 0;
        }
    }

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){

            if(a[i][j] == '#'){
                continue;
            }

            if(i == 0 && j == 0){
                dp[i][j] = 1;
            }
            else if(i == 0){
                dp[i][j] = dp[i][j - 1];
            }
            else if(j == 0){
                dp[i][j] = dp[i - 1][j];
            }
            else{
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
            }
        }
    }

    printf("%d", dp[H - 1][W - 1]);

    return 0;
}

Measured memory_bytes: 4992
#include <algorithm>
#include <cmath>
#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int main()
{
	string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	int n;
	string str;
	cin >> n >> str;
	int s = alphabet.length();

	for (char& c : str)
	{
		int num = alphabet.find_first_of(c);
		num = (num + n) % alphabet.length();
		c = alphabet.at(num);
	}

	cout << str << endl;
}

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

#define priMAX 1000000

vector<int> sieve_of_eratosthenes(int n) {
	vector<int> primes(n);
	for (int i = 2; i < n; ++i)
		primes[i] = i;
	for (int i = 2; i*i < n; ++i)
	if (primes[i])
		for (int j = i*i; j < n; j+=i)
			primes[j] = 0;
	return primes;
}

int main(){
	vector<int> primes = sieve_of_eratosthenes(priMAX);
	vector<int> all(priMAX);
	int cc = 0;
	for(int i=0; i<priMAX; i++){
		if(primes[i]) cc++;
		all[i] = cc;
	}
	int n;
	while(cin>>n){
		cout<<all[n]<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
int main(void) {
	int h, w, i;
	char row[2][301];

	while (1) {
		scanf("%d %d", &h, &w);
		if (h == 0 && w == 0)
			break;

		for (i = 0; i < w; i++) {
			row[0][i] = "#."[i&1];
			row[1][i] = ".#"[i&1];
		}
		row[0][i] = row[1][i] = '\0';

		for (i = 0; i < h; i++) {
			puts(row[i&1]);
		}
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 592
// Template
#include <bits/stdc++.h>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep3(i, l, r) for (ll i = (ll)(l); i < (ll)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define per(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003LL;
template <typename T> inline bool chmin(T &x, const T &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T &x, const T &y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET {IOSET() {cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

// Main
int main() {
    string s;
    cin >> s;
    
    string a = string(s.begin(), s.begin() + s.size() / 2);
    string b = string(s.end() - s.size() / 2, s.end());
    reverse(all(a));
    
    if (s.size() & 1) {
        char c = s[s.size() / 2];
        rep(i, a.size()) {
            if (a[i] != c || b[i] != c) {
                cout << a.size() + i + 1 << "\n";
                return 0;
            }
        }
        cout << s.size() << "\n";
    } else {
        char c = a[0];
        rep(i, a.size()) {
            if (a[i] != c || b[i] != c) {
                cout << a.size() + i << "\n";
                return 0;
            }
        }
        cout << s.size() << "\n";
    }
}


Measured memory_bytes: 3772
N = int(input())
A = map(int, input().split())
isApproved = True
for a in A:
  if a%2 == 0 and (a%3 != 0 and a%5 != 0):
    isApproved = False
    break
if isApproved:
    print('APPROVED')
else:
    print('DENIED')

Measured memory_bytes: 38384
n = int(input())
a = list(map(int, input().split()))

if a.count(0) > 0:
  print(0)
  exit()
  
ans = a[0]
for i in range(1,n):
  ans *= a[i]
  if ans > 10**18:
    print(-1)
    exit()

print(ans)

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

long long int N, a[55], o, A, B, i;

int main(){
    scanf("%lld", &N);
    for(; i < N; ++i){
        scanf("%lld", a + i);
    }
    sort(a, a + N, greater<long long>());
    //for(i = 0; i < N; ++i)cout << a[i] << " ";
    //cout << endl;
    for(i = 1; i < N; ++i){
        o = (a[i - 1] - a[i]) / (N + 1);
        A += o * i;
        //cout << A << " (" << o << ") ";
        //cout << a[i - 1] - o * N << " : " << a[i] + o * i << endl;
        for(int j = 0; j < i; ++j){
            a[j] -= o * (N + 1);
        }
        //for(int j = 0; j < N; ++j){
        //    cout << a[j] << " ";
        //}
        //cout << endl;
    }
    o = *min_element(a, a + N);
    for(i = 0; i < N; ++i)a[i] -= o;
    B = A;
    B += o;
    //for(i = 0; i < N; ++i)cout << a[i] << " ";
    //cout << endl;
    //cout << B << endl;
    for(i = 0; i < N; ++i){
        a[i] += (B - 1) % N + 1;
    }
    B -= (B - 1) % N + 1;
    while(*max_element(a, a + N) >= N){
        o = max_element(a, a + N) - a;
        //for(i = 0; i < N; ++i)cout << a[i] << " ";
        //cout << endl;
        for(i = 0; i < N; ++i){
            a[i] += (i == o) ? -N : 1;
        }
        ++A;
    }
    //for(i = 0; i < N; ++i)cout << a[i] << " ";
    //cout << endl;
    /*A += (B - N) * N;
    for(i = 0; i < N; ++i){
        a[i] += N;
    }
    while(*max_element(a, a + N) >= N){
        o = max_element(a, a + N) - a;
        for(i = 0; i < N; ++i)cout << a[i] << " ";
        cout << endl;
        for(i = 0; i < N; ++i){
            a[i] += (i == o) ? -N : 1;
        }
        ++A;
    }*/
    cout << A + B * N << endl;//*/
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
using ll =long long int;
ll n;
ll a[101];
int main() {
	
cin>>n;
  		
  for(ll i=0;i<n;i++)
    cin >> a[i];
		ll count=0;
  			
  		for(ll i=0;i<n;i++)
        {
          for(ll j=i+1;j<n;j++)
          {
            for(ll k=j+1;k<n;k++)
            {
              if(a[i]+a[j] > a[k] && a[k]+a[i]>a[j] && a[j]+a[k]>a[i] && a[i]!=a[j] && a[j]!=a[k] && a[i]!=a[k])
                count++;
            }
          }
        }
  
  		cout<<count<<endl;
			return 0;
}

Measured memory_bytes: 3540
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//using ll = long long;
void p(vector<int> A){rep(i,A.size()){cout << A[i] << " ";}cout << "\n";}

int main(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> ab(n);
    rep(i,m){
        int a, b;
        cin >> a >> b;
        ab[a-1].push_back(b);
        ab[b-1].push_back(a);

    }
  		rep(i,n){
        cout << ab[i].size() << "\n";
    }
}

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

int main() {
	int n,aa[500000];
	cin>>n;
	for(int i=0;i<n;i++)cin>>aa[i];
	int mx=0;
	for(int i=0;i<n;i++){
		if(mx>aa[i]){
			if(mx-aa[i]>1){
				cout<<"No";
				return 0;
			}
		}else mx=aa[i];
	}
	cout<<"Yes";
	return 0;
}

Measured memory_bytes: 640
N=int(input())
S=input()

RD={}
GD={}
BD={}
RL=[]
GL=[]
BL=[]
for i in range(N):
    if S[i]=="R":
        RD[i]=1
        RL.append(i)
    elif S[i]=="G":
        GD[i]=1
        GL.append(i)
    else:
        BD[i]=1
        BL.append(i)

#print(RD,GD,BD)
#print(RL,GL,BL)
import bisect
#print(bisect.bisect_left(RL,i))
ans=0
for i in range(1,N-1):
    if S[i]=="R":
        cnt=0
        cnt+=bisect.bisect_left(GL,i)*(len(BL)- bisect.bisect_left(BL,i))
        cnt+=bisect.bisect_left(BL,i)*(len(GL)- bisect.bisect_left(GL,i))
        hiku=0
        for j in range(i):
            if len(GL)==j or GL[j]>i:
                break
            if 2*i-GL[j] in BD:
                hiku+=1
        for j in range(i):
            if len(BL)==j or BL[j]>i:
                break
            if 2*i-BL[j] in GD:
                hiku+=1
        ans+=(cnt-hiku)
    elif S[i]=="G":
        cnt=0
        cnt+=bisect.bisect_left(RL,i)*(len(BL)-bisect.bisect_left(BL,i))
        #print(bisect.bisect_left(RL,i),bisect.bisect_left(BL,i))
        cnt+=bisect.bisect_left(BL,i)*(len(RL)-bisect.bisect_left(RL,i))
        #print(cnt)
        hiku=0
        for j in range(i):
            if len(RL)==j or RL[j]>i:
                break
            if 2*i-RL[j] in BD:
                hiku+=1
        for j in range(i):
            if len(BL)==j or BL[j]>i:
                break
            if 2*i-BL[j] in RD:
                hiku+=1
        ans+=(cnt-hiku)
    else:
        cnt=0
        cnt+=bisect.bisect_left(RL,i)*(len(GL)- bisect.bisect_left(GL,i))
        cnt+=bisect.bisect_left(GL,i)*(len(RL)- bisect.bisect_left(RL,i))
        hiku=0
        for j in range(i):
            if len(RL)==j or RL[j]>i:
                break
            if 2*i-RL[j] in GD:
                hiku+=1
        for j in range(i):
            if len(GL)==j or GL[j]>i:
                break
            if 2*i-GL[j] in RD:
                hiku+=1
        ans+=(cnt-hiku)
    #print(ans)
print(ans)

Measured memory_bytes: 71296
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define pi acosl(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
#define EPS 1e-4
#define arg ARG
#define cpdd const pdd
#define rank Rank
#define MAXN 205
//#define N 262144
#define ULL unsigned long long
#define ll long long
int cnt[100005];
int main(){
    int n;
    scanf("%d",&n);
    LL sum=0;
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        sum+=x;
        cnt[x]++;
    }
    int q;
    scanf("%d",&q);
    while(q--){
        int b,c;
        scanf("%d %d",&b,&c);
        sum-=b*1ll*cnt[b];
        sum+=c*1ll*cnt[b];
        cnt[c]+=cnt[b];
        cnt[b]=0;
            printf("%lld\n",sum);
    }

}

Measured memory_bytes: 4212
#include <stdio.h>
#include <stdlib.h>

typedef struct node{
  int p;
  int right;
  int left;
}Node;

Node *node,tmp;

int main(){
  
  int n,i,j,l,c,k,id,tmpP,depth,r;
  
  //in
  scanf("%d",&n);
  
  node = malloc(sizeof(Node)*n);

  //initialize
  for(i=0;i<n;i++){
    node[i].p = -1;
    node[i].right = -1;
    node[i].left = -1;
  }
  
  for(i=0;i<n;i++){
    scanf("%d%d",&id,&k);
    
    for(j=0;j<k;j++){
      scanf("%d",&c);
      if(j==0) node[id].left = c;
      else node[r].right = c;
      node[c].p = id;
      r=c;
    }
  }
  
  //depthSearch & typeJudge
  for(i=0;i<n;i++){
    depth = 0;
    tmpP = node[i].p;
    
    while(tmpP != -1){
      tmpP = node[tmpP].p;
      depth++;
    }
    
    if(node[i].p == -1){
      printf("node %d: parent = %d, depth = %d, root, [",
	   i,node[i].p,depth);
    }
    else if(node[i].left == -1) printf("node %d: parent = %d, depth = %d, leaf, [",
	   i,node[i].p,depth);
    else printf("node %d: parent = %d, depth = %d, internal node, [",
	   i,node[i].p,depth);
    
    tmpP = node[i].left;
    if(tmpP != -1) printf("%d",tmpP);
    
    while(tmpP != -1){
      tmpP = node[tmpP].right;
      if(tmpP != -1) printf(", %d",tmpP);
    }
    printf("]\n");
  }

  return 0;
}

Measured memory_bytes: 1784
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
priority_queue<int>q;
long long ans;
int main()
{
 int n,m;
 cin>>n>>m;
 for(int i=1;i<=n;i++)
 {
  int x;
  cin>>x;
  ans+=x;
  q.push(x);
 }
 while(m--)
 {
  int x=q.top();
  q.pop();
  ans=ans-x+x/2;
  q.push(x/2);
 }
 cout<<ans<<endl;
 return 0;
}

Measured memory_bytes: 892
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
      	String s = sc.next();
      	int[] charCnt = new int[26];
      	
      	for (char c: s.toCharArray()) {
        	if (charCnt[c - 'a'] != 0) {
            	System.out.println("no");
              	System.exit(0);
            }
          	charCnt[c - 'a']++;
        }
      	System.out.println("yes");
    }
}


Measured memory_bytes: 21844
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String ans = "";
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(c=='B'){
                int l = ans.length();
                if(l!=0){
                    ans=ans.substring(0,l-1);
                }
            }else{
                ans+=String.valueOf(c);
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 9680
#include <iostream>
#include <cmath>
#include <numeric>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <algorithm>
using namespace std;

using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define REP1(i, n) for (ll i = 1; i <= n; i++)
#define REPR(i, n) for (ll i = n - 1; i >= 0; i--)
#define REPR1(i, n) for (ll i = n; i >= 1; i--)
#define FOR(i, m, n) for (ll i = m; i <= n; i++)

int gcd(int a, int b) { if (a < b) { a ^= b; b ^= a; a ^= b; } return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }

ll H[200010];

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

    REP1(i, N) cin >> H[i];

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

    sort(&H[1], &H[N + 1]);

    ll h = 0;

    FOR(i, 1, N - K) h += H[i];

    cout << h << endl;

    return 0;
}


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

int main() {
  int64_t N, A, B;
  cin >> N >> A >> B;
  
  long long ans;
  if((B-A)%2==0)ans = (B-A)/2;
  else ans = (B-A + min(A-1, N-B)*2 +1)/2;
  
  cout << ans << endl;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef pair<l_l,ll> lll;
typedef vector<string> vs;
const ll dx[4]={1,-1,0,0};
const ll dy[4]={0,0,1,-1};
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int mod = 1000000007;
struct mint {
ll x;
mint(ll x=0):x((x%mod+mod)%mod){}
mint operator-() const { return mint(-x);}
mint& operator+=(const mint a) {
if ((x += a.x) >= mod) x -= mod;
return *this;
}
mint& operator-=(const mint a) {
if ((x += mod-a.x) >= mod) x -= mod;
return *this;
}
mint& operator*=(const mint a) {
(x *= a.x) %= mod;
return *this;
}
mint operator+(const mint a) const {
mint res(*this);
return res+=a;
}
mint operator-(const mint a) const {
mint res(*this);
return res-=a;
}
mint operator*(const mint a) const {
mint res(*this);
return res*=a;
}
mint pow(ll t) const {
if (!t) return 1;
mint a = pow(t>>1);
a *= a;
if (t&1) a *= *this;
return a;
}
mint inv() const {
return pow(mod-2);
}
mint& operator/=(const mint a) {
return (*this) *= a.inv();
}
mint operator/(const mint a) const {
mint res(*this);
return res/=a;
}
};
ll n,m;
vl g[110000];
ll dp1[110000],dp2[110000];
ll ans[110000];
void dfs(ll nw,ll lt=-1){
    ll res=1;
    for(auto nt:g[nw]){
        if(nt==lt)continue;
        dfs(nt,nw);
        res=res*dp1[nt];
        res%=m;
    }
    dp1[nw]=res+1;
    dp1[nw]%=m;
}
void dfs2(ll nw,ll lt=-1){
    if(lt==-1)dp2[nw]=1;
    vector<ll> lcnt(sz(g[nw]),1);
    vector<ll> rcnt(sz(g[nw]),1);
    rep(i,sz(g[nw])){
        ll nt=g[nw][i];
        if(i>=1)lcnt[i]=lcnt[i-1];
        if(nt==lt)continue;
        lcnt[i]*=dp1[nt];
        lcnt[i]%=m;
    }
    for(int i=sz(g[nw])-1;i>=0;i--){
        ll nt=g[nw][i];
        if(i<sz(g[nw])-1)rcnt[i]=rcnt[i+1];
        if(nt==lt)continue;
        rcnt[i]*=dp1[nt];
        rcnt[i]%=m;
    }
    rep(i,sz(g[nw])){
        ll nt=g[nw][i];
        if(nt==lt)continue;
        ll res=1;
        if(i!=0) res*=lcnt[i-1],res%=m;
        if(i!=sz(g[nw])-1) res*=rcnt[i+1],res%=m;
        dp2[nt]=(res*dp2[nw]+1)%m;
        dfs2(nt,nw);
    }
}
void dfs3(ll nw,ll lt=-1){
    ans[nw]=dp2[nw];
    for(auto nt:g[nw]){
        if(nt==lt)continue;
        ans[nw]*=dp1[nt];
        ans[nw]%=m;
        dfs3(nt,nw);
    }
}
int main(){
    cin>>n>>m;
    rep(i,n-1){
        ll u,v;cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1);
    dfs2(1);
    dfs3(1);
    rrep(i,n)cout<<ans[i]<<endl;
    return 0;
}

Measured memory_bytes: 21768
H, W, K = (int(i) for i in input().split())  

d = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
  R = input()
  for j, X in enumerate(R):
    if X == '#':
      d[i][j] = 1

ans = 0
for maskW in range(2 ** W):
  for maskH in range(2 ** H):
    tmp = 0
    for i in range(H):  # このループが一番のポイント
      for j in range(W): 
        if ((maskW >> j) & 1) and ((maskH >> i) & 1):
          if d[i][j] == 1:
            tmp += 1
            
    if tmp == K:
      #print(maskW, maskH)
      ans += 1

print(ans)

Measured memory_bytes: 9204
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a) for(int i = 0; i < (a); i++)
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const long long LINF = 1e18;
const long long MOD = 1e9 + 7;

signed main(){
    int n;
    cin >> n;
    int a[n];
    REP(i,n){
        cin >> a[i];
    }
    int ans = 0, pre = a[0];
    REP(i,n - 1){
        if(a[i + 1] > pre) ans++;
        pre = a[i + 1];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3488
import java.util.*;
import java.lang.Math;

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

    public static void main(String[] args){
        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        long[] x = new long[n];
        long ans = 0L;
        for(int i = 0; i < n; ++i){
            x[i] = sc.nextLong();

            if(i == 0) continue;

            ans += Math.min(a * (x[i] - x[i - 1]), b);
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 48096
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
val = 1000
prv = a[0]
for i in range(1,n):
    c = a[i]
    if c>prv:
        val = val + (val//prv)*c - (val//prv)*prv
    prv = c
#     print(val)
print(val)

Measured memory_bytes: 61788
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
//#include "h.h"
using namespace std;

#define ll long long
#define pint pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(VECTOR) (VECTOR).begin(),(VECTOR).end()

ll calc(ll X){
	if(X < 0)return 0;
	switch(X%4){
		case 0:
		return X;
		case 1:
		return (X - 1) ^ X;
		case 2:
		return ((X - 2) ^ (X - 1)) ^ X;
		case 3:
		return 0;
	}
}

int main(){

	ll A, B;
	cin >> A >> B;
	//cout << calc(B) << endl;
	//cout << calc(A) << endl;
	cout << (calc(B) ^ calc(A - 1)) << endl;

	return 0;
}

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

using namespace std;

int main()
{
	long n, t[10000], ct, st;
	
	while (scanf("%ld", &n), n != 0){
		for (int i = 0; i < n; i++){
			scanf("%ld", &t[i]);
		}
		
		sort (t, t + n);
		
		ct = st = 0;
		for (int i = 0; i < n - 1; i++){
			ct += t[i];
			st += ct;
		}
		
		printf("%ld\n", st);
	}
	return (0);
}

Measured memory_bytes: 1120
import heapq

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

h = []
s = set()
ia = ib = ic = 0

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


def f(ia, ib, ic):
    return (-(A[ia] + B[ib] + C[ic]), ia, ib, ic)


item = f(ia, ib, ic)
heapq.heappush(h, item)
s.add(item)
ans = []

for i in range(K):
    # print("----")
    # print(h)
    if len(h) == 0:
        break
    t = heapq.heappop(h)
    ans.append(t)
    if t[1] + 1 < len(A):
        item = f(t[1] + 1, t[2], t[3])
        if not item in s:
            heapq.heappush(h, item)
        s.add(item)
    if t[2] + 1 < len(B):
        item = f(t[1], t[2] + 1, t[3])
        if not item in s:
            heapq.heappush(h, item)
        s.add(item)

    if t[3] + 1 < len(C):
        item = f(t[1], t[2], t[3] + 1)
        if not item in s:
            heapq.heappush(h, item)
        s.add(item)

# print("==================")
# print(A)
# print(B)
# print(C)
# print(ans)
for i in range(K):
    print(-ans[i][0])


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

#define rep(i, n) for(int i=0; i < n; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()

#define pb(x) push_back(x)

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

ll mod=1000000007;

const ll INF = 1LL << 60;

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

int n;

P f(int x){
  int a=x%10;
  int b=0;
  while(x){
    b=x;
    x/=10;
  }
  return P(a,b);
}

int main() {
  cin >> n;
  map<P,int> freq;
  reps(i,n){
    P p= f(i);
    freq[p]++;
  }
  ll ans=0;
  reps(i,n){
    P p= f(i);
    P q(p.second,p.first);
    ans +=freq[q];
  }
  cout << ans;
}

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

int N, K;
vector<ll> H;

void input()
{
    cin >> N >> K;

    H.reserve(200005);

    for (int i = 0; i < N; i++) {
        int hi;
        cin >> hi;
        H.push_back(hi);
    }
}

int main()
{
    input();

    sort(H.begin(), H.end());

    ll ans = 0;
    for (int i = 0; i < N - K; i++) {
        ans += H[i];
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;

int gcd(int a, int b) {//最大公約数
	if (b == 0)return a;
	return gcd(b, a%b);
}
int lcm(int a, int b) {//最小公倍数
	int g = gcd(a, b);
	return a / g * b;
}
int modpow(int a, int p) {
	if (p == 0) return 1;
	if (p % 2 == 0) {

		int halfP = p / 2;
		int half = modpow(a, halfP);

		return half * half % mod;
	}
	else {

		return a * modpow(a, p - 1) % mod;
	}
}
VP P;

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

	int N; cin >> N;
	P.resize(N);
	int zero = 0;


	map<pii, pii>mp;

	REP(i, N) {
		cin >> P[i].first >> P[i].second;
		if (P[i].first == 0 && P[i].second == 0) {
			zero++;
			continue;
		}
		int g = gcd(P[i].first, P[i].second);
		P[i].first /= g;
		P[i].second /= g;
		if (P[i].second < 0) {
			P[i].first *= -1;
			P[i].second *= -1;
		}
		if (P[i].second == 0 && P[i].first < 0) P[i].first *= -1;
		bool rot = false;
		if (P[i].first <= 0) rot = 1;
		
		if (rot) {
			int tmp = P[i].first;
			P[i].first = P[i].second;
			P[i].second = -tmp;
		}
		if (rot)mp[pii(P[i].first, P[i].second)].first++;
		else mp[pii(P[i].first, P[i].second)].second++;
	}

	int ans = 1;
	fore(p, mp) {
		int s = p.second.first;
		int t = p.second.second;

		int now = 1;
		now += modpow(2,s) - 1;
		now += modpow(2,t) - 1;
		now = (now + mod) % mod;
		ans *= now;
		ans %= mod;

	}


	ans += zero;

	cout << (ans - 1 + mod) % mod << endl;
	
	return 0;
}



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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
 public:
  int n;
  vector<string> a;
  vector<vector<int>> cnt, sum;
  vector<int> c2, c5;
  const int geta = 9;
  Solver(LL n) : n(n), a(n), cnt(100, vector<int>(100)), sum(100, vector<int>(100)), c2(n), c5(n){};

  void solve() {
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
      int d = 0;
      int tmp = a[i].find('.');
      if (tmp != -1) {
        d = -(a[i].length() - tmp - 1);
      }
      LL b = 0;
      for (int j = 0; j < a[i].length(); ++j) {
        if (a[i][j] != '.') {
          b *= 10;
          b += a[i][j] - '0';
        }
      }
      int cnt2 = d, cnt5 = d;
      while (b > 0 && b % 2 == 0) {
        cnt2++;
        b /= 2;
      }
      while (b > 0 && b % 5 == 0) {
        cnt5++;
        b /= 5;
      }
      DBG(a[i], cnt2, cnt5)
      cnt[cnt2 + geta][cnt5 + geta]++;
      c2[i] = cnt2;
      c5[i] = cnt5;
    }
    sum = cnt;
    for (int i = (int)sum.size() - 1; i >= 0; --i) {
      for (int j = (int)sum[i].size() - 2; j >= 0; --j) {
        sum[i][j] += sum[i][j + 1];
      }
    }

    for (int i = (int)sum.size() - 2; i >= 0; --i) {
      for (int j = (int)sum[i].size() - 1; j >= 0; --j) {
        sum[i][j] += sum[i + 1][j];
      }
    }

    LL ans = 0, same = 0;
    for (int i = 0; i < n; ++i) {
      DBG(sum[-c2[i] + geta][-c5[i] + geta])
      if (c2[i] >= 0 && c5[i] >= 0) same++;
      ans += sum[max(0,-c2[i] + geta)][max(0,-c5[i] + geta)];
    }

    cout << (ans - same) / 2 << endl;
  }
};  // namespace Problem

}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);
  long long n = 0;
  std::cin >> n;

  Problem::Solver sol(n);
  sol.solve();
  return 0;
}


Measured memory_bytes: 11068
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    int ans = 1;
    int m = a[0];
    REP(i, 1, n) {
        if(m <= a[i]) ++ans;
        m = max(m, a[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)  
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){

  int n,k;
  cin>>n>>k;
  int x[n];
  REP(i,n){
    cin>>x[i];
  }
  int ans = INF;

  REP(i,n-k+1){
    int a,b;
    a = x[i];
    b = x[i+k-1];
    ans = min(ans,b-a+min(abs(b),abs(a)));
  }

  cout<<ans<<endl;


  return 0;
}

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

using namespace std;

int main( ) {
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t,n;
	t = 1;
	while(t--) {
	 cin >> n;
	 cout << (n * 800) - 200 * (n / 15) << endl;
	}
	return 0;
}



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

using namespace std;

int main()	{
  long long n, k;
  cin >> n >> k;
  long long a[n];
  for (int i = 0; i < n; i++)	{
    cin >> a[i];
  }
  sort(a, a + n, greater<int>());
  long long length = 0;
  for (int i = 0; i < k; i++)	{
    length += a[i];
  }
  cout << length << endl;
  return 0;
}

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

int A[55];
bool boleh[55];
int B[55];
int C[55];
int indx[55];
long long ncr[55][55];

long long ncrUpTo[55][55];

int cnt2[(1<<18)+5];
int s[55];

int main(){
    int N, K, S, T;
    scanf("%d%d%d%d", &N, &K, &S, &T);

    if( ((S&T) == S) && ((S|T) == T) ){
    }else{
        printf("0");
        return 0;
    }

    memset(ncr, 0, sizeof(ncr));
    ncr[0][0] = 1;
    for(int i = 1; i <= N; i ++){
        ncr[i][0] = 1;
        for(int j = 1; j <= i; j ++){
            ncr[i][j] = ncr[i-1][j] + ncr[i-1][j-1];
        }
    }

    ncrUpTo[0][0] = 0;
    for(int i = 1; i <= N; i ++){
        ncrUpTo[i][0] = 0;
        for(int j = 1; j <= N; j ++){
            ncrUpTo[i][j] = ncrUpTo[i][j-1] + ncr[i][j];
        }
    }

    for(int i = 0; i < N; i ++){
        scanf("%d", &A[i]);
        boleh[i] = true;
        //printf("A[%d]=%d\n", i, A[i]);
    }

    int L = 0;
    for(int i = 0; i < 20; i ++){
        if( (S&(1<<i)) == (T&(1<<i)) ){
            for(int j = 0; j < N; j ++){
                if( (S&(1<<i)) != (A[j]&(1<<i)) ){
                    boleh[j] = false;
                    //printf("boleh[%d]=false\n", j);
                }
            }
        }else{
            indx[L ++] = i;
        }
    }

    for(int i = 0; i < L; i ++){
        for(int j = 0; j < N; j ++){
            if(A[j]&(1<<indx[i])){
                B[j] |= (1<<i);
            }
        }
    }

    int M = 0;
    for(int i = 0; i < N; i ++){
        if(boleh[i]){
            C[M ++] = B[i];
        }
    }

    for(int i = 0; i < M; i ++){
        //printf("C[%d]=%d\n", i, C[i]);
    }

    memset(cnt2, 0, sizeof(cnt2));
    long long ans = 0;
    for(int U = 0; U < (1<<L); U ++){
        long long f = 0;

        int sizeS = 0;
        for(int i = 0; i < M; i ++){
            if(!cnt2[U&C[i]]){s[sizeS++] = (U&C[i]);}
            cnt2[U&C[i]] ++;
        }

        for(int k = 0; k < sizeS; k ++){
            int j = s[k];
            int cnt = cnt2[j];
            f += ncrUpTo[cnt][K];
            cnt2[j] = 0;
        }

        int temp = __builtin_popcount(U);
        if(temp&1){
            ans -= f;
        }else{
            ans += f;
        }
    }

    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 4832
S = list(input())
T = list(input())

ans = float("inf")
for i in range(len(S) - len(T) + 1):
    mismatch = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            mismatch += 1
    
    ans = min(ans, mismatch)

print(ans)

Measured memory_bytes: 9104
n = int(input())
word = []
cnt = None
for i in range(n):
    w = input()
    if w in word:
        print("No")
        exit()
    word.append(w)
cnt = word[0]
for i in range(1,n):
    if cnt[-1] != word[i][0]:
        print("No")
        exit()
    cnt = word[i]
print("Yes")



Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define li long int
#define lli long long int
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define fast std::ios_base::sync_with_stdio(false)
#define mod 1000000007
#define pi 3.14159265
lli power(lli a,lli b)
{
    if(b==0)
        return 1;
    lli p=power(a,b/2);
    if(b%2==0)
        return p*p;
    else
        return a*p*p;
}
li gcd(li a,li b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
int main()
{
    fast;
    lli n,i,ans=0;
    cin>>n;
    lli a[n];
    fr(i,n)
    {
    	cin>>a[i];
    }
    lli j;
    fr(i,n-1)
    {
    	for(j=i+1;j<n;j++)
    	{
    		ans+=a[i]*a[j];
    	}
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 1e9+7;
 
int main() {
	int n;
	string s;
	cin >> n >> s;
	int b = 0, w = 0;
	rep(i,n) {
		if (s[i] == '.') w++; 
	}
	int ans = w;

	rep(i,n) {
		if (s[i] == '#') b++;
		else w--;
		ans = min(ans, b+w);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3724