akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

int mp[101][101];
int w, h;
int gx, gy;

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

bool dfs(int y, int x, int c)
{
	if (y < 1 || y > h || x < 1 || x > w || mp[y][x] != c) return false;

	if (y == gy && x == gx) return true;

	mp[y][x] = 0;

	bool res = false;

	for (int i = 0; i < 4; ++i) res = res || dfs(y + dy[i], x + dx[i], c);

	return res;
}

int main()
{
	while (cin >> w >> h, w || h) {
		int sx, sy;
		cin >> sx >> sy >> gx >> gy;
		int n; cin >> n;
		while (n--) {
			int c, d, x, y; cin >> c >> d >> x >> y;
			if (d) {
				for (int i = 0; i < 4; ++i) for (int j = 0; j < 2; ++j) mp[y+i][x+j] = c;
			} else {
				for (int i = 0; i < 2; ++i) for (int j = 0; j < 4; ++j) mp[y+i][x+j] = c;
			}
		}

		cout << (dfs(sy, sx, mp[sy][sx]) ? "OK" : "NG") << endl;
	}
}

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

using namespace std;

const int MOD = 1e9 + 7;
const long long INF = 1e18;
const int MaxN = 16;

long long dp[1 << MaxN];
int a[MaxN][MaxN];
int n;

long long gc[1 << MaxN];

long long groupCost(int mask)
{
    long long ans = 0;

    for(int i1 = 0; i1 < n; ++i1)
        if(mask & (1 << i1))
            for(int i2 = i1 + 1; i2 < n; ++i2)
                if(mask & (1 << i2))
                    ans += a[i1][i2];

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);

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

    for(int mask = 1; mask < (1 << n); ++mask)
        gc[mask] = dp[mask] = groupCost(mask);

    for(int mask = 1; mask < (1 << n); ++mask)
    {
        for(int subMask = (mask & (mask - 1)); subMask; subMask = mask & (subMask - 1))
        {
            dp[mask] = max(dp[mask], dp[subMask] + dp[mask ^ subMask]);
        }
    }

    cout << dp[(1 << n) - 1] << '\n';

    return 0;
}



Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <map>
#include <algorithm>

using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    map<string, ll> m;
    for(int i = 0; i < n; ++i){
        string tmp;
        cin >> tmp;
        sort(tmp.begin(), tmp.end());
        m[tmp]++;
    }
    ll ans = 0;
    for(auto it = m.begin(); it != m.end(); ++it){
        ans += it->second * (it->second - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(j,n) for(int j = 0; j < (n); ++j)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define drep2(j,n) for(int j = (n)-1; j >= 0; --j)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define srep2(j,s,t) for (int j = s; j < t; ++j)
#define srep3(k,s,t) for (int k = s; k < t; ++k)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  int N;
  cin >> N;
  int ans = INF;
  srep(i,1,N) {
    int a = i;
    int b = N - i;
    int asum = 0;
    int bsum = 0;
    while(a > 0) {
      asum += a % 10;
      a = a / 10;
    }
    while(b > 0) {
      bsum += b % 10;
      b = b / 10;
    }
    ans = min(ans,asum+bsum);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<cmath>
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
stack<int> st;
queue<int> qu;
queue<pair<int,int> > qu2;
priority_queue<int> pq;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep2(i,n) for(int i=1; i<=(int)(n); i++)
#define mins(x,y) x=min(x,y)
#define maxs(x,y) x=max(x,y)
typedef set<int> set_t;
typedef set<string> set_g;
typedef complex<double> xy_t;
static const int NIL = -1;
static const int INF = 1000000007;
#define mp make_pair
#define sz(x) int(x.sise())
#define mod 1000000007
#define reps(i,s,n) for(int i = s; i < n; i++)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
deque<int> deq;
#define fi first
#define se second
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
typedef pair<int, int> P;
int main(){
    ll a,b,v,w,t;
    cin >> a>> v>>b>>w>>t;
    if(abs(a-b)>abs(v-w)*t||(v<w&&a!=b)){
        cout<<"NO"<<endl;
    }else{
        cout<<"YES"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,x,ans;
LL pow2[50];
map<int,int>mp;
priority_queue<int>pq;
int main()
{
    pow2[0]=1;
    for(int i=1;i<=31;i++)pow2[i]=pow2[i-1]*2;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        mp[x]++;
        pq.push(x);
    }
    while(!pq.empty())
    {
        if(mp[pq.top()]==0)
        {
            pq.pop();
            continue;
        }
        mp[pq.top()]--;
        for(int i=31;i>-1;i--)
        {
            if(pow2[i]-pq.top()>pq.top())continue;
            if(mp[pow2[i]-pq.top()]>0)
            {
                mp[pow2[i]-pq.top()]--;
                ans++;
                break;
            }
        }
        pq.pop();
    }
    printf("%d",ans);
}


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


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

   int ans=0;

   for (int i = 0; i < s.size(); i++){
      if (s[i] != t[i]) ans++;
   }

   cout << ans << endl;
}


Measured memory_bytes: 3828
//AtCoder ABC083 A - Libra
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;

int main() {
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<(a+b>c+d?"Left":a+b==c+d?"Balanced":"Right")<<endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;

typedef
tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> orderedSet;

#define pb push_back
#define F first
#define S second
#define all(a) (a).begin(), (a).end()

#define for1(i0, l0, r0) for (int i0 = l0; i0 < r0; ++i0)
#define for2(i0, l0, r0) for (int i0 = l0; i0 <= r0; ++i0)
#define forn(i0, n0) for (int i0 = 0; i0 < n0; ++i0)
#define forn1(i0, n0) for (int i0 = 1; i0 < n0; ++i0)
#define forr(i0, n0) for (int i0 = n0; i0 >= 0; --i0)
#define forr1(i0, r0, l0) for (int i0 = r0; i0 > l0; --i0)
#define forr2(i0, r0, l0) for (int i0 = r0; i0 >= l0; --i0)

#define Sort(a) sort(all(a))
#define Reverse(a) reverse(all(a))

typedef long double ld;
#define ui unsigned int
#define ull unsigned long long

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<string> vs;

typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;

typedef vector<vi> vvi;
typedef vector<vd> vvd;
typedef vector<vll> vvll;
typedef vector<vb> vvb;

#define vpss vector<pss>
#define vvs vector<vs>
#define vvpii vector<vpii>
#define vvpll vector<vpll>
#define vpt vector<pt>
#define vvvi vector<vvi>
#define vsi vector<set<int>>
#define ss second
#define ff first

#define printvi(arr) for (int x0 : arr) cout << x0 << ' '; cout << '\n';
#define printvll(arr) for (ll x0 : arr) cout << x0 << ' '; cout << '\n';
#define printpair(pair0) cout << pair0.F << ' ' << pair0.S << '\n';
#define printvp(arr) for (auto pair0 : arr) printpair(pair0);
#define initArray(arr, N0, X0) memset(arr, X0, N0 * sizeof(int))
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void init() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout.precision(16);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
}

void solve() {
    int n;
    cin >> n;
    ll ans = 2;
    ll T = 1, A = 1;
    forn(i, n){
        ll t, a;
        cin >> t >> a;
        ll x = t + a;
        ll k = (ans + x - 1) / x;
        k = max(k, (T + t - 1) / t);
        k = max(k, (A + a - 1) / a);
        ans = k * x;
        T = k * t, A = k * a;
    }
    cout << ans << '\n';
}

bool multitest = false;

int main() {
    init();
    int t = 1;
    if (multitest) cin >> t;
    forn(i, t) solve();
}

Measured memory_bytes: 3644
#include<stdio.h>

int main(void){
    
    char S[5],i;
    
    scanf("%s",S);

    for(i = 0;i < 4;i++){
        if(S[i] == S[i + 1]){
            printf("Bad");
            return 0;
        }
    }
    
    printf("Good");
    return 0;
}

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

using namespace std;

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

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int N, A, B;
	
	
	cin>>N>>A>>B;
	
	if((B - A)%2 == 0) {
		cout<<(B - A) / 2 <<endl;
	} else {
		int ans = min(B - 1, N - A);
		// cout<<B - 1<<" "<<N-A<<endl;
		if(B >= 3) {
			ans = min(ans, A + (B - (A) - 1)/2);
			// cout<<A + (B - (A) - 1)/2<<endl;
		}
		if(A <= N - 3) {
			ans = min(ans, (N - B + 1) + (N - (A + ((N - B + 1)))) / 2);
			// cout<< (N - B + 1) + (N - (A + ((N - B + 1)))) / 2<<endl;
		}
		
		cout<<ans<<endl;
	}
	
	
	return 0;
}

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

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

#define pow CHANGETHENAMESTUPID

using namespace std;

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

void load() {

}

void solve() {
	int n, m; scanf("%d%d", &n, &m);
	int sum = 0;
	bool ac[n]; FOR(i, n) ac[i] = false;
	int a[n]; FOR(i, n) a[i] = 0;
	FOR(i, m) {
		char s[5];
		int x;
		scanf("%d %s", &x, s);
		x--;
		if (s[0] == 'A') ac[x] = true;
		else if (!ac[x]) a[x]++;
	}
	int cnt = 0;
	FOR(i, n) if (ac[i]) { cnt++; sum += a[i]; }
	printf("%d %d\n", cnt, sum);
}

int main() {
	load();
	solve();
	return 0;
}


Measured memory_bytes: 768
// --https://kenkoooo.com/atcoder/#/table/soma62jp
#include <iostream>
#include <string>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstring>

using namespace std;

int main(int argc, char* argv[]) {

	int N, K;
	int ans = 0;

	cin >> N >> K;

	vector<int>l(N);

	for (int i = 0; i < N; i++) {
		cin >> l[i];
	}

	sort(l.rbegin(), l.rend());

	for (int i = 0; i < K; i++) {
		ans += l[i];
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
li = list(map(int,input().split()))
N = li[0]
K = li[1]
Q = li[2]
score = [K] * N
for i in range(Q):
    A_i = int(input())
    A_i -= 1
    score[A_i] += 1
score = map(lambda x: x - Q, score)
score = list(score)
index_num = 0
for i in range(N):
    if score[index_num] <= 0:
        print("No")
    else:
        print("Yes")
    index_num += 1

Measured memory_bytes: 9860
package main

import "fmt"

func main() {
	var (
		n, q, sum int
		s         []int
	)
	fmt.Scan(&n)
	s = make([]int, n)
	for i := range s {
		fmt.Scan(&s[i])
	}

	fmt.Scan(&q)
	var tmp int
	for i := 0; i < q; i++ {
		fmt.Scan(&tmp)
		if biSearch(s, tmp) {
			sum++
		}
	}
	fmt.Println(sum)

}

func biSearch(list []int, val int) bool {
	min := 0
	max := len(list)
	mid := (max + min) / 2
	for {
		// fmt.Println("min:", min, " mid:", mid, " max:", max)
		if list[mid] == val {
			return true
		} else if list[mid] < val {
			if min == mid {
				return false
			}
			min = mid
			mid = (max + min) / 2
		} else if list[mid] > val {
			if max == mid {
				return false
			}
			max = mid
			mid = (max + min) / 2
		}
	}
}



Measured memory_bytes: 5872
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <b; i++)
typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
#define trace(x) cout<<#x<<"="<<x<<"\n";
#define llp 1000000007
#define mod 1000000007

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    typename map< F , S >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define deb(x) cerr << #x << " = " << x << endl;


int32_t main(){
	ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vi b(n);
    REP(i,0,n){
        cin>>b[i];
    }
    vi ans(n);
    int maxi=1;
    for(int i=0;i<n;i++){
        if(b[i]>maxi){
            cout<<-1<<"\n";
            return 0;
        }
        for(int j=n-1;j>=b[i];j--){
            ans[j]=ans[j-1];
        }
        ans[b[i]-1]=b[i];
        maxi++;
    }
    REP(i,0,n){
        cout<<ans[i]<<"\n";
    }



	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int w[];
	static int v[];
	static int n, s;
	static long dp[][];

	public static long dp(int idx, int remw) {
		if (remw < 0)
			return -(int) 1e9;
		if (idx == n)
			return 0;
		if (dp[idx][remw] != -1) {
			return dp[idx][remw];
		}
		long take = v[idx] + dp(idx + 1, remw - w[idx]);
		long leave = dp(idx + 1, remw);
		return dp[idx][remw] = Math.max(take, leave);
	}

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		n = sc.nextInt();
		w = new int[n];
		v = new int[n];
		s = sc.nextInt();
		dp = new long[n + 1][s + 1];
		for (int j = 0; j < n + 1; j++) {
			Arrays.fill(dp[j], -1);
		}
		for (int i = 0; i < n; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		out.println(dp(0, s));
		out.flush();
		out.close();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}

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

int main(){
    char c;
    cin >> c;
    string vowel = "aeiou";
    for(int i=0; i<vowel.size(); i++){
        if (vowel.at(i) == c){
            cout << "vowel" << endl;
            return 0;
        }
    }
    cout << "consonant" << endl;
}

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;

  int D = max({A, B, C}) * 3 - A - B - C;

  cout << ((D % 2 == 0) ? D / 2 : (D + 3) / 2) << "\n";
}

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

int p[100000];

int main() {
  int n, rez;
#ifdef DEBUG
  freopen("codeforces.in", "r", stdin);
  freopen("codeforces.out", "w", stdout);
#endif
  scanf("%d", &n);
  for(int i = 0; i < n; ++i) {
    scanf("%d", &p[i]);
    --p[i];
  }
  rez = 0;
  for(int i = 0; i < n; ++i) {
    if(i + 1 < n && i == p[i] && i + 1 == p[i + 1]) {
      rez++;
      p[i + 1] = i;
    } else if(i == p[i])
      rez++;
  }
  printf("%d", rez);
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#define ULL unsigned long long
using namespace std;

int main()
{
  ULL A, B, N;
  cin >> A >> B >> N;
  
  ULL x = min(N, B-1);
  ULL ret = A * x / B - A * (x / B);
  
  cout << ret << endl;
}

Measured memory_bytes: 3636
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        string o = Console.ReadLine();
        string e = Console.ReadLine();

        for (int i = 0; i < e.Length; i++)
            Console.Write("{0}{1}", o[i], e[i]);

        if (o.Length > e.Length)
            Console.Write(o.Last());

        Console.WriteLine();
    }
}

Measured memory_bytes: 13268
h,w=map(int,input().split())
n=int(input())
a=list(map(int,input().split()))
temp=[]
for i in range(n):
    temp+=[str(i+1)]*a[i]

for i in range(h):
    if i%2==0:
        print(" ".join(temp[w*i:w*(i+1)]))
    else:
        print(" ".join(reversed(temp[w*i:w*(i+1)])))

Measured memory_bytes: 3700
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <random>

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

using namespace std;
typedef long long int ll;
const ll INF = 10000000000;
const double PI = acos(-1);
const ll mod = 1000000007;

double dp[3000][3000] = { 0.0 };

int main()
{
    int n;
    cin >> n;
    vector<double> p(n);
    rep(i, n) cin >> p[i];

    dp[0][0] = 1.0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i][j]   += dp[i - 1][j] * (1.0 - p[i - 1]);
            dp[i][j + 1] += dp[i - 1][j] * p[i - 1];
        }
    }

    double ans = 0.0;
    for (int i = n; i > (n / 2); i--) {
        ans += dp[n][i];
    }
    cout << std::fixed << std::setprecision(10) << ans << endl;
    return 0;
}


Measured memory_bytes: 49928
X, K, D = map(int, input().split())
 
Xa = abs(X)
Xs = Xa // D
Xm = Xa % D
 
if (K <= Xs):
    print(abs(Xa-D*K))
elif (K-Xs) % 2 == 0:
    print(abs(Xm))
else:
    print(abs(D-Xm))

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

#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (a); i >= (int)(b); i--)
#define all(x) (x).begin(), (x).end()
using i32 = int32_t;
using i64 = int64_t;
using f32 = float;
using f64 = double;
using P   = pair<int, int>;

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

template <class T>
void dump_vec(const vector<T>& v) {
    auto len = v.size();
    rep(i, 0, len) {
        cout << v[i] << (i == (int)len - 1 ? "\n" : " ");
    }
}

struct FastIO {
    FastIO() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} FASTIO;

//---------------------------------------------------------------------------------------------------

//---------------------------------------------------------------------------------------------------

vector<int> ds;
vector<int> fs;
vector<vector<int>> G;

int stamp = 0;

void dfs(int u) {
    if (ds[u] >= 0) return;
    ds[u] = ++stamp;

    for (auto& v : G[u]) {
        dfs(v);
    }
    fs[u] = ++stamp;
}

signed main() {
    int N;
    cin >> N;
    G.resize(N);
    ds.assign(N, -1);
    fs.assign(N, -1);
    rep(i, 0, N) {
        int id, k;
        cin >> id >> k;
        id--;
        rep(j, 0, k) {
            int u;
            cin >> u;
            u--;
            G[id].push_back(u);
        }
        sort(all(G[id]));
    }
    rep(i, 0, N) {
        dfs(i);
    }
    rep(i, 0, N) {
        cout << i + 1 << " " << ds[i] << " " << fs[i] << "\n";
    }
}



Measured memory_bytes: 3224
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]

    aaa = [0 for i in range(num)]
    for i in range(num):
        aaa[i] = (data[i][0] + data[i][1], i)
    aaa.sort(reverse=True)

    ans = 0
    # print(aaa)
    for i in range(num):
        ind = aaa[i][1]
        if i % 2:
            ans -= data[ind][1]
        else:
            ans += data[ind][0]

    print(ans)



if __name__ == '__main__':
    main()
    # test()



Measured memory_bytes: 69212
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<60;
#define all(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,k,n) for(int i=(k);i<(n);++i)

int main(){
    int N, K; cin >> N >> K;
    ll R, S, P; cin >> R >> S >> P;
    string T; cin >> T;
    ll dp[3][100005]; REP(i,3)REP(j,100005) dp[i][j] = 0;
    REP(j,N){
        if(j<K) {
            dp[0][j] = (T[j]=='s'?R:0);
            dp[1][j] = (T[j]=='p'?S:0);
            dp[2][j] = (T[j]=='r'?P:0);
        }
        else {
            dp[0][j] = max(dp[1][j-K],dp[2][j-K]) + (T[j]=='s'?R:0);
            dp[1][j] = max(dp[2][j-K],dp[0][j-K]) + (T[j]=='p'?S:0);
            dp[2][j] = max(dp[0][j-K],dp[1][j-K]) + (T[j]=='r'?P:0);
        }
    }
    ll ans = 0;
    for(int j=N-1; j>=N-K; j--) {
        ans += max(max(dp[0][j],dp[1][j]),dp[2][j]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2816
#include <iostream>
#include <map>
#include <vector>

using namespace std;

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

  double ans;
  if (n % 2 == 0) {
    ans = .5;
  } else {
    ans = double(n / 2 + 1) / n;
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int a,b,c,x,y;
    cin>>a>>c>>b>>x>>y;
    long long ans=0;
    if (b+b<=a+c)
    {
        int t=min(x,y);
        ans+=(long long)t*b*2;
        a=min(a,2*b);
        c=min(c,2*b);
        x-=t;
        y-=t;
        ans+=(long long)a*x+(long long)c*y;
    }
    else
    {
        ans+=(long long)a*x+(long long)c*y;
    }
    cout<<ans<<endl;
    return 0;
} 


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (n); ++i)
typedef long long ll;
 
const int mod = 1e9+7;
const int INF = 200000000;
 
int N,M,X;
ll ans = INF;
int A[15][15],C[15];
 
void dfs(int n, int m) {
    if(n == N) {
        vector<int> g(M,0);
        ll tmp = 0;
        for(int i=0;i<N;++i) {
            if(m & (1<<i)) {
                tmp += C[i];
                for(int j=0;j<M;++j) g[j] += A[i][j];
            }
        }
        for(int s:g) {
            if(s < X) return;
        }
        ans = min(ans, tmp);
        return;
    }
    dfs(n+1, m*10+0);
    dfs(n+1, m*10+1);
}
 
int main() {
    cin >> N >> M >> X;
    int a;
    for (int i = 0; i < N; i++)
    {
        cin >> C[i];
        for (int j = 0; j < M; ++j)
        {
            cin >> A[i][j];
        }
    }
    
    dfs(0,0);
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
}

Measured memory_bytes: 3580
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		System.out.println(solve());
	}

	public static int solve() {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int A = sc.nextInt();
		int res = H / A;
		
		return H % A == 0 ? res : res + 1;
	}
}


Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<utility>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iomanip>
#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i <= n; i++)
#define FORR(i, m, n) for(ll i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n)
#define MAX 100000
#define inf 1000000007
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

int main() {
    //cin高速化
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, ans, tmp;
    cin >> a;
    tmp = 100;
    ans = 0;
    while(tmp < a){
        tmp = tmp*1.01;
        ans++;
    }

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

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define op_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define fo(i,a,b) for(int i=a; i <b; i++)
#define pb push_back
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef map<int,int> mpii;
typedef map<ll,ll> mpll;
typedef map<int,ll> mpil;
typedef map<ll,int> mpli;

int main(){
  op_io;
  int n,m;
  cin>>n>>m;
  vvi g(n+1, vi());
  fo(i,0,m){
    int u,v;
    cin>>u>>v;
    g[u].pb(v);
    g[v].pb(u);
  }
  
  vi par(n+1,-1);
  vector<bool> vis(n+1, false);
  queue<int> q;
  q.push(1);
  par[1] = 0;
  vis[1] = true;
  while(!q.empty()){
    int u = q.front();
    q.pop();
    fo(i,0,g[u].size()){
      int v = g[u][i];
      if(vis[v]){
	continue;
      }
      q.push(v);
      vis[v] = true;
      par[v] = u;
    }
  }
  bool found = true;
  fo(i,2,n+1){
    if(par[i] == -1){
      found= false;
      break;
    }
  }
  if(!found){
    cout<<"No"<<endl;
  }else{
    cout<<"Yes"<<endl;
    fo(i,2,n+1){
      cout<<par[i]<<endl;
    }
  }
  
  return 0;
}


Measured memory_bytes: 10312
#include <iostream>
#include <cmath>

using namespace std;

bool is_pow(int x) {
  for (int i = 1; i <= sqrt(x); i++) {
    if (x == i * i) {
      return true;
    }
  }
  
  return false;
}

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

  int x[n][d];
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < d; j++) {
      cin >> x[i][j];
    }
  }
  int count = 0;
  int di,d2;
  
  for(int ix = 0; ix < n; ix++) {
    for(int iy = ix + 1; iy < n; iy++) {
      d2 = 0;
      for(int j = 0; j < d; j++) {
        di = x[ix][j] - x[iy][j];
        d2 += di * di;
      }
      
      if (is_pow(d2)) {
        count++;
      }
    }
  }
  
  cout << count << endl;
  
  return 0;
}


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

int n,a[210],ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=2*n;++i)
	scanf("%d",&a[i]);
	n*=2;
	sort(a+1,a+n+1);
	for(int i=n-1;i>=1;i-=2)
	ans+=a[i];
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
int main()
{
int i=1,n,q,t,j,a,b,c,d;
cin>>a;
cin>>b;
cin>>c;
cin>>d;
while(a>0 && c>0)
{
    if(i%2!=0)
    c=c-b;
    else a=a-d;
    i++;
}
if(c<=0)
    cout<<"Yes"<<endl;
else cout<<"No"<<endl;






return 0;
}


Measured memory_bytes: 3632
package main

import "fmt"

func main() {
	var sp, t string
	fmt.Scan(&sp, &t)

	begin := make([]int, 0)
	for i := 0; i < len(sp); i++ {
		flag := false
		for j := 0; j < len(t) && i+j < len(sp); j++ {
			if !(sp[i+j] == t[j] || sp[i+j] == '?') {
				break
			}
			if j == len(t)-1 {
				flag = true
			}
		}
		if flag {
			begin = append(begin, i)
		}
	}

	if len(begin) == 0 {
		fmt.Println("UNRESTORABLE")
		return
	}

	candinates := make([]string, len(begin))
	for j, k := range begin {
		s := ""
		for i := range sp {
			if i >= k && i < k+len(t) {
				s += string(t[i-k])
			} else if sp[i] == '?' {
				s += string('a')
			} else {
				s += string(sp[i])
			}
		}
		candinates[j] = s
	}

	var min string
	for i, str := range candinates {
		if i == 0 || str < min {
			min = str
		}
	}
	fmt.Println(min)
}


Measured memory_bytes: 640
<?php

fscanf(STDIN, "%d", $a);

switch ($a) {
    case 25:
        // code...
        echo "Christmas";
        break;
        
    case 24:
        // code...
        echo "Christmas Eve";
        break;
        
    case 23:
        // code...
        echo "Christmas Eve Eve";
        break;  
    
    case 22:
        // code...
        echo "Christmas Eve Eve Eve";
        break;  
    
    default:
        break;
}

?>

Measured memory_bytes: 16064
n,m = map(int,input().split())
h = list(map(int,input().split()))
ab =[]
for i in range(m):
    ab.append(list(map(int,input().split())))

ab = list(map(list,set(map(tuple,ab))))
i =0
an =[0]*n
while i < len(ab):
    if h[ab[i][0]-1]>h[ab[i][1]-1]:
        an[ab[i][1]-1]=1
        i += 1
    elif h[ab[i][0]-1]<h[ab[i][1]-1]:
        an[ab[i][0]-1]=1
        i += 1
    else:
        an[ab[i][1]-1]=1
        an[ab[i][0]-1]=1
        i += 1

print(an.count(0))

Measured memory_bytes: 50260
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define all(x) (x).begin(), (x).end()

using namespace __gnu_pbds;
using namespace std;

using ull = unsigned long long;
using ll = long long;
using ld = long double;
template <typename T> using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 1e9 + 7;
const int inf = INT_MAX;
const int N = 2e5 + 5;

int n, k, a[N];

bool f(int l) {
    ll c = 0;

    for (int i = 0; i < n; i++) {
        if (a[i] > l)
            c += (a[i] + l - 1) / l - 1;
    }

    return c <= k;
}

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

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

    int lo = 1, hi = *max_element(a, a + n);

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (f(mid))
            hi = mid;
        else lo = mid + 1;
    }

    cout << lo << "\n";
    return 0;
}

Measured memory_bytes: 4324
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<map>
using namespace std;

int main(){
//srandom((unsigned long)time(NULL));

long long n,k;
cin>>n>>k;

long long ans=k;
for(int i=0;i<n-1;i++){
    ans=ans*(k-1);
}

cout<<ans<<endl;

return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int maxn=100+10;
const int INF=(1<<21);
int n;
int p[maxn];
int dp[maxn][maxn];
int main()
{
//    freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d%d",&p[i],&p[i+1]);
    }

    for(int i=0; i<n; i++)
    {
        dp[i][i]=0;

    }
    for(int len=2;len<=n;len++)
    {
        for(int i=0;i<n-len+1;i++)
        {
            int j=i+len-1;
            dp[i][j]=INF;
            for(int k=i;k<j;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i]*p[k+1]*p[j+1]);
            }
        }
    }
    printf("%d\n",dp[0][n-1]);

    return 0;
}

Measured memory_bytes: 3228
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def is_same_root(self, x, y):
        return self.find(x) == self.find(y)

    def get_group_size(self, x):
        return -self.parents[self.find(x)]

N, M, K = map(int, input().split())
uf = UnionFind(N)

friends = defaultdict(set)
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    friends[u].add(v)
    friends[v].add(u)
    uf.union(u, v)
blocks = [0]*N
for _ in range(K):
    u, v = map(lambda x: int(x)-1, input().split())
    if uf.is_same_root(u, v):
        blocks[u] += 1
        blocks[v] += 1

res = [uf.get_group_size(i)-len(friends[i])-blocks[i]-1 for i in range(N)]
print(' '.join(map(str, res)))


Measured memory_bytes: 55688
# coding: utf-8
# Your code here!


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

from math import atan2, pi
#n = int(input())
a,b,x = [int(i) for i in readline().split()]

if a*a*b/2 > x:
    c = (x)*2/b/a
    print(atan2(b,c)*360/2/pi)

else:
    c = 2*(a*a*b-x)/a/a
    print(atan2(c,a)*360/2/pi)
    









Measured memory_bytes: 3060
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()
#define pl pair<ll,ll>
#define fi first
#define se second
#define inf 1000000007

ll N;
string S;
vector<ll> E(300010,0);
vector<ll> W(300010,0);

int main() {
    cin >> N;
    cin >> S;
    rep(i,S.size()){
        if (S[i] == 'E'){
            E[i+1] = E[i]+1;
            W[i+1] = W[i];
        }
        else{
            E[i+1] = E[i];
            W[i+1] = W[i]+1;
        }
    }
    ll ans = inf;
    repi(i,1,N+1){
        ll temp;
        temp = W[i-1]+E[N]-E[i];
        ans = min(ans,temp);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5508
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
const ll MOD=1000000007;
const long double PI=3.14159265358979;
const ll MAX=0;

int main() {
  ll N;
  cin>>N;
  ll A[N];ll B[N];
  for(int i=0;i<N;i++){
    cin>>A[i]>>B[i];
  }
  sort(A,A+N);sort(B,B+N);
  if(N%2==0){
    ll a=A[N/2-1]+A[N/2];ll b=B[N/2-1]+B[N/2];
    cout<<b-a+1;
  }
  else{
    ll a=A[N/2];ll b=B[N/2];
    cout<<b-a+1;
  }
}


Measured memory_bytes: 6764
#include <stdio.h>
#include <string.h>

int r_max,n;
int order[252];
char visited[252];
char start_visit[252];

void can_arrive_pre(int now) {
	int i;
	if(now>n+1 || start_visit[now])return;
	start_visit[now]=1;
	for(i=1;i<=r_max && now+i<=n+1;i++) {
		can_arrive_pre(now+i+order[now+i]>=0?now+i+order[now+i]:0);
	}
}

int can_arrive(int now) {
	int i;
	if(now+r_max>=n+1)return 1;
	if(visited[now])return 0;
	visited[now]=1;
	for(i=1;i<=r_max;i++) {
		if(can_arrive(now+i+order[now+i]>=0?now+i+order[now+i]:0))return 1;
	}
	return 0;
}

int main(void) {
	int i,ok;
	while(scanf("%d",&r_max)==1 && r_max>0) {
		scanf("%d",&n);
		for(i=1;i<=n;i++)scanf("%d",&order[i]);
		order[0]=order[n+1]=0;
		memset(start_visit,0,sizeof(start_visit));
		can_arrive_pre(0);
		if(!start_visit[n+1])puts("NG");
		else {
			ok=1;
			for(i=1;i<n+1;i++) {
				if(start_visit[i]) {
					memset(visited,0,sizeof(visited));
					if(!can_arrive(i)) {
						puts("NG");
						ok=0;
						break;
					}
				}
			}
			if(ok)puts("OK");
		}
	}
	return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
ll dp[3005][3005];

int main() {
  int N, S;
  cin >> N >> S;
  int A[N];
  for (int i=0; i<N; i++)
    cin >> A[i];
  dp[0][0] = 1;
  for (int i=0; i<N; i++) {
    int a = A[i];
    for (int j=0; j<=S; j++) {
      dp[i+1][j] += 2 * dp[i][j];
      dp[i+1][j] %= MOD;
      if (j+a <= S) {
        dp[i+1][j+a] += dp[i][j];
        dp[i+1][j+a] %= MOD;
      }
    }
  }
  cout << dp[N][S] << endl;
  return 0;
}

Measured memory_bytes: 74076
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

// one string
func strStdin() string {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	return strings.TrimSpace(scanner.Text())
}

//one int64
func int64stdin() int64 {
	stringin := strStdin()
	val, _ := strconv.ParseInt(strings.TrimSpace(stringin), 10, 64)
	return val
}

// eliminate space
func splitWithoutEmpty(stringTargeted string, delim string) []string {
	stringSplited := strings.Split(stringTargeted, delim)
	strs := []string{}

	for _, str := range stringSplited {
		if str != "" {
			strs = append(strs, str)
		}
	}
	return strs
}

//strings in line
func sliceStrsStdin(delim string) []string {
	stringin := strStdin()
	return splitWithoutEmpty(stringin, delim)
}

func sliceInt64Stdin() []int64 {
	splitted := sliceStrsStdin(" ")

	ret := make([]int64, len(splitted), len(splitted))

	for i := range splitted {
		val, _ := strconv.ParseInt(splitted[i], 10, 64)
		ret[i] = val
	}
	return ret
}

func main() {
	//str := strStdin()
	var str string
	fmt.Scanf("%s", &str)
	sum := 0

	for _, c := range str {
		sum += int(c - '0')
	}

	if sum%9 == 0 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}

}


Measured memory_bytes: 3280
n=int(input())
a=list(map(int,input().split()))
from collections import Counter as c
d=c(a)
s=0
for i in d.values():
  s+=i*(i-1)//2
for i in a:
  t=d[i]
  if t==1:
    print(s)
  else:
    print(s-(t*(t-1)//2)+((t-1)*(t-2)//2))

Measured memory_bytes: 24748
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int x;
    cin >> x;
    int p = 0;
    
    for (int i = 1; ; i++) {
        p += i;
        
        if (p >= x) {
            cout << i << endl;
            break;
        }
    }
    
    return 0;
}


Measured memory_bytes: 256
#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(){
    int x,a;
    cin >>x >>a;
    if(x<a) cout<<"0"<<endl;
    else cout<<10<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<stdio.h>
#define rep(i,n)for(int i=0;i<n;i++)
//printf("%.yf\n",x); xを小数点以下y桁で
using namespace std;
int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int o = 0, s = 0, n = 0, f = 0;
    if (a == 1 || b == 1 || c == 1 || d == 1) {
        o++;
    }
    if (a == 7 || b == 7 ||c == 7 || d == 7) {
        s++;
    }
    if (a == 9 || b == 9 || c == 9 ||d == 9) {
        n++;
    }
    if (a == 4 || b == 4 || c == 4 || d == 4) {
        f++;
    }
    if (o == 1 && s == 1 && n == 1 && f == 1) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int money[200005];
    int i=n;
    for(int i=0;i<n;++i)
    {
        cin>>money[i];
    }
    int MAX=-9999999999;
    int MIN=money[0];
    for(int i=1;i<n;++i)
    {
        MAX=max(MAX,money[i]-MIN);
        MIN=min(MIN,money[i]);
    }
    cout<<MAX<<endl;
    return 0;
}



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

typedef long long ll;
//loop
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//STL
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

//const
#define MOD 1000000007 //10^9+7:合同式の法

//acronym
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

void Main() {
    int x, y;
    cin >> x >> y;

    FOR(i,0,x) {
        int j = x - i;
        if (2 * i + 4 * j == y) {
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Main();
	return 0;
}


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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main() {
	int n = ri(), m = ri();
	int a[n];
	for (int i = 0; i < n; i++) a[i] = ri() - 1;
	
	int64_t base = 0; // always/out
	int64_t cost = 0; // in
	std::set<int> in;
	std::vector<int> diffs;
	std::vector<std::vector<int> > lower(m);
	std::vector<std::vector<int> > upper(m);
	for (int i = 0; i + 1 < n; i++) {
		int diff = (a[i + 1] + m - a[i]) % m;
		diffs.push_back(diff);
		if (diff > 1) {
			int high, low;
			if (a[i + 1] > a[i]) high = (a[i + 1] + 1) % m, low = (a[i] + 1) % m;
			else high = (a[i + 1] + m + 1) % m, low = (a[i] + 1) % m;
			upper[high].push_back(i);
			lower[low].push_back(i);
			assert(high != low);
			// std::cerr << "i:" << i << " (" << low << "," << high << ")" << std::endl;
			if (high < low) in.insert(i), cost += high;
			else base += diff;
		} else base += diff;
	}
	/*
	std::cerr << "cost:" << cost << std::endl;
	std::cerr << "base:" << base << std::endl;*/
	int64_t res = 100000000000;
	for (int i = 0; i < m; i++) {
		for (auto j : upper[i]) assert(in.count(j)), in.erase(j), base += diffs[j];
		cost -= in.size();
		for (auto j : lower[i]) assert(!in.count(j)), in.insert(j), cost += diffs[j] - 1, base -= diffs[j];
		// std::cerr << cost + base + in.size() << std::endl;
		res = std::min<int64_t>(res, cost + base + in.size());
	}
	std::cout << res << std::endl;
	return 0;
}


Measured memory_bytes: 15096
#include<stdio.h>

#define MAX_LENGTH 10
#define CHAR_MAX_LENGTH 10

int main(void)
{
        char line[MAX_LENGTH];
        char tmp;
        char ai[CHAR_MAX_LENGTH];
        int minus = 0;
        int i = 0;
        int a;
        long sum = 0;
        int min = 1000000;
        int max = -1000000;

        fgets(line, sizeof(line), stdin); //skip line

        while (1) {
                tmp = getchar();
                if (tmp == '-') minus = 1;
                else if ( ( tmp == ' ' ) || ( tmp == '\n' ) ) {
                        ai[i] = '\0';
                        sscanf(ai, "%d", &a);
                        if (minus == 1) {
                                a *= -1;
                                minus = 0;
                        }
                        i = 0;
                        sum += a;
                        if( a < min) min = a;
                        if( a > max) max = a;
                        // do process
                } else {
                        ai[i] = tmp;
                        i++;
                }
                if (tmp == '\n') break;
        }
        printf("%d %d %ld\n", min, max, sum);

        return 0;
}

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

#define int long long

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int n;
  cin >> n;

  vector<int> A(n);
  for ( int i = 0; i < n; i++ ) {
    cin >> A[i];
  }

  int ans = 0;
  for ( int i = 0; i < n; i++ ) {
    ans += A[i]/2;
    if ( i < n-1 && A[i]%2 && A[i+1] ) {      
      ans++;
      A[i+1]--;      
    }
  }

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


Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func allAtoi(num []string) []int {
	conv := make([]int, len(num))
	for i, item := range num {
		conv[i], _ = strconv.Atoi(item)
	}
	return conv
}

func main() {
	input := allAtoi(strings.Split(nextLine(), " "))
	a := input[0]
	b := input[1]
	if b%a == 0 {
		fmt.Println(a + b)
	} else {
		fmt.Println(b - a)
	}
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void) {
	long int K,A,B;
	scanf("%ld%ld%ld",&K,&A,&B);
	long bis=1;
	int cnt=K;
	
	if((A>=B)||(K<=A)){
		printf("%ld\n",bis+K);
	}else{
		cnt-=A+1;
		bis+=B-1;
		//printf("bis=%d\n",bis);
		//printf("cnt=%d\n",cnt);
		while(cnt>=2){
			cnt-=2;;
			bis+=(B-A);
			//printf("bis=%ld\n",bis);
		}
		//printf("bis=%d\n",bis);
		//printf("cnt=%d\n",cnt);
		if(cnt)bis++;
		if(bis>=1+K)printf("%ld\n",bis);
		else printf("%ld\n",K+1);
	}
	return 0;
}

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


int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;

    cout<<min(a,b)+min(c,d)<<endl;

    return 0;
}


Measured memory_bytes: 256
S = input()

dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
W = 'ABC'

MOD = 10 ** 9 + 7


def update1(i):
    for j in range(4):
        dp[i + 1][j] += dp[i][j] % MOD


def update2(i, c):
    ic = W.index(c)
    dp[i + 1][ic + 1] += dp[i][ic] % MOD


for i in range(len(S)):
    if S[i] == '?':
        for c in W:
            update1(i)
            update2(i, c)
    else:
        update1(i)
        update2(i, S[i])
print(dp[len(S)][-1] % MOD)


Measured memory_bytes: 29584