akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  int n,m;
  cin>>n>>m;
  int val[m+1]={};
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    for(int j=0;j<k;j++){
      int a;
      cin>>a;
      val[a]++;
    }
  }

  int ans=0;
  for(int i=1;i<=m;i++){
    if(val[i]==n) ans++;
  }
  cout<<ans<<endl;

  return 0;
}


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

int board[3][3];

int main(){
  rep(i,3) rep(j,3) cin >> board[i][j];
  int n; cin >> n;
  rep(i,n){
    int x; cin >> x;
    rep(j,3) rep(k,3){
      if(board[j][k] == x) board[j][k] = 0;
    }
  }

  bool bingo = false;
  rep(i,3){
    if(board[i][0] == board[i][1] && board[i][0] == board[i][2]) bingo = true;
    if(board[0][i] == board[1][i] && board[0][i] == board[2][i]) bingo = true;
  }
  if(board[0][0] == board[1][1] && board[0][0] == board[2][2]) bingo = true;
  if(board[0][2] == board[1][1] && board[0][2] == board[2][0]) bingo = true;

  if(bingo) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 100001
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define REP(i, n) for(int i=0; i<n; i++)
#define RER(i, n) for(int i=n-1; i>=0; i--)
#define ALL(v) v.begin() v.end()
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int w, h, n;

signed main(){
    cin >> w >> h >> n;
    int l, r, t, b;
    l = 0; r = w; t = h, b = 0;
    REP(i, n){
        int x, y, a;
        cin >> x >> y >> a;
        if(a==2) r = min(r, x);
        else if(a==1) l = max(l, x);
        else if(a==4) t = min(t, y);
        else if(a==3) b = max(b, y);
    }
    if(l<r && t>b) cout << (r-l)*(t-b) << endl;
    else cout << 0 << endl;


    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int INF = numeric_limits<int>::max();
int n;
int dp[100005];
int arr[100005];
int f(int curr){
	int&ret = dp[curr];
	if(~ret) return ret;
	if(curr>n) return ret = INF;
	if(curr==n) return ret = 0;
	ret = abs(arr[curr+1]-arr[curr])+f(curr+1);
	if(curr<n-1) ret = min(ret,abs(arr[curr]-arr[curr+2])+f(curr+2));
	return ret;
}
int main(){
	memset(dp,-1,sizeof(dp));
	cin>>n;
	for(int i=1; i<=n; i++) cin>>arr[i];
	cout<<f(1);
}

Measured memory_bytes: 9092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll ch[9][9];
	for(ll i=0;i<3;i++){
		for(ll j=0;j<3;j++){
			cin>>ch[i][j];
		}
	}
	ll n;
	cin>>n;
	map<ll,ll>q;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		q[now]++;
	}
	for(ll i=0;i<3;i++){
		bool ans=true;
		for(ll j=0;j<3;j++){
			ll now=ch[i][j];
			ans=false;
			if(q[now]==1){
				ans=true;
			}
			if(ans==false){
				break;
			}
		}
		if(ans){
			cout<<"Yes";
			return 0;
		}
	}
	for(ll i=0;i<3;i++){
		bool ans=true;
		for(ll j=0;j<3;j++){
			ll now=ch[j][i];
			ans=false;
			if(q[now]==1){
				ans=true;
			}
			if(ans==false){
				break;
			}
		}
		if(ans){
			cout<<"Yes";
			return 0;
		}
	}
	if(q[ch[0][0]]&&q[ch[1][1]]&&ch[ch[2][2]]){
		cout << "Yes";
		return 0;
	}
	if(q[ch[0][2]]&&q[ch[1][1]]&&ch[ch[2][0]]){
		cout << "Yes";
		return 0;
	}
	cout << "No";
	// your code goes here
	return 0;
}

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

using namespace std;

long long n;
long long a[3005];

int main() {
	cin>>n;
	for (long long i = 0; i < n; i++)
		cin>>a[i];
	sort(a, a + n);
	/*for (long long i = 0; i < n; i++)
		cout<<a[i]<<" ";
	cout<<endl;*/
	long long l, r, m;
	long long res = 0;
	for (long long i = 0; i < n; i++)
	for (long long j = i + 1; j + 1 < n; j++) { //[j + 1 ... n) 
		l = j + 1;
		r = n;
		while (r - l > 1) {
			m = (l + r) / 2;
			if (a[m] >= a[i] + a[j]) r = m; else l = m;
		}
		if (a[i] + a[j] > a[j + 1]) {
			res += l - j;
			//cout<<i<<" "<<j<<" "<<(j + 1)<<endl;	
		}
	}
	cout<<res<<endl;
}

Measured memory_bytes: 256
/*
    author:  Maksim1744
    created: 20.04.2019 15:04:21
*/

#include <bits/stdc++.h>

using namespace std;

#define ll   long long
#define ld   long double

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             istream& operator>>(istream& is,  vector<T>& v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>& v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;}

#ifdef HOME
#define TAG_LENGTH       25
#define LR_LEFT          left
#define LR_RIGHT         right
#define LR_VALUE         value
#define LR_SECOND_VALUE  mn
#include "C:/C++ libs/print.cpp"
#else
#define showl            42;
#define shows            42;
#define show(...)        42;
#define showt(...)       42;
#define printTree(...)   42;
#define printLRTree(...) 42;
#define printMatrix(...) 42;
#endif

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> v;
    if (s[0] == '.')
        v.pb(0);
    int i1 = 0;
    for (int i = 1; i < n; ++i) {
        if (s[i] != s[i - 1]) {
            v.pb(i - i1);
            i1 = i;
        }
    }
    v.pb(n - i1);
    if (v.size() % 2 == 1)
        v.pb(0);
    show(v);
    vector<vector<int>> dp(v.size() + 5, vector<int>(2));
    dp[0][0] = 0;
    dp[0][1] = 0;
    for (int i = 0; i < v.size(); ++i) {
        if (i % 2 == 0) {
            dp[i + 1][0] = min(dp[i][0], dp[i][1]);
            dp[i + 1][1] = dp[i][0] + v[i];
        } else {
            dp[i + 1][0] = dp[i][1];
            dp[i + 1][1] = min(dp[i][0], dp[i][1]) + v[i];
        }
    }
    cout << min(dp[v.size()][0], dp[v.size()][1]) << '\n';
    return 0;
}


Measured memory_bytes: 12152
import fractions
from functools import reduce
mod=10**9+7
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


P = 10**9 + 7
N = 10000
inv_t = [0]+[1]
for i in range(2,10**6+1):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
n=input()
hoge=list(map(int,input().split()))
#hoge=[i for i in range(1,10**4)]
ans=0
l=lcm_list(hoge)%mod
for i in hoge:
    tmp=l*inv_t[i]
    ans+=tmp
    ans%=mod
ans%=mod
print(ans)

Measured memory_bytes: 45692
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
int n = 100;
bool col[maxn][maxn];
void output()
{
	printf("%d %d\n", n, n);
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
			printf("%c", col[i][j] ? '#' : '.');
		puts("");
	}
}
int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	--a; --b;
	for(int i = 1; i < n; ++i)
		for(int j = 1; j <= n; ++j)
			if(i == 1 || j & 1)
				col[i][j] = 1;
	for(int j = 2; a > 0; j += 2)
		for(int i = 3; i < n && a > 0; i += 2)
		{
			col[i][j] ^= 1; 
			--a;
		}
	for(int j = n - 1; b > 0; j -= 2)
		for(int i = n - 2; i > 1 && b > 0; i -= 2)
		{
			col[i][j] ^= 1;
			--b;
		}
	output();
	return 0;
}
	

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

int main(){
    int n, cnt = 0, m = 1000000;
    cin >> n;
    rep(i,n){
        int p;
        cin >> p;
        if (p <= m){
            cnt ++;
            m = p;
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>

bool is_kai(const std::string& s, int b, int e) {
    while (b < e) {
        if (s[b] != s[e]) {
            return false;
        }
        b++;
        e--;
    }
    return true;
}

int main() {
    std::string s; std::cin >> s;
    size_t n = s.size();
    std::cout << (((is_kai(s, 0, n-1)&&is_kai(s, 0, (n-1)/2-1)&&is_kai(s, (n+3)/2-1,n-1)))?
    "Yes":"No") << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    int a,i;
    long int sum;
    char x[2]={0},str[1001];

    while(1){
        sum=0;
        scanf("%s",str);

        a=strlen(str);
        for(i=0;i<a;i++){
            x[0]=str[i];
            sum+=atoi(x);
        }
        if(sum!=0){
            printf("%d\n",sum);
        }else{break;}
    }
    return 0;
}


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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;

int POWINT(int x, int n) {
  int ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

ll POWLL(int x, int n) {
  ll ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

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

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

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

  int k, s;
  cin >> k >> s;

  int ans = 0;
  rep(x, 0, k+1) {
    rep(y, 0, k+1) {
      int xy = x + y;
      int z = s - xy;
      if (0 <= z && z <= k) ans++;
    }
  }

  cout << ans << endl;

  return 0;
};


Measured memory_bytes: 256
#include <stdio.h>

#define N 101

int main() {
    int i, j, k, n, m, l;
    int a[N][N], b[N][N];
    long int c[N][N];

    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            a[i][j] = b[i][j] = c[i][j] = 0;
        }
    }

    scanf("%d%d%d", &n, &m, &l);

     for (i = 0; i < n; i++) {
         for (j = 0; j < m; j++) {
             scanf("%d", &a[i][j]);
         }
     }

     for (i = 0; i < m; i++) {
         for (j = 0; j < l; j++) {
             scanf("%d", &b[i][j]);
         }
     }

     for (i = 0; i < n; i++) {
         for (j = 0; j < l; j++) {
             for (k = 0; k < m; k++) {
                 c[i][j] += a[i][k] * b[k][j];
             }
         }
     }
    for (i = 0; i < n; i++) {
        for (j = 0; j < l; j++) {
            printf("%ld", c[i][j]);
            if (j != l-1) printf(" ");
        }
        printf("\n");
    }

     return 0;
}



Measured memory_bytes: 2132
def pushBack(x):
    A.append(x)
def randomAccess(p):
    print(A[p])
def popBack():
    A.pop()
A = []
N = int(input())
for i in range(N):
    S = list(map(int,input().split(" ")))
    if S[0] == 0:
        pushBack(S[1])
    elif S[0] == 2:
        popBack()
    else:
        randomAccess(S[1])



Measured memory_bytes: 13368
N=int(input())
for i in range(0,N):
    a,b,c=map(int,input().split())
    if a**2==b**2+c**2:
        print("YES")
    elif b**2==a**2+c**2:
        print("YES")
    else:
        if c**2==a**2+b**2:
            print("YES")
        else:
            print("NO")
    i+=1


Measured memory_bytes: 5596
#include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstring>
    #include <chrono>
    #include <complex>
    #define endl "\n"
    #define ll long long int
    #define vi vector<int>
    #define vll vector<ll>
    #define vvi vector < vi >
    #define pii pair<int,int>
    #define pll pair<long long, long long>
    #define mod 1000000007
    #define inf 1000000000000000001;
    #define all(c) c.begin(),c.end()
    #define mp(x,y) make_pair(x,y)
    #define mem(a,val) memset(a,val,sizeof(a))
    #define eb emplace_back
    #define f first
    #define s second
    
    using namespace std;
    void max_self(ll& a, ll b) {
        a = max(a, b);
    }
    int main()
    {
        std::ios::sync_with_stdio(false);
        int T=1;
        //cin>>T;
        // cin.ignore(); must be there when using getline(cin, s)
        while(T--)
        {
            ll n;
            cin>>n;
            ll base=1;
            while(base<=n)
            {
                base*=2;
            }
            vector<ll> tree(2*base,0);
            ll a[n];
            ll b[n];
            ll dp[n+1]={0};
            for(ll i=0;i<n;i++)
            {
                cin>>a[i];
            }
            for(ll i=0;i<n;i++)
            {
                cin>>b[i];
            }
            for(ll i=0;i<n;i++)
            {
                ll best=0;
                ll x=a[i]+base;
                while(x>1)
                {
                    if(x%2==1)
                        max_self(best,tree[x-1]);
                    x/=2;
                }
                dp[a[i]]=b[i]+best;
                for(ll h=base+a[i];h>=1;h/=2)
                    max_self(tree[h],dp[a[i]]);
            }
            ll ans=0;
            for(ll i=0;i<=n;i++)
                max_self(ans,dp[i]);
            cout<<ans;
        }
        return 0;
    }


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

int main(){
	int sx, sy, tx, ty, dx, dy;
	cin >> sx >> sy >> tx >> ty;
	dx = tx - sx;
	dy = ty - sy;
	
	rep(i, dy) cout << "U";
	rep(i, dx) cout << "R";
	
	rep(i, dy) cout << "D";
	rep(i, dx) cout << "L";
	
	cout << "L";
	rep(i, dy+1) cout << "U";
	rep(i, dx+1) cout << "R";
	cout << "D";
	
	cout << "R";
	rep(i, dy+1) cout << "D";
	rep(i, dx+1) cout << "L";
	cout << "U" << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	map<int, int> mp;
	rep(i,n){
		int a;
		cin >> a;
		mp[a]++;
		mp[a-1]++;
		mp[a+1]++;
	}
	int ans = 0;
	for(auto p : mp){
		chmax(ans, p.second);
	}
	cout << ans << endl;
	return 0;
}

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

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

  string a, b; cin >> a >> b;
  string ans;
  if(a.size() > b.size()) ans = "GREATER";
  else if(a.size() < b.size()) ans = "LESS";
  else {
    if(a == b) ans = "EQUAL";
    else if(a > b) ans = "GREATER";
    else ans = "LESS";
  }

  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
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

x = int(input())
while True:
    p = prime_factorize(x)
    if len(p) == 1:
        print(p[0])
        break
    x += 1

Measured memory_bytes: 62716
import Debug.Trace

main = do
 [[x,s] ,y] <- map ((map read ) .words). lines <$> getContents
 --[[x,w] ,[y]]<- map (map read.words).lines <$> getContents
 --trace (show $ zipWith (-) ( [last y] ++ init y) y) .print $ x + 1
 --trace (show . (-) x $ maximum.map (\s -> mod s x) $ zipWith (-) y ( [last y] ++ init y) ) .print $ x + 1

 print . (-) x $ maximum.map (\s -> mod s x) $ zipWith (-) y ( [last y] ++ init y) 

Measured memory_bytes: 108540
#include<iostream>
using namespace std;
int A,B,C,X,cnt=0;
int find(int a,int b){
	if(a*500+b*100>X) return 0;
	else if((X-(a*500+b*100))%50==0&&(X-(a*500+b*100))/50<=C) return 1;
	return 0; 
} 
int main(){
	cin>>A>>B>>C>>X;
	for(int i = 0;i <= A;i++)
		for(int k = 0;k <= B;k++)
			if(find(i,k)) cnt++;
	cout<<cnt<<endl;
	return 0;
} 

Measured memory_bytes: 256
// Problem : E - Coprime
// Contest : AtCoder - AtCoder Beginner Contest 177
// URL : https://atcoder.jp/contests/abc177/tasks/abc177_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sort(a) sort(all(a))
#define ff first
#define ss second
#define vi vector<int>
#define pii pair<int, int>
#define vll vector<ll>
#define pll pair<ll,ll>
#define mod (int)1e9+7
#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define repf(i,a,b) for(i=a;i<b;i++)
#define repb(i,a,b) for(i=a;i>=b;i--)
#define N 1000001
vi b(N);

int main()
{
	FAST
    int t=1;
    // cin>>t;
    while(t--)
    {
		int i,n;
		cin>>n;
		vi a(n);
		repf(i,0,n) 
		{
			cin>>a[i];
			b[a[i]]++;
		}
		bool pairwise=true;
		repf(i,2,N)
		{
			int cnt=0;
			for(int j=i;j<N;j+=i) cnt+=b[j];
			
			if(cnt > 1) pairwise=false;
		}
		
		if(pairwise) cout<<"pairwise coprime";
		else
		{
			int g=0;
			repf(i,0,n)
			g=__gcd(g,a[i]);
			if(g==1) cout<<"setwise coprime"; else cout<<"not coprime";
		}
		
    }
    return 0;
} 


Measured memory_bytes: 11076
#include <iostream>
#include <string>
using namespace std;
int main()
{
  int n;
  cin>>n;
  int ac=0,tle=0,re=0,wa=0;
  for(int i=1;i<=n;i++)
  {
    string s;
    cin>>s;
    if(s=="AC")
      ac++;
    else if(s=="TLE")
      tle++;
    else if(s=="RE")
      re++;
    else
      wa++;
  }
  cout<<"AC x "<<ac<<"\n";
  cout<<"WA x "<<wa<<"\n";
  cout<<"TLE x "<<tle<<"\n";
  cout<<"RE x "<<re<<"\n";
  return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#include <math.h>
#include <cmath>
#include <limits>
#include <iostream>
#include <assert.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=10000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	int x,y,cost;
};
int main(){

	int x;
	cin>>x;

	int f=0;
	ll X=x;
	while(f==0){
		int f2=0;
		for(int i=2; i<=sqrt(x); i++){
			if(X%i==0){
				f2=1;
				break;
			}
		}
		if(f2==0){
			cout<<X<<endl;
			return 0;
		}
		X++;
	}

	return 0;

}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,a[100010],dp[100010],k;
int main(){
    cin>>n>>k;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1;i<=n;i++)
        dp[i]=INT_MAX;
    dp[1]=0;
    for (int i=2;i<=n;i++)
    {
        for (int j=i-1;j>=1 && j>=i-k;j--)
        {
            dp[i]=min(dp[i],dp[j]+abs(a[j]-a[i]));
        }
    }
    cout<<dp[n];
}



Measured memory_bytes: 1024
N , K = map(int,input().split())
x = list(map(int,input().split()))
ans = float("inf")
for i in range(N - K + 1):
    #x = x[i : i + K]

    if x[i + K - 1] <= 0:
        tmp_min = abs(x[i])
    elif 0 <= x[i]:
        tmp_min = abs(x[i + K - 1])
    else:
        PassTwice = min(abs(x[i + K - 1]) ,abs(x[i])) * 2
        PassOnce = max(abs(x[i + K - 1]) ,abs(x[i]))
        tmp_min = PassTwice + PassOnce
    if tmp_min < ans:
        ans = tmp_min
print(ans)

Measured memory_bytes: 14568
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int main()
{
    int a,b,c,d,m;
    while(scanf("%d",&m)!=EOF)
    {   a=m/1000;
        b=(m-1000*a)/100;
        c=m%100/10;
        d=m%10;
        if(a+b+c+d==7)printf("%d+%d+%d+%d=7\n",a,b,c,d);
        else if(a+b+c-d==7)printf("%d+%d+%d-%d=7\n",a,b,c,d);
        else if(a+b-c+d==7)printf("%d+%d-%d+%d=7\n",a,b,c,d);
        else if(a-b+c+d==7)printf("%d-%d+%d+%d=7\n",a,b,c,d);
        else if(a+b-c-d==7)printf("%d+%d-%d-%d=7\n",a,b,c,d);
        else if(a-b-c+d==7)printf("%d-%d-%d+%d=7\n",a,b,c,d);
        else if(a-b+c-d==7)printf("%d-%d+%d-%d=7\n",a,b,c,d);
    }
    return 0;
}

Measured memory_bytes: 128
def main():
    n, m, l = map(int, input().split())
    nm_arr = [list(map(int, input().split())) for _ in range(n)]
    ml_arr = [list(map(int, input().split())) for _ in range(m)]

    nml_arr = [[0 for _ in range(l)] for __ in range(n)]

    for j in range(n):
        for i in range(l):
            nml_arr[j][i] = sum([nm_arr[j][x] * ml_arr[x][i] for x in range(m)])
            
    [print(*nml_arr[x]) for x in range(n)]

main()


Measured memory_bytes: 7008
#include<bits/stdc++.h>
#define mod ((int)1e9+7)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define REPN(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long int ll;
const int N = (int)1e5+5;

ll ans[N];
ll power(ll a,ll b) {
    if(b==0) return 1;
    ll c = power(a,b>>1);
    c = (c*c)%mod;
    if(b&1) return (c*a)%mod;
    return c;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,k;
    ll fans = 0;
    cin>>n>>k;
    REPN(i,k,1) {
        ans[i] = power(k/i,n);
        for(int j=i*2;j<=k;j+=i) {
            ans[i] -= ans[j];
            ans[i] %= mod;
        }
        if(ans[i]<0) ans[i] += mod;
        fans += i*ans[i];
        fans %= mod;
    }
    cout<<fans;
}


Measured memory_bytes: 4420
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	private String name;
	private int q;

	//construct a pair object to keep track of each process's quantum, and a bool to check if it is complete
	public Main(String name, int q) {
		this.name = name;
		this.q = q;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getQ() {
		return q;	
	}

	public void setQ(int q) {
		this.q = q;
	}
	

	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		Queue<Main> queue = new LinkedList<Main>();
		
		//scan first line to get number of processes and the universal quantum
		String firstLine = in.nextLine();
		Scanner first = new Scanner(firstLine);
		int items = Integer.parseInt(first.next());
		int quantum = Integer.parseInt(first.next());

		//create queue with data from file
		for(int i = 0; i < items; i++) {
			String line = in.nextLine();
			Scanner linereader = new Scanner(line);
			
			String itemName = linereader.next();
			int itemQ = Integer.parseInt(linereader.next());
			
			queue.add(new Main(itemName, itemQ));
		}
		
		int turnCounter = 0;
		while(!queue.isEmpty()) {
			Main next = queue.remove();
			int qCheck = next.getQ() - quantum;
			
			//if item completes
			if(qCheck <= 0) {
				turnCounter+= next.getQ();
				next.setQ(turnCounter);
				System.out.println(next.getName() + " " + next.getQ());
			}
			//else if it has time remaining
			else {
				turnCounter += quantum;
				next.setQ(qCheck);
				queue.add(next);
			}
		}
	}
}



Measured memory_bytes: 210368
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			double W = sc.nextDouble();
			double H = sc.nextDouble();
			double x = sc.nextDouble();
			double y = sc.nextDouble();
			System.out.println(W * H / 2 + " " + (x * 2 == W && y * 2 == H ? "1" : "0"));
		}
	}
}

Measured memory_bytes: 24532
#include <iostream>

using namespace std;

int main()
{
    int n, a, b, c, d;
    cin>>n;
    a=n%10;
    b=n/10%10;
    c=n/100%10;
    d=n/1000%10;
    if(a==b || b==c || c==d)
    {
        cout<<"Bad";
    }
    else{
        cout<<"Good";
    }

    return 0;
}


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

using namespace std;

typedef long long ll;
const int maxn = 100005;

inline ll read() {
    reg ll s = 0, t = 0; reg char ch = getchar();
    while (!isdigit(ch)) t |= ch == '-', ch = getchar();
    while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return t ? -s : s;
}

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


Measured memory_bytes: 256
n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
m=[0]*2
index=[-1]*2
for i in range(n):
    if m[0]<a[i]:
        m[1]=m[0]
        index[1]=index[0]
        m[0]=a[i]
        index[0]=i
    elif m[1]<=a[i]:
        m[1]=a[i]
        index[1]=i
for i in range(n):
    if i==index[0]:
        print(m[1])
    else:
        print(m[0])

Measured memory_bytes: 69208
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str1 = br.readLine();
		int n = Integer.parseInt(str1);
		
		int a[] = new int[n];
		int b[] = new int[n];
		int c[] = new int[n];
		
		String[] tmpArray = br.readLine().split(" ");
		for(int i = 0; i < n; i++){
			a[i] = Integer.parseInt(tmpArray[i]);
		}
		
		tmpArray = br.readLine().split(" ");
		for(int i = 0; i < n; i++){
			b[i] = Integer.parseInt(tmpArray[i]);
		}
		
		tmpArray = br.readLine().split(" ");
		for(int i = 0; i < n; i++){
			c[i] = Integer.parseInt(tmpArray[i]);
		}
		
		Arrays.sort(a);
		Arrays.sort(b);
		Arrays.sort(c);
		
		long result = 0;
		
		int[] bc = new int[n];
		long[] sumBC = new long[n + 1];
		
		int minC = n - 1;
		for(int i = n - 1; i >= 0; i--){
			if(minC == n - 1 && b[i] >= c[minC]){
				continue;
			}
			for(int j = minC ; j >= 0 ; j--){
				if(b[i] < c[j]){
					minC = j;
				}
				else {
					break;
				}
			}
			bc[i] = n - minC;
			sumBC[i] += bc[i] + sumBC[i + 1];
		}
		
		int minBC = n - 1;
		for(int i = n - 1; i >= 0; i--){
			if(minBC == n - 1 && a[i] >= b[minBC]){
				continue;
			}
			for(int j = minBC ; j >= 0; j--){
				if(a[i] < b[j]){
					minBC = j;
				}
				else {
					break;
				}
			}
			result += sumBC[minBC];
//			System.out.println("add "+sumBC[minBC] + " result "+result);
		}
//		for(int i = 0; i < n; i++){
//			for(int j = n - 1; j >= 0; j--){
//				if(b[i] < c[j]){
//					bc[i]++;
//				}
//				else {
//					break;
//				}
//			}
//		}
		
//		for(int i = 0; i < n; i++){
//			long tmp = 0;
//			for(int j = n - 1; j >= 0; j--){
//				if(a[i] < b[j]){
//					tmp += bc[j];
//				}
//				else {
//					break;
//				}
//			}
//			result += tmp;
//		}
//		//素朴法
//		for(int i = 0; i < n; i++){
//			for(int j = 0; j < n; j++){
//				if(a[i] >= b[j]){
//					continue;
//				}
//				for(int k = n - 1; k >= 0; k--){
//					if(b[j] < c[k]){
//						result++;
//					}
//					else {
//						break;
//					}
//				}
//			}
//		}
		
		System.out.println(result);
	}

}


Measured memory_bytes: 53224
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int x = Integer.parseInt(scan.next());
        scan.close();

        int a = 0;
        int b = 0;

        for (long i = -1000; i <= 1000; i++) {
            for (long j = -1000; j <= 1000; j++) {
                long a5 = i * i * i * i * i;
                long b5 = j * j * j * j * j;
                if (a5 - b5 == x) {
                    a = (int)i;
                    b = (int)j;
                    break;
                }
            }
        }

        System.out.println(a + " " + b);
    }
}


Measured memory_bytes: 38728
# ABC079

import sys
input=sys.stdin.readline

def main():
    inf=10**6
    H,W=map(int,input().split())
    dp=[[inf]*10 for i in range(10)]
    for i in range(10):
        row=list(map(int,input().split()))
        for j in range(10):
            dp[i][j]=row[j]
    
    cnt=[0]*10
    for i in range(H):
        row=list(map(int,input().split()))
        for a in row:
            if a!=-1:
                cnt[a]+=1
                
    for k in range(10):
        for i in range(10):
            for j in range(10):
                if dp[i][k]<inf and dp[k][j]<inf:
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
                    
    ans=0
    for i in range(10):
        ans+=dp[i][1]*cnt[i]
        
    print(ans)
    
                
    
    
if __name__=="__main__":
    main()


Measured memory_bytes: 72636
#include <stdio.h>
#include <limits.h>
 
#define MAX 200000
#define INF INT_MAX
typedef long long ll;
 
void merge(int*, int, int, int);
void mergesort(int*, int, int);
 
ll ans;
 
int n, a[MAX];
 
int main(){
  int i;
 
  scanf("%d" ,&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d" ,a + i);
  }
  mergesort(a,0,n);
  printf("%lld\n" ,ans);
 
  return 0;
}
 
void merge(int a[], int left, int mid, int right){
  int n1 = mid - left, n2 = right - mid;
  int L[n1+1], R[n2+1], i, j, k;
  
  for(i = 0 ; i < n1 ; i++){
    L[i] = a[left + i];
  }
  
  for(i = 0 ; i < n2 ; i++){
    R[i] = a[mid + i];
  }
  
  L[n1] = R[n2] = INF;
  
  for(i = 0, j = 0, k = left ; k < right ; k++){
    if(i < n1 && (j == n2 || L[i] <= R[j])){
      a[k] = L[i++];
    }else{
      ans += (n1 + n2) / 2 - i;
      a[k] = R[j++];
    }
  }
}
  
void mergesort(int a[], int left, int right){
  int mid;
  
  if(left + 1 < right){
    mid = (left + right) / 2;
    mergesort(a, left, mid);
    mergesort(a, mid, right);
    merge(a, left, mid, right);
  }
}


Measured memory_bytes: 3296
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
// #include <numeric>

#define FAST ios_base::sync_with_stdio(false); cin.tie(0)
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
typedef long long int ll;
#define iceil(a,b) (x+y-1)/y
#define min(x,y)(x<y?x:y)
 
using namespace std;
typedef pair<int, int> P;


int main() {
	FAST;

	int N, M, a, b;
	cin >> N >> M;

	P ab[M];

	rep(i,M) {
		cin >> a >> b;
		ab[i] = make_pair(a-1,b-2);
	}

	sort(ab,ab+M);
	int l=0, r=M;
	int ans=1;

	rep(i,M) {
		if (r>=ab[i].first) {
			l=max(l, ab[i].first);
			r=min(r, ab[i].second);
		}
		else {
			l=ab[i].first;
			r=ab[i].second;
			++ans;
		}
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    cout << fixed << setprecision(10);
    int a,b;
    cin >> a >> b;
    if(b%a == 0) cout << a + b << endl;
    else cout << b - a << endl;
    return 0;
}

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

#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void()
#endif

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  int ans = 1, inc = 0;
  for (int i = 0; i < n - 1; i++) {
    int ninc;
    if (a[i] < a[i + 1]) {
      ninc = 1;
    } else if (a[i] > a[i + 1]) {
      ninc = -1;
    } else {
      ninc = 0;
    }
    if (inc != 0 && ninc != 0 && inc != ninc) {
      ans++;
      inc = 0;
    } else if (inc == 0) {
      inc = ninc;
    }
  }
  cout << ans << '\n';
  return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  ll k,a,b;
  cin>>k>>a>>b;
  ll c=a-1;
  if(a+2<=b&&c<=k) {
    if((k-c)%2==1) {
      c+=1;
    }
    cout << 1+c+(b-a)*((k-c)/2) << endl;
  } else {
    cout << 1+k << endl;
  }
  return 0;
}


Measured memory_bytes: 256
// In the name of Allah. Ya ali!
#include<bits/stdc++.h>
#define double long double
#define debug(x)  cerr << #x << " = " << x << endl
typedef long long ll;
const ll MAX_N = 3e5+100;
const ll MOD = 1e9+7;
using namespace std;

int main()
{
    int r,g,b,n;
    cin >> r >> g >> b >> n;
    int ans = 0;
    for(int i = 0;i<=n;++i)
    {
        for(int j = 0;j<=n;++j)
        {
            if (i*r+g*j>n)
                continue;
            if ((n-i*r-g*j)%b==0)
                ans++;
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
	int s,m,h;
	scanf("%d", &s);
	h = s/3600;
	m = (s-h*3600)/60;
	s = (s-h*3600-m*60);
	printf("%d:%d:%d\n",h,m,s);	
	return 0;
}


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

#define each(i, c) for (auto& i : c)
#define mkp(a, b) make_pair(a, b)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9+7;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; }

int main() {
  ll n, m;
  cin >> n >> m;

  vector<ll> a(n), b(n);
  for (ll i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
  }

  vector<ll> c(m), d(m);
  for (ll i = 0; i < m; ++i) {
    cin >> c[i] >> d[i];
  }

  vector<ll> ans(n);
  for (ll i = 0; i < n; ++i) {
    ll mx = 1e18;
    for (ll j = 0; j < m; ++j) {
      ll x = abs(a[i]-c[j]) + abs(b[i]-d[j]);
      if (mx > x) {
        mx = x;
        ans[i] = j+1;
      }
    }
  }

  each (i, ans) {
    cout << i << endl;
  }

  return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
    	
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int N = sc.nextInt();
		int M = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();

		ArrayList<Integer> listA = new ArrayList<Integer>();
		for(int i = 1;i <= N;i++){
			int tmp = sc.nextInt();
			listA.add(tmp);
		}
		listA.add(X);

		ArrayList<Integer> listB = new ArrayList<Integer>();
		for(int i = 1;i <= M;i++){
			int tmp = sc.nextInt();
			listB.add(tmp);
		}
		listB.add(Y);
		
//		Collections.sort(listA);
//		Collections.sort(listB);
		int max = Collections.max(listA);
		int min = Collections.min(listB);

		//最大の数
		if(max<min){
			System.out.println("No War");
		}else{
			System.out.println("War");
		}

   		sc.close();
        return ;

    }
    
}



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

int main() {
  cin.tie(0);
  std::ios::sync_with_stdio(false);
  string w;
  cin>>w;
  int alpha[26];
  memset(alpha,0,sizeof(alpha));
  for (int i=0; i<w.length(); i++) {
    alpha[w[i]-'a']++;
  }
  bool f=true;
  for (int i=0; i<26; i++) {
    if (alpha[i]%2!=0) {
      f=false;
    }
  }
  cout<<(f?"Yes":"No")<<endl;
  return 0;
}


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

using namespace std;

const int mod = 998244353;

long long dp[100000][2];
map <pair<int, int>, int> mp;

int count(int x, int y, int d) {
    int z1, z2;
    
    if (mp.count(make_pair(x, y))) {
        z1 = mp[make_pair(x, y)];
    } else {
        z1 = -1;
    }
    
    if (mp.count(make_pair(y, x))) {
        z2 = mp[make_pair(y, x)];
    } else {
        z2 = -1;
    }
    
    if (d == 0) {
        if (z1 == -1 && z2 == -1) {
            return 2;
        } else if (z1 == -1 || z2 == -1 || z1 == z2) {
            return 1;
        } else {
            return 0;
        }
    } else {
        if (z1 == -1 && z2 == -1) {
            return 2;
        } else if (z1 == -1 || z2 == -1 || z1 != z2) {
            return 1;
        } else {
            return 0;
        }
    }
}

long long pow_mod(long long x, long long y) {
    long long ans = 1;
    
    while (y > 0) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    
    return ans;
}

int main() {
    int n, m, i;
    long long p, ans;
    
    scanf("%d %d", &n, &m);
    
    p = (long long)(n - 3) * (n - 2) / 2;
    
    for (i = 0; i < m; i++) {
        int a, b, c;
        
        scanf("%d %d %d", &a, &b, &c);
        
        a--;
        b--;
        
        if (b < a - 2 || b > a + 2) {
            if (mp.count(make_pair(a, b))) {
                if (mp[make_pair(a, b)] != c) {
                    puts("0");
                    
                    return 0;
                }
            } else {
                mp[make_pair(a, b)] = mp[make_pair(b, a)] = c;
                
                p--;
            }
        } else {
            mp[make_pair(a, b)] = c;
        }
    }
    
    for (i = 0; i < n; i++) {
        if (!mp.count(make_pair(i, i)) || mp[make_pair(i, i)] == 0) {
            if (i == 0) {
                dp[0][0] = 1;
            } else if (i == 1) {
                dp[1][0] = dp[0][0] * count(0, 1, 0) + dp[0][1] * count(0, 1, 1);
            } else {
                dp[i][0] += dp[i - 1][0] * count(i - 1, i, 0) * count(i - 2, i, 0);
                dp[i][0] += dp[i - 1][1] * count(i - 1, i, 1) * count(i - 2, i, 1);
                dp[i][0] %= mod;
                
            }
        }
        
        if (!mp.count(make_pair(i, i)) || mp[make_pair(i, i)] == 1) {
            if (i == 0) {
                dp[0][1] = 1;
            } else if (i == 1) {
                dp[1][1] = dp[0][0] * count(0, 1, 1) + dp[0][1] * count(0, 1, 0);
            } else {
                dp[i][1] += dp[i - 1][0] * count(i - 1, i, 1) * count(i - 2, i, 0);
                dp[i][1] += dp[i - 1][1] * count(i - 1, i, 0) * count(i - 2, i, 1);
                dp[i][1] %= mod;
            }
        }
    }
    
    ans = (dp[n - 1][0] + dp[n - 1][1]) % mod * pow_mod(2, p) % mod;
    
    printf("%lld\n", ans);
    
    return 0;
}


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

#include<string>
#include<vector>
std::string minus2(long long n, int i = 40, bool padding = false) {
  static std::vector<long long> power = {1}, sum = {1, 2};
  while(int(power.size()) <= i) power.emplace_back(power.back() << 1);
  while(int(sum.size()) < i) sum.emplace_back(sum[sum.size() - 2] + power[sum.size()]);
  if(i < 0) return "";
  if(n == 0) return (padding ? std::string(i + 1, '0') : "0");
  if(i & 1) {
    if(i) if(sum[i - 1] < n + power[i]) return (padding ? "0" : "") + minus2(n, i - 1, padding);
    return "1" + minus2(n + power[i], i - 1, true);
  } else {
    if(i) if(n - power[i] < -sum[i - 1]) return (padding ? "0" : "") + minus2(n, i - 1, padding);
    return "1" + minus2(n - power[i], i - 1, true);
  }
}

#include<bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  cout << minus2(N) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vi a(n);
  REP(i,n) cin >> a[i];
  vi dp;
  dp.eb(a[0]);
  FOR(i,1,n){
    auto itr = lower_bound(ALL(dp),a[i]);
    if(itr!=dp.end()) *itr = a[i];
    else dp.eb(a[i]);
  }
  cout << dp.size() << endl;
}



Measured memory_bytes: 3688
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
using namespace std;
typedef long long ll;
const double PI=acos(-1);
typedef pair<int,int>P;
const int mod =1e9+7;

bool IsPrime(ll n)
{
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)return false;
    }
        return n!=1;

}
int main()
{
    ll n;
    cin>>n;
    while(1)
    {
        if(IsPrime(n))
        {
            cout<<n<<endl;
            return 0;
        }
        n++;
    }
}


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

int main() {
  int n; cin>>n;
  for(int i=1;i<=n;i++) {
    if(i*108/100==n) {
      cout<<i<<endl;
      return 0;
    }
  }
  cout<<":("<<endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<string>
#include <iomanip> 
#include <stack> 
#include <cmath> 

#define maxn 400010
#define LL long long
#define inf 10000000000
#define mod 1000000007
#define pi 3.14159265359
using namespace std;
int dx[24] = { 1,0,-1,0 ,2,0,-2,0 ,-1,-1,-2,-2 ,1,1,2,2    ,-1,-1,-2,-2 ,1,1,2,2 };
int dy[24] = { 0,1,0,-1 ,0,2,0,-2 ,-1,-2,-1,-2 ,-1,-2,-1,-2,1,2,1,2     ,1,2,1,2  };


LL n, m, k;
LL arr[maxn];
LL arr2[maxn];
//int visit[maxn];
//int cache[maxn];
int c[maxn];
int g[maxn];
//int dfsnum = 0;
//vector<vector<int>>rvi;
//vector<vector<int>>scc;
//vector<pair<int, int>>ett;
//stack<int>st;
//bool flg = 1;
//LL s, d;
//
int findp(int a) {
	if (c[a]==a)return a;
	return c[a] = findp(c[a]);
}
void unionp(int a, int b) {
	a = findp(a);
	b = findp(b);

	if (a != b) {
		if (g[a] > g[b]) {
			g[a] += g[b];
			g[b] = 0;
			c[b] = a;
		}
		else {
			g[b] += g[a];
			g[a] = 0;
			c[a] = b;
		}
		
	}

}
//LL power(LL x, LL y) {
//	LL ret = 1;
//	while (y > 0) {
//		if (y % 2) {
//			ret *= x;
//			ret %= mod;
//		}
//		x *= x;
//		x %= mod;
//		y /= 2;
//	}
//	return ret;
//}
//void dfs2(int v) {
//	cache[v] = 1;
//	scc.back().push_back(v);
//	for (int nv : rvi[v]) {
//		if (cache[nv])continue;
//		dfs2(nv);
//	}
//
//}
//LL fac(LL n) {
//	if (n == 1) return 1;        
//	return (n * fac(n - 1) - power(2,n-1) )%mod;
//}
//int fac2(LL n) {
//	LL res, i;
//	if (n == 1)return n;
//	res = n;
//	for (int i = n - 1; i > 0; --i) {
//		res *= i;
//		res %= mod;
//	}
//	return res;
//}

LL gcd(LL a, LL b) {
	while (b != 0) {
		LL r = a % b;
		a = b;
		b = r;
	}
	return a;
}


int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	//int t;   cin >> t; cin.ignore();
	int t = 1;
	for (int test_case = 0; test_case < t; ++test_case) {
		int flg = 0;
		LL ans1 = 0, ans2 = 0;
		string ans[2] = { "No","Yes" };
		string s1, s2 = "";
		cin >> n >> m;
		for (int i = 1; i <= n; ++i) {
			c[i] = i;
			g[i] = 1;
		}
		for (int i = 0; i < m; ++i) {
			int a, b;
			cin >> a >> b;
			unionp(a, b);
		}
		for (int i = 1; i <= n; ++i) {
			ans1 = max(ans1, (LL)g[i]);
		}
		cout << ans1;
		cout << '\n';

	}
	return 0;
}


Measured memory_bytes: 4708
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main() {
    // AtCoder
    // template
    ll n, k;
    cin >> k >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    ll fst = a[0];

    rep(i, n - 1) { a[i] = a[i + 1] - a[i]; }
    a[a.size() - 1] = fst + k - a[a.size() - 1];

    ll ma = -1;
    rep(i, n) ma = max(ma, a[i]);
    cout << k - ma << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
typedef long long ll;
typedef long double ld;
const ll MOD = 998244353;
void add(ll& x, ll y) {
	x += y;
	if (x >= MOD) x -= MOD;
}
void sub(ll& x, ll y) {
	x -= y;
	if (x < 0) x += MOD;
}
int main() {
	int n;
	scanf("%d", &n);
	vector<ll> ndp(90001), dp(90001);
	vector<ll> ndp2(90001), dp2(90001);
	dp[0] = dp2[0] = 1;
	ll sum = 0;
	for (int i = 0; i < n; ++i) {
		int a; 
		scanf("%d", &a);
		sum += a;
		fill(ndp.begin(), ndp.end(), 0);
		fill(ndp2.begin(), ndp2.end(), 0);
		for (int s = 0; s <= i * 300; ++s) {
			add(ndp[s], dp[s]);
			add(ndp[s], dp[s]);
			add(ndp[s + a], dp[s]);
			add(ndp2[s], dp2[s]);
			add(ndp2[s + a], dp2[s]);
		}
//		for (int s = 0; s <= 10; ++s) db2(s, ndp[s]);
		swap(dp, ndp);
		swap(dp2, ndp2);
	}
	ll ans = 1;
	for (int i = 1; i <= n; ++i) ans = ans * 3 % MOD;
	for (int i = (sum + 1) / 2; i <= sum; ++i) {
//		db2(i, dp[i]);
		sub(ans, dp[i] * 3 % MOD);
	}
	if (sum % 2 == 0) {
		add(ans, dp2[sum / 2] * 3 % MOD);
	}
	printf("%lld\n", ans);
}


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

using namespace std;

typedef long long ll;

const int MX = 603;
const ll MOD = 1000000007;

template <typename T> void cmin(T &x, const T &y)
{
	if(y < x) x = y;
}

template <typename T> void cmax(T &x, const T &y)
{
	if(y > x) x = y;
}

template <typename T> void read(T &x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

int n, k;
ll f[MX][MX], way[MX];
int mnid[MX][MX], mxid[MX][MX];
int sum[MX];

int main()
{
	read(n), read(k);
	memset(mnid, 0x3f, sizeof(mnid));
	memset(mxid, 0x00, sizeof(mxid));
	for(int i=1; i<=k; i++)
	{
		int a, b;
		read(a), read(b);
		mnid[a][a] = mxid[a][a] = b;
		mnid[b][b] = mxid[b][b] = a;
		sum[a]++, sum[b]++;
	}
	for(int i=1; i<=n*2; i++) sum[i] += sum[i-1];
	for(int i=1; i<=n*2; i++)
		for(int j=i+1; j<=n*2; j++)
		{
			mnid[i][j] = min(mnid[i][j-1], mnid[j][j]);
			mxid[i][j] = max(mxid[i][j-1], mxid[j][j]);
		}
	way[0] = 1;
	for(int i=2; i<=n*2; i++) way[i] = way[i-2] * (i-1) % MOD;
	ll ans = 0;
	for(int i=1; i<=n*2; i++)
	{
		for(int l=1; l+i-1<=n*2; l++)
		{
			int r = l+i-1;
			if(mnid[l][r]<l || mxid[l][r]>r) continue;
			int num = (r-l+1) - (sum[r]-sum[l-1]);
			if(num & 1) continue;
			f[l][r] = way[num];
			for(int j=l; j<r; j++)
			{
				int rem = (r-j) - (sum[r]-sum[j]);
				if(rem&1) continue;
				else if(mnid[j+1][r]<=j || mxid[j+1][r]>r) continue;
				else f[l][r] = (f[l][r] - f[l][j]*way[rem] + MOD*MOD) % MOD;
			}
			ans = (ans + f[l][r]*way[n*2-k*2-num]) % MOD;
			//cout<<l<<" "<<r<<" "<<f[l][r]<<" "<<way[n*2-k*2-num]<<endl;
		}
	}
	printf("%lld\n", ans);
	//printf("%lld\n", f[1][n*2]);
	return 0;
}


Measured memory_bytes: 5888