akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
char chlit(char c){return c+32;}
char chbig(char c){return c-32;}

int main(){
  int n,k;cin >> n >> k;
  string s;cin >> s;
  for(int i=0;i<n;++i){
    if(i == k-1)cout << chlit(s[i]);
    else cout << s[i];
  }
  return 0;
}


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

using namespace std;

using ll = long long int;

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

    vector<ll> a(n);
    vector<vector<ll>> x,y;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        vector<ll> tmpx(a[i]),tmpy(a[i]);
        for(int j = 0; j < a[i]; j++){
            cin >> tmpx[j] >> tmpy[j];
        }
        x.push_back(tmpx);
        y.push_back(tmpy);
    }

    ll ans = 0;

    for(int i = 0; i < (1LL << n); i++){
        bool flag = true;
        ll tmp = 0;
        for(int j = 0; j < n; j++){
            if((1LL << j) & i){
                tmp++;
                for(int k = 0; k < a[j]; k++){
                    if(((1 << (x[j][k] - 1)) & i ) && y[j][k] == 0){
                        flag = false;
                    }
                    if(!((1 << (x[j][k] - 1)) & i ) && y[j][k] == 1){
                        flag = false;
                    }
                }
            }
        }
        if(flag){
            ans = max(ans,tmp);
        }
    }

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

Measured memory_bytes: 256
from __future__ import print_function
[N, M] = map(int, raw_input().split())
d = [-1 for i in range(N)]
for i in range(M):
    [a,b] = map(int, raw_input().split())
    if d[a-1] == -1:
        d[a-1] = b
    elif d[a-1] != b:
        print("-1")
        exit(0)

if N == 1 and M == 0:
    print (0)
    exit(0)

if d[0] == -1:
    #print 1,
    print("1",end="")
elif d[0] == 0 and N > 1:
    print ("-1")
    exit(0)
elif N > 1:
    #print d[0],
    print(d[0], end="")

for i in range(1,N-1):
        if d[i] == -1:
            #print 0,
            print("0",end="")
        else:
            #print d[i],
            print(d[i], end="")

if d[N-1] == -1:
    #print 0
    print(0)
else:
    #print d[N-1]
    print(d[N-1])


Measured memory_bytes: 2820
A,B=map(int,input().split())
S=input()
s_list=[]
for i in range(10):
    s_list.append(str(i))
for i in range(A):
    if S[i] not in s_list:
        print("No")
        exit()
if S[A]!='-':
    print("No")
    exit()
for i in range(A+1,A+1+B):
    if S[i] not in s_list:
        print("No")
        exit()
print("Yes")

Measured memory_bytes: 3064
#include<iostream>
 #include<stdio.h>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 #include<stack>
 #include<queue>
 
 using namespace std;
 
 int main()
 {
   int h,m,s;
   int S;
   cin>>S;
   s=S%60;
   S/=60;
   m=S%60;
   S/=60;
   h=S;
   cout<<h<<":"<<m<<":"<<s<<endl;
   //while(1);
   return 0;
 }
 

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

int S[1001][1001];

void prep(string str1, string str2, int len1, int len2)
{
    int a, b, i;
    S[0][0] = 0;
    for(i = 1; i <= len1; i++){ S[i][0] = 0; }
    for(i = 1; i <= len2; i++){ S[0][i] = 0; }
    for(a = 1; a <= len1; a++){
        for(b = 1; b <= len2; b++){
            if(str1[a - 1] == str2[b - 1]){ S[a][b] = 1; }else{ S[a][b] = 0; }
        }
    }
    return;
}

int main()
{
    int i, a, b, q, len1, len2;
    cin >> q;
    string str1, str2;

    for(i = 0; i < q; i++){
        cin >> str1 >> str2;
        len1 = str1.size();
        len2 = str2.size();
        prep(str1, str2, len1, len2);
        for(a = 1; a <= len1; a++){
            for(b = 1; b <= len2; b++){
                if(S[a][b]){ S[a][b] = S[a - 1][b - 1] + 1; }
                else{ S[a][b] = max(S[a - 1][b], S[a][b - 1]); }
            }
        }
		cout << S[len1][len2] << endl;
    }
    return 0;
}

Measured memory_bytes: 5128
/**
 *   author: sahushivam
 *   created: 08 December 2019 (Sunday)  17:56:42
**/
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
#define REP(i,a,b) for(int i = a; i<b; i++)
#define MOD 1000000007
#define INF 1e18
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define int long long

int sumXOR(vector<int> arr, int n) 
{ 
    int sum = 0; 
    for (int i = 0; i < 64; i++)  
    { 
        int zc = 0, oc = 0;  
          
         int idsum = 0;  
        for (int j = 0; j < n; j++) 
        { 
            if (arr[j] % 2 == 0) 
                zc++; 
            else
                oc++; 
            arr[j] /= 2; 
        } 
          
        idsum = (((oc * zc)%MOD) * ((1LL << i)%MOD)%MOD)%MOD;  
  
        sum += idsum;  
        sum%=MOD;
    } 
    return sum%MOD; 
}
signed main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int t=1;
    cin>>t;
    vector<int> arr(t);
    for(int i=0;i<t;i++) cin>>arr[i];
    cout<<sumXOR(arr,t);  
return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
set<ll> se;
ll n,q,a,b,c;
vector<PP> v;
int main(void){
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>a>>b>>c;
        v.push_back({a-c,{0,c}});
        v.push_back({b-c-1,{2,c}});
    }
    while(q--){
        cin>>a;
        v.push_back({a,{1,0}});
    }
    sort(v.begin(),v.end());
    for(auto x:v){
        if(x.S.F==0)se.insert(x.S.S);
        else if(x.S.F==2)se.erase(x.S.S);
        else{
            if(se.size()==0)cout<<-1<<endl;
            else cout<<*se.begin()<<endl;
        }
    }
}


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

const int N = 1000;
const int MOD = 1e9 + 7;

vector<int> prime;

void enum_prime() {
  vector<bool> is_prime(N+1, true);
  for (int i = 2; i <= N; ++i) {
    if (!(is_prime[i])) continue;
    prime.push_back(i);
    for (int j = 2*i; j <= N; j += i) is_prime[j] = false;
  }
  return;
}

int main() {
  int n;
  cin >> n;
  enum_prime();
  vector<int> num_factor;
  rep(i, prime.size()) {
    int m = n;
    int c = 0;
    while (m) {
      c += m / prime[i];
      m /= prime[i];
    }
    num_factor.push_back(c);
  }
  ll ans = 1;
  rep(i, num_factor.size()) {
    ans = ans * (num_factor[i] + 1) % MOD;
  }
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 3736
#include<stdio.h>
#include<math.h>

typedef struct{
 double x;
 double y;
}point;


void koch(int d,point left,point right){
point s,t,u;

if(d==0){printf("%lf %lf\n",left.x,left.y);return;}

s.x=(2*left.x+right.x)/3;
s.y=(2*left.y+right.y)/3;
koch(d-1,left,s);

t.x=(left.x+2*right.x)/3;
t.y=(left.y+2*right.y)/3;

u.x=((t.x-s.x)-sqrt(3)*(t.y-s.y))/2+s.x;
u.y=((t.y-s.y)+sqrt(3)*(t.x-s.x))/2+s.y;
koch(d-1,s,u);

koch(d-1,u,t);

koch(d-1,t,right);


return;
}


int main(){
int n;
point Start;
point Last;

/*両端の設定*/
Start.x=0;
Start.y=0;

Last.x=100;
Last.y=0;
/*----------*/

scanf("%d",&n);

koch(n,Start,Last);

printf("%lf %lf\n",Last.x,Last.y);

return 0;
}


Measured memory_bytes: 2048
#include <iostream>
using namespace std;
int main(){
	int S,h,m,s;
	cin >> S;
	h=S/3600;
	m=S/60;
	m=m%60;
	s=S%60;
	cout << h << ":"<< m  << ":" << s << endl;
    return 0;
}

Measured memory_bytes: 3096
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define si(x) scanf("%d", &x)
#define sc(x) scanf("%c", &x)
#define sl(x) scanf("%lld", &x)
#define pl(x) printf("%lld\n", x)
#define pi(x) printf("%d\n", x)
#define pii pair <int, int>
#define pll pair <long long, long long>
#define gu getchar_unlocked
#define pu putchar_unlocked
#define setbits __builtin_popcountll
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define speed ios::sync_with_stdio(false)

const int N = 100005;

int main(){
    string s;
    cin>>s;
    if(s == "Sunny"){
    	cout<<"Cloudy"<<endl;
    }
    else if(s == "Cloudy"){
    	cout<<"Rainy"<<endl;
    }
    else{
    	cout<<"Sunny"<<endl;
    }
}

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

#define int long long
#define pb emplace_back
#define f(i,n) for(int i=1 ; i<=n ; i++)
#define F first
#define S second
#define fast ios:: sync_with_stdio(false),cin.tie(0);
int dp[3005][3005];
int32_t main(){
	fast;
	string s,t ,ans;
	cin >> s >> t;
	
	int n = s.length();
	int m = t.length();
	
	for(int i=0; i<=n ; i++)
	{
		for(int j=0 ; j<=m ; j++)
		{
			if(i==0 || j==0)
				continue;
			if(s[i-1]==t[j-1])
				dp[i][j] =  dp[i-1][j-1] + 1;
			else
				dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
		}
	}
	while(n>0 && m>0)
	{
		if(s[n-1]==t[m-1])
			ans += s[n-1], n--,m--;
		else if(dp[n][m-1] > dp[n-1][m])
			m--;
		else
			n--;
	}
	reverse(ans.begin() , ans.end());
	cout << ans;
}







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

int main(){
    string S ;
    string T ;
    cin >> S ;
    cin >> T ;
    int n = S.size() ;
    int A[30][30]={} ;
    rep(i,n) A[S.at(i)-'a'][T.at(i)-'a']++ ;
    rep(i,30){
        int count = 0 ;
        rep(j,30) if(A[i][j]>0) count++ ;
        if( count > 1 ){
            cout << "No" << endl;
            return 0 ;
        }
    }
    
    int B[30][30]={} ;

    rep(i,n) B[T.at(i)-'a'][S.at(i)-'a']++ ;
    rep(i,30){
        int count = 0 ;
        rep(j,30) if(B[i][j]>0) count++ ;
        if( count > 1 ){
            cout << "No" << endl;
            return 0 ;
        }
    }
    cout <<"Yes" << endl;
}

Measured memory_bytes: 776
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val k = sc.nextInt()
    val rem = (1..n).toMutableSet()
    repeat(k) {
        val d = sc.nextInt()
        repeat(d) {
            val a = sc.nextInt()
            rem.remove(a)
        }
    }
    println(rem.size)
}

Measured memory_bytes: 48204
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


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

  if(S.size() <= K) cout << S << endl;
  else cout << S.substr(0,K) << "..." << endl;
  
  return 0;
}



Measured memory_bytes: 3632
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int N, K; cin >> N >> K;
    vi A(N); REP(i, N) cin >> A[i];

    //sort(A.begin(), A.end());
    int ans = 1 + ((N - K) + K - 2) / (K - 1);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;
public class Main{
    
    public static void main (String[ ]args){
        
        Main main = new Main ();
        main.solve();
    }
    
    private void solve (){
        Scanner sc = new Scanner (System.in);
        
        int A = sc.nextInt();
        int B = sc.nextInt();
        
        if (A==B){
            System.out.println(A+B);
        } else {
            if (A>B){
                System.out.println(A+A-1);
            } else {
                System.out.println(B+B-1);
            }
        }
    }
}

Measured memory_bytes: 21716
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

template< typename T,char start='a',int csize=26 >
struct Trie{
    const int NONE = -1;
    struct Node{
        const int NONE = -1;
        vector<int> nxt;
        vector<int> acs;
        T val;
        T prefsum;
        Node(){
            val=0;
            prefsum=0;
            nxt.resize(csize,NONE);
            acs.resize(26,0);
        }
    };

    vector<Node> nodes;
    ll ans=0;

    Trie(){
        nodes.push_back(Node());
    }

    void accept(int noid,int id,T v){
        nodes[noid].acs[v]++;
        //nodes[noid].val=max(nodes[noid].val,v);
        nodes[noid].prefsum+=v;
    }

    void update(int noid,T v){
        nodes[noid].prefsum+=v;
    }

    void add(const string &S,int stid,int noid,int id,T v){
        if(stid==S.size()){
            accept(noid,id,v);
        }else{
            int c=S[stid]-start;
            if(nodes[noid].nxt[c]==NONE){
                nodes[noid].nxt[c]=(int)nodes.size();
                nodes.push_back(Node());
            }
            update(noid,v);
            add(S,stid+1,nodes[noid].nxt[c],id,v);
        }
    }

    void add(const string &S,int id,T v=1){
        add(S,0,0,id,v);
    }

    int find(const string &S,vector<int> &alp){
        int noid=0;
        for(int i=0;i<S.size();++i){
            rep(j,26) if(alp[j]>=i) ans+=nodes[noid].acs[j];
            int c=S[i]-start;
            if(nodes[noid].nxt[c]==NONE) return NONE;
            noid=nodes[noid].nxt[c];
        }
        return noid;
    }

    void solve(vector<string> &S){
      int N=S.size();
      for(int i=0;i<N;i++){
        string t=S[i].substr(0,(int)S[i].size()-1);
        char c=S[i][(int)S[i].size()-1];

        vector<int> A(26,-1);
        rep(j,S[i].size()) A[S[i][j]-'a']=j;
        find(S[i],A);

        add(t,i,c-'a');
      }
      cout<<ans<<endl;
    }
};

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

  int N;
  cin>>N;
  vector<string> S(N);
  rep(i,N) cin>>S[i];

  rep(i,N) reverse(all(S[i]));

  vector<int> ord(N);
  rep(i,N) ord[i]=i;
  sort(all(ord),[&](int a,int b){
    if(S[a].size()==S[b].size()) return a<b;
    else return S[a].size()<S[b].size();
  });
  vector<string> T;
  for(auto i:ord) T.push_back(S[i]);

  Trie<int> trie;
  trie.solve(T);

  return 0;
}


Measured memory_bytes: 449504
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#include <bitset>
#define M 1000000007
#define M1 998244353

#define tr(container, it) \
for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)

#define fast                        \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

ll power(ll x, ll n)
{
    ll result = 1;
    while (n)
    {
        if (n % 2 == 1)
            result = result * x;
        n = n / 2;
        x = x * x;
    }
    return result;
}

ll gcd(ll a, ll b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}

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

inline ll mul(ll x, ll y, ll m)
{
    ll z = 1LL * x * y;
    if (z >= m)
    {
        z %= m;
    }
    return z;
}

ll powmod(ll x, ll y, ll m)
{
    ll r = 1;
    while (y)
    {
        if (y & 1)
        {
            r = mul(r, x, m);
        }
        y >>= 1;
        x = mul(x, x, m);
    }
    return r;
}



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

int main()
{
    start();
    string s;
    cin>>s;
    int n=s.length();
    int ans=INT_MAX;
    for (int i=0;i<=n-3;i++)
    {
        ans=min(ans, abs(753-stoi(s.substr(i, 3))));
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

int N;
double L;

double X[86400];

bool ok(double M) {
  double hikaku[2];
  double now = L;
  for (int j=0;j<2;j++) {
      for (int i=0;i<86400;i++) {
	now = now - X[i] + M;
	if (now > L) {
	  now = L;
	} else if (now <= 0) {
	  return false;
	}
      }
      hikaku[j] = now;
  }
  if (hikaku[0] <= hikaku[1]) {
    return true;
  } else {
    return false;
  }
}

int main() {
  while(scanf("%d%lf",&N,&L) && N) {
    for (int i=0;i<86400;i++) {
      X[i] = 0;
    }
    for (int i=0;i<N;i++) {
      int s,t;
      double u;
      scanf("%d%d%lf",&s,&t,&u);
      for (int i=s;i<t;i++) {
	X[i] = u;
      }
    }
    double lo = 0, hi = 1e6;
    while (hi - lo >1e-6) {
      double m = (hi + lo)/2.0;
      if (ok(m)) {
	hi = m;
      } else {
	lo = m;
      }
    }
    printf("%.10f\n",lo);
  }
}

Measured memory_bytes: 1900
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
int cnt[4];
double dp[333][333][333];
double dfs(int a,int b,int c){
    if(a + b + c == 0) return 0.0;
    if(dp[a][b][c] > -0.5) return dp[a][b][c];
    double res = double(N)/(a+b+c);
    if(a) res += dfs(a-1,b,c) * a/(a+b+c);
    if(b) res += dfs(a+1,b-1,c) * b/(a+b+c);
    if(c) res += dfs(a,b+1,c-1) * c/(a+b+c);
    return dp[a][b][c] = res;
}
int main(){
    // debug;
    ios;

    cin>>N;
    for(int i = 1;i<=N;i++){
        int x;cin>>x;
        ++cnt[x];
    }
    for(int i = 0;i<=N;i++)
        for(int j = 0;j<=N;j++)
            for(int k = 0;k<=N;k++)
                dp[i][j][k] = -1;
    cout.precision(12);
    cout<<dfs(cnt[1],cnt[2],cnt[3])<<'\n';

    
    return 0;
}


Measured memory_bytes: 262272
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
const ll mod=1e9+7;
template<typename T> T pow(T a,T b, long long m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
const ll N=1e6+8;
const ll INF=1e18;
  string a,b;
 ll dp[3005][3005];
ll LCS(ll i,ll j){
    if(i==0||j==0)
    return 0;
    if(dp[i][j]!=-1)
    return dp[i][j];
    ll ans=0;
   if(a[i-1]==b[j-1]){
        ans=1+LCS(i-1,j-1);
   }
 ans=max(ans,LCS(i-1,j));
 ans=max(ans,LCS(i,j-1));
 return dp[i][j]=ans;
}
int main(){
    IOS;
    cin>>a>>b;
    string s="";
    memset(dp,-1,sizeof(dp));
    ll l=LCS(a.length(),b.length());
    ll n=a.length(),m=b.length();
  while(n>0&&m>0&&l!=0){
      if(a[n-1]==b[m-1]&&LCS(n,m)==l){
          s+=a[n-1];
        //cout<<a[n-1];
       n--;
       m--;
       l--;
      }
      else 
        if(dp[n-1][m]>dp[n][m-1]){
          n--;
      }
      else 
      m--;
  }
  reverse(s.begin(),s.end());
  cout<<s<<endl;
}


Measured memory_bytes: 71168
#include <bits/stdc++.h>
using namespace std;
//Atcoder
typedef long long ll;
int main() {
    ll n,d,i,j,a,b;
    ll c=0;
    cin>>n>>d;
    for(i=0;i<n;i++)
    {
        cin>>a>>b;
        if(a>d || b>d)
        continue;
        if(sqrt(a*a+b*b)<=d)
        c++;
        
    }
    
    cout<<c;
}


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

#define REP(i,n) for (int i=0;i<(n);i++)
#define PII pair<int,int>
#define LL long long
#define vi vector<int>

int main() {
	long double n, m;
	long double x = 0;
	long double dif;
	long double A;

	cin >> n >> m;

	A = pow(2, m);

	dif = pow(A, -1);

	for (LL i = 1; i < 1000; i++) {
		x += (double)((100 * (n - m) + 1900 * m)* i * dif);
		dif *= (A - 1) / A;
	}

	cout << x << endl;

	return 0;
}

Measured memory_bytes: 256
def bellman_ford(edges, n, src):
    # n:ノード数, src:スタートノード
    # edges:edge(src, tgt, cost)のリスト
    inf = float('inf')
    dist = [inf for _ in range(n)]
    dist[src] = 0
    # 移動経路
    pre = {}

    # 最短経路算出
    for i in range(n-1):
        for edge in edges:
            # srcにコストがあり、tgtのコストよりも低いコストで更新できそうなら
            if dist[edge[0]] != inf and dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                pre[edge[1]] = edge[0]

    # 負の閉路検出
    def checkpath(pre, n, src):
        if src in pre and pre[n-1] == src and pre[src] == n-1:
            return True
        count = 0
        p = pre[n-1]
        while p != src:
            p = pre[p]
            if p == src and src in pre:
                return True
            count += 1
            if count >= n-1:
                return True
        return False

    is_cycle = checkpath(pre, n, src)
    return (dist, is_cycle)


N, M = map(int, input().split())
edges = []
for _ in range(M):
    a, b, c = map(int, input().split())
    edges.append((a-1, b-1, -c))

d, is_cycle = bellman_ford(edges, N, 0)
if is_cycle:
    print('inf')
else:
    print(-d[N-1])

Measured memory_bytes: 3444
def main():
    N, T = (int(i) for i in input().split())
    CT = [[int(i) for i in input().split()] for j in range(N)]
    CT.sort()
    for c, t in CT:
        if t <= T:
            return print(c)
    print("TLE")


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>

#define FastIO 						\
		ios::sync_with_stdio(0); 	\
		cin.tie(NULL); 				\
		cout.tie(NULL);

using namespace std;

typedef long long ll;

#define MOD 1000000007

void solve() {
	int n;
	cin >> n;
	ll a[n] = {}, b[n + 1] = {};
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = n - 1; i > 0; i--) {
		b[i] = b[i + 1] + a[i];
	}
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		sum += ((a[i] % MOD) * (b[i + 1] % MOD)) % MOD;
		sum %= MOD;
	}
	cout << (sum % MOD) << "\n";
}

int main() {
	// FastIO;
	int n = 1;
	// cin >> n;
	while (n--) {
		solve();
	}
}


Measured memory_bytes: 6756
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define rrep(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = int(s); i < int(n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==int(v.size()-1)?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    vi a(n);
    cin >> a;
    int mx = *max_element(all(a));
    int x = 0,y = 0;
    // x -> unique  y -> not unique
    rep(i,n) {
        if(a[i] == mx) y++;
        else if(a[i] == mx-1) x++;
        else {
            Yes(0);
            return 0;
        }
    }
    if(y == n) {
        if(n >= mx*2 or n == mx+1) {
            Yes(1);
            return 0;
        } else {
            Yes(0);
            return 0;
        }
    }
    if(x >= mx) {
        Yes(0);
        return 0;
    }
    Yes(y >= (mx-x)*2);
}


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

int main () {
  int n; cin >> n;
  vector<int> hs(n, 0);
  for (int i = 0; i < n; i++) { cin >> hs[i]; }
  vector<int> memo(n, 0);

  for (int i = 1; i < n; i++)  {
    vector<int> tmp;
    for (int j = 1; j <= 2; j++) {
      int prevIdx = i - j;
      if (prevIdx < 0) {
        continue;
      }
      tmp.push_back(memo[prevIdx] + abs(hs[i] - hs[prevIdx]));
    }
    memo[i] = *min_element(tmp.begin(), tmp.end());
  }
  cout << memo[n-1] << endl;
  return 0;
}

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

int main() {
  int N, K;
  cin >> N >> K;
  vector P(N, 0);
  for (auto &p : P) cin >> p;
  sort(P.begin(), P.end());
  cout << accumulate(P.begin(), P.begin() + K, 0) << "\n";
}

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

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

    if(s == "Sunny") cout << "Cloudy" << endl;
    if(s == "Cloudy") cout << "Rainy" << endl;
    if(s == "Rainy") cout << "Sunny" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ll cnt = 0LL, a = 1LL;
  ll h;
  cin >> h;
  while (a <= h) {
    a *= 2LL;
    cnt++;
  }
  cout << a - 1LL<< endl;
  return 0;
}

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

using namespace std;

bool pairCompare(const pair<long, int> &a, const pair<long, int> &b) {
	return a.first < b.first;
}

int main(int argc, char *argv[]) {
	int n, m;
	cin >> n >> m;
	vector< pair<long, int> > ab(n);
	for (int i = 0; i < n; i++) {
		cin >> ab[i].first >> ab[i].second;
	}
	
	sort(ab.begin(), ab.end(), pairCompare);
	long ans = 0;
	for (int i = 0, sum = 0; sum < m; i++) {
		int buy = sum + ab[i].second > m ? m - sum : ab[i].second;
		ans += ab[i].first * buy;
		sum += buy;
		
	}
	
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define PB push_back
using namespace std;
typedef pair<int, int> P1;
typedef pair<int, pair<int, int> > P2;
static const int INF = 1ll<<60;
static const int dx[] = { 1, -1, 0, 0, };
static const int dy[] = { 0, 0, 1, -1 };
static const int mod = 1000000007;

int N,M;
vector<P1> interval[305];
int dp[305][305][305];
//[最後に塗ったRの場所][最後に塗ったGの場所][最後に塗ったBの場所]

int ans;

bool check(int color[]){
    sort(color,color+3);
    int r = color[2];
    for(auto c : interval[r]){
        int l = c.first,x =c.second;
        if(x == 1){
            if(color[0]>=l||color[1]>=l||r-l+1<1)return false;
        }
        else if(x == 2){
            if(color[0]>=l||color[1]<l||r-l+1<2)return false;
        }
        else if(x == 3){
            if(color[0]<l||r-l+1<3)return false;
        }
    }
    return true;
}

signed main(){
    cin>>N>>M;
    for(int i=0;i<M;++i){
        int l,r,x;
        cin>>l>>r>>x;
        interval[r].PB(P1(l,x));
    }
    dp[1][0][0] = 1;
    dp[0][1][0] = 1;
    dp[0][0][1] = 1;
    for(int R=0;R<=N;++R){
        for(int G=0;G<=N;++G){
            for(int B=0;B<=N;++B){
                int c[] = {R,G,B};
                if(!check(c))dp[R][G][B]=0;
                int nc = max(R,max(G,B));
                dp[nc+1][G][B]+=dp[R][G][B]%mod;
                dp[R][nc+1][B]+=dp[R][G][B]%mod;
                dp[R][G][nc+1]+=dp[R][G][B]%mod;
            }
        }
    }
    for(int i=0;i<N;++i)for(int j=0;j<N;++j){
        ans+=dp[N][i][j]+dp[i][N][j]+dp[i][j][N];
        ans%=mod;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 221440
#include <bits/stdc++.h>
#define ll long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
// rep(i, 1, 4) --> {1,2,3,4}
// rep(i, 4, 1) --> {4,3,2,1}
// rep(it, end(v), begin(v)) --> *it

using namespace std;

int main()
{
    string s;
    cin >> s;
    set<int> se = {1, -1};
    map<int, char> mp = {{1, '+'}, {-1, '-'}};
    int a = s[0] - '0';
    int b = s[1] - '0';
    int c = s[2] - '0';
    int d = s[3] - '0';
    for (auto op1:se)
        for (auto op2:se)
            for (auto op3:se)
            {
                if(a+op1*b+op2*c+op3*d==7)
                {
                    cout<<a<<mp[op1]<<b<<mp[op2]<<c<<mp[op3]<<d<<"=7";
                    return 0;
                }
            }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

using namespace std;

int main(){
  
	int n;
	int m;
	
	cin >> n;
	cin >> m;
	
	int arr[n];
	
	int i, sum = 0, num = 0;
	for(i = 0; i < n; i ++){
		cin >> arr[i];
		num ++;
		sum += arr[i];
	}
	
	int max = 0;
	
	for(i = 0; i < n; i ++){
		if((int)((m-sum)/arr[i]) > max){
			max = (int)((m-sum)/arr[i]);
		}
	}
	
	num += max;
	
	cout << num;
	
	return 0;
  
}

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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

int main() {
    vector<int> res;
    int n, m, p;
    while (cin >> n >> m >> p and n) {
        p = 100 - p;
        m--;
        vector<int> x(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }
        if (x[m] == 0) {
            res.push_back(0);
            continue;
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += x[i] * 100;
        }
        sum = (double)sum * (double)p / 100.0;
        res.push_back(sum / (double)x[m]);
    }
    for (int i = 0; i < (int)res.size(); i++) {
        dump(res[i]);
    }
    return 0;
}



Measured memory_bytes: 3124
class unionFind:
    def __init__(self, n):
        self.data = [-1] * (n+10)

    def find(self, x):
        if self.data[x]>=0:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
        else: return x

    def unite(self, x, y):
        a, b = self.find(x), self.find(y)
        if a!=b:
            self.data[b] += self.data[a]
            self.data[a] = b


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

tree = unionFind(n)
for i in range(m):
    x, y = map(int, input().split())
    tree.unite(p[x-1], p[y-1])

ans = 0
for i in range(n):
    if tree.find(i+1)==tree.find(p[i]): ans += 1
print(ans)

Measured memory_bytes: 13812
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n, q, c[500009], l, r, ans[500009], cnt[500009];
pair<pair<int, int>, int> dat[500009];
int seg, cur;

bool comp(const pair<pair<int, int>, int>& x, const pair<pair<int, int>, int>& y) {
	if (x.fi.fi / seg < y.fi.fi / seg) return true;
	else if (x.fi.fi / seg > y.fi.fi / seg) return false;
	return x.fi.se < y.fi.se;
}

void fun(int a, int b, int x, int y) {
	if (a < x) {
		for (int i = a; i < x; i++) {
			cnt[c[i]]--;
			if (cnt[c[i]] == 0) cur--;
		}
	}
	else {
		for (int i = a - 1; i >= x; i--) {
			if (cnt[c[i]] == 0) cur++;
			cnt[c[i]]++;
		}
	}
	if (b < y) {
		for (int i = b + 1; i <= y; i++) {
			if (cnt[c[i]] == 0) cur++;
			cnt[c[i]]++;
		}
	}
	else {
		for (int i = b; i > y; i--) {
			cnt[c[i]]--;
			if (cnt[c[i]] == 0) cur--;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	for (int i = 0; i < q; i++) {
		cin >> l >> r;
		pair<int, int> tmp = { l, r };
		dat[i] = { tmp, i };
	}
	seg = 1;
	while (seg * seg < n) seg++;
	sort(dat, dat + q, comp);
	for (int i = dat[0].fi.fi; i <= dat[0].fi.se; i++) {
		if (cnt[c[i]] == 0) cur++;
		cnt[c[i]]++;
	}
	ans[dat[0].se] = cur;
	for (int i = 1; i < q; i++) {
		fun(dat[i - 1].fi.fi, dat[i - 1].fi.se, dat[i].fi.fi, dat[i].fi.se);
		ans[dat[i].se] = cur;
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << E;
	}
	//system("pause");
	return 0;
}

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

typedef long long ll;
ll gcd(ll a, ll b){
    if(b==0)return a;
    return gcd(b, a%b);
}

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

int main(int argc, char const *argv[])
{
    ll a,b,c,d;cin>>a>>b>>c>>d;
    ll ret_c = b/c-(a-1)/c;
    ll ret_d = b/d-(a-1)/d;
    ll t = lcm(c,d);
    ll ret_cd = b/t-(a-1)/t;
    // cout << ret_c << " " << ret_d << " " << ret_cd << " ";
    cout << b-a+1-(ret_c + ret_d - ret_cd) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>

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

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF = (1 << 23);

int masu[31][31];
bool al[31][31];
int y[32][31];
int t[31][32];

int main() {
    int w,h;
    int masu[31][31];
    int y[32][31];
    int t[31][32];
    bool al[31][31];


    while(true){

        cin>>w>>h;
        if(w==0&&h==0)break;


        rep(i,h){rep(j,w){
                masu[i][j]=INF;
                al[i][j]=false;
            }
        }

        rep(i,h+1)rep(j,w){y[i][j]=0;}
        rep(i,h)rep(j,w+1){t[i][j]=0;}

        rep(i,w){
            y[0][i]=1;
            y[h][i]=1;
        }
        rep(i,h){
            t[i][0]=1;
            t[i][w]=1;
        }
        int yy=1;

        for(int i=0;i<2*h-1;i++){
            if(i%2==0){
                for(int j=0;j<w-1;j++){
                    cin>>t[i/2][j+1];
                }
            }else{
                for(int j=0;j<w;j++){
                    cin>>y[yy][j];
                }
                yy++;
            }
        }
        // cout<<y[1][1]<<endl;



        queue<pair<int,int>>q;
        q.push({0,0});
        masu[0][0]=1;
        while(!q.empty()){
            int mx=q.front().first;
            int my=q.front().second;
            q.pop();
            al[mx][my]=true;
            if(t[mx][my]==0){//左
                if(al[mx][my-1]==false){
                    q.push({mx,my-1});
                    al[mx][my-1]=true;
                    masu[mx][my-1]=min(masu[mx][my-1],masu[mx][my]+1);
                }
            }
            if(t[mx][my+1]==0){//右
                if(al[mx][my+1]==false){
                    al[mx][my+1]=true;
                    q.push({mx,my+1});
                    masu[mx][my+1]=min(masu[mx][my+1],masu[mx][my]+1);
                }

            }
            if(y[mx][my]==0){//うえ
                if(al[mx-1][my]==false){
                    al[mx-1][my]=true;
                    q.push({mx-1,my});
                    masu[mx-1][my]=min(masu[mx-1][my],masu[mx][my]+1);
                }
            }if(y[mx+1][my]==0){//した
                if(al[mx+1][my]==false){
                    al[mx+1][my]=true;
                    q.push({mx+1,my});
                    masu[mx+1][my]=min(masu[mx+1][my],masu[mx][my]+1);
                }
            }
        }

//        rep(i,h){
//            rep(j,w){
//                cout<<masu[i][j];
//            }
//            cout<<endl;
//        }

        if(masu[h-1][w-1]==INF){
            cout<<0<<endl;
        }else{
            cout<<masu[h-1][w-1]<<endl;
        }

    }



    return 0;
}





Measured memory_bytes: 3032
#include<bits/stdc++.h>
#define lld long long
#define pb push_back
#define mk make_pair
#define MAX (lld)1e18+7
#define lim (lld)1e9+7
#define MAX2 (int)2e5+9
#define ff first
#define ss second
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

const lld mod=lim;

int main()
{
	fastio
	lld a,ans2;
	long double b,ans;


	cin>>a>>b;
	ans = (a*b);
	ans2=floor(ans);

	cout<<ans2<<endl;

}

Measured memory_bytes: 3744
#include <iostream>
//#include <algorithm>
using namespace std;

int main() {
    int n;

    cin >> n;
    int *R = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) cin >> R[i];

    int maxv = R[1] - R[0];
    int minv = R[0];

    for (int i = 1; i < n; i++) {
        maxv = max(maxv, R[i] - minv);
        minv = min(minv, R[i]);
    }

    cout << maxv << endl;
    return 0;
}



Measured memory_bytes: 3876
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = pow(10, 9) + 7;
//const int mod = 998244353;
//const int mod = ;
const int INF = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}

signed main()
{
  int Q, H, S, D, N;
  cin >> Q >> H >> S >> D >> N;

  Q *= 8;
  H *= 4;
  S *= 2;

  int ans;
  if (N % 2 == 0) ans = min({Q, H, S, D}) * (N / 2);
  else ans = min({Q, H, S, D}) * (N / 2) + min({Q, H, S}) / 2;

  cout << ans << endl;
}

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

int main(){
    int i,n,p[100000];
    int result = 1;
    cin >> n;
    for(i=0;i<(n);i++){cin >> p[i];}
    for (i=0;i<(n);i++){
        if (p[i] %2==0){
            if(p[i]%3!=0){
                if(p[i]%5!=0){result = 0;}
            }
        }   
    }
    if(result == 0){cout << "DENIED"<<endl;}
    else{cout <<"APPROVED"<<endl;}
}

Measured memory_bytes: 256
import collections

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n=int(input())
c=collections.Counter(prime_factorize(n))
ans=0
for x in c:
    num=c[x]
    for i in range(1,num+2):
        if i*(i+1)/2>num:
            ans+=i-1
            break
print(ans)

Measured memory_bytes: 9464
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define MAX 510000
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

vl d(100100,-1);
vvl G;

ll dfs(ll u){
    if(d[u] != -1) return d[u];
    ll mx = 0;
    for(auto v : G[u]){
        mx = max(mx, dfs(v)+1);
    }
    return d[u] = mx;
}

int main(){
    ll n,m; cin >> n >> m;
    G.assign(n,vl());
    rep(i,m){
        ll x,y; cin >> x >> y;
        x--; y--;
        G[x].push_back(y);
    }
    ll ans = 0;
    rep(i,n) ans = max(ans, dfs(i));
    cout << ans << endl;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SUM(x) accumulate(rng(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))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
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 int mod = 1000000007;
const double EPS = 1e-9;
const int INF = 1<<30;
const ll INFLL = 1LL<<60;
//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;}

int main () {
  int N, X;
  cin >> N >> X;
  vi x(N);
  rep(i,N) cin >> x[i];
  
  vi d;
  rep(i,N) {
    d.pb(abs(x[i] - X));
  }

  int ans = 0;
  for (auto di : d) {
    ans = gcd(ans, di);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1276
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define pb push_back
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 2*(int)1e5 + 10;

const int mod = 1000000007;

int fact[N], ifact[N];

int power(int a, int b, int m = mod){a %= m; if(b < 0)b += m-1; int r = 1; while(b){if(b&1)r=(r*a)%m; a = (a*a)%m; b>>=1;}return r;}

void pre(){
   fact[0] = 1;
   for (int i = 1; i < N; ++i)
   {
      fact[i] = (fact[i-1] * i) % mod;
   }

   for (int i = 0; i < N; ++i)
   {
      ifact[i] = power(fact[i], -1) % mod; 
   }
}

int nCr(int n, int r){
   if(r > n or r < 0 or n < 0)
      return 0;
   int one = (ifact[n-r] * ifact[r]) % mod;
   int two = fact[n];
   int ans = one * two % mod;
   return ans;
}

vector<int> X, Y;

int getAns(vector<int> arr){
   sort(arr.begin(), arr.end());
   int ans = 0;
   int sum = 0;
   for (int i = 0; i < sz(arr); ++i)
   {
      ans += (arr[i]) * i - sum;
      sum += (arr[i]);
   }
   return ans;
}

void solve(int N, int M, int K){
   pre();

   for (int i = 1; i <= N; ++i)
   {
      for (int j = 1; j <= M; ++j)
      {
         X.push_back(i);
         Y.push_back(j);
      }
   }

   int A = getAns(X);
   int B = getAns(Y);

   int C = (A + B) % mod;

   int tot = nCr(N*M-2, K-2) * C;
   tot %= mod;

   cout<<tot;
}

int32_t main(){_
    int N;
    cin >> N;
    int M;
    cin >> M;
    int K;
    cin >> K;
    solve(N, M, K);
    return 0;
}

Measured memory_bytes: 8292
N = int(input())
A = [-1]
ans = 0
for i in range(N):
    A.append(int(input()))
    if A[i+1] == 0:
        continue
    elif A[i+1] == A[i] + 1:
        ans += 1
    elif A[i+1] <= A[i]:
        ans += A[i+1]
    else:
        print(-1)
        exit()
print(ans)


Measured memory_bytes: 88864
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#define ll long long
#define fo(i, l, r) for (int i = l; i <= r; i++)
#define fd(i, l, r) for (int i = r; i >= l; i--)
using namespace std;
inline ll read()
{
	ll x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
double p,q,dp[1050][1050];
int ip;
int main()
{
	int n,a1,a2,a3;
	n = read();
	fo(i,n,999){
		a1 = i%10;
		a2 = (i/10)%10;
		a3 = (i/100)%10;
		if(a1 == a2 && a1 == a3){
			cout<<i;
			break;
		}
	}
	//system("pause");
	return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
ll mo;
int W[5050];
ll dp[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	int L,R;
	R=(N-1)/2;
	L=R+1;
	FOR(i,L) W[i]=L-i;
	FOR(i,N) W[N-1-i]-=min(R,i+1);
	
	dp[N]=1;
	for(i=1;i<N;i++) {
		int w=-W[i]+1;
		for(x=N;x>=w;x--) (dp[x-w]+=dp[x])%=mo;
	}
	
	ll ret=0;
	FOR(i,N+1) ret+=dp[i]*i%mo;
	cout<<ret%mo<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,i,sum=0;
    cin>>n;
    int a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        sum=sum+a[i];
    }
    if((sum*1.0/n)>(sum/n+.50))
        sum=sum/n+1;
    else
        sum=sum/n;
    long long total=0;
    for(i=0;i<n;i++)
        total=total+(a[i]-sum)*(a[i]-sum);
    cout<<total<<endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define eb emplace_back
#define precision(n) cout << fixed << setprecision(n);
#define fast {ios_base::sync_with_stdio(false);cin.tie(NULL);}
int main()
{
    int r,d,x;
    cin>>r>>d>>x;
    int p=10;
    while(p--)
    {
        int q=r*x-d;
        cout<<q<<endl;
        x=q;
    }
    return 0;
}




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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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 (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair


int main() {
  int w, h, n;
  cin >> w >> h >> n;
  vii x2y(w);
  set<pii> st;
  rep (i, n) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    st.insert(pii(x, y));
    x2y[x].push_back(y);
  }
  rep (i, w) {
    sort(all(x2y[i]));
  }
  int nowx = 0, nowy = 0;
  int cnt = 0;
  while (true) {
    if (nowx == w - 1) {
      break;
    }
    if (x2y[nowx + 1].size() > 0 && x2y[nowx + 1][0] <= nowy) {
      break;
    }
    nowx++;
    cnt++;
    if (nowy == h - 1) {
      continue;
    }
    if (!st.count(pii(nowx, nowy + 1))) {
      nowy++;
    }
  }
  cout << cnt + 1 << endl;
}
  
  


Measured memory_bytes: 20608