akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a)), (a).end())
#define reverse(a)      reverse(all(a))
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }
#define pb              push_back
#define fst             first
#define int             long long
#define INF             __LONG_LONG_MAX__

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

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  for (int i = 1; i < 10; i++) {
    for (int j = 1; j < 10; j++) {
      cout << i << "x" << j << "=" << i*j << endl;
    }
  }
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}



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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 2e5+23;
char s[N];

void solve() {
  int n; scanf("%d", &n);
  int w = 0, r = 0;
  for (int i = 0; i < n; ++i) {
    scanf(" %c", s+i);
    if (s[i] == 'R') ++r;
    else ++w;
  }
  int ans = min(w, r);
  for (int i = 0, R = r; i < R; ++i) {
    if (s[i] == 'R') --r;
  }
  printf("%d", min(ans, r));
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


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


using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define reps(i,n) for (int i = 1; i <= (int)(n); ++i)
#define repd(i,n) for (int i = (int)(n - 1); i >= 0; --i)
#define repds(i,n) for (int i = (int)(n); i > 0; --i)
#define loop(i,x,n) for (int i = (int)(x); i < (n); ++i)
#define loops(i,x,n) for (int i = (int)(x); i <= (n); ++i)
#define loopd(i,x,n) for (int i = (int)(x); i > (n); --i)
#define loopds(i,x,n) for (int i = (int)(x); i >= (n); --i)
#define itrep(i,s) for (auto i = begin(s); i != end(s); ++i)
#define itrepd(i,s) for (auto i = rbegin(s); i != rend(s); ++i)
#define all(f,x,...) [&](decltype(x)& whole) { return (f)(begin(whole), end(whole), ##__VA_ARGS__); }(x)
using ll = long long;
using ld = long double;
constexpr ll inf = static_cast<ll>(1e18);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e18;
ll mod = static_cast<ll>(1e9 + 7);
std::ostream& endn(std::ostream& os) { return os.put(os.widen('\n')); }
template<class T> constexpr int sz(const T& a) { return (int)a.size(); }
template<class T> constexpr T pow2(const T a) { return a * a; }
template<class T, class ... Args> constexpr T mins(T& a, Args... args) { return a = min<T>({ a, args... }); }
template<class T, class... Args> constexpr T maxs(T& a, Args... args) { return a = max<T>({ a,args... }); }
template<class a, int N, class T>
void fillArray(a(&array)[N], const T& val) { std::fill((T*)array, (T*)(array + N), val); }

ll h, w, hh, ww;
void solve() {
    cin >> h >> w >> hh >> ww;

    auto tmp1 = h / hh;
    auto tmp2 = w / ww;
    auto l = -((h * w - tmp1 * tmp2) / (tmp1 * tmp2)) + 1;
    auto r = -hh * ww;
    if (h % hh == 0 && w % ww == 0) {
        cout << "No" << endn;
        return;
    }

    cout << "Yes" << endn;
    if (w % ww != 0) {
        rep(i, h) {
            rep(j, w) {
                if (j % ww != ww - 1) cout << 999999999 / (ww - 1) << " ";
                else cout << -(999999999 / (ww - 1)) * (ww - 1) - 1 << " ";
            }
            cout << endn;
        }
    }
    else {
        rep(i, h) {
            rep(j, w) {
                if (i % hh != hh - 1) cout << 999999999 / (hh - 1) << " ";
                else cout << -(999999999 / (hh - 1)) * (hh - 1) - 1 << " ";
            }
            cout << endn;
        }
    }
}

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


Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char b;cin>>b;
    if (b=='A') {
        cout<<'T'<<endl;
    }
    else if(b=='T')
    {
        cout<<'A'<<endl;
    }
    else if(b=='G')
    {
        cout<<'C'<<endl;
    }
    else if(b=='C')
    {
        cout<<'G'<<endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int a[55][55];
char ss[55];
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%s", ss);
        int len = strlen(ss);
        for(int j = 0; j < len; ++j){
            a[i][ss[j]-'a'] ++;
        }
    }
    string str = "";
    for(int i = 0; i < 26; ++i){
        //printf("%c\n", i+'a');
        int mi = 55;
        for(int j = 0; j < n; ++j) mi = min(a[j][i], mi);
        while(mi--) str += (i+'a');
    }
    cout<<str<<endl;
    return 0;
}


Measured memory_bytes: 256
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rrep(i,n) for(ll i##_len=(n) ,i=i##_len-1;i>=0;--i)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define printd(val) std::cout<< #val" = " <<val<<"\n";
#define lim 1000000007ll
#include<bits/stdc++.h>
using ll = long long;
using pii = std::pair<ll,ll>;
using namespace std;
template<class T>T chmin(T& a,T b){if(a>b){a^=b;b^=a;a^=b;return 1;}return 0;}
template<class T>T chmax(T& b,T a){if(a>b){a^=b;b^=a;a^=b;return 1;}return 0;}
template <class T> T gcd(T a, T b){if (a < b) {a ^= b;b ^= a;a ^= b;} return b ? gcd(b, a % b) : a;}
template <class T> T lcm(T a, T b){return a * b / gcd(a, b);}

template<class T> vector<pair<T,T>> duplicator(const vector<T>& input){
    vector<pair<T,T>> out(input.size()-1);
    rep(i,input.size()-1){
        out[i].first =input[i  ];
        out[i].second=input[i+1];
    }
    return(out);
}
vector<char> String_to_vector_char(const string& input){
    vector<char> out(input.size());
    rep(i,input.size()){
        out[i]=input[i];
    }
    return out;
}
inline bool operator<(const pii &lhs,const pii &rhs){
    return(lhs.first<rhs.first);
}

int n,m;
vector<int> L,R;
void input(){
    cin>>n>>m;
    int l,r;
    rep(i,m){
        cin>>l>>r;
        L.push_back(l);
        R.push_back(r);
    }
}
void src(){
    int count=0;
    cout<<max(*min_element(R.begin(),R.end())-*max_element(L.begin(),L.end())+1,0);
}

int main(int argc,char* argv[]){
    ios::sync_with_stdio(false);
    //ifstream in( argv[1] ); cin.rdbuf(in.rdbuf());
    input();
    src();    
    return 0;
}

Measured memory_bytes: 1276
/*by freesteed*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get_be(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
//get_be biger & equal
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const ll oo=1e9+10;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll n,ans;
void solve(){
	cin>>n;
	VI a(n);
	rep(i,0,n)cin>>a[i];
	sort(all(a));
	//rep(i,0,n)cout<<a[i]<<" ";cout<<endl; 
	rep(i,0,n-2){
		rep(j,i+1,n-1){
			int t = (lower_bound(a.begin()+j+1,a.end(),a[i]+a[j])-(a.begin()+j+1));
			//cout<<a[i]<<" "<<a[j]<<" a[i] + a[j] == "<<a[i]+a[j]<<" t== "<<t<<endl;
			ans+=t; 
		}
	}
	cout<<ans;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FIN         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ii          pair<int,int>
#define F           first
#define S           second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define rall(x)     (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a)   for(int i = a; i >= 0; i--)
#define fori(i,m)   for(auto i = m.begin(); i != m.end(); i++) 
#define w(t)        while(t--)
#define sz(s)       int(s.size())
#define cls(a,car)  memset(a,car,sizeof (a))
#define db(x)       cerr << #x << " is " << x << '\n'
#define FL          freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);
#define EjecuteTime cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"
#define angle(x)    double(x * acos(-1) / 180.0)
using namespace std;
typedef long long   ll;
typedef vector<int> vi;
typedef vector<ii>  vii;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const double E = 1e-9;
//int dx[] = {1, 0}, dy[] = {0, 1};
//int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
//int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy[] = {0 ,1, 1, 1, 0, -1, -1, -1};
// fflush(stdout)
// cout << flush
// a + b = a ^ b + 2 * (a & b)
int v[N][3];
int dp[N][3];
int n;
int f(int i, int last){
    if(i == n)return 0;
    int &ans = dp[i][last];
    if(ans == -1){
        ans = 0;
        if(last == 0){
            ans = max(ans, f(i + 1, 1) + v[i][1]);
            ans = max(ans, f(i + 1, 2) + v[i][2]);
        }
        if(last == 1){
            ans = max(ans, f(i + 1, 0) + v[i][0]);
            ans = max(ans, f(i + 1, 2) + v[i][2]);
        }
        if(last == 2){
            ans = max(ans, f(i + 1, 0) + v[i][0]);
            ans = max(ans, f(i + 1, 1) + v[i][1]);
        }
        ans = max(ans, f(i + 1, last));
    }return ans;
}
int main(){
    //FL;
    FIN;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> v[i][0] >> v[i][1] >> v[i][2];
    cls(dp, -1);
    cout << max({f(0, 0), f(0, 1), f(0, 2)}) << '\n';
    EjecuteTime;
    return 0;
}       

Measured memory_bytes: 13916
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <random>
#include <utility>
#include <cmath>
#include <set>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <algorithm>
#include <vector>
 
using namespace std;
typedef long long ll;
 
 
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする
 
vector<int> G[100005];
std::vector<P> tree[100010];
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
 
ll i,j,k;
ll a[200],b[200],c=0;
ll n,m,q,r;
ll ans;
 
int main(){
 
	cin>>q;
 
	for(i=0;i<q;i++){
		cin>>a[i]>>b[i];
	}
	for(i=0;i<q;i++){
		if(a[i]>b[i])swap(a[i],b[i]);
		r=sqrt((b[i]*a[i])*1.0);
		if(r*r==a[i]*b[i])r--;
		if(r*r+r>=a[i]*b[i]){
			ans=2*r-2;
		}else{
			ans=2*r-1;
		}
		if(a[i]==b[i])ans=2*a[i]-2;
		if(a[i]==b[i]-1)ans=2*a[i]-2;
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
int main(){
	int x, y;
	cin >> x >> y;
	if (y%2!=0){
		cout << "No" << endl;
		return 0;
	}
	if (x*2>y||x*4<y){
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	return 0;
}

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

int main()
{
	int A,B,K,j=0,i;
	cin >> A>>B >>K;
	for(i=min(A,B);i>0;i--){
		if((A%i==0)&&(B%i==0)){
			j++;
			if(j==K){
				break;
			}
		}
	}
	cout << i;
	return 0;
}


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

int main() {
	ll n;
	cin>>n;
	ll ch[100010];
	for(ll i=0;i<n;i++){
		cin>>ch[i];
	}
	ll ans=0;ll cnt=0;
	ll now=ch[0];
	for(ll i=1;i<n;i++){
		if(ch[i]<=now){
			cnt++;
			now=ch[i];
		}
		else{
			now=ch[i];
			ans=max(ans,cnt);
			cnt=0;
		}
	}
	cout << max(ans,cnt);
	// your code goes here
	return 0;
}

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(in.readLine());
    String[] str = in.readLine().split(" ");
    int count = 0;
    int[] p = new int[n];
    for(int i=0; i<n; i++) {
      p[i] = Integer.parseInt(str[i]);
    }
    
    for(int i=1; i<n-1; i++) {
      if(p[i-1]<p[i] && p[i]<p[i+1] || p[i-1]>p[i] && p[i]>p[i+1])
        count+=1;
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 21204
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;


const ll MOD = 1e9+7;

signed main(){
    ll a,b;
    cin >> a >> b;
    if(a*b % 2) cout << "Odd" << endl;
    else cout << "Even" << endl;
    return 0;
}


Measured memory_bytes: 3644
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();

		int c = 1;
		if(b < 10) {
			c = 10*a +b;
		}else if(b < 100) {
			c = 100*a +b;
		}else {
			c = 1000*a +b;
		}
		int hantei = 0;
		for(int i=1; i<317; i++) {
			if(i*i == c) {
				hantei += 1;
			}
		}
		if(hantei > 0) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 23764
import sys
input=sys.stdin.readline

def main():
    N,A,B=map(int,input().split())
    if A>B or (N==1 and A!=B):
        print(0)
        return
    if N==1:
        print(1)
    else:
        print((N-1)*B+A - ((N-1)*A+B) +1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
/**
*   @Author : MeGaCrazy
*   @InitTime : Wed Jan 02 22:33:27 2019
*   @Idea :
*
*
*
*
*
*  Happy Solving :)
**/
#include <bits/stdc++.h>
using namespace std;


int a[55][26];
int main(){
#ifndef ONLINE_JUDGE
   //freopen("in","r",stdin);
   //freopen("out","w",stdout);
#endif
   int n;
   cin>>n;
   string s;
   for(int i=0;i<n;i++){
        cin>>s;
        for(char c:s){
        	a[i][c-'a']++;
        }
   }
   string ans="";
   for(int i=0;i<26;i++){
         int m=1e9;
   	 for(int j=0;j<n;j++){
   	        m=min(m,a[j][i]);
   	 }

   	 ans+=string(m,(char)(i+'a'));
   }
   cout<<ans<<endl;
   



}

Measured memory_bytes: 256
a = input()
q, mod =divmod(int(a), 100)
if q == 0 :
  if mod < 13 and mod != 0:
    print("YYMM")
  else : print("NA")
elif mod == 0 :
  if q < 13 and q != 0:
    print("MMYY")
  else : print("NA")
elif q < 13 :
  if mod < 13 :
    print("AMBIGUOUS")
  else : print("MMYY")
else:
  if mod < 13 :
    print("YYMM")
  else : print("NA")

Measured memory_bytes: 3064
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef uint64_t ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;

const ll MOD = 1000000007;
//const ll MOD = 998244353;
struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

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

    int n; cin >> n;

    vll x(n);
    REP(i, n) cin >> x[i];

    mint ans = 0;

    mint fact;
    fact = 1;
    FOR(i, 1, n) {
        fact *= i;
    }

    mint cur = 0;
    REP(i, n - 1) {
        cur += fact / (i + 1);

        ans += cur * (x[i + 1] - x[i]);
    }

    print(ans);

}


Measured memory_bytes: 3964
N=int(input())
A=list(map(int,input().split()))
from collections import deque
list=[0 for i in range(10**6+1)]
for i in A:
  list[i]+=1

for i in range(len(list)):
  if list[i]!=0:
    for j in range(2*i,10**6+1,i):
      list[j]=0
ans=0
for i in range(len(list)):
  if list[i]==1:
    ans+=1
print(ans)


Measured memory_bytes: 32240
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean ok = true;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            if (a % 2 == 0) {
                if (a % 3 != 0 && a % 5 != 0) ok = false;
            }
        }
        if (ok) System.out.println("APPROVED");
        else System.out.println("DENIED");
    }
}

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

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;
constexpr int N_MAX = 200000;
constexpr int INF = 1<<30;

vector<int> graph[N_MAX];
vector<vector<int>> memo(N_MAX, vector<int>(3, INF));

int bfs(int s, int t) {
    queue<Pii> que;
    que.emplace(s, 0);
    memo[s][0] = 0;
    int node, d;
    while(!que.empty() && memo[t][0] == INF) {
        tie(node, d) = que.front(); que.pop();
        for(int child: graph[node]) {
            if(memo[child][(d+1)%3] != INF) continue;
            que.emplace(child, d+1);
            memo[child][(d+1)%3] = (d+1)/3;
        }
    }
    return (memo[t][0] == INF)?-1:memo[t][0];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m, u, v, s, t;
    cin >> n >> m;
    for(int i=0;i<m;++i){
        cin >> u >> v;
        --u; --v;
        graph[u].push_back(v);
    }

    cin >> s >> t;
    --s; --t;
    cout << bfs(s, t) << endl;

}


Measured memory_bytes: 19072
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>v;
int main()
{
    double n,a;
    double sum = 0;
    double inverseSum;
    cin >> n;
    while(n--)
    {
        cin >> a;
        sum = sum + (1/a);
    }
    inverseSum = 1 / sum;
    cout << inverseSum;

}


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

int main() {
  int a,b;
  int ans = 0;

  cin >> a >> b;

  //数字によって場合分け
  if (a + b == 3) {
    ans = 3;
  }
  else if (a + b == 4) {
    ans = 2;
  }
  else if (a + b == 5) {
    ans = 1;
  }

  cout << ans << endl;
}

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

const int MAX_H = 11000;
int dp[MAX_H];

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

    vector<int> a(n),b(n);
    rep(i,n) cin >> a[i] >> b[i];

    for (int h = 0; h < MAX_H; ++h) dp[h] = 1000000000; // INF
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        for (int h = a[i]; h <= MAX_H; ++h) {
            dp[h] = min(dp[h], dp[h - a[i]] + b[i]);
        }
    }
    int ans=dp[H];
    for(int i=H;i<=10000;++i) ans=min(ans,dp[i]);
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<> a(n); for (int i = 0; i < n; i++) cin >> a[i];
  V<> b(30);
  for (int i = 0; i < n; i++) b[__builtin_ctz(a[i])] = 1;
  int xora = 0; for (int i = 0; i < n; i++) xora ^= a[i];
  int res = 0;
  for (int i = 30 - 1; i >= 0; i--) {
    if (xora & 1 << i) {
      if (b[i]) {
        xora ^= (1 << i) - 1;
        res++;
      } else {
        res = -1;
        break;
      }
    }
  }
  cout << res << '\n';
}

Measured memory_bytes: 640
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String[] array = new String[n];
    array = sc.next().split("");

    int count = 1;
    int i = 0;

    if(n==1){
      System.out.println("1");
    }else{
      while(true){
        if(!(array[i].equals(array[i+1]))){
          count +=1;
        }
        if(i==n-2){break;}
        i += 1;
      }
      System.out.println(count);
    }



  }
}

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

int main(){
    int n;
    vector<int> d(60);
    int i,j;
    cin >> n ;
    for(i=0; i<d.size(); i++){
        d.at(i)=0;
    }
    for(i=0; i<n; i++){
        cin >> d.at(i);
    }
    int ans=0;
    for(i=0; i<d.size(); i++){
        for(j=i+1; j<d.size(); j++){
            ans=ans+d.at(i)*d.at(j);
        }
    }

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

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

typedef long long ll;

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll n,x;
    while(cin >> n >> x) {
        cout << 3*(n - gcd(n,x));
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        long r = nl(), d = nl(), a = nl();
        for(int i = 0; i< 10; i++){
            long x = r*a-d;
            pn(x);
            a = x;
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    long mod = (long)998244353, IINF = (long)1e18;
    final int INF = (int)1e9, MX = (int)2e5+5;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-8;
    static boolean multipleTC = false, memory = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Measured memory_bytes: 25044
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;

int main(){
  int N,M;

  cin >> N;

  int T[N];

  REP(i,N){
    cin >> T[i];
  }

  cin >> M;

  int P[M];//問題番号
  int X[M];//それぞれのかかる時間

  REP(i,M){
    cin >> P[i] >> X[i];
  }

  int sum_time = 0;
  int num,hozon,ans;

  REP(i,N){
    sum_time += T[i];
  }

  REP(j,M){
    hozon = 0;
    num = P[j]-1;
    hozon = X[j] - T[num];
    ans = sum_time + hozon;
    cout << ans << endl;
  }

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,f,e) for(int (i)=(f); (i)<(e); (i)++)
#define repr(i,e,f) for(int (i)=(e-1); (i)>=(f); (i)--)

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

// vector<tuple<long,long>> items; // (value, weight)
// auto item = items[i];
// long v = get<0>(item);
// long w = get<1>(item);
// long v, w;
//   for( int i = 0; i < N; i++ ){
//     cin >> v >> w;
//     items.push_back( make_tuple(v, w) ); // item : (value, weight)
//   }

string grid[1001][1001];
ll memo[1001][1001];
int H,W;

ll rec(int i, int j){
    if(memo[i][j]!=-1) return memo[i][j];
    ll ans = 0;
    if(grid[i+1][j]=="." && i+1<H) ans += rec(i+1, j);
    if(grid[i][j+1]=="." && j+1<W) ans += rec(i, j+1);
    if(i==H-1 && j==W-1) ans += 1;
    return memo[i][j] = ans % MOD;
}

int main(){
    cin >> H >> W;
    char c;
    rep(i,0,H){
        rep(j,0,W){
            cin >> c;
            grid[i][j] = c;
            memo[i][j] = -1;
        }
    }

    rec(0,0);

    // rep(i,0,H){
    //     cout << endl;
    //     rep(j,0,W){
    //         cout << memo[i][j] << " ";
    //     }
    // }

    if(memo[0][0]==-1) cout << 0;
    else cout << memo[0][0];
}


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

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= 9;i++){
        for(int j = 1;j <= 9;j++){
            if(i*j == n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3608
//#pragma GCC target("avx2")
#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << "\n";
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int n;
    cin >> n;

    print(!n);
    
}


Measured memory_bytes: 3592
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int main(void)
{
    int n;
    cin >> n;
    vector<double> a(n);
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
    }
    double prod = 1.0;

    for(int i = 0;i < n;i++)
    {
        prod *= a[i];
    }

    double den=0;
    
    for(int i = 0;i < n;i++)
    {
        den += prod/a[i];
    }

    double num=prod;

    printf("%lf\n",num/den);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) b.rbegin(),v.rend()
typedef long long ll;
//isPrime
//modpow modinv
//getDigit
using Gragh = vector<vector<int>>;
int main() {
  cout << fixed << setprecision(10);
  int n,x,y;
  cin >> n >> x >> y;
  Gragh G(n);
  rep(i,n-1){
    int a = i;
    int b = i+1;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  x--; y--;
  G[x].push_back(y);
  G[y].push_back(x);
  vector<int> ans(n,0);
  queue<int> que;
  rep(i,n){
    que.push(i);
    vector<int> dist(n,-1);
    dist[i]=0;
    while(!que.empty()){
      int x = que.front(); que.pop();
      for(auto nx:G[x]){
        if(dist[nx]!=-1) continue;
        dist[nx]=dist[x]+1;
        que.push(nx);
      }
    }
    rep(j,n){
      ans[dist[j]]++;
    }
  }
  for(int i=1; i<n; i++){
    cout << ans[i]/2 << endl;
  }
}

Measured memory_bytes: 384
import java.io.IOException;
import java.util.Scanner;


public class Main{
	public static void main(String args[]) throws IOException{
		Scanner bf = new Scanner(System.in);
		int tyou = 0;
		int hishi = 0;
		while(bf.hasNext()){
			String tmp = bf.nextLine();
			String[] str = tmp.split(",");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			int c = Integer.parseInt(str[2]);
			if(c >= a+b) continue;
			if(a == b) hishi++;
			else if(a*a+b*b==c*c) tyou++;
		}
		System.out.println(tyou);
		System.out.println(hishi);
	}
}

Measured memory_bytes: 17136
import numpy as np

def main():
    #n = int(input())
    x,n = map( int, input().split())
    if n == 0:
        print(x)
    else:
        p = list(map( int, input().split()))

        l = []
        for i in range(-100,120):
            if i not in p:
                l.append(i)
        
        l2 = []
        if x not in p:
            print(x)
        else:
            for j in range(1,101):
                nump = x+j
                numm = x-j
                if numm in l:
                    l2.append(numm)
                if nump in l:
                    l2.append(nump)
                if len(l2)>0:
                    break
            print(l2[0])

        
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 27128
n,m=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
x=[0,2,5,5,4,5,6,3,7,6]
d=dict()
for j in l:
    d[x[j]]=j
INF=float('inf')
dp=[-INF for i in range(n+1)]
dp[0]=0
l=d.keys()
for i in range(2,n+1):
    for j in d.keys():
        if j<=i:
            dp[i]=max(dp[i],dp[i-j]*10+d[j])
print(dp[n])

Measured memory_bytes: 14668
#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>;

int main(){
	int N;
	cin>>N;
	vector<int>a(N);
	rep(i,N){
		cin>>a.at(i);
	}
	int b=1;
	for(int i=0;i<N;i++){
		b=a.at(b-1);
		if(b==2){
			cout<<i+1<<endl;
			return 0;
		}
	}
	cout<<-1<<endl;
return 0;}

/*compile
g++ code.cpp
./a.out
run*/

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

using ll = long long;

int main() {
    int A, B, K;
    cin >> A >> B >> K;
    rep(i, K / 2) {
        if (A % 2) A--;
        A /= 2;
        B += A;
        if (B % 2) B--;
        B /= 2;
        A += B;
    }
    if (K % 2) {
        if (A % 2) A--;
        A /= 2;
        B += A;
    }
    cout << A << " " << B << "\n";
}

Measured memory_bytes: 256
#include <assert.h>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
 
using ll = long long;
using P = std::pair<ll, ll>;
 
#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " << i << std::endl
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
ll pow_mod(ll a, ll b, ll mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }
 
  ll x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;


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

  ll n;
  std::cin>>n;

  std::vector<P> a(n),b(n);
  std::vector<ll> tempa(n),tempb(n);
  rep(i,0,n){
    ll temp;
    std::cin>>temp;
    a[i]={temp,i};
    tempa[i]=temp;
  }
  rep(i,0,n){
    ll temp;
    std::cin>>temp;
    b[i]={temp,i};
    tempb[i]=temp;
  }

  std::sort(all(a));
  std::sort(all(b));

  rep(i,0,n){
    if(a[i].first>b[i].first){
      std::cout<<"No\n";
      return 0;
    }
  }


  for(ll i=n-1;i>0;i--){
    if(a[i].first<=b[i-1].first){
      std::cout<<"Yes\n";
      return 0;
    }
  }

  std::set<ll> used;

  ll now=0;
  ll sortitr=(ll)(std::lower_bound(all(a),P(tempa[now],now))-a.begin());
  now=b[sortitr].second;
  used.insert(now);
  while(now!=0){
    sortitr=(ll)(std::lower_bound(all(a),P(tempa[now],now))-a.begin());
    now=b[sortitr].second;
    used.insert(now);
  }

  if(used.size()!=n)std::cout<<"Yes\n";
  else std::cout<<"No\n";

  return 0;
}

Measured memory_bytes: 9600
#pragma gcc optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = __int128_t;
const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    vector<ll> ps(n);
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ps[i] = (a[i] + (!i ? 0 : ps[i - 1]));
    }
    for (int i = 0; i < n; ++i) {
        ans += ((ps[n - 1] - ps[i]) * a[i]) % MOD;
        ans %= MOD;
    }
    cout << ans << '\n';
}

Measured memory_bytes: 7120
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


def solve(K: int):
    def _make(s, idx):
        if idx > 0:
            if s[idx] == '9':
                return None
            prev = int(s[idx - 1])
            cur  = int(s[idx]) + 1
            if abs(prev - cur) > 1:
                return None
        if idx == 0 and s[idx] == '9':
            return '1' + ('0' * len(s))

        ret = s[:idx]
        ret += str(int(s[idx]) + 1)
        for _ in s[idx + 1:]:
            ret += str(max(0, int(ret[-1]) - 1))
        return ret

    def get_next(s):
        idx = 0
        l = len(s)
        for idx in range(l)[::-1]:
            tmp = _make(s, idx)
            if tmp is not None:
                return tmp
        return None

    val = '0'
    for i in range(K):
        val = get_next(val)
    print(val)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
# -*- coding: utf-8 -*-

x, y = map(int, input().split())

result = 0

if x == 1:
    result += 300000
elif x == 2:
    result += 200000
elif x == 3:
    result += 100000

if y == 1:
    result += 300000
elif y == 2:
    result += 200000
elif y == 3:
    result += 100000
    
if x == 1 and y == 1:
    result += 400000
    
print(result)

Measured memory_bytes: 38384
using System;
class GoodDistance{
	public static void Main(){
		string[] str1 = Console.ReadLine().Split(' ');
		int n = int.Parse(str1[0]);
		int d =int.Parse(str1[1]);
		int count=0;
		float[,] pos= new float[n,d];
		for(int a=0;a<n;a++){
			string[] str2 = Console.ReadLine().Split(' ');
			for(int b=0;b<d;b++){
				pos[a,b] = int.Parse(str2[b]);
			}
		}

		for(int a=0;a<n-1;a++){
			for(int b=a+1;b<n;b++){
				float total=0;
				for(int c=0;c<d;c++){
					total+=(pos[a,c]-pos[b,c])*(pos[a,c]-pos[b,c]);
				}
				if((int)Math.Sqrt(total)==Math.Sqrt(total)){
					count++;
				}
			}
		}
		Console.WriteLine("{0}",count);
	}
}


Measured memory_bytes: 13140
n, k = map(int, input().split())

s = input()

if s[k-1] == 'A':
    t = 'a'
elif s[k-1] == 'B':
    t = 'b'
elif s[k-1] == 'C':
    t = 'c'

s = s[:k-1] + t + s[k:]

print(s)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

using namespace std;

#define FOR(a,b) for(int a=0;a<b;a++)
#define F0R(a,b,c) for(int a = b; a<=c; a++)
#define f first
#define s second
#define m0(x) memset(x,0,sizeof(x))

typedef pair<int,int> pi;
typedef long long ll;
typedef vector<int> vi;
typedef vector<pi> vpi;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int a[11]; m0(a);
    int k; cin >> k;
    int fr = 0;
    FOR(lol,k){
        bool good = false;
        FOR(i,fr){
            if((a[i]-1 == a[i+1]) || (a[i] == 9 && a[i+1] == 9)) continue;
            good = true;
            a[i]++;
            for(int j = i-1; j>= 0; j--) a[j] = max(0,a[j+1]-1);
            break;
        }
        if(!good){
            if(a[fr] == 9){
                fr++; a[fr] = 1;
                FOR(i,fr) a[i] = 0;
            }else{
                a[fr]++;
                for(int i = fr-1; i >= 0; i--) a[i] = max(0,a[i+1]-1);
            }
        }
    }
    for(int i = fr; i>=0; i--) cout << a[i];
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
ans = 10**9
for i in range(1,n):
    ans_a = 0
    ans_b = 0
    a = str(i)
    b = str(n-i)
    for j in a:
        ans_a += int(j)
    for k in b:
        ans_b += int(k)
    ans = min(ans,ans_a+ans_b)
print(ans)


Measured memory_bytes: 3060
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    cnt = 0
    total = 0
    mi = f_inf
    for a in A:
        total += abs(a)
        if a < 0:
            cnt += 1
        if mi > abs(a):
            mi = abs(a)

    if cnt % 2 == 0:
        print(total)
    else:
        print(total - mi * 2)


def resolve2():
    n = int(input())
    A = list(map(int, input().split()))

    dp = [[0 for _ in range(2)] for _ in range(n + 1)]
    dp[0][1] = -f_inf
    for i in range(1, n + 1):
        dp[i][0] = max(dp[i - 1][0] + A[i - 1], dp[i - 1][1] - A[i - 1])
        dp[i][1] = max(dp[i - 1][0] - A[i - 1], dp[i - 1][1] + A[i - 1])

    print(dp[n][0])


if __name__ == '__main__':
    resolve2()


Measured memory_bytes: 32756
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

readString = map BS.unpack . BS.words

getString = readString <$> BS.getLine

seek :: String -> Bool
seek [s] = True
seek (s : ss)
  | s `elem` ss = False
  | otherwise = seek ss

main = do
  [s] <- getString
  if seek s
    then putStrLn "yes"
    else putStrLn "no"


Measured memory_bytes: 380
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5100;
const int mod=1e9+7;
struct edge
{
	int to,nxt;
}e[maxn*2];
int h[maxn],E;
int n; 
int dp[maxn][maxn],t[maxn];
int sz[maxn];
void add(int u,int v)
{
	E++;
	e[E].to=v;
	e[E].nxt=h[u];
	h[u]=E;
	return;
}
void dfs(int u,int fa)
{

	sz[u]=1;
	for(int i=1;i<=n;i++) dp[u][i]=0;
	dp[u][1]=1;
	for(int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
		for(int i=0;i<=sz[u]+sz[v];i++) t[i]=0;
		for(int j=1;j<=sz[u];j++)
		{
			for(int k=0;k<=sz[v];k++)
			{
				t[j+k]+=dp[u][j]*dp[v][k]%mod;
				t[j+k]%=mod;
			}
		}
		sz[u]+=sz[v];
		for(int j=1;j<=sz[u];j++) dp[u][j]=t[j];
	}
	int base=1;
	dp[u][0]=0;
	for(int i=2;i<=sz[u];i+=2)
	{
		base=base*(i-1)%mod;
		dp[u][0]+=dp[u][i]*base%mod;
		dp[u][0]%=mod;
	}
	dp[u][0]=(mod-dp[u][0])%mod;
	return;
}
signed main()
{
	scanf("%lld",&n);
	int u,v;
	for(int i=1;i<=n-1;i++)
	{
		scanf("%lld%lld",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	printf("%lld\n",(mod-dp[1][0])%mod);
	return 0;
}


Measured memory_bytes: 201472
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;
constexpr ll MOD = 1e9 + 7;
constexpr ll INF = 1LL << 60;



int main() {
  cin.tie(0); ios_base::sync_with_stdio(false);
  int n;string s;
  cin >> n >> s;
  for(auto &c : s) {
    c += n;
    if(c > 'Z') {
      c = 'A' + (c - 'Z' - 1);
    }
  }
  cout << s;
  return 0;
}


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

#define INF (1<<31-1)

int main(){

	int N;
	int A[100000];

	cin >> N;
	for(int i=0; i<N; i++)
		cin >> A[i];

	sort(A, A + N);
	int m = A[N-1];

	int d = INF, r;
	for (int i = 0; i < N; i++){
		if (m % 2 == 0){
			if (abs(A[i] - m / 2) < d){ d = abs(A[i] - m / 2); r = A[i]; }
		}
		else{
			if (abs(A[i] - m / 2) < d){ d = abs(A[i] - m / 2); r = A[i]; }
			if (abs(A[i] - (m + 1) / 2) < d){ d = abs(A[i] - (m + 1) / 2); r = A[i]; }
		}
	}


	cout << m << " " << r << endl;	

	return 0;
}


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

int main()
{
    int x;
    cin >> x;
    if (x >= 1800)
        cout << 1 << endl;
    else if (x >= 1600)
        cout << 2 << endl;
    else if (x >= 1400)
        cout << 3 << endl;
    else if (x >= 1200)
        cout << 4 << endl;
    else if (x >= 1000)
        cout << 5 << endl;
    else if (x >= 800)
        cout << 6 << endl;
    else if (x >= 600)
        cout << 7 << endl;
    else if (x >= 400)
        cout << 8 << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;

const ll M = 998244353;

vector<ll> fac(300001);
vector<ll> ifac(300001);

ll mpow(ll x, ll n){
  ll ans = 1;
  while(n != 0){
    if(n&1) ans = ans*x % M;
    x = x*x % M;
    n = n >> 1;
    }
  return ans;
}

ll comb(ll a, ll b){
  if( a == 0 && b == 0) return 1;
  if( a < b || a <  0) return 0;
  ll tmp = ifac[a-b]* ifac[b] % M;
  return tmp*fac[a]%M;
}

int main(){
  ll n, k;
  ll  a, b;
  cin >> n >> a >> b >> k;

  fac[0] = 1;
  ifac[0] = 1;
  for(ll i = 0; i < 300000; i++){
    fac[i+1] = fac[i]*(i+1) % M;
    ifac[i+1] = ifac[i]*mpow(i+1, M-2) % M;
  }

  ll ans = 0;

  for(ll i = 0; i <= n; i++){
    if(a * i > k) break;
    if((k-a*i) < 0) continue;
    if((k - a*i)%b) continue;
    int t1 = i, t2 = (k - a*i)/b;
    if(t2 > n || t2 < 0) continue;
    ans = (ans + comb(n,t1)*comb(n,t2))%M;
    ans %= M;
  }
  if(ans < 0) ans = (ans+M)%M;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 7868
#include <iostream>
#include <cstring>
#include <algorithm>
#define MOD 1000000007
using namespace std;

long long int n, k, arr[101], dp[101][100001], pre[101][100001], top=0;

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>arr[i];
		top+=arr[i];
	}
	sort(arr, arr+n);
	for(int i=0;i<=min(k, arr[0]);i++){
		dp[0][i]=1;
		pre[0][i]=i+1;
	}
	long long int ek=arr[0];
	for(long long int i=1;i<n;i++){
		dp[i][0]=1;
		pre[i][0]=1;
		for(long long int j=1;j<=min(arr[i]+ek, k);j++){
			if(j-arr[i]-1>-1)
				dp[i][j]=(pre[i-1][min(j, ek)]-pre[i-1][j-arr[i]-1]+MOD)%MOD;
			else 
				dp[i][j]=pre[i-1][min(j, ek)];
			pre[i][j]=(dp[i][j]+pre[i][j-1])%MOD;
		}
		if(ek<=k)
			ek+=arr[i];
	}
	cout<<dp[n-1][k];
	return 0;
}


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

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

long long gcd_vec(vector<long long> const &A) {
    int size = (int)A.size();
    long long ret = A[0];
    for (int i = 1; i < size; i++) {
        ret = gcd(ret, A[i]);
    }
    return ret;
}

int main() {
    long long N, X;
    cin >> N >> X;
    vector<long long> x(N), A(N);
    for (int i = 0; i < N; i++) {
        cin >> x.at(i);
        A[i] = abs(X - x[i]);
    }
    cout << gcd_vec(A) << endl;
}


Measured memory_bytes: 1792