akhauriyash/Code-Regression huggingface dataset:
#include"bits/stdc++.h"
using namespace std;

int gcd(int x, int y){
    if (y==0) return x;
    return gcd(y,x%y);
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> tmp(n);
    vector<int> tmp2(n);
    int ans = 0;
    for (int i = 0; i<n; i++){
        cin >> a[i];
    }
    tmp[0] = a[0];
    tmp2[n-1] = a[n-1];
    for (int i=1; i<n; i++){
        tmp[i] = gcd(tmp[i-1],a[i]);
        tmp2[n-i-1] = gcd(tmp2[n-i],a[n-i-1]);
    }
    for (int i=0; i<n-2; i++){
        ans=max(ans,gcd(tmp[i],tmp2[i+2]));
    }
    ans=max(ans,tmp2[1]);
    ans=max(ans,tmp[n-2]);
    cout << ans << endl;
}



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


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


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

using namespace std;

#define INF 1000000007
#define LINF 1000000000000000007

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


int n, a[101010];
int d[101010];

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	
	for(int i = 0; i <= n; i++) d[i] = -1;
	
	int cnt = 1;
	for(int i = 0; i < n; i++){
		if(i == 0){
			d[n - cnt] = a[i];
			continue;
		}
		if(*(lower_bound(d, d+n, a[i]) - 1) == -1){
			cnt++;
			d[n - cnt] = a[i];
		}
		else{
			*(lower_bound(d, d+n, a[i]) - 1) = a[i];
		}
	}
	
	cout << cnt << endl;
	
	
	
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n];
        for (int i = 0 ; i < n ; i++) {
            d[i] = sc.nextInt();
        }
        int sum = 0;
        for (int i = 0 ; i < n ; i++) {
            for (int j = i + 1 ; j < n ; j++) {
                sum += d[i] * d[j];
            }
        }

        System.out.println(sum);
    }

}

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

int main(){
    int N,M;
    bool flag=true;

    cin >> N >> M;

    int s[M],c[M],num[N]={};

    if(N==1&&M==0){
        num[0]==0;
    }
    else{
        num[0]=1;
    }

    for (int i=0; i<M; i++){
        cin >> s[i] >> c[i];
    }

    for(int i=0; i<M-1; i++){
        for (int k=i+1; k<M; k++){
            if(s[i]==s[k]&&c[i]!=c[k]){//同じ桁で違う数
                cout << -1;
                flag = false;
                break;
            }
            
        }
        if(flag==false){
            break;
        }
    }

    if(flag==true){
        for(int i=0; i<M; i++){
            if((s[i]==1&&c[i]==0)&&(N!=1)){
                cout << -1;
                flag=false;
                break;
            }
        }
    }


    if(flag==true){
        for(int i=0; i<M;i++){
            num[s[i]-1]=c[i];
        }
        for(int i=0; i<N; i++){
            cout << num[i];
        }

    }



    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#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)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  string s;
  cin >> s;
  rep(i,sz(s)){
    cout<<s[i];
    if(i==3)cout<<" ";
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 256
N, M, K = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

tmp = 0

flag = True
for i in range(N):
    if tmp + A[i] <= K:
        tmp += A[i]
    else:
        flag = False
        break

left = K - tmp #残りの使える時間

total = i
if flag:
    i += 1
    total += 1

ans = 0
flag = True
for j in range(M):
    if B[j] <= left:
        total += 1
        left -= B[j]
    else:
        flag = False
        break
if flag:
    print (total)
    exit()

ans = total
while i >= 1:
    total -= 1
    left += A[i - 1]
    i -= 1
    while j < M:
        if B[j] <= left:
            total += 1
            left -= B[j]
            j += 1
        else:
            break
    ans = max(ans, total)

print (ans)



Measured memory_bytes: 111136
#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<algorithm>
using namespace std;
long long num[100005];
int main(){
	long long i,n;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
		scanf("%lld",&num[i]);
	long long ans=1,zero=0;
	for(i=1;i<=n;i++)
		if(!num[i])
			zero++;
	if(zero)
		puts("0");
	else{
		for(i=1;i<=n;i++){
			if((double)ans>(double)1000000000000000000/num[i]){
				puts("-1");
				return 0;
			}
			ans*=num[i];
		}
		if(ans<=1000000000000000000)
			printf("%lld\n",ans);
		else
			puts("-1");
	}
}


Measured memory_bytes: 2440
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LB lower_bound
#define UB upper_bound

using namespace std;

typedef long long ll;
typedef long double DB;
typedef pair <int , int> pii;

const int N = 100100;
int p[N] , x[N] , y[N] , c;
bool mark[N];
vector <int> adj[N] , vc[N];

void DFS(int v){
	
	mark[v] = 1;
	vc[v].PB(c) , vc[p[v]].PB(c);
	for(int u : adj[v])
	   if(!mark[u])
		  DFS(u);
	
	return;
}

int main(){

	ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);

	int n , m , ans(0);
	cin >> n >> m;
	
	for(int i = 0 ; i < n ; i++){
	   cin >> p[i];
	   p[i]--;
	}
	
	for(int i = 0 ; i < m ; i++){
	   cin >> x[i] >> y[i];
	   adj[--x[i]].PB(--y[i]);
	   adj[y[i]].PB(x[i]);
	}

	for(int i = 0 ; i < n ; i++)
	   if(!mark[i])
		  DFS(i) , c++;
	
	for(int i = 0 ; i < n ; i++)
	   if(vc[i][0] == vc[i][1])
		  ans++;

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

Measured memory_bytes: 14464
#include <iostream>
//#include<cstring>
//#include <iomanip>

using namespace std;

long long combination(long long a)
{
  long long ans;
  ans=a*(a-1)/2;
  return ans;
}

int main()
{
  long long N,i,j;
  long long all,count,ans,memory;
  cin>>N;
  long long A[N];
  long long B[N]={};
 
  //配列に格納，その数字を覚えてBに数を入力
  for(i=0;i<N;i++)
  {
    cin>>A[i];
    memory=A[i];
    B[memory-1]++;
  }

  all=0;
  for(i=0;i<N;i++)
  {
    count=combination(B[i]);
    all+=count;
  }
  //cout<<all<<"\n\n";//引かない場合
  
  for(i=0;i<N;i++)
  {
    count=A[i];
    ans=combination(B[count-1]);
    //cout<<ans-1<<" ";
    cout<<all+1-B[count-1]<<"\n";
  }   
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    string S, T;
    cin >> S >> T;
    ll N = S.size();
    ll M = T.size();
    vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 0));
    rep(i, N) {
        rep(j, M) {
            if (S[i] == T[j]) {
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
            } else {
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }
    string ans = "";
    int s = N - 1;
    int t = M - 1;
    while ((s >= 0 && t >= 0) && ans.size() < dp[N][M]) {
        if (S[s] == T[t]) {
            ans += S[s];
            s--;
            t--;
        } else {
            if (s > 0 && t > 0) {
                if (dp[s+1][t] > dp[s][t+1]) {
                    t--;
                } else {
                    s--;
                }
            } else {
                if (s == 0) {
                    t--;
                } else {
                    s--;
                }
            }
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 73664
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using p = pair<int,int>;

int main() {
  int N;
  cin >> N;
  
  vector<int> A(1000000);
  ll sum = 0;
  rep (i, N)
  {
    int tmp;
    cin >> tmp;
    A.at(tmp)++;
    sum += tmp;
  }
  
  int Q;
  cin >> Q;
  vector<vector<int>> bc(Q, vector<int>(2));
  rep(i, Q)
  {
    cin >> bc.at(i).at(0) >> bc.at(i).at(1);
  }
  
  rep(i, Q)
  {
    sum += (bc.at(i).at(1) - bc.at(i).at(0)) * A.at(bc.at(i).at(0));
    cout << sum << endl;
    A.at(bc.at(i).at(1)) += A.at(bc.at(i).at(0));
    A.at(bc.at(i).at(0)) = 0;
  }
}

Measured memory_bytes: 12768
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    char str[20];scanf("%s",str);
    int cnt=0;
    for(int i=0;i<strlen(str);i++) cnt+=str[i]=='o';
    if(cnt+15-strlen(str)>=8) printf("YES\n");
    else printf("NO\n");
    return 0;
}


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

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

  int ans=(100*n+107)/108;
  if (n%27==26||n%27==13) cout<<":("<<endl;
  else cout<<ans<<endl;
}


Measured memory_bytes: 256
(princ (loop :for x :from 0 :upto (read) :with b := (read) :with c := (read)
             :with k := (read)
             :sum(loop :for y :from 0 :upto b
                       :sum(loop :for z :from 0 :upto c
                                 :count(= k (+ (* x 500) (* y 100) (* z 50)))))))

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() { 
    string w;
    map<char, int> mp;
    cin >> w;

    rep(i, w.length()) {
        if (mp[w[i]] == 0) {
            mp[w[i]] = 1;
        } else {
            mp[w[i]] += 1;
        }
    }

    for (const auto& [key, value] : mp) {
        if (value % 2 != 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl; 

    return 0;
}


Measured memory_bytes: 3596
(* O(1) *)
let solve a b = max (a + b) ((max a b) * 2 - 1)

let read_ints () = read_line () |> Str.split (Str.regexp " ") |> List.map int_of_string

let _ =
  match read_ints () with
  | [a; b] -> solve a b |> string_of_int |> print_endline
  | _ -> ()

Measured memory_bytes: 384
n, x = list(map(int, input().split()))
numlist = []
for i in range(n):
  numlist.append(int(input()))

numlist.sort()
donuts_count = n
while x - sum(numlist) - numlist[0] >= 0:
  donuts_count += 1
  x -= numlist[0]

print(donuts_count)


Measured memory_bytes: 3060
#include <stdio.h>

long long int max(long long int a,long long int b){
	if(a>b) return a;
	else return b;
}

int main(void) {
	// your code goes here
	int N,W;
	scanf("%d%d",&N,&W);
	long long int w[N],v[N];
	for(int i=0;i<N;i++){
		scanf("%lld%lld",&w[i],&v[i]);
	}
	long long int dp[N+1][W+1];
	
	for(int i=0;i<=W;i++) dp[0][i] = 0;
	
	for(int i=0;i<N;i++){
		for(int j=0;j<=W;j++){
			if(j<w[i]) dp[i+1][j] = dp[i][j];
			else dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i]);
		}
	}
	printf("%lld",dp[N][W]);
	return 0;
}

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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const int mod = 100000007;
int h,w,pow3[13];
int dp[11*11][180000];
char field[12][12];

#define get(bit,x) ((bit)/pow3[(x)]%3)
#define set(bit,x,value) ((bit)-(((bit)/pow3[x]%3)*pow3[x])+(value*pow3[x]))
#define fix(bit,width) ((bit)*3%pow3[width])

void compute(){
  bool starter = true;  
  rep(y,h){
    rep(x,w){
      if( starter && field[y][x] == '.' ) continue;
      if( starter ) { starter = false; ++dp[x+y*w][0]; }

      bool update = false;
      rep(bitmask3,pow3[w+1]){
	if( dp[x+y*w][bitmask3] == 0 ) continue;
	update = true;
	int left = get(bitmask3,x);
	int top  = get(bitmask3,x+1);
	if( field[y][x] == '.' ) {
	  if( left && top ) continue;
	  if( left && x == w-1 ) continue;
	  if( top && y == h-1 ) continue;
	  int nbitmask = bitmask3;
	  nbitmask = set(nbitmask,x,top);
	  nbitmask = set(nbitmask,x+1,left);
	  if( x == w-1 ) nbitmask = fix(nbitmask,w+1);
	  ( dp[x+y*w+1][nbitmask] += dp[x+y*w][bitmask3] ) %= mod;
	  continue;
	}

	int remain = field[y][x] - '0' - left - top;
	if( remain < 0 || remain > 4 ) continue;
	rep(next_bottom,3){
	  int next_right = remain - next_bottom;
	  if( next_right < 0 || next_right > 2 ) continue;
	  int nbitmask = bitmask3;
	  if( next_right && x == w-1 ) continue;
	  if( next_bottom && y == h-1 ) continue;
	  nbitmask = set(nbitmask,x,next_bottom);
	  nbitmask = set(nbitmask,x+1,next_right);
	  if( x == w-1 ) nbitmask = fix(nbitmask,w+1);
	  ( dp[x+y*w+1][nbitmask] += dp[x+y*w][bitmask3] ) %= mod;
	}
      }
    }
  }
  int sum = 0;
  rep(i,pow3[w+1]) ( sum += dp[h*w][i] ) %= mod;
  assert( sum >= 0 );
  cout << sum << endl;
}

int main(){
  pow3[0] = 1;
  REP(i,1,13) pow3[i] = pow3[i-1] * 3;

  cin >> h >> w;
  rep(i,h) scanf(" %s",&field[i]);
  compute();
  return 0;
}

Measured memory_bytes: 70832
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

#ifndef INCLUDED_ROLLING_HASH_HPP
#define INCLUDED_ROLLING_HASH_HPP

#include <vector>
#include <string>

class rolling_hash {
public:
	using u64 = std::uint_fast64_t;
	using size_type = std::uint_fast32_t;
	using i128 = __int128_t;

	static constexpr u64 MOD = (1uL << 61) - 1;
	static constexpr u64 base = 20200213;

	std::string str;
	std::vector<u64> hash_, pow;

private:
	static constexpr u64 mask30 = (1ul << 30) - 1;
	static constexpr u64 mask31 = (1ul << 31) - 1;

	u64 mul(i128 a, i128 b) const {
		i128 t = a * b;
		t = (t >> 61) + (t & MOD);

		if (t >= MOD) return t - MOD;
		return t;
	}
	size_type xorshift(size_type x) const {
		x ^= x << 13;
		x ^= x >> 17;
		x ^= x << 5;
		return x;
	}

public:
	rolling_hash(const rolling_hash &) = default;
	rolling_hash(rolling_hash&&) = default;

	rolling_hash() : str() {};
	rolling_hash(const std::string & str) : str(str) {
		hash_.resize(str.size() + 1, 0);
		pow.resize(str.size() + 1, 1);
		for (size_type i = 0; i < str.size(); i++) {
			hash_[i + 1] = mul(hash_[i], base) + xorshift(str[i] + 1);
			pow[i + 1] = mul(pow[i], base);
			if (hash_[i + 1] >= MOD) hash_[i + 1] -= MOD;
		}
	}

	u64 hash() const { return hash_.back(); }
	u64 hash(size_type l, size_type r) const {
		u64 ret = MOD + hash_[r] - mul(hash_[l], pow[r - l]);
		return ret < MOD ? ret : ret - MOD;
	}

	size_type size() const { return str.size(); }
};

#endif

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	int n;
	cin >> n;
	string s;
	cin >> s;
	rolling_hash rol(s);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			while (i + ans < j && j + ans < n) {
				if (rol.hash(i, i + ans + 1) != rol.hash(j, j + ans + 1)) break;
				ans++;
			}
		}
	}
	cout << ans << '\n';
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

ll N;
void dfs(string s, char M)
{
  ll sl = s.size();
  if (sl == N) {
    cout << s << endl;
    return;
  }
  for (ll i = 0; i <= M - 'a' + 1; ++i) {
    dfs(s + (char)('a' + i), max(M, (char)('a' + i)));
  }
}

int main()
{
  cin >> N;
  dfs("a", 'a');
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll x;
    cin>>x;
    ll ans=1;
    for (int i=1;i<=x;i++){
        ans=(ans%mod*i%mod)%mod;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	ll n, m, ans=0;

	cin>>n>>m;

	vll a(n+1, 0), sum(n+2, 0);

	rep(i, m){
		ll l, r;
		cin>>l>>r;
		a[l-1]++; a[r]--;
	}

	rep(i, n){
		sum[i+1]=sum[i]+a[i];
		if(sum[i+1]==m) ans++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1792
n, m = map(int, input().split())
s = []
for i in range(m):
    s.append(list(map(int, input().split()))[1:])
p = list(map(int, input().split()))

ans = 0
for i in range(2**n):
    i_bin = "{:010b}".format(i)[::-1]
    for m_i in range(m):
        bulb_sum = 0
        for x in s[m_i]:
            bulb_sum += int(i_bin[x-1])
        if bulb_sum % 2 != p[m_i]:
            break
    else:
        ans += 1

print(ans)


Measured memory_bytes: 3064
//author: zekigurbuz (Zeki Gurbuz) 2020
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define mp make_pair
#define pb push_back
#define lb lower_bound
#define all(x) begin(x),end(x)

const int N = 1e5 + 10;
const int M = 1e9 + 7;

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

template<class T>void ckmin(T&a,T b){a=min(a,b);}
template<class T>void ckmax(T&a,T b){a=max(a,b);}

void precomp() {

}

ll five(ll x) {
	return x * x * x * x * x;
}


void solve() {
	ll x; cin >> x;
	for (ll a = -2000LL; a <= 2000LL; ++a) {
		for (ll b = -2000LL; b <= 2000LL; ++b) {
			if (five(a) - five(b) == x) {
				cout << a << " " << b << endl;
				return;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	precomp();
	int t = 1; // cin >> t;
	for (int i = 1; i <= t; ++i) {
		solve();
	}
	return 0;
}



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

int main() {
  int A, B;
  cin >> A >> B;
  int a, b, m=0;
  for (int i=1; i<=10000; i++) {
    a=i*1.08-i;
    b=i*1.1-i;
    if (a==A && b==B) {
      m=i;
      break;
    }
  }
  if (m==0) {m=-1;}
  cout << m << endl;
}


Measured memory_bytes: 3684
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
//#include <unordered_map>
//#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")

using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()

//typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18; // segment tree size
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f; // memset(dp, 0x3f, sizeof(dp)), 2*INF < INT_MAX
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10; // double EPS

ll in[100050];
ll sum[2];
int main() {
	int N, i;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%lld", &in[i]);
		sum[i % 2] += max(0ll, in[i]);
	}
	if (sum[0] == 0 && sum[1] == 0) {
		int mxp = 1;
		for (i = 2; i <= N; i++) if (in[mxp] < in[i]) mxp = i;

		printf("%lld\n", in[mxp]);
		printf("%d\n", N - 1);
		for (i = N; i > mxp; i--) printf("%d\n", i);
		for (i = 1; i < mxp; i++) printf("1\n");
		return 0;
	}

	vector <int> Vp;
	if (sum[0] < sum[1]) {
		for (i = 1; i <= N; i += 2) if (in[i] > 0) Vp.push_back(i);
	}
	else {
		for (i = 2; i <= N; i += 2) if (in[i] > 0) Vp.push_back(i);
	}

	vector <int> Va;
	for (i = N; i > Vp.back(); i--) Va.push_back(i);

	for (i = (int)Vp.size() - 2; i >= 0; i--) {
		int t1 = Vp[i], t2 = Vp[i + 1];
		for (int j = 1; j < (t2 - t1) / 2; j++) Va.push_back(t1 + 2);
		Va.push_back(t1 + 1);
		//for (int j = 1; j <= (t2 - t1) / 2; j++) Va.push_back(t1 + 1);
	}
	for (int j = 1; j < Vp[0]; j++) Va.push_back(1);

	printf("%lld\n", max(sum[0], sum[1]));
	printf("%d\n", (int)Va.size());
	for (auto it : Va) printf("%d\n", it);
	return 0;
}

Measured memory_bytes: 256
// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

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

#define fi first
#define se second

using namespace std;

typedef long long ll;

int arr[205];

int n, ans;

void solve() {                   
	scanf("%d", &n);

    for (int i = 1; i <= (n << 1); ++i) {
    	scanf("%d", &arr[i]);
    }

    sort(arr + 1, arr + (n << 1) + 1);

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

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

int main() {    
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

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

    int n = sc.nextInt();

    int[] list = new int[n];
    for (int i = 0; i < n; i++) {
      list[i] = sc.nextInt();
    }

    int result = 100;
    for (int i = 0; i < n; i++) {
      int t = i;

      int left = 0;
      int right = 0;
      for (int j = 0; j < n; j++) {
        if(t >= j) {
          left += list[j];
        } else if (t < j) {
          right += list[j];
        }
      }

      int abs = Math.abs(left - right);

      if(abs < result) {
        result = abs;
      }
    }

    System.out.println(result);
  }
}


Measured memory_bytes: 21972
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using Pair = pair<int64_t, int64_t>;
constexpr int64_t kInf = INT64_MAX / 2L;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int64_t N;
  cin >> N;
  // const int64_t L = static_cast<int64_t>(T.length());
  vector<int64_t> A(N);
  for (int64_t i = 0; i < N; ++i) {
    cin >> A[i];
  }
  int64_t result = 0;
  int64_t active = 0;
  for (int64_t i = 0; i < N; ++i) {
    if (A[i] > active) {
      result += A[i] - active;
    }
    active = A[i];
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 3664
#include <stdio.h>

int main(void)
{
	double r;
	const double pi = 3.14159265359;

	scanf("%lf", &r);
	if(r <= 0)
		return -1;
	printf("%.5lf %.5lf\n", r * r * pi, 2 * r * pi);

	return 0;
}

Measured memory_bytes: 652
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define mi          map<int,int>
#define mii         map<pi,int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846

 const int N=2e5+5;

 int mod= 1e9+7;
 int dx[4]={0,0,+1,-1};
 int dy[4]={+1,-1,0,0};  
 
 
int po(int a, int b) {
	a %= mod;
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res * a) % mod;
		a =(a*a) % mod;
		b >>= 1;
	}
	 return res;	
   }



void solve() {
    int a;
    cin>>a;
    string s;
    cin>>s;
    int num=0;
    rep(i,0,sz(s)) {
		  if(s[i]!='.') {
			    int nax=s[i]-'0';
			    num+=nax;
			    num*=10;
			  }
			  
		}	  
		
		
		num/=10;
		cout<<(num*a)/100<<endl;
     
 }

    
int32_t main() {
	cool;
	int t=1;
	//cin>>t;
	while(t--)
	  solve();

return 0;	   
}


Measured memory_bytes: 3568
num = int(raw_input())
law = raw_input().split(" ")
tmp = 0
raw = []
for i in law:
    raw.append(int(i))
for i in range(num):
    for j in range(i, num):
        div = abs(raw[i] - raw[j])
        if div >= tmp:
            tmp = div
print tmp


Measured memory_bytes: 2568
use std::io;

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).ok().unwrap();
    let num : i32 = input.trim().parse().ok().unwrap();
    let mut input = String::new();
    io::stdin().read_line(&mut input).ok().unwrap();
    let vecs : Vec<i32> = input.trim().split_whitespace().map(|x| x.parse().ok().unwrap()).collect();
    let mut num2 : i32;
    let mut num3 : i32 = 0;
    for i in 1..(num + 1) {
        let num11 : i32 = vecs.iter().by_ref().take(i as usize).sum();
        let num22 : i32 = vecs.iter().by_ref().skip(i as usize).sum();
        num2 = num11 - num22;
        if num2 < 0{
            num2 = num2 * -1;
        }

        if i == 1{
            num3 = num2;
            continue;
        }

        if num3 < num2 {
            println!("{}", num3);
            break;
        }

        num3 = num2;
    }


}



Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

vector<int> v;
int main(){
    int n;
    string s;
    int cnt=0,ans,j;
    while(cin>>s>>n,n){
        v.clear();
        v.pb(stoi(s));
        ans=-1;cnt=0,j=-1;
        while(1){
            while(s.size()!=n) s+='0';
            sort(s.begin(),s.end());
            string t=s;
            reverse(t.begin(),t.end());
            int nx=stoi(t)-stoi(s);
            rep(i,v.size()){
                if(v[i]==nx){
                    j=i,ans=nx;
                    break;
                }
            }
            if(ans!=-1) break;
            v.pb(nx);
            s=to_string(nx);
            ++cnt;
        }
        cout<<j<<" "<<ans<<" "<<cnt-j+1<<endl;
    }
    return 0;
}


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

#define int long long 
#define dou  double 
#define endl "\n"

const int MOD=1e9+7;

void solve()
{
	int l,r,d,i,cnt=0;
	cin >> l >> r >> d;
	for(i=l;i<=r;i++)
	{
		if(i%d==0)
			cnt++;
	}
	cout << cnt << endl;
}

main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	solve();
}

Measured memory_bytes: 3608
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lf else if

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=5e6+19;

int D,c,L,a,b,top;
int coe[2][50];
ll val[20],ans;
pair<ll,ll> A[N],B[N];

ll Pow(ll a,int b){
	ll res=1;
	for (;b;b>>=1,a=a*a) if (b&1) res=res*a;
	return res;
}
void dfs_1(int x,ll v,ll coef){
	if (x==top/2){
		A[++a]=mp(v,coef);
		return;
	}
	For(i,-9,10){
		dfs_1(x+1,v+i*val[x],coef*coe[x==0][i+10]);
	}
}
void dfs_2(int x,ll v,ll coef){
	if (x==top){
		B[++b]=mp(v,coef);
		return;
	}
	For(i,-9,10){
		dfs_2(x+1,v+i*val[x],coef*coe[x==0][i+10]);
	}
}
void Main(){
	a=0,b=0;
	top=L/2;
	For(i,0,L) val[i]=Pow(10,L-1-i)-Pow(10,i);
	if (L%2==0){
		dfs_1(0,0,1);
		dfs_2(top/2,0,1);
	} else{
		dfs_1(0,0,L==1?1:10);
		dfs_2(top/2,0,L==1?1:1);
	}
	sort(A+1,A+a+1);
	sort(B+1,B+b+1);
	c=b;
	for (int la=1,ra;la<=a;la=ra+1){
		ll tmp=A[la].se;
		for (ra=la;ra+1<=a&&A[ra+1].fi==A[ra].fi;ra++) tmp+=A[ra+1].se;
		for (;c>=1&&A[la].fi+B[c].fi>D;c--);
		for (;c>=1&&A[la].fi+B[c].fi==D;c--) ans+=tmp*B[c].se;
	}
}

int main(){
	For(a,0,10) For(b,0,10) coe[0][a-b+10]++;
	For(a,1,10) For(b,1,10) coe[1][a-b+10]++;
	D=IN();
	for (L=1;L<=18;L++) Main();
	cout<<ans<<endl;
}

Measured memory_bytes: 43392
#include <bits/stdc++.h>
typedef long long ll;
#define pb puhs_back
using namespace std;
typedef pair< ll, ll> pll;


bool ok(ll x)
{
        ll ln = 0;
        while(x){
                x /= 10;
                ln++;
        }
        return (ln%2 == 1);
}
int main()
{
        ll n;
        cin >> n;
        ll ans = 0;
        for(ll i=1;i<=n;i++) {
                if(ok(i)) ans++;
        }
        cout << ans << endl;
        return 0;
}


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

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

	for(int n, q; cin >> n >> q, n;) {
		vector<string> name(n);
		vector<int> based(n), western(n);
		for(int i = 0; i < n; ++i)
			cin >> name[i] >> based[i] >> western[i];

		for(int i = 0; i < q; ++i) {
			int year;
			cin >> year;

			for(int i = 0; i < n; ++i)
				if(western[i] - based[i] < year && year <= western[i]) {
					cout << name[i] << " " << year - western[i] + based[i] << endl;
					goto next;
				}

			cout << "Unknown" << endl;

		next:;
		}
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <stack>
#include <limits>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <numeric>
//#include <tuple>

constexpr long long mod = static_cast<long long>(1e9 + 7);

int main() {
    int V, E;
    std::cin >> V >> E;
    std::vector<std::vector<long long>> dists(V, std::vector<long long>(V, std::numeric_limits<long long>::max()));
    for(int i = 0; i < V; ++i) {
        dists[i][i] = 0;
    }

    while(E--){
        int s, t, w;
        std::cin >> s >> t >> w;
        dists[s][t] = w;
    }

    for(int i = 0;i < V; ++i) {
        for(int j = 0; j < V; ++j) {
            for(int k = 0; k < V; ++k) {
                if(dists[j][i] < std::numeric_limits<long long>::max() && dists[i][k] < std::numeric_limits<long long>::max()) dists[j][k] = std::min(dists[j][k], dists[j][i] + dists[i][k]);
            }
        }
    }

    bool negative = false;
    for(int i = 0; i < V; ++i) {
        if(dists[i][i] < 0) negative = true;
    }

    if(negative) std::cout << "NEGATIVE CYCLE" << std::endl;
    else {
        for(const auto& dist: dists) {
            for(int i = 0; i < dist.size(); ++i){
                if(dist[i] == std::numeric_limits<long long>::max())std::cout << "INF";
                else std::cout << dist[i];
                if(i < dist.size() - 1) std::cout << " ";
            }
            std::cout << "\n";
        }
    }

    std::cout << std::flush;

    return 0;
}



Measured memory_bytes: 3172
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

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

    int a[3];

    for(int i = 0;i  < 3;i++) cin >> a[i];

    sort(a,a+3);

    cout << a[2]-a[0];
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
#include <list>
#include <limits>
#include <string>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 998244353;

int gcd(int a, int b){
  if(b == 0) return a;
  return gcd(b, a%b);
}

int main()
{
  int N;
  cin >> N;
  int x[100],y[100];
  ll h[100],hmax = 0,value;
  for(int i=0;i<N;i++){
    cin >> x[i] >> y[i] >> h[i];
    if(h[i] > hmax) hmax = h[i];
  }
  for(int i=0;i<=100;i++){
    for(int j=0;j<=100;j++){
      for(ll k=hmax+200;k>=hmax;k--){
        for(int l=0;l<N;l++){
          value = k-abs(i - x[l])-abs(j - y[l]);
          if(value < 0) value = 0;
          if(value != h[l]) break;
          if(l == N-1){
            cout << i << " " << j  << " " << k;
            return 0;
          } 
        }
      }
    }
  }
      cout << hmax;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
int a[1234567];
 
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
  }
  int g = 0;
  int mx = 0;
  for (int i = 0; i < n; i++) {
    g = __gcd(g, a[i]);
    mx = max(mx, a[i]);
  }
  if (k <= mx && k % g == 0) {
    cout << "POSSIBLE" << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
  return 0;
}

Measured memory_bytes: 640
import Control.Monad
import Control.Applicative
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import Data.Foldable (foldMap)
import Data.List.Split
import Data.Char
import Data.Ratio
import Data.Ord
import Data.Array.IO
 
readInt = read :: String -> Int
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
-- end of templete

f n = 1 + n * (n+1) `div` 2

main = map (f . read) . lines <$> getContents >>= mapM_ print

Measured memory_bytes: 3892
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def dfs(s,Map,H,W):
    dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
    for i in range(4):
        Map[s[0]][s[1]] = '*'
        nextPos = (s[0]+dxdy[i][0],s[1]+dxdy[i][1])
        if nextPos[0] >= 0 and nextPos[1] >= 0 and nextPos[0] < H and nextPos[1] < W:
            if Map[nextPos[0]][nextPos[1]] == '.':
                dfs(nextPos,Map,H,W)

while True:
    W,H = map(int,input().split(" "))
    if W == 0 and H == 0:
        break
    Map = [list(input()) for i in range(0,H)]
    for i in range(H):
        for j in range(W):
            if Map[i][j] == '@':
                S = (i,j)

    dfs(S,Map,H,W)
    print(sum([1 if Map[i][j] == '*' else 0 for i in range(H) for j in range(W)]))

Measured memory_bytes: 6832
#include <stdio.h>

int main(void)
{
    int a, b, i, j, n, f, c=0;
    char s[6];

    scanf("%d", &a);
    scanf("%d", &b);

    for (i=a; i<=b; i++) {
        n = sprintf(s, "%d", i);
        f = 0;
        for (j=0; j<n/2; j++) {
            if (s[j]!=s[n-1-j]) {
                f = 1;
                break;
            }
        }

        if (f==0)   c++;
    }

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

    return 0;
}

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

typedef long long int ll;
ll x, y;

int main() {
    scanf("%lld %lld", &x, &y);
    for(ll i = 0; i <= x && i <= y/4; ++i) {
        ll cur = x - i;
        if(i * 4 + cur * 2 == y) {
            printf("Yes\n");
            return 0;
        }
    }

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

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


void solve(long long N, std::vector<long long> P){
    long long cmin = N + 1;
    long long res = 0;
    for(int i=0; i < N; i++){
        if(P[i] < cmin){
            res++;
        }
        cmin = min(cmin, P[i]);
    }
    cout << res << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> P(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&P[i]);
    }
    solve(N, std::move(P));
    return 0;
}


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

using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n); i > 0; i--)
#define print(n) cout << n << endl
#define all(n) n.begin(), n.end()

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    ll k,n;
    cin >> k >> n;
    vector<ll> a(n+1);
    rep(i,n) cin >> a[i];
    a[n] = k + a[0];
    
    vector<ll> b(n);
    rep(i,n) b[i] = a[i+1] - a[i];

    sort(all(b));
    print(accumulate(all(b),0LL)-b[n-1]);
    return 0;
}

Measured memory_bytes: 3456
n = int(input())
an = [int(i) for i in input().split()]
lowe, min_an_sub = 0, an[0]
an_sub = []
for i in range(0, n):
    an_sub.append(an[i])
    min_an_sub = min(min_an_sub, an[i])
    if an_sub[i] <= min_an_sub:
        lowe += 1
print(lowe)

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

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

vector<int64_t> fact, fact_inv;

void create_mod_tables(int num){
    fact.assign(num+1, 1);
    fact_inv.assign(num+1, 1);
    for(int i=1; i<=num; i++) fact[i] = fact[i-1] * i % MOD;
    fact_inv[num] = inv_mod(fact[num]);
    for(int i=num; i>0; i--) fact_inv[i-1] = fact_inv[i] * i % MOD;
}

int64_t comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}

int64_t perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}

// P = {P[0], P[1], ..., P[N]}
int64_t LagrangeInterpolation(vector<int64_t> P, int64_t T){
    int N = P.size()-1;
    if(T <= N) return P[T];
    int64_t Qi = 1, QTA = 1;
    for(int i=0; i<=N; i++){
        if(i) mul(Qi, MOD-i);
        mul(QTA, T-i);
    }
    int64_t ans = 0;
    for(int i=0; i<=N; i++){
        add(ans, P[i] * inv_mod(Qi) % MOD * QTA % MOD * inv_mod(T-i));
        mul(Qi, (i+1) * inv_mod(MOD-N+i) % MOD);
    }
    return ans;
}

int64_t calc(int N){
    int64_t ans = 0;
    for(int i=0; 2*i+5<=N; i++) add(ans, comb_mod(i+4, 4) * comb_mod(N-2*i+5, 10));
    return ans;
}

void solve(){
    int N;
    cin >> N;
    if(N < 5){
        cout << 0 << endl;
        return;
    }
    int r = (N-5)%2, n = (N-5)/2;
    vector<int64_t> V(20);
    for(int i=0; i<20; i++) V[i] = calc(2*i+5+r);
    int64_t ans = LagrangeInterpolation(V, n);
    cout << ans << endl;
}

int main(){
    create_mod_tables(100);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1000000000000000000;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x,y;
    cin >> x >> y;
    ll k=1;
    //yがxの約数なら-1
    if(x%y==0) {
        cout << -1 << endl;   
    }else{
        cout << x << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[n + 1];
    for(int i = 1; i <= n; ++i) cin >> arr[i];
    for(int i = 1; i <= n; ++i){
        arr[0] = arr[i];
        int j = i-1;
        while(arr[0] < arr[j]) { arr[j + 1] = arr[j]; --j; }
        arr[j + 1] = arr[0];
        for(j = 1; j < n; ++j) cout << arr[j] << " ";
        cout << arr[j] << endl;
    }
    return 0;
}


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

typedef long long ll;
typedef vector <ll> vr;
typedef pair <ll, ll> pr;
typedef vector <ll> :: iterator ir;

#define pub push_back
#define pob pop_back
#define mp make_pair
#define pc __builtin_popcount
#define lb lower_bound

ll dig(ll n) {
	string s = to_string(n);
	return s.size();
}

ll totSum(ll arr[], ll n) {
	ll sum = 0;
	for (ll i = 0; i < n; i++) {
		sum += arr[i];
	}
	return sum;
}


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	/*#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif*/




// write your code here

	double d, t, s;
	cin >> d >> t >> s;
	if (d / s <= t)cout << "Yes";
	else cout << "No";

// this is the end of your code

}


Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s; cin >> s;
    deque<char> que(s.begin(), s.end());
    int q; cin >> q;
    bool rev = false;
    for (int i = 0; i < q; i++) {
        int t; cin >> t;
        if (t == 1) {
            rev = (rev ? false : true);
        } else {
            int f; char c; cin >> f >> c;
            if (f == 1) {
                if (rev) {
                    que.push_back(c);
                } else {
                    que.push_front(c);
                }
            } else {
                if (rev) {
                    que.push_front(c);
                } else {
                    que.push_back(c);
                }
            }
        }
    }
    if (rev) reverse(que.begin(), que.end());
    for (char c : que) cout << c;
}


Measured memory_bytes: 1024
//通れー！！！(๑>◡<๑)
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
using namespace std;
int main(){
  int n,k,gu,ch,pa;
  int ans=0;
  string robot;
  cin >> n >> k >> gu >> ch >> pa >> robot;
  bool check[n]={false};
	
  auto score = [&](int i){
	if(robot[i] == 'r') return pa;
	else if(robot[i] == 's') return gu;
	else return ch;
  };
	
  rep(i,n){
    if(i<k){
	  ans += score(i);
	  check[i] = true;
    }
	else{
	  if(robot[i]==robot[i-k] && check[i-k]) continue;
      else{
        ans += score(i);
        check[i] = true;
      }
    }
  }
	cout << ans << endl;
}


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

void fnInput(vector<int>& rvnCard)
{
  int nCardSiz;
  cin >> nCardSiz;

  for (int i = 0; i < nCardSiz; i++)
    cin >> rvnCard[i];

  sort(begin(rvnCard), end(rvnCard), greater<int>() );
}

int fnDigitsSum(int nNum)
{
  int nDigitsSum = 0;
  while ( nNum )
  {
    nDigitsSum += nNum % 10;
    nNum /= 10;
  }
  return nDigitsSum;
}

int fnGameExec(const vector<int>& cnrvnCard)
{
  int nAlcePnt = 0, nBobPnt = 0;

  for (int i = 0; i < cnrvnCard.size(); i++)
  {
    if (i % 2 == 0)
      nAlcePnt += cnrvnCard[i];
    else
      nBobPnt  += cnrvnCard[i];
  }

  int nDiffPnt = nAlcePnt - nBobPnt;
  return nDiffPnt;
}

int main()
{
  vector<int> vnCard(100);
  fnInput(vnCard);
  cout << fnGameExec(vnCard) << endl;

  return 0;
}


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

int main(){
	int n;
	int div, sisu;
	int sum, res;
	
	while((scanf("%d", &n)) != 0){
		
		if(n == 0) break;
		
		div = 5; sisu = 1;
		sum = 0; res = 0;
		
		while(div * 5 <= n){
			div *= 5;
			sisu++;
		}
		
		while(sisu > 0){
			res += (n / div - sum) * sisu;
			sum = n / div;
			sisu--;
			div /= 5;
		}
		
		printf("%d\n", res);
	}
	
	return 0;
}

Measured memory_bytes: 1028
from fractions import gcd
"""
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
"""
class SegTree():
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.func = function
        self.basement = basement
        self.seg = [basement]*2**(self.K+1)#basementで初期化
 
        for i in range(self.n):
            self.seg[i+2**self.K-1] = lists[i]
 
        for i in range(2**(self.K)-2, -1, -1):
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])
 
    def update(self, k, value):
        # 0-indexでa[k]の値をvalueに変更
        k += 2**self.K-1
        self.seg[k] = value
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])
 
    def query(self, p, q):
        # 0-indexで[p,q)の値を取得する
        if q <= p:
            return self.basement
        num = 2**self.K
        p += num-1
        q += num-2
        res = self.basement
        while q-p > 1:
            if p & 1 == 0:
                res = self.func(res, self.seg[p])
            if q & 1 == 1:
                res = self.func(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res, self.seg[p])
        else:
            res = self.func(self.func(res, self.seg[p]), self.seg[q])
        return res
 

n=int(input())
a=list(map(int,input().split()))
seg=SegTree(a,gcd,0)
ans=1
for i in range(n):
    ans=max(ans,gcd(seg.query(0,i),seg.query(i+1,n)))
print(ans)


Measured memory_bytes: 16176